Численные методы. Ионкин (2009) (формат хуже), страница 5

Ñôîðìóëèðóåì ñîîòâåòñâóþùåå óòâåðæäåíèå:Óòâåðæäåíèå. Ïóñòü âûïîëíåíû ñëåäóþùèå ïðåäïîëîæåíèÿ:1. (A) Ìàòðèöà A èìååò áàçèñ èç ñîáñòâåííûõ âåêòîðîâ2. (B)| λλm−1|<1m3. (Ñ)x0 = c1 e1 + c2 e2 + · · · + cm em ,Òîãäàxn → e mãäå(ïî íàïðàâëåíèþ) ïðè{ei }i=mi=1cm 6= 0n → ∞,ãäåem- ñîáñòâåííûéâåêòîð, îòâå÷àþùèé íàèáîëüøåìó ïî ìîäóëþ ñîáñòâåííîìó çíà÷åíèþn (i)x(n)λm−1λm , à λm = n+1.(i) = λm + OλmxnÇàìå÷àíèå. Óñëîâèÿ (A) è (B) íåñêîëüêî îãðàíè÷èâàþò êëàññ çàäà÷, êêîòîðûì ïðèìåíèì ýòîò ìåòîä, õîòÿ îí âñå ðàâíî îñòàåòñÿ äîñòàòî÷íî øèðîêèì.(n)Çàìå÷àíèå.

Íàéòè λm ìîæíî òàêæå ïî ôîðìóëå:λ(n)m =(Axn , xn )(xn+1 , xn )=(xn , xn )(xn , xn ).Ðàññìîòðèì äâà ñëó÷àÿ:i=m∗1. Ïóñòü A = A . Òîãäà ∃ {ei }i=1 - îðòîíîðìèðîâàííûé áàçèñ èç ñîáñòâåííûõ âåêòîðîâ ìàòðèöû A:Aek = λk ek ,k = 1, . . . , m,ek 6= 0(ei , ej ) = δijxn+1 = c1 λn+1e1 + c2 λn+1e2 + · · · + cm λn+112m emxn = c1 λn1 e1 + c2 λn2 e2 + · · · + cm λnm emÌåòîäû ðåøåíèÿ çàäà÷ íà ñîáñòâåííûå çíà÷åíèÿÍàéäåì(n)λm41:(xn+1 , xn )c2 λ2n+1 + c2 λ2n+1 + · · · + c2m λ2n+1m== 1 1 2 2n 2 2 2 2n22n(xn , xn )c1 λ1 + c2 λ2 + · · · + cm λm2 2n+1 2 2n+1 cm−1λm−1λ12 2n+1cm λm1 + cm+ · · · + ccm1λmλm==2 2n 2 2n λm−1cm−1λ1c122ncm λm 1 + cm+ · · · + cmλmλmλ(n)m == λm + Oλm−1λm2n !∗Òàêèì îáðàçîì, ïðè A = A ïîëó÷èëè áîëåå áûñòðóþ ñõîäèìîñòü.i=m2. Ïóñòü ∃ {ei }i=1 - áàçèñ èç ñîáñòâåííûõ âåêòîðîâ (îðòîíîðìèðîâàííîñòü íå ïðåäïîëàãàåòñÿ).

Òîãäà:mPλ(n)m =(xn+1 , xn )=(xn , xn )ci cj λn+1λnj (ei , ej )ii,j=1mP=ci cj λni λnj(ei , ej )i,j=1(em , em ) 1 +c2m λ2nm (em , em ) 1 +c2m λ2n+1m=cm−1 (em ,em−1 )cm(em ,em )λm−1λmcm−1 (em ,em−1 )cm(em ,em )λm−1λmnn+ ··· +c1cm+ ··· +c1cm22(e1 ,e1 )(em ,em )λ1λm(e1 ,e1 )(em ,em )λ1λm2n+1 2n n λm−1= λm + Oλmn λm−1(n)λm − λm = OλmÌåòîä îáðàòíûõ èòåðàöèéÏóñòü ìàòðèöàA(m x m) òàêîâà, ÷òî∃A−1 .Ðàññìîòðèì èòåðàöèîí-íûé ñòåïåííîé ìåòîä ðåøåíèÿ ÷àñòè÷íîé ïðîáëåìû ñîáñòâåííûõ çíà÷åíèé:Axn+1 = xn ,n = 0, 1, . . . ,x0 çàäàí.=Ìåòîäû ðåøåíèÿ çàäà÷ íà ñîáñòâåííûå çíà÷åíèÿÄîìíîæèì îáå ÷àñòè ñëåâà íàxn+1 = A−1 xn ,42A−1 :n = 0, 1, .

