Н.И. Ионкин - Электронные лекции (2009) (1135239), страница 5
Текст из файла (страница 5)
,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 − αÇàìå÷àíèå. Åñëè èçâåñòíî ïðèáëèæåííîå çíà÷åíèå êàêîãî-òî ñîáñòâåííîãî çíà÷åíèÿ, à ìû õîòèì åãî óòî÷íèòü, òî ìîæíî èñïîëüçîâàòüýòîò ìåòîä. Íàéòè âåñü ñïåêòð ýòèì ìåòîäîì ïðàêòè÷åñêè íåâîçìîæíî.Ïðèâåäåíèå ìàòðèöû ê âåðõíåé ïî÷òè òðåóãîëüíîé ôîðìå (ÂÏÒÔ) 4510Ïðèâåäåíèå ìàòðèöû ê âåðõíåé ïî÷òè òðåóãîëüíîé ôîðìå (ÂÏÒÔ)Ëåã÷å âñåãî íàéòè ñîáñòâåííûå çíà÷åíèÿ ó äèàãîíàëüíîé èëè òðåóãîëüíîé ìàòðèöû.
Íàøà çàäà÷à - ïðèâåñòè ìàòðèöó A (m x m) ê òðåóãîëüíîé. Îäíàêî, ïðèâåäåíèå ìàòðèöû A ê òðåóãîëüíîé ôîðìå ìåòîäîìÃàóññà íå ñîõðàíÿåò ñïåêòð ìàòðèöû. Ñïåêòð ìàòðèöû ñîõðàíÿåòñÿ ïðèïðåîáðàçîâàíèè ïîäîáèÿ:C = Q−1 AQÅñëè ìàòðèöà Q - îðòîãîíàëüíà (óíèòàðíà), òî ñîõðàíÿåòñÿ ñèììåòðèÿ.Îïðåäåëåíèå. Ìàòðèöà íàõîäèòñÿ â âåðõíåé ïî÷òè òðåóãîëüíîé ôîðìå (ÂÏÒÔ), åñëè îíà èìååò âèä (íåíóëåâûå ýëåìåíòû îáîçíà÷åíû ÷åðåçx):xx0A = ...00x x ···x x ···x x ···.........0 0 ···0 0 ···Ðàññìîòðèì âåêòîð-ñòîëáåöx x xx x xx x x......
...x x x0 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 AU1U12Hm−1= E Òàêèì îáðàçîì,- îðòîãîíàëüíàÿ.a11−σ1 zm−10C1 = ...0(1)c12 .
. .(2)c22 . . . (1)(1) c32 cij .... . .(1)cm2 . . .Ïðèâåäåíèå ìàòðèöû ê âåðõíåé ïî÷òè òðåóãîëüíîé ôîðìå (ÂÏÒÔ) 49Òàêèì îáðàçîì, ñòðóêòóðó ìàòðèöû ìîæíî ïðåäñòàâèòü òàê:××××.........× ... ×××00 ...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 ||00=...0U2 :- îðòîãîíàëüíàÿ ìàòðèöàÀíàëîãè÷íî, îáîçíà÷èìC2 :C2 = U2−1 C1 U2 = U2−1 U1−1 AU1 U2U1Ïðèâåäåíèå ìàòðèöû ê âåðõíåé ïî÷òè òðåóãîëüíîé ôîðìå (ÂÏÒÔ) 50Ïîñìîòðèì íà ñòðóêòóðó ìàòðèöû××0C2 = 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 . . . Um−2TT−1−1U T = Um−2Um−3. . . U2T U1T = Um−2Um−3. . . U2−1 U1−1 = U −1Ñëåäîâàòåëüíî, ìàòðèöà U - îðòîãîíàëüíà.C = U −1 AU ⇒ C ∼ AÏðè÷åì ïîäîáèå âûïîëíÿåòñÿ ñ ïîìîùüþ îðòîãîíàëüíîé ìàòðèöûUÝëåìåíòû ìàòðèöû C èìåþò âèä:cij = 0, i ≥ j + 2, j = 1, 2, . . .
, m − 2Çàìå÷àíèå. Ñîáñòâåííûå çíà÷åíèÿ ìàòðèöû A ñîâïàäàþò ñ ñîáñòâåííûìè çíà÷åíèÿìè ìàòðèöû C, ò.å.:CλAk = λk , k = 1, mÏîíÿòèå î QR-àëãîðèòìå. Ðåøåíèå ïîëíîé ïðîáëåìû ñîáñòâåííûõçíà÷åíèé.51Äîêàçàòåëüñòâî.Ax = λx, x 6= 0U −1 Ax = λU −1 x, îáîçíà÷èìU −1 x = y 6= 0 ⇒ x = U yU−1 AU y = λy, y 6= 0Cy = λyÇàìå÷àíèå. Åñëè A = AT , òî C = C TÄîêàçàòåëüñòâî.C T = (U −1 AU )T = U T AT (U −1 )T = U −1 AU = C11Ïîíÿòèå î QR-àëãîðèòìå.
Ðåøåíèå ïîëíîé ïðîáëåìû ñîáñòâåííûõ çíà÷åíèé.Èçó÷åííûå â ïðåäûäóùåì ïàðàãðàôå ñâîéñòâà ïîçâîëÿò íàì ïðåäñòàâèòü ìàòðèöóAâ âèäå:A = QRãäåQ−1 = QT- îðòîãîíàëüíàÿ ìàòðèöà, à(1)Rèìååò âåðõíåòðåóãîëüíóþôîðìó.x = (a11 , a21 , . . . , am1 ). Äëÿ íåãî ñóùåñòâóåò òàêàÿVVT, êîòîðàÿ ïîäàâëÿåò âñå êîîðîðòîãîíàëüíàÿ ìàòðèöà H1 = E − 2||V ||2äèíàòû âåêòîðà x, êðîìå ïåðâîé.Ìàòðèöà H1 A èìååò âèä:× × ... × 0 × .
. . ×H1 A = 0 × . . . × .. .. . .... ...0 × ... ×1 0Ïîñòðîèì ìàòðèöó H2 = 0 Hïîðÿäêà m × m,òàêóþ, ÷òîÂîçüìåì âåêòîðÏîíÿòèå î QR-àëãîðèòìå. Ðåøåíèå ïîëíîé ïðîáëåìû ñîáñòâåííûõçíà÷åíèé.52×0H2 H1 A = 0 ...0× × ... ×× × . . . ×0 × . . . ×....... ×..0 × ... ×Î÷åâèäíî, ÷òî çà (m-1) øàã ìû îáíóëèì âñå ýëåìåíòû ïîä ãëàâíîéäèàãîíàëüþ:×0...0Hm−1 Hm−2 . . . H2 H1 A = R =××...0............×!×××−ÂÒÔÏîñòðîèì ìàòðèöó Q ñëåäóþùèì îáðàçîì:Q = H1 H2 . . .
Hm−1ÍàéäåìQT :TT−1−1Hm−2. . . H2T H1T = Hm−1Hm−2. . . H1−1 = Q−1QT = Hm−1Ñëåäîâàòåëüíî, ìàòðèöà Q îðòîãîíàëüíà.Òàêèì îáðàçîì, ìû ïîëó÷èëè ðàçëîæåíèå ìàòðèöû A.Çàìå÷àíèå. Ïðè ôàêòîðèçàöèè â âèäå QR:1. Äëÿ ïðîèçâîëüíîé ìàòðèöû2. Äëÿ ìàòðèöûAAòðåáóåòñÿâèäà ÂÏÒÔ òðåáóåòñÿ3. Äëÿ òðåõäèàãîíàëüíîé ìàòðèöûAO(m3 )O(m2 )òðåáóåòñÿäåéñòâèé.äåéñòâèé.O(m)äåéñòâèé.QR-àëãîðèòìÂîçüìåì ìàòðèöóA0 .
Ïðåäñòàâèì åå â âèäå A0 = Q0 R0 , ãäå QT0 = Q−10 ,R - ìàòðèöà ÂÒÔ.ÏîëîæèìA1 = R0 Q0R0 = Q−10 A0(2)Ïîíÿòèå î QR-àëãîðèòìå. Ðåøåíèå ïîëíîé ïðîáëåìû ñîáñòâåííûõçíà÷åíèé.53A1 = Q−10 A0 Q0Òàêèì îáðàçîì, ìàòðèöûA1A0èïîäîáíû ñ îðòîãîíàëüíîé ìàòðèöåé.Àíàëîãè÷íî, ñäåëàåì ñëåäóþùèå øàãè:A1 = Q1 R1 , QT1 = Q−11 , R1 − ÂÒÔ...Óñòðåìèìk → ∞,Ak = Qk Rk , k = 0, 1, . . .(3)Ak+1 = Rk Qk(4)òîãäà:× × ...0 × ...Ak → .. .. . .. ..0 0 ...××××Ãäå íà ãëàâíîé äèàãîíàëè áóäóò ñòîÿòü ñîáñòâåííûå çíà÷åíèÿ ìàòðèöA0 , A1 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
