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

×òîáû îïðåäåëèòü îñòàâøèéñÿñîìíîæèòåëü g(A), îáîçíà÷èìa = a0 = max |aij |,ij(k)ak = max |aij |,ij>kk = 1, 2, . . . , n − 1.Òîãäàg(A) = max ak /a.660 k n−1Òàêèì îáðàçîì, âåëè÷èíà g(A) èçìåðÿåò íàñêîëüêî ìîãëè âûðàñòè ýëåìåíòû ïðîìåæóòî÷íûõ ìàòðèö ìåòîäà ïî ñðàâíåíèþ ñ óðîâíåì ýëåìåíòîâ â èñõîäíîé ìàòðèöå A.Èòàê, ïðè ïðî÷èõ ðàâíûõ óñëîâèÿõ îøèáêè δA, âíîñèìûå ìåòîäîì â èñõîäíóþèíôîðìàöèþ, òåì áîëüøå, ÷åì áîëüøèé ðîñò ýëåìåíòîâ ìàòðèö äîïóñêàåòñÿ â ïðÿìîìõîäå. Åñëè â âåðñèè ìåòîäà Ãàóññà èç ïåðâîé ëåêöèè ðîñò ýëåìåíòîâ ìîæåò áûòü ñêîëüóãîäíî âåëèê, òî â ñõåìàõ ñ âûáîðîì âåäóùåãî ýëåìåíòà îí îãðàíè÷åí. Äåéñòâèòåëüíî, çà øàã ìàêñèìàëüíûé ìîäóëü ýëåìåíòà ìàòðèöû ìîæåò âûðàñòè ñàìîå áîëüøååâ äâà ðàçà (ñì.

(4.17)). Òàê êàê ìàëîâåðîÿòíî, ÷òîáû âîçìóùåíèå ïðîèñõîäèëî íàêàæäîì øàãå, òî îáû÷íî êîýôôèöèåíò ðîñòà g(A) íåâåëèê.  ýòîì ñëó÷àå áëàãîäàðÿìíîæèòåëþ p−t â ïðàâîé ÷àñòè (4.19) ìàòðèöó-âîçìóùåíèå δA ìîæíî ñ÷èòàòü ìàëîéïî ñðàâíåíèþ ñ A.Íà âîïðîñ î òîì, êàê ñêàçûâàåòñÿ âîçìóùåíèå (4.18) íà ðåøåíèè ñèñòåìû (4.1),îòâå÷àåò44Ÿ 4. ÓÑÒÎÉ×ÈÂÎÑÒÜ ÂÛ×ÈÑËÈÒÅËÜÍÛÕ ÀËÃÎÐÈÒÌÎÂÒåîðåìà 4.1.

Ïóñòü ìàòðèöà A ñèñòåìû (4.1) èìååò îáðàòíóþ è äëÿ åå âîçìó-ùåíèÿ δA ñïðàâåäëèâà îöåíêàkδAk < kA−1 k−1 .(4.20)Òîãäà äëÿ îòíîñèòåëüíîé ïîãðåøíîñòè ðåøåíèÿ ñïðàâåäëèâà îöåíê൶kδAk kδbkkδxkcond A6+,kδAk kAkkxkkbk1 − cond AkAkãäå(A + δA)(x + δx) = b + δb(4.21)(4.22) âîçìóùåííàÿ ñèñòåìà.Äîêàçàòåëüñòâî. Èç (4.22)Ax + δAx + Aδx + δAδx = b + δb.Âû÷èòàÿ îòñþäà (4.1), ïîëó÷èìAδx = δb − δAx − δAδx,èëèÎòñþäàδx = A−1 [δb − δAx − δAδx].kδxk 6 kA−1 k(kδbk + kδAk kxk + kδAk kδxk).Ðàçðåøèì ýòî íåðàâåíñòâî îòíîñèòåëüíî kδxk(1 − kA−1 k kδAk)kδxk 6 kA−1 k(kδbk + kδAk kxk).Ñ ó÷åòîì (4.20)kδxk 6kA−1 k(kδbk + kδAk kxk).1 − kA−1 k kδAkÍî1 − kA−1 k kδAk = 1 − cond A(4.23)kδAk.kAkÓ÷èòûâàÿ ýòî è äåëÿ (4.23) íà kxk, áóäåì èìåòüµ¶kδbkkδAk−1kA k kAk+kδxkkAk kxkkAk6.kδAkkxk1 − cond AkAkÏîñêîëüêó kAk kxk > kbk, òî èç (4.24) âûòåêàåò (4.21).

