Итерациональные методы решения нелинейных уравнений

      1) при ;

      2) при . 

Оценка  приближения 

      Из  формулы (2.8) имеем:

.

      Устремляя к бесконечности и учитывая, что , окончательно получим:

                          . (2.12)

      Отсюда  видно, что чем меньше , тем больше скорость сходимости итерационного процесса, заданного формулой (2.5).

      Для оценки приближения можно использовать и другую формулу.

      Пусть . Очевидно, что . Учитывая, что , получим:

          ,

где находится между и . Следовательно, , т.е.

.

Используя формулу (2.7), получим:

                            .  (2.13)

      Если  , то . В этом случае из неравенства вытекает неравенство , где - заданная точность. 

Условия окончания итерационного  процесса 

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

1. если два последующих приближения отличаются между собой по модулю на величину, не превышающую заданной точности , т.е. . Отдельно этого критерия недостаточно, так как в случае крутизны графика, данное условие будет выполнено, но может находиться далеко от корня;
2. мера удовлетворения уравнению (2.1) последнего приближения корня: . Отдельно данного критерия недостаточно, так как при пологой функции это условие может быть выполнено, но может находиться далеко от корня.

      Метод простых итераций имеет два достоинства:

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

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

Недостатки  метода:

      - трудоемкость процесса приведения уравнения (2.1) к виду (2.4);

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

     Пример 2.4. Доказать графическим и аналитическим методами существование единственного корня нелинейного уравнения

                               (2.14)

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

     1. Докажем графическим методом  единственность корня нелинейного уравнения (2.14). Из графика функции на рис. 2.8 видно, что функция пересекает ось в одной точке, являющейся приближенным значением корня нелинейного уравнения (2.14). Но так как данная функция имеет сложный аналитический вид, то преобразуем уравнение (2.14) к виду и построим два графика функций и , имеющих более простой аналитический вид (рис. 2.9). Абсцисса точки пересечения графиков является приближенным значением корня.

       Для доказательства единственности корня на отрезке  воспользуемся аналитическим методом. Функция  непрерывна на отрезке , имеет на концах отрезка разные знаки ( ), а производная функции не меняет знак на отрезке ( ). Следовательно, нелинейное уравнение (2.14) имеет на указанном отрезке единственный корень.

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

                          (2.15)

     Итерационный  процесс (2.15) можно начать, задав  произвольное начальное приближение .

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

 

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

      Пусть

                               . (2.16)

      По  формуле Тейлора получим

.

      Следовательно, .

      Внося эту правку в формулу (2.16), получим  рабочую формулу метода Ньютона вида:

                           (2.17)

      Геометрически метод Ньютона эквивалентен замене небольшой дуги кривой касательной, проведенной в некоторой точке этой кривой.

       Для определенности положим  и . Выберем начальное приближение , для которого . Проведем касательную к кривой в точке . За первое приближение берем точку пересечения касательной с осью . На кривой определим точку и проведем касательную к кривой в этой точке. Найдем следующее приближение и т.д. (рис. 2.10).

      Составим  уравнение касательной в точке  :

.

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

.

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

      Теорема 2.5. Если и производные не равны нулю и сохраняют определенные знаки на отрезке , то исходя из начального приближения , удовлетворяющего неравенству , по методу Ньютона, заданному формулой (2.17), можно вычислить единственный корень уравнения (2.1) с любой степенью точности.

      Доказательство.

      Пусть для определенности , , при (остальные случаи рассматриваются аналогично).

      Из  неравенства  следует, что , т.е. .

      Докажем, что все приближения  расположены правее , т.е. , а значит .

      Доказательство  проведем методом индукции:

      а) ;

      б) предположим, что ;

      с) докажем, что  .

      Точное  решение уравнения (2.1) можно представить  в виде

.

      Применяя  формулу Тейлора, получим:

                 (2.18)

где .

      Так как по условию теоремы  , то последнее слагаемое в соотношении (2.18) положительное, следовательно,

.

      Отсюда, в силу того, что  , получим:

.

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

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

,

т.е. . Отсюда следует, что , т.е. . А это означает, что последовательные приближения сходятся к корню уравнения (2.1), что и требовалось доказать.

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

                             .  (2.19)

      Замечание. Чем больше числовое значение в окрестности корня , тем меньше правка . Поэтому методом Ньютона удобно пользоваться, когда в окрестности искомого корня график функции имеет большую крутизну (т.е. , тогда ). Если кривая вблизи точки пересечения с осью почти горизонтальная (т.е. , тогда ), то применять метод Ньютона для решения уравнения (2.1) не рекомендуется.

      Метод Ньютона можно рассматривать  как частный случай метода простых  итераций, если считать . Тогда достаточное условие сходимости метода простых итераций примет вид:

                    для всех  .  (2.20)

      Если  выполнено условие (2.20), то итерационный процесс, заданный формулой (2.17), будет  сходиться при произвольном выборе начального приближения .

      Достоинства метода Ньютона:

      - обладает достаточно большой скоростью сходимости, близкой к квадратичной;

      - достаточно простое получение итерационной формулы (2.17).

      Недостатки метода Ньютона:

      - сходится не при любом выборе начального приближения ;

      - применим только, когда для любого . 

§2.5. Модифицированный метод Ньютона 

      Если  производная  мало изменяется на отрезке , то можно считать, что . Заменив в формуле (2.17) на , получим рабочую формулу модифицированного метода Ньютона:

                           (2.21)

       В отличие  от метода Ньютона, в модифицированном методе касательная заменяется на прямые, параллельные касательной, проведенной в точке (рис. 2.11).

     Пример 2.5. Запишем рабочие формулы метода Ньютона и модифицированного метода Ньютона для нелинейного уравнения из примера 2.4. В качестве начального приближения здесь выбирается правый или левый конец отрезка, в зависимости от того, где выполняется достаточное условие сходимости метода Ньютона вида (2.19). Заметим, что в точке условие не выполняется, а в точке - выполняется. Следовательно, в качестве начального приближения выбирается точка . Рабочая формула метода Ньютона (2.17) для данной задачи запишется так:

                           

     Рабочая формула модифицированного метода Ньютона (2.21) для данной задачи запишется в виде:

                             

§2.6. Непрерывные схемы  решения нелинейных уравнений