. . ,x0 çàäàí.Ïîëó÷èëè ñòåïåííîé ìåòîä äëÿ îáðàòíîé ìàòðèöû. Ïóñòü âåðíû ñëåäóþùèå ïðåäïîëîæåíèÿ:1. (A) Ìàòðèöà A èìååò áàçèñ èç ñîáñòâåííûõ âåêòîðîâ2. (B)| λλ12 | < 13. (Ñ)x 0 = c1 e 1 + c2 e 2 + · · · + cm e m ,ãäåi=m{ei }i=1c1 6= 0Òîãäà:−n−nxn = c1 λ−n1 e1 + c2 λ2 e2 + · · · + cm λm em n nλ1λ1ne 2 + · · · + cmemλ1 xn = c1 e1 + c2λ2λmÒàêèì îáðàçîì,xn → e1(ïî íàïðàâëåíèþ) ïðèn → ∞.Çàäà÷à. Ïóñòü âûïîëíåíû óñëîâèÿ (A), (B) è (C).

Òîãäà ìåòîä îáðàòíûõ èòåðàöèé ïîçâîëÿåò íàéòè ñîáñòâåííîå çíà÷åíèå n (i)(n)xnO λλ21, ãäå λ1 = (i).x(n)λ1= λ1 +n+1Äîêàçàòåëüñòâî. Âûïèøåì âûðàæåíèÿ äëÿ(i)xnè(i)xn+1 :−n−nxn = c1 λ−n1 e1 + c2 λ2 e2 + · · · + cm λm emxn+1 = c1 λ−n−1e1 + c2 λ−n−1e2 + · · · + cm λ−n−1em12m(i)xn(i)xn+1(i)xn(i)xn+1 :−n −n (i) (i)e−n (i)c2 e2λ2λmc1 λ1 e1 1 + c1 (i) λ1+ · · · + ccm1 m(i)λ1e1e1=−n−1 =−n−1(i)(i)ee−n−1 (i)λmc1 λ1e1 1 + cc21 2(i) λλ21+ · · · + ccm1 m(i)λ1Òåïåðü ïîäåëèìíàe1e1= λ1 + Oλ1λ2n (n)= λ1Ìåòîäû ðåøåíèÿ çàäà÷ íà ñîáñòâåííûå çíà÷åíèÿÏóñòü òåïåðüA = A∗ .Òîãäà43i=m∃ {ei }i=1- îðòîíîðìèðîâàííûé áàçèñ èç(n)ñîáñòâåííûõ âåêòîðîâ ìàòðèöû A. Íàéäåì λ1 :−2n(xn , xn )c21 λ−2n+ c22 λ−2n+ · · · + c2m λm12== 2 −2n+1(xn+1 , xn )+ c22 λ2−2n−1 + · · · + c2m λ−2n−1c1 λ 1m 2 −2n 2 −2n c2λ2λm2 −2nc1 λ11 + c1+ · · · + ccm1λ1λ1= 2 −2n−1 2 −2n−1 =c2λ2λm2 −2n−11 + c1c1 λ1+ · · · + ccm1λ1λ1λ(n)m == λ1 + OÒàêèì îáðàçîì, ïðèA = A∗λ1λ22n !ñíîâà èìååì áîëåå áûñòðóþ ñõîäèìîñòü.i=mÇàäà÷à.

