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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

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

Òîãäà:Äîêàçàòåëüñòâî. Ïóñòüñîáñòâåííîìó çíà÷åíèþ- ñîáñòâåííûé âåêòîð ìàòðèöû A, îòâå÷àþùèé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Ïðåäïîëîæèì, ÷òîµ1 = 0. Òîãäà λ1 µ0 = 0, µ0 = 0, îòêóäà ñëåäóåò, ÷òî xk = 0, à ýòî ïðîòèâîðå÷èòòîìó, ÷òî x - íåíóëåâîé âåêòîð.Ìåòîä îáðàòíûõ èòåðàöèé ñî ñäâèãîìÈíîãäà áûâàåò íóæíî íàéòè ñîáñòâåííîå çíà÷åíèå èç âíóòðåííåé ÷àñòè ñïåêòðà.

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

Íàøàçàäà÷à - ïðèâåñòè ìàòðèöó A (m x m) ê òðåóãîëüíîé. Îäíàêî, ïðèâåäåíèå ìàòðèöû A ê òðåóãîëüíîé ôîðìå ìåòîäîì Ãàóññà íå ñîõðàíÿåò ñïåêòð ìàòðèöû. Ñïåêòð ìàòðèöû ñîõðàíÿåòñÿïðè ïðåîáðàçîâàíèè ïîäîáèÿ:C = Q−1 AQÅñëè ìàòðèöà Q - îðòîãîíàëüíà (óíèòàðíà), òî ñîõðàíÿåòñÿ ñèììåòðèÿ.Ïðèâåäåíèå ìàòðèöû ê âåðõíåé ïî÷òè òðåóãîëüíîé ôîðìå (ÂÏÒÔ)34Îïðåäåëåíèå. Ìàòðèöà íàõîäèòñÿ â âåðõíåé ïî÷òè òðåóãîëüíîé ôîðìå (ÂÏÒÔ), åñëè îíàèìååò âèä (íåíóëåâûå ýëåìåíòû îáîçíà÷åíû ÷åðåç x):xx0A =  ...00Ðàññìîòðèì âåêòîð-ñòîëáåöx 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= ||ν||2ν T ν = ν12 + ν22 + · · · + νmν1 ν2 · · · ν1 νmν12 ν2 ν1ν22 · · · ν2 νm Tνν =  ...... .. ....

2νm ν1 νm ν2 · · · νmÌàòðèöàνν T- ñèììåòðè÷íàÿ.Ñâîéñòâà îïåðàòîðà H:1.HT = H2.H −1 = H TÄîêàæåì âòîðîå ñâîéñòâî, òî åñòü ÷òîHÿâëÿåòñÿ îðòîãîíàëüíîé ìàòðèöåé.Äîêàçàòåëüñòâî.VVTVVTE−2=H H =H = E−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 ÿâëÿåòñÿ îðòîãîíàëüíîé.Ïðèâåäåíèå ìàòðèöû ê âåðõíåé ïî÷òè òðåóãîëüíîé ôîðìå (ÂÏÒÔ)35Ñôîðìóëèðóåì è äîêàæåì ñâîéñòâî 3.Òåîðåìà. Äëÿ ëþáîãî âåêòîðà x: x1 x=ìîæíî âûáðàòü òàêîé âåêòîðx2x3...xmV = (v1 , v2 , . . .

, vm ), ÷òî −σ Hx = ãäåσ = ||x||,00...0òî åñòü ïðåîáðàçîâàíèå H ïîäàâëÿåò âñå êîîðäèíàòû âåêòîðà êðîìå ïåðâîé.Äîêàçàòåëüñòâî. ÂûáåðåìVâ âèäå:V = x + σz, σ ∈ R, z = (1, 0, 0, . . . , 0)THx = x − 2(x + σz)(x + σz)Tx=(x + σz)T (x + σz)2(x + σz)T xx − (x + σz)(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)222 −σ (||x|| + 2σx1 + σ ) + ||x|| − σ= x − x − σz = ||x||2 + 2σx1 + σ 200...0Ïîëó÷åííûå 3 ñâîéñòâà ìû áóäåì ïðèìåíÿòü ïðè ïðèâåäåíèè ìàòðèöû ê âåðõíåé ïî÷òè òðåóãîëüíîé ôîðìå.A ïîðÿäêà m × m:a11 a12 . .

. a1m a21 a22 . . . a2m A=. . . . . . . . . . . . . . . . . . .am1 am2 . . . ammÏóñòü äàíà ïðîèçâîëüíàÿ ìàòðèöàÏðèâåäåíèå ìàòðèöû ê âåðõíåé ïî÷òè òðåóãîëüíîé ôîðìå (ÂÏÒÔ)36Ïðåäñòàâèì åå â âèäå áëî÷íîé ìàòðèöû ñëåäóþùåãî âèäà:A=a11 ym−1xm−1 Am−1ãäåym−1 = (a12 , a13 , . . . , a1m )xm−1 = (a21 , a31 , .

. . , am1 )à ìàòðèöàAm−1ïîëó÷àåòñÿ èç ìàòðèöûAóäàëåíèåì ïåðâîãî ñòîëáöà è ïåðâîé ñòðîêè.Âîñïîëüçóåìñÿ ñâîéñòâîì 3:Hm−1 xm−1Ðàññìîòðèì ìàòðèöóU1ïîðÿäêàm×mâèäà:U1 =Î÷åâèäíî,U1 = U1T ,U12−||xm−1 ||0=...01012021 Hm−1çíà÷èò:=1012021 Hm−11012021 Hm−1Ïîñëåäíåå ðàâåíñòâî âåðíî â ñèëó òîãî, ÷òîìàòðèöà=10122021 Hm−12Hm−1= E- îðòîãîíàëüíàÿ.−1Îáîçíà÷èì C1 = U1 AU1a11−σ1 zm−10C1 = ...0(1)c12 . .

