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

0 a21 0 . . . 0S=.... .. ......am1 am2 . . . 0 íèæíåòðåóãîëüíàÿ ìàòðèöà. Îòíîñèòåëüíî ïåðâîé ïîáî÷íîé äèàãîíàëè, ñ íóëÿìè íà ãëàâíîé äèàãîíàëèa11 0 . . . 0 0 a22 . . . 0 D=.... .. ......0 0 . . . amm äèàãîíàëüíàÿ ìàòðèöà,0 a12 . . . a1m0 0 . . . a2m R2 =  ... ... . . . ...

0 0 ... 0âåðõíåòðåóãîëüíàÿ ìàòðèöà ñ íóëÿìè íà ãëàâíîé äèàãîíàëè.Ìîæåì ïåðåïèñàòü ñèñòåìó â ìàòðè÷íîì âèäå. (Ïîçæå ìû óâèäèì, ÷òî òîãäàâñå èòåðàöèîííûå ìåòîäû, êîòîðûå ìû èçó÷àåì, èññëåäóþòñÿ åäèíûì îáðàçîì - âýòîì çàñëóãà Ñàìàðñêîãî).R1 x + Dx + R2 x = fDx = f − R1 x − R2 xÏðåäïîëîæèì, ÷òî ìàòðèöà D èìååò îáðàòíóþ (ò.å.aii îòëè÷íû îò íóëÿ). Òîãäà:x = D−1 f − D−1 R1 x − D−1 R2 xÇàïèøåì ìåòîäû ßêîáè è Çåéäåëÿ (âåêòîð íà÷àëüíîãî ïðèáëèæåíèÿx0òàêæå, êàê è ðàíüøå, ñ÷èòàåì çàäàííûì):Dxn+1 = f − R1 xn − R2 xn(1.21)(D + R1 )xn+1 = f − R2 xn(1.22)- ìåòîä ßêîáè,- ìåòîä Çåéäåëÿ.Ìîæåì èõ ïåðåïèñàòü è â áîëåå óäîáíîì âèäå:D(xn+1 − xn ) + Axn = f16(1.23)(D + R1 )(xn+1 − xn ) + Axn = f(1.24)Èç ïîñëåäíåãî ïðåäñòàâëåíèÿ õîðîøî âèäíî, ÷òî ïðè íàëè÷èè ñõîäèìîñòè ìåòîäà ìû ïðèõîäèì (â ïðåäåëå) ê òî÷íîìó ðåøåíèþ ñèñòåìû.Òàê ìû ïðèõîäèì ê êàíîíè÷åñêîìó âèäó èòåðàöèîííûõ ìåòîäîâ.Îïðåäåëåíèå:Êàíîíè÷åñêîé ôîðìîé çàïèñè äâóõñëîéíîãî èòåðàöèîííîãî ìåòîäà ðåøåíèÿñèñòåìû 1.17 íàçûâàåòñÿ åãî çàïèñü â âèäå:xn+1 − xnBn+1+ Axn = f, n = 0, 1, .

. . ;τx0- çàäàí,τn+1 > 0- èòåðàöèîííûé ïàðàìåòð,Bn+1(1.25)- îáðàòèìàÿ ìàòðèöà.Ïðèìå÷àíèå:Çà÷åì íóæåí ïîëîæèòåëüíûé èòåðàöèîííûé ïàðàìåòð? Ýòî ïîçâîëÿåò óñêîðèòü ñêîðîñòü ñõîäèìîñòè. Âûáîð èòåðàöèîííîãî ïàðàìåòðà - ýòî öåëàÿ òåîðèÿ.Ìû êîñíåìñÿ ýòîãî âîïðîñà äàëåå.ÅñëèBn+1 = E ,òî ìåòîä 1.26 íàçûâàåòñÿ ÿâíûì. ÅñëèBn+1 = B, τn+1 = τ ,òî ìåòîä íàçûâàþò ñòàöèîíàðíûì.Ïðèìå÷àíèå:Çäåñü èìååòñÿ íåêîòîðàÿ òåðìèíîëîãè÷åñêàÿ íåòî÷íîñòü: êîíå÷íî, åñëè äàæåìàòðèöàBn+1íå ÿâëÿåòñÿ åäèíè÷íîé, ìû ìîæåì íàéòè ÿâíûå ôîðìóëû ðåøåíèÿ.Íî ìû âñ¼-òàêè ïðèäåðæèâàåìñÿ ôîðìàëüíîãî îïðåäåëåíèÿ.Ðàññìîòðèì è äðóãèå ìåòîäû:Ìåòîä ïðîñòîé èòåðàöèè (ÏÈ) çàäàåòñÿ ñëåäóþùèì îáðàçîì:xn+1 − xn+ Axn = f, τ > 0ττ = τnÅñëè çàìåíèòü â ïîñëåäíåé ôîðìóëå- ïåðåìåííûé ïàðàìåòð, òî ïðè-õîäèì ê ìåòîäó Ðè÷àðäñîíà (â êîòîðîì äëÿ áûñòðîé ñõîäèìîñòè ðåêîìåíäóåòñÿâûáèðàòü òàê íàçûâàåìûé ÷åáûøåâñêèé íàáîð ïàðàìåòðîâ).Ðàññìîòðèì ïîïåðåìåííî-òðåóãîëüíûé èòåðàöèîííûé ìåòîä (åãî òàê æå íàçûâàþò ìåòîäîì Ñàìàðñêîãî).ÏóñòüA = R1 + R2 ,ãäå a112 a21R1 = ...0a222............am1 am2 .

