Численные методы. Ионкин (2012) (v1.1) (косяки есть), страница 4

Òîãäà ìåòîä Çåéäåëÿ ñõîäèòñÿ â ñðåäíåêâàäðàòè÷íîé íîðìåëþáîì íà÷àëüíîì ïðèáëèæåíèè x0 .ÏóñòüïðèÄîêàçàòåëüñòâî:B − 0.5τ A > 0B = D + R1 − 21 (R1 + D + R2 ) > 0⇒ D + R1 − R2 > 0;((D + R1 − R2 )x, x) > 0;(Dx, x) + (R1 x, x) − (R1∗ x, x) > 0;∗ò.ê. (R1 x, x) = (R1 x, x), òî (Dx, x) > 0÷òä.Ñëåäñòâèå 4:A = A∗ > 0(â âåùåñòâåííîì ïðîñòðàíñòâå).Ìåòîä ïðîñòîé èòåðàöèè Åñëè âûáðàòüτ: 0 < τxn+1 −xnτ< γ22 ,+ Axn = f .γ2 = max λAkk(ìîäóëü íå íóæåí, ìàòðèöàïîëîæèòåëüíî îïðåäåëåíà), òîãäà ìåòîä ïðîñòîé èòåðàöèè ñõîäèòñÿ∀x0â ñðåä-íåêâàäðàòè÷íîé íîðìå.[ìåòîä ðåëàêñàöèè] [î÷åíü ïîõîæå íà ïðîèçâîäíóþ ïîâðåìåíè] [ïðîñòåéøèé ñ òî÷êè çðåíèÿ ðåàëèçàöèè] [äâà ïàðàìåòðà äëÿ óñêîðåíèÿ24ñõîäèìîñòè, íî âñòàåò âîïðîñ âûáîðà]Ïðèìå÷àíèå:Íà âòîðîì êóðñå ðàññìàòðèâàëàñü îáóñëîâëåííîñòü.

Òðóäíî ñòðîèòü ñèëüíîðàçáðîñàííûå ñïåêòðû,minÍàïðèìåð, åñëèmaxmin << max, ãðàíèöà äëÿ âûáîðà τ î÷åíü óçêàÿ.= 10−6 , íåëüçÿ τ = 1. ×åì êîìïàêòíåå ñïåêòð, òåìíàìóäîáíåå è áûñòðåå. Ýòè âîïðîñû ìû ðàññìîòðèì â æ¼ñòêèõ ñèñòåìàõ.Äîêàçàòåëüñòâî:Äëÿ ñõîäèìîñòè íåîáõîäèìî1−0.5λAkB − 0.5τ A = 0.Äîëæíî áûòüE − 0.5τ A > 0.> 0.1 − 0.5τ γ2 > 0 - íàñ óñòðàèâàåò.τ < 0 - ïîòîìó ÷òî τ äîëæíî áûòü ïîëîæèòåëüíûì.

ÊàêÎòñþäà τ <káûëî äëÿ óðàâíåíèé òåïëîïðîâîäíîñòè: îò π äî ∞.  ðàçíîñòíîé ñõåìå ìû ýòî2×åðåç ñîáñòâåííûå çíà÷åíèÿ:2γ2 .ïî÷óâñòâóåì, êîãäà áóäåì ñòðîèòü ãðàíèöû.Ÿ 7. Îöåíêà ñêîðîñòè ñõîäèìîñòè èòåðàöèîííûõ ìåòîäîâ ýòîì ïàðàãðàôå ìû áóäåì ïîëó÷àòü îöåíêó ñêîðîñòè ñõîäèìîñòè èòåðàöèîííûõ ìåòîäîâ îöåíèâàòü êîëè÷åñòâî èòåðàöèé äëÿ äîñòèæåíèÿ çàäàííîé òî÷íîñòè è íàõîäèòü îöåíêè ïðè êàêèõ ñîîòíîøåíèÿõ ñõîäèòñÿ èëè ñõîäèëîñü.Ñíà÷àëà ïîëó÷èì îáùèå îöåíêè äëÿ äâóõñëîéíîãî èòåðàöèîííîãî ìåòîäà,ïîòîì áóäåì ïðèìåíÿòü ê êîíêðåòíûì.Ïî-ïðåæíåìó íàì èíòåðåñíà ñèñòåìàAx = f,ãäå|A| =6 0, A ∈ Rm×m .ãäåxn+1 − xnB+ Axn = f,ττ > 0, ∃B −1 , n = 0, 1, ...

