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

. . −1 −101 −1 . . . −1 −1001 . . . −1 −1.........................000 ...1 −1000 ...01,b=−1−1−1·−11.38Ÿ 4. ÓÑÒÎÉ×ÈÂÎÑÒÜ ÂÛ×ÈÑËÈÒÅËÜÍÛÕ ÀËÃÎÐÈÒÌΠðàçâåðíóòîì âèäå ñèñòåìà çàïèøåòñÿ òàêx1 −x2 −x3 − . . . −xn = −1,x2 −x3 − . . . −xn = −1,....................................xn−1 −xn = −1,xn =1.(4.11)Î÷åâèäíî, ÷òî ðåøåíèåì ñèñòåìû (4.11) ÿâëÿåòñÿ âåêòîðx = [0, 0, . . . , 0, 1]T .Ëåãêî âèäåòü, ÷òî det A = 1.Âîçìóòèì ïîñëåäíþþ êîìïîíåíòó âåêòîðà bb̃ = [−1, −1, . . . , −1, 1 + ε]Tè îöåíèì ïîãðåøíîñòü ðåøåíèÿ.Âû÷èòàÿ èç âîçìóùåííîé ñèñòåìû ñèñòåìó (4.11), äëÿ ïîãðåøíîñòè ðåøåíèÿ ïîëó÷èìδx1 −δx2 − . . .

−δxn = 0,δx2 − . . . −δxn = 0,................................δxn−1 −δxn = 0,δxn = ε.Îòñþäà íàõîäèì, ÷òîδxn = ε, δxn−1 = ε, δxn−2 = δxn + δxn−1 = 2ε,δxn−3 = δxn + δxn−1 + δxn−2 = 4ε = 22 ε.Ïîãðåøíîñòü â êàæäîé èç ïîñëåäóþùèõ êîìïîíåíò, íà÷èíàÿ ñ δxn−2 , óäâàèâàåòñÿ, òàê÷òîδxn−k = δxn + δxn−1 + · · · + δxn−(k−1) = 2k−1 ε,àÒàêèì îáðàçîì,δx1 = 2n−2 ε.kδxk∞ = 2n−2 |ε|, kxk∞ = 1,kδbk∞ = |ε|, kbk∞ = 1, kAk∞ = n.Ïîñêîëüêó â ñèëó (4.8)à â ðàññìàòðèâàåìîì ñëó÷àåkδxk∞kδbk∞6 cond A,kxk∞kbk∞kδxk∞= 2n−2 |ε|,kxk∞4.3. ÏÐÈÌÅÐ ÕÎÐÎØÎ ÎÁÓÑËÎÂËÅÍÍÎÉ ÑÈÑÒÅÌÛòî39cond A = kA−1 k∞ kAk∞ > 2n−2è, ñëåäîâàòåëüíî,kA−1 k∞ > n−1 2n−2 .Ïðè n = 102, kAk∞ = 102, cond A > 2100 > 1030 , kA−1 k > 1027 .

Åñëè ε = 10−15 , òîkδxk∞ > 1015 . Ìàòðèöà ðàññìàòðèâàåìîé ñèñòåìû î÷åíü ïëîõî îáóñëîâëåíà.Ïîíÿòèå ÷èñëà îáóñëîâëåííîñòè ââåäåíî íàìè òîëüêî äëÿ íåâûðîæäåííûõ ìàòðèö.Óñëîâèå det A = 0 îçíà÷àåò âûðîæäåííîñòü ìàòðèöû A, è ìîæåò ñëîæèòüñÿ âïå÷àòëåíèå, ÷òî, åñëè det A ≈ 0, òî ìàòðèöà ïëîõî îáóñëîâëåíà. Îäíàêî, ïðÿìîé ñâÿçè ìåæäóâåëè÷èíîé îïðåäåëèòåëÿ ìàòðèöû A è åå îáóñëîâëåííîñòüþ íåò. Òàê, îïðåäåëèòåëüìàòðèöû èç ïðèìåðà (4.2) ðàâåí åäèíèöå, àcond A > 2n−2 .Ñ äðóãîé ñòîðîíû, õîðîøî îáóñëîâëåííàÿ ìàòðèöà ìîæåò èìåòü î÷åíü ìàëåíüêèéîïðåäåëèòåëü.

