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

Â.Á. Àíäðååâ×ÈÑËÅÍÍÛÅ ÌÅÒÎÄÛ×àñòü I2Ãëàâà IÂû÷èñëèòåëüíûå ìåòîäû ëèíåéíîéàëãåáðû35Ñ âû÷èñëèòåëüíîé òî÷êè çðåíèÿ â ëèíåéíîé àëãåáðå èìåþòñÿ, åñëè ïîíèìàòü èõäîñòàòî÷íî øèðîêî, äâå îñíîâíûå çàäà÷è:1◦ ðåøåíèå ñèñòåì ëèíåéíûõ óðàâíåíèé,2◦ âû÷èñëåíèå ñîáñòâåííûõ çíà÷åíèé è ñîáñòâåííûõ âåêòîðîâ ìàòðèöû.Îñíîâíîå âíèìàíèå â ëåêöèÿõ áóäåò óäåëåíî ðåøåíèþ ïåðâîé çàäà÷è, äà è òîïðè âåñüìà îãðàíè÷èòåëüíûõ ïðåäïîëîæåíèÿõ. Âòîðàÿ çàäà÷à áîëåå òðóäíàÿ ååìû êîñíåìñÿ ìåíåå ïîäðîáíî. ñèëó òåîðåìû Êðîíåêåðà - Êàïåëëè ñèñòåìà ëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèéAx = bðàçðåøèìà òîãäà è òîëüêî òîãäà, êîãäà ðàíã ìàòðèöû A ðàâåí ðàíãó ðàñøèðåííîéìàòðèöû [Ab].

Ýòî çàâåäîìî òàê, åñëè ìàòðèöà A êâàäðàòíàÿ è íåâûðîæäåííàÿ, ò.å.det A 6= 0.  ýòîì ñëó÷àå ñèñòåìà íå òîëüêî ðàçðåøèìà ïðè ëþáûõ b, íî è èìååòåäèíñòâåííîå ðåøåíèå. (Ðàçðåøèìà îäíîçíà÷íî).Èìåííî ýòîò ñëó÷àé ìû è áóäåì èçó÷àòü.Ìåòîäû ðåøåíèÿ ñèñòåì ëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèé äåëÿòñÿ íà äâå ãðóïïû. Ê ïåðâîé ãðóïïå ïðèíàäëåæàò òàê íàçûâàåìûå ïðÿìûå ìåòîäû àëãîðèòìû,ïîçâîëÿþùèå ïîëó÷èòü ðåøåíèå çà êîíå÷íîå ÷èñëî àðèôìåòè÷åñêèõ äåéñòâèé. Ñþäàîòíîñÿòñÿ èçâåñòíîå ïðàâèëî Êðàìåðà íàõîæäåíèÿ ðåøåíèÿ ïðè ïîìîùè îïðåäåëèòåëåé, ìåòîä èñêëþ÷åíèÿ Ãàóññà, ìåòîä ïðîãîíêè ìåòîä ðåøåíèÿ ñèñòåì ñ òðåõäèàãîíàëüíûìè ìàòðèöàìè.

Ñóùåñòâóþò è äðóãèå ìåòîäû, èç êîòîðûõ îòìåòèì ìåòîäÕîëåöêîãî (ìåòîä êâàäðàòíûõ êîðíåé), ïðèìåíÿåìûé ê ñèñòåìàì ñ ñèììåòðè÷íûìèïîëîæèòåëüíî îïðåäåëåííûìè ìàòðèöàìè, ìåòîä âðàùåíèé è ìåòîä îòðàæåíèé.Âòîðóþ ãðóïïó ñîñòàâëÿþò ïðèáëèæåííûå ìåòîäû, â ÷àñòíîñòè, èòåðàöèîííûå. èòåðàöèîííûõ ìåòîäàõ ðåøåíèå ñèñòåìû ïîëó÷àåòñÿ êàê ïðåäåë ïðè ñòðåìëåíèè÷èñëà èòåðàöèé n ê áåñêîíå÷íîñòè. Ïðè êîíå÷íûõ n, êàê ïðàâèëî, ïîëó÷àþòñÿ ëèøüïðèáëèæåííûå ðåøåíèÿ.Ïðÿìûå è èòåðàöèîííûå ìåòîäû èìåþò ñâîþ îáëàñòü ïðèìåíåíèÿ: åñëè ðàçìåðíîñòü ñèñòåìû íå ñëèøêîì âåëèêà, òî ÷àñòî ïðåäïî÷òèòåëüíåå èñïîëüçîâàòü ïðÿìûåìåòîäû. Èòåðàöèîííûå ìåòîäû âûãîäíû äëÿ ñèñòåì áîëüøîãî ïîðÿäêà.