x0 çàäàí.v n = xn − xv n+1 − v nB+ Av n = f,τ(1.36)(1.37)(1.38)n = 0, 1, ... v 0 = x0 − x.Ñòàâèì çàäà÷ó ïîëó÷èòü â íîðìàõ îöåíêè âèäà||v n+1 || ≤ ρ||v n ||,25(1.39)n = 0, 1, ... 0 < ρ < 1.Ïîêà íå ôèêñèðóåì íîðìó ãäå óäàñòñÿ. Ýòî ïîêà íå âàæíî.||v n || ≤ ρn ||v 0 ||, n → ∞ ⇒Îòêóäà ñõîäèìîñòü? Ïðèìåíèì êàê ðåêóððåíòíîå.ρn → 0 ⇒ ||v n || → 0ñõîäèòñÿ.Ýòî óæå èçâåñòíî èç òåîðåìû Ñàìàðñêîãî, òåïåðü íåîáõîäèìî íàéòè ñêîðîñòüñõîäèìîñòè.0 < ρ < 1áóäåò áûñòðåå.

ñõîäèìîñòü, ýòî ïîíÿòíî. Êîãäà ïðèáëèæàåìρíàçûâàþò çàòóõàíèåì ïîãðåøíîñòè,ρê 0, ñõîäèòüñÿρ-îöåíêà.Åñëè ïîëó÷èì 1.39, òî ïîëó÷èì íóæíîå êîëè÷åñòâî èòåðàöèé. Ýòî ãëàâíûéêðèòåðèé, ïî êîòîðîìó îòáèðàåì êà÷åñòâî èòåðàöèîííîãî ìåòîäà.(Ðåøèòü çàäà÷ó ñ òî÷íîñòüþ äîε çíà÷èò ïîëó÷èòüÐåêóððåíòíàÿ ôîðìóëà äà¼ò ñîîòíîøåíèåòî÷íîñòè, êîãäàÏåðåâåðí¼ì:n0 (ε) =ln 1εln p1||xn − x|| ≤ ρn ||x0 − x||.Äîáü¼ìñÿnρ ≤ ε.1ε≤Ëîãàðèôìèðóåì:h||xn − x|| ≤ ε||x0 − x||.)i1ρn .n ln p1 ≥ ln 1ε . òîãäàn ≥ n0 (ε),îöåíêà âûïîëíåíà.ln p1 ñêîðîñòü ñõîäèìî-n0 (ε),ñòè èòåðàöèîííîãî ìåòîäà: ÷åì îíà áîëüøå, òåì ìåíüøåòåì ìåíüøå ÷èñëîèòåðàöèé. äàëüíåéøåì ìû íàó÷èìñÿ íàõîäèòü ÷èñëî. Âàæíåéøàÿ çàäà÷à!ρ ïîëó÷àåòñÿ÷åðåç ñïåêòð è èíûìè ìåòîäàìè.H, dim H = m.mP∀x, y ∈ H : (x, y) =xi yi .

||x|| = (x, x)1/2 =Îïÿòü ââîäèì âåùåñòâåííîå ïðîñòðàíñòâîÑêàëÿðíîå ïðîèçâåäåíèå:i=1smPxi y i .i=1B = B ∗ > 0 (ïîêà||x||B = (Bx, x)1/2 .íå ñâÿçàí ñ 1.37, íî ïîòîì áóäåò). Ýíåðãåòè÷åñêàÿ íîðìàÒåîðåìà 1:Ïóñòü∗A = A ∗ > 0, B = B ∗ > 0.B 6= B . Íî ñ òî÷êè∃ρ, 0 < ρ < 1 ⇒(Óæåñòî÷èëè, ó Ñàìàðñêîãî ìîãëî áûòüçðåíèÿ êëàññà çàäà÷ âñ¼ â ïîðÿäêå,1−ρ1+ρB≤A≤Bττ26Bìû âûáèðàåì ñàìè.)(1.40)Òîãäà èòåðàöèîííûé ìåòîä 1.37 ðåøåíèÿ 1.36 ñõîäèòñÿ, è âåðíà îöåíêà:||v n+1 ||B ≤ ρ||v n ||B ,n = 0, 1, .