Ïóñòü ∃ {ei }i=1 - áàçèñ èç ñîáñòâåííûõ âåêòîðîâ ìàòðèöû A.Òîãäà(n)λ1 = λ1 + O n λ1λ2.Äîêàçàòåëüñòâî.mP(n)λ1 =−nci cj λ−ni λj (ei , ej )(xn , xn )i,j=1= P=m(xn+1 , xn )−nci cj λ−n−1λ(e,e)i jiji,j=1(e1 , e1 ) 1 +=2 −2n−1(e1 , e1 ) 1 +c1 λ1c21 λ−2n1c2 (e1 ,e2 )c1 (e1 ,e1 )c2 (e1 ,e2 )c1 (e1 ,e1 ) −nλ2λ1 −nλ2λ1+ ··· +cmc1+ ··· +cmc1= λ1 + O(n)λ1− λ1 = Oλ1λ2n λ1λ2Ñôîðìóëèðóåì åùå îäíî óòâåðæäåíèå:n 22(em ,em )(e1 ,e1 )λmλ1(em ,em )(e1 ,e1 )λmλ1−2n −2n−1 =Ìåòîäû ðåøåíèÿ çàäà÷ íà ñîáñòâåííûå çíà÷åíèÿ44Óòâåðæäåíèå. Åñëè åñòü õîòÿ áû îäíî êîìïëåêñíîå ñîáñòâåííîå çíà÷åíèåλk = λ0 + iλ1 , λ1 6= 0,òî è îòâå÷àþùèé åìó ñîáñòâåííûé âåêòîðäîëæåí áûòü êîìïëåêñíûì, è íà÷àëüíîå ïðèáëèæåíèå äëÿ íåãî äîëæíîáûòü êîìïëåêñíûì.Äîêàçàòåëüñòâî. Ïóñòüxk = µ0 + iµ1 , µ1 6= 0ìàòðèöû A, îòâå÷àþùèé ñîáñòâåííîìó çíà÷åíèþ- ñîáñòâåííûé âåêòîðλk = λ0 + iλ1 .Òîãäà:Axk = A(µ0 + iµ1 ) = (λ0 + iλ1 )(µ0 + iµ1 ) = λ0 µ0 − λ1 µ1 + i(λ0 µ1 + λ1 µ0 ) ñèëó ëèíåéíîñòè:Aµ0 = λ0 µ0 − λ1 µ1Aµ1 = λ0 µ1 + λ1 µ0Ïðåäïîëîæèì, ÷òîxk = 0,µ1 = 0.Òîãäàλ1 µ0 = 0, µ0 = 0,îòêóäà ñëåäóåò, ÷òîà ýòî ïðîòèâîðå÷èò òîìó, ÷òî x - íåíóëåâîé âåêòîð.Ìåòîä îáðàòíûõ èòåðàöèé ñî ñäâèãîìÈíîãäà áûâàåò íóæíî íàéòè ñîáñòâåííîå çíà÷åíèå èç âíóòðåííåé ÷àñòè ñïåêòðà.

Ðàññìîòðèì ìåòîä îáðàòíûõ èòåðàöèé ñî ñäâèãîì:(A − αE)xn+1 = xn , α ∈ R, n ∈ Nn = 0, 1, . . . ,Ïóñòü ñóùåñòâóåò(A − αE)−1 = B ,x0 çàäàí.òîãäà ïîëó÷èì ñòåïåííîé ìåòîä äëÿìàòðèöû B:xn+1 = Bxn ,n = 0, 1, . . . ,x0 çàäàí.Ñîáñòâåííûå çíà÷åíèÿ ìàòðèöû B:λBk =Òîãäàxn → e lλAk1−α(ïî íàïðàâëåíèþ), ãäå l òàêîâî, ÷òî:λBl = maxk=1,...,m λAk11= A−αλl − αÇàìå÷àíèå. Åñëè èçâåñòíî ïðèáëèæåííîå çíà÷åíèå êàêîãî-òî ñîáñòâåííîãî çíà÷åíèÿ, à ìû õîòèì åãî óòî÷íèòü, òî ìîæíî èñïîëüçîâàòüýòîò ìåòîä. Íàéòè âåñü ñïåêòð ýòèì ìåòîäîì ïðàêòè÷åñêè íåâîçìîæíî.Ïðèâåäåíèå ìàòðèöû ê âåðõíåé ïî÷òè òðåóãîëüíîé ôîðìå (ÂÏÒÔ) 45Ÿ10Ïðèâåäåíèå ìàòðèöû ê âåðõíåé ïî÷òè òðåóãîëüíîé ôîðìå (ÂÏÒÔ)Ëåã÷å âñåãî íàéòè ñîáñòâåííûå çíà÷åíèÿ ó äèàãîíàëüíîé èëè òðåóãîëüíîé ìàòðèöû. Íàøà çàäà÷à - ïðèâåñòè ìàòðèöó A (m x m) ê òðåóãîëüíîé.