Òåîðåìà äîêàçàíà.(4.24)4.4. ÌÅÒÎÄ ÃÀÓÑÑÀ Ñ ÂÛÁÎÐÎÌ ÂÅÄÓÙÅÃÎ ÝËÅÌÅÍÒÀ45Ïðèâåäåì ïðèìåðû ìàòðèö, ïðåîáðàçîâàíèå êîòîðûõ ïðè ïîìîùè ìåòîäà Ãàóññà ñâûáîðîì âåäóùåãî ýëåìåíòà ïðèâîäèò ê ìàêñèìàëüíî âîçìîæíîìó óâåëè÷åíèþ êîýôôèöèåíòîâ ïðîìåæóòî÷íûõ ìàòðèö ïðÿìîãî õîäà.Ïðèìåð 4.3. Âûáîð ïî ñòîëáöó100−1 10A=−1 −1 1−1 −1 −11 0 00 1 0A3 = U = 0 0 10 0 011,1112,4810A1 = 001−1L=−1−10010−1 1−1 −10010−1 1−1 −11102, A2 = 020200.010 01 00 10 −112,44Óïðàæíåíèå 4.3.

Ïîêàçàòü, ÷òî âûáîð âåäóùåãî ýëåìåíòà ïî ñòðîêå äëÿ ìàòðèöû1 −1 −1 −10 1 −1 −1A=0 01 −11 111ïðèâîäèò ê ìàêñèìàëüíîìó ðîñòó ýëåìåíòîâ ïðîìåæóòî÷íûõ ìàòðèö.Çàìå÷àíèå 4.1. Âîçìîæíà åùå îäíà ñõåìà âûáîðà âåäóùåãî ýëåìåíòà: âûáîð ïî âñåéìàòðèöå.  ýòîì ñëó÷àå ãàðàíòèðóåòñÿ ïîëíàÿ óñòîé÷èâîñòü ìåòîäà Ãàóññà, îäíàêîñàìà ïðîöåäóðà âûáîðà òàêîãî âåäóùåãî ýëåìåíòà î÷åíü òðóäîåìêà äëÿ åå ðåàëèçàöèè òðåáóåòñÿ O(n3 ) äåéñòâèé, ÷òî ñðàâíèìî ñ òðóäîåìêîñòüþ ñàìîãî ìåòîäà è,ñëåäîâàòåëüíî, ñóùåñòâåííî óäîðîæàåò ðåøåíèå. Îòìåòèì, ÷òî ïðè âûáîðå âåäóùåãîýëåìåíòà ïî ñòîëáöó èëè ïî ñòðîêå òðåáóåòñÿ ëèøü O(n2 ) äîïîëíèòåëüíûõ îïåðàöèé.46Ÿ 4. ÓÑÒÎÉ×ÈÂÎÑÒÜ ÂÛ×ÈÑËÈÒÅËÜÍÛÕ ÀËÃÎÐÈÒÌΟ 5Ìåòîäû âðàùåíèé è îòðàæåíèé5.1Ìåòîä âðàùåíèéÂíîâü îáðàòèìñÿ ê ðåøåíèþ ñèñòåìû(5.1)Ax = bñ íåâûðîæäåííîé ìàòðèöåé.

Ðàññìîòðèì ìåòîä âðàùåíèé ðåøåíèÿ ñèñòåìû (5.1),êîòîðûé ïîçâîëÿåò ïîëó÷èòü ïðåäñòàâëåíèå ìàòðèöû A â âèäå ïðîèçâåäåíèÿ îðòîãîíàëüíîé ìàòðèöû Q è âåðõíåé òðåóãîëüíîé ìàòðèöû R.Êàê è â ìåòîäå Ãàóññà, â ìåòîäå âðàùåíèé íà ïåðâîì øàãå íåèçâåñòíîå x1 èñêëþ÷àåòñÿ èç âñåõ óðàâíåíèé êðîìå ïåðâîãî. Äëÿ òîãî, ÷òîáû èñêëþ÷èòü x1 èç âòîðîãîóðàâíåíèÿ, óìíîæèì ïåðâîå óðàâíåíèå íà íåêîòîðîå ÷èñëî c12 , à âòîðîå íà s12è çàìåíèì ïåðâîå óðàâíåíèå ñóììîé âíîâü ïîëó÷åííûõ óðàâíåíèé. Çàòåì óìíîæèìïåðâîå óðàâíåíèå íà s12 , âòîðîå íà c12 è âû÷òåì ïåðâîå èç âòîðîãî:(c12 a11 + s12 a21 )x1+ (c12 a12 + s12 a22 )x2+ ...(−s12 a11 + c12 a21 )x1 + (−s12 a12 + c12 a22 )x2 + .