. .(1.41)(àïðèîðíàÿ îöåíêà).Îòñþäà ìû ìîæåì îöåíèòü ÷èñëî èòåðàöèé.Äîêàçàòåëüñòâî:A≤ρ < 1,1+ρBτ⇒ B − 0.5τ A > 0Çíà÷èò cõîäèìîñòü áóäåò. Íî îöåíêà ïîëó÷àåòñÿ â ýíåðãåòè÷åñêîé íîðìå.Çàìå÷àíèå:Èç 1.41 ìîæíî ïîëó÷èòü è â íîðìå|| · ||A .Óäîáíåå:B íàø âûáîð,A¾çàêàç÷èê¿.(n)-é êA = A∗ ⇒Èäåÿ: äîêàçàòåëüñòâî èç äâóõ ýòàïîâ. Ñòðîèì ìàòðèöó ïåðåõîäà îò(n + 1)-éèòåðàöèè, ñòðîèì å¼ ñïåêòð.

Ó íå¼ âñå|λi | < ρ < 1.À òàê êàêåñòü îðòîíîðìèðîâàííûé áàçèñ ñîáñòâåííûõ âåêòîðîâ.Ïîëó÷èì îöåíêó 1.41:B = B ∗ > 0,òîãäà ñóùåñòâóþòÄîìíîæàåì 1.38 íàÂâîäèìB 1/2 = (B 1/2 )∗ > 0, B −1/2 = (B −1/2 )∗ > 0.B −1/2 : B 1/2 vz n = B 1/2 v n .n+1−v nτ+ B −1/2 Av n = 0.Äîñòàòî÷íî äëÿ 1.41 ïîëó÷èòü îöåíêó||z n+1 || ≤ ρ||z n ||(1.42)||z n ||2 = (zn , zn ) = (B 1/2 v n , B 1/2 v n ) = (Bv n , v n ) = ||v n ||B .n−1/2 nîòñþäà v = Bz . ñàìîì äåëå:Êñòàòè,Óðàâíåíèå ïðèìåò âèä:z n+1 − z n+ B −1/2 AB −1/2 z n = 0τÂûðàæàåìz n+1 :z n+1 = z n − τ B −1/2 AB −1/2 z n = Sz nS = E − τ B −1/2 AB −1/2ÏîìåòèìSek = sk ek , k = 1...m, lk 6= 0, sk = eigenvalues(çàäà÷àíûå çíà÷åíèÿ).27(1.43)íà ñîáñòâåí-Ñàìîñîïðÿæ¼ííîñòüS:1S ∗ = (E − τ B −1/2 AB −1/2 )∗ = E ∗ − τ (B −f rac12 )∗ A∗ (B − 2 )∗ =111E − τ (B ∗ )− / 2 A(B ∗ )− 2 = E − τ B −f rac12 AB − 2 = SÑàìîñîïðÿæ¼ííîñòüBÍàäî äîêàçàòü, ÷òî- ýòî î÷åíü óäîáíî.|sk | ≤ ρ.Çàäà÷à íà ñîáñòâåííûå çíà÷åíèÿ:11(E − τ B − 2 AB − 2 )ek = sk ek ,ek 6= 0, k = 1...m.Îáîçíà÷èì11(B 2 − τ AB − 2 )ek = sk B 1/2 ek .11y = B − 2 ek .

ek = B 2 y, y 6= 0.Ïîäåéñòâóåì íà âñ¼Ïåðåïèñûâàåì çàäà÷ó:(B − τ A)y = sk By.Îòñþäàτ Ay = (1 − sk )ByèëèAy =1 − skBy.τÏîäñòðîèëèñü ïîä 1.40. Ýòî îçíà÷àåò åñëè ñêàëÿðíî óìíîæèì íà(Ay, y) =y 6= 0:1 − sk(By, y)τ×åðåç 1.40:1−ρ1 − sk1+ρ(By, y) ≤(By, y) ≤(By, y),τττ(By, y) > 0 èç y 6= 0! Òàê è ñîêðàòèì: |sk | ≤ ρ, k = 1...m.D = D∗ ⇒ ∃ îðòîíîðìèðîâàííûé áàçèñ ñîáñòâåííûõ âåêòîðîâ.Ó ñàìîñî-ïðÿæ¼ííûõ íåò çàìêíóòîé òåîðèè. Ïðîïàäàþò çàìå÷àòåëüíûå êà÷åñòâà, âìåñòîðàâåñòâà Ïàðñåâàëÿ íåðàâåíñòâî Ðèñà.Dek = dk lk , k = 1...m, (lk , leP) = δkl = (k == l).2∀x ∈ H : x = c1 e1 + ...

