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

Следовательно можно записать условие 1) в виде:  || x⁽ⁱ⁺¹⁾-x⁽ⁱ⁾||£ (*)

     Теперь  можно установить с помощью  (*) , что

 || x^(k+1)-x⁽⁰⁾||£ £ £r,

т.е. все  члены заданной последовательности (х^(k))  принадлежат SÍ M. Покажем, что она удовлетворяет критерию Коши. С помощью того же неравенства (*) имеем:

||x^(k+m)x^(k)||£ £ = (1+ )< (1+ =

     Полученное  неравенство, рассматриваемое при  фиксированном mÎN и k®µ, говорит о фундаментальности (х^(k))  и существовании предельного вектора x^* в шаре S, так же если в нём зафиксировать k и перейти к пределу при m®µ, сразу получается утверждаемая оценка

||x*-x^(k)||£

Подстановка выражения  p_k=p₀   в условие 2) показывает, что ||F(x^(k+1))||®0 при k®µ (т.е. при x^k®x^* ), а это, в силу предполагаемой

непрерывности F(x), означает, что x*:= есть решение уравнения F(x)=0. 

Теорема 2.

     Пусть существуют такие последовательности положительных чисел H_k   и G_k, удовлетворяющих условиям H_k £H₀ , G_k £G₀, и число µ>1, что в предположении, что х^(k) ÎМ, при всех kÎN₀ выполняются неравенства:

1) || x^(k+1)- x^(k)||£H_k||F(x^(k))||;

2) ||F(x^(k+1))||£ G_k||F(x^(k))||^µ. 

Тогда справедлива Теорема 1 с p₀ ³||F(x⁽⁰⁾)||, l:=H₀.

Доказательство.

     Определим последовательность (р_k) равенством р_k+1 =G₀ р_k^µ и по индукции покажем, что эта последовательность мажорирует  (||F(x^(k))||), одновременно доказывая принадлежность векторов х^(k) шару S(x⁽⁰⁾, r).

По условию  x⁽⁰⁾ÎS и ||F(x⁽⁰⁾)||£ p₀ . сделаем индуктивное предположение, что

x⁽ⁱ⁾ÎS и ||F(x⁽ⁱ⁾)||£ p_i "iÎ{0,1, 2…k}.

Тогда || x⁽ⁱ⁺¹⁾-x⁽ⁱ⁾||£ H₀p₀= H₀p₀

Из этого следует  неравенство ||х^(k+1)-х⁽⁰⁾|| £ r, означающее, что х^(k+1)ÎSÍM. Таким образом, F(x^(k+1))  существует и

  G_k ^µ£G₀p_k ^µ=p_k+1 

Теорема 3.

Пусть функция  F(х) определена и дифференцируема по Фреше в некоторой открытой области МÍÂ_n, т.е. дифференцируемость функции в классическом смысле, это есть существование ограниченного линейного оператора – дифференциала Фреше D xF`(x)- приближающего приращение функции при   D x®0 (функция F является дифференц. в т. х₀ если выполняется  
]=0). 
 
 
 

И выполняется:

1) $L>0: L||x- || "x, ÎM, где L- оценка сверху величины ||F``(х)||

2) $ ^-1 и $С>0: || ^-1 ||£C "xÎM

Тогда если v:0.5LC²p₀<1, где p₀³ ||F(x⁽⁰⁾)|| и замкнутый шар

S целиком содержится в М, то все члены последовательности, определяемые методом Ньютона (3), начинающимся с заданного х⁽⁰⁾, лежат в SÍM; последовательность( х^(k) ) имеет предел х*ÎS, служащий решением уравнения F(x)= 0; справедлива оценка погрешности

||x*-x^(k)||£  

Доказательство.

     Непосредственно из (3) получаем || x^(k+1)-x^(k)||£ ^-1 £C , С- некоторое число.

 Для  метода Ньютона F(x^(k+1)) + F`(x^(k))(x^(k+1)-x^(k)) можно применить условие

 Липшица для любых х, х⁽⁰⁾ из М

                                                                           , положив х:=х^(k+1), x⁽⁰⁾:= x^(k),

Получим L/2 ²£1/2LC^{2 2}.

Таким образом, выполняется требование 2) Теоремы 2 с G_k=1/2LC², µ=2 и поставив постоянные l=С, G₀=1/2LC², µ=2 в Теорему 1

(||x*-x^(k)||£ ).

      Модификации метода Ньютона.

