Оглавление

Введение: 3

Теоретическая часть 4

1.Вводные  замечания. 4

2.Метод  деления отрезка  пополам (метод  бисекции). 5

3. Метод хорд. 8

4. Метод Ньютона  (метод касательных). 10

5. Метод простой  итерации. 12

Практическая  часть 15

Решение методом дихотомии. 17

Решение методом хорд. 18

Решение методом Ньютона. 19

Решение методом простых  итераций. 20

Вывод: 21 

 

Введение:

В современных  науке и технике важную роль играет математическое моделирование, заменяющее эксперименты с реальными объектами  экспериментами с их математическими  моделями. Возник даже термин "вычислительный эксперимент". Математическое моделирование  и вычислительный эксперимент применяются  не только в точных науках и технике, но и в экономических науках, социологии и многих других областях, традиционно  считавшихся далекими от математики и компьютеров. Зачем нужен вычислительный эксперимент? Проектирование сложных  объектов, например, атомных, космических  и многих других требует проведения колоссальных объемов вычислений. Например, для решения многих прикладных задач  аэродинамики и ядерной физики требуется  выполнения более  арифметических операций. Современные технологии зачастую используют предельные режимы, которые требуют учета сложных нелинейных факторов. Зачастую требуется изучить поведение объекта в экстремальных и аварийных ситуациях, что практически невозможно путем натурного эксперимента, например, при изучении ядерных взрывов, последствий техногенных катастроф и во многих других ситуациях.

Для практических задач довольно редко удается  найти аналитическое решение  уравнений, составляющих математическую модель явления. Поэтому приходится применять численные методы.

 

Теоретическая часть

1.Вводные замечания.

Задача  нахождения корней нелинейных уравнений  вида  

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

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

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

а) отыскания  приближенного значения корня (начального приближения);

б) уточнения  приближенного значения до некоторой  заданной степени точности.

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

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

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

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

то говорят, что итерационный процесс сходится .

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

2.Метод деления отрезка пополам (метод бисекции).

Это один из простейших методов нахождения корней нелинейных уравнений. Он состоит в  следующем. Допустим, что нам удалось  найти отрезок , на котором расположено искомое значение корня , т. е. с Е . (Далее мы предполагаем, что — единственный корень на отрезке . Если корней на  несколько, то в результате применения метода деления отрезка пополам и метода хорд (см. п. 3) будет найдено приближенное значение одного из корней). В качестве начального приближения корня принимаем середину этого отрезка: . Далее исследуем значения функции на концах отрезков и, т. е. в точках . Тот из отрезков, на концах которого принимает значения разных знаков, содержит искомый корень; поэтому его принимаем в качестве нового отрезка. Вторую половину отрезка , на которой знак не меняется, отбрасываем. В качестве первого приближения корня принимаем середину нового отрезка и т. д. Таким образом, -е приближение вычисляется как

                     (2)

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

            (3)

Пусть приближенное решение требуется найти с точностью до некоторого заданного малого числа ε > 0:

                (4)

Взяв  в качестве приближенного решения  -е приближение корня: , запишем (4) с учетом обозначения в виде

                (5)

 Как  легко видеть, из (2) следует, что (5) выполнено, если

              (6)

Таким образом, итерационный процесс нужно  продолжать до тех пор, пока не будет  выполнено условие (6).

Метод деления отрезка пополам проиллюстрирован на рис. 5.1. Пусть для определенности , . В качестве начального приближения корня примем . Поскольку в рассматриваемом случае

, то с  и рассматриваем только отрезок , т. е. , . Следующее приближение:

При этом отрезок  отбрасываем, поскольку и . Таким образом, с [], . Аналогично находим другие приближения: и т. д. до выполнения условия (6).

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

Однако  метод деления отрезка пополам  довольно медленный. Вычислим число  итераций N, требуемое для достижения точности. Для этого выясним, пользуясь (3), для каких выполнено условие (6), и возьмем в качестве N наименьшее из таких . Окончательно получим (7)  

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

Итерационный  процесс можно завершать и  тогда, когда значение функции  после -й итерации станет меньшим по модулю е, т. е.  

Для уравнения(1) величина есть невязка, полученная на -и итерации. На рис. 5.2 представлен алгоритм итерационного процесса нахождения корня уравнения (1) методом деления отрезка пополам. Здесь сужение отрезка производится путем замены границ или на текущее значение корня с. При этом значение вычисляется лишь один раз, поскольку нам нужен только знак функции на левой границе, а он в процессе итераций не меняется.

3. Метод хорд.

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

Сначала находим уравнение хорды АВ:  

Для точки пересечения ее с осью абсцисс () получим уравнение  

Далее, сравнивая знаки величин  и для рассматриваемого случая, приходим к выводу, что корень находится в интервале (, ), так как < 0. Отрезок [] отбрасываем. Следующая итерация состоит в определении нового приближения как точки пересечения хорды с осью абсцисс и т. д.

