Буслов, Яковлев - Численные методы. 2. Решение уравнений (947496), страница 3
Текст из файла (страница 3)
. . , 1 ., xk =(fk −UN NUkki=k+1Çàìåòèì, ÷òî ïðè ïðÿìîì õîäå ìåòîäà Ãàóññà ìîæåò âîçíèêíóòü ñèòóàöèÿ, êîãäà ïðîèñõîäèò äåëåíèå íàíóëü, äà è âîîáùå, æåëàòåëüíî íå äåëèòü íà ìàëîå ÷èñëî, ÷òîáû íå íàêàïëèâàëàñü îøèáêà. Ïîýòîìó ìåòîäÃàóññà îáû÷íî ïðîâîäÿò ñ ÷àñòè÷íûì âûáîðîì ãëàâíîãî ýëåìåíòà, òî åñòü ïîñëå êàæäîãî øàãà (ïóñòü ýòî10áûë k -é øàã) ïåðåñòàâëÿþò ñòðîêè ñ íîìåðàìè k , k + 1 , . .
. , N òàêèì îáðàçîì, ÷òîáû íà ìåñòå kk îêàçàëñÿ(k)ýëåìåíò amk , íàèáîëüøèé èç âñåõ â k -îì ñòîëáöå ïðè m > k (ïðè ýòîì, åñòåñòâåííî, ïåðåñòàâëÿþòñÿ èêîìïîíåíòû âåêòîðà b).Ìîæíî äëÿ ìàêñèìàëüíîé òî÷íîñòè ïåðåñòàâëÿòü òàêæå è ñòîëáöû ïðåîáðàçóåìîé ìàòðèöû, ÷òîáû íàìåñòå kk îêàçàëñÿ ìàêñèìàëüíûé ýëåìåíò èç âñåõ ñ èíäåêñàìè áîëüøå, ëèáî ðàâíûìè k . Ýòà ïðîöåäóðàíàçûâàåòñÿ ìåòîäîì Ãàóññà ñ âûáîðîì ãëàâíîãî ýëåìåíòà. Îíà íåñêîëüêî ïîâûøàåò òî÷íîñòü ïî ñðàâíåíèþ ñ ÷àñòè÷íûì âûáîðîì ãëàâíîãî ýëåìåíòà, íî âåñüìà íåóäîáíà, â òîì ÷èñëå è äëÿ ïðîãðàììèðîâàíèÿ,ïîñêîëüêó ïðè ïåðåñòàíîâêå ñòðîê êîìïîíåíòû èñêîìîãî âåêòîðà x ïåðåñòàâëÿòü íå íàäî, òîãäà êàê ïðèïåðåñòàíîâêå ñòîëáöîâ íàäî ïåðåñòàâëÿòü è ñîîòâåòñòâóþùèå êîìïîíåíòû âåêòîðà x.Îïèøåì îáðàòíûé õîä ìåòîäà Ãàóññà â íåñêîëüêî èíîé ôîðìå (òðåóãîëüíîå ðàçëîæåíèå).
Ââåäåì ìàòðèöû Mk ïî ïðàâèëóMk = 10···0···010············...······00···1···00···ck+1,k···00···ck+2,k···············...00···cN,k···00 ··· 0 .0 0 ··· 1Íà êàæäîì øàãå ìåòîäà Ãàóññà ïîëó÷àåòñÿ íåêîòîðàÿ ïðîìåæóòî÷íàÿ ìàòðèöà Ak+1 =Mk Mk−1 . . . M1 A , èâåêòîð fk+1 = Mk Mk−1 .
. . M1 b . Íåòðóäíî âèäåòü, ÷òîN −1N −1U=←Y−Mi A , f =i=1←Y−Mi b ;U x = f , det U =i=1NYUii = det A .i=1Âîïðîñ. Ïî÷åìó det U = det A?Åñëè ïðîèçâîäèòü òàêæå âûáîð ãëàâíûõ ýëåìåíòîâ, òî íåîáõîäèìî èñïîëüçîâàòü îïåðàòîð P ïåðåñòàíîâêè èíäåêñîâ l è m, ìàòðè÷íûå ýëåìåíòû êîòîðîãî ðàâíû: pij = 0 , i, j 6= l, m ; pim = pmi = 0 , i 6= l ;pli = pil = 0 , i 6= m ; pml = plm = 1 . Ïðè ïðèìåíåíèè îïåðàòîðà ïåðåñòàíîâêè èíäåêñîâ ê ìàòðèöå ñëåâà,ìåíÿþòñÿ ìåñòàìè ñòðîêè ìàòðèöû è êîìïîíåíòû ñâîáîäíîãî âåêòîðà (P Ax = P b) , åñëè æå åãî ïðèìåíèòüñïðàâà ê ìàòðèöå, òî ìåíÿþòñÿ ìåñòàìè åå ñòîëáöû è êîìïîíåíòû ðåøåíèÿ (A |{z}P P x = b).=I1.2.3 L-R ðàçëîæåíèåÄëÿ ðåøåíèÿ çàäà÷è Ax = b íåñêîëüêî ìîäèôèöèðóåì åå. Èìåííî, ââåäåì N × (N + 1) ìàòðèöóC=b1Ab2...bN11è âåêòîð X = (x1 , x2 , . .
. , xN , −1)T ðàçìåðíîñòè (N + 1), òîãäà èñõîäíàÿ çàäà÷à ýêâèâàëåíòíà ñëåäóþùåéCX = 0 .Ïðåäñòàâèì C â âèäå C = LR, ãäå L íèæíåòðåóãîëüíàÿ N × N ìàòðèöàL=l110···0l21...l22...···...0...lN 1lN 2···lN N ,à R N × (N + 1)-ìàòðèöà:10R = 0...0r12r13···r1N1r23···r2N0...1...···...r3N...00···1r1,N +1r2,N +1 r3,N +1 ....rN,N +1Êàê íàõîäèòü ìàòðèöû L è R?1-é øàã) à) Óìíîæèì êàæäóþ ñòðîêó ìàòðèöû L íà ïåðâûé ñòîëáåö ìàòðèöû R, îòêóäà li1 = ci1 . Òàêèìîáðàçîì, ìû îïðåäåëèëè ïåðâûé ñòîëáåö ìàòðèöû L.á) Óìíîæèì ïåðâóþ ñòðîêó L íà êàæäûé ñòîëáåö R, îòêóäà r1i = c1i /l11 , òî åñòü îïðåäåëåíàïåðâàÿ ñòðîêà R.2-é øàã) a) Óìíîæèì êàæäóþ ñòðîêó L (íà÷èíàÿ ñî âòîðîé) íà âòîðîé ñòîëáåö R è îïðåäåëèì âòîðîéñòîëáåö L: li2 = ci2 − li1 r12 .á) Óìíîæàÿ âòîðóþ ñòðîêó L íà êàæäûé ñòîëáåö R, îïðåäåëÿåì âòîðóþ ñòðîêó R: r2i =(c2i − l21 r1i )/l22 .m-é øàã) Ïóñòü èçâåñòíû ïåðâûå m − 1 ñòîëáåö L è m − 1 ñòðîêà R, òîãäà ïðè i ≥ mlim = cim −m−1Xcmi −m−1Plmk rkik=1lik rkm , rmi =lmmk=1.Òåïåðü çàìåòèì, ÷òî âîâñå íåò íåîáõîäèìîñòè ðåøàòü çàäà÷ó CX = 0, à äîñòàòî÷íî ðåøèòü ñèñòåìó RX = 0.Äåéñòâèòåëüíî, ðàíã ìàòðèöû R ðàâåí N , òàêèì îáðàçîì èñõîäíàÿ ìàòðèöà A è L âûðîæäåíû èëèíåâûðîæäåíû îäíîâðåìåííî.
Êîìïîíåíòû xi íàõîäèì ïîñëåäîâàòåëüíî, íà÷èíàÿ ñ N -îé:xN = rN,N +1 , xi = ri,N +1 −NXrik xk .k=i+1Âû÷èñëåíèÿ ïî èçëîæåííîìó ìåòîäó òðåáóþò â äâà ðàçà ìåíüøèé îáúåì ïàìÿòè, ÷åì ïî ìåòîäó Ãàóññà.1.2.4 Ìåòîä ïðîãîíêèÏóñòü A òðåõäèàãîíàëüíàÿ ìàòðèöà, êîòîðóþ ìû ïðåäñòàâèì â âèäå:12c1 −a2A= 0 ···0−b1000···00c2−b200···0−a3c3−b30···0··················0000···−aN0 0 ··· cNÇíàê − ïåðåä bi , ci ïîñòàâëåí äëÿ óäîáñòâà.
Äëÿ ðåøåíèÿ çàäà÷è At = s â ýòîì ñëó÷àå ïðèìåíÿåòñÿìåòîä ïðîãîíêè.Ïîëîæèì a1 = bN = 0 , òîãäà òðåõäèàãîíàëüíàÿ ñèñòåìà ìîæåò áûòü çàïèñàíà â âèäå−tk−1 ak + tk ck − tk+1 bk = sk , k = 1 , 2 , . . . , N .Ðàññìîòðèì ýòó ñèñòåìó ïîäðîáíåå. Âûðàçèì èç ïåðâîãî óðàâíåíèÿ t1 ÷åðåç t2 :t1 c1 − t2 b1 = s1 ⇒ t1 =b1s1t2 +.c1c1Òåïåðü èç âòîðîãî óðàâíåíèÿ âûðàçèì t2 ÷åðåç t3 : −t1 a2 + t2 c2 − t3 b2 = s2 , èë赶s2 + ac12 s1s1b1b2 t3+ t2 a2 + t2 c2 − t3 b2 = s2 ⇒ t2 =−+.c1c1c2 − cb1 a2c2 − cb1 a211Àíàëîãè÷íî,tk = αk tk+1 + βk ,ãäåαk =bk,ck − αk−1 akβk =sk + βk−1 ak.ck − αk−1 akÓáåäèìñÿ â ñïðàâåäëèâîñòè ýòîãî ïðåäñòàâëåíèÿ ïî èíäóêöèè. Äåéñòâèòåëüíî, α1 =b1c1, β1 =s1c1, òàêèìîáðàçîì áàçà èíäóêöèè âåðíà. Òåïåðü îñóùåñòâèì ñîáñòâåííî èíäóêöèîííûé ïåðåõîä.
Ïóñòü tk = αk tk+1 +βk , òîãäà−ak+1 tk + ck+1 tk+1 − bk+1 tk+2 = sk+1 ,−ak+1 (αk tk+1 + βk) + ck+1 tk+1 − bk+1 tk+2 = sk+1 ,îòêóäàbk+1 tk+2sk+1 + βk ak+1+= αk+1 tk+2 + βk+1 ,ck+1 − αk ak+1ck+1 − αk ak+1tk+1 =òî åñòü èíäóêöèîííûé ïåðåõîä òàêæå èìååò ìåñòî.Ðàññìîòðèì òåïåðü êàêèì îáðàçîì ïðèìåíÿåòñÿ ìåòîä ïðîãîíêè. Íà ïåðâîì ýòàïå (ïðÿìîé õîä ïðîãîíêè)ìû îïðåäåëÿåì êîýôôèöèåíòû αk , βk ÷åðåç èçâåñòíûå íàì ýëåìåíòû ìàòðèöû A (bk , ck , ak ) , çàäàííûåçíà÷åíèÿ sk è ïðåäûäóùèå αk−1 , βk−1 :α1 =b1c1 ,αk =bkck −αk−1 ak ,β1 =s1c1 , íà÷àëî ïðÿìîãî õîäà,βk =sk +βk−1 akck −αk−1 ak , ïðÿìîé õîä.Ïîñëå òîãî êàê îïðåäåëåíû êîýôôèöèåíòû αk è βk íà÷èíàåòñÿ îáðàòíûé õîä ïðîãîíêè ñîáñòâåííîîïðåäåëåíèå êîìïîíåíò tk .
ÈìååìtN = αN tN +1 + βN ,ïðè ýòîì αN = 0 , ò.ê. bN = 0 , à αN =bNcN −αN −1 aN. Òàêèì îáðàçîì,13tN = β N(íà÷àëî îáðàòíîãî õîäà) ,tk = αk tk+1 + βk(îáðàòíûé õîä) .Óòâåðæäåíèå (Äîñòàòî÷íîå óñëîâèå ðàçðåøèìîñòè ïðîãîíêè): Ïóñòü |ck | > |bk | + |ak | , k = 1 , . . . , N ,òîãäà det A 6= 0.Äîêàçàòåëüñòâî. Íåîáõîäèìî óáåäèòüñÿ, ÷òî çíàìåíàòåëü â ôîðìóëàõ ïðÿìîãî õîäà íå îáðàùàåòñÿ âíóëü. Äëÿ ýòîãî äîñòàòî÷íî óáåäèòüñÿ â òîì, ÷òî |αk | < 1. Âåäü åñëè ýòî òàê, òî|ck − αk−1 ak | ≥ |ck | − |αk−1 ||ak | > |ck | − |ak | > |bk | ≥ 0è íå ïðîèñõîäèò äåëåíèÿ íà íóëü. Èìååì :|α1 | = |b1|<1 ,c1|αk | =|bk ||bk |<=1.|ck − αk−1 ak ||bk |1.2.5 Ìåòîä èòåðàöèé äëÿ ðåøåíèÿ ëèíåéíûõ ñèñòåìÑèñòåìà ëèíåéíûõ óðàâíåíèé Ax = b :NXaij xj = bi , i = 1, 2, .
. . , N ,(1)j=1ìîæåò áûòü ðåøåíà íå òîëüêî ïðÿìûìè ìåòîäàìè, íî òàêæå è èòåðàöèîííûìè. Ðàçóìååòñÿ, ìû ïðåäïîëàãàåì, ÷òî ñèñòåìà èìååò åäèíñòâåííîå ðåøåíèå, ò.å., ÷òî det A 6= 0.Ïðåäñòàâèì ìàòðèöó A â âèäå A = B+D , ãäå D = diag{a11 , . . . , aN N } . Ïðåäïîëîæèì, ÷òî det D 6= 0 ,÷òî ðàâíîñèëüíî òîìó, ÷òî aii 6= 0 , i = 1 , . .
. , N (åñëè èñõîäíî ýòî íå òàê, òî ïåðåñòàíîâêîé ñòðîê èñòîëáöîâ ýòîãî âñåãäà ìîæíî äîáèòüñÿ ïðè det A 6= 0 ). Òîãäà (1) ïåðåïèñûâàåòñÿ â âèäå Dx = b − Bx, èëèx = D−1 b − D−1 Bx .Ïðåäëîæèì ñëåäóþùóþ èòåðàöèîííóþ ïðîöåäóðóxs+1 = D−1 b − D−1 Bxs ,x0 ïðîèçâîëüíûé íà÷àëüíûé âåêòîð.  ðàçâåðíóòîé ôîðìånX−1xs+1= a−1iii bi − aiiaij xsj , i = 1, 2, . . . N .j=1,j6=iÎáîçíà÷èì D−1 b = u, D−1 B = T , òîãäà èòåðàöèîííûé ïðîöåññ ïðèíèìàåò âèäxs+1 = u − T xs .(2)Òåîðåìà1. Ïðîöåññ (2) ñõîäèòñÿ, äëÿ ëþáîãî íà÷àëüíîãî âåêòîðà, åñëè ||D−1 (A − D)|| = ||T || < 1 .Äîêàçàòåëüñòâî. Äëÿ äîêàçàòåëüñòâà äîñòàòî÷íî çàìåòèòü, ÷òî îòîáðàæåíèå x → u − T x ÿâëÿåòñÿ ñæàòèåì.Òàêèì îáðàçîì, ïîñëåäîâàòåëüíîñòü xs èìååò ïðåäåë. Ïóñòü x∗ = lim xs , òîãäà x∗ = u − T x∗ , èëè,s→∞âîçâðàùàÿñü ê èñõîäíîé ôîðìóëèðîâêå, Ax∗ = b.
Èòàê, äëÿ ñõîäèìîñòè èçëîæåííîãî ìåòîäà, íàçûâàåìîãîìåòîäîì ïðîñòûõ èòåðàöèé, íåîáõîäèìî ÷òîáû||D−1 (A − D)|| < 1 .141.2.6 Ìåòîä ÇåéäåëÿÌîäèôèöèðóåì ìåòîä ïðîñòûõ èòåðàöèé, êîîðäèíàòíóþ ôîðìó êîòîðîãî, â ÷àñòíîñòè, ìîæíî çàïèñàòü ââèäåxs+1= a−1iii [bi −Xj<i|aij xsj −{zXaij xsj ] , i = 1, 2, . . . , N .j>i}∗Çàìåòèì, ÷òî åñëè ïîñëåäîâàòåëüíî âû÷èñëÿòü êîìïîíåíòû (s + 1)-ãî ïðèáëèæåíèÿ xs+1 , íà÷èíàÿ ñ ïåðâîés+1xs+1, êîîðäèíàòû xs+1, . . .
, xs+11 , òî ê ìîìåíòó âû÷èñëåíèÿ êîíêðåòíîé i-îé êîìïîíåíòû xi1i−1 óæå îïðåäå-ëåíû è èõ ìîæíî áûëî áû èñïîëüçîâàòü äëÿ îïðåäåëåíèÿ áîëåå òî÷íîãî ïîñëåäóþùåãî ïðèáëèæåíèÿ xs+1 .Ìîäèôèöèðóåì ñîîòâåòñòâóþùèì îáðàçîì ìåòîä ïðîñòûõ èòåðàöèé, çàìåíèâ â ñóììå ∗ êîìïîíåíòû xsj íàxs+1. Òàêèì îáðàçîì, ìû ïîëó÷àåì íîâóþ èòåðàöèîííóþ ïðîöåäóðój−1xs+1= a−1iii bi − aiiXaij xs+1− a−1jiij<iXaij xsj , i = 1, 2, .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