.(2)c22 . . . (1)(1) c32 cij .... . .(1)cm2 . . .Òàêèì îáðàçîì, ñòðóêòóðó ìàòðèöû ìîæíî ïðåäñòàâèòü òàê:××00 ...0Âîçüìåì âåêòîð(1)c32. . .(1)cm2xm−2 = ××××.........× ... ×××××............=EÒàêèì îáðàçîì, ìû ïîëó÷èëè ÷òîU1Ïðèâåäåíèå ìàòðèöû ê âåðõíåé ïî÷òè òðåóãîëüíîé ôîðìå (ÂÏÒÔ)Ïî ñâîéñòâó 3, ìîæíî ïîñòðîèòü òàêîé îïåðàòîðHm−2 ,37÷òî:Hm−2 xm−2Ðàññìîòðèì ìàòðèöóU2 ,ïîñòðîåííóþ àíàëîãè÷íî ìàòðèöåU2 =ãäåE2 =1 00 1U2 = U2T2.U2 = U2−1E2012021 Hm−2U1Ñâîéñòâà ìàòðèöû1.−||xm−2 ||00=...0U2 :- îðòîãîíàëüíàÿ ìàòðèöàÀíàëîãè÷íî, îáîçíà÷èìC2 :C2 = U2−1 C1 U2 = U2−1 U1−1 AU1 U2Ïîñìîòðèì íà ñòðóêòóðó ìàòðèöûC2 :××××............0 × ... ×××0C2 =  0 ...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Ïîíÿòèå î QR-àëãîðèòìå. Ðåøåíèå ïîëíîé ïðîáëåìû ñîáñòâåííûõ çíà÷åíèé.38Ñëåäîâàòåëüíî, ìàòðèöà 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Äîêàçàòåëüñòâî.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 = CŸ11Ïîíÿòèå î QR-àëãîðèòìå.

Ðåøåíèå ïîëíîé ïðîáëåìûñîáñòâåííûõ çíà÷åíèé.Èçó÷åííûå â ïðåäûäóùåì ïàðàãðàôå ñâîéñòâà ïîçâîëÿò íàì ïðåäñòàâèòü ìàòðèöóA = QRãäåQ−1 = QT- îðòîãîíàëüíàÿ ìàòðèöà, àRA â âèäå:(1)èìååò âåðõíåòðåóãîëüíóþ ôîðìó.Âîçüìåì âåêòîð x = (a11 , a21 , . . . , am1 ). Äëÿ íåãî ñóùåñòâóåò òàêàÿ îðòîãîíàëüíàÿ ìàòðèöàVVTH1 = E − 2 ||V, êîòîðàÿ ïîäàâëÿåò âñå êîîðäèíàòû âåêòîðà x, êðîìå ïåðâîé.||2Ìàòðèöà H1 A èìååò âèä:×0H1 A =  0 ...0Ïîñòðîèì ìàòðèöóH2 =1 00 Hïîðÿäêà× ... ×× . . . ×× .

. . ×.........× ... ×m × m,òàêóþ,÷òîÏîíÿòèå î QR-àëãîðèòìå. Ðåøåíèå ïîëíîé ïðîáëåìû ñîáñòâåííûõ çíà÷åíèé.39× × ... ×× × . . . ×0 × . . . ×....... ×..0 × ... ××0H2 H1 A =  0 ...0Î÷åâèäíî, ÷òî çà (m-1) øàã ìû îáíóëèì âñå ýëåìåíòû ïîä ãëàâíîé äèàãîíàëüþ:Hm−1 Hm−2 .

. . H2 H1 A = R =×0...0××...0............×!×××−ÂÒÔÏîñòðîèì ìàòðèöó Q ñëåäóþùèì îáðàçîì:Q = H1 H2 . . . Hm−1ÍàéäåìQT :TT−1−1QT = Hm−1Hm−2. . . H2T H1T = Hm−1Hm−2. . . H1−1 = Q−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 Q0(2)R0 = Q−10 A0A1 = Q−10 A0 Q0Òàêèì îáðàçîì, ìàòðèöûA1èA0ïîäîáíû ñ îðòîãîíàëüíîé ìàòðèöåé.Àíàëîãè÷íî, ñäåëàåì ñëåäóþùèå øàãè:A1 = Q1 R1 , QT1 = Q−11 , R1 − ÂÒÔ...Ak = Qk Rk , k = 0, 1, . . .(3)Ak+1 = Rk Qk(4)Ïîíÿòèå î QR-àëãîðèòìå. Ðåøåíèå ïîëíîé ïðîáëåìû ñîáñòâåííûõ çíà÷åíèé.Óñòðåìèìk → ∞,40òîãäà:× × ...0 × ...Ak →  .. ..

Характеристики

Список файлов лекций