В.Б. Андреев - Численные методы (2 в 1). (2007) (1160465), страница 4
Текст из файла (страница 4)
ÌÅÒÎÄ ÁËÎ×ÍÎÃÎ ÈÑÊËÞ×ÅÍÈß29 ñèëó ëåììû 3.1 íåíóëåâûìè ýëåìåíòàìè lik ìàòðèöû L ìîãóò áûòü òîëüêî òå, óêîòîðûõ èíäåêñû ïîä÷èíåíû óñëîâèÿìj−p6k 6jÏîýòîìó ôîðìóëà (3.5) ïðèíèìàåò âèävuj−1Xutljj = ajj −(ljk 6= 0).2,ljkj = 1, . . . , n.(3.9)(3.10)k=max[1,j−p] ñèëó (3.9) â ôîðìóëàõ (3.6) i − p 6 k 6 i è i − p 6 j 6 i. Ïîýòîìó ôîðìóëû (3.6)ïðèíèìàþò âèäj−1Xi = j + 1, . . . , min[n, p + j],1 lij =aij −lik ljk ,(3.11)ljjj = 1, . .
. , n.k=max[1,i−p]Ëåíòî÷íûé âàðèàíò ðàçëîæåíèÿ Õîëåöêîãî ïîñòðîåí.Äëÿ îòûñêàíèÿ ðåøåíèÿ ñèñòåìû (3.1) íóæíî åùå ïðåîáðàçîâàòü ôîðìóëû (3.8).Îíè ïðèíèìàþò âèäi−1X1lik yk , i = 1, . . . , n,yi = bi −liik=max[1,i−p](3.12)min[n,i+p]X1 xi =lki xk , i = n, . . . , 1.yi −liik=i+1Ýòè ôîðìóëû ïîëíîñòüþ àíàëîãè÷íû ôîðìóëàì (??).Óïðàæíåíèå 3.3. Ïîäñ÷èòàòü ÷èñëî äåéñòâèé óìíîæåíèÿ, äåëåíèÿ è èçâëå÷åíèÿêîðíÿ, íåîáõîäèìûõ äëÿ ðåàëèçàöèè ôîðìóë (3.10)-(3.11).Îòâåò.Q=(p + 1)(p + 2)(3n − 2p).63.3 Ìåòîä áëî÷íîãî èñêëþ÷åíèÿ (ìåòîä ÷àñòè÷íîãîèñêëþ÷åíèÿ íåèçâåñòíûõ) ìåòîäå èñêëþ÷åíèÿ Ãàóññà èç ñèñòåìû (3.1) ïîñëåäîâàòåëüíî èñêëþ÷àþòñÿ íåèçâåñòíûå êîìïîíåíòû âåêòîðà xT = [x1 , x2 , .
. . , xn ].  ðÿäå ñëó÷àåâ áûâàåò ïîëåçíûìïðîöåäóðó èñêëþ÷åíèÿ íåèçâåñòíûõ ïðîèçâåñòè áëî÷íî. Ïóñòü· ¸¸· ¸·xb1A11 A12(3.13), x= 1 ,, b=A=x2b2A21 A2230 3. ÌÅÒÎÄÛ ÕÎËÅÖÊÎÃÎ È ÁËÎ×ÍÎÃÎ ÈÑÊËÞ×ÅÍÈßãäå A11 êâàäðàòíàÿ íåâûðîæäåííàÿ ìàòðèöà ðàçìåðîâ m × m, à b1 è x1 m-ìåðíûåâåêòîðû. Ñ ó÷åòîì (3.13) ñèñòåìà (3.1) ïðèíèìàåò âèä·¸· ¸ · ¸A11 A12 x1b= 1A21 A22 x2b2èëè ïîñëå áëî÷íîãî ïåðåìíîæåíèÿA11 x1 + A12 x2 = b1 ,A21 x1 + A22 x2 = b2 .(3.14)Èç ïåðâîãî óðàâíåíèÿ (3.14) íàõîäèì, ÷òîx1 = A−111 (b1 − A12 x2 ).(3.15)Ïîäñòàâëÿÿ ýòî ïðåäñòàâëåíèå x1 âî âòîðîå óðàâíåíèå (3.14), ïîëó÷èìA21 A−111 (b1 − A12 x2 ) + A22 x2 = b2èëè ïîñëå ïðåîáðàçîâàíèÿ−1(A22 − A21 A−111 A12 )x2 = b2 − A21 A11 b1 .(3.16) ðåçóëüòàòå ñèñòåìà (3.14) ïðåîáðàçîâàëàñü ê ñèñòåìåA11 x1 + A12 x2 = b1 ,−1(A22 − A21 A−111 A12 )x2 = b2 − A21 A11 b1 .(3.17)(Íåèçâåñòíûå x1 èñêëþ÷åíû èç âòîðîé ãðóïïû óðàâíåíèé).Èç (3.17) âðîäå áû ñëåäóåò, ÷òî äëÿ ðåàëèçàöèè áëî÷íîãî èñêëþ÷åíèÿ íóæíî âû÷èñëÿòü A−111 .
Íà ñàìîì äåëå ÿâíî ýòî äåëàòü âîâñå íå îáÿçàòåëüíî. Ïðèíèìàÿ âîâíèìàíèå (3.15), ââåäåì ñëåäóþùèå îáîçíà÷åíèÿ:◦A−111 b1 = x1 ,A−111 A12 = Z12 .(3.18)Òîãäà âòîðàÿ ãðóïïà óðàâíåíèé (3.17) ïðèìåò âèä◦(A22 − A21 Z12 )x2 = (b2 − A21 x1 ).(3.19)Ñîîòíîøåíèÿ (3.18) ìîæíî ïåðåïèñàòü â âèäå ñèñòåìû óðàâíåíèé◦A11 x1 = b1 ,A11 Z12 = A12 ,(3.20)à èç (3.15) è (3.18) íàõîäèì, ÷òî◦x1 = x1 − Z12 x2 .Èòàê, ÷òîáû íàéòè ðåøåíèå ñèñòåìû (3.14) íóæíî:(3.21)3.3. ÌÅÒÎÄ ÁËÎ×ÍÎÃÎ ÈÑÊËÞ×ÅÍÈß31◦1◦ ðåøèòü (m + 1) ñèñòåìó (3.20) ñ ìàòðèöåé A11 äëÿ îòûñêàíèÿ âåêòîðà x1 èñòîëáöîâ ìàòðèöû Z12 ,◦2◦ ïî íàéäåííûì x1 è Z12 ñôîðìèðîâàòü ìàòðèöó è ïðàâóþ ÷àñòü ñèñòåìû (3.19) èðåøèòü ïîëó÷åííóþ ñèñòåìó íàéòè âåêòîð x2 ,3◦ íàéòè âåêòîð x1 ïî ôîðìóëàì (3.21).Çàìå÷àíèå 3.3.
 òðàêòîâêå (3.19),(3.20) ìåòîäà áëî÷íîãî èñêëþ÷åíèÿ ôàêòè÷åñêèèñêëþ÷åííûìè îêàçûâàþòñÿ íå íåèçâåñòíûå x1 , à íåèçâåñòíûå x2 . Èç ñèñòåìû (3.14)êàê áû èñêëþ÷àåòñÿ ÷àñòü íåèçâåñòíûõ (èìåííî x2 ), çàòåì îíà ðåøàåòñÿ îòíîñèòåëüíîîñòàâøèõñÿ íåèçâåñòíûõ (3.20) (íî íå ïîëíîñòüþ íóæåí åùå øàã (3.21)) è ëèøüïîòîì íàõîäèòñÿ x2 èç (3.19). Îòñþäà âòîðîå íàçâàíèå ìåòîäà ìåòîä ÷àñòè÷íîãîèñêëþ÷åíèÿ íåèçâåñòíûõ (èñêëþ÷åíèå x2 ).Ïðèìåð 3.1. Ïóñòü ìàòðèöà A èìååò ïîðòðåò, èçîáðàæåííûé íà ðèñ. 1. ÌàòðèöàA íå ÿâëÿåòñÿ ëåíòî÷íîé, õîòÿ åå ïîäìàòðèöà A11 , ðàñïîëîæåííàÿ â ïåðâûõ (n − 1)ñòðîêàõ è (n − 1) ñòîëáöàõ ÿâëÿåòñÿ ëåíòî÷íîé ñ ïîëóøèðèíîé p = 2. Äëÿ ðåøåíèÿñèñòåìû (3.1) ñ òàêîé ìàòðèöåé íå ãîäèòñÿ ëåíòî÷íûé âàðèàíò èñêëþ÷åíèÿ Ãàóññà,à ïðèìåíåíèå îáùåãî ìåòîäà òðåáóåò O(n3 ) óìíîæåíèé è äåëåíèé. Íî åñëè ìîæíîïðèìåíèòü àëãîðèòì áëî÷íîãî èñêëþ÷åíèÿ,∗ ∗ ∗∗∗ ∗ ∗ ∗∗∗ ∗ ∗ ∗ ∗∗ ∗ ∗ ∗ ∗ ∗∗.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .∗ ∗ ∗ ∗∗ ∗ ∗ ∗ ∗ ··· ∗ ∗ ∗ ∗Ðèñ. 1òî äëÿ ðåøåíèÿ äâóõ ñèñòåì (3.20) ñ ïÿòèäèàãîíàëüíûìè ìàòðèöàìè ñ èñïîëüçîâàíèåìëåíòî÷íîãî âàðèàíòà èñêëþ÷åíèÿ ïîòðåáóåòñÿ O(n) äåéñòâèé. Ñòîëüêî æå äåéñòâèéïîòðåáóåòñÿ äëÿ âû÷èñëåíèé ïî ôîðìóëàì (3.19) è (3.21).  ðåçóëüòàòå ñèñòåìà áóäåòðåøåíà çà O(n) äåéñòâèé.Ïðèìåð 3.2. Ìàòðèöà èìååò ïîðòðåò, èçîáðàæåííûé íà ðèñ.
