Численное решение и программная реализация задачи о провисании цепи

МИНИСТЕРСТВО  ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

НЕФТЕКАМСКИЙ  ФИЛИАЛ

ФЕДЕРАЛЬНОГО  ГОСУДАРСТВЕННОГО БЮДЖЕТНОГО ОБРАЗОВАТЕЛЬНОГО УЧРЕЖДЕНИЯ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО  ОБРАЗОВАНИЯ

  «БАШКИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

 

 

Экономико-математический факультет Кафедра математического  моделирования и информационной безопасности

 

 

 

КУРСОВАЯ работа

по дисциплине «Системный анализ»

на  тему

«Численное решение и программная реализация задачи о провисании цепи»

 

 

 

Выполнил: студент 4 курса  очной формы обучения группы М-41 Габдрахимова Г.С.______   Научный руководитель: к.ф.-м.н., доц. Сафина Г.Ф.

 

 

 

 

Нефтекамск 2012

СОДЕРЖАНИЕ

 

Введение	3
Численные методы решений систем нелинейных уравнений	6
Решение систем нелинейных уравнений	6
Метод Ньютона–Рафсона	7
Метод спуска	9
Метод простой итерации и метод Зейделя	13
Задача о провисании цепи	16
Постановка задачи	16
Вывод уравнения цепной линии	17
Вычисление длины плоской линии	20
3  Программная реализация решений задач	23
3.1 Программная реализация решения задачи о провисании цепи	23
3.1.1 Описание программы	23
3.1.2 Тестирование программы	23
3.2 Программная реализация метода  Ньютона – Рафсона	26
3.2.1 Описание программы	26
3.2.2 Тестирование программы	27
Заключение	31
Список использованных источников и  литературы	32
Приложение А Листинг программы  «Задача о провисании цепи»	33
Приложение Б Листинг программы «Метод Ньютона – Рафсона»	39

 

 

 

 

 

ВВЕДЕНИЕ

 

Решение систем нелинейных уравнений является одной из важных математических задач, возникающих в различных разделах физики, химии, биологии и других областях науки и техники.

В отличие от систем линейных уравнений  для систем нелинейных уравнений  не известны прямые методы решения. Лишь в отдельных случаях систему  можно решить непосредственно. Например, для системы из двух уравнений  иногда удается выразить одно неизвестное  через другое и таким образом  свести задачу к решению одного нелинейного  уравнения относительно одного неизвестного. Поэтому итерационные методы для  нелинейных систем приобретают особую актуальность.

Методы решений систем нелинейных уравнений были рассмотрены во всех учебниках по численным методам, в том числе в работах В.М. Вержбницкого¹, Н.С. Бахвалова², П.Ф. Фильчакова,³ Дж. Шнабеля, В.И. Киреева и А.В. Пантелеева⁴. В данных работах содержатся классические разделы численного анализа: метод алгебры, теории приближения функций одной переменной с их приложениями, разностные методы решения задач Коши, численные методы решения уравнений математической физики с двумя и тремя переменными. Приводится большое число пояснительных примеров, имеющих самостоятельную прикладную ценность и служащих справочным материалом.

В книгах Г. Корна, А. Жидкова и Н.С. Дубровской⁵ изложены методы решений систем линейных уравнений, методы решения нелинейных уравнений, интерполирование и экстраполирование, математическая обработка данных, численное интегрирование и дифференцирование. Теоретический материал иллюстрируется многочисленными примерами.

В книге С.А. Абрамова⁶ предложен курс программирования, разделенный на несколько частей: начальный курс и дополняющие. Начальный курс представляет собой выборку из языка, по объему и содержанию достаточную для изучения процедурного программирования. Остальные части учебника последовательно дополняют первую, включая специфические разделы, что в общем соответствует курсу объектно – ориентированного программирования, а также некоторые другие, избранные разделы. Специальный раздел посвящен решению задач программными методами.

В отличие от изученных работ  по численным методам, решению систем нелинейных уравнений в данной курсовой работе  решается задача провисания цепи численными методами и проводится программная реализация этого решения.

Целью курсовой работы является изучение и применение численных методов к задаче о провисании цепи и программная реализация задачи.

В соответствии с целью поставлены следующие задачи:

