В.Б. Андреев - Численные методы (1113834), страница 15
Текст из файла (страница 15)
Ñêîðîñòü ñõîäèìîñòè íèçêàÿ.Îïðåäåëåíèå 11.4. Ìàòðèöà A èìååò âåðõíþþ ôîðìó Õåññåíáåðãà, åñëè aij = 0äëÿ ëþáûõ i > j + 1.Ýòî îçíà÷àåò, ÷òî ìàòðèöà èìååò ïî÷òè òðåóãîëüíóþ ôîðìó.∗ ∗ ∗ ∗ ∗∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗∗ ∗ ∗∗ ∗Òåîðåìà 11.1. Âñÿêàÿ äåéñòâèòåëüíàÿ êâàäðàòíàÿ ìàòðèöà ïðè ïîìîùè îðòîãîíàëüíîãî ïðåîáðàçîâàíèÿ ïîäîáèÿ ìîæåò áûòü ïðèâåäåíà ê ôîðìå Õåéñåíáåðãà.Äîêàçàòåëüñòâî. Ïîñòðîèì òðåáóåìîå ïðåîáðàçîâàíèå.
Ýòîò àëãîðèòì î÷åíü ïîõîæ íà àëãîðèòì QR-ðàçëîæåíèÿ ìàòðèöû ïðè ïîìîùè îòðàæåíèé. Ïðèâåäåíèå îñóùåñòâëÿåòñÿ çà n − 2 øàãà. Íà ïåðâîì øàãå íåîáõîäèìûìè íóëÿìè çàïîëíèòñÿ ïåðâûéñòîëáåö, íà âòîðîì øàãå âòîðîé è ò.ä.Âûïîëíèì ïåðâûé øàã. Çàïèøåì ìàòðèöó A â âèäå·¸a11 cTA=b .b A114 11. ÏÐÎÁËÅÌÀ ÑÎÁÑÒÂÅÍÍÛÕ ÇÍÀ×ÅÍÈÉb1 ìàòðèöà îòðàæåíèÿ, ïåðåâîäÿùàÿ (n−1)-ìåðíûé âåêòîð â âåêòîð [t 0 . . . 0]T ,Ïóñòü Uè ïóñòü·¸1 0U1 =(11.21)b1 .0 UÒîãäà·¸·¸ ·¸ TT1 0a11 ca11 cU1 A == b=bbbb0 U1b AU1 b U1 Aa11 cTt10..
b b. U1 A10.Äàëåå, ïðè âû÷èñëåíèè U1 AU1−1 âñïîìíèì, ÷òî U1−1 U1T = U1 , è, ñëåäîâàòåëüíî,·a11 cTU1 AU1 =bb A¸·¸ 1 0=b10 Ub1a11 cT Ut10.. b b b. U1 A1 U10 = a11 ∗ . . . ∗t10..b1 Ub1A.0(11.22)è ò.ä.Çàìå÷àíèå 11.4. Åñëè áû ìû ïîïûòàëèñü âçÿòü òàêóþ ìàòðèöó îòðàæåíèé U1 , êîòî-ðàÿ îñòàâëÿåò â ïåðâîì ñòîëáöå òîëüêî îäèí íåíóëåâîé ýëåìåíò, òî ïðè óìíîæåíèè U1 Aíà U1 ñïðàâà íàì íå óäàëîñü áû ñîõðàíèòü ñòðóêòóðó ïåðâîãî ñòîëáöà, ò.å. ïîëó÷åííûåïîñëå ïåðâîãî óìíîæåíèÿ A íà U1 ñëåâà íóëè.
Èìåííî áëàãîäàðÿ ôîðìóëå (11.21) äëÿìàòðèöû U1 îïåðàöèÿ óìíîæåíèÿ íà U1 ñïðàâà íå çàòðàãèâàåò íóëè â ïåðâîì ñòîëáöå(11.22).Çàìå÷àíèå 11.5. Äëÿ ñèììåòðè÷íîé ìàòðèöû A îðòîãîíàëüíî ïîäîáíàÿ åé ìàòðèöàòîæå ñèììåòðè÷íà è, ñëåäîâàòåëüíî, â ýòîì ñëó÷àå ìàòðèöà Õåññåíáåðãà áóäåò òðèäèàãîíàëüíîé.Òåîðåìà 11.2. Ïóñòü Am íåâûðîæäåííàÿ âåðõíÿÿ õåññåíáåðãîâà ìàòðèöà è Am+1ïîëó÷åíà èç Am ïîñðåäñòâîì îäíîé QR-èòåðàöèè (11.20). Òîãäà Am+1 òàêæå èìååòâåðõíþþ õåññåíáåðãîâó ôîðìó.Äîêàçàòåëüñòâî.
Äëÿ ïîñòðîåíèÿ Am+1 íàì íóæíî ñíà÷àëà ïîñòðîèòü ðàçëîæå-−1. Ðàíåå áûëî ïîêàçàíîíèå Am = Qm Rm , êîòîðîå ìîæíî ïåðåïèñàòü â âèäå Qm = Am Rm(óïðàæíåíèå 1.1), ÷òî îáðàòíàÿ ê íåâûðîæäåííîé âåðõíåé òðåóãîëüíîé ìàòðèöå åñòüâåðõíÿÿ òðåóãîëüíàÿ ìàòðèöà. Àíàëîãè÷íî äîêàçûâàåòñÿ, ÷òî ïðîèçâåäåíèå âåðõíåéòðåóãîëüíîé è âåðõíåé õåññåíáåðãîâîé ìàòðèöû â ëþáîì ïîðÿäêå åñòü âåðõíÿÿ õåññåíáåðãîâà ìàòðèöà. Ïîýòîìó Qm åñòü âåðõíÿÿ õåññåíáåðãîâà ìàòðèöà.
Íî è Am+1 =Rm Qm äîëæíà áûòü âåðõíåé õåññåíáåðãîâîé. Òåîðåìà äîêàçàíà.11.5. Q R - ÀËÃÎÐÈÒÌÏóñòü115(m)(m)(m)a1,n−1 a1,na11 am12 · · · (m) m(m)(m) a21 a22 · · · a2,n−1 a2,n (m)(m) mAm = a···aa3,n−13,n 32. . . . . . . . . . . . . . . . . . . . . . . . . . .(m)(m)an,n−1 an,nÅñëè |λi | > |λi+1 |, òî(m)ai+1,iµ¯¯ λi+1= O ¯¯λi¯¶m¯¯.¯Òåîðåìà 11.3 (Òåîðåìà Øóðà). Ïóñòü A ∈ Cn ×Cn .
Òîãäà ñóùåñòâóåò óíèòàðíàÿìàòðèöà U ∈ Cn × Cn è âåðõíÿÿ òðåóãîëüíàÿ ìàòðèöà T ∈ Cn × Cn òàêèå, ÷òîT = U ∗ AU.A = U T U ∗ ðàçëîæåíèå Øóðà.Çàìå÷àíèå 11.6. Ïðè ðåøåíèè ñèñòåìû (11.18)(èëè ñèñòåìû ñ ìàòðèöåé (11.19))ñëåäóåò îïàñàòüñÿ òðóäíîñòåé, êîòîðûå ìîãóò âîçíèêíóòü â ñâÿçè ñ ïëîõîé îáóñëîâb ). Ñ îäíîé ñòîðîíû, ÷åì áëèæå ê ñîáñòâåííîìóëåííîñòüþ ìàòðèöû A (èëè (A − λI)çíà÷åíèþ, òåì áûñòðåå ñõîäÿòñÿ èòåðàöèè, ñ äðóãîé ñòîðîíû, òåì õóæå îáóñëîâëåííîñòü ìàòðèöû, ïîäëåæàùåé îáðàùåíèþ.116 11. ÏÐÎÁËÅÌÀ ÑÎÁÑÒÂÅÍÍÛÕ ÇÍÀ×ÅÍÈÉÃëàâà IIÌåòîäû ðåøåíèÿ íåëèíåéíûõóðàâíåíèé117 12Ìåòîäû ðåøåíèÿ íåëèíåéíûõóðàâíåíèéÏóñòü çàäàíà íåïðåðûâíàÿ ôóíêöèÿ f (x) äåéñòâèòåëüíîé ïåðåìåííîé x, è òðåáóåòñÿíàéòè åå íóëè, ò.å.
êîðíè óðàâíåíèÿf (x) = 0.(12.1)Ïðè òàêîé ôîðìóëèðîâêå çàäà÷à âåñüìà íåîïðåäåëåííà, èáî êîðíåé ìîæåò íå áûòüâîâñå, èëè èõ ìîæåò áûòü áåñêîíå÷íî ìíîãî. Îáû÷íî çàäà÷à ôîðìóëèðóåòñÿ áîëååêîíêðåòíî ñ äîïîëíèòåëüíûìè óêàçàíèÿìè. Íàïðèìåð, îòûñêàíèå êîðíåé íà çàäàííîìèíòåðâàëå. Ïîñêîëüêó íå ñóùåñòâóåò ðåãóëÿðíûõ ìåòîäîâ îòûñêàíèÿ òî÷íûõ çíà÷åíèéêîðíåé óðàâíåíèÿ (12.1), òî ðå÷ü äîëæíà èäòè îá èòåðàöèîííûõ ìåòîäàõ íàõîæäåíèÿïðèáëèæåííîãî ðåøåíèÿ. (Òîëüêî åñëè f (x) ïðåäñòàâëÿåò ñîáîé ìíîãî÷ëåí íå âûøå4-îé ñòåïåíè, èìåþòñÿ ìåòîäû ïðåäñòàâëåíèÿ åãî íóëåé â âèäå ðàäèêàëîâ.)×òîáû âîñïîëüçîâàòüñÿ òåì èëè èíûì èòåðàöèîííûì ìåòîäîì, íóæíî èìåòü íà÷àëüíîå ïðèáëèæåíèå ê êîðíþ. Äëÿ ýòîãî íóæíî, ïî êðàéíåé ìåðå, èçó÷èòü ðàñïîëîæåíèå êîðíåé è âûäåëèòü îáëàñòè, ãäå èìååòñÿ åäèíñòâåííûé êîðåíü.
 ïðîòèâíîìñëó÷àå ìû äîëæíû ñ èñïîëüçîâàíèåì òîãî èëè èíîãî èòåðàöèîííîãî ïðîöåññà óòî÷íèòüçíà÷åíèÿ êîðíåé èëè íàéòè èõ ñ òðåáóåìîé òî÷íîñòüþ.Ñïîñîáû ëîêàëèçàöèè êîðíåé (âûäåëåíèå îáëàñòåé, ãäå èìååòñÿ åäèíñòâåííûé êîðåíü) ìíîãîîáðàçíû, è óêàçàòü óíèâåðñàëüíûé ìåòîä íå ïðåäñòàâëÿåòñÿ âîçìîæíûì.Èíîãäà îòðåçêè ëîêàëèçàöèè èçâåñòíû çàðàíåå, à èíîãäà îïðåäåëÿþòñÿ èç ôèçè÷åñêèõñîîáðàæåíèé.  ïðîñòûõ ñèòóàöèÿõ õîðîøèé ðåçóëüòàò ìîæåò äàòü ãðàôè÷åñêèé ìåòîä; øèðîêî ïðèìåíÿþò ïîñòðîåíèå òàáëèö ôóíêöèè f (x) âèäà yi = f (xi ), i = 1, n äëÿîáíàðóæåíèÿ ïåðåìåí çíàêà.119120 12.
ÌÅÒÎÄÛ ÐÅØÅÍÈß ÍÅËÈÍÅÉÍÛÕ ÓÐÀÂÍÅÍÈÉ12.1 Ìåòîä áèñåêöèè (ìåòîä äåëåíèÿ îòðåçêà ïîïîëàì)Ïóñòü f (x) ∈ C[a, b] è f (a)f (b) < 0. Ïîñëåäíåå îçíà÷àåò, ÷òî íà [a, b] èìååòñÿ, ïîêðàéíåé ìåðå, îäèí êîðåíü óðàâíåíèÿ (12.1). (Óñëîâèå ñóùåñòâîâàíèÿ ðåøåíèÿ.) Ïðåäïîëîæèì, ÷òî ðåøåíèå åäèíñòâåííîå, ò.å. x∗ ∈ (a, b) åäèíñòâåííûé êîðåíü óðàâíåíèÿ(12.1) íà [a, b].
Ïîëîæèì a0 = a, b0 = b, íàéäåì ñåðåäèíó îòðåçêà [a0 , b0 ]x0 =a0 + b02è ïðèìåì ýòó âåëè÷èíó çà ïðèáëèæåííîå çíà÷åíèå x∗ . Òàê êàê ïîëîæåíèå êîðíÿ x∗íà îòðåçêå [a0 , b0 ] íåèçâåñòíî, òî ìîæíî ëèøü óòâåðæäàòü, ÷òî ïîãðåøíîñòü ýòîãîïðèáëèæåíèÿ íå ïðåâîñõîäèò ïîëîâèíû äëèíû [a0 , b0 ]:|x0 − x∗ | 6b0 − a 0.2x0ua0x∗b0Ðèñ. 1Âû÷èñëèì f (x0 ). Åñëè f (x0 ) = 0, òî x∗ = x0 , è âû÷èñëåíèÿ íà ýòîì çàêàí÷èâàþòñÿ.Åñëè f (x0 ) 6= 0, òî çíàê f (x0 ) ñîâïàäàåò ëèáî ñî çíàêîì f (a0 ), ëèáî ñî çíàêîì f (b0 ).Ïóñòü äëÿ îïðåäåëåííîñòè f (a0 ) < 0, f (b0 ) > 0.
Èç äâóõ îòðåçêîâ [a0 , x0 ] è [x0 , b0 ] âûáåðåì òîò, íà êîíöàõ êîòîðîãî f (x) ïðèíèìàåò çíà÷åíèÿ ñ ïðîòèâîïîëîæíûìè çíàêàìè.Îáîçíà÷èì ýòîò îòðåçîê ÷åðåç [a1 , b1 ], ãäåa1 = a0 ,b 1 = x0ïðèf (x0 ) > 0a 1 = x0 ,b 1 = b0ïðèf (x0 ) < 0.è12.2. ÌÅÒÎÄ ÏÐÎÑÒÛÕ ÈÒÅÐÀÖÈÉ121Îòðåçîê [a1 , b1 ] èìååò âäâîå ìåíüøóþ äëèíó, ÷åì [a0 , b0 ], f (a1 )f (b1 ) < 0 è x∗ ∈ (a1 , b1 ),0ïðè÷åì |x0 − x∗ | 6 b0 −a. Íàéäåì ñåðåäèíó îòðåçêà [a1 , b1 ] è ò.ä. Ïóñòü2xk =ak + bk,2k = 1, 2, . . . ,è âñåãäàbk − a kb−a= k+1 .22Ïðîöåññ äåëåíèÿ îòðåçêà ïîïîëàì ïðîäîëæàåòñÿ äî òåõ ïîð, ïîêà äëèíà íîâîãî îòðåçêà [ak , bk ] íå ñòàíåò ìåíüøå 2ε, ãäå ε òðåáóåìàÿ òî÷íîñòü â îïðåäåëåíèè ïðèáëèæåííîãî çíà÷åíèÿ êîðíÿ.
Òîãäà|xk − x∗ | 6xk = xe,|ex − x∗ | 6 ε,ò.å. èçëîæåííûé ìåòîä ïîçâîëÿåò íàéòè ïðèáëèæåííîå ðåøåíèå ñ ãàðàíòèðîâàííîéòî÷íîñòüþ. Ñêîðîñòü ñõîäèìîñòè ìåòîäà íå íèæå ñêîðîñòè ñõîäèìîñòè ê íóëþ ãåîìåòðè÷åñêîé ïðîãðåññèè ñî çíàìåíàòåëåì 1/2. Êàæäàÿ èòåðàöèÿ óìåíüøàåò ïîãðåøíîñòüíå ìåíåå, ÷åì â äâà ðàçà.Ïðèìåð 12.1. Äëÿ òîãî, ÷òîáû óìåíüøèòü ïåðâîíà÷àëüíóþ ëîêàëèçàöèþ â 106 ðàç,íóæíî ñäåëàòü 20 èòåðàöèé, èáî 220 = 1048576.12.2 Ìåòîä ïðîñòûõ èòåðàöèé×òîáû ïðèìåíèòü ìåòîä ïðîñòûõ èòåðàöèé äëÿ ðåøåíèÿ íåëèíåéíîãî óðàâíåíèÿ (12.1),íåîáõîäèìî ïðåîáðàçîâàòü ýòî óðàâíåíèå ê ñëåäóþùåìó âèäó:x = ϕ(x).(12.2)Ýòî ìîæíî ñäåëàòü ìíîãèìè ðàçëè÷íûìè ñïîñîáàìè, íåêîòîðûå èç êîòîðûõ áóäóòèçëîæåíû ïîçæå.
Ïóñòü, íàïðèìåð,ϕ(x) = x + τ (x)f (x),(12.3)ãäå τ (x) ïðîèçâîëüíàÿ íåïðåðûâíàÿ çíàêîîïðåäåëåííàÿ ôóíêöèÿ.Âûáèðàÿ íåêîòîðîå íà÷àëüíîå ïðèáëèæåíèå x0 , ïîñòðîèì èòåðàöèîííûé ïðîöåññxk+1 = ϕ(xk ),k = 0, 1, . . . .(12.4)Èòåðàöèîííûé ïðîöåññ (12.4) íàçûâàåòñÿ ìåòîäîì ïðîñòûõ èòåðàöèé.Òåîðåìà 12.1. Ïóñòü x∗ êîðåíü óðàâíåíèÿ (12.2). Òîãäà, åñëè |ϕ0 (x)| 6 q < 1äëÿ x ∈ [x∗ − δ, x∗ + δ], òî ïðè ëþáîì íà÷àëüíîì ïðèáëèæåíèè x0 ∈ [x∗ − δ, x∗ +δ] ìåòîä ïðîñòûõ èòåðàöèé ñõîäèòñÿ ñî ñêîðîñòüþ ãåîìåòðè÷åñ÷êîé ïðîãðåññèè,çíàìåíàòåëåì êîòîðîé ÿâëÿåòñÿ ÷èñëî q . Ïðè ýòîì|xk − x∗ | 6 q k |x0 − x∗ |.122 12.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
