book1989

то положительные	корни }(х) не	превосходят	числа с.	Действительно, из фор­
м улы Тейлора
/ (X) = / (с) +	( х - с ) Г (с) +	(* ~ С)2 г	( *) +• ■■ +	!{т) W
получаем, что / ( * )	> 0 при х ^ с .

Численные методы решения нелинейных уравнений являются, как правило, итерационными методами, которые предполагают за­ дание достаточно близких к искомому решению начальных данных.

Прежде чем переходить к изложению конкретных итерацион­ ных методов, отметим два простых приема отделения действитель­ ных корней уравнения (1). Предположим, что f(x) определена и непрерывна на [а, Ь].

Первый прием состоит в том, что вычисляется таблица значе­ ний функции f(x) в заданных точках xh^[a , b], k = Q, 1, ... , п. Если обнаружится, что при некотором k числа f(xh), f(xh+t) имеют раз­ ные знаки, то это будет означать, что на интервале (хк, лг*+1) урав­ нение (1) имеет по крайней мере один действительный корень (точ­ нее, имеет нечетное число корней на {хк, х*+1)). Затем можно раз­ бить интервал (xh, xh+l) на более мелкие интервалы и с помощью аналогичной процедуры уточнить расположение корня.

Более регулярным способом отделения действительных корней является метод бисещии (деления пополам). Предположим, что на (а, Ь) расположен лишь один корень х, уравнения (1). Тогда f(a) и f(b) имеют различные знаки. Пусть для определенности f( a)> >0, f(b) <0. Положим х0= 0,5(а + b) и вычислим f(x0). Если f(x0) < <0, то искомый корень находится на интервале (а, х0), если же f(xa) > 0, то х ,е (х 0, Ь). Далее, из двух интервалов (о, х0) и (х0, Ь) выбираем тот, на границах которого функция }(х) имеет различ­ ные знаки, находим точку х ,— середину выбранного интервала, вы­ числяем f(x,) и повторяем указанный процесс. В результате полу­ чаем последовательность интервалов, содержащих искомый корень х,, причем длина каждого последующего интервала вдвое меньше, чем предыдущего. Процесс заканчивается, когда длина вновь полу­ ченного интервала станет меньше заданного числа е>0, и в качест­ ве корня х, приближенно принимается середина этого интервала.

Заметим, что если на (а, Ь) имеется несколько корней, то ука­ занный процесс сойдется к одному из корней, но заранее неизвест­ но, к какому именно. Можно использовать прием выделения кор­ ней: если корень х = х. кратности m найден, то рассматривается функция

g{x) = /(х)/(х—x.)m

идля нее повторяется процесс нахождения корня.

2.Метод простой итерации. Он состоит в том, что уравнение (1) заменяется эквивалентным уравнением

x = s(x)

(3)

и итерации образуются по правилу

*n+i = s(xn),

п = 0, 1, . . . ,

(4)

191

причем задается начальное приближение х„. Для сходимости боль­ шое значение имеет выбор функции s(x). Эту функцию можно за­ давать различными способами, однако обычно она берется в виде

«W =x + r(x)f(x),

(5)

причем функция т(х) не меняет знака на том отрезке, где отыски­ вается корень. В § 2 будет показано, что метод простой итерации сходится при надлежащем выборе начального приближения ха, если | s'(x.) | < 1, где х. — корень уравнения (1).

Отметим, что в форме метода простой итерации (4) можно за­ писать, по существу, любой одношаговый итерационный метод.

В частности, если т(х) = т = const, то получим метод релаксации

XJ t ± l ^ =	f (Xn)t п = 0 , 1 , . . . ,	(6)
т
для которого s'(x) = I + T/^ X), и метод сходится при условии
—2 < тП * .)< 0 .		(7)
Если в некоторой окрестности корня выполняются условия
Г(Х)<о,	0< m ,< \ f'(x) | <Ми	(8)

то метод релаксации сходится при т е (0, 2/Aft).

Чтобы выбрать оптимальный параметр т в методе релаксации, рассмотрим уравнение для погрешности zn = xn—х„ Подставляя xTi = x. + zn в (6), получим уравнение

