Численные методы. Ионкин (2009) (1160433), страница 4
Текст из файла (страница 4)
, m.Ïîñêîëüêó âñå ìàòðèöû, âõîäÿùèå â ïðàâóþ ÷àñòü âûðàæåíèÿ (7), ÿâëÿþòñÿ ñàìîñîïðÿæåííûìè, òî è ìàòðèöà S ÿâëÿåòñÿ ñàìîñîïðÿæåííîé. Ñëåäîâàòåëüíî, ñóùåñòâóåò îðòîíîðìèðîâàímíûé áàçèñ {ek }1 , ñîñòîÿùèé èç ñîáñòâåííûõ âåêòîðîâ ìàòðèöû S :Sek = sk ek , k = 1, . . .
, m.Îöåíêà ñêîðîñòè ñõîäèìîñòè èòåðàöèîííûõ ìåòîäîâÐàçëîæèì âåêòîðznïî áàçèñó25{ek } :nXzn =(n)ck ek .k=1Òîãäàzn+1n= Sz =nX(n)ck Sek=nXk=1(n)ck sk ek .k=1Ïîëüçóÿñü ðàâåíñòâîì Ïàðñåâàëÿ è ïîëó÷åííîé îöåíêîé äëÿkzn+1 2k =nX(n)(ck )2 s2k2≤ρnX|sk |,èìååì:(n)(ck )2 = ρ2 kz n k2 .k=1k=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 ,γ1 è γ2 :(γ1 + γ2 = τ2 ,⇔γ2 − γ1 = ρ(γ1 + γ2 );ãäåρ=(9)1−ξ,1+ξξ=γ1.γ2Äîêàçàòåëüñòâî. Íàéäåì(τ=ρ=2,γ1 +γ21−ξ;1+ξ(γ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.Äîêàçàòåëüñòâî. Óòâåðæäåíèå äàííîãî ñëåäñòâèÿ âûòåêàåò èç óòâåðæäåíèÿ ïðåäûäóùåãî ñëåäñòâèÿ.Èññëåäîâàíèå ñõîäèìîñòè ïîïåðåìåííî òðåóãîëüíîãî èòåðàöèîííîãî ìåòîäà826Èññëåäîâàíèå ñõîäèìîñòè ïîïåðåìåííî òðåóãîëüíîãî èòåðàöèîííîãî ìåòîäàÐàññìîòðèì ÑËÀÓ:Ax = f, |A| =6 0(1)Çàïèøåì ïîïåðåìåííî òðåóãîëüíûé èòåðàöèîííûé ìåòîä (ÏÒÈÌ):(E + ωR1 )(E + ωR2 )ω > 0,τ > 0,xn+1 − xn+ Axn = f,τn = 0, 1, . .
. ,x0(2)çàäàíî,A = R1 + R2 ,0, 5a110 a210,5a22R1 = .... ..am1am20, 5a11a12 00,5a22R2 = .... ..00······00..... íèæíåòðåóãîëüíàÿ ìàòðèöà,···0, 5amm······a1ma2m ...0, 5amm âåðõíåòðåóãîëüíàÿ ìàòðèöà.....···Îáîçíà÷èìB = (E + ωR1 )(E + ωR2 ).Ýòî îáîçíà÷åíèå ñîãëàñóåòñÿ ñ îáîçíà÷åíèåì äëÿ èòåðàöèîííîãî ìåòîäà îáùåãî âèäà, ðàññìàòðèâàåìîãî â ïðåäûäóùèõ ïàðàãðàôàõ.Òåîðåìà 1.
Ïóñòü A∗ = A > 0, ω >ïðèáëèæåíèèx0τ. Òîãäà ÏÒÈÌ (2) ñõîäèòñÿ ïðè ëþáîì íà÷àëüíîì4â ñðåäíåêâàäðàòè÷íîé íîðìå.Äîêàçàòåëüñòâî. ÐàñïèøåìB:B = (E + ωR2∗ )(E + ωR2 ) = E + ωA + ω 2 R2∗ R2 = (E − ωR2∗ )(E − ωR2 ) + 2ωAÎáîçíà÷èìC = E −ωR2 . Òîãäà C ∗ = (E −ωR2∗ ), C ∗ C > 0,ò.ê.(C ∗ Cx, x) = (Cx, Cx) > 0ïðèx 6=0,B − 0, 5τ A > B − 2ωA = C ∗ C > 0.Òàêèì îáðàçîì, ïî òåîðåìå Ñàìàðñêîãî, èìååò ìåñòî ñõîäèìîñòü â ñðåäíåêâàäðàòè÷íîé íîðìå.Òåîðåìà 2(îá îöåíêå ñêîðîñòè ñõîäèìîñòè ÏÒÈÌ). ÏóñòüA ≥ δE,R2∗ R2 ≤∆A.4A = A∗ > 0,∃δ, ∆ > 0,ò.÷.(3)Èññëåäîâàíèå ñõîäèìîñòè ïîïåðåìåííî òðåóãîëüíîãî èòåðàöèîííîãî ìåòîäàÏóñòü2ω=√ ,δ∆τ=272,γ1 + γ2(4)ãäå√ √δ( δ∆)√ ,γ1 = √2( δ + ∆)√γ2 =δ∆.4(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 äàííîãî ïàðàãðàôàB ≥ 2ωA.
Òàêèì îáðàçîì, A ≤1.2ω1B,2ωγ2 (ω) =1δ1δB = E + ωA + ω 2 R2 R2∗ ≤ A + ωA + ω 2 A = ( + ω + ω 2 )A,δ4δ41δγ1 (ω) = ( + ω + ω 2 )−1 .δ4Òàêèì îáðàçîì, èç ñëåäñòâèÿ 1 ïàðàãðàôà 7 ïîëó÷àåì, ÷òî äëÿ ÏÒÈÌ èìååò ìåñòî1−ξ(ω)(6), ãäå ρ(ω) =, ξ(ω) = γγ12 (ω).1+ξ(ω)(ω)ρ-îöåíêàÌåòîäû ðåøåíèÿ çàäà÷ íà ñîáñòâåííûå çíà÷åíèÿÌèíèìèçèðóåìρ(ω).1f (ω) =2f 0 (ω) = 0äîñòèãàåòñÿf (ω) =Äëÿ ýòîãî ìèíèìèçèðóåì0f 00 (ω0 ) > 0, òîìèíèìóì è ρ(ω)Ïîñêîëüêó28ïðèÏîäñòàâèâ ïîëó÷åííîå çíà÷åíèåïðèω = ω0ω0∆1− 24δωγ2 (ω).γ1 (ω),2ω = ω0 = √ .δ∆äîñòèãàåòñÿ ìèíèìóìâ âûðàæåíèÿ äëÿf (ω),γ1 (ω), γ2 (ω)èñëåäîâàòåëüíî, íàρ(ω),Íàïîìíèì, ÷òî ÷èñëî èòåðàöèé, íåîáõîäèìîå äëÿ äîñòèæåíèÿ òî÷íîñòè,ω0ïîëó÷èì (5) è (7).ìîæíî âû÷èñëèòüïî ôîðìóëå:ln 1.n0 () = ln ρ1Âåëè÷èíàln ρ1íàçûâàåòñÿ ñêîðîñòüþ ñõîäèìîñòè èòåðàöèîííîãî ìåòîäà.Ñðàâíèì ÏÒÈÌ è ìåòîä ïðîñòîé èòåðàöèè (ÏÈ) ïî ñêîðîñòè ñõîäèìîñòè.Íàïîìíèì, ÷òî ìåòîä ÏÈ èìååò âèä:xn+1 − xn+ Axn = f,ττ > 0, ðåàëüíûõ çàäà÷àõn = 0, 1, .
. . ,x0 çàäàíî.η = O(m−2 ).  ñîîòâåòñòâèè ñ ýòèì, îöåíèì ñêîðîñòü ñõîäèìîñòè ÏÒÈÌ:√p1+3 η1ln =√ = Θ( (η)) ⇒ n0 () = Θ(m)ρ1− ηÒåïåðü îöåíèì ñêîðîñòü ñõîäèìîñòè ÏÈ:ln1+ξ(1 + ξ)2 ∼1= ln= ln= ln(1 + 2ξ) ∼= ln(1 + 2η) ∼= η ⇒ n0 () = Θ(m2 ).ρ1−ξ1 − ξ2Òàêèì îáðàçîì, ÏÒÈÌ ñõîäèòñÿ íà ïîðÿäîê áûñòðåå ÏÈ.9Ìåòîäû ðåøåíèÿ çàäà÷ íà ñîáñòâåííûå çíà÷åíèÿÏóñòü ìàòðèöàìàòðèöûAèìååò ðàçìåðíîñòüm × m.Ðàññìîòðèì çàäà÷ó íà ñîáñòâåííûå çíà÷åíèÿA:Ax = λx,x 6= 0.λ è âåêòîð x óäîâëåòâîðÿþò (1), òî λ íàçûâàåòñÿ ñîáñòâåííûì çíà÷åíèåì(îïåðàòîðà) A, à x íàçûâàåòñÿ ñîáñòâåííûì âåêòîðîì ìàòðèöû (îïåðàòîðà) A.Äëÿ íàõîæäåíèÿ ñîáñòâåííûõ çíà÷åíèé A íóæíî ðåøèòü óðàâíåíèåÅñëè ÷èñëîf (λ) = |A − λE| = 0.(1)ìàòðèöûÌåòîäû ðåøåíèÿ çàäà÷ íà ñîáñòâåííûå çíà÷åíèÿÏðè ýòîì,f (λ) ìíîãî÷ëåí ñòåïåíèm.Ïðè29m≥5äàííàÿ çàäà÷à àíàëèòè÷åñêè íå ðàçðåøèìàâ îáùåì ñëó÷àå.Çàìåòèì, ÷òî â îáùåì ñëó÷àåλ ∈ C,äàæå åñëèA ∈ Rm×mÐàçëè÷àþò äâå ïðîáëåìû ñîáñòâåííûõ çíà÷åíèé:1.
×àñòè÷íàÿ ïðîáëåìà ñîáñòâåííûõ çíà÷åíèé. Òðåáóåòñÿ íàéòè íåêîòîðîå ïîäìíîæåñòâîñïåêòðà ìàòðèöû A (êàê ïðàâèëî, ìèíèìàëüíîå è ìàêñèìàëüíîå ïî ìîäóëþ ñîáñòâåííûåçíà÷åíèÿ).2. Ïîëíàÿ ïðîáëåìà ñîáñòâåííûõ çíà÷åíèé. Òðåáóåòñÿ íàéòè âåñü ñïåêòð ìàòðèöû A.Äëÿ ïðîñòîòû áóäåì ðàññìàòðèâàòü òîëüêî ñîáñòâåííûå âåêòîðà, èìåþùèå íîðìó1: kxk = 1.Ñòåïåííîé ìåòîä ðåøåíèÿ ÷àñòè÷íîé ïðîáëåìû ñîáñòâåííûõ çíà÷åíèéÝòîò ìåòîä èìååò âèäxn+1 = Axn ,n = 0, 1, .
. . ,Ïóñòü ñîáñòâåííûå çíà÷åíèÿλ1 , . . . , λ mx0(2) çàäàíî.ìàòðèöûAïðîíóìåðîâàíû òàê, ÷òî|λ1 | ≤ |λ2 | ≤. . . ≤ |λm |.Äëÿ äîêàçàòåëüñòâà ñõîäèìîñòè äàííîãî ìåòîäà ïîòðåáóåì âûïîëíåíèå ñëåäóþùèõ óñëîâèé:A)Ñóùåñòâóåò áàçèñ{ek }mk=1èç ñîáñòâåííûõ âåêòîðîâA : Aek = λk ek , k = 1, . . . , m. λm−1 < 1.λm B) C)Ïðè ðàçëîæåíèè íà÷àëüíîãî ïðèáëèæåíèÿ ïî áàçèñóâûïîëíåíîÇàïèøåì{ek } : x0 = c1 e1 + c2 e2 + . . .
+ cm emcm 6= 0.xn :xn = c1 λ1 e1 + c2 λ2 e2 + . . . + cm λm em , n nλ1λ2xn=ce+ce2 + . . . + cm em .112λnmλmλmÒàêèì îáðàçîì, ïðèn → ∞ xnñòðåìèòñÿ ïî íàïðàâëåíèþ ê ñîáñòâåííîìó âåêòîðó, îòâå÷à-þùåìó ìàêñèìàëüíîìó ïî ìîäóëþ ñîáñòâåííîìó çíà÷åíèþ.(i)Îáîçíà÷èì ÷åðåç xn+1 i-óþ êîîðäèíàòó âåêòîðà xn+1 . Òîãäà:(i)(i)(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+1íà(i)xn(i)xnn+1n+1 (i)(i) cm−1 em−1λm−1c1 e 1λ11 + cm (i)+ · · · + cm (i) λmλmemem=nn (i)(i) (i)cm−1 em−1λm−1c1 e1λ1ncm λm em 1 + cm (i)+ · · · + cm (i) λmλm(i)cm λn+1m em(i)xn+1:=ememÌåòîäû ðåøåíèÿ çàäà÷ íà ñîáñòâåííûå çíà÷åíèÿ= λm + OÒàêèì îáðàçîì,(n)λm −λm = Oλm−1λmn 30λm−1λmn = λ(n)m, òî åñòü ìû ðåøèëè çàäà÷ó íàõîæäåíèÿ ìàêñèìàëüíîãîïî ìîäóëþ ñîáñòâåííîãî çíà÷åíèÿ. Ñôîðìóëèðóåì ñîîòâåòñâóþùåå óòâåðæäåíèå:Óòâåðæäåíèå.
Ïóñòü âûïîëíåíû ñëåäóþùèå ïðåäïîëîæåíèÿ:1. (A) Ìàòðèöà A èìååò áàçèñ èç ñîáñòâåííûõ âåêòîðîâ2. (B)| λλm−1|<1m3. (Ñ)x 0 = c1 e 1 + c2 e 2 + · · · + cm e m ,Òîãäàxn → e mãäå(ïî íàïðàâëåíèþ) ïðèi=m{ei }i=1cm 6= 0n → ∞,ãäåem- ñîáñòâåííûé âåêòîð, îòâå÷àþùèén (i)xn+1(n)λm−1íàèáîëüøåìó ïî ìîäóëþ ñîáñòâåííîìó çíà÷åíèþ λm , à λm = (i) = λm + O.λmxnÇàìå÷àíèå.
Óñëîâèÿ (A) è (B) íåñêîëüêî îãðàíè÷èâàþò êëàññ çàäà÷, ê êîòîðûì ïðèìåíèìýòîò ìåòîä, õîòÿ îí âñå ðàâíî îñòàåòñÿ äîñòàòî÷íî øèðîêèì.(n)Çàìå÷àíèå. Íàéòè λm ìîæíî òàêæå ïî ôîðìóëå:λ(n)m =(xn+1 , xn )(Axn , 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)λm:2n+1c2 λ2n+1 + c2 λ2n+1 + · · · + c2m λm(xn+1 , xn )= 1 1 2 2n 2 2 2 2n=(xn , xn )c1 λ1 + c2 λ2 + · · · + c2m λ2nm2 2n+1 2 2n+1 cm−1λm−1λ12 2n+1cm λ m1 + cm+ · · · + ccm1λmλm==2 2n 2 2n cm−1λm−1c1λ122ncm λ m 1 + c m+ · · · + cmλmλmλ(n)m == λm + OÒàêèì îáðàçîì, ïðèA = A∗λm−1λm2n !ïîëó÷èëè áîëåå áûñòðóþ ñõîäèìîñòü.Ìåòîäû ðåøåíèÿ çàäà÷ íà ñîáñòâåííûå çíà÷åíèÿ2.
Ïóñòü∃ {ei }i=mi=131- áàçèñ èç ñîáñòâåííûõ âåêòîðîâ (îðòîíîðìèðîâàííîñòü íå ïðåäïîëàãàåò-ñÿ). Òîãäà: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=12n+1c2m λm=(em , em ) 1 +c2m λ2nm (em , em ) 1 +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 çàäàí.A−1 :xn+1 = A−1 xn ,n = 0, 1, . . . ,x0 çàäàí.Ïîëó÷èëè ñòåïåííîé ìåòîä äëÿ îáðàòíîé ìàòðèöû. Ïóñòü âåðíû ñëåäóþùèå ïðåäïîëîæåíèÿ:1. (A) Ìàòðèöà A èìååò áàçèñ èç ñîáñòâåííûõ âåêòîðîâ2. (B)| λλ12 | < 13. (Ñ)x0 = c1 e1 + c2 e2 + · · · + cm em ,ãäå{ei }i=mi=1c1 6= 0Òîãäà:−n−nxn = c1 λ−n1 e1 + c2 λ2 e2 + · · · + cm λm em n nλ1λ1nλ 1 x n = c1 e 1 + c2e 2 + · · · + cmemλ2λmÒàêèì îáðàçîì,xn → e 1(ïî íàïðàâëåíèþ) ïðèn → ∞.Çàäà÷à. Ïóñòü âûïîëíåíû óñëîâèÿ (A), (B)è (C). Òîãäà ìåòîä îáðàòíûõ èòåðàöèé ïîçâîëÿåò íàéòè ñîáñòâåííîå çíà÷åíèå(n)λ1 = λ1 + Oλ1λ2n, ãäå(n)λ1 =(i)xn(i) .xn+1Ìåòîäû ðåøåíèÿ çàäà÷ íà ñîáñòâåííûå çíà÷åíèÿ(i)xnÄîêàçàòåëüñòâî. Âûïèøåì âûðàæåíèÿ äëÿ32è(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 :−n −n (i) (i)λ2c2 e 2cm e m+ · · · + c1 (i) λλm11 + c1 (i) λ1e1e1=−n−1 −n−1 =(i) (i)−n−1 (i)c2 e2λ2cm emc1 λ 1e1 1 + c1 (i) λ1+ · · · + c1 (i) λλm1(i)c1 λ−n1 e1(i)xn(i)xn+1e1e1= λ1 + OA = A∗ .(n)Íàéäåì λ1 :Ïóñòü òåïåðüìàòðèöû A.Òîãäà∃ {ei }i=mi=1λ1λ2n (n)= λ1- îðòîíîðìèðîâàííûé áàçèñ èç ñîáñòâåííûõ âåêòîðîâ−2n(xn , xn )c21 λ1−2n + c22 λ2−2n + · · · + c2m λm== 2 −2n+1−2n−1(xn+1 , xn )c1 λ1+ c22 λ−2n−1+ · · · + c2m λm2 2 −2n 2 −2n −2ncλλm2c21 λ11 + c21+ · · · + ccm1λ1λ1= 2 −2n−1 2 −2n−1 =λ2λmc21 λ−2n−11 + cc12+ · · · + ccm11λ1λ1! 2nλ1= λ1 + Oλ2λ(n)m =Òàêèì îáðàçîì, ïðèA = A∗ñíîâà èìååì áîëåå áûñòðóþ ñõîäèìîñòü.(n)i=mÇàäà÷à.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
