[ Буслов, Яковлев ] Введение в численный анализ

И т йлоро ско о р ло ния т к н тру но и ть, что

f(xi) + f(xi 1)

= f(xi) +

hi2

f00(xi) +

hi4

f(4)(xi) + O(hi6) ;

4!24

2

2!22

îòêó

f(xi) + f(xi

1)

hi2

00

hi4

(4)

6

f(xi) =

f

(xi)

f

(xi)

O(hi ) :

2

2!22

4!24

По ст ляя это ыр ни (8), получ м

xi

h3i

hi5

f(xi) + f(xi

1)

(4)

1

6

f(x)dx = hi

12 f00(xi) +

f

(xi)[

1] + O(hi ) :

2

4!24

5

xiZ1

Д л , поскольку S =

2

M +

1

T , òî

3

3

xi

2f(xi) +

+

x Z

f(x)dx =

hi

(f(xi) + f(xi

1))

3

2

i

1

f(4)(xi)h5i

2

1

1

4

6

f(4)(xi)hi5

6

+

h3

5 i

+ O(hi ) = S +

[ 2] + O(hi ) :

4!24

5

3

4!243 5

Ито о, ля p ноотстоящих у ло и (8) по p шность сост ной формулы ср них ЖM ð í

b

b

N

N

Za

Za

hi3

5

X

X

ÆM =

f(x)fdx

hif(xi) =

24 f00(xi) + O(h ) ;

f(x)dx M =

i=1

i=1

òî ñòü

ÆM

1

N

hi3 f00 C = h2jjf00jjC

N hi = (b a)

f00 C h2 :

X

j j

jj

jj

24

X

24

jj

jj

24 i=1

i=1

È (9), í ëî è÷íî

j

ÆT

j

(b a)

jj

f00

jj

C h2 :

12

È (10)

(9)

(10)

jÆS j jjf(4)jjC h4 (b a) :

6!4

З сь им тся и у сост н я фоpмул Симпсон S . Для о о щ нной фоpмулы Симпсон н о h м нить н 2h:

j Sj jj	f(4)	C 24h4				M4	4
	6! jj	22	(b		a) =	180	h (b		a) :
Æ

4.6Дру и формулы

4.6.1Ñïë éí-ê p òóp

Для при ли нно о инт риро ния мо но т к исполь о ть спл йны. Им нно, инт риру м я функция м ня тся спл йном, который и инт риру тся.

			x	x
Пусть x 2 i = [xi 1; xi] ; hi = xi xi 1	; ! = 1	! =		hii		1 . Ïðèì íèì ñïë éí S31 ëÿ ïðè ëè ííî î
èíò ðèðî íèÿ. Ç ì òèì, ÷òî í ïðîì óòê i	î ìî íî ïp ñò èòü è :

51