. .1700 ..  ,.amm2 a1120R2 =  ...0a12 . . . a1ma22. . . a2m 2.... .....0 . . . amm2Ïîïåðåìåííî-òðåóãîëüíûé èòåðàöèîííûé ìåòîä (ÏÒÈÌ) çàäà¼òñÿ ôîðìóëîé:(E + ωR1 )(E + ωR2 )x0xn+1 − xn+ Axn = f, n = 0, 1, . . . ;τn+1(1.26)- çàäàííîå íà÷àëüíîå ïðèáëèæåíèå.Ìåòîä, êîíå÷íî, íå ÿâëÿåòñÿ ÿâíûì. Íî ìû îðãàíèçóåì ïðîöåññ òàê, ÷òîáûâû÷èñëÿòü êàæäóþ èòåðàöèþ ïî ÿâíûì ôîðìóëàì.Ââåäåì îáîçíà÷åíèÿ:wn+1 = (E + ωR2 )v n+1 ,ãäåv n+1 =xn+1 −xnτrn = f − Axn âåëè÷èíà, íàçûâàåìàÿ íåâÿçêîé.Òîãäà ðåàëèçàöèþ ìåòîäà âûïîëíÿåì â 3 ýòàïà:•1-ûé ýòàï:(E + ωR1 )wn+1 = rn ⇒wn+1 .•2-îé ýòàï:(E + ωR2 )v n+1 = wn+1 ⇒v n+1 .•îáðàùàÿ íèæíþþ òðåóãîëüíóþ ìàòðèöó, íàõîäèìîáðàùàÿ âåðõíþþ òðåóãîëüíóþ ìàòðèöó, íàõîäèì3-èé ýòàï:xn+1 = xn + τ v n+1 .18Ÿ 6. Òåîðåìû î ñõîäèìîñòè èòåðàöèîííûõ ìåòîäîâÐàññìîòðèì åùå îäèí ìåòîä ðåøåíèÿ ÑËÀÓ:Ax = f,ãäåA- íåâûðîæäåííàÿ ìàòðèöà ðàçìåðà(1.27)m×mÐàññìîòðèì ìåòîä:ãäåτ > 0, B-xn+1 − xn+ Axn = fBτ0îáðàòèìàÿ, n = 0, 1, 2..