• изучение методов приближенного решения систем нелинейных уравнений (метод Ньютона – Рафсона, метод спуска, метод простой итерации и метод Зейделя);
• решение задачи о провисании цепи;
• программная реализация решения задачи.

Методы исследования. Поставленная задача решалась аналитически и с  применением вычислений на ЭВМ.

Практическая значимость работы состоит в том, что разработанная программа решения задачи о провисании цепи позволяет определить точные и приближенные значения расстояния цепи от земли и величину “отстояния” этого расстояния от первого столба.

Курсовая работа состоит  из введения, трех глав, заключения, списка литературы и приложения. Во введении проведен обзор литературы по теме исследования, указаны цели и задачи работы.

Первая глава посвящена  приближенным методам решения систем нелинейных уравнений. Приведены основные положения по методу Ньютона –Рафсона, методу спуска, методу простой итерации и методу Зейделя.

Вторая глава посвящена изучению задачи о провисании цепи. Приведен вывод уравнения цепной линии и вычисление длины плоской линии.

Третья глава содержит программную реализацию задачи о провисании цепи на языке Delphi.

В заключении подведены итоги  исследований, сделаны основные выводы.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЙ СИСТЕМ НЕЛИНЕЙНЫХ УРАВНЕНИЙ

 

1.1 Решение систем нелинейных уравнений

 

 

Систему нелинейных уравнений с n неизвестными можно записать в виде⁷

 

               (1.1)

 

 

Более коротко, в векторной форме , где – вектор неизвестных величин, – вектор – функция

 

 

, , .

 

 

В редких случаях  для решения такой системы  удается применить метод последовательного  исключения неизвестных и свести решение исходной задачи к решению  одного нелинейного уравнения с  одним неизвестным. Значения других неизвестных величин находятся  соответствующей подстановкой в  конкретные выражения. Однако в подавляющем  большинстве случаев для решения  систем нелинейных уравнений используются итерационные методы.⁸

В дальнейшем предполагается, что ищется изолированное решение  нелинейной системы.

Как и в случае одного нелинейного  уравнения, локализация решения  может осуществляться на основе специфической  информации по конкретной решаемой задаче (например, по физическим соображениям), и с помощью методов математического анализа. При решении системы двух уравнений, достаточно часто удобным является графический способ, когда месторасположение корней определяется как точки пересечения кривых на плоскости .

 

1.2 Метод Ньютона – Рафсона

 

Если определено начальное  приближение  итерационный процесс нахождения решения системы (1.1) методом Ньютона можно представить в виде⁹:

 

    (1.1.1)

 

где значения приращений определяются из решения системы линейных алгебраических уравнений, все коэффициенты которой выражаются через известное предыдущее приближение :

 

 

 

 

В векторно – матричной форме расчетные формулы имеют вид:

 

   (1.1.2)

 

где вектор приращений находится из решения уравнения (1.1.3).

 

.   (1.1.3)

 

Здесь – матрица Якоби первых производных вектор – функции

Выражая из (1.1.3) вектор приращений и подставляя его в (1.1.2), итерационный процесс нахождения решения можно записать в виде:

 

 

где – матрица, обратная матрице Якоби.

Для уменьшения арифметических действий Рафсон предложил не вычислять обратную матрицу, а вычислять поправки, как решение систем линейных уравнений, поэтому данный метод получил название метода Ньютона – Рафсона.

Использование метода Ньютона предполагает дифференцируемость функций и невырожденность матрицы Якоби ( ). В случае, если начальное приближение выбрано в достаточно малой окрестности искомого корня, итерации сходятся к точному решению, причем сходимость квадратичная.

В практических вычислениях в качестве условия окончания итераций обычно используется критерий

 

,     

 

где ε – заданная точность.

 

1.3 Метод спуска

 

Общий недостаток всех рассмотренных  выше методов решения систем нелинейных уравнений  состоит в локальном  характере сходимости, затрудняющем их применение в случаях, когда существуют проблемы с выбором начального приближения, обеспечивающего сходимость итерационной вычислительной процедуры. В этих случаях можно использовать численные методы оптимизации.¹⁰ Для использования наглядной геометрической интерпретации приводимых ниже рассуждений и их результатов ограничимся, рассмотрением системы, состоящей из двух уравнений с двумя неизвестными

 

     (1.3.1)

 

Из функций  , системы (1.3.1) образуем новую функцию

 

                                   (1.3.2)

 