2.∗ ∗ ∗ ∗ ∗ ∗ ··· ∗ ∗ ∗∗ ∗ ∗∗∗ ∗ ∗ ∗∗∗∗∗∗∗∗∗∗∗∗. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .∗∗ ∗ ∗∗ ∗ ∗ ∗ ∗ ∗ ··· ∗ ∗ ∗Ðèñ. 232 3. ÌÅÒÎÄÛ ÕÎËÅÖÊÎÃÎ È ÁËÎ×ÍÎÃÎ ÈÑÊËÞ×ÅÍÈßÏåðåñòàâëÿÿ ïåðâóþ ñòðîêó íà ïîñëåäíåå ìåñòî è òî æå äåëàÿ ñ ïåðâûì ñòîëáöîì,ïîëó÷èì ìàòðèöó ñ ïîðòðåòîì, èçîáðàæåííûì íà ðèñ.
3.∗ ∗∗ ∗∗ ∗ ∗∗ ∗ ∗ ∗ ∗∗ ∗∗∗∗∗∗. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .∗ ∗ ∗ ∗∗ ∗ ∗ ∗ ∗ · · · ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ··· ∗ ∗ ∗ ∗Ðèñ. 3Òåïåðü â êà÷åñòâå A11 ñëåäóåò âûáðàòü òðåõäèàãîíàëüíóþ ìàòðèöó ðàçìåðîâ (n − 2) ×(n − 2), ñòîÿùóþ â ëåâîì âåðõíåì óãëó.3.4 Îáðàùåíèå ìàòðèöûÑðàçó æå çàìåòèì, ÷òî îáðàùåíèå ìàòðèöû â äåéñòâèòåëüíîñòè íóæíî íå òàê ÷àñòî,êàê ýòî ìîæåò êàçàòüñÿ. Ïðåäïîëîæèì,íàïðèìåð, ÷òî, ïîñëåäóþùåå (çà âû÷èñëåíèåì)èñïîëüçîâàíèå A−1 ïðåäóñìàòðèâàåò òîëüêî ôîðìèðîâàíèå åå ïðîèçâåäåíèé ñ âåêòîðàìè: u = A−1 r, v = A−1 s è ò.ä.
 òàêîì ñëó÷àå ìîæíî áûëî áû âîâñå íå âû÷èñëÿòü A−1â ÿâíîì âèäå. Âìåñòî ýòîãî äîñòàòî÷íî ïðîâåñòè äëÿ A ïðÿìîé õîä ìåòîäà Ãàóññà,à çàòåì íàõîäèòü âåêòîðû u, v , . . . êàê ðåøåíèÿ ëèíåéíûõ ñèñòåì ñ ìàòðèöåé A èïðàâûìè ÷àñòÿìè r, s, . . . . Ìû âèäåëè â ëåêöèè 1, ÷òî ðåøåíèå íàøåé ñèñòåìû òðåáóåòq ≈ n2 îïåðàöèé óìíîæåíèÿ, íî òàêîâà æå ñòîèìîñòü âû÷èñëåíèÿ ïðîèçâåäåíèÿ A−1 íàâåêòîð.