В отличие  от метода деления отрезка пополам  в методе хорд условие окончания  итераций типа (6) неприменимо. Так, на рис. 5.3 видно, что длина отрезка [a, никогда не станет меньше длины отрезка Вместо (6) нужно использовать условие близости двух последовательных приближений

                                      (10)

или условием малости невязки (8).

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

4. Метод Ньютона  (метод касательных).

Его отличие  от предыдущего метода состоит в  том, что на -й итерации вместо хорды  проводится касательная к кривой при и ищется точка пересечения касательной с осью абсцисс. При этом не обязательно задавать отрезок [], содержащий корень уравнения (1), а достаточно лишь найти некоторое начальное приближение корня (рис. 5.4).                     

Уравнение касательной, про- веденной к кривой в точке с координатами и , имеет вид  

Отсюда  найдем следующее приближение корня  как абсциссу точки пересечения касательной с осью  

Аналогично  могут быть найдены и следующие  приближения как точки пересечения  с осью абсцисс касательных, проведенных  в точках и т. д. Формула для -го приближения имеет вид

-

При этом необходимо, чтобы не равнялась нулю. Для окончания итерационного процесса могут быть использованы условия (10) или (8). Из (11) следует, что на каждой итерации объем вычислений в методе Ньютона больший, чем в рассмотренных ранее методах, поскольку приходится находить значение не только функции но и ее производной. Однако скорость сходимости здесь значительно выше, чем в других методах.

Остановимся на некоторых вопросах, связанных  со сходимостью метода Ньютона и  его использованием. Имеет место  следующая теорема.

Теорема. Пусть — корень уравнения (1), т. е. , a непрерывна. Тогда существует окрестность D корня с (с D) такая, что если начальное приближение принадлежит этой окрестности, то для метода Ньютона последовательность значений { } сходится к с при . При этом для погрешности корня имеет место соотношение  

Фактически  это означает, что на каждой итерации погрешность возводится в квадрат, т. е. число верных знаков корня удваивается. Если  

то легко  показать, что при || пяти-шести итераций достаточно для получения минимально возможной погрешности при вычислениях с двойной точностью. Действительно, погрешность теоретически станет в этом случае величиной порядка , что намного меньше, чем максимальная погрешность округления при вычислениях с двойной точностью, равная . Заметим, что для получения столь малой погрешности в методе деления отрезка пополам потребовалось бы согласно (7) более 50 итераций.

Трудность в применении метода Ньютона состоит  в выборе начального приближения, которое  должно находиться в окрестности  D. При неудачном выборе начального приближения итерации могут расходиться.

5. Метод простой  итерации.

Для использования этого метода исходное нелинейное уравнение записывается в виде

      (12)

Пусть известно начальное приближение  корня. Подставляя это значение в правую часть уравнения (12), получаем новое приближение  

Подставляя  каждый раз новое значение корня  в (12), получаем последовательность значений

, 

Итерационный  процесс прекращается, если результаты двух последовательных итераций близки, т. е. если выполнено неравенство (10). Заметим, что в методе простой итерации для невязки, полученной на -й итерации, выполнено соотношение  

Таким образом, условие малости невязки  на -й итерации оказывается эквивалентным условию близости -го и + 1-го приближений.

Достаточное условие сходимости метода простой  итерации дается следующей теоремой.

Теорема. Пусть  — корень уравнения (12), т. е. и непрерывна. Тогда существует окрестность D корня такая, что если начальное приближение принадлежит этой окрестности, то для метода простой итерации последовательность значений {} сходится к с при .

Метод простой итерации рассмотрен нами для  уравнения (12). К такому виду можно привести и более общее уравнение (1), аналогично тому, как это делалось при решении систем линейных уравнений:  

         (13)

Здесь — некоторое число. Уравнение (13) эквивалентно (12) с функцией За счет выбора значения параметра t можно добиваться сходимости метода простой итерации и повышения скорости сходимости. Например, если на некотором отрезке, содержащем корень уравнения, производная ограничена константами и :  

то для  производной будет справедливо неравенство  

Выбирая ), получаем  

т. е. , что обеспечивает сходимость метода простой итерации.

Параметр  t в (13) можно выбирать и переменным, зависящим от номера итерации. Так, если положить , то метод простой итерации для уравнения (13) примет вид  

   Это соотношение совпадает с формулой метода Ньютона (11). Следовательно, метод Ньютона можно трактовать как частный случай метода хорд простой итерации с переменным .

На рис. 5.5 представлен алгоритм решения  нелинейного уравнения (12) методом простой итерации. Здесь — начальное приближение корня, а в дальнейшем —значение корня после каждой итерации, — результат предыдущей итерации. В данном алгоритме предполагалось, что итерационный процесс сходится. Если такой уверенности нет, то необходимо ограничить число итераций и ввести для них счетчик .

  
 
 
 
 
 
 
 
 
 
 

Практическая  часть

Пусть дано нелинейное уравнение:

исходное нелинейное уравнение

 

Для использования  рассмотренных ранее методов  решения этого уравнения необходимо выбрать отрезок [a,b] (если корней на  несколько, то в результате применения метода деления отрезка пополам и метода хорд будет найдено приближенное значение одного из корней), который удовлетворял бы все условия для наших методов.

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

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

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

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

     Тогда нужно провести пробные решения  на ЭВМ выбранным методом с  исследованием сходимости.

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

     Если  приближения расходятся, следует  провести более точные графические  построения и выбрать начальное  приближение в области сходимости.

Для этого  построим график нашего уравнения:

[a,b] отрезок,  на котором расположен искомый  корень

 
 

заданная точность

Решение методом дихотомии.

искомый корень

количество итераций

промежуточные итерации

Решение методом хорд.

искомый корень

количество итераций

промежуточные итерации

Решение методом Ньютона.

искомый корень

количество итераций

промежуточные итерации

 
 
 
 
 
 
 
 
 
 
 
 
 
 

Графическая интерпретация метода Ньютона:

Решение методом простых  итераций.

Представим  наше уравнение в виде:    Для этого проделаем следующие преобразования:

       

где

некоторое число.

 

Тогда

искомый корень

количество итераций

промежуточные итерации

 
 
 
 
 
 

 

Вывод:

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

     

     К достоинствам программы можно отнести  также  высокую стабильность работы. Однако имеются и некоторые недостатки. К недостаткам программы можно отнести: критичность к вводимым пользователем функций, особый подход к выбору отрезка [a,b]. Это, естественно, ограничивает возможности программы.