В.Б. Андреев - Численные методы (1113834), страница 14
Текст из файла (страница 14)
Ïðåäïîëîæèì, ÷òîc1 6= 0(11.6)è âû÷èñëèì ïîñëåäîâàòåëüíî âåêòîðûxk = Axk−1 ,k = 1, 2, . . . .Òîãäà ñîãëàñíî (11.5), (11.2)x1 = Ax0 = A(c1 ξ1 + c2 ξ2 + · · · + cn ξn ) == c1 λ1 ξ1 + c2 λ2 ξ2 + · · · + cn λn ξn(11.7)108 11. ÏÐÎÁËÅÌÀ ÑÎÁÑÒÂÅÍÍÛÕ ÇÍÀ×ÅÍÈÉè âîîáùåxk = c1 λk1 ξ1 + c2 λk2 ξ2 + · · · + cn λkn ξn = λk1 (c1 ξ1 + η k ),(11.8)ãäåη k = c2 (λ2 /λ1 )k ξ2 + c3 (λ3 /λ1 )k ξ3 + · · · + cn (λn /λ1 )k ξn .Âû÷èñëÿÿ íîðìó η k , ñ ó÷åòîì (11.3), (11.4) íàõîäèì, ÷òîkkη k2 6nXk|cj | |λj /λ1 | |kξj k2 6 |λ2 /λ1 |kj=2nX|cj | =j=2(11.9)k= O(|λ2 /λ1 | ) → 0 ïðè k → ∞.Ñ ó÷åòîì (11.8) âû÷èñëèì ñêàëÿðíûå ïðîèçâåäåíèÿ¡¢(xk , xk+1 ) = λ2k+1c1 ξ1 + η k , c1 ξ1 + η k+1 =1£ 2¤= λ2k+1c1 (ξ1 , ξ1 ) + c1 (ξ1 , η k+1 ) + c1 (η k , ξ1 ) + (η k , η k+1 ) .1Îöåíèâàÿ, íàõîäèì, ÷òî|(ξ1 , η k+1 )| 6 kξ1 k kη k+1 k = kη k+1 k|(η k , ξ1 )| 6 kη k k,|(η k , η k+1 )| 6 kη k k kη k+1 kè ñ ó÷åòîì (11.9)(xk , xk+1 ) = λ2k+1(c21 + O(|λ2 /λ1 |k )).1Àíàëîãè÷íî2k(xk , xk ) = λ2k1 (c1 + O(|λ2 /λ1 | ))è, ñëåäîâàòåëüíî,(k)λ1 :=Èç (11.10)(xk+1 , xk )= λ1 + O(|λ2 /λ1 |k−1 ).(xk , xk )(11.10)(11.11)¡¢kxk k = |λ1 |k |c1 | + O(|λ2 /λ1 |k ) ,à ñ ó÷åòîì (11.8)ξ k :=xk= ±ξ1 + rk ,kxk k(11.12)ãäåkrk k = O(|λ2 /λ1 |k ).Òàêèì îáðàçîì, èòåðàöèîííûé ïðîöåññ (11.7), (11.11), (11.12) ïîçâîëÿåò íàéòè ñëþáîé òî÷íîñòüþ îäíîêðàòíîå ìàêñèìàëüíîå ïî ìîäóëþ ñîáñòâåííîå çíà÷åíèå (11.11)è îòâå÷àþùèé åìó ñîáñòâåííûé âåêòîð (11.12), åñëè âûïîëíåíî óñëîâèå (11.6).11.2.
ÑÒÅÏÅÍÍÎÉ ÌÅÒÎÄ ÐÅØÅÍÈß ×ÀÑÒÍÛÕ ÏÐÎÁËÅÌ109Çàìå÷àíèå 11.1. Åñëè |λ1 | > 1, òî kxk k → ∞ ïðè k → ∞, à åñëè |λ1 | < 1, òîkxk k → 0. È òî, è äðóãîå ÿâëåíèå íåæåëàòåëüíû ïðè âû÷èñëåíèÿõ íà êîìïüþòåðå. ïåðâîì ñëó÷àå ìîæåò ïðîèçîéòè ïåðåïîëíåíèå, à âî âòîðîì ñëó÷àå xk ìîæåò ñòàòüìàøèííûì íóëåì. Ïîýòîìó âìåñòî (11.7) èòåðàöèè íóæíî âåñòè ïî ôîðìóëàìξ10 = x0 /kx0 k,(k)xk+1 = Aξ1k ,λ1 = (xk+1 , ξ1k ) = (Aξ1k , ξ1k ),(11.13)ξ1k+1 = xk+1 /kxk+1 k.Çàìå÷àíèå 11.2. Åñëè óñëîâèå (11.6) íå âûïîëíåíî (àïðèîðè ïðîâåðèòü ýòî óñëî-âèå íåëüçÿ), òî ýòî åùå íå çíà÷èò, ÷òî èòåðàöèîííûé ïðîöåññ (11.7) (èëè (11.13)) ñíà÷àëüíûì ïðèáëèæåíèåì (11.5) íå ïðèâåäåò ê ðåçóëüòàòó.
Ïðè äîñòàòî÷íî áîëüøîì÷èñëå èòåðàöèé çà ñ÷åò îøèáîê îêðóãëåíèÿ ìîæåò ïîÿâèòüñÿ íåíóëåâàÿ êîìïîíåíòàc1 , è èòåðàöèîííûé ïðîöåññ âûéäåò â êîíöå êîíöîâ íà íóæíîå ðåøåíèå. Íî ïðè ýòîìíóæíî èìåòü â âèäó, ÷òî åñëè |λ3 | ¿ |λ2 |, òî èòåðàöèè î÷åíü áûñòðî âûéäóò íà âòîðîåñîáñòâåííîå çíà÷åíèå è âòîðîé ñîáñòâåííûé âåêòîð, è ìîæíî îáìàíóòüñÿ, ïðèíÿâèõ çà èñêîìûå âåëè÷èíû. Ýòî íå òàê âåðîÿòíî, åñëè |λ2 | è |λ3 | íå ñëèøêîì ñèëüíîðàçëè÷àþòñÿ, à òðåáóåìàÿ òî÷íîñòü äîñòàòî÷íî âåëèêà.
Èòåðàöèè â ýòîì ñëó÷àå áóäóòñõîäèòüñÿ äîñòàòî÷íî ìåäëåííî, è èõ ïîòðåáóåòñÿ ìíîãî äëÿ ïîëó÷åíèÿ òðåáóåìîéòî÷íîñòè. Çà ýòî âðåìÿ ïîãðåøíîñòè îêðóãëåíèÿ íàêîïÿòñÿ, è ìîæåò ñôîðìèðîâàòüñÿíîâàÿ òî÷êà ïðèòÿæåíèÿ èòåðàöèîííîãî ïðîöåññà (λ1 , ξ1 ). Åñëè íåò óâåðåííîñòèâ ïðàâèëüíîñòè íàéäåííîãî ñîáñòâåííîãî çíà÷åíèÿ, ñëåäóåò ïðîâåñòè åùå îäèí èëèíåñêîëüêî ðàñ÷åòîâ ñ äðóãèìè íà÷àëüíûìè ïðèáëèæåíèÿìè.Çàìå÷àíèå 11.3.
1) Ïîäòâåðæäåíèåì òîãî, ÷òî λ1 íå ÿâëÿåòñÿ êðàòíûì ñîáñòâåííûìçíà÷åíèåì, è ÷òî íåò ñîáñòâåííîãî çíà÷åíèÿ (−λ1 ), ñëóæèò ñõîäèìîñòü èòåðàöèîííîãîïðîöåññà ê îäíîìó è òîìó æå ñîáñòâåííîìó âåêòîðó (ñ òî÷íîñòüþ äî çíàêà) ïðèðàçëè÷íûõ íà÷àëüíûõ ïðèáëèæåíèÿõ.(k)2) Åñëè ïðè ðàçëè÷íûõ íà÷àëüíûõ âåêòîðàõ x0 çíà÷åíèÿ λ1 ñõîäÿòñÿ ê îäíîìó(k)è òîìó æå ÷èñëó, à ïîñëåäîâàòåëüíîñòè âåêòîðîâ ξ1 ïðèâîäÿò ê íåêîëëèíåàðíûìâåêòîðàì, òî ýòî îáñòîÿòåëüñòâî ñëóæèò ïîäòâåðæäåíèåì òîãî, ÷òî ìàêñèìàëüíîå ïîìîäóëþ ñîáñòâåííîå çíà÷åíèå ÿâëÿåòñÿ êðàòíûì. Åñëè òðåáóåòñÿ íàéòè ñîáñòâåííîåïîäïðîñòðàíñòâî, èëè íóæíî îïðåäåëèòü êðàòíîñòü íàéäåííîãî ñîáñòâåííîãî çíà÷åíèÿ, íóæíî ïðîâîäèòü âû÷èñëåíèÿ ñ ðàçëè÷íûìè íà÷àëüíûìè ïðèáëèæåíèÿìè äî òåõïîð, ïîêà ïåðåñòàíóò ïîëó÷àòüñÿ âåêòîðû, ëèíåéíî-íåçàâèñèìûå ñ óæå íàéäåííûìè.(k)(2k+1)(2k)3) Åñëè çíà÷åíèÿ λ1 íå ñõîäÿòñÿ ïðè k → ∞, îäíàêî λ1è λ1 ñõîäÿòñÿ, íîê ðàçíûì ÷èñëàì, òî ýòî ñâèäåòåëüñòâóåò î íàëè÷èè äâóõ ìàêñèìàëüíûõ ïî ìîäóëþñîáñòâåííûõ çíà÷åíèÿõ, çíàêè êîòîðûõ ðàçëè÷íû.
 ýòîì ñëó÷àå öåëåñîîáðàçíî ïðîèçâåñòè "ñäâèã ñïåêòðà"ïóòåì ïðîâåäåíèÿ èòåðàöèé (11.7) ñ ìàòðèöåé A0 = A + cI , ãäåc çàäàííîå ÷èñëî.110 11. ÏÐÎÁËÅÌÀ ÑÎÁÑÒÂÅÍÍÛÕ ÇÍÀ×ÅÍÈÉ11.2.2 Íàõîæäåíèå âòîðîãî ïî âåëè÷èíå ìîäóëÿ ñîáñòâåííîãîçíà÷åíèÿÏóñòü|λ1 | > |λ2 | > |λ3 | > · · · > |λn |.Áóäåì ñ÷èòàòü, ÷òî λ1 , ξ1 è η1 (AT η1 = λ1 η1 ) èçâåñòíû, ïðè÷åì kξ1 k = 1, (η1 , ξ1 ) = 1.Íàéòè λ1 , ξ1 è η1 ìîæíî îïèñàííûì âûøå ñïîñîáîì.
