Метод Ньютона

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

Рассмотрим простой пример (рис. 1.1).

 

Рис. 1.1. Итерация метода Ньютона для

 

Поскольку , гдеx₀— начальное приближение, то и

можно получить новое приближение .Продолжая итерационный про-цесс, можно с требуемой точно­стью риблизиться к одному из решений, например, = 1,73205...

Расчетная формула для метода Ньютона может быть получена, ес­ли представить w(x) в окрестности текущего приближения х_k в виде ряда Тейлора

 

 

и ограничиться линейными членами, тогда в матричной форме получим

 

где

Применительно к СНАУ W(X) = 0 получим следующий алгоритм:

1) Выбрать начальный вектор положить k = 0, =

2) Вычислить вектор . Если все < , где — за­данная точность расчета, то получено решение, расчет окончен..

Если k>1 и max , то итерационныйпроцесс расходится, расчет завершить аварийно.

3) Построить матрицу Якоби

 

и вычислить значения всех производных в точке

4) Решить систему уравнений, определив вектор поправок АХ^(k):

5) Вычислить новое приближение

и положить k= k + 1.

6) Если k>k_тax,, где k_max — заданное предельное число итераций, то аварийно завершить расчет, иначе перейти к п. 2.

7) Конец алгоритма.

Метод Ньютона при начальном приближении, близком к некото­рому решению, часто обладает устойчивой квадратичной сходимостью. При плохой начальной точке имеет место расходящийся итераци­онный процесс. Метод Ньютона расходится, если матрица Якоби пло­хо обусловлена в окрестности решения. Часто перед использованием метода Ньютона выполняют несколько итераций, например методом последовательных приближений, для того чтобы иметь "хорошее" на­чальное приближение.

В качестве косвенного критерия расходимости итерационного про­цесса можно использовать изменение знака якобиана — определите­ля матрицы Якоби. Однако это условие будучи достаточным, не явля­ется необходимым. Якобиан может быть вычислен, как побочный про­дукт решения методом Гаусса системы из п. 3 алгоритма.