Буслов, Яковлев - Численные методы. 2. Решение уравнений (947496), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Ïóñòü x1 êîðåíü ôóíêöèè f (x),ðàññìîòðèì ôóíêöèþ f1 (x) =f (x)x−x1 .Òî÷êà x1 áóäåò ÿâëÿòüñÿ êîðíåì ôóíêöèè f1 (x) íà åäèíèöó ìåíüøåéêðàòíîñòè, ÷åì f (x), ïðè ýòîì âñå îñòàëüíûå êîðíè ó ôóíêöèé f (x) è f1 (x) ñîâïàäàþò ñ ó÷åòîìêðàòíîñòè. Ïðèìåíÿÿ òîò èëè èíîé ìåòîä íàõîæäåíèÿ êîðíåé ê ôóíêöèè f1 (x), ìû íàéäåì íîâûé êîðåíüx2 (êîòîðûé ìîæåò â ñëó÷àå êðàòíûõ êîðíåé è ñîâïàäàòü ñ x1 ).

Äàëåå ìîæíî ðàññìîòðåòü ôóíêöèþf2 (x) =f1 (x)x−x2=f (x)(x−x1 )(x−x2 )è èñêàòü êîðíè ó íå¼. Ïîâòîðÿÿ óêàçàííóþ ïðîöåäóðó, ìîæíî íàéòè âñå êîðíèf (x) ñ ó÷åòîì êðàòíîñòè.Çàìåòèì, ÷òî êîãäà ìû ïðîèçâîäèì äåëåíèå íà òîò èëè èíîé êîðåíü x∗ , òî â äåéñòâèòåëüíîñòè ìû äåëèìëèøü íà íàéäåííîå ïðèáëèæåíèå x0∗ , è, òåì ñàìûì, íåñêîëüêî ñäâèãàåì êîðíè âñïîìîãàòåëüíîé ôóíêöèèîòíîñèòåëüíî èñòèííûõ êîðíåé ôóíêöèè f (x) . Ýòî ìîæåò ïðèâåñòè ê çíà÷èòåëüíûì ïîãðåøíîñòÿì, åñëèïðîöåäóðà îòäåëåíèÿ ïðèìåíÿëàñü óæå äîñòàòî÷íîå ÷èñëî ðàç.

×òîáû èçáåæàòü ýòîãî, ñ ïîìîùüþ âñïîìîãàòåëüíûõ ôóíêöèé âû÷èñëÿþòñÿ ëèøü ïåðâûå èòåðàöèè, à îêîí÷àòåëüíûå ïðîâîäÿòñÿ ïî èñõîäíîé ôóíêöèè6f (x) , èñïîëüçóÿ â êà÷åñòâå ñòàðòîâîãî ïðèáëèæåíèÿ, ïîñëåäíþþ èòåðàöèþ, ïîëó÷åííóþ ïî âñïîìîãàòåëüíîé ôóíêöèè.1.1.4 Ìíîãîìåðíûé ñëó÷àéÌåòîä ïðîñòûõ èòåðàöèéÌåòîä ïðîñòûõ èòåðàöèé (ïîñëåäîâàòåëüíûõ ïðèáëèæåíèé) ëåãêî îáîáùàåòñÿ íà ñëó÷àé ñèñòåìû íåëèíåéíûõ óðàâíåíèéfk (x1 , x2 , . . . , xN ) = 0 , k = 1, 2, . . .

