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

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

Рассмотрим нелинейную систему уравнений

(1)

Она может быть также представлена в матричном виде:  (1’),  где

Её решением называется такое значение , для котрого

Если для посл. x_n, сходящейся к х_*, верна формула:

(k – положит-е действ-е число), то k - скорость сходимости данной последовательности.

Итерационные методы решения систем нелинейных уравнений: метод простых итераций, преобразование Эйткена, метод Ньютона, метод градиентного спуска, метод Пикара

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

Основная идея метода Ньютона состоит в выделении из уравнений линейных частей, которые являются главными при малых приращениях аргументов. Это позволяет свести исходную задачу к решению последовательности линейных систем.

Рассмотрим систему уравнений:  

в предположении, что  – непрерывно-дифференцируемые функции.

Полагая , перейдём к векторной записи  (2)

Опишем общий шаг метода.

Пусть уже получено приближение  Разложим функцию  в ряд Тейлора, оставив только два первых члена в силу малости отклонения приближения  от корня: , – матрица Якоби для .

Очередное приближение  определяется как решение линейной системы , т.е.

Если матрица Якоби  не вырождена, то решение системы линейной системы можно записать в явном виде, что приводит к стандартной формуле метода Ньютона  (3)

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

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

 – система линейных уравнений.

 

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

Пусть в  выбрана нек-я векторная  и согласованная с ней матричная .

 

Теорема (о сходимости). Пусть

1) вектор-функция  определена и непрерывно-дифференцируема в области  где  – решение уравнения (2),

2) для всех  существует обратная матрица , причём

3) для всех

4)

Тогда метод Ньютона (3)

1)

2)

3)

Замечание. Оценка погрешности метода Ньютона: