Метод Ньютона и его модификации решения систем нелинейных уравнений (стр. 3 из 5)

. (1.10)

2. МЕТОД НЬЮТОНА И ЕГО РЕШЕНИЯ СИСТЕМ НЕЛИНЕЙНЫХ УРАВНЕНИЙ.

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

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

к решению

построены приближения

. Заменим в системе

(*)

каждую из функций

линейной частью её разложения по формуле Тейлора в точке

В результате придём к системе линейных алгебраических уравнений:

. . . . . . . . . . . . . . .

имеющей в матричной форме записи вид:

. (2.1)

Здесь

- матрица Якоби.

Предположим, что матрица

невырожденная, т.е. существует обратная матрица

. Тогда система (2.1) имеет единственное решение, которое принимается за очередное приближение

к решению

. Таким образом, приближение

удовлетворяет равенству:

, (2.2)

выражая из которого

, выводим итерационную формулу метода Ньютона:

. (2.3)

Замечание.

Формула (2.3) предполагает использование трудоёмкой операции обращения матрицы, поэтому непосредственное её использование для вычисления

в большинстве случаев нецелесообразно. Обычно вместо этого решают эквивалентную системе (2.2) систему линейных алгебраических уравнений:

(2.4)

относительно поправки

. Затем полагают:

(2.5)

2.2. СХОДИМОСТЬ МЕТОДА.

Сформулируем основную теорему о сходимости метода Ньютона.

Теорема 3.

Пусть в некоторой окрестности решения

системы (*) функции

дважды непрерывно дифференцируемы и матрица

невырождена. Тогда найдётся такая малая

- окрестность решения

, что при произвольном выборе начального приближения

из этой окрестности итерационная последовательность метода Ньютона не выходит за пределы окрестности и справедлива оценка:

Эта оценка означает, что метод сходится с квадратичной скоростью.

Квадратичная скорость сходимости метода Ньютона позволяет использовать простой практический критерий окончания:

. (2.6)

Пример 3.

Используя метод Ньютона, найдём с точностью

решение

системы

Возьмём

и будем вести вычисления по формулам (2.4), (2.5), в которых

Результаты вычислений с шестью знаками мантиссы приведены в табл. 2.

Табл. 2

При

критерий окончания

выполняется и можно положить

2.3. ТРУДНОСТИ ИСПОЛЬЗОВАНИЯ.

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

из

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

3. МОДЕФИКАЦИЯ МЕТОДА НЬЮТОНА.

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

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

требуется, как правило, 3-5 итераций.

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

1) вычисление

компонент вектора

;

2) вычисление

компонент матрицы Якоби

;

3) решение системы линейных алгебраических уравнений (2.4).

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