Решение систем нелинейных алгебраических уравнений методом Ньютона

⇐ Предыдущая 1 2 3 456 Следующая ⇒

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

Рассмотрим простой пример решения уравнения f(x)=x²–3=0 (рис.1).

Рис. 1

Пусть выбрано некоторое исходное приближение x⁽⁰⁾. Значение невязки уравнения равно значению функции в этой точке f(x⁽⁰⁾). Если функция f(x) дифференцируема в окрестности точки x⁽⁰⁾, то заменим эту нелинейную функцию в окрестности данной точки линейной - в геометрической интерпретации на рис. 1 - касательной. Тогда из соотношения

можно определить поправку Dx и получить новое приближение x⁽¹ ⁾ =x⁽⁰⁾+Dx. Продолжая итерационный процесс по вычисленному x⁽¹ ⁾,можно найти значение x⁽² ⁾ и т.д. пока очередное приближение x⁽^k ⁾с требуемой точностью не будет близко к одному из решений, например, для рис.1 к решению x_*=1.73205...

Расчетная формула для метода Ньютона может быть получена, если представить f(x) в окрестности текущего приближения x⁽^k ⁾ в виде ряда Тейлора

где = x – x⁽^k), и ограничиться линейными членами

По аналогии для системы нелинейных уравнений вида

=0 (17)

получим линеаризованную форму:

, (17)

где D x (k)= x (k+1) - x (k) - вектор поправок;

- квадратная матрица первых производных вектор-функции F (x) по вектору x, называемая матрицей Якоби, элементы которой формируются следующим образом:

, (19)

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

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

На втором этапе применяют собственно итерационный алгоритм для получения решения, например, следующего вида:

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

þ 2. Вычислить вектор невязок F(x (k) ) по формуле (17).

Если все f i(x (k))<, где - заданная точность расчета, то получено решение, расчет окончен.

Если k>1 и максимальная по модулю невязка на очередной итерации увеличилась по сравнению с максимальной по модулю невязкой на предыдущей итерации, т.е. , то итерационный процесс расходится, расчет необходимо завершить аварийно.

þ3. Вычислить значения всех производных в точке x (k) и построить матрицу Якоби (19).

þ4. Решив систему линейных алгебраических уравнений (18), например методом Гаусса, и определить вектор поправок D x (k).

þ 5. Вычислить новое приближение x (k+1) =x (k)+ D x (k) и положить k=k+1.

þ6. Если k>kmax, где kmax -заданное предельное число итераций, то аварийно завершить расчет, иначе перейти к п.2 алгоритма.

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

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

В качестве косвенного критерия расходимости итерационного процесса можно использовать изменение знака якобиана - определителя матрицы Якоби. Якобиан может быть вычислен как побочный продукт решения методом Гаусса системы (17).

Задания:

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

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

Таблица 1

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

.№ варианта	Система нелинейных алгебраических уравнений	№ варианта	Система нелинейных алгебраических уравнений