Файл: Ермолаева Э.Н. Элементы численного анализа учеб. пособие.pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 07.07.2024

Просмотров: 149

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

? ( х ) є

^] П Р И

 

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).

§ 2.6. О Ц Е Н К А П О Г Р Е Ш Н О С Т И М Е Т О Д А И Т Е Р А Ц И И

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

I Xn-\-k — Хп \ =

| Хц+k — Хп : *

- l

-f-

Хп + к-1

— Х„ ; ь 2

Т"

Хп ' k-2 ~

— . . . — Хп : 1 f

Хп г 1 — Хп |

С

* „

д. -

Хп + и-\ [ + \ Хп\ к-\ —

— Xn +

k - 2 |

" И

| *п ;

fc-2

—

ЛГл-і-Л-з

[ +

• •

•

+

І -

W i —

хп

| .

В силу неравенств

(2.12)

имеем.

 

 

 

 

 

 

 

 

і хп+к - хп

\ < 9» (1 + ? + <?2 + . . . +

 

 

 

! х{

-- х„ ; -

 

 

J

 

пк

 

 

 

 

I ^

 

лп

- -

 

I v

 

V 1

 

 

 

nil

 

 

*

V

 

_

у

 

"

 

 

 

 

 

 

1 _

q

• ~ i

 

~« « -

1 _ 9

 

<• '

 

 

 

 

так как q< 1.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Поскольку

lim л:„

* *= с,

то в пределе

получаем

 

 

 

 

 

 

 

 

 

 

 

1

-

 

* ! — * „ , .

 

(2.13)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Из этой формулы видно, что процесс итерации сходится к

корню £

тем быстрее, чем меньше

| «' (х) | .

 

 

 

 

Выведем другую формулу для оценки

абсолютной

погреш­

ности. Поскольку решаемое уравнение f(x)

 

= 0 переписывается

в виде х — ? (х)

== 0,

то

/

(х)

=

х — « (х),

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

 

 

/

(*п)

=

* л

 

-

?

(•*„)

=

Ха

-

 

*„.,

,

,

 

 

а так как / ( £ )

=* 0,

то справедливо

 

 

 

 

 

 

 

 

хл -

хп,,

 

=

/ (*„) =

/

(*„)

-/(?)

=

/'

(с) (хп

-

I)

но теореме Лагранже, где с є (хп\ д). Поскольку

/' (с) - 1 - ?' (с) > 1 - ? ,

то имеем

а в силу неравенства (2.11):

- £ _ - ! * „ . - . * „ . , • .

(2.13')

Смотрите также файлы