Модифицированный  метод Ньютона.

     Если  матрицу Якоби F`(х) вычислить и обратить лишь один раз- в начальной точке х⁽⁰⁾, то от метода Ньютона придём к модифицированному методу Ньютона  x^(k+1)=x^(k)- ^-1 F(x^(k)) (5)

Этот  метод требует значительно меньших  вычислительных затрат на один итерационный шаг, но итераций при этом может потребоваться значительно больше для достижения заданной точности по сравнению с основным методом Ньютона x^(k+1)= x^(k)- F(x^(k)) поскольку, являясь частным случаем методом последовательных итераций ( ),  он имеет лишь скорость сходимости геометрической прогрессии.

Рекурсивный метод Ньютона.

     Компромиссный вариант — это вычисление и  обращение матриц Якоби не на каждом итерационном шаге, а через несколько  шагов (иногда такие методы называют рекурсивными).

Например, простое чередование основного метода и модифицированного (5) методов Ньютона приводит к итерационной формуле

x^(k+1)= x^(k)- F(x^(k))- F(x^(k)- F(x^(k))) (6)

где                         k = 0,1,2,… За x^(k) здесь принимается результат последовательного применения одного шага основного, а затем одного шага модифицированного метода, т.е. двухступенчатого процесса

   (7)

     Доказано, что такой процесс при определенных условиях порождает кубически сходящуюся последовательность (x^(k)). См. так же Теорему о сходимости модифицированного метода Ньютона.

Для модифицированного  метода Ньютона требование обратимости  матрицы Якоби в любой точке  М заменим менее ограничительным  требование ее обратимости лишь в  начальной точке х⁽⁰⁾.

Теорема 4. « О сходимости модифицированного метода Ньютона»

     Пусть L- оценка сверху величины ||F``(x)|| и для F: (MÍÂ_n)®Â_n:

1) $ F`(x): ($L>0: L||x- || "x, ÎM)

2) $ ^-1 $C₀>0: || ^-1 ||£C₀.

Тогда если при р₀³  ||F(x⁽⁰⁾)|| величина t:= LC₀²p₀ £0.125 и замкнутый шар

S  содержится в М, то начатый с (x⁽⁰⁾) модифицированный метод Ньютона сходится к решению х* уравнения F(x)=0 с оценкой погрешности ||x*-x^(k)||£ , где v:=

(одновременно  берется либо только верхний  знак, либо только нижний).

Доказательство.

      Требование || x^(k+1)-x^(k)||£   , где Н_k некоторая последовательность положительных чисел, получается из формулы, определяющей метод:  .

Для оценки ||F(x^(k+1))|| преобразуем неравенство из Теоремы 3:

                                                                            , так, чтобы воспользоваться равенством нулю выражения F(x^(k)) + F`(x⁽⁰⁾)(x^(k+1)-x^(k)) в соответствии с (5).

     Имеем:

£ + ²£ £L C₀ £LC₀ 2LC₀r .

Отсюда  видно, что можно считать выполненным  требование 2) Теоремы 2 с 

G_k= G₀= 2LC₀r и µ=1.

     Подстановка постоянных µ= 1, l= C₀  в заключительную часть Теоремы 1 показывает что в данном случае должно быть r= , а               v= 2LC₀r<1.

Исключая из последних двух равенств параметр r, получаем квадратное относительно v уравнение v²- v+ 2t= 0, оба корня которого =0,5   положительны и меньше 1. Подставляя эти значения v, находим связанные с ним значения радиуса r шара S.

Аппроксимационный аналог метода Ньютона.

      Задачу обращения матриц Якоби  на каждом k- м шаге метода Ньютона можно решать не точно, а приближенно- ограничиваясь всего одним шагом процесса второго порядка, в котором за начальную матрицу принимается матрица, полученная в результате предыдущего (k-1)- го шага. Таким образом, переходим к методу Ньютона с последовательной аппроксимацией обратных матриц (аппроксимационный аналог метода Ньютона ААМН ):

 (8)

  где k= 0, 1, 2,.., а х⁽⁰⁾ и А₀-начальный вектор  и матрица  
соответственно. (требования к степени близости А₀ к ^-1                         наряду с другими требованиями, гарант. сходимость метода см. далее в Теореме 5 ). Этот метод имеет простую схему вычислений- поочередное выполнение векторных в первой строке и матричных во второй строке его записи (8) операций. Скорость его сходимости почти так же высока, как и у метода Ньютона. Последовательность (x^(k)) так же может квадратично сходиться к решению х* уравнения F(x)= 0 (при это матричная последовательность (А_k) так же квадратично сходится к A*:= ^-1 ,         т.е. в нормально развивающемся итерационном процессе (8) должна наблюдаться достаточно быстрая сходимость (||Y_k|| к нулю).