, N ,èëè â âåêòîðíîé ôîðìåf (x) = 0 .Ýòó ñèñòåìó óäîáíî, êàê è â îäíîìåðíîì ñëó÷àå, çàïèñàòü â âèäå çàäà÷è íà íåïîäâèæíóþ òî÷êóF(x) = x .Çàìå÷àíèå. Íàõîæäåíèå òàêîé ôîðìû çàïèñè ìîæåò îêàçàòüñÿ ñàìî ïî ñåáå ñåðüåçíîé çàäà÷åé. Íåîáõîäèìîäîáèòüñÿ è òîãî, ÷òîáû îòîáðàæåíèå F ÿâëÿëîñü ñæàòèåì (äëÿ ñõîäèìîñòè èòåðàöèé) è, ïðè ýòîì, áûëîýêâèâàëåíòíî èñõîäíîé ïîñòàíîâêå.Âûáðàâ ñòàðòîâîå ïðèáëèæåíèå, îðãàíèçóåì èòåðàöèèx(j+1) = F(x(j) ) .Åñëè èòåðàöèè ñõîäÿòñÿ, òî îíè ñõîäÿòñÿ ê îäíîìó èç ðåøåíèé ñèñòåìû óðàâíåíèé. Ïîðÿäîê ñõîäèìîñòèïðîñòûõ èòåðàöèé ëèíåéíûé. Äåéñòâèòåëüíî, ïóñòü x∗ ðåøåíèå, ê êîòîðîìó ñõîäÿòñÿ èòåðàöèè, òîãäà äëÿêàæäîé k -îé åãî êîìïîíåíòû(j+1)xk−x∗k(j)= Fk (x∗) − Fk (x ) =¸N ·X∂Fk (zj )l=1jãäå z íåêîòîðûé âåêòîð â íàïðàâëåíèè x(j)∂xl(j)(xl− x∗l ) ,∗− x , ëåæàùèé ìåæäó ýòèìè òî÷êàìè.

Îòîáðàæåíèå F áóäåòÿâëÿòüñÿ ñæàòèåì, åñëè íîðìà ìàòðèöû ïðîèçâîäíûõ (ñîãëàñîâàííàÿ ñ íîðìîé âåêòîðà â äàííîì ïðîñòðàíon∂Fk (ξ k )ìåíüøå åäèíèöû. Ïîñêîëüêó â êîíå÷íîìåðíîì ïðîñòðàíñòâå âñå íîðìû ýêâèâàëåíòíû (àñòâå)∂xlçíà÷èò è ïîñëåäîâàòåëüíîñòü ñõîäÿùàÿñÿ ïî îäíîé íîðìå, áóäåò ñõîäèòüñÿ è ïî ëþáîé äðóãîé), òî äîñòàkòî÷íî ýòî óñëîâèå ïðîâåðèòü äëÿ ëþáîé èç íîðì ìàòðèöû ñ ýëåìåíòàìè Mkl = max | ∂F∂xl | , ìàæîðèðóþùåénokk (ξ )ñîîòâåòñòâóþùèå íîðìû ∂F∂x.lÓëó÷øèòü ñõîäèìîñòü ìåòîäà ïîñëåäîâàòåëüíûõ ïðèáëèæåíèé ìîæíî (õîòÿ îíà ïî ïðåæíåìó îñòàíåòñÿ(j+1)ëèíåéíîé), åñëè óæå íàéäåííûå êîìïîíåíòû xkïðèáëèæåíèÿ x(j+1)èñïîëüçîâàòü äëÿ íàõîæäåíèÿ êîìïîíåíò ýòîãî æåñ íîìåðàìè áîëüøèìè k , òî åñòü îðãàíèçîâàòü èòåðàöèè ñëåäóþùèì îáðàçîì(j+1)(j+1)xk+1 = Fk (x1(j+1), x2(j+1), .

. . , xk(j)(j)(j), xk+1 , xk+2 , . . . , xN ) .Ìåòîä ÍüþòîíàÌåòîä Íüþòîíà, ÿâëÿÿñü ÷àñòíûì ñëó÷àåì ìåòîäà ïðîñòûõ èòåðàöèé ñ âåêòîð-ôóíêöèåé F, ðàâíîé·¸−1∂f (x)F(x) = x −f (x) ,∂x7åñòåñòâåííî îáîáùàåòñÿ íà ìíîãîìåðíûé ñëó÷àé. Èòåðàöèè ïî ìåòîäó Íüþòîíà èìåþò âèä·x(j+1) = x(j) −∂f (x)∂x¸−1f (x(j) ) .x=x(j)Ïðîâåðêà óñëîâèé ñõîäèìîñòè (òî åñòü òîãî, ÷òî íîðìà ìàòðèöû ïðîèçâîäíûõ ∂F/∂x ìåíüøå åäèíèöû)ïî÷òè íèêîãäà íå ïðîèçâîäèòñÿ, ïîñêîëüêó òðåáóåò áîëüøîãî îáúåìà âû÷èñëåíèé. Ñàì æå ìåòîä Íüþòîíàîáû÷íî èñïîëüçóþò â íåñêîëüêî äðóãîé çàïèñè.