. .= c12 b1 + s12 b2 ,= −s12 b1 + c12 b2 .×èñëà c12 è s12 âûáåðåì èç óñëîâèéc212 + s212 = 1,(5.2)−s12 a11 + c12 a21 = 0.Ðåøåíèå íåëèíåéíîé ñèñòåìû (5.2) ïðè a211 + a221 6= 0 äàþò, íàïðèìåð, ôîðìóëûc12 = pa11a211 + a221,a21s12 = pa211 + a221.(5.3)Åñëè æå a211 +a221 = 0, òî ðåøåíèå (5.2) äàþò ÷èñëà c12 = 1, s12 = 0. Âòîðîå èç óðàâíåíèé(5.2) êàê ðàç è îçíà÷àåò, ÷òî â íîâîì âòîðîì óðàâíåíèè íåèçâåñòíîãî x1 íå áóäåò.4748Ÿ 5. ÌÅÒÎÄÛ ÂÐÀÙÅÍÈÉ È ÎÒÐÀÆÅÍÈÉ ðåçóëüòàòå ñèñòåìà (5.1) ïðåîáðàçóåòñÿ ê âèäó(1)(1)(1)+ a1n xn = b1 ,(1)(1)+ a2n xn = b2a11 x1 + a12 x2 + a13 x2 + .

. .a22 x2 + a23 x3 + . . .a31 x1+ a32 x2+ a33 x3+ ...(1)(1)(1)(1),+ a3n xn = b3 ,(5.4)........................................................an1 x1 + an2 x2 + an3 x3 + . . .+ ann xn = bn ,â êîòîðîì(1)a1j= c12 a1j + s12 a2j ,(1)a2j= −s12 a1j + c12 a2j ,j = 1, 2, . . . , n,(1)b1= c12 b1 + s12 b2 ,(1)b2(5.5)= −s12 b1 + c12 b2 .Êàê ëåãêî âèäåòü, ïðåîáðàçîâàíèå èñõîäíîé ñèñòåìû (5.1) ê âèäó (5.4) ýêâèâàëåíòíî óìíîæåíèþ ìàòðèöû ñèñòåìû A è âåêòîðà ïðàâîé ÷àñòè b ñëåâà íà ìàòðèöó T12 ,èìåþùóþ âèäc12 s120−s12 c121T12 = ...0. 1Äëÿ èñêëþ÷åíèÿ íåèçâåñòíîãî x1 èç òðåòüåãî óðàâíåíèÿ ñèñòåìû (5.4) íîâîå ïåðâîåóðàâíåíèå è òðåòüå óðàâíåíèå, êîòîðîå ïîêà íå áûëî çàòðîíóòî ïðåîáðàçîâàíèÿìè,çàìåíÿþòñÿ èõ ëèíåéíûìè êîìáèíàöèÿìè ñ êîýôôèöèåíòàìè c13 , s13 è −s13 , c13 , ñîîòâåòñòâåííî.

Ïðè ýòîì êîýôôèöèåíòû c13 è s13 íàõîäÿòñÿ èç ñèñòåìûc213 + s213 = 1,(1)(5.6)−s13 a11 + c13 a31 = 0è ñóòü(1)a,c13 = r³ 11´2(1)a11 + a231s13 = r³a31´2(1)a11,+ a231à êîýôôèöèåíòû ïðåîáðàçîâàííûõ ïåðâîãî è òðåòüåãî óðàâíåíèé íàõîäÿòñÿ ïî ôîðìóëàì(2)(1)(1)(1)a1j = c13 a1j + s13 a3j ,a3j = −s13 a1j + c13 a3j ,j = 2, 3, . . . , n,(2)b1(1)= c13 b1 + s13 b3 ,(1)b3(1)= −s13 b1 + c13 b3 .5.1. ÌÅÒÎÄ ÂÐÀÙÅÍÈÉ49Ýòî ïðåîáðàçîâàíèå ýêâèâàëåíòíî óìíîæåíèþ ñëåâà ìàòðèöû ñèñòåìû (5.4) è åå âåêòîðà ïðàâîé ÷àñòè íà ìàòðèöóc13 0 s13 01 00−s13 0 c13T13 = 1..0.

