|
1 _
(26)
2
nt\
Тогда если г0е [ / г(г ,), то метод (24) сходится, причем для по
грешности справедлива оценка
1
( 27)
где
„
__
1 го
— г*
I ^ j
4
2m1
^
(28)
Мб
Д о к а з а т е л ь с т в о . Для погрешности получаем уравнение
t {Zk)
(29)
7 к ¥\
Г
(2ft)
где
F{z) = (z—z j f ' (z)
—
f ( z ) , F' ( z ) =
(z—z.)
f" (z
).
Воспользовавшись формулой Ньютона — Лейбница, получим
F (
2
k) = F ( z J +
§
F ’ ( z ) d z
,
2
.
т. е.
гк
F
(zk) = f
(z — zt)f"{z)dz.
(30)
Докажем оценку (27) по индукции. При ^ = 0 из (29) получим
f(Zo)
(31)
2, — 2.
/' (2с)
Так как
2
, e l / r(z J , имеем согласно (25), что ] / '(z0) | ^ ^ > 0 . Д а
лее, оценим
F{z0) = \ { z - z t) f ”(z)dz.
(32)
2.
Для этого сделаем в интеграле (32) замену переменной
г = /
2
0+ (
1
—
i)z.
и перепишем его в виде
^ (?о) = (г0 - О 2 $ Г (dt.
(33)
0
Имеем
z —z. = t{z,— Z'),
\z—
z, | < |z 0—
2
.| < r ,
t
.
e. z = te 0+ ( l —f ) z e [ / r(z), и согласно (25) выполняется оценка
| №
o
+ ( 1 - / )
z
. ) | < M 2.
Отсюда и из (33) получаем оценку
I
F
(г0) |
Мо
| г0 — г,
|2 \ t d t =
0,5 Vf31
г0
— г ,|2.
Учитывая (31), получим неравенство
,
,
М о
| гп ■
\ ~
I_- I ч
2 т г
которое совпадает с неравенством (27) при
k = \ .
Предположим, что оценка (27) выполняется при
k —
и до
кажем, что она выполняется и при
k = l-\-\.
Заметим прежде всего,
206
что из оценки (27) при
k = l
следует, что
2
, e ( / r (
2
j . Поэтому со
гласно условию (25) имеем
\ f'(z,_)
|
Далее, оценим
г1
F(zt) = ^ (z — zjf"(z)dz.
г,
Учитывая, что
z ^ U r{z
.) , можно получить оценку этого интеграла
гак же, как и оценку
F (z
0) , а именно
I
F (zd
I ^
y
Iг/ _ 12'
Тогда из (29) при
k = l
получим
H/fL -
.API 2/ — г*
2т
L
и, учитывая (27) при
k = l,
придем к неравенству (27) при
k = l-{-
1.
Теорема 5 доказана.
Заметим, что условие сходимости (26) означает близость на
комплексной плоскости начального приближения
z„
к искомому
корню
2
.. В частности, это условие может не выполняться для ве
щественных начальных приближений.
При численной реализации метода Ньютона можно пользовать
ся комплексной арифметикой, однако иногда бывает удобнее раз
делить в формулах (24) действительные и мнимые части и прово
дить вычисления только с вещественными числами.
§ 4. Итерационные методы для систем нелинейных уравнений
1. Общие понятия.
Рассмотрим систему нелинейных уравнений
fi (хи х2, . . . , хт) =
О,
/■2
( Х1 > Х2г ■■■
у
х т )
— О ,
( П
f т (
х
1
у
х
2
у
• • •
i
Х т )
—
О ,
где fi, i = l , 2, . . . , m,— функции вещественных переменных
х„ . . .
хт.
В дальнейшем систему (1) будем рассматривать как опе
раторное уравнение в некотором линейном пространстве
Н
раз
мерности
т.
Обозначим
х=
(хь
х2,
. . . , i„ )r e / / ,
F(x) =
(/i(x),
f2{x). . . . , fm(x))T
и запишем (1) в виде операторного уравнения
F (х)
=0,
(2)
где
F: Fl-+Fi
— отображение, нелинейное, вообще говоря, из
Н
в
Н.
207
Многие одношаговые итерационные методы для решения си
стемы (2) можно записать в виде
„*+1
л
Bk+1
- ----------- h
F (xk)
= 0,
k —
0, 1, . . . ,
x0
задан,
(3)
TA+1
где
k
— номер итерации,
xk = (xl *1
л т
)r ,
тк+1 — числовые параметры,
Bk+i
— матрица mXm, имеющая об
ратную.
Если
F
— линейный оператор, то (3) совпадает
с
канонической формой
одношагового итерационного метода (см. §
1
гл.
2
), т. е. в виде (3) можно за
писать любой одношаговый метод для линейной системы уравнений. В случае
нелинейной системы (
1
) возможны методы, содержащие новую итерацию x
* + 1
нелинейно, и тем самым не представимые в виде (3 ). Однако мы по-прежнему
будем называть канонической формой запись итерационного метода в виде (3).
Для нахождения х,1+1 по известному
хк
из уравнения (3) необ
ходимо решить систему линейных алгебраических уравнений
Bk+ixk+i = g( x h),
(4)
где
g( xk) = B h+ixk—rk+lF(xh) .
Метод (3) называется
явным,
если
Вк+1 = Е
для всех
k = Q,
1, . . . , и
неявным
— в противном случае. Ме
тод (3) называется
стационарным,
если
В
и т не зависят от номера
итерации
k.
Систему линейных уравнений (4) можно решать либо
прямым, либо итерационным методом. В последнем случае итера
ции, приводящие к решению системы (4), называются
внутренни
ми итерациями,
а итерации (3) —
внешними итерациями.
2. Сходимость стационарного метода.
Остановимся кратко на
вопросе о сходимости метода (3). Предположим, что метод (3) —
стационарный, т. е.
В
и т не зависят от
k.
Тогда уравнение (3) мож
но переписать в виде
xh+l = S ( x h),
(5)
а исходное уравнение (2) — в виде
x = S ( x ) ,
(6)
где S(x)
= х
—т
B~lF(x).
Будем считать, что
Н
— конечномерное линейное нормирован
ное пространство, т. е. что определен функционал ||
jc
||, удовлетво
ряющий всем аксиомам нормы.
Точка д :е Я , для которой
S ( x t) = x t,
называется
неподвижной
точкой оператора S.
Очевидно, что точка
х щ
является решением опе
раторного уравнения (2) тогда и только тогда, когда она является
неподвижной точкой оператора S. Таким образом, отыскание кор
ней уравнения (2) эквивалентно отысканию неподвижных точек
оператора 5.
Говорят, что S является
сжимающим оператором на множестве
К ^ Н
.
качффи :
; он
.
ел пи существует число такое
для
•"-r=.V чыиол яе-тя неравенство
208
Теперь мы в состоянии сформулировать теорему, которая назы
вается
принципом сжимающих отображений
и содержит условия
сходимости метода простой итерации
x'1+, = S ( ^ )
(7)
в конечномерном линейном нормированном пространстве
Н.
Она
является многомерным аналогом теоремы 1 из § 2.
Т е о р е м а 1.
Пусть оператор S определен на множестве
Ur(a)
= ( x e tf : ||х—я ||< г }
и является сжимающим оператором на этом множестве с коэффи
циентом сжатия q, причем
IIS ( « ) - « ! ! < ( 1—<7) г,
0L
< < 7 < 1.
(8)
Тогда в Ur(a) оператор S имеет единственную неподвижную
точку
х#
и итерационный метод
(7)
сходится к
х.
при любом
х°<=
<=
UT(a
).
Дл я погрешности справедливы оценки
II** —
xt \ \ ^ q k\\x° —
х,||,
(9)
I х* — x , | K y ^ - | | S ( x 0) — х°||.
(10)
Доказательство теоремы 1 можно найти в [42].
3. Примеры итерационных методов.
П р и м е р 1.
Метод релаксации
представляет собой частный
случай метода (3), когда
Bh+t = E,
тй+
1
= т. Это стационарный ите
рационный метод, который можно записать в виде
xh+> = S ( x h),
где
5 (х) = х—t-F(x).
Метод сходится, если ||S'(x ) ||< 1 . В данном случае S'(x) =
= Е
—т-Р(х) и
d f x
Do'stlaringiz bilan baham: |
