|
6
)
причем
М« | х0 — х* |
2 т х
< 1 .
(7)
Тогда если
г 0б ( / г( г ) ,
то метод Ньютона
(2)
сходится, причем
для погрешности справедлива оценка
\Хк—Х>\<:Я2к~1\Х0—ХА>
(8)
где
м г
|х0 —х*| ^ J
4
2 т,
"
(9)
Д о к а з а т е л ь с т в о . Из уравнения (2) получим
/(**>
Хш
x, — xk
x t
t
(*А>
или
F
( Ч)
*. = „ , , •
/ (*ft)
(10)
F(x) = (x—X' )f' (x)—f(x).
(И )
Заметим, что Т(х.) = 0 и
F (x ) = ( * - * ) № ) ■
(12)
200
Далее, воспользовавшись тождеством
Xk
F{xk) = F ( x , ) + ^ F'{t)dt
и выражением (12) для
F'(t),
получим
F (xk) = 1 (( — х,) f"
(0
dt.
х .
Так как функция
t
—х# не меняет знак на отрезке интегрирования,
можно воспользоваться формулой среднего значения и записать,
что
xk
xk
,
_
12
F
(х/,) = J (/ -
X,) Г (t) dt = Г
O k )
J
(t
- *.)
dt
=
f"
(Ы,
где |* = 0 ) А + ( 1 —
Qk)x„
| 0ftj < l . Обращаясь к (10), получим
Г ( Ы К - * * ) 2
Xk*x — X , =
----- -- -------
,
(13)
2 / ы
т. е. погрешность на (£+1)-й итерации пропорциональна квадрату
погрешности на
k -й
итерации.
Докажем оценку (8) по индукции. При
k = 0
из (13) получим
Xi — x,
_ /' (So) (*о — -У*)2
V
Ы
( 1 4 )
По условию теоремы
x 0^ U r(xt) ,
и поэтому согласно первому из ус
ловий (6) имеем I/'(х 0) | ^ т ! > 0 . Кроме того, | 0 = 9оХ0+ ( 1 —0о)х.>
1о—
х. = 0о(хо—Х#), |Ео—
хт\
^ |0„|
\х0—
Х.|
<Г,
т. е.
10^ и г(хщ
) .
Но тогда согласно (6) | / " ( | 0) I
^ М 2.
Таким обра
зом, приходим к оценке
|* i —
~ ~ У \хо
— *. 1 *
совпадающей с оценкой (8) при
k = l .
Предположим, что оценка (8) выполняется при
k = t ^ l ,
и до
кажем, что она выполняется и при
k = l-
f-1. При
k — l
выражение
(13) принимает вид
X t — X,
Г
К/)
(x t
— x j2
V ( Z )
( 1 5 )
Покажем, что
x,t
h ^ U r( xJ.
Действительно, из (8) при
k = l
имеем
I */ — ■*, •
| * 0
*. К I
- *. I <
г. е.
x,<=Ur{X').
Кроме то; о,
0, (л'.— ),
10, | < 1.
I. следовательно,
£/,(*.)
201
Теперь можно воспользоваться условиями (6) и оценить
I
|/"(Ы I
Отсюда н из (15) получим
/Л.,
(xt — xt)2
2
т1
X[
X^
Из этого неравенства и из неравенства (8), имеющего следующий
вид при
k = l:
получим оценку
\xi+l— xt \ ^
Ms
I ■
2
ml
xr — x i — a
2/fi_
t
.
e. оценку (8) при
k = l-j-
1. Из оценки (8) следует сходимость ме
тода (2), так как для
q ^ (
0, 1) правая часть неравенства (8) стре
мится к нулю при
k-*-ao.
Теорема 1 доказана.
З а м е ч а н и я . 1. У с л о в и е ( 7 ) о з н а ч а е т , ч т о н а ч а л ь н о е п р и б л и ж е н и е н а д о
б р а т ь д о с т а т о ч н о б л и з к о к и с к о м о м у к о р н ю .
2 . В ы п о л н е н и е р а в е н с т в а ( 1 3 ) о з н а ч а е т , ч т о м е т о д и м е е т к в а д р а т и ч н у ю с х о
д и м о с т ь .
3 . П о с к о л ь к у
х
, з а р а н е е н е и з в е с т е н ,
и н о г д а
т р у д н о
п р о в е р и т ь
у с л о в и е
Хо
< = £ /г ( х „ ) . Н о е с л и
и з в е с т н о , ч т о
| / ' ( х ) | T s m i X )
в
н е к о т о р о й о к р е с т н о с т и
к о р н я , т о д л я о ц е н к и б л и з о с т и н а ч а л ь н о г о п р и б л и ж е н и я к к о р н ю м о ж н о в о с
п о л ь з о в а т ь с я н е р а в е н с т в о м
к о — х . |
| / ( * о )
\/mi.
( 1 6 )
Д е й с т в и т е л ь н о ,
f(x0) = { ( х 0
) — / ( * . ) =
о т к у д а и с л е д у е т ( 1 6 ) .
2. Кратные корни. Говорят, что
х,
является корнем кратности р,
если
f
(*.)
= Г (х,)
= • • • =
f iP~l) (х,)
= 0,
/ (в) (*.)
ф
О
Будем предполагать сейчас, что
(д-) непрерывна в окрестности
корня л:# кратности р. В случае корня кратности р квадратичную
сходимость имеет
метод Ньютона с параметром
f ( x k) Xk* ~ Xk- + f ( x k) =
О,
(17)
т
где т = р. Справедлива
Т е о р е м а 2.
Пусть х г
—
корень кратности р уравнения
(1
) и в
окрестности
Ur{x,) = {x: \х— х.\ < г )
производная
f(p) (
х
)
отлична от нуля.
Пусть
f(p+i)
(х) непрерывна в UT{x} и
О
< ш р =
inf
| / (
р
) (
а
-)|,
x=Ur (r.t )
MP,L=
sup | / (PH)(jf)|,
x=Ur (x,)
202
причем
МР¥
1
ко — ** I
трр ( р +
1
)
Тогда если x „ ^ U r(xt), то метод
(17)
при х = р сходится, причем
для погрешности справедлива оценка
\Xk
- V . j -
/
-
1 |
Х0 —
А , | ,
где
mPP ( Р +
1)
Доказательство теоремы 2 мало отличается от доказательства
теоремы 1 (см. [25]). Для погрешности
х к+1
—
х &
метода (17) с т
= р
получаем выражение (10), где
F ( x ) = ( x — x j [ ' ( x ) — p [ ( x ) .
При этом
F(m)
(-О = 0,
т = 0, 1,...,р—1
, р.
Применяя формулу Тейлора с остаточным членом в интегральной
форме, получим, что
*к
F
^
= - 7 — Ч т f {t ~ Х •> {Хк - ^
(Р+1) {t) dL
(Р—
1)! J
Далее, воспользовавшись формулой среднего значения, получим
представление
F (хк)
в виде
F(xk).
/(р+1) (if)
(Хк
—
А . )
pei
(Р+
О!
Для оценки
знаменателя
выражения (10)
используется
формула Тейлора с остаточ
ным членом в форме Лагран
жа. В результате получаем,что
(
а
* —
Г
(**) = •
( Р -
1)!
/ (Р) (If).
Рис.
6
. Монотонная сходимость
Ньютона
метода
Далее повторяются те же рас
суждения, что и при доказа
тельстве теоремы 1.
3. Односторонние приближе
ния.
Если в окрестности корня
х %
производная функции
f (х)
сохраняет знак и монотонна, то при
ближения
а
*, получаемые в методе Ньютона, сходятся к х. с одной
стороны. Это означает, что последовательность
{хк}
либо монотон
но убывает, так что A4- j
4!< ;
xs
для всех
k,
либо монотонно воз-
203
растает, так что
xh< .xh+i<.x,
для всех
k.
Монотонная сходимость
метода Ньютона хорошо видна на рис. 6. Важное свойство моно
тонности метода Ньютона более точно сформулировано в теоре
мах 3, 4. В этих теоремах предполагается, что на отрезке
[а, b
]
уравнение (1) имеет единственный корень
х
_ и функция
f(x)
дваж
ды непрерывно дифференцируема.
Т е о р е м а 3.
Пусть для всех
х е Lа, 6]
либо
П х ) >
0
,
f " ( x ) >
0
,
(18)
либо
Г ( Х ) <
О,
f " ( x ) <
0.
(19)
Тогда последовательность
{хй},
определенная согласно
(2)
с
ха = Ь, монотонно убывает и сходится к х %
.
Т е о р е м а 4.
Пусть для всех
x e l
а, Ь] либо
/'(* )> 0,
Г ( х ) <
0,
либо
Г(х)< о, / " ( * ) > 0.
Тогда последовательность {xh}, определенная согласно
(2)
с
хй = а, монотонно возрастает и сходится к
х..
Поскольку формулировки и доказательства теорем 3, 4 совер
шенно аналогичны, ограничимся доказательством теоремы 3.
Д о к а з а т е л ь с т в о т е о р е м ы 3. Монотонность последова
тельности {xft} докажем по индукции. По условию
ха = Ь.
Предпо
ложим, что для некоторого
выполняются неравенства
x , < x k^ b ,
(20)
и докажем, что тогда
х , < х к+1Сх„.
(21)
Перепишем уравнение (2) в виде
Xk
Xk+i
—-
f {xk) — f
( X , )
/ ' ( * * )
и воспользуемся формулой конечных приращений Лагранжа. Тогда
получим
Xk
Xk+i
(xk — x*) Г (W
г (ч)
(
22
)
где £ле ( х #, xfc). Пусть выполнено условие (18). Тогда
Г
(У
0 <
Г (Ч)
<
1
,
(23)
причем последнее неравенство является следствием монотонного
возрастания
f'(x).
Те же самые неравенства (23) выполняются и в
случае условий (19). Таким образом,
0 ^
(xk - x*)f
(Ц
Г
(
xk
)
< X k — **,
204
и из (22) получим
0 < x h—x k+l< x
h—
т. е. получим требуемые неравенства (21). Таким образом, после
довательность {х„} монотонно убывает и ограничена снизу чис
лом л:*. Поэтому данная последовательность имеет предел, который
в силу непрерывности функции
f(x)
и условия ^(х^)фО совпадает
с корнем
х
, уравнения (1). Теорема 3 доказана.
Сделаем замечания относительно скорости сходимости метода Ньютона при
условиях теорем 3 и 4. Если начальное приближение
х 0
выбрано достаточно
близко к искомому корню, так что выполняется условие (7 ), то согласно тео
реме
1
метод имеет квадратичную сходимость и для погрешности справедлива
оценка (
8
).
Если ж е условие (7) не выполнено, то на начальных итерациях погрешность
будет убывать более медленно. Однако в силу сходимости последовательности
{
ха
} найдется номер
k — ko, для которого очередное приближение х*„ удовлет
ворит неравенству
Mi\xka — x*\
^
2
т 1
и с этого момента сходимость станет квадратичной.
4. Комплексный корень. Пусть
f ( z )
— функция комплексного
переменного
z
= x-{-iy
и
zr= xt-\-iyt
— простой нуль
f(z).
Будем
считать, что
f(z)
аналитична в некоторой окрестности z.. Тогда
можно рассматривать метод Ньютона
zk+l = zk - - ^ L t
й = 0, 1, . . .
(24)
Сходимость метода (24) устанавливается в теореме 5, которая
обобщает на комплексный случай теорему 1.
Т е о р е м а 5.
Пусть г
*—
простой корень уравнения f{z) =
0
и
пусть f(z) аналитична в круге
Vr(z*) = {z:
|z —z * |< r} .
Предположим, что
inf
|
f'{z)
| = n i i > 0,
sup
\f"(z)\
= M2,
(25)
z=C/r (z,)
z=t/f(z.)
причем
Ab .\.z° — z*\,
Do'stlaringiz bilan baham: |
