В.Б. Андреев - Численные методы (2 в 1). (2007) (1160465), страница 6
Текст из файла (страница 6)
Ðåøèòü ñèñòåìó (4.12) ìåòîäîì Ãàóññà ñ âûáîðîì âåäóùåãî ýëå-ìåíòà ïî ñòîëáöó íà 6-ðàçðÿäíîì äåñÿòè÷íîì êàëüêóëÿòîðå.Èíîãäà èñïîëüçóåòñÿ è äðóãàÿ ñõåìà âûáîðà âåäóùåãî ýëåìåíòà, à èìåííî, ñõåìàâûáîðà ïî ñòðîêå. Çäåñü äî íà÷àëà 1-ãî øàãà îïðåäåëÿåòñÿ íàèáîëüøèé ïî ìîäóëþñðåäè êîýôôèöèåíòîâ a11 , a12 , . . . , a1n . Ïóñòü èì áóäåò êîýôôèöèåíò a1k . Åñëè k > 1, òîïðîèçâîäèòñÿ ïåðåíóìåðàöèÿ íåèçâåñòíûõ: 1-å è k -å íåèçâåñòíûå ìåíÿþòñÿ íîìåðàìè.Ýòî ñîîòâåòñòâóåò ïåðåñòàíîâêå ñòîëáöîâ ìàòðèöû ñèñòåìû.
Ïðè k = 1 ïåðåñòàíîâêàíå íóæíà. Òåïåðü îáû÷íûì îáðàçîì ïðîâîäèòñÿ 1-é øàã ïðÿìîãî õîäà. È ò.ä.Ïåðåõîäÿ ê âûáîðó âåäóùåãî ýëåìåíòà ïî ñòîëáöó, ìû ïîëó÷èëè äëÿ ñèñòåìû (4.12)ïðèáëèæåííîå ðåøåíèå õîðîøåãî êà÷åñòâà. Íî ýòî íå çíà÷èò, ÷òî îïèñàííûå ñõåìû ñâûáîðîì âåäóùåãî ýëåìåíòà ïðèäàþò ìåòîäó Ãàóññà ãàðàíòèðîâàííóþ óñòîé÷èâîñòü.Õîòÿ îáû÷íî ñõåìû ñ âûáîðîì âåäóùåãî ýëåìåíòà ïî ñòîëáöó èëè ïî ñòðîêå äåéñòâèòåëüíî îáåñïå÷èâàþò óñòîé÷èâîå âû÷èñëåíèå. êàêèõ æå ñëó÷àÿõ óòðà÷èâàåòñÿ óñòîé÷èâîñòü? ×òîáû ïîíÿòü ýòî, çàìåòèì, ÷òîâî ìíîãèõ ÷èñëåííûõ ìåòîäàõ îøèáêè ïðîìåæóòî÷íûõ âû÷èñëåíèé â ñîâîêóïíîñòèðàâíîñèëüíû òîìó, êàê åñëè áû òåì æå ìåòîäîì òî÷íî ðåøàëè èñõîäíóþ çàäà÷ó,ïðåäâàðèòåëüíî èçìåíèâ åå âõîäíûå äàííûå.
Ýòî îòíîñèòñÿ è ê ìåòîäó Ãàóññà. Ìîæíîïîêàçàòü, ÷òî ðåøåíèå ëèíåéíîé ñèñòåìû (4.1), âû÷èñëåííîå ìåòîäîì Ãàóññà (ñ òîé èëèèíîé ñõåìîé âûáîðà âåäóùåãî ýëåìåíòà èëè âîîáùå áåç âûáîðà) ïðè íàëè÷èè îøèáîê4.4. ÌÅÒÎÄ ÃÀÓÑÑÀ Ñ ÂÛÁÎÐÎÌ ÂÅÄÓÙÅÃÎ ÝËÅÌÅÍÒÀ43îêðóãëåíèÿ òî÷íî óäîâëåòâîðÿåò èçìåíåííîìó óðàâíåíèþ(4.18)(A + δA)x̃ = b. ïîÿñíåíèå ñêàçàííîãî ðàññìîòðèì óìíîæåíèå äâóõ òðåóãîëüíûõ ìàòðèö ñ ó÷åòîìîøèáîê îêðóãëåíèÿ·¸ ·¸^aabb11121112g=AB=0 a220 b22·¸a11 b11 (1 + ε1 ) (a11 b12 (1 + ε2 ) + a12 b22 (1 + ε3 ))(1 + ε4 )=0a22 b22 (1 + ε5 )Åñëè ïîëîæèòü·¸a11 a12 (1 + ε3 )(1 + ε4 )eA=,0a22 (1 + ε5 )òî ëåãêî ïðîâåðèòü, ÷òî·¸b11 (1 + ε1 ) b12 (1 + ε2 )(1 + ε4 )eB=,0b22g=AeB.eABÄëÿ íîðìû ìàòðèöû âîçìóùåíèÿ â (4.18) ñïðàâåäëèâà îöåíêàkδAk∞ 6 f (n)g(A)kAk∞ p−t .(4.19)Çäåñü f (n) íåêîòîðàÿ ìåäëåííî ðàñòóùàÿ ôóíêöèÿ îò ïîðÿäêà n ñèñòåìû (òèïàñòåïåííîé ñ íåáîëüøèì ïîêàçàòåëåì); p îñíîâàíèå ìàøèííîé àðèôìåòèêè; t ÷èñëîðàçðÿäîâ, îòâåäåííûõ äëÿ ïðåäñòàâëåíèÿ ìàíòèññû.
×òîáû îïðåäåëèòü îñòàâøèéñÿñîìíîæèòåëü 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 −11 0 00 1 0A3 = U = 0 0 10 0 011,1112,4810A1 = 001−1L=−1−10010−1 1−1 −10010−1 1−1 −11102, A2 = 020200.010 01 00 10 −112,44Óïðàæíåíèå 4.3.
Ïîêàçàòü, ÷òî âûáîð âåäóùåãî ýëåìåíòà ïî ñòðîêå äëÿ ìàòðèöû1 −1 −1 −10 1 −1 −1A=0 01 −11 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 c121T12 = ...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 01 00−s13 0 c13T13 = 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) . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