Èìåííî:·¸∂f (x)∆x(j) = −f (x(j) ) , ∆x(j) = x(j+1) − x(j) .∂x x=x(j)Îïðåäåëÿÿ èç ýòîé ëèíåéíîé ñèñòåìû (ñêàæåì ìåòîäîì Ãàóññà) âåêòîð ∆x(j)áëèæåíèå x(j+1)è, ñîîòâåòñòâåííî, ïðè-, çàíîâî ðàññ÷èòûâàþò ìàòðèöó ïðîèçâîäíûõ è ïðîäîëæàþò èòåðàöèè. Åñëè íà÷àëüíîåïðèáëèæåíèå âûáðàíî óäà÷íî, òî îáû÷íî äîñòàòî÷íî âñåãî íåñêîëüêèõ èòåðàöèé, ïîñêîëüêó ñõîäèìîñòüêâàäðàòè÷íàÿ.Ìåòîäû ñïóñêàÂâåä¼ì ôóíêöèþ Φ =NPj=1|fj (x)|2 . Îíà îãðàíè÷åíà ñíèçó íóëåì è äîñòèãàåò ñâîåãî ãëîáàëüíîãî ìèíèìóìà(íóëÿ) òîëüêî â òåõ òî÷êàõ, ãäå f (x) = 0. Òàêèì îáðàçîì, çàäà÷à íà ïîèñê êîðíåé âåêòîð-ôóíêöèè ñâîäèòñÿê çàäà÷å íà ïîèñê ìèíèìóìà ñêàëÿðíîé ôóíêöèè ìíîãèõ ïåðåìåííûõ, ìåòîäû ðåøåíèÿ êîòîðîé ðàññìàòðèâàþòñÿ â ñîîòâåòñòâóþùåé ãëàâå. Çäåñü ëèøü îòìåòèì, ÷òî ýòè ìåòîäû íàçûâàþòñÿ ìåòîäàìè ñïóñêà èÿâëÿþòñÿ ñõîäÿùèìèñÿ äëÿ ãëàäêèõ ôóíêöèé, îäíàêî òî÷íîñòü èõ íåâåëèêà, ïîýòîìó èõ åñòåñòâåííî èñïîëüçîâàòü äëÿ íàõîæäåíèÿ íà÷àëüíîãî ïðèáëèæåíèÿ ñ ïîñëåäóþùèì èñïîëüçîâàíèåì ìåòîäà Íüþòîíà.Âàæíî òàêæå èìåòü â âèäó, ÷òî ìåòîäû ñïóñêà ìîãóò ñõîäèòñÿ íå ê ãëîáàëüíîìó ìèíèìóìó, à ê îäíîìóèç ëîêàëüíûõ (â çàâèñèìîñòè îò âûáîðà ñòàðòîâîé òî÷êè), íå îòâå÷àþùèõ, ðàçóìååòñÿ, êîðíÿì èñõîäíîéçàäà÷è.1.2 Ðåøåíèå ëèíåéíûõ ñèñòåì1.2.1 Îáóñëîâëåííîñòü ëèíåéíûõ ñèñòåì, ïîãðåøíîñòüÏðè ðåøåíèè àáñòðàêòíîé çàäà÷è Ax = b, ãäå A îïåðàòîð ïðîèçâîëüíîé ïðèðîäû, âàæíûì ìîìåíòîì ÿâëÿåòñÿ êîððåêòíîñòü åå ïîñòàíîâêè.

Çàäà÷à ñ÷èòàåòñÿ êîððåêòíîé, åñëè ðåøåíèå ñóùåñòâóåò è åäèíñòâåííîè, êðîìå òîãî, ðåøåíèå íåïðåðûâíî çàâèñèò îò âõîäíûõ äàííûõ (òî åñòü, ïðè ∆b → 0 , ∆x òàêæå ñòðåìèòñÿê íóëþ).Îäíàêî è íåïðåðûâíàÿ çàâèñèìîñòü îò âõîäíûõ äàííûõ ìîæåò èìåòü ñâîè íþàíñû. ×åì ìåíüøåå (áîëüøåå) èçìåíåíèå ðåøåíèÿ âûçûâàåò âàðèàöèÿ âõîäíûõ äàííûõ, òåì áîëåå õîðîøî (ïëîõî) îáóñëîâëåííîéñ÷èòàåòñÿ çàäà÷à. Ïîíÿòèå îáóñëîâëåííîñòè ÿâëÿåòñÿ òåì áîëåå ñóùåñòâåííûì äëÿ ÷èñëåííûõ ìåòîäîâ,ïîñêîëüêó íà ïðàêòèêå âõîäíûå äàííûå èçâåñòíû, êàê ïðàâèëî, ñ íåêîòîðîé ïîãðåøíîñòüþ.