Íàïðèìåð, ó ìàòðèöû10−110−10 A=...010−1cond A = 1, õîòÿ det A = 10−n .4.3 Ïðèìåð õîðîøî îáóñëîâëåííîé ñèñòåìûÐàññìîòðèì ñëåäóþùóþ ñèñòåìó2x1 −9x2 +5x3 =−4,1.2x1 − 5.4x2 +6x3 =0.6,x1 −x2 − 7.5x3 = −8.5.(4.12)Ëåãêî ïðîâåðèòü, ÷òî ðåøåíèåì ýòîé ñèñòåìû ÿâëÿåòñÿ âåêòîðx = [0 1 1]T .Âîçìóòèì ìàòðèöó è âåêòîð ïðàâîé ÷àñòè ñèñòåìû (4.12) òàê, ÷òîáû 0 0 00δA = 0 ε 0 , δb = ε .0 0 00(4.13)40Ÿ 4. ÓÑÒÎÉ×ÈÂÎÑÒÜ ÂÛ×ÈÑËÈÒÅËÜÍÛÕ ÀËÃÎÐÈÒÌÎÂÎ÷åâèäíî, ÷òî ðåøåíèå âîçìóùåííîé ñèñòåìû ñîâïàäàåò ñ òî÷íûì ðåøåíèåì, ò.å.x̃ = x = [0 1 1]T .Áóäåì òåïåðü ðåøàòü ñèñòåìó (4.12) ñ âîçìóùåíèåì (4.13) ïðè ε = 10−4 íà øåñòèðàçðÿäíîì äåñÿòè÷íîì êàëüêóëÿòîðå ìåòîäîì ïîñëåäîâàòåëüíûõ èñêëþ÷åíèé, èñïîëüçóÿôîðìóëû (1.3) (1.6).Ïðÿìîé õîä.

1-é øàã. Âû÷èñëÿåì ïî ôîðìóëå (1.5) ìíîæèòåëèa21= 0.6,a11l21 =l31 =a31= 0.5,a11ÿâëÿþùèåñÿ ýëåìåíòàìè ïåðâîãî ñòîëáöà ëåâîé òðåóãîëüíîé ìàòðèöû L, è âû÷èòàÿ èçâòîðîãî è òðåòüåãî óðàâíåíèé âîçìóùåííîé ñèñòåìû ïåðâîå óðàâíåíèå, óìíîæåííîåíà l21 è l31 , ñîîòâåòñòâåííî, ò.å. ïðåîáðàçîâûâàÿ ñèñòåìó ïðè ïîìîùè ôîðìóë (1.3),(1.4), ïîëó÷èì2 x1 −9 x2 + 5 x3 =−4,0.0001 x2 + 3 x3 = 3.0001,(4.14)3.5 x2 − 10 x3 =−6.5.Âñå âû÷èñëåíèÿ íà ýòîì øàãå âûïîëíåíû òî÷íî, áåç îêðóãëåíèé, èáî âñå ÷èñëà âïðîìåæóòî÷íûõ âû÷èñëåíèÿõ, ðàâíî êàê è îêîí÷àòåëüíûå ÷èñëà, èìåëè ìàíòèññû ñìåíüøèì, ÷åì øåñòü, ÷èñëîì ðàçðÿäîâ.2-é øàã.