Ïóñòü x0 ïðîèçâîëüíûé âåêòîð,òàêîé, ÷òî (x0 , η2 ) 6= 0. Òîãäàx0 = c1 ξ1 + c2 ξ2 + · · · + cn ξn ,c1 = (x0 , η1 ),c2 6= 0.Ïîñòðîèì âåêòîðy 0 = x0 − (x0 , η1 )ξ1 = c2 ξ2 + c3 ξ3 + · · · + cn ξnè âåêòîðξ20 = y 0 /ky 0 k.Èòåðàöèîííûé ïðîöåññ áóäåì îñóùåñòâëÿòü ïî ôîðìóëàìxk+1 = Aξ2k ,(k)λ2 = (xk+1 , ξ2k ),y k+1 = xk+1 − (xk+1 , η1 )ξ1 ,Òîãäàξ2k+1 = y k+1 /ky k+1 k.(k)λ2 = λ2 + O(|λ3 /λ2 |k ),ξ2k = ±ξ2 + O(|λ3 /λ2 |k ).11.2.3 Íàõîæäåíèå max λi (A) è min λi (A)16i6n16i6nà) Íàéäåì ìàêñèìàëüíîå ïî ìîäóëþ ñîáñòâåííîå çíà÷åíèå ïî îïèñàííîé âûøå ìåòîäèêå. Ïóñòü ýòî λ̄(A)|λ̄(A)| = max |λi (A)|.iÅñëè λ̄(A) > 0, òî íàéäåííîå ìàêñèìàëüíîå ïî ìîäóëþ ñîáñòâåííîå çíà÷åíèå λ̄(A)áóäåò èñêîìûì ìàêñèìàëüíûì çíà÷åíèåìmax λi (A) = λ̄(A)iá) Íàéäåì λ̄i (B): |λ̄(B)| = max |λi (B)|, ãäåiB = A − λ̄(A)I.Ïðè ýòîìλi (B) = λi (A) − λ̄(A) 6 0.(11.14)11.3.
ÌÅÒÎÄ ÎÁÐÀÒÍÛÕ ÈÒÅÐÀÖÈÉ111Ïîýòîìó ìàêñèìàëüíîå ïî ìîäóëþ ñîáñòâåííîå çíà÷åíèå ìàòðèöû B åñòü ìèíèìàëüíîåñîáñòâåííîå çíà÷åíèå ýòîé ìàòðèöûλ̄(B) = min [λi (A) − λ̄(A)] = min λi (A) − λ̄(A),iiò.å.min λi (A) = λ̄(A) + λ̄(B).i(11.15)Åñëè æå λ̄(A) < 0, òî âñå íàîáîðîò.11.3 Ìåòîä îáðàòíûõ èòåðàöèéÅñëè ìàòðèöà A íåâûðîæäåíà, òî óðàâíåíèå (11.1) ìîæíî ïåðåïèñàòü â âèäå1ξ(11.16)λè äëÿ îòûñêàíèÿ íàèìåíüøåãî ïî ìîäóëþ ñîáñòâåííîãî çíà÷åíèÿ ìàòðèöû A èñïîëüçîâàòü ïðèáëèæåíèå ê íàèáîëüøåìó ïî ìîäóëþ çíà÷åíèþ ìàòðèöû A−1 .
Èìåííî, ïóñòüA−1 ξ =x0 = c1 ξ1 + c2 ξ2 + · · · + cn ξn , cn 6= 0,|λ1 | > |λ2 | > · · · > |λn−1 | > |λn |.Òîãäà111>> ··· >,|λn ||λn−1 ||λ1 |x0ξn0 = 0 , xk+1 = A−1 ξnk ,kx k¡ k+1 k ¢1xk+1k+1=x,ξ,ξ=,nnλ(k+1)kxk+1 k(11.17)Ðàçóìååòñÿ, âû÷èñëÿòü A−1 íåò íåîáõîäèìîñòè äîñòàòî÷íî ðåøàòü ñèñòåìûAxk+1 = ξnk(11.18)ñ îäíîé è òîé æå ìàòðèöåé è ðàçëè÷íûìè ïðàâûìè ÷àñòÿìè.Ìåòîä îáðàòíûõ èòåðàöèé ìîæåò áûòü èñïîëüçîâàí è â òîì ñëó÷àå, êîãäà óæåèçâåñòíî ñ íåêîòîðîé òî÷íîñòüþ êàêîå-ëèáî ñîáñòâåííîå çíà÷åíèå, è íóæíî åãî óòî÷íèòü, à òàêæå íàéòè îòâå÷àþùèé åìó ñîáñòâåííûé âåêòîð. Äëÿ ýòîãî íóæíî âìåñòîìàòðèöû 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 .Èòåðàöèè î÷åíü òðóäîåìêèå.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
