В.Б. Андреев - Численные методы (2 в 1). (2007) (1160465), страница 5
Текст из файла (страница 5)
×åì áîëüøå ýòà íîðìà, òåì íà ìåíüøóþ òî÷íîñòü ìûìîæåì ðàññ÷èòûâàòü.Ïîëó÷èì òåïåðü îöåíêó îòíîñèòåëüíîé ïîãðåøíîñòè. Èç (4.1) â ñèëó (4.5)kAk kxk > kbk.(4.7)kδxkkδbk6 kAk kA−1 k.kxkkbk(4.8)Äåëÿ (4.6) íà (4.7), ïîëó÷èìÝòî è åñòü îöåíêà îòíîñèòåëüíîé ïîãðåøíîñòè, êîòîðàÿ, âîîáùå ãîâîðÿ, íåñåò áîëüøåèíôîðìàöèè, ÷åì îöåíêà (4.6). Çäåñü êîýôôèöèåíòîì óñèëåíèÿ âûñòóïàåò ÷èñëîkAk kA−1 k =: cond A,íàçûâàåìîå ÷èñëîì îáóñëîâëåííîñòè ìàòðèöû A.Åñëè ÷èñëî îáóñëîâëåííîñòè ìàòðèöû A áîëüøîå, òî ïðî ìàòðèöó A ãîâîðÿò, ÷òîîíà ïëîõî îáóñëîâëåíà.
 ïðîòèâíîì ñëó÷àå ãîâîðÿò î õîðîøî îáóñëîâëåííîé ìàòðèöå.Ïîñêîëüêó AA−1 = I , òî kAk kA−1 k > 1, ò.å. ÷èñëî îáóñëîâëåííîñòè íå ìîæåò áûòüìåíüøå åäèíèöû. Èìåÿ ñèñòåìó ñ õîðîøî îáóñëîâëåííîé ìàòðèöåé, ìû âïðàâå ðàññ÷èòûâàòü íà òî, ÷òî ïðè íåáîëüøèõ âîçìóùåíèÿõ ïðàâîé ÷àñòè âîçìóùåíèå ðåøåíèÿíå áóäåò ñëèøêîì âåëèêî.4.2. ÏÐÈÌÅÐÛ ÑÈÑÒÅÌ Ñ ÏËÎÕÎ ÎÁÓÑËÎÂËÅÍÍÎÉ ÌÀÒÐÈÖÅÉ4.237Ïðèìåðû ñèñòåì ñ ïëîõî îáóñëîâëåííîé ìàòðèöåéÏðèìåð 4.1.x1= 1,x1 + 0.01x2 = 1.(4.9)Î÷åâèäíî, ÷òî ýòà ñèñòåìà íåâûðîæäåíà è åå åäèíñòâåííûì ðåøåíèåì ÿâëÿåòñÿ âåêòîð[1, 0]T . Âîçìóòèì ïðàâóþ ÷àñòü ñèñòåìû (4.9) è íàéäåì ðåøåíèå âîçìóùåííîé çàäà÷è½x̃1= 1,δb2 = 0.01.(4.10)x̃1 + 0.01x̃2 = 1.01,Î÷åâèäíî, ÷òî ðåøåíèåì ýòîé ñèñòåìû ÿâëÿåòñÿ âåêòîð x̃ = [1, 1]T , êîòîðûé ìàëîïîõîæ íà íåâîçìóùåííûé âåêòîð x, èáîδx2 = 1,δx1 = 0,kδxk1 = 1.Ýòî çíà÷åíèå àáñîëþòíîé ïîãðåøíîñòè ðåøåíèÿ ïîëíîñòüþ ñîãëàñóåòñÿ ñ îöåíêàìè(4.6), (4.8), èá10−1,A =−100 100kAk1 = maxj2X|aij | = 2,i=1−1kA k1 = 101,kxk1 = 1,kbk1 = 2,kδbk1 = 0.01è, ñëåäîâàòåëüíî, â ñèëó (4.6)kδxk1 6 101 · 0.01 = 1.01,à â ñèëó (4.8)kδxk10.016 2 · 101 ·= 1.01.kxk12Ïðè çàäàííîì (4.10) óðîâíå ïîãðåøíîñòè ïðàâîé ÷àñòè îáóñëîâëåííîñòü ìàòðèöû ýòîéñèñòåìû (cond A = 202) ñëåäóåò ïðèçíàòü ïëîõîé.Ïðèìåð 4.2.A=1 −1 −1 .
. . −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−110−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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