2п+1~ * -П = /(* . + 2„).

Т

По теореме о среднем имеем

f{xt+ zn) =f(x.) + znf'(x, + Qzn) =znf'(x. + Qzn),

где 0e(O, 1). Таким образом, для погрешности метода релаксации выполняется уравнение

гв+1 - » я==/, (	+0гя)гя>
т
Отсюда приходим к оценке
| г„+1 [ ^ | 1 + т/' (х, + 0г„) | ■| г„ | ^	шах | 1+ т/' (х, + 0г„) [ • | гЛ\,
и если выполнены условия (8 ),то	X

|гп+1[< т а х { | 1—тЛ4,|, 11—т т ,|} |2 п|.

Таким образом, задача выбора оптимального параметра сводит­ ся к нахождению т, для которого функция

<7( т ) = т а х { | 1—тМ,|, |1—тт^}

принимает минимальное значение.

192

Из рассмотрения графика функции q(т) видно, что точка мини­ мума определяется условием

11—хМ, | = 11—ш , |

и равна

т = т0= 2/(Mi + m^.
При этом значении т имеем	т1
1- g
ЯЮ = Ро
1+ 1
так что для погрешности справедлива оценка
Ы < р ? к 1 ,	« = 0, 1, . . .

3. Метод Ньютона. Пусть начальное приближение х0 известно. Заменим f(x) отрезком ряда Тейлора

f ( x ) ^ H i{x) =f(x0) + (x—x0)f'(x0)

иза следующее приближение х, возьмем корень уравнения Н1(х) =

=0, т. е.

Вообще, если итерация хк известна, то следующее приближение хк+1 в методе Ньютона определяется по правилу

	Xk+i — Xk	f(4)	k = 0 , 1,	(9 )
		Г (Ч)
			’

Метод Ньютона называют также методом касательных, так как новое приближение л:к+, является абсциссой точки пересечения касательной, проведенной в точке (xh, f(xh)) к графику функции f(x), с осью Ох.

Исследование сходимости метода Ньютона будет проведено в § 3. Здесь отметим без доказательства лишь две особенности этого метода. Во-первых, метод имеет квадратичную сходимость, т. е. в отличие от линейных задач погрешность на следующей итерации пропорциональна квадрату погрешности на предыдущей итерации: xk+l—x, = 0((xk—x.)2).

И, во-вторых, такая быстрая сходимость метода Ньютона гаран­ тируется лишь при очень хороших, т. е. близких к точному решению, начальных приближениях. Если начальное приближение выбрано неудачно, то метод может сходиться медленно, либо не сойдется вообще.

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

**+1 = ** — 7 7 *7 , k = 0 , \ , . . .	(10)
Г (*о)

применяют в том случае, когда хотят избежать многократного вы­

числения производной f'(x). Метод (10)	предъявляет меньше тре-
7 А. А. Самарский, А. В. Гулин	193

бований к выбору начального приближения хс, однако обладает лишь линейной сходимостью, т. е. хЛ+1—х. = 0(хк—х.).

Метод (10) гарантирует отсутствие деления на нуль, если

Г(х„)ф0.

4. Метод секущих. Этот метод получается из метода Ньютона

(9) заменой f'(xh) разделенной		разностью	/ ( х к ) — / ( X f )	, вычис-
			------------:—
ленной по известным значениям		хк и хк-,.	хк ~ xk-1	получаем
			В результате
итерационный метод
Xkц -- Xfi	Кк- 1	7 (*/<),	k = 1, 2,	( И )
	/ (Хк) — / К -Р

который в отличие от ранее рассмотренных методов является двух­ шаговым, т. е. новое приближение хк+, определяется двумя преды­ дущими итерациями хк и xh-i. В методе (11) необходимо задавать два начальных приближения хии лд.

Геометрическая интерпретация метода секущих состоит в сле­ дующем. Через точки (лд_,, f (хк- 1)), (хк, f(xh)) проводится прямая, абсцисса точки пересечения этой прямой с осью Ох и является новым приближением хк+1. Иначе говоря, на отрезке [xh- u лд] функ­

ция f (х) интерполируется		многочленом	первой степени и за оче­
редное	приближение дд+1	принимается	корень этого многочлена.
5.	Интерполяционные методы. Идея интерполяционных методов
состоит в том, что нахождение корней			уравнения (1) заменяется

нахождением корней интерполяционного многочлена, построенного для f(x). Интерполяционный метод первого порядка приводит к методу секущих. Интерполяционный метод второго порядка назы­ вается методом парабол. Метод Ньютона (9) можно получить, за­ меняя f(x) интерполяционным многочленом Эрмита первой сте­ пени.

Получим формулы метода парабол. Пусть приближения хк- 2, хк- и хк известны. Построим интерполяционный многочлен Ньютона

(см. (11) из § 1 гл. 3)
p 2{x)=f(xh) + (x—xh)f(xkj .*„_,) + ( х — хк) (х—хк-,){{хк, Х к- , ,		хк-9)
и обозначим 2 =;х—хк. Тогда уравнение Р2(х) = 0 примет вид
az2+ oz+c’	= 0,	(12)

где a= f(xh, xh- t, xk- 2), b= f(xh, *„_,) + (хк—xk.,)f(xk, хк- и хк. 2), с=

= f{xh).

Решая уравнение (12), получим два, может быть комплексных, корня, z(1) и z{2>, по которым вычислим х(,) =.rft + z(1), x[2)= xh+ zm. В качестве следующего приближения в методе парабол выбирается

то из значений х(1>, хт, которое ближе к хк, т. е. отвечающее мини­ мальному по модулю корню уравнения (12). Метод парабол удо­ бен тем, что позволяет получить комплексные корни уравнения (7),

пользуясь вещественными начальными приближениями	лд, х2.
194

6.Использование обратной интерполяции. Ряд итерационных

методов	можно получить с помощью интерполирования функции
х= Ф(у),	обратной f(x). Заметим, что если х, — корень уравнения

f(x)=0, то <р(0)=х.. Таким образом, задача нахождения корня х, сводится к вычислению значения ср(0).

Предположим, что известны приближения .г„, л'ь . . . , х„ к корню х,. Тогда можно вычислить £/,• = /(л:;). <= 0, 1, . . . , п, и считать, что по переменной у заданы узлы у„, г/,, . . . , уп и в них известны значе­ ния х„= ф(у,,), . . . . х„ = ф(уп). По данным ((/,, ф((/,-)), ( = О, 1, . .. , п, строится интерполяционный многочлен Ln(y) для функции ф(у) и в качестве следующего приближения х„+1 берется L„(0).

Линейная обратная интерполяция (/г= 1) приводит к методу се­ кущих. Квадратичная обратная интерполяция (п=2) приводит к

методу	+ xklxhq{yk, yk- u ук- г),
xk+l = xk—xhy (yk,
отличному от метода парабол. Здесь у(ук, Уь- i ) и		Ук-ь Ук-г) —

разделенные разности первого и второго порядков соответственно. Сделаем следующее замечание. Перечисленные выше итераци­ онные методы в случае сходимости позволяют при заданных на­ чальных приближениях найти лишь один из корней уравнения (1). Чтобы отыскать другие корни, надо менять начальные приближе­ ния. Может оказаться, что и при других начальных данных метод сходится к тому же корню х = х,. Тогда целесообразно отделить этот корень, т. е. применить итерационный метод к g(x) =f(x)/(x —х .).

§2. Сходимость метода простой итерации

1.Теорема о сходимости. Перепишем уравнение

f(*)= 0	(1)
в эквивалентном виде	(2)
x = s(x)
и рассмотрим метод простой итерации
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^qk\x0—х.\, £ = 0 , 1 , 2 , . . .	(7)
Д о к а з а т е л ь с т в о . Сначала докажем по индукции, что
е UT(a), k —1, 2, ... , т. е. что метод простой итерации	не выводит

за пределы того множества, на котором s(x) липшиц-непрерывна с постоянной <?е(0, 1). Предположим, что ^ е (/,(а ) при некотором /^ 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\xj — 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 ) ,
и согласно (8) имеем	i=i
\Xk+p— X tK I* ! — x0\Y	g-t+M — g* L z i! |X! — X0| ^ —		Ixi — 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\xh—х,|,	(10)

справедливому для всех k = 0, 1, . . . , из которого и следует оценка

(7). Теорема 1 доказана.

З а м е ч а н и е	1. Если для погрешности какого-либо итерационного метода
выполняется неравенство
	|*а—х.\ < М к7а|л:о—х ,\,
где q e ( 0 , 1 ) и	не зависит от 6 , то говорят, что метод сходится линейно со

скоростью геометрической прогрессии со знаменателем q. Такая терминология объясняется тем, что при 6 -»-оо погрешность убывает как qh.

З а м е ч а н и е 2. Зафиксируем в неравенстве (9) индекс k и устремим р

к бесконечности. Тогда получим оценку погрешности

qk

	I хк —	1sg ■t _	|s (*o) — x01,	6 = 1 , 2 , . . ,	(11)
В правую	часть оценки	(11) входят только известные величины, в то			время
как оценка	(7) содержит заранее неизвестное значение х..

Приведем следствия из теоремы 1, содержащие более удобные для проверки условия сходимости.

Будем предполагать, что s(x) непрерывно дифференцируема на отрезке UT(a).

С л е д с т в и е 1. Если
\ s ' ( x ) \ ^ q < l	(12)
для х е Д (а ), выполнено условие (6) и х0е Д ( а ) ,	то уравнение (2)
имеет единственное решение х ,е £ /г(а), метод (3)	сходится и спра­
ведлива оценка (7).
Действительно, из (12) следует (4) с ^ е ( 0, 1).
	197

С л е д с т в и е 2. Пусть уравнение (2) имеет решение х,, функ­

ция s(x) непрерывно дифференцируема на отрезке
11т{х,)={х\ \х—а- , |^ г}	(13)
и |s'(x.) | <1. Тогда существует е>0 такое, что на отрезке	Ut(x,)

уравнение (2) не имеет других решений и метод (3) сходится, если ТОЛЬКО А'„1=.Ut {x,).

Д о к а з а т е л ь с т в о . Поскольку s(x) непрерывно дифференци­ руема на отрезке Ur(x.) и |s'(x.) | <1, найдутся числа д е ( 0, 1) и

е е (0, г] такие, что

\s'(x) | ==S<7 < 1

для всех х 'е[/((х,).

2. Метод Эйткена ускорения сходимости. Предположим, что ка­ кой-либо итерационный метод имеет линейную сходимость, т. е.

xk—x ,^ a q \ q<=(0,1), k=l,2, ...

Числа a, q, х, заранее неизвестны, но их можно найти, используя три последовательных итерации хк, хк+1, хк+г. Составим уравнения

xh—x, = aq\ хкы—х:, = aqk+i, xM —x, = aqh+i

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

Axk = Xkn— *k — aqk (q— 1), А2хк= Ax*+1 — Axk — aqh (q — l)2,

(14)

Метод Эйткена ускорения сходимости состоит в том, что после вычисления xh, xh+l, хк+г производится пересчет по формуле

и —

(W > 2

Ук %k+2 (15)

ЛЧ

и значение ук+, принимается за новое приближение. Если бы равен­ ство (14) выполнялось точно, то ук^, совпало бы с точным решением х.. В общем случае ук+1 дает лучшее приближение к х., чем очеред­ ная итерация хк+г. Подчеркнем, что главным предположением здесь является требование линейной сходимости основного итерационного метода. В случае методов, имеющих более высокую скорость схо­ димости (например метода Ньютона), ускорение по Эйткену в фор­ ме (15) неэффективно.

На практике не обязательно проводить пересчет по формуле (15) на каждой итерации к. Употребительны методы, в которых та­ кой пересчет осуществляется циклически, т. е. через определенное число основных итераций.

С помощью метода Эйткена на основе известных итерационных методов можно получить иногда новые итерационные методы, об-

198

ладающие более высокой сходимостью. Рассмотрим, например, ме­ тод релаксации

+ f (Хк) = о

(16)

т

(см. (6) из § 1), который имеет линейную сходимость, если M,>f'(x) > 0 , 0< т< 2 /М „

Предположим, что при некотором k получены значения xk, хк+, %h+2‘ Вычислим согласно (15) величину

_„	(хь	- w	2	(17)
Укк1 ■— ^£+2	Хк+2		+ xk

и исключим из (17) с помощью (16) величины хк+1, хк+2. Имеем

хк+1= X k — тf ( X k ) ,

Xv+ 2 = X k + l — т/ (.r,lf!) = X k — if (x /;) — T/ {xk— T/ (**)),

следовательно,

/2 (**)

i/fc+l ----C'i '

/ Pfc) —/ (-b — Т/ (•**))

Проведенные построения позволяют предположить, что одно­ шаговый итерационный метод

	Уь+1—Уь	/ 2 G fo)	(18)
		т*f(yk) - n y k - xf{yk))

обладает более быстрой сходимостью, чем исходный метод релак­ сации (16). Действительно, как показано, например, в [25], метод (18) при т=1 (метод Стеффенсена) имеет квадратичную сходи­ мость.

§3. Сходимость метода Ньютона

1.Простой вещественный корень. Предположим, что уравнение

f(x)= 0	(1)
имеет простой вещественный корень	x = xt, так что f ( x j = 0,

f'(x.)=?=Q- Будем предполагать, что }{х) дважды непрерывно диф­ ференцируема в окрестности корня х„. Исследуем сходимость ме­ тода Ньютона

X k ^ X k - — ^ - ,	/2 = 0 , 1 , . . .	(2)
Г (хк)
Заметим прежде всего, что (2) можно рассматривать как част­
ный случай метода простой итерации
*ft+i = s(xft),	£ = 0 , 1 , . . . ,	(3)
для которого

s w = * —/ W	■	(4)
		199

R § 2 было показано, что для сходимости метода (3) достаточ­ но потребовать, чтобы в некоторой окрестности искомого корня выполнялось неравенство

	\ s ' ( x ) \ ^ q < \ .		(5)
	Для функции (4) имеем	{ (х) г (*)
	s'(x)
		(Г W)2	’

и если хт— корень f(x), то s'(x#) =0. Поэтому найдется окрестность корня, в которой выполнено неравенство (5). Тем самым при над­ лежащем выборе начального приближения метод Ньютона сходит­ ся. Однако следствием малости s'{x) в окрестности является не просто сходимость, а сходимость существенно более быстрая, чем в общем случае метода простой итерации. В следующей теореме доказано, что метод Ньютона имеет квадратичную сходимость, т. е.

что он сходится и погрешность на		(й-{-1)-й итерации					пропорцио­
нальна квадрату погрешности на й-й итерации.
Т е о р е м а 1. Пусть х. — простой вещественный корень уравне­
ния (1) и пусть У(х)Ф0 в окрестности
Ur(x.) = {*: \х—хш\ <г}.
Предположим, что f"(x) непрерывна в Ur(x,) и
0 < m 1= inf	| /' (х) |,	АТ2=			sup	|/"(х)|,	( )
X & J r (X,)					X & J г\х,)		6
причем	М« | х0— х* |
		< 1 .					(7)
	2т х
Тогда если г0б ( / г(г ),	то метод Ньютона (2)					сходится, причем
для погрешности справедлива оценка
\Хк—Х>\<:Я2к~1\Х0—ХА>							(8)
где	мг|х0 —х*|			^	J
							(9)
4	2т,			"
Д о к а з а т е л ь с т в о . Из уравнения				(2) получим
Хш	x, — xk	xt			/(**>
					t (*А>
или
		F(Ч)
	*. =				•		(10)
		„	,	,
		/	(*ft)
F(x) = (x—X')f'(x)—f(x).							(И)
Заметим, что Т(х.) =0 и
F(x) = (* - * )№ )■							(12)
200