Н.И. Ионкин - Электронные лекции (2008) (1135232), страница 4
Текст из файла (страница 4)
n = 0, 1, . . . , x0xn+1 − xn+ Axn = f,τãäå(1.48) çàäàíîB = (E + ωR1 )(E + ωR2 ), A = R1 + R20.5a1100.5a11....R1 = , R2 = ..aij0.5amm0Â ýòîì ìåòîäå 2 èòåðàöèîííûõ ïàðàìåòðà (]τÒåîðåìà 4(Î ñõîäèìîñòè ÏÒÈÌ)aij0.5amm> 0, ω > 0).
Ïóñòü A = A∗ > 0. Ïðè âûïîëíåíèèóñëîâèÿ ω > ïîïåðåìåííî òðåóãîëüíûé èòåðàöèîííûé ìåòîä ñõîäèòñÿâ ñðåäíåêâàäðàòè÷íîé íîðìå ïðè ëþáîì íà÷àëüíîì ïðèáëèæåíèè.τ4Äîêàçàòåëüñòâî.R1 = R2∗ ⇒ B = (E + ωR2∗ )(E + ωR2 ), A = R1 + R2 == E + ω(R2∗ + R2 ) + ω 2 R2 R2∗ = E + ωA + ω 2 R2 R2∗Î÷åâèäíî, ÷òî:B = (E − ωR1 )(E − ωR2 ) + 2ωAÃëàâà 1. ×èñëåííûå ìåòîäû ëèíåéíîé àëãåáðû28Ââåäåì íîâóþ ìàòðèöó C:C = E − ωR2 ⇒ C ∗ = E − ωR2∗ ⇒B = CC ∗ ≥ 0ò.ê.(CC ∗ x, x) = (Cx, Cx) ≥ 0 ⇒B ≥ 2ωAÅñëèω>τ4 , òî âûïîëíÿåòñÿ óñëîâèå òåîðåìû Ñàìàðñêîãî:B − 0.5A > 0Ïîýòîìó, ïîïåðåìåííî òðåóãîëüíûé èòåðàöèîííûé ìåòîä ñõîäèòñÿ â ñðåäíåêâàäðàòè÷íîé íîðìå ïðè ëþáîì íà÷àëüíîì ïðèáëèæåíèè.Òåîðåìà 5. Ïóñòü A = A∗ > 0 è ïóñòü(Îá îöåíêå ñõîäèìîñòè ÏÒÈÌ)δ > 0, ∆ > 0 :A ≥ δE, R2∗ R2 ≥Ïîëîæèì ω =√2 , δδ∆=2γ1 +γ2 ,∆A4ãäå√√√δδ∆δ∆√√ , γ2 =γ1 =2 δ+ ∆4Òîãäà ÏÒÈÌ ñõîäèòñÿ è èìååò ìåñòî îöåíêà:√1− ηδn+1nkVkB ≤ ρkV kB , ãäå ρ =√ , η = , B = (E + ωR2∗ )(E + ωR2 )1+3 η∆Äîêàçàòåëüñòâî.1. Ïîêàæåì, ÷òîδ < ∆:(R2∗ R2 x, R2 x) = (R2 x, R2 x) = kR2 xk2 ≤Íàéäåì∆(Ax, x)4(Ax, x):(Ax, x) = ((R1 + R2 )x, x) = (R2∗ x, x) + (R2 x, x) = (xR2 , x) + (R2 x, x)(Ax, x) = 2(R2 x, x)Òîãäà4(R2 x, x)24kR2 xk2 kxk2(Ax, x)2=≤≤(Ax, x)(Ax, x)(Ax, x)kR2 xk2 ∆≤(Ax, x) = ∆kxk2(Ax, x) 4δkxk2 ≤ (Ax, x) =Òàêèì îáðàçîì ìû ïîëó÷èëè:δkxk2 ≤ ∆kxk2 ⇒ δ ≤ ∆ ⇒ ρ < 1Ïîäáåðåìγ1 , γ 2òàêèì îáðàçîì, ÷òîáû âûïîëíÿëîñü ïåðâîå ñëåäñòâèå èçòåîðåìû î ñõîäìîñòè èòåðàöèîííûõ ìåòîäîâ.Èç òåîðåìû î ñõîäèìîñòè ïîëó÷àåì:B ≥ 2ωA ⇒ A ≤11B, γ2 =2ω2ω1.8.
Èññëåäîâàíèå ñõîäèìîñòè ïîïåðåìåííî-òðåóãîëüíîãî ìåòîäà29B = E + ωA + ω 2 R2∗ R2Ïî óñëîâèþA ≥ δE, R2∗ R2 ≥B≤∆4 A, ñëåäîâàòåëüíî:∆ω 21∆ω 21A + ωA +A=( +ω+)A ⇒δ4δ41∆ω 2 −1γ1 = ( + ω +)δ4Ïîëàãàÿτ (ω) =2γ1 +γ2 ,1−ξ(ω)1+ξ(ω) ,ρ(ω) =ξ(ω) =γ1 (ω)γ2 (ω) , ïîëó÷àåì, ÷òî ìåòîäáóäåò ñõîäèòñÿ.×òîáû óâåëè÷èòü ñêîðîñòü ñõîäèìîñòè íóæíî ìèíèìèçèðîâàòüÂâåäåì ôóíêöèþìàêñèìàëüíàγ2 (ω)γ1 (ω) . Òàì, ãäå áóäåò ìèíèìàëüíàf (ω) =ξ(ω) =γ1 (ω)γ2 (ω) , ñëåäîâàòåëüíî òàì áóäåò ìèíèìàëüíàf (ω) =0f (ω) =∆1−82δω 200Ïåðåñ÷èòàåìïðè1ω3002ω = √ , f (ω) > 0 ⇒ fδ∆γ1 , γ2 , ξ(ω), ρ(ω)ρ(ω):f (ω):f (ω) = cf (ω) = 0ρ(ω).òàì áóäåò1 1∆ω 2( +ω+)2ω δ4Ïîñ÷èòàåì 1-þ è 2-þ ïðîèçâîäíûå0f,2√δ∆â ñîîòâåòñòâèè ñ çíà÷åíèåì= minω:√δ∆4√√∆ω 2 −11δδ∆√ )) =(√γ1 = ( + ω +δ42δ+ ∆√1 δγ1 (ω)√=√ξ(ω) =γ2 (ω)δ+ ∆q√√δ√1−1− η1 − ξ(ω)∆− δ∆√ =q =ρ(ω) ==√√1 + ξ(ω)1+3 ηδ∆+3 δ1+3 ∆1=γ2 =2ωÒàêèì îáðàçîì, ìû ïîëó÷èëè òðåáóåìóþ îöåíêó.Çàìå÷àíèå:1m2 )Îöåíèì ÷èñëî èòåðàöèé n0 , òðåáóåìîå äëÿ äîñòèæåíèÿ çàäàííîé òî÷íî-ñòèε:íà ïðàêòèêåηìàëî (η"=O#ln 1εn0 =ñì.
(1.40)ln ρ1√√√1+3 η(1 + 3 η)(1 − η)1√√=ln' ln(1 + 4 η) ' ηln = ln√ρ1− η1−ηÃëàâà 1. ×èñëåííûå ìåòîäû ëèíåéíîé àëãåáðû30n0 (ε) = O1√η= O (m)Ñðàâíèì ñêîðîñòü ñõîäèìîñòè ÏÒÈÌ ñ ìåòîäîì ïðîñòîé èòåðàöèè (ÌÏÈ):xn+1 − xn+ Axn = f,ττ > 0, n = 0, 1, . . . , x0ãäå çàäàíî Ïî ñëåäñòâèþ 2 èç òåîðåìû î ñõîäèìîñòèèòåðàöèîííûõ ìåòîäîâ:kxn+1 − xk ≤ ρkxn − xk,ξ∼ρ=γ11−ξ, ξ=1+ξγ21 11−ξ(1 + ξ)2,' 1 + 2ξ==m2 ρ1+ξ1 − ξ2lnñëåäîâàòåëüíîãäåno (ε) = O(m2 ).11∼ O(ξ) ∼ 2 ,ρmÒàêèì îáðàçîì, ÏÒÈÌ íà ïîðÿäîê áûñòðååÌÏÈ.1.9Ìåòîäû ðåøåíèÿ çàäà÷ íà ñîáñòâåííûå çíà÷åíèÿAx = λx,ãäåA(m × m) x 6= 0, λ(1.49) ñîáñòâåííûå çíà÷åíèÿ A.det(A − λE) = am λm + .
. . + a1 λ + a0ãäåλ = λAk êîðíè 1.50,(1.50)k = 1, m×àñòè÷íàÿ ïðîáëåìà ñîáñòâåííûõ çíà÷åíèé çàêëþ÷àåòñÿ â íàõîæäåíèèîòäåëüíûõ ñîáñòâåííûõ çíà÷åíèé (íàïðèìåð, ìàêñèìàëüíîãî è ìèíèìàëüíîãî). Ïîëíàÿ ïðîáëåìà ñîáñòâåííûõ çíà÷åíèé çàêëþ÷àåòñÿ â íàõîæäåíèèâñåãî ñïåêòðà.1.9.1Ñòåïåííîé ìåòîäxn+1 = Axn , n = 0, 1, . . . , x0 − íà÷àëüíî ïðèáëèæåíèå(1.51)Åñëè ðàññìàòðèâàòü ôîðìóëó (1.51), êàê ðåêóððåíòíîå ñîîòíîøåíèå, òîx n = An x 0Çàíóìåðóåìλkâ ïîðÿäêå íåóáûâàíèÿ èõ ìîäóëåé (òàê êàê îíè ìîãóò áûòüêîìïëåêñíûìè):|λ1 | ≤ |λ2 | ≤ . .
. ≤ |λm |Îãðàíè÷åíèÿ íà A:m1. A - èìåeò áàçèñ èç ñîáòâåííûõ âåêòîðîâ ({ei }1 )1.9. Ìåòîäû ðåøåíèÿ çàäà÷ íà ñîáñòâåííûå çíà÷åíèÿ2. λm−1 λm > 13.x0 = c1 e1 + . . . + cm em , cm 6= 031(òðåáóåòñÿ äëÿ ñõîäèìîñòè)Íà n-îé èòåðàöèè áóäåì èìåòü:xn =mXck λnk ek(1.52)k=1Òàê êàêcm 6= 0,xncm λnmÓñòðåìèìλiλmòî ïîäåëèì íà íåãî:xnc1 n=λ e1 + . . .
+ λnm emcmcm 1c1λ1 ncm−1 λm−1 n=e1 + . . . +em−1 + emcm λmcmλmn → ∞.→ 0.ÒîãäàÒàê êàê ïî âòîðîìó óñëîâèþxn → em|λm | íàèáîëüøèé, òî âñå(ïî íàïðàâëåíèþ).(i)n(i) nx(i)n = c1 e1 λ1 + . . . + cm em λm , i = 1, m(i)(i)n+1xn+1 = c1 e1 λ1n+1 + . . . + cm e(i)m λmÏîäåëèì(i)xn+1íà(i)xn:(i)(i)xn+1=(i)c1 e1 λn+1+ . . . + cm em λn+1m1=(i)(i)c1 e1 λn1 + . . .
+ cm em λnmn+1(i) (i)c1 e1λ1cm em λn+1+ . . . + 1)m ( cm e(i)λmm==n(i)e1(i)λ1cm em λnm ( ccm1 (i)+...+1)λmemnλm−1= λm + Oλm−1(i)xn(i)λ(i)m =xn+1(i)xn, λ(n)m − λm = Oλm−1λmnÈòàê, ìû ðåøèëè ÷àñòè÷íóþ çàäà÷ó íàõîæäåíèÿ ìàêñèìàëüíîãî ïî ìîäóëþñîáñòâåííîãî çíà÷åíèÿ Ñàìî(n)λmìîæíî íàéòè è ñëåäóþùèì ñïîñîáîì:λ(n)m =(Axn , xn )(xn , xn )Ðàññìîòðèì äâà ñëó÷àÿ:1.A = A∗ ,ñëåäîâàòåëüíî∃{ei }m1 îðòîíîðìèðîâàííûé áàçèñ èç ñîá-ñòâåííûõ âåêòîðîâ.λ(n)m =(Axn , xn )(xn+1 , xn )=,(xn , xn )(xn , xn )Ãëàâà 1.
×èñëåííûå ìåòîäû ëèíåéíîé àëãåáðû32xn = c1 λn1 e1 + . . . + λnm emãäå ðàçëîæåíèå ïî îðòîíîðìèðîâàííîìó áàçèñóèç ñîáñòâåííûõ âåêòîðîâ. Òàê êàê áàçèñ îðòîíîðìèðîâàííûé, òî îñòàíóòñÿ(ei , ej ) = 0): 2 2n+1 c1λ1c2m λ2n+11+...+mcmλm= 2 2n =λ122ncm λm 1 + . . . + ccm1λmòîëüêî äèàãîíàëüíûå ýëåìåíòû (òàê êàê(xn+1 , xn )c2 λ2n+1 + .
. . + c21 λ2n+11= m 2m 2n(xn , xn )cm λm + . . . + c21 λ2n1= λm + Oλm−1λm2n ïîëó÷èëè îöåíèêó âûøå, ÷åì ðàíüøå2. A - èìååò áàçèñ{ei }m1èç ñîáñòâåííûõ âåêòîðîâ (íå ïðåäïîëàãàåòñÿ åãîîðòîíîðìèðîâàíîñòü).λ(n)mPmn+1 nλj (ei , ej )i,j=1 ci cj λici cj λni λnj (ei , ej )=n2 2n+1(e1 , e1 )(em , em ) + cm λn+1c2m λ2n+1m cm−1 λm−1 (em , em−1 ) + . . .
+ c1 λ1m=n22n22nncm λm (em , em ) + cm λm cm−1 λm−1 (em , em−1 ) + . . . + c1 λ1 (e1 , e1 )==(Axn , xn )(xn+1 , xn )===(xn , x − n)(xn , x − n)c2m λ2n+1(em , em )(1 +mcm−1cmλm−1λmc2m λ2nm (em , em )(1 +cm−1cmλm−1λm= λm + Oλm−1λmnn(em ,em−1 )(em ,em )+ ... +c1cm(em ,em−1 )(em ,em )+ ... +c1cm2 2 λ1λmλ1λm2n+12n(e1 ,e1 )(em ,em ) )(e1 ,e1 )(em ,em ) )nÌû äîêàçàëè ñëåäóþùåå óòâåðæäåíèåÓòâåðæäåíèå 2. Ïóñòü ìàòðèöà A óäîâëåòâîðÿåò ñëåäóþùèì óñëîâèÿì:1. A - èìåeò áàçèñ èç ñîáòâåííûõ âåêòîðîâ ({ei }m1 )2.
λλm−1 > 1 (òðåáóåòñÿ äëÿ ñõîäèìîñòè)m3. x0 = c1 e1 + . . . + cm em , cm 6= 0Òîãäà, íàéäåííûå ïî ñòåïåííîìó ìåòîäó xn òàêèå, ÷òî:lim xn = em ,n→∞ãäå em - ñîáñòâåííûé âåêòîð, îòâå÷àþùèé ìàêñèìàëüíîìó ïî ìîäóëþñîáñòâåííîìó çíà÷åíèþ. Ìàêñèìàëüíîå ïî ìîäóëþ ñîáñòâåííîå çíà÷åíèåìîæíî íàéòè ïî ôîðìóëàì:(i)λ(i)m =xn+1(i)xn, λ(n)m =Ñ òî÷íîñòüþ:(i)λm= λm + O(xn+1 , xn )(xn , xn )λm−1λmn1.9. Ìåòîäû ðåøåíèÿ çàäà÷ íà ñîáñòâåííûå çíà÷åíèÿÇàìå÷àíèå:33Óñëîâèÿ 1 è 2 íåñêîëüêî îãðàíè÷èâàþò êëàññ çàäà÷, ê êîòîðûìïðèìåíèì ýòîò ìåòîä (õîòÿ îí âñå ðàâíî îñòàåòñÿ äîñòàòî÷íî øèðîêèì).Óòâåðæäåíèå 3. Åñëè åñòü õîòÿ áû 1 êîìïëåêñíîå ñîáñòâåííîå çíà÷åíèåλk = λ0 + iλ1 , λ1 6= 0 Òîãäà, îòâå÷àþùèé åìó ñîáñòâåííûé âåêòîð êîìïëåñíûé è íà÷àëüíîå ïðèáëèæåíèå äëÿ íåãî äîëæíî áûòü êîìïëåêñíûìÄîêàçàòåëüñòâî.x = µ0 + iµ1 , µ1 6= 0A(µ0 + iµ1 ) = (λ0 + iλ1 )(µ0 + iµ1 ) = λ0 µ0 − λ1 µ1 + i(λ0 µ1 + λ1 µ0 )Ñ äðóãîé ñòîðîíû, â ñèëó ëèíåéíîñòè ìàòðèöû A:Aµ0 = λ0 µ0 − λ1 µ1 , Aµ1 = λ0 µ1 + λ1 µ0Åñëèµ1 = 0 ⇒ λ1 µ0 = 0 ⇒ µ0 = 0 ⇒ x = 01.9.2 ïðîòèâîðå÷èåÌåòîä îáðàòíûõ èòåðàöèéAxn+1 = xn , n = 0, 1 .
. . , x0 íà÷àëüíîå ïðèáëèæåíèå(1.53)Ïóñòü ó ìàòðèöû A ñóùåñòâóåò îáðàòíàÿ, òîãäà:xn+1 = A−1 xnÒàêèì îáðàçîì, ìû èìååì ñòåïåííîé ìåòîä äëÿ ìàòðèöû1A−1 , çíàÿ ÷òî λAk =−1 , ìû ìîæåì, ïðåäïîëîæèâ âûïîëíåíèå óñëîâèé 1 3, ñðàçó ñêàçàòü,λAkêóäà áóäåò ñõîäèòñÿ xn Óñëîâèå 3 äîëæíî âûãëÿäåòü ñëåäóþùèì îáðàçîì:x0 = c1 e1 + . . . + cm em , c1 6= 0,à óñëîâèå 2 òàê: λ1 < 1. λ2 Òîãäà ìû ñìîæåì íàéòè ìèíèìàëüíîå ïî ìîäóëþ çíà÷åíèå ìàòðèöû A:−nxn = c1 λ−n1 e1 + . . . + λ m em nnxnc2 λ 1cm λ1= e1 +λn1e2 + .
. . +em .c1c1 λ 2c1 λmÍà êàæäîé èòåðàöèè ìû íîðìèðóåìxn ,ïîýòîìó ïðè óñòðåìëåíèè n êìû ñ÷èòàåì, ÷òî ñëåâà ïðîñòî ñòîèò âåêòîðÏîýòîìó,xn → e1xn .λ1λj(ïî íàïðàâëåíèþ).Çàäà÷à 5. Ïîêàçàòü, ÷òî(n)λ1=(xn , xn ),(xn+1 , xn )(i)(n)λ1=xn(i)xn+1= λ1 + Oλ1λ2n.∞,ñòðåìèòñÿ ê íóëþ.Ãëàâà 1. ×èñëåííûå ìåòîäû ëèíåéíîé àëãåáðû341.9.3Ìåòîä îáðàòíûõ èòåðàöèé ñî ñäâèãîìÈíîãäà íà ïðàêòèêå íóæíî íàéòè êàêîå-òî ñîáñòâåííîå çíà÷åíèå èç âíóòðåííåé ÷àñòè ñïåêòðà.(A − αE)xn+1 = xn , α ∈ R, n ∈ NÏîòðåáóåì ñóùåñòâîâàíèÿ(A − αE)−1 .Òîãäàxn+1 = (A − αE)−1 xn|{z}BÏîëó÷èëè ñòåïåííîé ìåòîä äëÿ ìàòðèöû B:xn+1 = BxnÑîáñòâåííûå çíà÷åíèÿ ìàòðèöû B:÷òî:λBl = maxk=1,m1Òîãäà(λAk −α)λBk =(λAkxn → el , ãäå l òàêîâî,11= A− α)(λl − α)Çàäà÷à 6.
Ïîêàçàòü, ÷òî åñëè äëÿ ìàòðèöû A âûïîëíåíû óñëîâèÿ, àíàëîãè÷íûå 1 - 3, òî(i)λl = lim (α +n→∞Çàìå÷àíèå:xn(i)).xn+1Åñëè èçâåñòíî ãðóáîå ïðèáëèæåííîå çíà÷åíèå êàêîãî-òî ñîá-ñòâåííîãî çíà÷åíèÿ, à ìû õîòèì åãî óòî÷íèòü, òî èñïîëüçóþò ýòîò ìåòîä.Íî ñ ïîìîùüþ ýòîãî ìåòîäà ïðàêòè÷åñêè íåâîçìîæíî íàéòè âåñü ñïåêòð.1.10Ïðèâåäåíèå ìàòðèöû ê âåðõíåé ïî÷òè òðåóãîëüíîé ôîðìåËåã÷å âñåãî íàéòè ñîáñòâåííûå çíà÷åíèÿ ó äèàãîíàëüíîé èëè òðåóãîëüíîéìàòðèöû.Ñëåäîâàòåëüíî íàøà çàäà÷à ïðèâåñòè ìàòðèöóA(m × m)ê òðå-óãîëüíîé.
Îäíàêî ïðèâåäåíèå ìàòðèöû A ê òðåóãîëüíîé ìåòîäîì Ãàóññàíå ñîõðàíÿåò ñïåêòð ìàòðèöû. Ïðåîáðàçîâàíèÿ ïîäîáèÿ ñîõðàíÿþò ñïåêòðìàòðèöû.C = Q−1 AQÎïðåäåëåíèå 11.ìàòðèöû,×Ôîðìà Õåññåíáåðãà (âåðõíÿÿ ïî÷òè òðåóãîëüíàÿ ôîðìà- âîîáùå ãîâîðÿ, íåíóëåâûå ýëåìåíòû)×× × × 0 ×ÂÏÒÔ = 0 0 . . .. ..××0Îïðåäåëåíèå 12.0...×.........................0××..××× . . .. . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