1			h2i		3	!)Mi + (!	3	!)Mi 1
S3	(x) = !fi + !fi 1 +		6	[(!					] :
Ç ñü Mi = S00(xi). Пусть S(!) = S31(x), òî
	xi		1
	x Z	S31(x)dx = hi Z0		S(!)d! ; (dx = hid!) :
	i	1

11

Ïðè ýòîì

R

!d! =

1

;

R

(!3

!)d! =

1

: Ò êèì î ð îì

2

4

0

0

xi

1

fi + fi

1

3 Mi + Mi

1

S3

(x)dx = hi

2

hi

24

:

xiZ1

|

{z

}

p

p

Д йст ит льно, тор я прои о н я от спл йн , ппроксимиру т торую прои о ную от функции и

h3i (Mi + Mi 1) h3i f00(xi) ;

24 12

что пр ст ля т со ой попр очный чл н формулы тр п ций (см. формулу (9)). Т ким о р ом происхо ит комп н- с ция оши ки формулы тр п ций. Оконч т льно

	b	N
	Za			fi + fi 1		Mi + Mi 1
		X			3
			hi	2	hi	24		:
	f(x)dx	i=1

З м ч ни . Спл йн-к p туp н сть к p туpн я фоpмул чистом и , поскольку он исполь у т н только эн ч ния функции, но и торы прои о ны от спл йн .

4.6.2Фоpмулы Филон

b

Пусть I = f(x)ei!xdx ; j!j >> 1=jb aj , f(x) м л нно м няющ яся относит льно п рио T = 2 =! кол ний,

Ra i!x

функция. В этом случ по инт p льн я функция f(x)e им т мно о осциляций н пром утк (a; b) и исполь о-

ни о ычных к p туpных фоpмул сьм тру н но, поскольку прихо ится лить пром уток инт риро ния н ольшо колич ст о ч ст й. О н ко н т н о хо имости м нять сю по инт р льную функцию инт рполяционным полиномом. Дост точно эту проц уру про л ть лишь с функци й f(x). Ит к, м ним f инт pполяционным полиномом p. То

N

N

(x xk)

f(x) p(x) =

X

j(x)f(xj) ;

j

(x) =

Y

;

L

L

(xj xk)

j=0

k=j;k=0

6

b

N

b

N

Za

Za

X

X

J =

p(x)ei!xdx =

j=0

f(xj)

ei!xLj (x)dx =

j=0

Aj(!)f(xj) :

b

Èíò p ëû Aj(!) =

R

ei!xLj(x)dx pутся эл м нт pных функциях. Получ мы при этом формулы при ли нно о

a

инт риро ния н ы ются формул ми Филон :

b

N

Za

I =

f(x)ei!xdx

X

Aj(!)f(xj) :

j=0

1

1

Ç ÷ : Äëÿ èíò p ëî sin !xf(x)dx ,

R1

cos !xf(x)dx получить фоpмулу Филон с тp мя у л ми: x0 = 1 ; x1 =

0 ; x2 = 1.

R1

52

4.6.3Сост ны фоpмулы Филон

Ð î ü ì ïpîì óòîê [a; b] í N ÷ ñò é a = x0 < x1 инт pполяционным полиномом pk н которой ст п ни,

b

N

xk

	X
I = Za	f(x)ei!xdx = k=1x Z		1
		k

< : : : < xN = b è í ê îì ïpîì óòê [xk 1; xk] ì íèì f(x) òî

N xk

X
f(x)ei!xdx J = k=1x Z		pk(x)ei!xdx :
	k	1

Ïpèì p. Àí ëî ôîpìóëû ñp íèõ.

	xk			xk
	x Z	f(x)ei!xdx x Z				1	f(x)ei!xdx =
	k	1	k
	= f(xk) ei!xk ei!xk 1		=		2		f(xk)ei!xk sin	!hk	:
				!				2
		i!

Оц ним по p шность этой формулы. Пр ст им f(x) при ли нно: f(x) f(xk) + f0(xk)(x xk) . То по р шность R при ли нно описы тся ыр ни м

xN

N

xk

R =

r(x)ei!xdx

X

f0(xk)

(x xk)ei!xdx =

xZ0

k=1

xkZ 1

2i

N

!hk

!hk

!hk

i!x

X

f0

k ;

= !2

2

2

cos 2

e

k=1

(xk) sin

ò. . ñëè ïðîè íè !hk поря к 1, то фоpмул Филон им т н ольшую по р шность, проти ном случ по р ш- ность то о поря к , что и н ч ни инт р л .

53

54

Ãë 5

Ñèñò ìû óp í íèé

5.1Ð ø íè í ëèí éíûõ óp í íèé

З чу н хо ния р ш ний ур н ний мо но формулиро ть р личными спосо ми. Н прим р к к чу н н - хо ни корн й: f(x) = 0 , или к к чу н н хо ни н по и ной точки: F (x) = x . При этом исимости от формулиро ки чи у о но прим нять т или ины спосо ы р ш ния. Р ссмотрим сн ч л о ном рную ситу цию.

5.1.1Î íîì ðíûé ñëó÷ é

М то л ния попол м

Прост йшим м то ом н хо ния корн й ур н ния f(x) = 0						я ля тся м то л ния попол м или ихотомия.
Пр поло им мы н шли точки x0			è x1, ò êè ÷òî f(x0)			è f(x1) им ют р ны н ки, то м у этими
òî÷ê ìè, ñëè f 2 C0 , н хо ится хотя ы о ин кор нь функции						f . Ïî ëèì îòð îê [x0; x1] попол м и м точку
x2 = x0+x1 . Ëè î f(x2)f(x0)		0 , ëè î	f(x2)f(1)		0 . Ост им ту поло ину отр к ля которой н ч ния н конц х
2

им ют р ны н ки. Т п рь этот отр ок лим попол м и ост ля м ту о ч сть, н р ниц х которо о функция им т р ны н ки, и т к л , о ости ния тр у мой точности.

К остоинст м м то л ния попол м сл у т отн сти о ысокую н ность и простоту, при этом от функции тр у тся только н пр ры ность. Поря ок схо имости м то лин йный, н к ом ш точность о р ст т о .

Í îñò òêîì ì òî ÿ ëÿ òñÿ òîò ô êò, ÷òî ïð ÷ ì í ÷ òü î ïðèì í íè , í î õî èìî ïð ðèò ëüíî í éòè

точки, н ч ния функции которых, им ют р ны н ки. Оч и но, что м то н прим ним ля корн й ч тной кр тности. Он т к н мо т ыть о о щ н н случ й компл ксных корн й и н сист мы ур н ний.

М то простых ит p ций

Пусть F : [a; b] ! [a; b] è F ñ òè : jF(x) F (y)j qjx yj ; q < 1 ( ч стности, тот ф кт, что F с ти , к к л кои ть, о н ч т, что F 2 C[a;b]). По т оp м Б н х сущ ст у т и инст нн н по и н я точк x , и он мо тыть н й н к к пр л простой ит р ционной проц уры

x = lim xn ; xn+1 = F (xn) ; n!1

í ÷ ëüíî ïðè ëè íè x0 прои ольн я точк пром утк [a; b]. Если функция F ифф р нциру м , то у о ным

кpит pи м с тия я ля тся число: q = sup jF 0(x)j = jjF 0jjC < 1. Ä éñò èò ëüíî, ïî ò îp ì Ë p í

x2[a;b]

jF (x) F(y)j = jF 0( )jjx yj jjF 0jjC jx yj = qjx yj :

55

Т ким о р ом, сли прои о н я м ньш иницы, то F я ля тся с ти м.

Óñëî è F ([a; b]) [a; b] ñóù ñò ííî, è î ñëè, í ïðèì ð, F (x) 2

н [0,1] , то н по и н я точк отсутст у т,

хотя прои о н я р н нулю. Скорость схо имости исит от личины

q . Ч м м ньш q , т м ыстр схо имость.

Ïpèì p. Ð øèòü óð í íè : x2 = a . Ç ñü, ñëè ê ÷ ñò

F

ять функцию F (x) =

a

, òî ñîîò òñò óþù ÿ

x

ит р ционн я проц ур у т им ть и :

xn+1 =

a

. К к н тру но у иться, м то ит р ций нном случ

xn

, н со п ющ й с со ст нно н по и ной точкой x = p

. Î í êî

р схо ится, при лю ой н ч льной точк x0

a

мо но к ч ст F пр ло ить и ол хитрую функцию, с той н по и ной точкой. Пусть F (x) =

1

[x +

a

].

2

x

Соот тст ующ я ит р ционноя проц ур сь им т и : xn+1 =

1

[xn +

a

], è ýòè èò ð öèè ñõî ÿòñÿ ê í ïî è íîé

2

xn

òî÷ê ëÿ ëþ î î í ÷ ëüíî î ïðè ëè íèÿ x0 2 (0; 1).

F(x) =

a

;

xn+1 =

a

; ;

x

xn

( F(x) =

1

[x +

a

] ;

xn+1 =

1

[xn +

a

] ; p:

2

2

x

xn

Ä éñò èò ëüíî, ï ð îì ñëó÷ F 0(xn) =

a

, ò. . ÷òî û F 0(xn) < 1 í î õî èìî ÷òî û xn2 > a, íî òî jF 0(xn+1)j =

xn2

a

=

a

xn2

a

j

x2

j

a2

=

a

> 1. Ò êèì î ð îì îòî ð íè F (x) = x ñ òè ì í ÿ ëÿ òñÿ.

n+1

x2

n

1

a

Äëÿ F (x) =

[x +

], í ïî è í ÿ òî÷ê ò ñ ì ÿ, ñèòó öèÿ pó ÿ. Ç ñü, õîòÿ ôîðì ëüíî ïðîè î í ÿ

2

x

мо т ыть о ольно ольшой (при м лых x), о н ко у н сл ующ м ш он у т м ньш 1. У имся этом:

										1					a				1								a
			F0(xn+1) =									1					=				1												=
										2					x2n+1				2						1	(xn +			a		)2
																									2				xn
	1	"					a						#		1 (1 +			a	)		2		2a				1 1 +					a			2		1
=			1				xn2							=				xn2					xn2		=							xn2				<		;
	2				1	(1 +				a	)2				2 (1 +						a	)2					2 (1 +					a		)2			2
																					2											2
										2
				2				xn												xn										xn

т. . т кой ит р ционный проц сс с схо ится.

5.1.2М то Ньютон

М то Ньютон или к с т льных ключ тся том, что сли xj

н которо при ли ни к корню x ур н ния

f(x) = 0 ;

f 2 C1 ; то сл ующ при ли ни опр ля тся к к кор нь к с т льной к функции f(x), про нной

òî÷ê xj. Т ким о р ом ур н нии к с т льной

f0(xj) = y f(xj)

í î õî èìî ïîëî èòü y = 0 è x = xj+1 , òî ñòü

x xj

xj+1 = xj

f(xj)

:

f0(xj)

f(x)

Поскольку м то Ньютон пр ст ля т со ой м то простых ит р ций при F(x) = x

, то н тру но у иться,

f0(x)

÷òî ïðè

f 2 C2 сущ ст т окр стность корня которой

jF 0j < 1 . Ä éñò èò ëüíî,

F 0 = 1

(f0)2 ff00 =

ff00

;

(f0)2

(f0)2

òî ñëè

x

кор нь кр тности , то о окр стности

f(x)

a(x

x ) è, ñë î ò ëüíî, F 0(x ) =

1

. Ç ì òèì,

÷òî ñëè

x | простой кор нь, то схо имость м то к с т льных к р тичн я (то сть поря ок схо имости р н 2).

У имся этом. Поскольку xj+1 x = xj x

f(xj)

, òî

f0(xj)

xj+1

x

=

1

f(xj)

=

1

xj x f0(xj)(xj x )2

(xj x )2

xj x

f0(x )(xj

x ) +

1

f00(x )(xj

x )2 + o (xj

x )2

2

:

(xj

x )2

[f0

(x ) + f00(x

)(xj

x

) + o(xj

x

)]

îòêó

lim

xj+1 x

=

f00(x )

:

2f0(x )

j!1 (xj x )2

56

Т ким о р ом схо имость м то Ньютон оч нь ыстр я. При этом сяких и м н ний м то о о щ тся н комп- л ксный случ й. Если кор нь x я ля тся корн м торой кр тности и ыш , то, к к н тру но у иться, поря ок схо имости ср у п т и ст но ится лин йным.

К н ост тк м м то Ньютон сл у т отн сти о лок льность, поскольку он р нтиро нно схо ится при прои -ольном ст рто ом при ли нии только сли ыполн но jff00j=(f02) < 1 , проти ной ситу ции схо имость сть лишь н которой окр стности корня. Дру им н ост тком м то Ньютон я ля тся тот ф кт, что н к ом ш

н о хо имо но о ычислять прои о ную.

5.1.3М то с кущих

Что ы и ть ычисл ния прои о ной, м то Ньютон мо но упростить, м ни прои о ную н р ностную,ычисл нную по ум пр ы ущим ит р циям, что эк и л нтно м н функции f(x) н инт рполяционный полином, прохо ящий ч р точки xj è xj 1 . При этом ит р ционный проц сс приним т и

xj+1 = xj fj (xj xj 1) ; fj fj 1

fj = f(xj) . то ухш о ый ит р ционный проц сс, поскольку исполь у т ля н хо ния посл ующ о при-ли ния пр ы ущих. Поря ок схо имости м то с кущих ст ст нно ни ч м у м то к с т льных и р н

случ о нокр тно о корня d = p5+1 . Ó èìñÿ ýòîì ñ÷èò ÿ ëÿ ó î ñò , ÷òî x = 0 .

2

0

1

00

2

3

+

+ O(xj )](xj

fj (xj xj 1) =

[f xj

2 f xj

xj 1)

=

0 (xj

x2

) + O(x3

x3

fj

fj

1

f

xj 1) +

1

f

00(x2

)

2

j

j 1

j

j 1

f00

2

1 +

xj + O(xj )

f00

2f0

2

= xj

= xj 1

xj 1 + O(xj ) :

00

f

2

2f0

0

"1 + 2f (xj + xj 1) + O(xj ) #

Т ким о р ом с точностью о скон чно м лых ол ысоко о поря к

00

xj+1 = xj

fj (xj xj 1) =

f

0

xjxj

1 + O(xj3) :

fj

fj

1

2f

f00

От р сы я ост точный чл н, получ м р кур нтно соотнош ни

xj+1

= xjxj 1

, =

2f0

, р ш ни которо о

ñò ñò ííî èñê òü è xj+1 = cxjd . Ïîñë ïî ñò íî êè èì ì: cd = 1 è

d2 d 1 = 0 , îòêó ñèëó òî î, ÷òî

d = p

ля схо имости н о хо имо, что ы

d

ыло поло ит льным, ключ м что

5+1 .

2

Поскольку н ни прои о ной н тр у тся, то при том о ъ¼м ычисл ний м то с кущих (н смотря н м ньший поря ок схо имости) мо но о иться ольш й точности, ч м м то к с т льных. Отм тим, что ли и корня прихо ится лить н м ло число и это при о ит к пот р точности (осо нно случ кр тных корн й), поэтому ы р относит льно м ло Ж ыполняют ычисл ния о ыполн ния jxj+1 xjj < Ж и про ол ют их пок мо уль р ности сос них при ли ний у ы т. К к только н чн тся рост, ычисл ния пр кр щ ют и посл нюю ит р цию н исполь уют. М то с кущих ст но ится н прим нимым. Т к я проц ур опр л ния мом нт оконч ния ит р ций н ы тся при¼мом Г р ик.

Ì òî ï ð îë

Р ссмотрим тр хш о ый м то , котором при ли ни xj+1 îïð ëÿ òñÿ ïî òð ì ïð û óùèì òî÷ê ì xj , xj 1 è xj 2 . Для это о м ним, н ло ично м то у с кущих, функцию f(x) инт рполяционной п р олой прохо ящ й ч р точки xj , xj 1 è xj 2 . В форм Ньютон он им т и

p2(x) = fj + fj 1;j (x xj) + fj 2;j 1;j (x xj)(x xj 1) :

57

Òî÷ê xj+1 опр ля тся к к тот и корн й это о полином , который ли по мо улю к точк xj . Поря ок схо-имости м то п р ол ыш , ч м у м то с кущих, но ни , ч м у м то Ньютон . В ным отличи м от р н р ссмотр нных м то о , я ля тся то о стоят льст о, что сли f(x) щ ст нн при щ ст нных x и ст р- то ы при ли ния ы р ны щ ст нными, м то п р ол мо т при сти к компл ксному корню исхо ной чи.тот м то оч нь у о н ля поиск корн й мно очл но ысокой ст п ни.

Поиск с х корн й

О щим н ост тком почти с х ит р ционных м то о н хо ния корн й я ля тся то, что они при о нокр тном прим н нии по оляют н йти лишь о ин кор нь функции, при том н и стно к кой. Что ы н йти ру и корни, мо но ыло ы р ть но ы ст рто ы точки и прим нять м то но о, но н т ник кой р нтии, что при этом ит р ции сой утся к но ому корню, н к у н й нному ( сли оо щ сой утся, к к ск м о мо но м то Ньютон ).

Для поиск ру их корн й исполь у тся м то у л ния корн й. Пусть x1 кор нь функции f(x) , р ссмотрим

f(x)
функцию f1(x) = x x1	. Òî÷ê x1	у т я ляться корн м функции f1(x) н иницу м ньш й кр тности, ч м f(x) ,

при этом с ост льны корни у функций f(x) и f1(x) со п ют с уч том кр тности. Прим няя тот или иной

м то н хо ния корн й к функции f1(x) , ìû í é ì íî ûé êîð íü	x2 (который мо т случ кр тных корн й
è ñî ï òü ñ x1 ). Д л мо но р ссмотр ть функцию f2(x) = f1(x) =		f(x)	, и иск ть корни у н ¼. По торяя
		(x x1)(x x2)
x x2
ук нную проц уру мо но н йти с корни f(x) с уч том кр тности.
Ç ì òèì, ÷òî êî ìû ïðîè î èì ë íè í òîò èëè èíîé êîð íü	x , то йст ит льности мы лим лишь н

í é ííî ïðè ëè íè x0 и т м с мым н сколько с и м корни спомо т льной функции относит льно истинных корн й функции f(x) . то мо т при сти к н чит льным по р шностям, сли проц ур от л ния прим нял сь у ост точно число р . Что ы и ть это о, с помощью спомо т льных функций ычисляются лишь п р ы ит р ции, оконч т льны про о ятся по исхо ной функции f(x) , исполь уя к ч ст ст рто о о при ли ния, посл нюю ит р цию, получ нную по спомо т льной функции.

5.1.4Ìíî îì ðíûé ñëó÷ é

М то простых ит р ций

М то простых ит р ций (посл о т льных при ли ний) л ко о о щ тся н случ й сист мы н лин йных ур н ний

fk(x1; x2; : : : ; xN ) = 0 ; k = 1; 2; : : : ; N ;

или кторной форм

f(x) = 0 :

ту сист му у о но к к и о ном рном случ пис ть и чи н н по и ную точку

F(x) = x :

З м ч ни . Н хо ни т кой формы писи мо т ок ться с мо по с с рь¼ ной ч й. Н о хо имо о иться и то о, что ы ото р ни F я лялось с ти м ( ля схо имости ит р ций) и, при этом ыло эк и л нтно исхо ной пост но к .

Âû ð ñò ðòî î ïðè ëè íè , îð íè ó ì èò ð öèè

x(j+1) = F(x(j)) :

58

Если ит р ции схо ятся, то они схо ятся к о ному и р ш ний сист мы ур н ний. Поря ок схо имости простых ит р - ций лин йный. Д йст ит льно, пусть x р ш ни , к которому схо ятся ит р ции, то ля к ой k-ой о компон нты

N

(j+1)

x(j)

) Fk(

x

X

@Fk(zj )

(j)

xk

xk = Fk(

) =

l=1

@xl

(xl

xl ) ;

zj н который ктор н пр л нии x(j) x

л щий м у этими точк ми. Ото р ни F у т я ляться

с ти м, сли норм м трицы прои о ных (со л со нн я с нормой ктор нном простр нст )

@Fk( k)

n @xl o

м ньш иницы. Поскольку кон чном рном простр нст с нормы эк и л нтны ( н чит и посл о т льность схо ящ яся по о ной норм , у т схо иться и по лю ой ру ой), то ост точно это усло и про рить ля лю ой и

@Fk		n	@Fk( k)	o .
норм м трицы с эл м нт ми Mkl = max j @xl	j , м орирующ й соот тст ующи нормы		@xl

Улучшить схо имость м то посл о т льных при ли ний, мо но (хотя он по пр н му ост н тся лин йной)сли у н й нны компон нты x(kj+1) исполь о ть ля н хо ния компон нт это о при ли ния x(j+1) с ном р ми ольшими k , то сть ор ни о ть ит р ции сл ующим о р ом

x(kj+1+1) = Fk(x(1j+1); x(2j+1); : : : ; x(kj+1); x(kj+1) ; x(kj+2) ; : : : ; x(Nj)) :

М то Ньютон

М то Ньютон , я ляясь ч стным случ м м то простых ит р ций с ктор-функци й F р ной

F(x) = x @f(x) 1 f(x) ; @x

ст ст нно о о щ тся н мно ом рный случ й. Ит р ции по м то у Ньютон им ют и

	(j+1)		(j)		@f(x)	1	(j)
x		= x			@x	x=x(j) f(x		) :

Про рк усло ий схо имости (то сть то о, что норм м трицы прои о ных @F=@x м ньш иницы) почти нико -н прои о ится, поскольку тр у т ольшо о о ъ м ычисл ний. С м м то Ньютон о ычно исполь уют н сколько ру ой писи. Им нно

@f(x)

x=x(j) x

(j)

= f(x

(j)

) ; x

(j)

= x

(j+1)

x

(j)

:

@x

Îïð ëÿÿ è ýòîé ëèí éíîé ñèñò ìû (ñê ì ì òî îì Ã óññ ) êòîð

x(j) è, ñîîò òñò ííî, ïðè ëè íè x(j+1) ,

но о р считы ют м трицу прои о ных и про ол ют ит р ции. Если н ч льно при ли ни ы р но у чно, то о ычно ост точно с о н скольких ит р ций, поскольку схо имость к р тичн я.

М то ы спуск

N

В ¼м функцию = P jfj (x)j2 . Он о р нич н сни у нул¼м и ости т с о о ло льно о минимум (нуля)

j=1

только т х точк х, f(x) = 0 . Т ким о р ом ч н поиск корн й ктор-функции с о ится к ч н поиск минимум ск лярной функции мно их п р м нных, м то ы р ш ния которой мы р ссмотрим соот тст ующ й л . З сь лишь отм тим, что эти м то ы н ы ются м то ми спуск и я ляются схо ящимися ля л ких функций, о н ко точность их н лик , и поэтому их ст ст нно исполь о ть ля н хо ния н ч льно о при ли ния с посл ующим исполь о ни м м то Ньютон . В но т к им ть и у, что м то ы спуск мо ут схо ится н кло льному минимуму, к о ному и лок льных ( исимости от ы ор ст рто ой точки), н от ч ющих р ум тся корням исхо ной чи.

59

5.2Ð ø íè ëèí éíûõ ñèñò ì

5.2.1О усло л нность лин йных сист м, по р шность

При р ш нии стр ктной чи Ax = b, A оп р тор прои ольной приро ы ным мом нтом я ля тся кор- р ктность пост но ки. З ч счит тся корр ктной сли р ш ни сущ ст у т и инст нно и, кром то о, р ш ни н пр ры но исит от хо ных нных (то сть, при b ! 0 ; x т к стр мится к нулю).

О н ко и н пр ры н я исимость от хо ных нных мо т им ть с ои ню нсы. Ч м м ньш ( ольш ) и м н - ни р ш ния ы ы т ри ция хо ных нных, т м ол хорошо (плохо) о усло л нной счит тся ч . Поняти о усло л нности я ля тся т м ол сущ ст нным ля числ нных м то о , поскольку н пр ктик хо ны нны и стны к к пр ило с н которой по р шностью. Кром то о, сущ ст уют оши ки окру л ния, о ник ющи при ы- числ ниях. Т ким о р ом форм льно корр ктн я ч , я ляясь плохо о усло л нной, мо т ок ться р р шимой столь н точно, что этом у т отсутст о ть пр ктич ский смысл.

Ч м мо но ох р кт ри о ть колич ст нно о усло л нность ля лин йных сист м? Пусть A к р тн я N N-м триц . Р ссмотрим чу

Ax = b :

Пусть т к

jj jj

- ñòü ê ê ÿ-íè ó ü íîðì RN

(í ïðèì ð

jj

x

jj

=max

xi

j

, =

P

j

xi

j

, =

pP

x2). Íîðì îï ð òîð

i j

i

A îïð ëÿ òñÿ ñò í ðòíî

= jjAjj = max jjAxjj :

x6=0 jjxjj

О о н чим y = Ax и м число m по пр илу

m = min jjAxjj = min

jjyjj

=

max jjA 1yjj

1

=

jj

A 1

jj

1

:

x6=0

x

jj

y6=0

jj

A 1y

jj

y6=0

y

M

A

1

jj

jj jj

В личин C(A) =

=

jj

A

jj jj

jj

н ы тся числом о усло л нности. Оч и но

m

1)C(A) 1;

2)C( A) = C(A);

max jaiij

3) ñëè A è îí ëüí ÿ, òî C(A) = mini jaiij (Для к кой нормы? или ля с х ыш при нных?).

i

Ч м м ньш число о усло л нности C(A), т м лучш о усло л нн сист м . Д йст ит льно, пусть b ри ция пр ой ч сти, x соот тст ующ и м н ни р ш ния. То спр ли о сл ующ н р нст о

			jj xxjj	C(A)	jj bbjj		:
			jj jj		jj	jj
	Äîê ò ëüñò î. Èì ì: Ax = b, A(x + x) = b + b, A x = b. Ò ê ê ê
			m jjA xxjj = jj bxjj ;
		1	jj	jj jj		jj
	òî jj xjj		jj bjj. Ан ло ично, поскольку Ax = b , то jjbjj			Mjjxjj. О ъ иняя н р нст , оконч т льно
		m

получ м

jjjjxxjjjj Mm jjjjbbjjjj :

5.2.2Ì òî Ã óññ

О ин и с мых р спростр н нных прямых м то о р ш ния сист м лин йных ур н ний Ax = b :

60