Êðîìå òîãî,ñóùåñòâóþò îøèáêè îêðóãëåíèÿ, âîçíèêàþùèå ïðè âû÷èñëåíèÿõ. Òàêèì îáðàçîì, ôîðìàëüíî êîððåêòíàÿçàäà÷à, ÿâëÿÿñü ïëîõî îáóñëîâëåííîé, ìîæåò îêàçàòüñÿ ðàçðåøèìîé ñòîëü íåòî÷íî, ÷òî â ýòîì áóäåò îòñóòñòâîâàòü ïðàêòè÷åñêèé ñìûñë.8×åì ìîæíî îõàðàêòåðèçîâàòü êîëè÷åñòâåííî îáóñëîâëåííîñòü äëÿ ëèíåéíûõ ñèñòåì? Ïóñòü A êâàäðàòíàÿ N × N -ìàòðèöà. Ðàññìîòðèì çàäà÷óAx = b .Ïóñòü òàêæå || ∗ || êàêàÿ-íèáóäü íîðìà â RN (íàïðèìåð ||x||=max |xi | , =iP|xi | , =pPx2i ).

Íîðìàîïåðàòîðà A îïðåäåëÿåòñÿ ñòàíäàðòíîM = ||A|| = maxx6=0||Ax||.||x||Îáîçíà÷èì y = Ax è ââåäåì ÷èñëî m ïî ïðàâèëóm = minx6=0Âåëè÷èíà C(A) =Mm³||Ax||||y||||A−1 y|| ´−1= min= max= ||A−1 ||−1 .−1y6=0 ||Ay6=0||x||y||||y||= ||A|| · ||A−1 || íàçûâàåòñÿ ÷èñëîì îáóñëîâëåííîñòè. Î÷åâèäíî1) C(A) ≥ 1;2) C(αA) = C(A);3) åñëè A äèàãîíàëüíàÿ, òî C(A) =max |aii |imin |aii |(Äëÿ êàêîé íîðìû, èëè äëÿ âñåõ âûøåïðèâåäåííûõ?).i×åì ìåíüøå ÷èñëî îáóñëîâëåííîñòè C(A), òåì ëó÷øå îáóñëîâëåíà ñèñòåìà. Äåéñòâèòåëüíî, ïóñòü ∆b âàðèàöèÿ ïðàâîé ÷àñòè, à ∆x ñîîòâåòñòâóþùåå èçìåíåíèå ðåøåíèÿ. Òîãäà ñïðàâåäëèâî ñëåäóþùåå íåðàâåíñòâî||∆x||||∆b||≤ C(A).||x||||b||Äîêàçàòåëüñòâî.

Èìååì: Ax = b, A(x + ∆x) = b + ∆b, A∆x = ∆b. Òàê êàêm≤òî ||∆x|| ≤1m ||∆b||.||A∆x||||∆b||=,||∆x||||∆x||Àíàëîãè÷íî, ïîñêîëüêó Ax = b , òî ||b|| ≤ M ||x||. Îáúåäèíÿÿ äâà íåðàâåíñòâà, îêîí÷à-òåëüíî ïîëó÷àåì||∆x||M ||∆b||≤.||x||m ||b||1.2.2 Ìåòîä ÃàóññàÎäíèì èç ñàìûõ ðàñïðîñòðàíåííûõ ïðÿìûõ ìåòîäîâ ðåøåíèÿ ñèñòåì ëèíåéíûõ óðàâíåíèé Ax = b : a11 a12 · · · a1Nx1b1   a21 a22 · · · a2N   x2   b2 =  ······ ··· ···  ···   ···  aN 1 aN 2 · · · aN NxNbNÿâëÿåòñÿ ìåòîä Ãàóññà.