Îñîáåííî âñëó÷àå ìàòðèö ñïåöèàëüíîãî âèäà. íàñòîÿùåì êóðñå îñíîâíîå âíèìàíèå áóäåò óäåëåíî ïðÿìûì ìåòîäàì, à èòåðàöèîííûõ ìåòîäîâ êîñíåìñÿ ëèøü êðàòêî. Áîëåå ïîäðîáíî èòåðàöèîííûå ìåòîäû áóäóòèçëîæåíû âî âòîðîé ÷àñòè êóðñà "×èñëåííûå ìåòîäû", êîòîðàÿ ÷èòàåòñÿ íà ÷åòâåðòîìêóðñå.6Ÿ 1Ìåòîä èñêëþ÷åíèÿ Ãàóññà èòðåóãîëüíîå (LU ) ðàçëîæåíèåìàòðèöû1.1 Ìåòîä èñêëþ÷åíèÿ ÃàóññàÑèñòåìà Ax = b â ðàçâåðíóòîé ôîðìå èìååò âèänXaij xj = bi ,(1.1)i = 1, .

. . , n.j=1Êàê èçâåñòíî, ìåòîä Ãàóññà èëè ìåòîä ïîñëåäîâàòåëüíîãî èñêëþ÷åíèÿ íåèçâåñòíûõñîñòîèò â òîì, ÷òî íåèçâåñòíûå xj , j = 1, . . . , n − 1 ïîñëåäîâàòåëüíî èñêëþ÷àþòñÿ èçñîîòâåòñòâóþùèõ óðàâíåíèé ñèñòåìû (1.1) , â ðåçóëüòàòå ÷åãî îíà ïðåîáðàçóåòñÿ êýêâèâàëåíòíîé ñèñòåìå ñ òðåóãîëüíîé ìàòðèöåé(0)(0)(0)+ ...+ a1n xn(1)(1)+ ...+ a2n xna11 x1 + a12 x2 + a13 x3a22 x2 + a23 x3(0)= b1 ,(0)(1)= b2 ,(1)..............................................................(i−1)aiixi + . . .(i−1)+ ainxn(i−1)= bi,(1.2)..............................................................(n−1)ann(k)(n−1)xn = b n(k),êîýôôèöèåíòû aij êîòîðîé è êîìïîíåíòû åå ïðàâîé ÷àñòè bi âû÷èñëÿþòñÿ ïî ôîðìóëàìi, j = k + 1, .

. . , n;(k)(k−1)(k−1)aij = aij− lik akj ,(1.3)k = 1, . . . , n − 1;78Ÿ 1. ÌÅÒÎÄ ÃÀÓÑÑÀ È ÒÐÅÓÃÎËÜÍÎÅ ÐÀÇËÎÆÅÍÈÅ ÌÀÒÐÈÖÛ(k)bi(k−1)= bi(k−1)− lik bki, j = k + 1, . . . , n;k = 1, . . . , n − 1;,à(k−1)lik = aik(0)(k−1)/akk(1.4)i = k + 1, . . . , n;k = 1, . . . , n − 1;,(1.5)(0)ïðè÷åì aij = aij , bi = bi .Âû÷èñëåíèÿ ïî ôîðìóëàì (1.3)-(1.5)íàçûâàþòñÿ ïðÿìûì õîäîì ìåòîäà Ãàóññà.Ïîñëå ýòîãî íåèçâåñòíûå xk ïîñëåäîâàòåëüíî, íà÷èíàÿ ñ xn , íàõîäÿòñÿ èç (1.2) ïîôîðìóëàìnhi.X(i−1)(i−1)(i−1)xi = b i−aij xjaii ,i = n, . .