Так как эта функция неотрицательная, то найдется точка (вообще говоря,

не  единственная) , такая, что

 

   

  

 

Следовательно, если тем или иным способом удается получить точку  , минимизирующую функцию , и если при этом окажется, что то точка - истинное решение системы (1.3.1), поскольку

 

 

 

Последовательность точек  - приближений к точке минимума функции - обычно получают по рекуррентной формуле

 

                                                                   (1.3.3)

 

 

где - вектор, определяющий направление минимизации, а - скалярная величина, характеризующая величину шага минимизации (шаговый множитель). Учитывая геометрический смысл задачи минимизации функций двух переменных - «спуск на дно» поверхности (рис. 1.3), итерационный метод (1.3.3) можно назвать методом спуска, если вектор при каждом k является направлением спуска (т.е. существует такое , что ) и если множитель подбирается так, чтобы выполнялось условие релаксации , означающее переход на каждой итерации в точку с меньшим значением минимизируемой функции.

Таким образом, при построении численного метода вида (1.3.2) минимизации функции следует ответить на два главных вопроса: как выбирать направление спуска и как регулировать длину шага в выбранном направлении с помощью скалярного параметра - шагового множителя . Приведем простые соображения по этому поводу.

При выборе направления спуска естественным является выбор такого направления, в котором минимизируемая функция убывает наиболее быстро.

 

Рисунок 1.3.1 - Пространственная интерпретация метода наискорейшего  спуска для функции (1.3.2)	Рисунок 1.3.2 - Траектория наискорейшего спуска для  функции (1.3.2)

 

Как известно из математического  анализа функций нескольких переменных, направление наибольшего возрастания функции в данной точке показывает ее градиент в этой точке. Поэтому примем за направление спуска вектор

 

- антиградиент функции . Таким образом, из семейства методов (1.3.2) выделяем градиентный метод

 

                                     .                          (1.3.4)

 

Оптимальный шаг в направлении  антиградиента - это такой шаг, при котором значение - наименьшее среди всех других значений Ф(х,у) в этом фиксированном направлении, т.е. когда точка является точкой условного минимума. Следовательно, можно рассчитывать на наиболее быструю сходимость метода (1.3.4). Если полагать в нем

 

            .          (1.3.5) 

   

Такой выбор шагового множителя, называемый исчерпывающим спуском, вместе с формулой (1.3.4) определяет метод наискорейшего спуска.

Геометрическая интерпретация  этого метода хорошо видна из рисунков (1.3.1), (1.3.2). Характерны девяностоградусные изломы траектории наискорейшего спуска, что объясняется исчерпываемостью спуска и свойством градиента (а значит, и антиградиента) быть перпендикулярным к линии уровня в соответствующей точке.

Наиболее типичной является ситуация, когда найти точно (аналитическими методами) оптимальное значение не удается. Следовательно, приходится делать ставку на применение каких - либо численных методов одномерной минимизации и находить  в (1.3.3) лишь приближенно.

Несмотря на то, что задача нахождения минимума функции одной  переменной намного проще, чем решаемая задача, применение тех или иных численных методов нахождения значений с той или иной точностью требует вычисления нескольких значений минимизируемой функции. Так как это нужно делать на каждом итерационном шаге, то при большом числе шагов реализация метода наискорейшего спуска в чистом виде является достаточно высокозатратной.

Зачастую успешной является такая стратегия градиентного метода, при которой шаговый множитель  в (1.3.3) берется либо сразу достаточно малым постоянным, либо предусматривается его уменьшение, например, делением пополам для удовлетворения условию релаксации на очередном шаге. Хотя каждый отдельный шаг градиентного метода при этом, вообще говоря, далек от оптимального, такой процесс по числу вычислений функции может оказаться более эффективным, чем метод наискорейшего спуска.

 

1.4 Метод простой итерации и метод Зейделя

 

При использовании метода простой итерации система уравнений (1.1) приводится к эквивалентной системе специального вида

 

 

Если выбрано некоторое  начальное приближение  последующие приближения в методе простой итерации находятся по формулам¹¹:

    (1.4.1)

 

Если последовательность векторов сходится, то она сходится к решению

Достаточное условие сходимости итерационного процесса (1.4.1) формулируется следующим образом:

Теорема.¹² Пусть вектор – функция непрерывна, вместе со своей производной

 

,

 

