Метод Ньютона для решения систем нелинейных уравнений

Пусть задана система нелинейных уравнений

решение которой достигается в точке пространства . Обозначим ; . Тогда исходная система запишется в виде

.

Предположим, что известно k-е приближение к . Построим правило Ньютона вычисления (k+1)-го приближения в форме

.

Разложим функцию в ряд Тейлора в окрестности точки и сохраним в разложении два члена:

.

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

.

Тогда

,

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

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

1. Решается система линейных алгебраических уравнений и вычисляется вектор поправки:

,

где – матрица Якоби системы;

2. Вычисляется (k+1)-е приближение

,

3. Пункты 1, 2 повторяются для k=0,1,2,… до тех пор, пока не будет достигнута требуемая точность.

Критерием завершения итерационного процесса служат условия

, ,

или в более общей форме

, .

Модификации метода Ньютона. Краткий обзор.

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

· трудность задания начального приближения, от которого метод сходится;

· необходимость вычисления на каждой итерации матрицы Якоби, что может потребовать существенных вычислительных затрат;

· необходимость решения на каждой итерации системы линейных алгебраических уравнений;

· требование невырожденности матрицы Якоби.

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

Метод Ньютона с кусочно-постоянной матрицей.

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

,

в котором , например (матрица Якоби лишь при нарушении этого условия вычисляется заново).

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