Ïîñëå âû÷èñëåíèÿ ïî ôîðìóëå (1.5) ìíîæèòåëÿ(1)(1)l32 = a32 /a22 = 3.5/0.0001 = 35000ïîñëåäíåå óðàâíåíèå ñèñòåìû (4.14) ñîãëàñíî (1.2) äîëæíî áûòü ïðåîáðàçîâàíî ê âèäó(2)(2)a33 x3 = b3 ,(4.15)ãäå ñîãëàñíî (1.3)(2)(1)(1)a33 = a33 − l32 a23 = −10 − l32 · 3 = −10 − 105000 = −105010,à ñîãëàñíî (1.4)(2)(1)(1)b3 = b3 − l32 b2 = −6.5 − l32 · 3.0001 == −6.5 − 105003.5 = −105010,ò.å.−105010 x3 = −105010.Îäíàêî íà èñïîëüçóåìîì êàëüêóëÿòîðå áóäåò ïîëó÷åíî óðàâíåíèå−105010 x3 = −105011.(2)(4.16) ñàìîì äåëå, êîýôôèöèåíò a33 âû÷èñëÿåòñÿ òî÷íî, òàê êàê ïðè åãî âû÷èñëåíèè íåâîçíèêàåò ÷èñåë, ìàíòèññû êîòîðûõ èìåþò áîëüøå øåñòè ðàçðÿäîâ.

 òî æå âðåìÿ4.3. ÏÐÈÌÅÐ ÕÎÐÎØÎ ÎÁÓÑËÎÂËÅÍÍÎÉ ÑÈÑÒÅÌÛ41(2)ïðè âû÷èñëåíèè b3 óìíîæåíèå 3.0001 íà l32 äàåò ñåìèçíà÷íîå ÷èñëî 105003.5, ïîñëå(2)îêðóãëåíèÿ êîòîðîãî äî øåñòè ðàçðÿäîâ ïîëó÷èì 105004. Âû÷èñëåíèå b3 çàâåðøàåòñÿâûïîëíåíèåì îïåðàöèè âû÷èòàíèÿ(2)b3 ≈ −6.5 − 105004 = −105010, 5 ≈ 105011,êîòîðàÿ òàêæå ïðîâîäèòñÿ ñ îêðóãëåíèåì, ÷òî è ïðèâîäèò ê (4.16).Îáðàòíûé õîä. Èç (4.16)x̃3 = 1.000009522 · · · ≈ 1.00001.Ñðàâíåíèå ñ èñòèííûì çíà÷åíèåì x3 ïîêàçûâàåò õîðîøóþ òî÷íîñòü.

Äàëåå, ñîãëàñíî(1.6), (4.14)x2 = (3.0001 − 3 x3 )/0.0001 = (3.0001 − 3.00003)/0.0001 = 0.7.Çäåñü âñå âû÷èñëåíèÿ âûïîëíåíû òî÷íî. Íàêîíåö,x̃1 = (−4 + 9 x2 − 5 x3 )/2 = (−4 + 6.3 − 5.00005)/2 == −1.350025 ≈ −1.35003.Èòàê, ïðèáëèæåííîå ðåøåíèå [−1.35003 0.7 1.00001] ìàëî ïîõîæå íà òî÷íîå ðåøåíèå. ÷åì ïðè÷èíà ïîÿâëåíèÿ ñòîëü çíà÷èòåëüíîé ïîãðåøíîñòè? Ãîâîðèòü î íàêîïëåíèè îøèáîê îêðóãëåíèÿ íå ïðèõîäèòñÿ, òàê êàê âñåãî áûëî âûïîëíåíî 28 àðèôìåòè÷åñêèõ îïåðàöèé è ëèøü â ÷åòûðåõ ñëó÷àÿõ ïîòðåáîâàëîñü îêðóãëåíèå.

Ïðåäïîëîæåíèåî ïëîõîé îáóñëîâëåííîñòè ñèñòåìû òàêæå íå ïîäòâåðæäàåòñÿ, èáî, êàê ïîêàçûâàþòâû÷èñëåíèÿ,2−956  , det A = −21,A = 1.2 −5.41−1 −1.5−46.5 72.5 271 −1520 6 A−1 =21−4.270è, ñëåäîâàòåëüíî,kAk1 = 18.5,kA−1 k1 =99.5,21cond A 6 102 .Äåéñòâèòåëüíàÿ ïðè÷èíà ñîñòîèò â òîì, ÷òî ìåòîä èñêëþ÷åíèÿ Ãàóññà â òîì âèäå,â êàêîì îí áûë îïèñàí, ÿâëÿåòñÿ íåóñòîé÷èâûì ìåòîäîì. ×òîáû îïðåäåëèòü, â ÷åì(2)èìåííî åãî ñëàáîñòü, ðàññìîòðèì áîëåå âíèìàòåëüíî ïðîöåäóðó âû÷èñëåíèÿ b3 , ãäå(1)è ïîÿâèëèñü ïåðâûå îêðóãëåíèÿ. Ïðè âû÷èñëåíèè ïðîèçâåäåíèÿ l32 · b2 = 105003.5èç-çà òîãî, ÷òî åãî ìàíòèññà ñîäåðæèò áîëåå øåñòè çíàêîâ, ïðèøëîñü ïðèáåãíóòüê îêðóãëåíèþ.