1è ïðèâîäèò ê òîìó, ÷òî êîýôôèöèåíò ïðè x1 â ïðåîáðàçîâàííîì òðåòüåì óðàâíåíèèîáðàùàåòñÿ â íóëü.Ïðîäîëæàÿ ïîäîáíûì îáðàçîì, ìû èñêëþ÷èì x1 èç âñåõ îñòàëüíûõ óðàâíåíèé.Ïåðâîå óðàâíåíèå èçìåíÿåòñÿ íà êàæäîì òàêîì "ìàëîì"øàãå, êîòîðûõ áóäåò n − 1.Ïîýòîìó, ïî çàâåðøåíèè ïåðâîãî øàãà ñèñòåìà (5.1) ïðèìåò âèä(n−1)a11(n−1)x1 + a12(n−1)x2 + a13x3 + . . .(1)+ ...(1)a22 x2+ a23 x3(n−1)+ a1n(n−1)xn = b1(1),(1)+ a2n xn= b2 ,......................................................(1)an2 x2(1)+ an3 x3+ ...(1)(1)= bn .+ ann xn(1)(l−1)(1)Óïðàæíåíèå 5.1. Âûâåñòè ñîîòíîøåíèÿ äëÿ a(l−1), alj , b1 , bl è ïðåîáðàçóþùèõ1jêîýôôèöèåíòîâ c1l è s1l , l = 2, .

. . , n; j = 1, . . . , n.Îòâåò.(l−1)a1j(l−2)= c1l a1j(1)+ s1l alj ,alj(l−2)= −s1l a1j+ c1l alj ,j = 1, 2, . . . , n,(l−1)b1(l−2)= c1l b1(1)+ s1l bl ,bl(l−2)= −s1l b1+ c1l bl ,l = 2, 3, . . . , n,(l−2)c1l= r³a11(l−2)a11´2,+s1la2l1= r³al1´2(l−2)a11,+l = 2, 3, . . .

, n,a2l1(0)a11 = a11 .Çàìå÷àíèå 5.1. Ïîñêîëüêó â ñèëó íåâûðîæäåííîñòè ìàòðèöû A ïî êðàéíåé ìåðå(n−1)îäèí èç êîýôôèöèåíòîâ ai1 6= 0, òî a116= 0. ìàòðè÷íîé çàïèñè ýòà ñèñòåìà èìååò âèäA(1) x = b(1) ,50Ÿ 5. ÌÅÒÎÄÛ ÂÐÀÙÅÍÈÉ È ÎÒÐÀÆÅÍÈÉãäåA(1) = T1 A,b(1) = T1 b,T1 = T1n T1 n−1 . .

. T13 T12 .Íà âòîðîì øàãå ìåòîäà âðàùåíèé èç òðåòüåãî, ÷åòâåðòîãî è ò.ä. óðàâíåíèé ïîëó÷åííîé ñèñòåìû èñêëþ÷àåòñÿ íåèçâåñòíîå x2 . Øàã ñîñòîèò èç (n − 2) "ìàëûõ"øàãîâ,è â êàæäîì èç íèõ âòîðîå óðàâíåíèå êîìáèíèðóåòñÿ ñ îäíèì èç íèæåëåæàùèõ. Ïîñëåâûïîëíåíèÿ âòîðîãî øàãà ñèñòåìà ïðåîáðàçóåòñÿ ê âèäó(n−1)a11(n−1)x2 + a13(n−1)x1 + a12a22(n−1)x3 + . . .+ a1nx2 + a23(n−2)x3 + . .

.+ a2n(2)+ ...a33 x3(n−1)xn = b1(n−2)xn = b2(2)(n−1),(n−1),(2)+ a3n xn= b3 ,.........................................(2)an3 x3+ ...(2)(2)+ ann xn= bn .(2)(l−1)(2)Óïðàæíåíèå 5.2. Âûâåñòè ñîîòíîøåíèÿ äëÿ a(l−1), alj , b2 , bl , c2l è s2l .2jÎòâåò.(l−1)a2j(l−2)= c2l a2j(1)(2)+ s2l alj ,alj(l−2)= −s2l a2j(1)+ c2l a2j ,j = 2, 3, . . . , n,(l−1)b2(l−2)= c2l b2(1)(2)+ s2l bl ,bl(l−2)= −s2l b2(1)+ c2l bl ,l = 3, 4, . . . , n,(1)(l−2)c2l= r³a22´2(l−2)a22³+(1)al2´2 ,s2l= r³(l−2)a22al2´2³+(1)al2´2 . ìàòðè÷íîé ôîðìå ýòà ñèñòåìà èìååò âèäA(2) x = b(2) ,ãäåA(2) = T2 A(1) ,b(2) = T2 b(1) ,T2 = T2n T2 (n−1) .