+ ck ek . Òîãäà ||x|| =i = 1mc2i . Ýòî ðàâåíñòâîÔîðìàëüíî:Ïàðñåâàëÿ. Îíî åù¼ âñòðåòèòñÿ â ýòîì êóðñå.Òåïåðü äîêàæåì îöåíêó äëÿÐàñêëàäûâàåì ïî áàçèñózn =X(n)z : z n+1 = Sz n .Ïîìíèì:Sek = sk ek , k = 1...m.⇒k = 1mck lk =X(n)k = 1mck Sek =28X(n)k = 1mck sk ekÍàéäåìPêîýôôèöèåíòû(n)k = 1m ck2ÏîÏàðñåâàëþ(äâàæäû):||z n+1 ||2=s2k .||zÒî åñòüÔóðüå.n+1 2|| ≤ ρ||z n+1 || ≤ ρ||z n ||.2Xk = 1m(n)ck2= ρ2 ||z n ||2Óñëîâèé îêàçàëîñü äîñòàòî÷íî äëÿ 1.41.÷òä.Ñëåäñòâèå 1:A = A∗ > 0, B = B ∗ > 0, ∃γ2 > γ1 > 0: γ1 B ≤ A ≤ γ2 B .2Òîãäà, åñëè τ = τ0 =γ1 +γ2 , òî âûïîëíÿåòñÿ îöåíêà 1.41:||v n+1 ||B ≤ ρ||v n ||B ,ρ=1−ξ1+ξ ,ξ=γ1γ2 .Ãàììû ýòî âåðõíÿÿ/íèæíÿÿ ãðàíèöà ïî ìîäóëþ çàäà÷è íà ñîáñòâåííûåçíà÷åíèÿ.Ïîïàäàåì â óñëîâèå òåîðåìû:2Ñêëàäûâàåì:τÂû÷èòàåì:Òîãäàρ== γ1 + γ2 ; τ =γ2 − γ1 = 2ρτ .γ2 −γ121−ρτ =2γ1 +γ2 .γ1 ,1+ρτ= γ2 .γ·2γ1 +γ2=1− γ1γ21+ γ1=21−ξ1+ξ .Ìàòåìàòèêè õîòÿò ðåøèòü ìàêñèìàëüíî øèðîêèé êëàññ çàäà÷, íî íàäî äàâàòüäîñòàòî÷íûå óñëîâèÿ äëÿ íåîáðàçîâàííûõ èíæåíåðîâ.

;)Ñëåäñòâèå 2:Ìåòîä ïðîñòîé èòåðàöèè:xn+1 − xn+ Axn = fτA = A∗ > 0,γ1 = min1≤k≤m λAk,γ2 = max1≤k≤m λAk (γ2 > γ1 > 0Ïóñòüàâòîìàòè÷åñêè),Òîãäà||v n+1 || ≤ ρ||v n ||, ρ =ãäåξ- ÷èñëî îáóñëîâëåííîñòè!29τ=2γ1 +γ2 .1−ξγ1, ξ= ,1+ξγ2Äîêàçàòåëüñòâî:×åðåç Ñëåäñòâèå 1:B = E , γ1 E ≤ A ≤ γ2 E , || · ||B = || · ||E = || · ||,äàëüøåðàññóæäåíèÿ àíàëîãè÷íûå.÷òä.Ÿ 8. Èññëåäîâàíèå ñõîäèìîñòè ïîïåðåìåííîãî òðåóãîëüíîãî èòåðàöèîííîãî ìåòîäà(ÏÒÈÌ)Ðåøàåì ÑËÀÓ:Ax = fãäå(1.44)detA 6= 0, A(m, m)A = R1 + R2 , ãäå0.5a11 a12 a13 .