. , 1.(1.6)j=i+1Âû÷èñëåíèÿ ïî ýòèì ôîðìóëàì íàçûâàþò îáðàòíûì õîäîì ìåòîäà Ãàóññà.Çàìå÷àíèå 1.1.  ôîðìóëàõ (1.2) ïðè ïðåáðàçîâàíèÿõ ñèñòåìû (1.1) ïåðâîå óðàâíå-íèå îñòàëîñü áåç èçìåíåíèÿ. Ñ ðàâíûì óñïåõîì ìîæåò áûòü èñïîëüçîâàí è äðóãîéâàðèàíò èñêëþ÷åíèÿ, êîãäà ïåðâîå óðàâíåíèå (1.1) äåëèòñÿ íà a11 , à âìåñòî (1.2)ïîëó÷àåòñÿ ñèñòåìà ñ åäèíè÷íûìè êîýôôèöèåíòàìè ïðè xj â j -îì óðàâíåíèè.Çàìå÷àíèå 1.2. Âû÷èñëåíèÿ ïî ôîðìóëàì (1.5), (1.6) , à, ñëåäîâàòåëüíî, è ïî ôîðìóëàì (1.3), (1.4) âîçìîæíû ëèøü òîãäà, êîãäà âñå ÷èñëà(i−1)aii6= 0,(1.7)i = 1, . . .

, n.Íåîáõîäèìûå è äîñòàòî÷íûå óñëîâèÿ âûïîëíåíèÿ (1.7) óñòàíàâëèâàþòñÿ â äîêàçûâàåìîé ÷óòü ïîçæå òåîðåìå 1.21.2LU ðàçëîæåíèå ìàòðèöû.Ïîêàæåì, ÷òî ìåòîä Ãàóññà ýêâèâàëåíòåí ðàçëîæåíèþ ìàòðèöû A ñèñòåìû (1.1) âïðîèçâåäåíèå íèæíåé L è âåðõíåé U òðåóãîëüíûõ ìàòðèö ñ ïîñëåäóþùèì ðåøåíèåìâñïîìîãàòåëüíûõ ñèñòåì ñ ýòèìè ìàòðèöàìè.  ñàìîì äåëå, èç (1.4) íàõîäèì, ÷òî(k−1)bi(k−2)= bi(k−2)− li k−1 bk−1 .Ïîäñòàâëÿÿ ýòî ñîîòíîøåíèå â (1.4), ïîëó÷èì(k)bi(k−2)= bi(k−2)(k−1)− li k−1 bk−1 − lik bk(k−2).(k−3), à çàòåì äëÿ biÒî÷íî òàê æå ïîäñòàâëÿÿ ñþäà âûðàæåíèÿ äëÿ bièìåòü(0)(1)(k−1)(0)(k).bi = bi − li1 b1 − li2 b2 − · · · − lik bkè ò.ä., áóäåì1.2.

LU ÐÀÇËÎÆÅÍÈÅ ÌÀÒÐÈÖÛ.9(0)(j)Ïîëàãàÿ çäåñü k = i − 1 è âûðàæàÿ bibi =i−1X= bi ÷åðåç bi , ïîëó÷èì(j−1)lij bj(i−1)+ bi.(1.8)j=1Îáîçíà÷èì ñòîëáåö ïðàâîé ÷àñòè ñèñòåìû (1.2) ÷åðåç y = [y1 . . . yn ]T , ïîëàãàÿ(i−1)yi = bi(1.9). ýòèõ îáîçíà÷åíèÿõ (1.8) ïåðåïèøåòñÿ òàêbi =i−1Xlij yj + yi ,i = 1, . . . , n.(1.10)j=1Îáîçíà÷èì ÷åðåç L íèæíþþ òðåóãîëüíóþ ìàòðèöó ñ êîýôôèöèåíòàìè lij , âû÷èñëÿåìûì ïî ôîðìóëàì (1.5), è åäèíè÷íîé ãëàâíîé äèàãîíàëüþ1 0 0 ...