. . T24 T23 .Ïîñëå (n − 1) øàãîâ ïîëó÷èì ñèñòåìó(n−1)a11(n−1)x2 + a13(n−1)x2 + a23x1 + a12a22(n−1)x3 + . . . + a1n(n−1)xn = b 1(n−2)x3 + . . . + a2n(n−1),(n−2)xn = b 2(n−1),....................................................................(n−1)ann(n−1)xn = b n,(5.7)5.1. ÌÅÒÎÄ ÂÐÀÙÅÍÈÉãäå(l−1)akj(l−2)= ckl akj51(k−1)+ skl alj,(k)alj(l−2)= −skl akj(k−1)+ ckl alj,j = k, k + 1, .

. . , n,(l−1)bk(l−2)= ckl bk(k−1)+ skl bl,(k)blk = 1, . . . , n,(l−2)= −skl bk(k−1)+ ckl bl,(5.8)l = k + 1, . . . , n,à(l−2)ckl = r³(k−1)akk´2 ³´2 ,(l−2)(k−1)+ alkakkskl = r³(l−2)akkalk´2³+(k−1)alk´2 .(5.9) ìàòðè÷íîé çàïèñè ïîëó÷åííàÿ ñèñòåìà èìååò âèäA(n−1) x = b(n−1) ,ãäåA(n−1) = Tn−1 A(n−2) ,b(n−1) = Tn−1 b(n−2) ,Tn−1 = Tn−1n .Îáîçíà÷èì ÷åðåç R ïîëó÷åííóþ âåðõíþþ òðåóãîëüíóþ ìàòðèöó A(n−1) . Îíà ñâÿçàíà ñ èñõîäíîé ìàòðèöåé A ðàâåíñòâîìR = T A,(5.10)ãäå T = Tn−1 Tn−2 .

. . T1 .Çàìå÷àíèå 5.2. Äåéñòâèå ìàòðèöû Tkl íà âåêòîð x ýêâèâàëåíòíî åãî ïîâîðîòó ïðîòèâõîäà ÷àñîâîé ñòðåëêè â êîîðäèíàòíîé ïëîñêîñòè Oxk xl íà óãîë ϕkl òàêîé, ÷òîcos ϕkl = ckl ,sin ϕkl = skl .Ñóùåñòâîâàíèå òàêîãî óãëà ãàðàíòèðóåòñÿ ñîîòíîøåíèÿìè (5.9). Ýòà ãåîìåòðè÷åñêàÿèíòåðïðåòàöèÿ è äàëà íàçâàíèå ìåòîäó.Ñ ó÷åòîì (5.2), (5.6) è ò.ä. ëåãêî âèäåòü, ÷òîTkl TklT = I,ò.å.

ìàòðèöû Tkl îðòîãîíàëüíûå. Ïðîèçâåäåíèå îðòîãîíàëüíûõ ìàòðèö åñòü ìàòðèöàîðòîãîíàëüíàÿ, è ïîýòîìó T åñòü îðòîãîíàëüíàÿ ìàòðèöà, ðàâíî êàê è T T = T −1 = Q.Îòñþäà è èç (5.10) íàõîäèì, ÷òîA = QR.(5.11)Óïðàæíåíèå 5.3. Ïîêàçàòü, ÷òî äëÿ ïîñòðîåíèÿ ðàçëîæåíèÿ (5.11) ñ èñïîëüçîâàíèåì ôîðìóë (5.8), (5.9), òðåáóåòñÿ ≈ 4n3 /3 äåéñòâèé óìíîæåíèÿ.52Ÿ 5. ÌÅÒÎÄÛ ÂÐÀÙÅÍÈÉ È ÎÒÐÀÆÅÍÈÉÇàìå÷àíèå 5.3. Ïðèíèìàÿ âî âíèìàíèå ðåçóëüòàòû âû÷èñëåíèé èç óïðàæíåíèÿ 5.3,çàêëþ÷àåì, ÷òî ìåòîä âðàùåíèé ïðèìåðíî â ÷åòûðå ðàçà áîëåå òðóäîåìîê, ÷åì ìåòîäÃàóññà.Âûÿñíèì, êàêèìè æå äîñòîèíñòâàìè îáëàäàåò ýòîò ìåòîä ïî ñðàâíåíèþ ñ ìåòîäîì Ãàóññà, áëàãîäàðÿ êîòîðûì îí çàñëóæèâàåò ïðàâî íà ñóùåñòâîâàíèå íåñìîòðÿ íàáîëüøóþ òðóäîåìêîñòü.Ñ ó÷åòîì (5.2) èç (5.5) íàõîäèì, ÷òî(1)(1)[a1j ]2 + [a2j ]2 = c212 a21j + s212 a22j + 2c12 s12 a1j a2j ++ s212 a21j + c212 a22j − 2s12 c12 a1j a2j = a21j + a22j ,j = 1, 2, .