2.2. Ошибка деления на нуль.

Очевидной ловушкой в методе Ньютона является возможность деления на нуль в формуле (2.3), которая возникает, если f ' (x(k ) )= 0 . Вполне вероятно,

что f (x(k ) ) достаточно близко к нулю и x(k ) приемлемое приближение к корню. Рассмотрим данную ситуацию и определим скорость сходимости итерации.

Определение (порядок корня): Предположим, что функция

f (x) и ее

производные f ' (x),..., f (M ) (x)

определены и непрерывны на интервале в ок-

рестности точки x = x* . Говорят, что

f (x )= 0 имеет корень порядка М в точке

x = x* тогда и только тогда, когда

f (x* )= 0 ,

f ' (x* )= 0 , …, f (M −1) (x* )= 0 , f (M ) (x* )≠ 0

(2.9)

Корень порядка

M = 1 часто называют простым корнем,

а если M > 1 ,

его называют кратным корнем. Корень порядка M = 2 иногда называют двой-

ным корнем и т.д.

f (x )= 0 имеет корень порядка М при x = x* , то

Лемма: Если уравнение

существует такая непрерывная функция h(x),

что

f (x) можно представить в

виде произведения:

f (x)= (x − x* )M h(x), где h(x* )≠ 0

(2.10)

Пример 2: Функция f (x)= x3 − 3 x + 2 имеет простой корень в x = −2 и

x* = 1 .

*

двойной

в

Это

можно

проверить,

рассмотрев

производные

f ' (x)= 3 x2 − 3 и

f "(x)= 6 x . При значении x

= −2 получим

f (−2)= 0 и

f ' (−2)= 9 , так, что

*

M = 1 в соответствии с (2.9), поэтому x* = −2 – простой

корень. Для значения

x* = 1

получаем, что f (1)= 0 ,

f ' (1)= 0

и

f "(1)= 6 ,

так что M = 2 в определении (2.9), поэтому x*

= 1 – двойной корень. Заметим

также,

что

разложение

на

множители

функции

f (x)

имеет вид

f (x )= (x + 2) (x − 1)2 .

2.3. Скорость сходимости.

Рассмотрим следующие свойства сходимости. Если x* - простой корень уравнения f (x )= 0 , то метод Ньютона сходится быстро и количество десятичных знаков точности приблизительно удваивается с каждой итерацией. С дру-

гой стороны, если x* является кратным корнем, то ошибка в каждом последующем приближении равна части предыдущей ошибки. Отметим, что метод Ньютона характеризуется вторым порядком сходимости вблизи корня и первым порядком – вдали от него.

15

2.4. Модификации метода Ньютона.

Метод касательных, являясь весьма эффективным средством численного анализа, к сожалению, имеет достаточно жесткие ограничения. Действительно, он не может применяться для сеточных уравнений; при нарушении знакопостоянства производных (рис. 2.3); при существовании неограниченных вторых производных и др. Так, если даже условие знакопостоянства нарушено вдали от

корня, где выбрано x(0) , а вблизи корня выполняется, то все равно метод касательных неприменим (рис. 2.3), если не произвести сужение начального отрезка.

y

y = f (x)

x(2)

x*1

0

x*2

x(1)

x(0) x

Рис. 2.3 Пример неприменимости метода касательных

Помимо этого, в случае, если функция f (x ) достаточно сложная, то будет

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

В силу этого в ряде случаев могут оказаться более предпочтительными модификации метода касательных. Рассмотрим основные из них:

2.5. Упрощенный метод Ньютона

Методика его применения совпадает с изложенной для метода Ньютона, но

вместо формулы (2.3) используется формула:
	(k +1)		(k )		f (x(k ) )
x		= x		−		, где k = 0 ,1,...	(2.11)
					f ' (x(0) )

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

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

Для этой модификации снимаются некоторые ограничения метода касательных, например условие знакопостоянства производных. Сходимость упрощенного метода Ньютона линейная.

16

y

y = f (x)

0

x*

x(2) x(1)

x(0)

x

Рис. 2.4 Геометрические построения для упрощенного метода Ньютона

2.6. Метод Ньютона-Бройдена

Этот метод позволяет увеличить скорость сходимости последовательных

приближений благодаря использованию формулы:

(k +1)

(k )

f (x(k ) )

x

= x

− ck

, где k = 0 ,1,2,...

(2.12)

f ' (x(k ) )

где ck - число,

которое выбирается на каждой итерации так, чтобы уменьшить

значение

f (x(k +1) )

по сравнению с

f (x(k ) )

. При ck

= 1

метод Ньютона-

Бройдена совпадает с методом Ньютона.

Как

правило,

при

плохой сходимости

или ее отсутствии

полагают

0 < ck < 1

(рис. 2.5,а), а при хорошей сходимости для ck

= 1

полагают ck

> 1

(это ускоряет сходимость (рис. 2.5, б)).

f (x(0) )

a )

y

0 < ck < 1

б )

y

f (x

(0)

)

ck > 1

y = f (x)

x(1)

x*

x*

x(0)

x(1)

x(0)

0

x

(1)

x

0

x

(1)

δ (0)

x

δ (0)

c δ (0)

c0δ

(0)

0

f (x(1) ) > f (x(0) )

Рис. 2.5 Геометрические построения для метода Ньютона-Бройдена

17

На рис 2.5 прямоугольниками отмечены точки x(1), полученные при c0

= 1 ,

(k )

f (x(k ) )

k

= 0 ,1,... -

δ

=

,

поправка, соответствующая методу Ньютона, а

f ' (x(k ) )

точки

x(1) = x(0)

− c δ(0) получены по методу Ньютона-Бройдена.

0

2.7. Метод секущих

f (x )

В этом методе производная функции

подсчитывается с помощью

конечно-разностных соотношений:

f (x(0) )− f (x(0) −δ )

-

в точке

x(0)

используется формула

f ' (x(0) )=

,

где

δ

– малая положительная величина;

δ

-

в

точках

x(k ),

k = 0,1,...

используется

формула

f '

(

x

(k )

)

=

f (x(k ) )− f (x(k−1) )

.

x(k ) − x(k−1)

Вычисленное значение f ' (x(k ) ) определяет тангенс угла наклона секущей

(рис. 2.6).

y

		x*			x(0)
	0	x	(2)	x	(1)	x
					δ
		y = f (x)
Рис. 2.6		Геометрические построения для метода секущих

Методика применения метода секущих совпадает с методикой применения метода Ньютона, но вместо (2.3) используется формула:

x(k +1) = x(k ) − f (x(k )f)(−x(fk )()x(k −1) ) (x(k ) − x(k −1) ), k = 1,2,... (2.13)

18