Ïðåäâàðèòåëüíàÿ æå ðàáîòà ðåçêî ðàçëè÷àåòñÿ ïî îáúåìó: Q ≈ n3 /3 îïåðàöèéóìíîæåíèÿ äëÿ òðåóãîëüíîãî ðàçëîæåíèÿ A è (êàê ìû ñåé÷àñ ïîêàæåì) ≈ n3 îïåðàöèéäëÿ âû÷èñëåíèÿ A−1 , ò.å. âî âòîðîì ñëó÷àå âòðîå áîëüøå.Ìîæåò ñëó÷èòüñÿ, ÷òî íóæíû â ÿâíîì íåêîòîðûå ýëåìåíòû îáðàòíîé ìàòðèöû,ïðè÷åì îíè ðàñïîëîæåíû â îäíîì èëè íåñêîëüêèõ (íåáîëüøîì ÷èñëå) ñòîëáöîâ A−1 .Åñëè íîìåðà ýòèõ ñòîëáöîâ k , l è ò.ä., òî óêàçàííûå ñòîëáöû îïÿòü-òàêè ïðîùå âñåãîâû÷èñëèòü êàê ðåøåíèÿ ñèñòåì ñ ìàòðèöåé A, â êîòîðûõ ïðàâûìè ÷àñòÿìè ñëóæàòåäèíè÷íûå âåêòîðû ek , el è ò.ä.
(ñòîëáöû åäèíè÷íîé ìàòðèöû).È òîëüêî åñëè íåîáõîäèìû âñå èëè áîëüøàÿ ÷àñòü ýëåìåíòîâ A−1 , ïðèìåíåíèåïðîöåäóðû ÷èñëåííîãî îáðàùåíèÿ A îïðàâäàíà.Îïèøåì îäíó èç âîçìîæíûõ ïðîöåäóð âû÷èñëåíèÿ A−1 , îñíîâàííóþ íà èñïîëüçîâàíèè LU -ðàçëîæåíèÿ. Ïóñòü A = LU . Òîãäà A−1 = U −1 L−1 èëèU A−1 = L−1 .3.4. ÎÁÐÀÙÅÍÈÅ ÌÀÒÐÈÖÛ33Âîñïîëüçóåìñÿ ýòèì ñîîòíîøåíèåì äëÿ âû÷èñëåíèÿ A−1 . Äîïóñòèì ñíà÷àëà, ÷òî L−1 èçâåñòíà. Îáîçíà÷èì A−1 = X , L−1 = Y . Ïóñòü x.j è y.j j -å ñòîëáöû ìàòðèö Xè Y , ñîîòâåòñòâåííî, ò.å. X = [x.1 x.2 .
. . x.n ], x.j = [x1j x2j . . . xnj ]T . Òîãäà ïîëó÷èì nñèñòåì âèäàU x.j = y.j , j = 1, . . . , n(3.22)ñ òðåóãîëüíîé ìàòðèöåé, ðåøåíèÿ êîòîðûõ ìîãóò áûòü íàéäåíû ïî ôîðìóëàì (1.21)è"#nX1xkj =ykj −ukm xmj , k = n, n − 1, . . . 1.ukkm=k+1Íàéäåì òåïåðü L−1 = Y . Ïîñêîëüêó LY = I , òî èìååì n ñèñòåìLy.j = ej ,j = 1, . . . , n.(3.23)Çàìåòèì, ÷òî ìàòðèöà L−1 íèæíÿÿ òðåóãîëüíàÿ è ïîýòîìó ó ñòîëáöà y.j ïåðâûå(j − 1) ýëåìåíòà èçâåñòíû è ðàâíû íóëþ, ò.å. y.jT = [0 . . . 0 yjj yj+1 j . . . ynj ] = [0 y T.j ].Îòñþäà ñëåäóåò, ÷òî äëÿ îòûñêàíèÿ èñòèííûõ íåèçâåñòíûõ âåêòîðà y.j íóæíî ðåøèòüñèñòåìó ñ òðåóãîëüíîé ìàòðèöåé ðàçìåðîâ (n − j + 1) × (n − j + 1) îòíîñèòåëüíî y .j .Äëÿ ýòîãî ìîæíî âîñïîëüçîâàòüñÿ ôîðìóëàìè òèïà (1.21).Îöåíèì îáúåì ðàáîòû ïî âû÷èñëåíèþ A−1 .
 ñèëó (1.22) ôàêòîðèçàöèÿ A = LUòðåáóåò ≈ n3 /3 óìíîæåíèé, ðåøåíèå îäíîé ñèñòåìû (3.22) (ñì. (1.23) ) ≈ n2 /2, àâñåõ ≈ n3 /2, ðåøåíèå âñåõ ñèñòåì (3.23)nX(n − j + 1)2j=12=n1 X 2 n(n + 1)(2n + 1)i =≈ n3 /6.2 j=112Ñêëàäûâàÿ, íàõîäèì, ÷òî äëÿ âû÷èñëåíèÿ ìàòðèöû A−1 ïðè ïîìîùè îïèñàííîãî àëãîðèòìà òðåáóåòñÿ ∼ n3 óìíîæåíèé. Ýòî âñåãî ëèøü â òðè ðàçà áîëüøå, ÷åì äëÿ ðåøåíèÿñèñòåìû (3.1).34 3. ÌÅÒÎÄÛ ÕÎËÅÖÊÎÃÎ È ÁËÎ×ÍÎÃÎ ÈÑÊËÞ×ÅÍÈß 4Óñòîé÷èâîñòü âû÷èñëèòåëüíûõàëãîðèòìîâ ëèíåéíîé àëãåáðû4.1ÂâåäåíèåÈññëåäóåì âîïðîñ îá óñòîé÷èâîñòè ðåøåíèÿ ëèíåéíîé ñèñòåìû ïî îòíîøåíèþ ê âîçìóùåíèþ ïðàâîé ÷àñòè.