в ограниченной выпуклой замкнутой  области и 

 

 

где q – постоянная. Если и все последовательные приближения также содержатся в G, то процесс итерации (1.4.1) сходится к единственному решению уравнения в области G и справедливы оценки погрешности (∀k ∈N):

 

 

Метод Зейделя представляет собой некоторую модификацию  метода итераций. Он заключается в использовании уточненных значений переменных уже на текущем итерационном шаге. Так, для уточнения значений первой переменной используются только значения предыдущего шага, для второй переменной – значение , текущего шага, а остальных – от предыдущего и т.д.:

 

 

Указанные выше условия сходимости для простой итерации остается верной для итерации по методу Зейделя. Обычно метод Зейделя дает лучшую сходимость, чем метод простой итерации.

 

 

 

 

 

 

2 ЗАДАЧА О ПРОВИСАНИИ ЦЕПИ

 

2.1 Постановка задачи

 

Имеется цепь (однородная, гибкая, нерастяжимая, тяжелая нить) фиксированной длинны S подвешенная на двух «столбах» высотою  и  отстоящих друг от друга на расстоянии (пролет) – рисунок 1. Необходимо определить величину   – минимальное расстояние («зазор») цепи от земли и величину – "отстояние" этого зазора от первого столба, на котором у нас будет зафиксирована ось y. Ось х «лежит на земле».

 

 

Рисунок 2.1 – Схема задачи о провисании цепи

 

Если принять, что оси декартового  графика, отображающего формулу цепной линии, пересекаются в самой нижней точке, то формула цепной линии будет имеет такой общий вид:

 

.

 

Эта формула выводится в процессе решения дифференциального уравнения, составленного после анализа  баланса сил, действующего на бесконечно малый элемент цепи.

2.2 Вывод уравнения цепной  линии

 

Цепная линия – плоская  трансцендентная кривая, форму которой  принимает под действием силы тяжести однородная, гибкая, не растяжимая, тяжелая нить (цепь) с закрепленными концами.

Для того, чтобы вывести  уравнение цепной линии, выделим  бесконечно малый элемент нити  от точки до точки  и рассмотрим систему сил, действующих на него.

 

 

Рисунок 2.2 – Проекция на оси Оx и Oy

 

В точке А на нить действует  натяжение , направленное по касательной к кривой. Обозначим через  и его составляющие по осям координат. Соответственно в точке В имеется натяжение  с составляющими и . Кроме того, на элемент АВ действует сила тяжести  направленная вертикально вниз и равная по абсолютной величине , где – дифференциал дуги АВ, а – вес единицы длины нити. Для того, чтобы система сил находилась в равновесии, необходимо и достаточно, чтобы сумма проекций на каждую ось всех действующих сил была равна нулю. Приравнивая к нулю проекцию сил на ось Ох, получим:

 

 или 

 

т.е. горизонтальная составляющая натяжения нити есть величина постоянная.

Проецируя силы на ось Оу, получим:

 

.

 

С другой стороны, обозначив через «» угол, образованный касательной к кривой в точке А с осью Ох, получим:

 

 

 

Продифференцируем последнее  равенство по , учитывая, что :

 

 

 

Учитывая, что  и , получим следующее дифференциальное уравнение:

 

 

 

где обозначено .  Найдем общее решение данного уравнения. Для этого производим замену: . Тогда  и уравнение примет вид: Интегрируя последнее равенство по , получим:  . Следовательно   и окончательно:

 

 

Получили семейство цепных линий. Подбирая произвольные постоянные и так, чтобы выполнялись начальные условия

, получим искомое  уравнение линии провисания нити.¹³

Предположим, что константы  и   уже подобраны, тогда уравнение цепной линии можно упростить. Произведем преобразование координат: 

 

 

 

т.е. за новое начало координат  принимается точка  . В новой системе координат уравнение цепной линии с сохранением прежних обозначений для новых координат примет вид:

 

 

 

Если принять за начало координат нижнюю точку цепной линии, то и окончательно уравнение цепной линии примет вид:

 

 

 

Если мы будем применять формулу  цепной линии к нашей задаче (рисунок 2.2), где оси декартового графика пересекаются не в нижней точке цепи, а у основания левого столба и тем самым сдвинуты на величины   (по горизонтали) и  (по вертикали), то формула цепной линии примет вид:

 

 

 

 

 С этой формулой мы и будем дальше работать.