; x - çàäàííîå(1.28)íà÷àëüíîå óñëîâèå.Ãîâîðÿ î ñõîäèìîñòè, íàäî ïîíèìàòü î êàêîé íîðìå äëÿ ñõîäèìîñòè èäåò ðå÷ü.Ââåäåì íîðìû.ÏóñòüH- ëèíåéíîå ïðîñòðàíñòâî ðàçìåðíîñòèm,ò.å.Ïîêà ÷òî ìû íå áóäåì ãîâîðèòü î òîì, ñ÷èòàåì ëè ìû∀x ∈ HHx = (x1 , ..xm )âåùåñòâåííûìè èëèêîìïëåêñíûìè ÷èñëàìè.Ââåäåì ñêàëÿðíîå ïðîèçâåäåíèå:(x, y) =mPxi ȳii=1Òîãäà çà íîðìó ìîæíî âçÿòükxk =p(x, x)Ðàññìîòðèì ñàìîñîïðÿæåííûé îïåðàòîð- ñðåäíåêâàäðàòè÷íàÿ íîðìà.D = D∗.Ïðèìå÷àíèå:Ïîíÿòèÿ ìàòðèöà è îïåðàòîð äëÿ íàñ áóäóò ñèíîíèìàìè.Ñàìîñîïðÿæåííûé îïåðàòîðDâCîáëàäàåò òàêèì ñâîéñòâîì, ÷òî∀x ∈ C (Dx, x) ∈ RÒîãäà ìîæíî ñâÿçàòü íîðìó ñ ñàìîñîïðÿæåííûì îïåðàòîðîì. Òàêæå ìîæíîââåñòè ýíåðãåòè÷åñêóþ íîðìó:1kxkD = (Dx, x) 2 ,ãäåD- ñàìîñîïðÿæåííûé îïåðàòîð.Ê ïðèìåðó, åñëè D - åäèíè÷íàÿ ìàòðèöà, òî ìû ïîëó÷èì îáû÷íóþ ñðåäíåêâàäðàòè÷íóþ íîðìó.Îïðåäåëåíèå:ÎïåðàòîðD-ïîëîæèòåëüíî0 ∀x 6= 019îïðåäåëåí,åñëè(Dx, x) >Îïðåäåëåíèå:D - íåîòðèöàòåëüíûé, åñëè (Dx, x) ≥ 0 ∀x.

Òàêèì îáðàçîì ìîæåòñóùåñòâîâàòü x0 : (Dx0 , x0 ) = 0, ò.å. íåîòðèöàòåëüíûé îïåðàòîð ìîæåò áûòü íåÎïåðàòîðïîëîæèòåëüíî îïðåäåëåííûì.Ñâîéñòâà ïîëîæèòåëüíûõ ñàìîñîïðÿæåííûõ îïåðàòîðîâ1.∃δ > 0çíà÷åíèåì: (Dx, x) ≥ δkxk2îïåðàòîðà D .- çäåñüδáóäåò ñâÿçàíî ñminñîáñòâåííûì2. Ñëåäóþùèé ôàêò ïðåäëàãàåòñÿ â âèäå çàäà÷è:Çàäà÷à 1:ÏóñòüH- âåùåñòâåííîå ïðîñòðàíñòâî, à îïåðàòîðäåëåííûé, íî íå ñàìîñîïðÿæåííûé.

