Н.И. Ионкин - Электронные лекции (2009) (1135239), страница 4
Текст из файла (страница 4)
Ïóñòü A∗ = A > 0, B ∗ = B > 0,∃ρ : 0 < ρ < 1,1+ρ1−ρB≤A≤B.ττ(5)Òîãäà èòåðàöèîííûé ìåòîä (2) ñõîäèòñÿ ê ðåøåíèþ (1) è âûïîëíåíàîöåíêàkv n+1 kB ≤ ρkv n kB .Çàìå÷àíèå. Èç òîãî, ÷òî A ≤1+ρB èτA<ρ < 1,(6)ñëåäóåò, ÷òî2B,τò.å.B − 0.5τ A > 0.Òàêèì îáðàçîì, ïî òåîðåìå Ñàìàðñêîãî, ñõîäèìîñòü èìååò ìåñòî.Äîêàçàòåëüñòâî òåîðåìû. Èç ïîëîæèòåëüíîé îïðåäåëåííîñòè ìàòðèöûBñëåäóåò, ÷òî11∃B 2 = (B 2 )∗ > 0,11∃B − 2 = (B − 2 )∗ > 0.Äîìíîæèì îáå ÷àñòè (3) ñëåâà íà1B2Îáîçíà÷èì11B− 2 :1v n+1 − v n+ B − 2 Av n = 0.τB 2 vn = zn.Îöåíêà ñêîðîñòè ñõîäèìîñòè èòåðàöèîííûõ ìåòîäîâ32Òîãäà11z n+1 − z n+ B − 2 AB − 2 z n = 0.τÂûðàçèìz n+1:11z n+1 = z n − τ B − 2 AB − 2 z n .Îáîçíà÷èì11S = E − τ B − 2 AB − 2 .Òîãäàz n+1 = Sz n .Íàçîâåì ìàòðèöóS(7)ìàòðèöåé ïåðåõîäà äëÿzn.Äîêàæåì, ÷òî èç òîãî, ÷òîkz n+1 k ≤ ρkz n k,ñëåäóåò, ÷òîkv n+1 kB ≤ ρkv n kB .Äåéñòâèòåëüíî,11kz n k2 = (z n , z n ) = (B 2 v n , B 2 v n ) = (Bv n , v n ) = kv n k2B .Òàêèì îáðàçîì, îñòàëîñü äîêàçàòü, ÷òîkz n+1 k ≤ ρkz n k.(8)sk , k = 1, .
. . , m ñîáñòâåííûå çíà÷åíèÿ ìàòðèöû S . Çàôèêñèx ñîáñòâåííûé âåêòîð, ñîîòâåòñòâóþùèé ñîáñòâåííîìóçíà÷åíèþ sk :Sx = sk x (x 6= 0).Ïóñòüðóåìk,ïóñòüÇàìåòèì, ÷òî1111B 2 Sx = (B 2 − τ AB − 2 )x = sk B − 2 x.Îáîçíà÷èì1y = B − 2 x.Òîãäà ïðåäûäóùåå âûðàæåíèå ìîæíî ïåðåïè-ñàòü â âèäå:(B − τ A)y = sk By,(1 − sk )By = τ Ay,1 − skAy =By.τÎöåíêà ñêîðîñòè ñõîäèìîñòè èòåðàöèîííûõ ìåòîäîâ33Èç óñëîâèÿ (5) òåîðåìû ñëåäóåò, ÷òî1−ρ1 − sk1+ρ(By, y) ≤ (Ay, y) =(By, y) ≤(By, y).τττÏîñêîëüêó(By, y) > 0,òî ïðåäûäóùåå íåðàâåíñòâî âëå÷¼ò1 − sk1+ρ1−ρ≤≤.τττÑëåäîâàòåëüíî,|sk | ≤ ρ, k = 1, . .
. , m.Ïîñêîëüêó âñå ìàòðèöû, âõîäÿùèå â ïðàâóþ ÷àñòü âûðàæåíèÿ (7), ÿâëÿþòñÿ ñàìîñîïðÿæåííûìè, òî è ìàòðèöàSÿâëÿåòñÿ ñàìîñîïðÿæåííîé.mÑëåäîâàòåëüíî, ñóùåñòâóåò îðòîíîðìèðîâàííûé áàçèñ {ek }1 , ñîñòîÿùèéèç ñîáñòâåííûõ âåêòîðîâ ìàòðèöû S :Sek = sk ek , k = 1, . . . , m.Ðàçëîæèì âåêòîðzn{ek } :ïî áàçèñónz =nX(n)ck ek .k=1Òîãäàz n+1 = Sz n =nX(n)ck Sek =nX(n)ck sk ek .k=1k=1Ïîëüçóÿñü ðàâåíñòâîì Ïàðñåâàëÿ è ïîëó÷åííîé îöåíêîé äëÿåì:kzn+1 2k =nX(n)(ck )2 s2kk=12≤ρnX|sk |, èìå-(n)(ck )2 = ρ2 kz n k2 .k=1Ìû äîêàçàëè (8) è (6).Cëåäñòâèå 1. Ïóñòü A∗ = A > 0, B ∗ = B > 0, ∃ 0 < γ1 < γ2 :γ1 B ≤ A ≤ γ2 B.Òîãäà, åñëèτ=2γ1 +γ2= τ0 ,òîkvn+1 kB ≤ ρkvn kB ,(9)ãäåρ=1−ξ,1+ξξ=γ1.γ2Èññëåäîâàíèå ñõîäèìîñòè ïîïåðåìåííî òðåóãîëüíîãî èòåðàöèîííîãîìåòîäà34Äîêàçàòåëüñòâî.
Íàéäåì(τ=ρ=2,γ1 +γ21−ξ;1+ξγ1èγ2 :(γ1 + γ2 = τ2 ,⇔γ2 − γ1 = ρ(γ1 + γ2 );(γ1 + γ2 = τ2 ,⇔;γ2 − γ1 = 2ρτ(γ1 =⇔γ2 =1−ρ,τ1+ρ.τÒàêèì îáðàçîì, ìû íàõîäèìñÿ â óñëîâèÿõ äîêàçàííîé òåîðåìû.Cëåäñòâèå 2. Ïóñòü A∗ = A > 0, B = E,γk ñîáñòâåííûå çíà÷åíèÿ ìàòðèöû A, k= 1, . . . , m,γ1 = min γ k , γ2 = max γ k .k=1,...,mk=1,...,mÒîãäà èòåðàöèîííûé ìåòîä èìååò âèäBè èìååò ìåñòîxn+1 − xn+ Axn = fτρ-îöåíêàkvn+1 k ≤ ρkvn k,ãäåρ=1−ξγ1,ξ=1+ξγ2.Äîêàçàòåëüñòâî. Óòâåðæäåíèå äàííîãî ñëåäñòâèÿ âûòåêàåò èç óòâåðæäåíèÿ ïðåäûäóùåãî ñëåäñòâèÿ.8Èññëåäîâàíèå ñõîäèìîñòè ïîïåðåìåííî òðåóãîëüíîãî èòåðàöèîííîãî ìåòîäàÐàññìîòðèì ÑËÀÓ:Ax = f, |A| =6 0(1)Çàïèøåì ïîïåðåìåííî òðåóãîëüíûé èòåðàöèîííûé ìåòîä (ÏÒÈÌ):(E + ωR1 )(E + ωR2 )ω > 0,τ > 0,xn+1 − xn+ Axn = f,τn = 0, 1, . .
. ,A = R1 + R2 ,x0çàäàíî,(2)Èññëåäîâàíèå ñõîäèìîñòè ïîïåðåìåííî òðåóãîëüíîãî èòåðàöèîííîãîìåòîäà350, 5a110···0 a210, 5a22 · · ·0 R1 = ........ ....am1am2 · · · 0, 5amm íèæíåòðåóãîëüíàÿ ìàòðèöà,0, 5a11a12···a1m 00, 5a22 · · ·a2m R2 = ........ ....00· · · 0, 5amm âåðõíåòðåóãîëüíàÿ ìàòðèöà.Îáîçíà÷èìB = (E + ωR1 )(E + ωR2 ).Ýòî îáîçíà÷åíèå ñîãëàñóåòñÿ ñ îáîçíà÷åíèåì äëÿ èòåðàöèîííîãî ìåòîäà îáùåãî âèäà, ðàññìàòðèâàåìîãî â ïðåäûäóùèõ ïàðàãðàôàõ.Òåîðåìà 1. Ïóñòü A∗ = A > 0, ω >τ. Òîãäà ÏÒÈÌ (2) ñõîäèòñÿ ïðè40ëþáîì íà÷àëüíîì ïðèáëèæåíèè x â ñðåäíåêâàäðàòè÷íîé íîðìå.Äîêàçàòåëüñòâî.
ÐàñïèøåìB:B = (E + ωR2∗ )(E + ωR2 ) = E + ωA + ω 2 R2∗ R2 = (E − ωR2∗ )(E − ωR2 ) + 2ωAC = E−ωR2 . Òîãäà C ∗ = (E−ωR2∗ ), C ∗ C > 0,(Cx, Cx) > 0 ïðè x 6= 0,Îáîçíà÷èìò.ê.(C ∗ Cx, x) =B − 0, 5τ A > B − 2ωA = C ∗ C > 0.Òàêèì îáðàçîì, ïî òåîðåìå Ñàìàðñêîãî, èìååò ìåñòî ñõîäèìîñòü â ñðåäíåêâàäðàòè÷íîé íîðìå.Òåîðåìà 20,(îá îöåíêå ñêîðîñòè ñõîäèìîñòè ÏÒÈÌ). Ïóñòü∃δ, ∆ > 0,ÏóñòüA = A∗ >ò.÷.A ≥ δE,R2∗ R2 ≤2ω=√ ,δ∆τ=∆A.42,γ1 + γ2(3)(4)Èññëåäîâàíèå ñõîäèìîñòè ïîïåðåìåííî òðåóãîëüíîãî èòåðàöèîííîãîìåòîäà36ãäå√ √δ( δ∆)√ ,γ1 = √2( δ + ∆)√δ∆.4γ2 =(5)Òîãäà èòåðàöèîííûé ìåòîä (2) ðåøåíèÿ (1) ñõîäèòñÿ è èìååò ìåñòî îöåíêàkxn+1 − xkB ≤ ρkxn − xkB ,ãäå√1− ηρ=√ ,1+3 ηη=(6)δ,∆(7)B = (E + ωR2∗ )(E + ωR2 ).δ ≤ ∆.∀x ∈ H : x 6= 0Äîêàçàòåëüñòâî.
Äîêàæåì, ÷òîÈç óñëîâèÿ (3) ñëåäóåò, ÷òîèìååì(Ax, x) ≥ δkxk2 ,kR2 xk2 = (R2 x, R2 x) = (R2∗ R2 x, x) ≤ÏîñêîëüêóA = R1 + R2 , R1 = R2∗ ,∆(Ax, x)4òî(Ax, x) = (R2∗ x, x) + (R2 x, x) = 2(R2 x, x).Òàêèì îáðàçîì,δkxk2 ≤ (Ax, x) =(Ax, x)24(R2 x, x)2=.(Ax, x)(Ax, x)Èç íåðàâåíñòâà Êîøè-Áóíÿêîâñêîãî:δkxk2 ≤Ñîêðàòèâ íàkxk2 ,4kR2 xk2 · kxk2∆≤ 4 kxk2 = ∆kxk2(Ax, x)4ïîëó÷èìδ ≤ ∆. ñîîòâåòñòâèè ñî ñëåäñòâèåì 1 ïàðàãðàôà 7, ïîäáåðåì êîýôôèöèåíòûγ1èγ2òàê, ÷òîáû âûïîëíÿëîñüγ1 B ≤ A ≤ γ2 B .Èç äîêàçàòåëüñòâà òåîðåìû 1 äàííîãî ïàðàãðàôà11îáðàçîì, A ≤B, γ2 (ω) = 2ω.2ωB ≥ 2ωA.ÒàêèìÈññëåäîâàíèå ñõîäèìîñòè ïîïåðåìåííî òðåóãîëüíîãî èòåðàöèîííîãîìåòîäà37δδ11B = E + ωA + ω 2 R2 R2∗ ≤ A + ωA + ω 2 A = ( + ω + ω 2 )A,δ4δ41δγ1 (ω) = ( + ω + ω 2 )−1 .δ4Òàêèì îáðàçîì, èç ñëåäñòâèÿ 1 ïàðàãðàôà 7 ïîëó÷àåì, ÷òî äëÿ ÏÒÈÌ1−ξ(ω), ξ(ω) = γγ12 (ω).ρ-îöåíêà (6), ãäå ρ(ω) = 1+ξ(ω)(ω)γ2 (ω).Ìèíèìèçèðóåì ρ(ω).
Äëÿ ýòîãî ìèíèìèçèðóåì f (ω) =γ1 (ω)èìååò ìåñòî1f (ω) =20∆1− 24δω,2ω = ω0 = √ .δ∆00Ïîñêîëüêó f (ω0 ) > 0, òî ïðè ω = ω0 äîñòèãàåòñÿ ìèíèìóì f (ω),ñëåäîâàòåëüíî, íà ω0 äîñòèãàåòñÿ ìèíèìóì è ρ(ω)Ïîäñòàâèâ ïîëó÷åííîå çíà÷åíèå ω0 â âûðàæåíèÿ äëÿ γ1 (ω), γ2 (ω) èρ(ω), ïîëó÷èì (5) è (7).f 0 (ω) = 0ïðèÍàïîìíèì, ÷òî ÷èñëî èòåðàöèé, íåîáõîäèìîå äëÿ äîñòèæåíèÿ òî÷íîñòè,ìîæíî âû÷èñëèòü ïî ôîðìóëå:1lnn0 () = .ln ρ1Âåëè÷èíàln ρ1íàçûâàåòñÿ ñêîðîñòüþ ñõîäèìîñòè èòåðàöèîííîãî ìå-òîäà.Ñðàâíèì ÏÒÈÌ è ìåòîä ïðîñòîé èòåðàöèè (ÏÈ) ïî ñêîðîñòè ñõîäèìîñòè.Íàïîìíèì, ÷òî ìåòîä ÏÈ èìååò âèä:xn+1 − xn+ Axn = f,ττ > 0,n = 0, 1, .
. . ,x0 çàäàíî.Ìåòîäû ðåøåíèÿ çàäà÷ íà ñîáñòâåííûå çíà÷åíèÿ ðåàëüíûõ çàäà÷àõη = O(m−2 ).38 ñîîòâåòñòâèè ñ ýòèì, îöåíèì ñêî-ðîñòü ñõîäèìîñòè ÏÒÈÌ:√p1+3 η1ln =√ = Θ( (η)) ⇒ n0 () = Θ(m)ρ1− ηÒåïåðü îöåíèì ñêîðîñòü ñõîäèìîñòè ÏÈ:ln11+ξ(1 + ξ)2 ∼= ln= ln= ln(1+2ξ) ∼= ln(1+2η) ∼= η ⇒ n0 () = Θ(m2 ).ρ1−ξ1 − ξ2Òàêèì îáðàçîì, ÏÒÈÌ ñõîäèòñÿ íà ïîðÿäîê áûñòðåå ÏÈ.9Ìåòîäû ðåøåíèÿ çàäà÷ íà ñîáñòâåííûå çíà÷åíèÿÏóñòü ìàòðèöàAèìååò ðàçìåðíîñòüñîáñòâåííûå çíà÷åíèÿ ìàòðèöûm × m.Ðàññìîòðèì çàäà÷ó íàA:Ax = λx,x 6= 0.(1)λ è âåêòîð x óäîâëåòâîðÿþò (1), òî λ íàçûâàåòñÿ ñîáñòâåííûìA, à x íàçûâàåòñÿ ñîáñòâåííûì âåêòîðîììàòðèöû (îïåðàòîðà) A.Äëÿ íàõîæäåíèÿ ñîáñòâåííûõ çíà÷åíèé A íóæíî ðåøèòü óðàâíåíèåÅñëè ÷èñëîçíà÷åíèåì ìàòðèöû (îïåðàòîðà)f (λ) = |A − λE| = 0.Ïðè ýòîì,f (λ) ìíîãî÷ëåí ñòåïåíèm.Ïðèm≥5äàííàÿ çàäà÷à àíà-ëèòè÷åñêè íå ðàçðåøèìà â îáùåì ñëó÷àå.Çàìåòèì, ÷òî â îáùåì ñëó÷àåλ ∈ C,äàæå åñëèA ∈ Rm×mÐàçëè÷àþò äâå ïðîáëåìû ñîáñòâåííûõ çíà÷åíèé:1. ×àñòè÷íàÿ ïðîáëåìà ñîáñòâåííûõ çíà÷åíèé.
Òðåáóåòñÿ íàéòè íåêîòîðîå ïîäìíîæåñòâî ñïåêòðà ìàòðèöû A (êàê ïðàâèëî, ìèíèìàëüíîå è ìàêñèìàëüíîå ïî ìîäóëþ ñîáñòâåííûå çíà÷åíèÿ).2. Ïîëíàÿ ïðîáëåìà ñîáñòâåííûõ çíà÷åíèé. Òðåáóåòñÿ íàéòè âåñü ñïåêòðìàòðèöû A.Äëÿ ïðîñòîòû áóäåì ðàññìàòðèâàòü òîëüêî ñîáñòâåííûå âåêòîðà, èìåþùèå íîðìó1: kxk = 1.Ìåòîäû ðåøåíèÿ çàäà÷ íà ñîáñòâåííûå çíà÷åíèÿ39Ñòåïåííîé ìåòîä ðåøåíèÿ ÷àñòè÷íîé ïðîáëåìû ñîáñòâåííûõ çíà÷åíèéÝòîò ìåòîä èìååò âèäxn+1 = Axn ,n = 0, 1, . . . ,Ïóñòü ñîáñòâåííûå çíà÷åíèÿòàê, ÷òîx0(2) çàäàíî.λ1 , . .
. , λmìàòðèöûAïðîíóìåðîâàíû|λ1 | ≤ |λ2 | ≤ . . . ≤ |λm |.Äëÿ äîêàçàòåëüñòâà ñõîäèìîñòè äàííîãî ìåòîäà ïîòðåáóåì âûïîëíåíèå ñëåäóþùèõ óñëîâèé:A)Ñóùåñòâóåò áàçèñ{ek }mk=1 èç ñîáñòâåííûõ âåêòîðîâ A : Aek = λk ek , k =1, . . . , m. λm−1 B) λm < 1.C){ek } : x0 =Ïðè ðàçëîæåíèè íà÷àëüíîãî ïðèáëèæåíèÿ ïî áàçèñóc1 e1 + c2 e2 + . . . + cm emÇàïèøåìâûïîëíåíîcm 6= 0.xn :xn = c1 λ1 e1 + c2 λ2 e2 + .
. . + cm λm em , n nxnλ2λ1e+ce2 + . . . + cm em .=c121λnmλmλmÒàêèì îáðàçîì, ïðèn → ∞ xnñòðåìèòñÿ ïî íàïðàâëåíèþ ê ñîá-ñòâåííîìó âåêòîðó, îòâå÷àþùåìó ìàêñèìàëüíîìó ïî ìîäóëþ ñîáñòâåííîìó çíà÷åíèþ.Îáîçíà÷èì ÷åðåç(i)xn+1 i-óþ(i)êîîðäèíàòó âåêòîðà(i)xn+1 .Òîãäà:(i)(i)xn+1 = c1 λn+1e1 + c2 λn+1e2 + · · · + cm λn+112m em(i)(i)nnn (i)x(i)n = c1 λ1 e1 + c2 λ2 e2 + · · · + cm λm emÏîäåëèì(i)xníà(i)xn(i)cm λn+1m em(i)xn+1(i)xn+1=:(i)cm−1 em−1cm e(i)m1+(i)cm λnm em 1 +(i)cm−1 em−1cm e(i)mλm−1λmn+1λm−1λmn(i)+ ··· +c1 e1cm e(i)m(i)+ ··· +c1 e 1cm e(i)mλ1λmλ1λmn+1 n =Ìåòîäû ðåøåíèÿ çàäà÷ íà ñîáñòâåííûå çíà÷åíèÿ40n λm−1(n)= λm + O= λmλmn − λm = O λλm−1, òî åñòümÒàêèì îáðàçîì,(n)λmìû ðåøèëè çàäà÷óíàõîæäåíèÿ ìàêñèìàëüíîãî ïî ìîäóëþ ñîáñòâåííîãî çíà÷åíèÿ.
Ñôîðìóëèðóåì ñîîòâåòñâóþùåå óòâåðæäåíèå:Óòâåðæäåíèå. Ïóñòü âûïîëíåíû ñëåäóþùèå ïðåäïîëîæåíèÿ: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, . . .