Âíà÷àëå èñõîäíàÿ ñèñòåìà ïðèâîäèòñÿ ê âåðõíåòðåóãîëüíîìó âèäó. Ýòî äîñòèãàåòñÿñëåäóþùåé ïîñëåäîâàòåëüíîñòüþ ïðåîáðàçîâàíèé (ïðÿìîé õîä ìåòîäà Ãàóññà). Áóäåì ñ÷èòàòü äëÿ óäîáñòâà,(1)÷òî ýëåìåíòû aij èñõîäíîé ìàòðèöû è êîìïîíåíòû âåêòîðà bi åñòü, ñîîòâåòñòâåííî, ýëåìåíòû aij ïåðâîãîøàãà ïðåîáðàçîâàííîé ìàòðèöû A1 è ïðåîáðàçîâàííîãî âåêòîðà b1 : A = A1 , b = b1 . Äàëåå, íà âòîðîì øàãåïðèáàâèì ê âòîðîé ñòðîêå ïåðâóþ, óìíîæåííóþ íà − aa21= c21 . Àíàëîãè÷íî ïîñòóïèì ñî âñåìè îñòàâøèìèñÿ11ñòðîêàìè, ò.å.

ïðèáàâèì ê êàæäîé i-îé ñòðîêå i = 2, 3, . . . , N , ïåðâóþ, óìíîæåííóþ íà êîýôôèöèåíòi1− aa11.Ïðè ýòîì ñîîòâåòñòâåííî èçìåíèòñÿ è âåêòîð b1 . Òàêèì îáðàçîì,9i1=2 øàã) Èìååì ñèñòåìó óðàâíåíèé(1)a 11 0 ···0(2)(1)(1)(2)ãäå aij = aij + ci1 a1j , bi(1)= biA2 x = b2 :(1)···a22(2)·········(2)···a12aN 2(1)+ ci1 b1(1)a1Nx1(1)b1   (2)(2)  a2N   x2   b2= ···  ···   ··· (2)(2)aN NxNbN ,, i≥2.3 øàã) Ïðèáàâèì ê íîâîé òðåòüåé ñòðîêå íîâóþ âòîðóþ, óìíîæåííóþ íà c32 = −(2)a32(2)a22.

Òî æå ñàìîåñäåëàåì ñ îñòàëüíûìè ñòðîêàìè 4 , 5 , . . . , N , ò.å. ïðèáàâèì ê êàæäîé i-îé ñòðîêå âòîðóþ, óìíîæåííóþ íàci2 = −(2)ai2(2)a22, i > 2. Ïðè ýòîì ïîëó÷èì ñèñòåìó A3 x = b3 :(1)a11 0 0 ···0(k+1)(k + 1)-ûé øàã) Çäåñü aij(1)a13(1)···a22(2)a23(2)···0a33(3)············0aN 3(3)···a12(k)(k)(1)a1N(2)  a2N  (3)  a3N  ··· (3)aN N(k+1)= aij + cik akj , bi(k)= bix1  x2    x3  =   ···   xN(k)(1)b1(3) b3  ,··· (3)bN(2)b2+ cik bk , ãäå cik = −(k)aik(k)akk, i, j > k .Ïîñòóïàÿ òàê è äàëåå, íà (N − 1)-îì øàãå ïîëó÷àåì âåðõíåòðåóãîëüíóþ ñèñòåìó: (1)(1)(1)(1)(1)a11 a12 a13 · · · · · · a1Nx1b1   (2) (2)(2)(2)   0a22 a23 · · · · · · a2N   x2   b2    (3) (3)  (3) 00a33 · · · · · · a3N   x3   b3 =  (4)  .(4)  (4) 000a44 · · · a4Nxb 4   4   ··· ··· ··· ··· ··· ···  ···   ···  (N )(N )000···0 aN NxNbNÏðè ýòîì, ìû òàêæå ïîëó÷èëè ìàòðèöó C ïåðåâîäíûõ êîýôôèöèåíòîâ, èìåþùóþ âèä:0000···0000···0  c2100···0  c31 c32 .0···0  c41 c42 c43.. ··· ··· ··· ···.···cN 1cN 2cN 3···cN N −10Ðåøåíèå ïîëó÷åííîé òðåóãîëüíîé ñèñòåìû U x = f (U = AN , f = bN ), êàê ëåãêî âèäåòü, èìååò âèä(îáðàòíûé õîä ìåòîäà Ãàóññà)xN =NXfN N1Uki xi ) , k = N , N − 1 , .

Характеристики

Список файлов книги