Îäíàêî, ïðèâåäåíèå ìàòðèöû A ê òðåóãîëüíîé ôîðìå ìåòîäîìÃàóññà íå ñîõðàíÿåò ñïåêòð ìàòðèöû. Ñïåêòð ìàòðèöû ñîõðàíÿåòñÿ ïðèïðåîáðàçîâàíèè ïîäîáèÿ:C = Q−1 AQÅñëè ìàòðèöà Q - îðòîãîíàëüíà (óíèòàðíà), òî ñîõðàíÿåòñÿ ñèììåòðèÿ.Îïðåäåëåíèå. Ìàòðèöà íàõîäèòñÿ â âåðõíåé ïî÷òè òðåóãîëüíîé ôîðìå (ÂÏÒÔ), åñëè îíà èìååò âèä (íåíóëåâûå ýëåìåíòû îáîçíà÷åíû ÷åðåçx):xx0A =  ...00x x ···x x ···x x ···.........0 0 ···0 0 ···Ðàññìîòðèì âåêòîð-ñòîëáåöx x xx x xx x x...... ...x x x0 x xν:ν = (ν1 , ν2 , . .

. , νm )Tν T = (ν1 , ν2 , . . . , νm )Îïðåäåëåíèå. Ýëåìåíòàðíûì îòðàæåíèåì, ñîîòâåòñòâóþùèì âåêòîðóν,íàçûâàåòñÿ ïðåîáðàçîâàíèå, çàäàâàåìîå ìàòðèöåé:H =E−2νν T||ν||2Çàìå÷àíèå.2ν T ν = ν12 + ν22 + · · · + νm= ||ν||2ν12ν1 ν2 · · · ν1 νm ν2 ν1ν22 · · · ν2 νm Tνν =  ...... .. .... 2νm ν1 νm ν2 · · · νmÌàòðèöàνν T- ñèììåòðè÷íàÿ.Ïðèâåäåíèå ìàòðèöû ê âåðõíåé ïî÷òè òðåóãîëüíîé ôîðìå (ÂÏÒÔ) 46Ñâîéñòâà îïåðàòîðà H:1.HT = H2.H −1 = H THÄîêàæåì âòîðîå ñâîéñòâî, òî åñòü ÷òîÿâëÿåòñÿ îðòîãîíàëüíîé ìàò-ðèöåé.Äîêàçàòåëüñòâî.VVtVVtH H =H = E−2E−2=||V ||2||V ||2T2E−4Èñïîëüçóÿ ñâîéñòâîVVTV (V T V )V T+4||V ||2||V ||4V T V = ||V ||2 , ñîêðàòèì â ïîñëåäíåì ñîîòíîøåíèèäðîáè è ïîëó÷èì, ÷òîHT H = EÇíà÷èò, ìàòðèöà H ÿâëÿåòñÿ îðòîãîíàëüíîé.Ñôîðìóëèðóåì è äîêàæåì ñâîéñòâî 3.Òåîðåìà.

Äëÿ ëþáîãî âåêòîðà x: x1 x=ìîæíî âûáðàòü òàêîé âåêòîðx2x3...xmV = (v1 , v2 , . . . , vm ), −σ Hx = ãäåσ = ||x||,00...0÷òîòî åñòü ïðåîáðàçîâàíèå H ïîäàâëÿåò âñå êîîðäèíàòûâåêòîðà êðîìå ïåðâîé.Ïðèâåäåíèå ìàòðèöû ê âåðõíåé ïî÷òè òðåóãîëüíîé ôîðìå (ÂÏÒÔ) 47Äîêàçàòåëüñòâî. ÂûáåðåìVâ âèäå:V = x + σz, σ ∈ R, z = (1, 0, 0, . . . , 0)THx = x − 2(x + σz)(x + σz)Tx=(x + σz)T (x + σz)x − (x + σz)2(x + σz)T x(x + σz)T (x + σz)Äëÿ äàëüíåéøåãî ïðåîáðàçîâàíèÿ âîñïîëüçóåìñÿ ñâîéñòâàìè 1 è 2 :(x + σz)T x = ||x||2 + σx1(x + σz)T (x + σz) = ||x||2 + σx1 + σx1 + σ 2 =||x||2 + 2σx1 + σ 2Ïîëîæèìσ = ||x||.Òîãäà ïîëó÷èì:x − (x + σz)2x − (x + σz)2(x + σz)T x=(x + σz)T (x + σz)22 −σ 2(||x|| + 2σx1 + σ ) + ||x|| − σ= x − x − σz = ||x||2 + 2σx1 + σ 200...0Ïîëó÷åííûå 3 ñâîéñòâà ìû áóäåì ïðèìåíÿòü ïðè ïðèâåäåíèè ìàòðèöû ê âåðõíåé ïî÷òè òðåóãîëüíîé ôîðìå.Ïóñòü äàíà ïðîèçâîëüíàÿ ìàòðèöàAm × m:ïîðÿäêàa11 a12 .