0 l21 1 0 . . . 0L=(1.11) l31 l32 1 . . . 0 .. . . . . . . . . . . . . . . . . . .ln1 ln2 ln3 . . . 1Òîãäà (1.10) ìîæíî çàïèñàòü â ìàòðè÷íîì âèäå(1.12)b = Ly.Åñëè âåðõíþþ òðåóãîëüíóþ ìàòðèöó ñèñòåìû (1.2) îáîçíà÷èòü ÷åðåç U è ïåðåïèñàòü(1.2) â ìàòðè÷íîì âèäå, òî áóäåì èìåòü(1.13)U x = y.Äåéñòâóÿ òåïåðü íà ëåâóþ è ïðàâóþ ÷àñòü (1.13) íåâûðîæäåííîé ìàòðèöåé L è ïðèíèìàÿ âî âíèìàíèå (1.12), ïîëó÷èìLU x = Ly = b⇒A = LU.(1.14)Èòàê, ìû ïîêàçàëè, ÷òî ðåàëèçàöèÿ âû÷èñëåíèé ïî ôîðìóëàì (1.3) è (1.5) ïðÿìîãîõîäà ìåòîäà Ãàóññà ýêâèâàëåíòíà ðàçëîæåíèþ ìàòðèöû A ñèñòåìû (1.1) â ïðîèçâåäåíèå íèæíåé òðåóãîëüíîé ìàòðèöû ñ åäèíè÷íîé ãëàâíîé äèàãîíàëüþ L è âåðõíåéòðåóãîëüíîé ìàòðèöû U . Ïðè ýòîì ýëåìåíòû ìàòðèöû L âû÷èñëÿþòñÿ ïî ôîðìóëàì(1.5), à ýëåìåíòû ìàòðèöû U ñóòü(k−1)ukj = akj(1.15)10Ÿ 1.

ÌÅÒÎÄ ÃÀÓÑÑÀ È ÒÐÅÓÃÎËÜÍÎÅ ÐÀÇËÎÆÅÍÈÅ ÌÀÒÐÈÖÛè âû÷èñëÿþòñÿ ïî ôîðìóëàì (1.3).Ïîñëå ðàçëîæåíèÿ ìàòðèöû A â ïðîèçâåäåíèå äâóõ òðåóãîëüíûõ äëÿ îòûñêàíèÿðåøåíèÿ ñèñòåìû (1.1) íóæíî ðåøèòü äâå ñèñòåìû ñ òðåóãîëüíûìè ìàòðèöàìè ñèñòåìû (1.12) è (1.13). Ðåøåíèå ñèñòåìû (1.12) çàìåíÿåò ïðåîáðàçîâàíèå âåêòîðàïðàâîé ÷àñòè ñèñòåìû (1.1) ïî ôîðìóëàì (1.4) ïðÿìîãî õîäà ìåòîäà Ãàóññà. Ðåøåíèåæå x ñèñòåìû (1.13) ñ ó÷åòîì îáîçíà÷åíèé (1.9) è (1.15) îïðåäåëÿåòñÿ ôîðìóëàìè (1.6)îáðàòíîãî õîäà ìåòîäà Ãàóññà.Çàìå÷àíèå 1.3.

Ñîîòíîøåíèÿ (1.3) ñîäåðæàò ôîðìóëû äëÿ ukj (1.15) è ïðîìåæóòî÷íûå çíà÷åíèÿ, êîòîðûå òîæå íóæíî çàïîìèíàòü è õðàíèòü. Ìû ñåé÷àñ ïðåîáðàçóåìýòè ôîðìóëû ê òàêîìó âèäó, ïðè êîòîðîì õðàíåíèå ïðîìåæóòî÷íûõ çíà÷åíèé íåòðåáóåòñÿ.Ïóñòü ìàòðèöà L èìååò âèä (1.11), ò.å. åå ýëåìåíòûlik = 0 ïðè k > i,à(1.16)u11 u12 u13 . . .

