В.Б. Андреев - Численные методы (2 в 1). (2007) (1160465), страница 15
Текст из файла (страница 15)
Äëÿ ýòîãî íóæíî âìåñòîìàòðèöû A èñïîëüçîâàòü ìàòðèöóe I,A−λ(11.19)e èçâåñòíîå ïðèáëèæåíèå ê èñêîìîìó ñîáñòâåííîìó çíà÷åíèþ. Åñëè ïðèáëèæåãäå λe I åñòü ñîáñòâåííîå çíà÷åíèå, ïî ìîäóëþíèå äîñòàòî÷íî õîðîøåå, òî ó ìàòðèöû A − λçíà÷èòåëüíî ìåíüøåå îñòàëüíûõ.  ýòîì ñëó÷àå îáðàòíûå èòåðàöèè áûñòðî ñõîäÿòñÿe, à çàîäíî íàõîäèòñÿê ýòîìó ìàëîìó ñîáñòâåííîìó çíà÷åíèþ, ò.å. ê ïîïðàâêå äëÿ λ(èëè óòî÷íÿåòñÿ) ïðèáëèæåííûé ñîáñòâåííûé âåêòîð.112 11. ÏÐÎÁËÅÌÀ ÑÎÁÑÒÂÅÍÍÛÕ ÇÍÀ×ÅÍÈÉ11.4 ÏðèìåðÏðèìåíèì ñòåïåíîé ìåòîä äëÿ îòûñêàíèÿ ìàêñèìàëüíîãî ïî ìîäóëþ ñîáñòâåííîãîçíà÷åíèÿ ìàòðèöû·¸2 1A=−1 0 êà÷åñòâå íà÷àëüíîãî ïðèáëèæåíèÿ âîçüìåì âåêòîð·¸· ¸ · ¸·2 1 01202x ==, x =−1 0 10−1·¸· ¸ · ¸2 123x3 ==,...−1 0 −1−2x0 = [0, 1]T . Òîãäื ¸ · ¸1 12=,0 0−1Î÷åâèäíî, ÷òî xk = [k (−k +1)]T , xk+1 = [(k +1) (−k)]T .
Òîãäà (xk , xk ) = 2k 2 −2k +1,(xk , xk+1 ) = 2k 2 , è, ñëåäîâàòåëüíî,µ ¶2k 211(k+1)λ= 2=1++O.2k (1 − 1/k + O(k −2 ))kk2Ñõîäèìîñòü ê ñîáñòâåííîìó çíà÷åíèþ λ = 1 î÷åíü ìåäëåííà è íå ïîõîæà íà òó,êîòîðóþ ìû èìåëè â 2.2. Âûÿñíèì, ñ ÷åì ýòî ñâÿçàíî. Ðåøàÿ çàäà÷ó íà ñîáñòâåííûå çíà÷åíèÿ, íàõîäèì, ÷òî ðàññìàòðèâàåìàÿ ìàòðèöà èìååò äâóêðàòíîå ñîáñòâåííîåçíà÷åíèå λ = 1, êîòîðîìó îòâå÷àåò åäèíñòâåííûé ñîáñòâåííûé âåêòîð [1, −1]T .
Òåìñàìûì, ýòà ìàòðèöà íå ÿâëÿåòñÿ ìàòðèöåé ïðîñòîé ñòðóêòóðû, êàê ýòî áûëî â 2.2, à ååæîðäàíîâîé ôîðìîé ÿâëÿåòñÿ êëåòêà ïîðÿäêà äâà. Ïðèâåäåííûé ïðèìåð ïîêàçûâàåò,÷òî ñòåïåíîé ìåòîä íå îòêàçûâàåòñÿ ðàáîòàòü è â òîì ñëó÷àå, êîãäà ìàêñèìàëüíîìóïî ìîäóëþ êðàòíîìó ñîáñòâåííîìó çíà÷åíèþ îòâå÷àåò æîðäàíîâà êëåòêà, íî ñêîðîñòüñõîäèìîñòè ðåçêî ïàäàåò îò ñêîðîñòè ñõîäèìîñòè ãåîìåòðè÷åñêîé ïðîãðåññèè ê ñêîðîñòè ñõîäèìîñòè ãàðìîíè÷åñêîãî ðÿäà.11.5Q R - àëãîðèòìÊðàòêî îïèøåì îäèí èç íàèáîëåå óïîòðåáèòåëüíûõ ìåòîäîâ ïðè ðåøåíèè ïîëíîéïðîáëåìû ñîáñòâåííûõ çíà÷åíèé.Ïóñòü ìàòðèöà A ðàçëîæåíà â ïðîèçâåäåíèå îðòîãîíàëüíîé Q ìàòðèöû è âåðõíåéòðåóãîëüíîé ìàòðèöû R, ò.å.A0 = A = QR = Q1 R1 .Ñäåëàòü ýòî ìîæíî, íàïðèìåð, ïðè ïîìîùè ìåòîäà âðàùåíèé èëè ìåòîäà îòðàæåíèé.Ïîñòðîèì ìàòðèöóA1 = R1 Q1 .11.5. Q R - ÀËÃÎÐÈÒÌÏîñêîëüêó113−1A1 = Q−11 Q1 R1 Q1 = Q AQ,(11.20)òî ìàòðèöû A è A1 ïîäîáíû è, ñëåäîâàòåëüíî, èìåþò îäèíàêîâûé íàáîð ñîáñòâåííûõçíà÷åíèé.Äàëåå,A 2 = Q2 R 2 ,A3 = R3 Q3 è ò.ä.Ïðè íåêîòîðûõ îãðàíè÷åíèÿõ íà A ìàòðèöû Ai ïî ôîðìå ñõîäÿòñÿ ê òðåóãîëüíîéìàòðèöå, íà ãëàâíîé äèàãîíàëè êîòîðîé ñòîÿò ñîáñòâåííûå ÷èñëà.
Ïîíèìàòü ýòî íóæíîòàê, ÷òî ïîääèàãîíàëüíûå ýëåìåíòû ñòðåìÿòñÿ ê íóëþ, äèàãîíàëüíûå ê ñîáñòâåííûì÷èñëàì, à íàääèàãîíàëüíûå ìîãóò íèêóäà íå ñòðåìèòüñÿ.(k)Åñëè âñå |λi | ðàçëè÷íû, aij , i > j ñòðåìÿòñÿ ê íóëþ ñî ñêîðîñòüþ ãåîìåòðè÷åñêîéïðîãðåññèè ñî çíàìåíàòåëåì (λi /λj ).Îäíà èòåðàöèÿ O(n3 ). Ìàòðèöà Õåññåíáåðãà ïî÷òè òðåóãîëüíàÿ ìàòðèöà (ïåðâàÿïîääèàãîíàëü îòëè÷íà îò íóëÿ). Îäíà èòåðàöèÿ O(n2 ).Èòåðàöèè ñî ñäâèãîìAk − τk I = Qk Rk ,Ak+1 = Rk Qk + τk I = Q−1k (Ak − τk I)Qk + τk I == Q−1k AQk .Èòåðàöèè î÷åíü òðóäîåìêèå. Ñêîðîñòü ñõîäèìîñòè íèçêàÿ.Îïðåäåëåíèå 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, .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