. . a1m0.5a22 a23 . . . a2m , R2 =  0 ...... ... ......000 . . . 0.5ammÐåøèì ýòó ñèñòåìó ÏÒÈÌ. Äëÿ ýòîãî ïðåäñòàâèì ìàòðèöó0.5a1100 a21 0.5a22 0R1 =  .........am1am2 am3...0...0....... . . 0.5ammÒîãäà îïåðàòîðxn+1 − xn+ Axn = f,B = (E + wR1 )(E + wR2 ) ⇒ Bτn = 1, 2, . . . , τ > 0, w > 0, xçàäàíî.(1.45)Ìåòîä ñóãóáî íåÿâíûé èç-çà îïåðàòîðà B. Ðåàëèçàöèÿ ìåòîäà ïðîáëåì íåâûçûâàåò.τ, w- èòåðàöèîííûå ïàðàìåòðû.Òåîðåìà1: (î äîñòàòî÷íîì óñëîâèè ñõîäèìîñòè)Ïóñòü ìàòðèöà A - ñàìîñîïðÿæåííàÿ è ïîëîæèòåëüíî îïðåäåëåíà0).Ïóñòüw>τ4⇒(A = A∗ >èòåðàöèîííûé ìåòîä 1.45, ðåàëèçóþùèé çàäà÷ó 1.44, ñõîäèòñÿâ ñðåäíåé êâàäðàòè÷íîé ôîðìå ïðè ëþáîì íà÷àëüíîì ïðèáëèæåíèè.Äîêàçàòåëüñòâî:⇒ B − 0.5τ A > 0.A = A∗ ⇒ R1 = R2∗ ⇒Îïèðàåìñÿ íà òåîðåìó ÑàìàðñêîãîÐàññìîòðèì îïåðàòîð B.

Ò.ê.B = (E + wR2∗ )(E + wR2 ) = E + w(R2∗ + R2 ) + w2 R2∗ R2 = E + wA + w2 R2∗ R2Çàïèøåì B ïî-äðóãîìó:B = (E − wR2∗ )(E − wR2 ) + 2wA.30E − wR2 = C ⇒ C ∗ = E − wR2∗ ⇒ (C ∗ Cx, x) = (Cx, Cx) ≥ 0 ⇒(E − wR2∗ )(E − wR2 ) ≥ 0. Òàêèì îáðàçîì B ≥ 2wA.ÏóñòüÒàêæå èç òåîðåìû ÑàìàðñêîãîB ≥ 2wA > 0.5τ A.Òîãäà⇒ B ≥ 0.5τ A.Ïî ñâîéñòâó òðàíçèòèâíîñòè2w > 0.5τ, w >τ4.

Âýòîì ñëó÷àå ðàáîòàåò äîñòàòî÷íîå óñëîâèå ò. Ñàìàðñêîãî.÷òä.Òåïåðü ïîêàæåì, ÷òî ñêîðîñòü ñõîäèìîñòè ÏÒÈÌ ãîðàçäî âûøå îñòàëüíûõìåòîäîâ.Òåîðåìà 2: Îá îöåíêå ñêîðîñòè ñõîäèìîñòè ÏÒÈÌ (Äîñòàòî÷íîåóñëîâèå)Ïóñòü A ñàìîñîïðÿæåííûé ïîëîæèòåëüíûé îïåðàòîð, ò.å.ñóùåñòâóþò êîíñòàíòûδ > 0, ∆ > 0.w=√2 ,∆δτ=ÏóñòüÏóñòü äëÿ íèõ âûïîëíåíû óñëîâèÿ:A ≥ δE1 , R2∗ R2 ≤ÏîëîæèìA = A∗ > 0.∆A42γ1 +γ2 , ãäå√√∆δδ∆δ√ , γ2 =γ1 = √2 δ+ ∆4γ1 , γ2(1.46)(1.47)- êîíñòàíòû.Òîãäà èòåðàöîííûé ìåòîä 1.45 ñõîäèòñÿ, è äëÿ íåãî ñïðàâåäëèâà îöåíêàkv n+1 kB ≤ ρkv n kB ,√1− ηδρ=√ , η=1+3 η∆Çäåñüóñëîâèé:B = (E + wR2∗ )(E + wR2 ).0 < ρ < 1, δ < ∆.δ < ∆,íà îñíîâàíèè Cëåäñòâèÿ 1.Ñëåäñòâèå 1:ÏóñòüA = A∗ , B = B ∗ ,åñëè(1.49)Äëÿ ñõîäèìîñòè íåîáõîäèìî âûïîëíåíèå 2-õÄîêàçàòåëüñòâî:Óáåäèìñÿ, ÷òî(1.48)γ1 > γ2 > 0 ⇒kxn+1 − xkB ≤ ρ(w), kxn − xkB , ρ(w) =.311 − ξ(w)γ1 (w), ξ(w) =1 + ξ(w)γ2 (w)Ïîñêîëüêóρ - ïåðåìåííàÿ âåëè÷èíà, òî äëÿ íå¼ íåîáõîäèìî íàéòè min.  ýòîéòî÷êå áóäåò ñàìàÿ áûñòðàÿ ñõîäèìîñòü.ÈçA ≥ δE ⇒ (Ax, x) ≥ δ(x, x) = δkxk2∆∆(Ax, x) ⇒ kR2 xk2 ≤ (Ax, x)44∗(Ax, x) = (R2 x, x) + (R2 x, x)(R2∗ R2 x, x) ≤Ò.ê.