книги из ГПНТБ / Ермолаева Э.Н. Элементы численного анализа учеб. пособие

Решение этого уравнения

л , - л-., -

.

с « )

можно принять за первое приближение решения уравнения (2.1). * і Для выяснения геометрического смысла формулы (2.6) проведем касательную к кривой (2.2) в точке В(х0; /(*о)) для

случая расположения кривой, изображенного на рис. 2.8.

Уравнение касательной		к, кривой		(2.2) в точке В запишется
в виде:
> ' - / ( • * < > ) = / '			(•*„)	( * - * „ ) •
Положив в этом уравнении у = 0,				найдем х\ — точку пере­
сечения касательной	с осью	ОХ:
			f<JC0)
Таким образом,	уравнение		(2.6)	дает точку	пересечения
рассмотренной касательной с осью абсцисс.
Взяв точку Bi(x\\	f(xi)),	проведя касательную к кривой
(2.2) в этой точке и обозначив			точку	пересечения	новой каса­
тельной с осью ОХ через Х2,		будем иметь:
	х -	х	/(*»>

г

Продолжив этот процесс, найдем, что

Описанный процесс уточнения корня предложил Ньютон.

Теорема. Если f(a)

/

(b) <

0,

причем f'(x)

и / " ( * )

отлич­

ны от нуля и сохраняют

определенные

знаки

при

х є [а; Ь], то

исходя из начального приближения х0

є [а;

Ь], удовлетворяю­

щего неравенству f(x0)f"(xo)>0,

можно

вычислить по

форму­

ле (2.7) корень

g уравнения/(х) = 0

с любой

степенью

точ­

ности (?= Игл л'„) .

Очевидность

теоремы

вытекает

из

рассмотрения рис. 2.8.

Напомним,

что знак

\" {х)

определяет

выпуклость

кривой

(f"(x)>0

— кривая вогнута; f"(x)<0

— кривая

выпукла). На

рис. 2.8 кривая вогнута, f " ( x ) > 0

и последовательность

хп,

оп­

ределяемая по формуле

(2.6), сходится

к корню

с, если

взять

х0 = Ь. Так

как f(b)

>0,

то f(b)f"(b)

>0.

Если

же

за

начальное приближение взять х0

= а,

то

f(a)f"(a)<0,

так

как f(a)<0.

И если

провести

касательную к

кривой (2.2)

в точке A (a; f(a)),

то точка пересечения этой

ка­

сательной с осью

абсцисс

х\

даст

отдаление

от

корня

а не

приближение к нему.

Остальные возможные случаи (различные варианты знаков

/(a), [(b),

f"[х))

предоставляем

читателю рассмотреть

на

ри­

сунках.

Из формулы

(2.7)

видно, что чем больше численное

значе­

ние производной

f (х)

в окрестности данного корня, тем

мень­

ше поправка, которую нужно прибавить к (п—1)-му

прибли­

жению,

чтобы получить

n-е приближение.

Поэтому

метод

Ньютона особенно удобен, когда в окрестности данного корня график функции имеет большую крутизну. Если же численное значение производной /'(Л;) близ корня мало, то поправки бу­ дут велики и вычисление корня по методу Ньютона может ока­ заться долгим, а иногда и невозможным. Тогда применяют ме­ тод хорд.

Пример 2.3. Решить уравнение	х3	— Зх— 5 = 0		с точностью
до 0,001, приняв за первое приближение х0			= 3.
Р е ш е н и е .
/ (х) — Xі — Зх — 5; / ' (х) =	Зх2	-	3; fix)	= 6х .

Так как /'(3) =24, хорошо применять метод Ньютона. Поскольку /(3)f"(3)>0, применяем формулу (2.7):

і ЗлГя_і 5

X — Х„-\	34-! - 3

Вычисления по этой формуле дадут:

*, =

3 -

2 7

~

^ ~ 5

=

2,46 ;

<>,.«

14,89 - 7 , 3 8

- 5

A s

5 = 1 2 , 4 6

1 8 , 1 6 - 3

= 2 ' 2 9 5 '

12,088 -

6,885

- 5

л - 8 - Л 2 У о

1 5 , 8 0 1 - 3

- - . ^ J -

хк

-

2,279 -

11,837 — 6,807 -

5

= 2,279

"

| Ц

; ' е и

Г '

0

u

15,582

Итак, с точностью до 0,001 выполняется

равенство хъ — х^

поэтому корень уравнения х3—Зх—5

= 0 с точностью до 0,001

равен 2,279.

з

Пример 2.4. Применяя

метод Ньютона, найти

J/970 с точ­

ностью до 0,001.

Р е ш е н и е .

Сначала

рассмотрим

более

общий случай —

к

а

уравнения хк—а = 0.

нахождение

корня

|/

как

решение

Тогда

/

(Л-) =

х* — a,

f

(х)

=

kx"-x

и формула

(2.7) примет вид

x

n -

i

-

а

Хп

— Х п - \

hyk--l

или

R

X

n

1

х„

a +

(k-

])*„*_.,

Для решения примера

возьмем

/г = 3,

а так как о = 970, то

возьмем х0 = Ю. Поскольку

/ ( 1 0 )

/ " (10) =

(108

— 970) • 3 • 2 • 10 >

0 ,

то формула

(2.7) применима.

Получаем

_

а

+

2Х^

970

4- 9

. i n 3

* i =

3

1

0

2

= 9,900;

3. З а к . 428.

33

Итак, Б пределах заданной точности значения Х\ и Хг совпа-

					:з
дают, поэтому с точностью до 0,001				имеем V 970 ^ 9,899.
Иногда метод Ньютона видоизменяют: знаменатель фор­
мулы (2.7) заменяют на f'(xo),			т. е. решают по формуле
	Хп-\			fix,,	•)
Геометрически это значит, что все касательные, кроме пор­
кой, заменяют	наклонными	прямыми,			параллельными	каса­
тельной в точке	(х0; )'(хо)).	Здесь		последовательность		хп схо­
дится к корню	с хуже, но зато расчеты				значительно упроща­
ются, если fix)	имеет сложное		выражение.
На практике	часто используют			комбинированный		метод,

т. е. применяют одновременно и способ касательных, и способ

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

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

При комбинированном методе абсолютную погрешность можно вычислить, находя длины отрезков [х'і; Хі], [хГ2, х&....

(рис. 2.9).

Р и с . 2.9

Пример 2.5. Решить уравнение х— sin х— 0,5 — 0 с точ­ ностью до 0,001.

Р е ш е н и е .

Составим

табл.

2.1

значений

функции

/(#)

=х—sinx—0,5.

Таблица 2.1

X

— 1

0

1

2

у

-

0,659

- 0 , 5

—

0 , 4 1

0,591

Из таблицы

видно, что корень уравнения

с лежит

между

1 и 2. Так как f'(x) = 1—cos#>0,

то корень с

на отрезке [1; 2]

единственный. Формула

Ньютона

примет вид:

Л я

—

А",; - і

Л",,

і — Sill

Х„-\

0,5

1

— COS

Х„-\

Так как

/ "

(л) =

sin #

и

f

(2) / " (2) =

0,591 sin 2 >

0 ,

то возьмем х0 = 2. Тогда

л-,

=

2 -

2

~

S 1 " 2 ~ 0

, - ~ =

1,583 (sin 2 .= 0,909)

'

1 ~

cos 2

По формуле хорд

(2.4) имеем:

х'

=

1

2

-

1

( _

0,341) = 1,306 .

0,591 -

( -

0.341)

1

*

Применяя дальше формулы (2.7) и

(2.4)

к отрезку

[1,366;

,583], получаем:

,

х 3

-

1 583 -

1.583

-

1,000 -

0,5

_

-

1,083

і +

0,012

i ' 3 6 6

+ o

' n

' 3 - 4 f M ^ 3 L ^ 1

' 4 9 1 -

Далее по тем же формулам (2.7) и (2.4) находим #3 = 1,498

и #'3 =1,498, т. е. корень

уравнения

с точностью до 0,001 есть

1,498.

Описанные выше метоДы последовательных приближений п

математике

называются

итерационными

(по-латыни

итера­

ция — последовательно повторяющийся единообразный про­

цесс). Это единообразие'очень	удобно в применении быстро­
действующих вычислительных	машин.

В результате итерации получаются все более точные при­ ближенные значения.

Однако непосредственно методом интераций называется способ численного решения уравнения, излагаемый ниже.

§ 2.5. М Е Т О Д И Т Е Р А Ц И И ( П О С Л Е Д О В А Т Е Л Ь Н Ы Х

П Р И Б Л И Ж Е Н И И )

Требуется решить уравнение (2.1), где функция (2.2) — непрерывна. Перепишем уравнение (2.2) в равносильном виде:

.* =

<?-(*)•

(2.8)

Например, уравнение

ех—sinx

= 0 можем переписать в виде

х = ех—sinx+x.

И

вообще,

переписав

уравнение

(2.1)

в

виде

x = x + cf(x),

где

с

—

произвольная постоянная,

отличная от

нуля, видим,

что уравнение

(2.1) в виде (2.8)-можно предста­

вить любым числом способов.

Выберем

одно конкретное

уравнение

(2.8) и найдя

каким-

либо способом грубо приближенное значение корня х0

и под­

ставив это значение в правую часть уравнения

(2.8), получим

некоторое число х,=ср(л-( 1 ).

Подставляя теперь в правую часть

того же

уравнения

(2.8)

число Х\,

получаем

новое

число

x2 = 'f(xl).

Повторяя этот процесс, находим

хя

=

?(*„_ ,);

п

= 1,

2 , . . .

(2.9)

Если последовательность {хп}

сходящаяся, т. е.

lim хп

= £,

то переходя к пределу в равенстве

(2.9)

и используя непрерыв­

ность функции

ts (х),

получаем

lim хп =

lim 'і

(x„-i)

—

<? (Hm хп-\)

или

£ =

© ( £ ) ,

т. е. предельное

значение

?

является

корнем уравнения

(2.8),

а следовательно, и уравнения

(2.1).

Однако последовательность

хп

может расходиться,

но это

еще не значит,

что

решения

уравнения

(2.1)

не

существует,

просто

может

оказаться,

что

процесс

итерации

выбран не­

удачно.

Чтобы процесс итерации оказался сходящимся, достаточно,

чтобы в окрестности

корня

производная

(х)

удовлетворяла

неравенству

? '

(.V)

• </,

где

q

< \ .

(2.10)

Теорема (строгая формулировка): пусть функция г-?(х) оп­ ределена и дифференцируема на [а; Ь], причем все ее значения

? ( х ) є

^] П Р И

x

6

ЭД-

Если существует

такое число q< 1,

что

(х)

<

<7

при всех

хє [а; Ь], то:

1) процесс итерации

х„ — a (х„

і) сходится

независимо от

начального значения

х п є

[а;

Ь];

является

единствеы-

2) предельное

значение

£ — lim «v„

Л ->••*=

пым корнем уравнения х — &(х) на отрезке [а; 6].

Доказательство.

Рассмотрим

разность

двух

равенств

хп

=

(л-л -і)

и

=• ? (л;л _2 ) :

х л

—

=

а

— Ф (лгл _2 ),

/г =

2,

3, 4

, . . .

Применив теорему Лагранжа,

получаем

хп

—

x „ - i

=

?'

(т,„_і) (л:„_і

— х,,-г)

,

где

Т(„_] Є

[ Х „ -

г'.

- * V

l ]

•

В силу условия

| «' (ті л _і)

I < q имеем:

Xn

—

Xa-x

\ <q\

Xn-l

— X„-2

, •

(2.11 )

І Із этого неравенства

следует:

I х, — х, I < q I Xj — x0 !

1 x.j — x%

<7 I x.> — Xj j

> ^7"

^ i

^"o

} .

