В.Б. Андреев - Численные методы (2 в 1). (2007) (1160465), страница 2
Текст из файла (страница 2)
Òàêáóäåì ïîñòóïàòü è ìû.12 1. ÌÅÒÎÄ ÃÀÓÑÑÀ È ÒÐÅÓÃÎËÜÍÎÅ ÐÀÇËÎÆÅÍÈÅ ÌÀÒÐÈÖÛËåãêî âèäåòü, ÷òî äëÿ âû÷èñëåíèé ïî ôîðìóëàì (1.19) (äëÿ ïîëó÷åíèÿ òðåóãîëüíîãî ðàçëîæåíèÿ) òðåáóåòñÿn Xnn XnnXXXQ=(i − 1) +j=[(i − 1)(n − i + 1) + i(n − i)] =i=1 j=inXj=1 i=j+1i=1[(n + 1)i − i2 ] − n(n + 1) = n(n + 1)2 −=2i=12=n(n + 1)(2n + 1)− n(n + 1) = (1.22)3n(n − 1)n3n3=+ O(n) ≈333äåéñòâèé óìíîæåíèÿ è äåëåíèÿ.Äëÿ âû÷èñëåíèé ïî ôîðìóëàì (1.20) è (1.21) èìååì ñîîòâåòñòâåííînXn(n − 1)q=(i − 1) =2i=1◦ènXn(n + 1)q=,(n − k + 1) =2k=1ò.å. îáùåå ÷èñëî äåéñòâèé äëÿ ðåøåíèÿ ñèñòåì (1.12) è (1.13) ïî ôîðìóëàì (1.20),(1.21) åñòü◦q = q + q = n2 .(1.23)Çàìå÷àíèå 1.5. Èç ôîðìóë (1.22) è (1.23) ñëåäóåò, ÷òî ïðè áîëüøèõ n îñíîâíîéîáúåì ðàáîòû, êîòîðóþ íóæíî âûïîëíèòü äëÿ ðåøåíèÿ ñèñòåìû (1.1) îïèñàííûììåòîäîì, ïàäàåò íà ïðåîáðàçîâàíèå êîýôôèöèåíòîâ ìàòðèöû ñèñòåìû, ò.å.
íà ïîñòðîåíèå òðåóãîëüíîãî ðàçëîæåíèÿ, â òî âðåìÿ êàê ïðåîáðàçîâàíèå âåêòîðà ïðàâîé ÷àñòè(ðåøåíèå ñèñòåìû (1.12)) è íà îòûñêàíèå ñàìîãî ðåøåíèÿ òðóäîçàòðàòû ñðàâíèåòåëüíîíåâåëèêè.  ñâÿçè ñ ýòèì ïðè áîëüøèõ n ðåøåíèå íåñêîëüêèõ ñèñòåì ñ ðàçëè÷íûìèïðàâûìè ÷àñòÿìè è îäíîé è òîé æå ìàòðèöåé îêàçûâàåòñÿ ïî òðóäîåìêîñòè ïðàêòè÷åñêè òàêèì æå êàê è ðåøåíèå îäíîé ñèñòåìû.Âûÿñíèì òåïåðü óñëîâèÿ, ïðè êîòîðûõ âû÷èñëåíèÿ ïî ôîðìóëàì (1.19)-(1.21) âîçìîæíû, ò.å. âñå ujj îòëè÷íû îò íóëÿ.Òåîðåìà 1.1. Ïóñòü A íåâûðîæäåííàÿ ìàòðèöà, L íèæíÿÿ òðåóãîëüíàÿ ìàò-ðèöà ñ åäèíè÷íîé ãëàâíîé äèàãîíàëüþ, à U íåâûðîæäåííàÿ âåðõíÿÿ òðåóãîëüíàÿìàòðèöà.
Òîãäà, åñëè A = LU , òî ýòî ïðåäñòàâëåíèå åäèíñòâåííî.Äëÿ äîêàçàòåëüñòâà òåîðåìû 1.1 íàì ïîòðåáóåòñÿËåììà 1.1. Ïðîèçâåäåíèå íèæíèõ (âåðõíèõ)òðåóãîëüíûõ ìàòðèö åñòü íèæíÿÿ(âåðõíÿÿ) òðåóãîëüíàÿ ìàòðèöà. Îáðàòíàÿ ê íåâûðîæäåííîé íèæíåé (âåðõíåé) òðåóãîëüíîé ìàòðèöå åñòü íèæíÿÿ (âåðõíÿÿ) òðåóãîëüíàÿ ìàòðèöà.Óïðàæíåíèå 1.1. Äîêàçàòü ëåììó 1.1.1.2. LU ÐÀÇËÎÆÅÍÈÅ ÌÀÒÐÈÖÛ.13Äîêàçàòåëüñòâî òåîðåìû 1.1.
Ïóñòü A = L1 U1 = L2 U2 . ÒîãäàL2 = L1 U1 U2−1è−1L−11 L2 = U1 U2 .Ñëåâà ñòîèò ïðîèçâåäåíèå íèæíèõ òðåóãîëüíûõ ìàòðèö, à ñïðàâà âåðõíèõ. Ïîýòîìóïðîèçâåäåíèå åñòü äèàãîíàëüíàÿ ìàòðèöà D, ò.å. L−11 L2 = D . Îòñþäà íàõîäèì, ÷òîL2 = L1 D. Ïîñêîëüêó ãëàâíûå äèàãîíàëè L1 è L2 åäèíè÷íûå, òî ãëàâíàÿ äèàãîíàëüL1 D ñîâïàäàåò ñ ãëàâíîé äèàãîíàëüþ D, ñëåäîâàòåëüíî, D = I . Îòñþäà L1 = L2 èU1 = U2 . Òåîðåìà äîêàçàíà.Òåîðåìà 1.2. Ïóñòü A êâàäðàòíàÿ íåâûðîæäåííàÿ ìàòðèöà, L íèæíÿÿ òðå-óãîëüíàÿ ìàòðèöà ñ åäèíè÷íîé ãëàâíîé äèàãîíàëüþ, à U íåâûðîæäåííàÿ âåðõíÿÿòðåóãîëüíàÿ ìàòðèöà. Ðàçëîæåíèå A = LU ñóùåñòâóåò òîãäà è òîëüêî òîãäà,êîãäà âñå óãëîâûå ìèíîðû ìàòðèöû A îòëè÷íû îò íóëÿ.Íàïîìíèì, ÷òî óãëîâûìè ìèíîðàìè ìàòðèöû A íàçûâàþòñÿ âåëè÷èíû·¸a11 a12∆1 = a11 , ∆2 = det, .
. . , ∆n = det[A].a21 a22Äîêàçàòåëüñòâî. 1◦ . (Íåîáõîäèìîñòü)Ïóñòü ðàçëîæåíèå A = LU ñóùåñòâóåò. Òîãäà ïî òåîðåìå 1.1 îíî åäèíñòâåííî.Ïðåäñòàâèì ìàòðèöû A, L è U â áëî÷íîì âèäå·¸·¸·¸Am A12Lm 0Um U12A=, L=, U=,A21 A22L21 L220 U22ãäå Am , Lm , Um è A22 , L22 , U22 êâàäðàòíûå ìàòðèöû ðàçìåðíîñòåé m × m è (n −m) × (n − m) ñîîòâåòñòâåííî, à m < n ïðîèçâîëüíîå ÷èñëî. Ðàçëîæåíèå A = LU âáëî÷íîì ïðåäñòàâëåíèè èìååò âèä·¸ ·¸·¸ ·¸Am A12Lm 0Um U12Lm UmLm U12==(1.24)A21 A22L21 L220 U22L21 Um L21 U12 + L22 U22Îòñþäà ñëåäóåò, ÷òîAm = Lm Um .(1.25)Ïîñêîëüêó ìàòðèöà U òðåóãîëüíàÿ è íåâûðîæäåííàÿ, òî âñå åå äèàãîíàëüíûå ýëåìåíòû îòëè÷íû îò íóëÿ. Ïîýòîìó íåâûðîæäåíà è òðåóãîëüíàÿ ìàòðèöà Um .
Òåì ñàìûì∆m = det[Am ] = det[Lm ] det[Um ] = u11 . . . umm 6= 0ïðè m = 1, . . . , n.2◦ . (Äîñòàòî÷íîñòü) Ïóñòü òåïåðü ∆1 ∆2 . . . ∆n 6= 0. Äëÿ äîêàçàòåëüñòâà ñóùåñòâîâàíèÿ òðåóãîëüíîãî ðàçëîæåíèÿ âîñïîëüçóåìñÿ ìåòîäîì ïîëíîé ìàòåìàòè÷åñêîéèíäóêöèè ïî ïîðÿäêó ñèñòåìû n. Ïðè n = 1 ìàòðèöà A = a11 = ∆1 6= 0, ìàòðèöà L = 114 1. ÌÅÒÎÄ ÃÀÓÑÑÀ È ÒÐÅÓÃÎËÜÍÎÅ ÐÀÇËÎÆÅÍÈÅ ÌÀÒÐÈÖÛè ïîýòîìó U = u11 = a11 = det U 6= 0. Ñóùåñòâîâàíèå èñêîìîãî ðàçëîæåíèÿ ïðè n = 1äîêàçàíî.Ïóñòü Ak ìàòðèöà ïîðÿäêà k è ðàçëîæåíèå Ak = Lk Uk ñóùåñòâóåò ñ det Uk 6= 0ïðè k = 1, . . .
, m − 1. Äîêàæåì, ÷òî ñóùåñòâóåò è Am = Lm Um , ïðè÷åì det Um 6= 0.Ïóñòü a·m = [a1m . . . am−1 m ]T ñòîëáåö, am· = [am1 . . . am m−1 ] ñòðîêà è ðàçëîæåíèåAm áóäåì èñêàòü â âèä常·¸ ··Lm−1 0 Um−1 u·mAm−1 a·m==Am =lm· 10ummam· amm·¸Lm−1 Um−1Lm−1 u·m=.lm· Um−1 lm· u·m + ummÎòñþäà ñëåäóåò, ÷òî íåèçâåñòíûé ñòîëáåö u·m , íåèçâåñòíàÿ ñòðîêà lm· è umm îïðåäåëÿþòñÿ ñëåäóþùèìè ñîîòíîøåíèÿìè:Lm−1 u·m = a·mTTlm· Um−1 = am· ⇒ Um−1lm·= aTm· ,umm = amm − lm· u·m .(1.26)Ïîñêîëüêó Lm−1 è Um−1 íåâûðîæäåííûå, èç ïåðâîãî è âòîðîãî ñîîòíîøåíèé (1.26)ìîæíî íàéòè u·m è lm· , ñîîòâåòñòâåííî, ïîñëå ÷åãî òðåòüå ñîîòíîøåíèå äàåò umm .Ñóùåñòâîâàíèå ðàçëîæåíèÿ (1.24) äëÿ m äîêàçàíî. Îñòàëîñü äîêàçàòü, ÷òî det Um 6= 0.Íî ñ ó÷åòîì (1.25)0 6= ∆m = det Am = det Um ,÷òî è òðåáîâàëîñü äîêàçàòü. Òåîðåìà ïîëíîñòüþ äîêàçàíà. 2Ëåíòî÷íûå ìåòîäû2.1Ìåòîä ïðîãîíêèÐàññìîòðèì ñèñòåìó ëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèé(2.1)Ax = b,ìàòðèöà êîòîðîé ÿâëÿåòñÿ òðåõäèàãîíàëüíîé.
Çàïèøåì ýòó ñèñòåìó â ðàçâåðíóòîìâèäå. Ïóñòüb1 x1 + c1 x2a2 x1 + b2 x2= d1 ,+ c 2 x3= d2 ,...............................................................ai xi−1 + bi xi+ ci xi+1= di ,(2.2)...............................................................an xn−1 + bn xn = dn .Àëãîðèòì ìåòîäà ïðîãîíêè ìåòîäà ðåøåíèÿ ñèñòåìû (2.2) ñîñòîèò â ñëåäóþùåì(ñì. êóðñ "Ââåäåíèå â ÷èñëåííûå ìåòîäû", íî, ìîæåò áûòü, ñ äðóãèìè îáîçíà÷åíèÿìè!)à) Íàõîæäåíèå ïðîãîíî÷íûõ êîýôôèöèåíòîâ (ïðÿìàÿ ïðîãîíêà) ïî ôîðìóëàìαi = −ci /γi , i = 1, 2, .
. . , n − 1,γi = bi + ai αi−1 , i = 2, . . . , n, γ1 = b1 ,βi = (di − ai βi−1 )/γi , i = 2, . . . , n, β1 = d1 /b1 .(2.3)á) Íàõîæäåíèå ñàìîãî ðåøåíèÿ (îáðàòíàÿ ïðîãîíêà)xi = αi xi+1 + βi ,i = n − 1, . . . , 1,15x n = βn .(2.4)16 2. ËÅÍÒÎ×ÍÛÅ ÌÅÒÎÄÛÈç (2.3),(2.4) ñëåäóåò, ÷òî îáùåå ÷èñëî óìíîæåíèé è äåëåíèé ïðè âû÷èñëåíèè êîýôôèöèåíòîâ αi è γiQ = 2(n − 1, )(2.5)à ïðè âû÷èñëåíèè êîýôôèöèåíòîâ βi è ðåøåíèÿ xi(2.6)q = 3(n − 1).Ñðàâíåíèå (2.5),(2.6) ñ (1.22), (1.23) ñâèäåòåëüñòâóþò î òîì, ÷òî ïðîãîíêà ñóùåñòâåííîìåíåå òðóäîåìêà ïî ñðàâíåíèþ ñ îáùèì ìåòîäîì Ãàóññà. Ñâÿçàíî ýòî ñ òåì, ÷òî ìûÿâíûì îáðàçîì âîñïîëüçîâàëèñü òåì, ÷òî çíà÷èòåëüíàÿ ÷àñòü ýëåìåíòîâ ìàòðèöû Aðàâíà íóëþ.2.2 Ëåíòî÷íûå ìàòðèöûÎïðåäåëåíèå 2.1.
Ìàòðèöà A íàçûâàåòñÿ ëåíòî÷íîé ñ ïîëóøèðèíîé ëåíòû p, åñëèåå ýëåìåíòû aij = 0 ïðè |i − j| > p, íî ñóùåñòâóåò ïî êðàéíåé ìåðå îäèí ýëåìåíòaij 6= 0 ïðè |i − j| = pÏðèìåð 2.1. Äëÿ äèàãîíàëüíîé ìàòðèöû aij = 0 ïðè |i − j| > 0 è, ñëåäîâàòåëüíî,åå ïîëóøèðèíà ðàâíà íóëþ. Åå ëåíòà ñîñòîèò èç îäíîé äèàãîíàëè è øèðèíà ðàâíà 1.Óñëîâíî äèàãîíàëüíóþ ìàòðèöó ìîæíî èçîáðàçèòü êàê íà ðèñ. 1.∗∗∗∗∗ ∗Ðèñ.
1.Ïðèìåð 2.2. Ïîëíàÿ ìàòðèöà èìååò 2n−1 äèàãîíàëåé. Ýòî è åñòü øèðèíà åå ëåíòû,à ïîëóøèðèíà áóäåò p = n − 1.∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗Ðèñ. 2.∗∗∗∗∗∗∗∗∗∗∗∗2.3. ËÅÍÒÎ×ÍÛÉ ÂÀÐÈÀÍÒ ÒÐÅÓÃÎËÜÍÎÃÎ ÐÀÇËÎÆÅÍÈß17Ïðèìåð 2.3. Íà ðèñ. 3 èçîáðàæåíà ìàòðèöà ñ ïîëóøèðèíîé p = 1.∗ ∗∗ ∗ ∗ ∗ ∗ ∗∗ ∗ ∗∗ ∗ ∗∗ ∗Ðèñ. 3.Ìàòðèöû òàêîé ñòðóêòóðû íàçûâàþòñÿ òðåõäèàãîíàëüíûìè. Øèðèíà ëåíòû 3.Ïðèìåð 2.4.
Ìàòðèöà, èçîáðàæåííàÿ íà ðèñ.4, èìååò ïîëóøèðèíó p = 1 è øèðèíóëåíòû 2. Ìàòðèöû òàêîé ñòðóêòóðû íàçûâàþòñÿ òðàïåöèåâèäíûìè. Èçîáðàæåííàÿìàòðèöà òàêæå íàçûâàåòñÿ ïðàâîé ëåíòî÷íîé.∗ ∗ ∗ ∗∗∗∗∗∗ ∗∗Ðèñ. 4.Ïðèìåð 2.5.
Ó ìàòðèöû íà ðèñ. 5∗0∗0∗0∗∗0∗0∗∗0∗0∗∗0∗0∗0∗Ðèñ. 5.ïîëóøèðèíà p = 2, øèðèíà 5 è âñåãî òðè íåíóëåâûõ äèàãîíàëè.Îïðåäåëåíèå 2.2. Ðèñóíîê, íà êîòîðîì (çâåçäî÷êàìè) îòìå÷åíû ïîçèöèè, ãäå òîëü-êî è ìîãóò ðàñïîëàãàòüñÿ íåíóëåâûå ýëåìåíòû ìàòðèöû A, íàçûâàåòñÿ åå ïîðòðåòîì.2.3 Ëåíòî÷íûé âàðèàíò òðåóãîëüíîãî ðàçëîæåíèÿÌîäèôèöèðóåì àëãîðèòì èñêëþ÷åíèÿ Ãàóññà íà ñëó÷àé ëåíòî÷íûõ ìàòðèö, ò.å. çàðàíåå îòáðîñèì òå âû÷èñëåíèÿ, êîòîðûå çàâåäîìî ïðèâîäÿò ê íóëåâûì ýëåìåíòàì. Ýòî18 2. ËÅÍÒÎ×ÍÛÅ ÌÅÒÎÄÛïîçâîëèò íàì ñýêîíîìèòü â òðóäîçàòðàòàõ íà ðåøåíèå ñèñòåìû. Îáðàòèìñÿ ñðàçó êâàðèàíòó, îñíîâàííîìó íà òðåóãîëüíîì ðàçëîæåíèè ìàòðèöû A.Íàì ïîòðåáóåòñÿËåììà 2.1.
Åñëè ïîëóøèðèíà ìàòðèöû A ðàâíà p, òî â òðåóãîëüíîì ðàçëîæåíèèA = LU ïîëóøèðèíà L (U ) íå áîëüøå p.Äîêàçàòåëüñòâî. ÏóñòüÄîêàæåì, ÷òîaij = 0 ïðè |i − j| > p.(2.7)lij = 0 ïðè i − j > p.(2.8)Äëÿ äîêàçàòåëüñòâà ïðèìåíèì ìåòîä ïîëíîé ìàòåìàòè÷åñêîé èíäóêöèè ïî íîìåðàìñòîëáöîâ ìàòðèöû L. Ïðè j = 1 èç (1.19) íàõîäèì, ÷òîli1 = ai1 /a11 ,i = 2, .
. . , n.Îòñþäà ñ ó÷åòîì (2.7) ïðèõîäèì ê (2.8) ñ j = 1, ò.å. li1 = 0 ïðè i − 1 > p. Ïóñòü òåïåðüóòâåðæäåíèå (2.8) âåðíî äëÿ ñòîëáöîâ ìàòðèöû L ñ íîìåðàìè k = 1, 2, . . . , j − 1, ò.å.lik = 0 ïðè i − k > p,k = 1, 2, . . . , j − 1.(2.9)Äîêàæåì ñïðàâåäëèâîñòü (2.8) äëÿ j -îãî ñòîëáöà. Ïóñòüi − j > p.(2.10)0j−1j−1X¤1 £k1 Xlij =a ij −lik ukj = −lik ukj .ujjujjk=1k=1(2.11)Òîãäà â ñèëó (1.19) è (2.7)Îöåíèì ðàçíîñòü èíäåêñîâ i − k ó ïåðâûõ ñîìíîæèòåëåé ïîä çíàêîì ñóììû â (2.11).Ñ ó÷åòîì (2.10) è (2.11) áóäåì èìåòüi − k > p + j − k > p + 1.Íî òîãäà â ñèëó (2.9) ïåðâûå ñîìíîæèòåëè â ñóììå (2.11) îáðàùàþòñÿ â íóëü èñîîòíîøåíèå (2.8) óñòàíîâëåíî. Ëåììà äîêàçàíà.Ïðåîáðàçóåì ôîðìóëû (1.19)-(1.21) íà ñëó÷àé ëåíòî÷íîé ìàòðèöû A. Ñíà÷àëà âûÿñíèì, äëÿ êàêèõ çíà÷åíèé èíäåêñîâ i è j íóæíî ïðîâîäèòü âû÷èñëåíèÿ ïî ôîðìóëàì(1.19).
Òàê êàê â ñèëó ëåììû 2.1uij = 0 ïðè j − i > p,(2.12)2.3. ËÅÍÒÎ×ÍÛÉ ÂÀÐÈÀÍÒ ÒÐÅÓÃÎËÜÍÎÃÎ ÐÀÇËÎÆÅÍÈß19òî íåíóëåâûå ýëåìåíòû uij ìîãóò áûòü ëèøü ïðè j−i 6 p, ò.å. ïðè j 6 p+i. Àíàëîãè÷íîlij = 0 ïðè i − j > p(2.13)è, ñëåäîâàòåëüíî, íåíóëåâûå ýëåìåíòû lij ìîãóò áûòü òîëüêî ïðè i − j 6 p, ò.å. ïðèi 6 p + j . Îòñþäài = 1, . . . , n,uij 6= 0j = i, . . . , min[n, p + i],j = 1, . . . , n,i = j + 1, .
. . , min[n, p + j].lij 6= 0Òåïåðü ïðåîáðàçóåì ñóììû â (1.19).  ñèëó (2.12) íåíóëåâûå ñëàãàåìûå â ñóììàõ(1.19) ìîãóò áûòü òîëüêî ïðè j − k 6 p, ò.å. ïðèk > j − p.à â ñèëó (2.13) òîëüêî ïðè i − k 6 p, ò.å. ïðèk > i − p.Îáúåäèíÿÿ ýòè íåðàâåíñòâà è ïðèíèìàÿ âî âíèìàíèå, ÷òî k íàòóðàëüíîå, áóäåìèìåòük > max[1, i − p, j − p].Ïîñêîëüêó â ôîðìóëàõ äëÿ uij èíäåêñû i, j ïîä÷èíåíû îãðàíè÷åíèþ j > i, òî â ýòèõôîðìóëàõk > max[1, j − p]. ôîðìóëàõ æå äëÿ lij íàîáîðîò i > j è ïîýòîìó â íèõk > max[1, i − p].Ñ ó÷åòîì ñêàçàííîãî, äëÿ ëåíòî÷íîé ìàòðèöû A ñ ïîëóøèðèíîé p ôîðìóëû (1.19)ïðèíèìàþò âèäi−1X£uij = aij −lik ukj¤i = 1, . .
. , n,j = i, . . . , min[n, p + i],k=max[1,j−p]1 £lij =aij −ujjj−1Xlik ukj¤k=max[1,i−p]j = 1, . . . , n,i = j + 1, . . . , min[n, p + j].(2.14)Ïðåîáðàçóåì ôîðìóëû (1.20) è (1.21). Â ôîðìóëàõ (1.20) â ñèëó (2.13) i − k 6 p, àâ ôîðìóëàõ (1.21) â ñèëó (2.12) j − k 6 p. Ïîýòîìóyi = bi −i−1Xlik yk ,i = 1, . . . , n,k=max[1,i−p]min[n,k+p]iX1 hyk −ukj xj ,xk =ukkj=k+1(2.15)k = n, . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