u1nu22 u23 . . . u2n u33 . . . u3n U =,. . . . . . . . . . . . . . . . . . . . . . . unnò.å.ukj = 0 ïðè k > j.(1.17)Ïîñêîëüêó LU = A, òî ïî ïðàâèëó óìíîæåíèÿ ìàòðèö íàõîäèì, ÷òîaij =nX(1.18)lik ukj .k=1Ïðåîáðàçóåì ýòó ôîðìóëó äâóìÿ ñïîñîáàìè. Â ñèëó (1.11), (1.16)nXlik ukj =k=1i−1Xlik ukj +lii=1 uij+k=1=i−1XnX0kl ik ukj =k=i+1lik ukj + uij ,k=1à â ñèëó (1.17)nXlik ukj =k=1j−1Xlik ukj + lij ujj +k=1k=j+1j−1=Xk=1nXlik ukj + lij ujj .0klik ukj =1.2. LU ÐÀÇËÎÆÅÍÈÅ ÌÀÒÐÈÖÛ.11Îòñþäà è èç (1.18) èìååìi−1hiXuij = aij −lik ukji = 1, .

. . , n;j = i, . . . , n;k=1j−1iX1 hlij =aij −lik ukjj = 1, . . . , n;ujjk=1(1.19)i = j + 1, . . . , n.(j−1)Î÷åâèäíî, ÷òî ðåàëèçàöèÿ ôîðìóë (1.19) âîçìîæíà òîëüêî òîãäà, êîãäà âñå ujj = ajjâ ñèëó (1.15) îòëè÷íû îò íóëÿ (ñð. ñ (1.7)).Çàìå÷àíèå 1.4.

Ôîðìóëû (1.19) óñòðîåíû òàê, ÷òî íåëüçÿ ñíà÷àëà âû÷èñëèòü âñåuij , à çàòåì âñå lij èëè íàîáîðîò. Ìîæíî ïðåäëîæèòü ñëåäóþùèé ïîðÿäîê âû÷èñëåíèéïî ôîðìóëàì (1.19):u1j = a1j ,j = 1, 2, . . . , n;li1 = ai1 /u11 ,i = 2, 3, . . . , n;u2j = a2j − l21 u1j ,j = 2, 3, . . . , n;li2 = (ai2 − li1 u12 )/u22 ,i = 3, 4, . .

. , n;è ò.ä., ò.å. ÷åðåäîâàòü âû÷èñëåíèå ñòðîê ìàòðèöû U è ñòîëáöîâ ìàòðèöû L.Ïîñëå ïîñòðîåíèÿ ìàòðèö L è U ðåøåíèå ñèñòåì (1.12) è (1.13) ñ òðåóãîëüíûìèìàòðèöàìè íàõîäÿòñÿ ïî ôîðìóëàìyi = bi −i−1Xlik yk ,i = 1, 2, . . . , n,(1.20)k=1(âû÷èñëåíèÿ âåäóòñÿ ñâåðõó âíèç).xk =niX1 hyk −ukj xj ,ukkj=k+1k = n, n − 1, . . . , 1(1.21)(âû÷èñëåíèÿ âåäóòñÿ ñíèçó ââåðõ).Îäíîé èç âàæíåéøèõ õàðàêòåðèñòèê ëþáîãî ÷èñëåííîãî ìåòîäà ÿâëÿåòñÿ åãî òðóäîåìêîñòü. Ïîä òðóäîåìêîñòüþ ìåòîäà, ïðåäíàçíà÷åííîãî äëÿ ðåøåíèÿ ñèñòåìû (1.1),îáû÷íî ïîíèìàþò ÷èñëî àðèôìåòè÷åñêèõ äåéñòâèé, íåîáõîäèìûõ äëÿ íàõîæäåíèÿèñêîìîãî ðåøåíèÿ.

×àñòî â òðóäîåìêîñòü ìåòîäà âêëþ÷àþò ëèøü äåéñòâèÿ óìíîæåíèÿè äåëåíèÿ, êàê íàèáîëåå òðóäîåìêèå îïåðàöèè ñ òî÷êè çðåíèÿ ðàáîòû êîìïüþòåðà. Òàêáóäåì ïîñòóïàòü è ìû.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 íåâûðîæäåííàÿ âåðõíÿÿ òðåóãîëüíàÿìàòðèöà.