. . a1m a21 a22 . . . a2m A=. . . . . . . . . . . . . . . . . . .am1 am2 . . . ammÏðåäñòàâèì åå â âèäå áëî÷íîé ìàòðèöû ñëåäóþùåãî âèäà:Ïðèâåäåíèå ìàòðèöû ê âåðõíåé ïî÷òè òðåóãîëüíîé ôîðìå (ÂÏÒÔ) 48A=a11 ym−1xm−1 Am−1ãäåym−1 = (a12 , a13 , . . . , a1m )xm−1 = (a21 , a31 , . . . , am1 )à ìàòðèöàAm−1ïîëó÷àåòñÿ èç ìàòðèöûAóäàëåíèåì ïåðâîãî ñòîëáöà èïåðâîé ñòðîêè.Âîñïîëüçóåìñÿ ñâîéñòâîì 3:−||xm−1 ||0=...0Hm−1 xm−1Ðàññìîòðèì ìàòðèöóU1ïîðÿäêàm×mU1 =1012021 Hm−1âèäà:U1 = U1T , çíà÷èò: 1012101210122U1 ===E2021 Hm−1021 Hm−1021 Hm−1Î÷åâèäíî,Ïîñëåäíåå ðàâåíñòâî âåðíî â ñèëó òîãî, ÷òîìû ïîëó÷èëè ÷òî ìàòðèöà−1Îáîçíà÷èì C1 = U1 AU1U12Hm−1= E Òàêèì îáðàçîì,- îðòîãîíàëüíàÿ.a11−σ1 zm−10C1 = ...0(1)c12 .

. .(2)c22 . . . (1)(1) c32 cij .... . .(1)cm2 . . .Ïðèâåäåíèå ìàòðèöû ê âåðõíåé ïî÷òè òðåóãîëüíîé ôîðìå (ÂÏÒÔ) 49Òàêèì îáðàçîì, ñòðóêòóðó ìàòðèöû ìîæíî ïðåäñòàâèòü òàê:××××.........× ... ×××00 ...0Âîçüìåì âåêòîðxm−2 = ××××(1)c32.............

. .(1)cm2Ïî ñâîéñòâó 3, ìîæíî ïîñòðîèòü òàêîé îïåðàòîðHm−2 ,÷òî:Hm−2 xm−2Ðàññìîòðèì ìàòðèöóU2 ,ïîñòðîåííóþ àíàëîãè÷íî ìàòðèöåU2 =ãäåE2 =1 00 1U2 = U2T2.U2 = U2−1E2012021 Hm−2Ñâîéñòâà ìàòðèöû1.−||xm−2 ||00=...0U2 :- îðòîãîíàëüíàÿ ìàòðèöàÀíàëîãè÷íî, îáîçíà÷èìC2 :C2 = U2−1 C1 U2 = U2−1 U1−1 AU1 U2U1Ïðèâåäåíèå ìàòðèöû ê âåðõíåé ïî÷òè òðåóãîëüíîé ôîðìå (ÂÏÒÔ) 50Ïîñìîòðèì íà ñòðóêòóðó ìàòðèöû××0C2 =  0 ...0C2 :××××............0 × ...

××××0××××............Î÷åâèäíî, ÷òî ñäåëàâ òàêèì îáðàçîì m-2 øàãà, ìû ïðèäåì ê âåðõíåéïî÷òè òðåóãîëüíîé ôîðìå.  èòîãå ìû ïîëó÷èì:−1−1C = Um−2Um−3. . . U2−1 U1−1 AU1 U2 . . . Um−3 Um−2 =××0= 0 ...0Îáîçíà÷èì×××0××××....................00×.××××...×-ÂÏÒÔU = U1 U2 . .