Методы вычислений. Часть I. Численные методы алгебры. Курцева К.П - 67 стр.

UptoLike

Составители: 

67
Если величина
()
xx
k
X
rr
мала, то можно написать приближенное равенство
()
() () ()
F(x)F(x)x x F(x)
kk k
+−
rrrrr
Поскольку F(x ) 0
=
r
, то
()
() () ()
F(x)F(x)x x 0
kk k
+−
rrrr
Возьмем в качестве следующего приближения решения уравнения
()
() () ( 1) ()
F(x ) F (x ) x x 0
kkkk+
+−=
rrrr
В предположении, что оператор
F
обратим, это решение можно записать в виде (5):
()
()
(1) ()
()
F(x )
x x , 0,1, 2,...
F(x )
k
kk
k
k
+
=− =
r
rr
r
(5)
Такой итерационный процесс называют методом Ньютона.
Теорема о сходимости метода Ньютона для системы:
Пусть
{
}
x: x x
a
a
Ω=
r
rr
некоторое множество и в нем при некоторых
12 12
,,,0 ,0 ,aa a a a a<≤< выполнены условия:
1)
[] []
11
1
F(x), причем F(x) , такая, что F(x) , x
a
a
−−
′′
∃∃ Ω
rr rr
2)
()
2
12 212212
F(x ) F(x ) F (x ) x x x x
X
Y
a
−− −≤
rr rrr rr
при
12
x,x
a
∈Ω
rr
. Обозначим
(
)
1
12
,min,caa b ac
==
Тогда при условиях 1), 2) и
0
x
b
∈Ω
r
итерационный процесс Ньютона (5) сходится с
оценкой погрешности:
()
2
() 1 (0)
xx xx
K
k
XX
cc
∗−
−≤
rr rr
. #
Согласно определению ,cb,
(0)
xx 1
X
ccb
−<
rr
Принято говорить, что метод Ньютона сходится с квадратичной скоростью,
МПИ сходится со скоростью геом. прогрессии
Сущность метода Ньютона.
Метод применяется для уточнения найденного решения системы нелинейных
уравнений , т.к. в случае систем уравнений имеются довольно жесткие условия
сходимости, в силу чего МН не удается применить, когда исходное приближенное
решение обладает небольшой точностью. В случае удачного нач. приближения МН
обладает высокой степенью сходимости.
Обычно, прежде чем применять МН, используют
другой метод, который имеет
слабые условия сходимости, вследствие чего в некоторых случаях требует большого
кол-ва вычислений. Например, метод скорейшего спуска, обладающий важным
преимуществом: неизбежной сходимости процесса.
Сравнение методов решения систем нелинейных уравнений
Для системы из 2-х уравнений первоначальное определение решений удобно
производить графическим методом. Метод скорейшего спусканаиболее общий метод
решения систем уравнений в силу своей неизбежной сходимости, его целесообразно
применять, когда МПИ и МН расходятся. (однако, если применять его для
первоначального определения корней, взяв в качестве исходных данных произвольные
              r r
Если величина x ∗ − x ( k )                 мала, то можно написать приближенное равенство
                                        X


      F(x ( k ) ) + F′(x ( k ) ) ( x ∗ − x ( k ) ) ≈ F(x ∗ )
        r              r           r r                 r

                   r
Поскольку F(x ∗ ) = 0 , то

   F(x ( k ) ) + F′(x ( k ) ) ( x ∗ − x ( k ) ) ≈ 0
     r              r           r r

Возьмем в качестве следующего приближения решения уравнения
    F(x ( k ) ) + F′(x ( k ) ) ( x ( k +1) − x ( k ) ) = 0
      r              r           r           r

В предположении, что оператор F′ обратим, это решение можно записать в виде (5):
                                               r
                         r ( k +1) r ( k ) F(x ( k ) )
                         x        =x − r                 , ( k = 0,1, 2,...)     (5)
                                           F′ (x ( k ) )
Такой итерационный процесс называют методом Ньютона.

           Теорема о сходимости метода Ньютона для системы:
                        r r r
                                {                       }
           Пусть Ω a = x : x − x ∗ ≤ a – некоторое множество и в нем при некоторых
a, a1 , a2 , 0 < a, 0 ≤ a1 , a2 < ∞ выполнены условия:
                  r                         r −1                       r −1    r
          1) ∃ F′(x), причем ∃ [ F′(x) ] , такая, что [ F′(x) ] ≤ a1 , ∀ x ∈ Ω a
                r       r          r r r                     r r 2
          2) F(x1 ) − F(x 2 ) − F′(x 2 ) ( x1 − x 2 ) Y ≤ a2 x1 − x 2 X
при x1 , x 2 ∈ Ω a . Обозначим c = a1a2 , b = min ( a, c −1 )
       r r
                                       r
Тогда при условиях 1), 2) и x 0 ∈ Ωb итерационный процесс Ньютона (5) сходится с
оценкой погрешности:

                                                                   (       )
                                    r         r              r      r     2K
                                    x ( k ) − x ∗ ≤ c −1 c x (0) − x ∗       . #
                                                               X       X



           Согласно определению c, b ,
             r       r
           c x (0) − x ∗ < cb ≤ 1
                            X



      Принято говорить, что метод Ньютона сходится с квадратичной скоростью,
МПИ сходится со скоростью геом. прогрессии
       Сущность метода Ньютона.
      Метод применяется для уточнения найденного решения системы нелинейных
уравнений , т.к. в случае систем уравнений имеются довольно жесткие условия
сходимости, в силу чего МН не удается применить, когда исходное приближенное
решение обладает небольшой точностью. В случае удачного нач. приближения МН
обладает высокой степенью сходимости.
      Обычно, прежде чем применять МН, используют другой метод, который имеет
слабые условия сходимости, вследствие чего в некоторых случаях требует большого
кол-ва вычислений. Например, метод скорейшего спуска, обладающий важным
преимуществом: неизбежной сходимости процесса.
      Сравнение методов решения систем нелинейных уравнений
      Для системы из 2-х уравнений первоначальное определение решений удобно
производить графическим методом. Метод скорейшего спуска – наиболее общий метод
решения систем уравнений в силу своей неизбежной сходимости, его целесообразно
применять, когда МПИ и МН расходятся. (однако, если применять его для
первоначального определения корней, взяв в качестве исходных данных произвольные
                                                                                             67