Äîêàçàòü, ÷òîC - ïîëîæèòåëüíî îïðå∗(Cx, x) = ( C+C2 x, x)Ðåøåíèå:ÏîñêîëüêóH-âåùåñòâåííîå ïðîñòðàíñòâî, ñïðàâåäëèâî(Cx, x) = (x, C ∗ x) = (C ∗ x, x), ∀x ∈ HC + C∗ C − C∗C=+⇒22C + C∗C − C∗(Cx, x) = (, x) + (, x) =22C + C∗1C + C∗∗(, x) + ((C x, x) − (Cx, x)) = (x, x)222D = D∗ è D > 0,(D−1 )∗ è D−1 > 03. ÅñëèÁîëåå òîãîÁîëåå òîãî1òîãäà1∃D−1- îáðàòíûé îïåðàòîð, òàêîé ÷òî1∃D 2 = (D 2 )∗ è D 2 > 0111∃D− 2 = (D− 2 )∗ è D− 2 > 04. Ââåäåì âåêòîðvn:v n = xn − xìåòîä ñõîäèëñÿ, íåîáõîäèìî,Òàêèì îáðàçîì, ìû ïîëó÷èëè çàäà÷ó äëÿxn(1.29)n-îé èòåðàöèè. Äëÿ òîãî, ÷òîáû èòåðàöèîííûén÷òîáû kv k → 0 ïðè n → ∞.Ýòîò âåêòîð - ïîãðåøíîñòü íàÂûðàçèâD−1 =vn.èç 1.29 è ïîäñòàâèâ â 1.28, ïîëó÷àåì:20ãäåv n+1 − v n+ Av n = 0,Bτ00v = x − x.n = 0, 1, 2, ...,(1.30)Ïîëó÷èëè àíàëîãè÷íîå, íî îäíîðîäíîå óðàâíåíèå .ÏóñòüB- îáðàòèìûé îïåðàòîð, òîãäà, äîìíîæèâ íàB −1 ,ïîëó÷èì:v n+1 − v n+ B −1 Av n = 0τÐàçðåøèì îòíîñèòåëüíî ïåðâîãî ñëîÿ:v n+1 = v n − τ B −1 Av n = (E − τ B −1 A)v nÎáîçíà÷èì ÷åðåçS:S = E − τ B −1 AÌàòðèöàS(1.31)íàçûâàåòñÿ ìàòðèöåé ïåðåõîäà îòèòåðàöèè, ò.å.vn+1= Svnn-îéèòåðàöèè ê(n + 1)-îé.Âñå ñâîéñòâà ïðîöåññà çàâèñÿò îòS,à èìåííî îò ñïåêòðà ìàòðèöûS.Òåîðåìà 1 (áåç äîêàçàòåëüñòâà):Èòåðàöèîííûé ìåòîä 1.28 ðåøåíèÿ çàäà÷è 1.27 ñõîäèòñÿ ïðè ëþáîì íà÷àëüíîìïðèáëèæåíèèSx0òîãäà è òîëüêî òîãäà, êîãäà âñå ñîáñòâåííûå çíà÷åíèÿ ìàòðèöûïî ìîäóëþ ìåíüøå åäèíèöû:Ïðèìå÷àíèå:| λs |< 1.Ýòà òåîðåìà î÷åíü ðåäêî ïðèìåíèìà â ÷èñòîì âèäå.H - êàê âåùåñòâåííîå ïðîñòðàíñòâî.R, áóäóò ñèììåòðè÷åñêèìè.Îïÿòü ðàññìàòðèâàåìöû, ñàìîñîïðÿæåííûå âÎ÷åâèäíî, ìàòðè-Òåîðåìà 2 (òåîðåìà Ñàìàðñêîãî î äîñòàòî÷íûõ óñëîâèÿõ ñõîäèìîñòèäâóõñëîéíûõ èòåðàöèîííûõ ìåòîäîâ):ÏóñòüA = A∗ > 0, τ > 0- ïîëîæèòåëüíûé ïàðàìåòð, è âûïîëíåíî:B − 0.5τ A > 0(1.32)Òîãäà èòåðàöèîííûé ìåòîä 1.28 ðåøåíèÿ ñèñòåìû 1.27 ñõîäèòñÿ ïî ñðåäíåêâàäðàòè÷íîé íîðìå ïðè ëþáîì íà÷àëüíîì ïðèáëèæåíèèmX1kx − xk = ((xni − xi )2 ) 2 → 0,ni=121x0:n → ∞ ∀x0(1.33)Óñëîâèå 1.32 íàçûâàåòñÿ óñëîâèåì Ñàìàðñêîãî.Äîêàçàòåëüñòâî:Ââåäåì ÷èñëîâóþ ïîñëåäîâàòåëüíîcòüñíèçó:yn : yn = (Av n , v n );yn- îãðàíè÷åíàyn ≥ 0;Ðàññìîòðèìyn+1 :yn+1 = (Av n+1 , v n+1 ) = (ASv n , Sv n ) = (A(E − τ B −1 A)v n , (E − τ B −1 A)v n ) == (Av n , v n ) − τ [(Av n , B −1 Av n ) + (AB −1 Av n , v n ) − τ (AB −1 Av n , B −1 Av n )] == yn − τ [2(Av n , B −1 Av n ) − τ (AB −1 Av n , B −1 Av n )] == yn − 2τ ((B − 0.5τ A)B −1 Av n , B −1 Av n ))Ïîëó÷åííîå òîæäåñòâîyn+1 = yn − 2τ ((B − 0.5τ A)B −1 Av n , B −1 Av n ));îáû÷íî ïåðåïèñûâàþò â ñëåäóþùåì âèäå:yn+1 − yn+ 2((B − 0.5τ A)B −1 Av n , B −1 Av n ) = 0;τ(B − 0.5τ A)B −1 Av n , B −1 Av n ≥ 0;Çíà÷èò yn+1 ≤ yn , ñëåäîâàòåëüíî yn íèæíåå îãðàíè÷åíèå: ∃ lim yn = yÇäåñüìîíîòîííî óáûâàåò è èìååò ìåñòîn→∞ÏóñòüH ∈ R; C > 0,òîãäà∃δ > 0 : (Cx, x) ≥ δkxk2Ýòî ñëåäóåò èç ñâîéñòâà ïîëîæèòåëüíîãî îïåðàòîðàò.ê.B = 0.5τ A > 0,C.òî:∃δ > 0 : ((B − 0.5τ A)B −1 Av n , B−1Av n ) ≥ δkB −1 Av n k2(1.34)Ïðèìåíÿÿ äàííîå íåðàâåíñòâî, ìîæíî çàâåðøèòü äîêàçàòåëüñòâî òåîðåìû:Äëÿ óäîáñòâà ââåäåìyn+1 − yn+ 2δkB −1 Av n k2 ≤ 0;τnW = B −1 Av n .Îòñþäà âèäíî, ÷òî åñëèn → ∞,òîkW n k → 022Òåïåðü ìîæíî âûðàçèòü ïîãðåøíîñòü:v n = A−1 BW nò.å.n→∞kv n k ≤ kA−1 BkkW n k⇒ kv n k −→ 0÷òä.Ñëåäñòâèå 1:ÏóñòüA = A∗ > 0(ìàòðèöàAñàìîñîïðÿæåííàÿ è ïîëîæèòåëüíàÿ)Òîãäà ìåòîä ßêîáè ñõîäèòñÿ â ñðåäíåêâàäðàòè÷íîé íîðìå ïðè ëþáîì íà÷àëüíîì ïðèáëèæåíèè, åñëè âûïîëíåíîìåòîäå ßêîáè, ãäå(òóòD- äèàãîíàëüíàÿ ìàòðèöà âA = R1 + D + R2 )Äîêàçàòåëüñòâî:Ìåòîä ßêîáè:2D > ADxn+1−xnτ+ Axn = f ,B = D, τ = 1ãäåB − 0.5τ A > 0 ⇒ D − 0.5A > 0 ⇒ 2D > A⇒ âûïîëíåíû óñëîâèÿ òåîðåìû Ñàìàðñêîãî, òîãäàñëåäñòâèå âûïîëíÿåòñÿ.÷òä.Ñëåäñòâèå 2:ÏóñòüA = A∗ > 0.

