разделенные разности первого и второго порядков соответственно.
Сделаем следующее замечание. Перечисленные выше итераци
онные методы в случае сходимости позволяют при заданных на
чальных приближениях найти лишь один из корней уравнения (1).
Чтобы отыскать другие корни, надо менять начальные приближе
ния. Может оказаться, что и при других начальных данных метод
сходится к тому же корню
х = х,.
Тогда целесообразно отделить этот
корень, т. е. применить итерационный метод к
g(x) = f ( x ) / ( x
—
х .) .
§ 2. Сходимость метода простой итерации
1. Теорема о сходимости.
Перепишем уравнение
f ( * ) = 0
(1)
в эквивалентном виде
x = s(x)
(2)
и рассмотрим метод простой итерации
xk+l = s(xk),
й = 0, 1, . . . , *„ задан.
(3)
Говорят, что итерационный метод
сходится,
если последователь
ность
{хк)
имеет предел при
k-^oo.
В следующей теореме формулируются условия на функцию
s(x),
гарантирующие существование и единственность решения
уравнения (2) и сходимость метода простой итерации к этому ре
шению. Напомним, что функция s(x) называется липшиц-непре-
рывиой с постоянной
q
на множестве
X,
если для всех
х
' ,
x
"
g
X вы
полняется неравенство
] s ( x ' ) —
s { x " ) \ ^ q \ x ' —х"\.
( 4 )
В дальнейшем в качестве
X
будем брать отрезок
Ur(a)={x: \х—
д|==Сг}
(5)
длины 2
г
с серединой в точке
а.
7
*
195
Т е о р е м а 1.
Если s(х) липшиц-непрерывна с постоянной q
е
е ( 0 , 1)
на отрезке UT(a), причем
\ s(a)—a \ s ^ ( l — q)r,
(6)
то уравнение
(2)
имеет на отрезке Ur(a) единственное решение х
.
и метод простой итерации
(3)
сходится к х, при любом начальном
приближении x0^ U r(a). Дл я погрешности справедлива оценка
\ х — х . \ s^q k\x0—х.\,
£ = 0 , 1 , 2 , . . .
(7)
Д о к а з а т е л ь с т в о . Сначала докажем по индукции, что
е
UT(a
),
k —
1, 2, . . . , т. е. что метод простой итерации не выводит
за пределы того множества, на котором s(x) липшиц-непрерывна с
постоянной / ^ 0 , и докажем, что тогда
xj+l^ U T(a
) . Из равенства
xj+l
—
a = s(Xj)— а = (s(Xj)
—
s(a))
+ (
s(a
) —
a)
получим
I X j+ l
—a
I
I s
( X j ) —
s (a)
| + |
s
(a) — a
\
.
Учитывая условие липшиц-непрерывности, предположение индук
ции и условие (6), имеем
| s
(Xj) — s ( a ) \ ^ q \ x j — a \ ^ q r ,
|
Xj+1 — a \ ^ q r + { \ — q ) r ^ r ,
т. e.
xj+i^ U r{a).
Оценим теперь разность двух соседних итераций xj+1—
х,.
Имеем
и поскольку все точки
хи j=
1, 2, . . . , находятся на отрезке
Ur(a),
получаем оценку
|хж —
Xj\ s^q\Xj—
jCj-iI
и,следовательно,
|Х;+1—^ |
^ q s\ x —
х0|,
/ = 1 , 2 , . . .
(8)
Оценка (8) позволяет доказать фундаментальность последова
тельности {xj. Действительно, пусть
р
— любое натуральное число.
Тогда
р
X k + p
X k
= 2 (Xft+j
Х / ц - j - i ) ,
i
=i
и согласно (8) имеем
\Xk+p—
X tK I * ! —
x
0\Y g-t+M — g* L z i ! |X! — X0| ^ —
I xi — x0\,
i L
Х~ Ц
X~ q
t
. e.
|x*+p —
| Xi — x0|,
k, p — 1,2,
. . .
(9)
196
Поскольку правая часть неравенства (9) стремится к нулю при
k-*-oo
и не зависит от
р,
последовательность {xj является фунда
ментальной. Следовательно, существует
lim
Xk =
х. е
Uг (а).
/г—
юо
Переходя в (3) к пределу при
k->-oo
и учитывая непрерывность
функции
s(x),
получим x, = s (х.), т. е. х. — решение уравнения (2),
Предположим, что х / — какое-то решение уравнения (2), при
надлежащее отрезку
Ur(a).
Тогда
X, —
* '= s(x „ ) —
s{x)
и по условию теоремы
\x. — x ' J ^ q \ x , — xJ.
Так как
q <\ ,
последнее неравенство может выполняться лишь при
х / = х„ т. е. решение единственно.
Докажем оценку погрешности (7). Из уравнения (3) получим
**+
1
—
= S (х„) —X, = s (хЛ) —s
(х
.) ,
и так как
хк,
х ,е £ /г(а), приходим к неравенству
К -и —
х.\ s ^ q \ x h—
х ,|,
(10)
справедливому для всех
k = 0,
1, . . . , из которого и следует оценка
(7). Теорема 1 доказана.
Do'stlaringiz bilan baham: |