Наша задача о провисании цепи будет  сводиться к поиску значений констант  входящих в формулу цепной линии. Для решения этой задачи нужно составить систему трех нелинейных алгебраических уравнений с вышеперечисленными тремя неизвестными. Первые два уравнения получаются при рассмотрении двух точек закрепления цепи на столбах: – левый столб и  – правый столб. Третье уравнение возникает при вводе в задачу формулы, описывающей длину дуги линии. 

 

2.3 Вычисление длины плоской  линии

 

Пусть линия  представляет собой график функции , рассматриваемый при   Будем предполагать, что функция  имеет на  непрерывную производную. Наша цель  найти длину линии .

Рассмотрим разбиение   отрезка    точками   и отметим соответствующие точки   на графике. На каждом отрезке разбиения приближённо заменим дугу графика   на хорду .

 

 

Рисунок 2.3.1 – Разбиение отрезка    

 
Длина этой хорды по теореме Пифагора равняется, которая изображена на рисунке (2.3.2) и вычисляется по формуле:

 

.

 

 

Рисунок 2.3.2 – Определение хорды 

Преобразуем это выражение к виду

 

(

 

По теореме Лагранжа, на интервале ( найдётся такая точка , что

 

.

 

Поэтому получаем

 

(

 

Рассмотрим теперь точки , , как отмеченные точки и получим размеченное разбиение. Соответствующая этому разбиению суммарная длина ломаной  равна:

 

 

Будем считать эту длину приближённым значением длины линии , а предел этой величины при неограниченном измельчении разбиения  по определению равным длине линии :

 

 

 

Заметим теперь, что величина:

 

 

 

 

представляет  собой интегральную сумму, составленную по размеченному разбиению  для функции . Эта интегральная сумма при измельчении разбиения будет стремиться к значению определённого интеграла, так что получаем в итоге:

 

.

 

3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ РЕШЕНИЙ ЗАДАЧ

1. Программная реализация решения задачи о провисании цепи

 

3.1.1 Описание программы

 

В качестве языка программирования выбран язык Delphi ввиду его наглядности и облегченного понимания, а также возможности в дальнейшем использовать для решения более трудных задач.

Программа позволяет решить систему трех нелинейных уравнений и найти минимальное расстояние цепи от земли.

Переменная – это область памяти, содержащая значение определённого типа и позволяющая изменить текущее значение на новое. При определении переменной должен указываться тип данных. Переменная определяется в разделе var.

Операторы используются для того чтобы присвоить значение переменной.

:= Единственный оператор присвоения

Условные операторы IF. . THEN – позволяет определить выполняются ли некоторые условия и в зависимости выполнить тот или иной код.

IF –> выражение –> THEN –>  оператор –> ELSE –> оператор  –> END.

 

3.1.2 Тестирование программы

 

Данные значения:

• высота первого столба – ;
• высота второго столба – ;
• расстояние от до ; (пролет) – ;
• длина цепи подвешенной на двух столбах и – .

Цепь провисает под  действием тяжести, но величины свободного падения в формуле провисания цепи нет. Это значит, что любая цепь одинаково провисает (тяжелая стальная и тонкая нитка). Поэтому задача о провисании цепи сводится к поиску значений констант Для нахождения сотавим систему трех нелинейных алгебраических уравнений:

 

(3.1.1)

 

Подставив наши данные в систему (3.1.1) получим новую систему уравнений:

 

(3.1.2)

 

В системе (3.1.2) вычислив интеграл:

 

,

 

получаем  или , т.е.  .

Система (3.1.2) приводится к виду:

 

(3.1.3)

Подставляя  уравнение в первое и второе уравнение системы (3.1.3) вместо получаем:

 

 

 

Теперь подставим значение во второе уравнение системы:

 

 

 

отсюда  =­29.

Подставив значение в первое и второе уравнение системы получаем:

 

, .

 

На рисунке (3.1) представлены вычисления системы нелинейного уравнения.

 

Рисунок 3.1 – Решение системы нелинейного уравнения

 

2. Программная реализация метода Ньютона – Рафсона

 

3.2.1 Описание программы

 

 

 Благодаря визуальному  программированию, а также достаточно большой библиотеке визуальных компонентов, Delphi позволяет создавать программы  наиболее быстро и эффективно.