À òàê êàê ýòî ïðîèçâåäåíèå ê òîìó æå îêàçàëîñü î÷åíü áîëüøèì,ïîãðåøíîñòü îêðóãëåíèÿ òàêæå îêàçàëàñü áîëüøå 0.5.42Ÿ 4. ÓÑÒÎÉ×ÈÂÎÑÒÜ ÂÛ×ÈÑËÈÒÅËÜÍÛÕ ÀËÃÎÐÈÒÌÎÂ4.4 Ìåòîä Ãàóññà ñ âûáîðîì âåäóùåãî ýëåìåíòàÈç-çà îòìå÷åííîé íåóñòîé÷èâîñòè ìåòîä Ãàóññà â âû÷èñëèòåëüíîé ïðàêòèêå îáû÷íîïðèìåíÿåòñÿ â ñî÷åòàíèè ñ íåêîòîðîé ñõåìîé âûáîðà âåäóùåãî ýëåìåíòà. Íàïðèìåð,ñõåìà âûáîðà âåäóùåãî ýëåìåíòà ïî ñòîëáöó ñîñòîèò â ñëåäóþùåì. Ïåðåä íà÷àëîìïåðâîãî øàãà ñðåäè êîýôôèöèåíòîâ a11 , a21 , . . . , an1 , îáðàçóþùèõ ïåðâûé ñòîëáåö ìàòðèöû A, âûáèðàåòñÿ êîýôôèöèåíò ñ íàèáîëüøèì ìîäóëåì; ïóñòü ýòî áóäåò ak,1 .

Åñëèk > 1, òî â ñèñòåìå (4.1) ïåðåñòàâëÿþòñÿ 1-å è k -å óðàâíåíèÿ, ïðè k = 1 ïåðåñòàíîâêàíå íóæíà. Ïîñëå ýòîé ïðåäâàðèòåëüíîé ðàáîòû îáû÷íûì îáðàçîì ïðîâîäèòñÿ 1-é(1) (1)(1)øàã ïðÿìîãî õîäà. Äî íà÷àëà 2-ãî øàãà ñðåäè êîýôôèöèåíòîâ a22 , a31 , . . . , an2 (ò.å.(1)âî âòîðîì ñòîëáöå òåêóùåé ìàòðèöû) âûáèðàåòñÿ êîýôôèöèåíò al2 ñ íàèáîëüøèììîäóëåì.  ñëó÷àå l > 2 ïåðåñòàâëÿþòñÿ 2-å è l-å óðàâíåíèÿ, çàòåì âûïîëíÿåòñÿ 2-éøàã. È ò.ä.×òî äîñòèãàåòñÿ âûáîðîì âåäóùåãî ýëåìåíòà ïî ñòîëáöó? Ìû ìîæåì òåïåðü ãàðàíòèðîâàòü, ÷òî ìíîæèòåëè lij âñåõ øàãîâ ïî àáñîëþòíîé âåëè÷èíå îãðàíè÷åíû åäè(k−1)íèöåé. Ôîðìóëû (1.3) ïîêàçûâàþò, ÷òî, âî-ïåðâûõ, äîáàâêè lik akjê òåêóùèì çíà÷åíèÿì êîýôôèöèåíòîâ èìåþò òîò æå ïîðÿäîê âåëè÷èíû, ÷òî è ñàìè êîýôôèöèåíòû,âî-âòîðûõ, çà îäèí øàã óðîâåíü êîýôôèöèåíòîâ ìàòðèöû ìîæåò âûðàñòè íå áîëåå,÷åì â äâà ðàçà.

Äåéñòâèòåëüíî, ñîãëàñíî (1.3)¯ (k) ¯ ¯ (k−1)¯ ¯ (k−1) ¯ ¯ (k−1) ¯¯ (k−1) ¯(k−1)¯a ¯ = ¯a− lik akj ¯ 6 ¯aij ¯ + ¯akj ¯ 6 2 max ¯aij ¯.ijijij(4.17)Óïðàæíåíèå 4.2. Ðåøèòü ñèñòåìó (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 ÷èñëîðàçðÿäîâ, îòâåäåííûõ äëÿ ïðåäñòàâëåíèÿ ìàíòèññû.