Ïóñòü òàêæå A - ìàòðèöà ñî ñòðîãèì äèàãîíàëüíûì ïðåîá-ëàäàíèåì, ò.å. ýëåìåíò äèàãîíàëè áîëüøå ñóììû îñòàëüíûõ â ñòðîêå:aii >mX|aij |(1.35)j=1i6=jÒîãäà ìåòîä ßêîáè ñõîäèòñÿ ïðè ëþáîì íà÷àëüíîì ïðèáëèæåíèèx0â ñðåäíå-êâàäðàòè÷íîé íîðìå.Äîêàçàòåëüñòâî:Ðàññìîòðèì êâàäðàòè÷íóþ ôîðìó:(Ax, x) =m XmXaij xi xj ≤m XmXi=1 j=1i=1Ïî ñâîéñòâó, àíàëîãè÷íîìóm mm XmX1 XX2|aij ||xi ||xj | ≤ (|aij ||xi | +|aij ||xj |2 ) =2 i=1 j=1j=1i=1 j=12ab ≤ a2 + b2 ,ýòî ðàâíîmmX1X2|aij ||xi | ) · 2 =|aij ||xi |2(2 i,j=1i,j=123ÒîãäàmX(Ax, x) ≤2|aij ||xi | =i,j=1mXx2i (aiii=1+mX|aij |)j=1i6=j÷òä.Çàäà÷à 3:ÏóñòüA = A∗ > 0.aii > 0;Äîêàçàòü, ÷òîÐåøåíèå:Èç 1.35 ñëåäóåò, ÷òî:aii +mX|aij | < 2aiii,j=1ÒîãäàmXx2i (aiii=1+mX|aij |) <j=1mX2aii x2i = (2Dx, x) ⇒ 2D > Ai=1Ïðèìåíåíèå Ñëåäñòâèÿ 1 çàâåðøàåò äîêàçàòåëüñòâî.÷òä.Ñëåäñòâèå 3:A = A∗ > 0.