Ïóñòü ðàññìàòðèâàåòñÿ ñèñòåìà ñ êâàäðàòíîé íåâûðîæäåííîéìàòðèöåéAx = b(4.1)è ñèñòåìà ñ âîçìóùåííîé ïðàâîé ÷àñòüþ(4.2)Ax̃ = b̃.Îáîçíà÷èì b̃ − b = δb, x̃ − x = δx è îöåíèì δx ÷åðåç δb. Âû÷èòàÿ (4.1) èç (4.2), áóäåìèìåòüAδx = δb ⇒ δx = A−1 δb.(4.3)Ïóñòü k · k íåêîòîðàÿ íîðìà âåêòîðà.
 ëèíåéíîé àëãåáðå íàèáîëåå ÷àñòî èñïîëüçóþòñÿ ñëåäóþùèå íîðìûvu nnXuXkxk∞ = max |xi |, kxk1 =|xi |, kxk2 = tx2i .ii=1i=1Êàê èçâåñòíî, íîðìà ìàòðèöû, ïîä÷èíåííàÿ âåêòîðíîé íîðìå k · k, îïðåäåëÿåòñÿ ñîîòíîøåíèåìkAxk= sup kAxk.(4.4)kAk = supx6=0 kxkkxk=1Óêàçàííûì âåêòîðíûì íîðìàì ïî÷èíåíû ñëåäóþùèå ìàòðè÷íûå íîðìû:kAk∞ = maxinXj=1|aij |, kAk1 = maxj35nXi=1|aij |, kAk2 =pλmax (AAT ).36 4. ÓÑÒÎÉ×ÈÂÎÑÒÜ ÂÛ×ÈÑËÈÒÅËÜÍÛÕ ÀËÃÎÐÈÒÌÎÂÎ÷åâèäíî, ÷òî äëÿ ñèììåòðè÷íûõ ìàòðèöA = AT ,k · k∞ = k · k1 , à kAk2 = |λmax |,èáî Ax = λx, A2 x = λAx = λ2 x.Óïðàæíåíèå 4.1. Äîêàçàòü, ÷òî ïîä÷èíåííûå íîðìû çàäàþòñÿ èìåííî ýòèìè ñîîò-íîøåíèÿìè.Èç îïðåäåëåíèÿ (4.4) ìàòðè÷íîé íîðìû, â ÷àñòíîñòè, ñëåäóåò, ÷òîkAk >kAxkkxk⇒kAxk 6 kAk kxk.(4.5)Ïðèìåíÿÿ ýòî íåðàâåíñòâî êî âòîðîìó ñîîòíîøåíèþ (4.3), áóäåì èìåòükδxk 6 kA−1 k kδbk.(4.6)Ñîîòíîøåíèå (4.6) äàåò îöåíêó àáñîëþòíîé ïîãðåøíîñòè ðåøåíèÿ ÷åðåç àáñîëþòíóþïîãðåøíîñòü ïðàâîé ÷àñòè. Ïðè ýòîì ìíîæèòåëåì (êîýôôèöèåíòîì óñèëåíèÿ) âûñòóïàåò íîðìà îáðàòíîé ìàòðèöû.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