(2.12)

X„

Xn — \

I ^

'

j

і

^(i

Рассмотрим

ряд

* 0 +

(-«1 — * o ) +

( * 2 — X l )

+

• • • +

(Xa

-

Xn-i)

+

• • •

Частичной

суммой

этого ряда

будет

Sn

+ \ =

хп,

В силу нера­

венств (2.12) члены ряда по абсолютной величине меньше со­ ответствующих членов геометрической прогрессии со знаме­

нателем q<\,	поэтому ряд абсолютно сходится, следователь­
но, существует	предел
	lim 5Л 11 — lim хп	— t	,
который является корнем уравнений		(2.8).
Докажем, что этот корень — единственный на рассматри­
ваемом отрезке [а; Ь] при выполнении условий				теоремы. Если
предположить,	что существует другой		корень	£ j =г Ї, т. е.

=	z (EJ,	то имеем	с, — с — s (с,) — a ( t ) .		Приме­
ним к правой части теорему				Лагранжа: с, — с — <?'(с) (с, — с),
где	с- є [с; с,]. Переписав			последнее равенство	в виде
(cj — с.) [ I — «' (г)] = 0 ,			в силу того, что ?' (<~)=^1		по усло­
вию, получаем		с, = с,	т. е. что с — единственный		корень на
[а; Ь].

Из теоремы следует, что последовательность (2.9) сходится при любом выборе начального значения х0 из [а; Ь]. Благода­ ря этому метод итерации является самоисправляющимся, т. е. отдельная ошибка в вычислениях, не выводящая за пределы отрезка [а; Ь\ не повлияет на конечный результат, так как оши­ бочное значение можно рассматривать как новое начальное значение х0 , при этом может лишь возрасти объем вычислений.

Свойство самоисправлепия делает	метод итерации одним
из надежнейших методов вычислений,	тем более, что этот ме­

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

Пример 2.6. Найти один действительный

корень

уравнения

х—х3 + 2 = 0.

f(x)=x—х3

Р е ш е н и е .

Так как функция

+ 2

принимает

значения /(1) = 2 > 0

и /(2) = — 8<0 , то корень находится на от­

резке [1; 2]. Перепишем

в виде х = х3 —2, тогда

ср (х)

=

хл — 2, о'

(х)

— Зх- ,

но так как

на [1, 2], то метод итераций

неприменим.

Перепишем

уравнение

х—х3

+ 2 = 0

по-другому:

х

з

2 ,

=

|

.V

тогда

'

3

і

? (х)

=

V х + 2 ,

%' (х) =

з

*

•

З V

(х +

2)2

Так

как

теперь

«' (х)

<

1

на [1; 2], то процесс

итераций

применим.

Возьмем х 0

= 1 . Решение

проводим

по формуле

(2.9):

3

л-,

т

(1)

=

[ЛЗ == 1,442

;

з

А-а = % (Xl) = V3,442 = 1,510 ;

/				'з
х3	=	ъ (*,)	=	J 3,510	=	1,520 ;
				з
xt	=	-J. (*,) =		I ',3+520	=	1,521 ;
•Ч = ? (*4 )				з
			=• /3,521			1,521 .

Итак, с точностью до 0,001 искомый корень равен 1,521. Рассмотрим геометрическое истолкование процесса итера­

ции.

Поскольку уравнение (2.1) преобразовано к виду (2.8), то графически левая часть уравнения у—-х изобразится биссек­ трисой, а правая — кривой с уравнением у = -•? (х). Величина абсциссы точки пересечения биссектрисы іі кривой у =» 'f (.v) будет, следовательно, корнем уравнения (2.1) (рис. 2.10).

Пусть нашли грубо приближенное значение корня х0. Отло­ жим его по оси абсцисс (рис. 2.11 и 2.12). Формула первого приближения хх -- -f (v0 ) показывает, что геометрически для получения Х\ следует на кривой <?(*) найти точку, абсцисса которой равна х0 (на рис. 2.11 и 2.12 это будет точка Л), и, сле­ довательно, ордината равна » (х()). Из полученной точки А сле­ дует провести прямую, параллельную оси абсцисс, до пересе­

чения с прямой у = х в точке В. Точка	В будет иметь абсциссу,
равную X), так как ее ордината равна	<s (*„) и так как у бис­

сектрисы координатного угла ордината и абсцисса равны. Для второго приближения х2 =- <р (xt), продолжая построение со­ вершенно таким же образом, получим точку D с абсциссой хч.

На рис. 2.11 и 2.12 видно, как				при описанном геометрическом
построении абсциссы	хп	-> t	и видно, что угловые коэффициен­
ты касательных ъ'	(с) | <		1.	На рис.	2.13	и 2.14 абсциссы х„
удаляются от корня	?,	причем		«' (£)	і >	Г.

Р и с . 2.12

Р и с . 2.13

Из рисунков также видно, что при '•?'(•*) > 0 последова­ тельность хп • > с монотонна; если «' (х) < 0, последователь­ ность х„ колеблется около

Р и с . 2.14

Р и с . 2.15

Надо заметить, что для метода итерации необязательно представлять данное уравнение (2.1) в виде (2.8), а можно представить в более общем виде fi(x) =f?.(x) (рис. 2.15).