В.Б. Андреев - Численные методы, страница 2

Òîãäà, åñëè 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, . .