Численные методы. Ионкин (2009), страница 3

. ; x0R1 + R2 = A,···0···0 . ,... ..· · · amm2ãäå çàäàí(5)Òåîðåìû î ñõîäèìîñòè èòåðàöèîííûõ ìåòîäîâa16a1ma2m . .. .a12 · · ·a22···21120R2 =  .. .0.....0···.amm2Ðåàëèçàöèÿ ïîïåðåìåííî-òðåóãîëüíîãî èòåðàöèîííîãî ìåòîäà ìîæåò áûòü îñóùåñòâëåíà ïî ÿâíûì ôîðìóëàì. Ïóñòü:v n+1 =xn+1 − xnτn+1wn+1 = (E + ωR2 )v n+1rn = f − AxnÒîãäà:(E + ωR1 )wn+1 = rn ,ãäå(E + ωR1 )íèæíåòðåóãîëüíàÿ ìàòðèöà,Èç ýòîãî óðàâíåíèÿ, ïóòåì îáðàùåíèÿ íèæíåòðåóãîëüíîé ìàòðèöû ïî ÿâíûì ôîðìóëàì âûïèn+1ñûâàåòñÿ âåêòîð ω.(E + ωR2 )v n+1 = wn+1 ,ãäå(E + ωR2 )âåðõíåòðåóãîëüíàÿ ìàòðèöà,n+1Ïî èçâåñòíîìó âåêòîðó ω, îáðàùàÿ âåðõíåòðåóãîëüíóþ ìàòðèöó ïî ÿâíûì ôîðìóëàì ìîæíîn+1íàéòè âåêòîð v, è äàëåå:xn+1 = xn + τn+1 v n+1 .Òàêèì îáðàçîì, íåñìîòðÿ íà òî, ÷òî ÏÒÈÌ - íåÿâíûé èòåðàöèîííûé ìåòîä, åãî ðåàëèçàöèÿïðîñòà è ñâîäèòñÿ ê ïîïåðåìåííîìó îáðàùåíèþ íåæíåòðåóãîëüíîé è âåðõíåòðåóãîëüíîé ìàòðèö(îòñþäà - íàçâàíèå ìåòîäà).Ÿ6Òåîðåìû î ñõîäèìîñòè èòåðàöèîííûõ ìåòîäîâÐàññìîòðèì ìàòðè÷íîå óðàâíåíèå âèäàAx = f,ãäåA ìàòðèöà ðàçìåðà(1)(m × m), |A| =6 0Ðàññìîòðèì òàêæå ìàòðè÷íîå óðàâíåíèå âèäàxn+1 − xn+ Axn = f,Bτãäån = 0, 1, 2, .

. . , ∃B −1 ,è çàäàí âåêòîð íà÷àëüíîãî ïðèáëèæåíèÿÐàññìîòðèì ëèíåéíîå ïðîñòðàíñòâî H, òàêîå ÷òîdim H = mÂîçüìåì 2 ïðîèçâîëüíûõ âåêòîðà x è y èç ýòîãî ïðîñòðàíñòâà:x ∈ H, x = (x1 , x2 , . . . , xm )Ty ∈ H, y = (y1 , y2 , . . . , ym )TÂâåäåì ñêàëÿðíîå ïðîèçâåäåíèå âåêòîðîâ(x, y)(x, y) =mXi=1ïî ôîðìóëå:xi y i(2)x0Òåîðåìû î ñõîäèìîñòè èòåðàöèîííûõ ìåòîäîâ17Ââåäåì íîðìó âåêòîðà x:1||x|| = (x, x) 2Çàìå÷àíèå. Åñòü ñëàáûå íîðìû, êîòîðûå îáëàäàþò íå ïîòî÷å÷íîé áëèçîñòüþ. Ðåøåíèÿñèñòåì ñòàðàþòñÿ áðàòü â ñèëüíîé íîðìå, âõîäíûå äàííûå - â ñëàáîé, ÷òîáû ìàêñèìàëüíîðàñøèðèòü îáëàñòü ïðèìåíåíèÿ ìåòîäà.Ðàññìîòðèì ñàìîñîïðÿæåííûé îïåðàòîðD = D∗ > 0Îïðåäåëåíèå. Áóäåì ãîâîðèòü î ñêàëÿðíîì ïðîèçâåäåíèè âåêòîðîâ x è y â ñìûñëå D, åñëè(x, y)D = (Dx, y)Ýòî ïîçâîëÿåò íàì ââåñòè ýíåðãåòè÷åñêåóþ íîðìó:Îïðåäåëåíèå.

Ýíåðãåòè÷åñêàÿ íîðìà - íîðìà, êîòîðàÿ çàäàåòñÿ ñîîòíîøåíèåì:1||x||D = (Dx, x) 2Âñïîìíèì íåêîòîðûå ñâîéñòâà ñàìîñîïðÿæåííîãî ïîëîæèòåëüíî îïðåäåëåííîãî îïåðàòîðàD, èçâåñòíûå èç òåîðèè îïåðàòîðîâ:1.∃D−1 = (D−1 )∗ > 02.∃D 2 = (D 2 )∗ > 03.∃D− 2 = (D− 2 )∗ > 01111èç ýòèõ ñâîéñòâ ñëåäóåò, ÷òî ñóùåñòâóåò òàêîåδ>0:(Dx, x) ≥ δ||x||2 äàëüíåéøåì íàì ïîòðåáóåòñÿ ïîíÿòèå ïîëîæèòåëüíîé èëè íåîòðèöàòåëüíîé îïðåäåëåííîñòè îïåðàòîðà.Îïðåäåëåíèå.C > 0 ⇔ (Cx, x) > 0,∀x 6= 0C ≥ 0 ⇔ (Cx, x) ≥ 0,∀x ∈ HÇàäà÷à.

Äàíî: Îïåðàòîð C > 0, H - âåùåñòâåííîå ëèíåéíîå ïðîñòðàíñòâî ñ çàäàííûì ñêàëÿðíûì ïðîèçâåäåíèåì. Äîêàçàòü, ÷òî:(Cx, x) = (C + C∗x, x)2Äîêàçàòåëüñòâî. Äëÿ ðåøåíèÿ çàäà÷è âîñïîëüçóåìñÿ ñëåäóþùèìè ðàâåíñòââàìè, âåðíûìè äëÿâåùåñòâåííîãî ïðîñòàðàíñòâàH:(C ∗ x, x) = (x, Cx) = (Cx, x),Ïðåäñòàâèì îïåðàòîðCâ âèäå ñóììû:C=C+C ∗2+∀x ∈ HC−C ∗2. Òîãäà:C + C∗C − C∗x, x) + (x, x) =22C + C∗1 ∗C + C∗(x, x) +(C x, x) − (Cx, x) = (x, x),{z}22 |2(Cx, x) = (=0∀x ∈ HÒåîðåìû î ñõîäèìîñòè èòåðàöèîííûõ ìåòîäîâ18Îïðåäåëåíèå. Ïîãðåøíîñòü èòåðàöèîííîãî ìåòîäàV n = xn − xÎïðåäåëåíèå.

Ìåòîä(3)(2) ñõîäèòñÿ, åñëè||V n || → 0(n → ∞)Èç îïðåäåëåíèÿ ïîãðåøíîñòè ÿñíî, ÷òî ðåøåíèþ ìàòðè÷íîãî óðàâíåíèÿ (2) íà n-îé èòåðàöèèñîîòâåòñòâóåò âåêòîðxn = V n + x,ãäåx òî÷íîå ðåøåíèå ñèñòåìû.Èñïîëüçóÿ ýòî ñîîòíîøåíèå, ïåðåïèøåì óðàâíåíèå (2) ÷åðåç âåêòîð ïîãðåøíîñòè:BãäåV n+1 − V n+ AV n = 0,τ(4)n = 0, 1, 2, . . .Óìíîæèì óðàâíåíèå (4) íà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 = SV nÒàêèì îáðàçîì, ïîëó÷èì ìàòðèöó S:S = E − τ B −1 A(5)Îïðåäåëåíèå. S íàçûâàåòñÿ ìàòðèöåé ïåðåõîäà îò n-é èòåðàöèè ê (n+1)-éÒåîðåìà 1(î ñõîäèìîñòè èòåðàöèîííûõ ìåòîäîâ).

Èòåðàöèîííûé ìåòîä (2) ðåøåíèÿ çàäà÷è(1) ñõîäèòñÿ ïðè ëþáîì íà÷àëüíîì ïðèáëèæåíèè òîãäà è òîëüêî òîãäà, êîãäà âñå ñîáñòâåííûåçíà÷åíèÿ ìàòðèöûSïî ìîäóëþ ìåíüøå åäèíèöû.Çàìå÷àíèå. Ýòà òåîðåìà õîðîøà, íî ðåäêî ïðèìåíèìà, ò.ê. â áîëüøèíñòâå ñëó÷àåâ èñêàòüñîáñòâåííûå çíà÷åíèÿ òðóäíî.Çàìå÷àíèå. Äàëåå âñþäó áóäåì ðàññìàòðèâàòü òîëüêî âåùåñòâåííûå ïðîñòàðíñòâà.Òåîðåìà 2(Ñàìàðñêîãî).

Ïóñòü îïåðàòîðA = A∗ > 0 (A∗ = AT )Ïóñòü âûïîëíåíî íåðàâåíñòâîB − 0, 5τ A > 0, (τ > 0)(6)Òîãäà èòåðàöèîííûé ìåòîä (2) ðåøåíèÿ ñèñòåìû (1) ñõîäèòñÿ â ñðåäíåêâàäðàòè÷íîé íîðìåïðè ëþáîì íà÷àëüíîì ïðèáëèæåíèè, òî åñòü||xn − x|| =mXi=1! 21(xni − xi )→ 0, n → ∞Òåîðåìû î ñõîäèìîñòè èòåðàöèîííûõ ìåòîäîâyn = (AV n , V n )Äîêàçàòåëüñòâî. ÂâåäåìÐàññìîòðèì19yn+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 ) = ((A − τ AB −1 A)V n , (E − τ B −1 A)V n ) == (AV n , V n ) − τ (AB −1 AV n , V n ) + (AV n , B −1 AV n ) − τ (AB −1 AV n , B −1 AV n ) =åñëè ó÷åñòü, ÷òî{(AB −1 AV n , V n ) = (B −1 AV n , A∗ V n ) = (AV n , B −1 AV n )},ïîëó÷èì= yn − τ 2(AV n , B −1 AV n ) − τ (AB −1 AV n , B −1 AV n ) =τ= y n + 2τ (B − A)B −1 AV n , B −1 AV n2n+1ny−y+ 2 ( B − 0, 5τ A )B −1 AV n , B −1 AV n  = 0| {z }τÈòàê:>0 ïî óñëîâèþÑëåäîâàòåëüíî, è âñå ñêàëÿðíîå ïðîèçâåäåíèå áîëüøå ëèáî ðàâíî íóëþ.

À ñòàëî áûòü,y n+1 ≤ y n ,è ïîñëåäîâàòåëüíîñòü{y n }íå âîçðàñòàåò è èìååò ïðåäåë.Âîñïîëüçóåìñÿ ñâîéñòâîì ïîëîæèòåëüíî îïðåäåëåííîãî îïåðàòîðà: åñëè îïåðàòîð C >0, òî2∃δ > 0 : (Cx, x) ≥ δ||x|| , ∀x ∈ HÈç ýòîãî ñâîéñòâà ñëåäóåò íåðàâåíñòâî:(B − 0, 5τ A)B −1 AV n , B −1 AV n ≥ δ||B −1 AV n ||2 ,δ>0ãäåy n+1 − y n+ 2δ||B −1 AV n ||2 ≤ 0τÏðèn→∞ïîëó÷èìlim ||B −1 AV n || = 0n→∞ÂâåäåìW n = B −1 AV n .ÎòñþäàV n = A−1 BW nÎöåíèì íîðìó ïîãðåøíîñòè:||V n || ≤ ||A−1 B|| ∗ ||W n || ñèëó íåçàâèñèìîñòèA−1 Bîò n è ñòðåìëåíèþ ê íóëþ íîðìû||W n ||ïðèn→∞ïîëó÷èì,÷òîlim ||V n || = 0n→∞Òàê êàê ìû íèãäå íå èñïîëüçîâàëè íà÷àëüíîå ïðèáëèæåíèå0îñòàåòñÿ âåðíîé äëÿ ëþáîãî íà÷àëüíîãî ïðèáëèæåíèÿ xx0 ,òî ôîðìóëèðîâêà òåîðåìûÒåîðåìû î ñõîäèìîñòè èòåðàöèîííûõ ìåòîäîâ20Cëåäñòâèå. Ïóñòü A = A∗ > 0.

(Íàïîìíèì, ÷òî A = R1 + D + R2 , ãäå R1 è R2 - íèæíåòðåóãëüíàÿ è âåðõíåòðåóãîëüíàÿ ìàòðèöû, àD = diag(a11 , a22 , . . . , amm ))Òîãäà ìåòîä ßêîáè ñõîäèòñÿ â ñðåäíåêâàäðàòè÷íîé íîðìå ïðè ëþáîì íà÷àëüíîì ïðèáëèx0 , åñëè 2D > A.æåíèèÄîêàçàòåëüñòâî.D(xn+1 − xn ) + Axn = fτ =1óñëîâèþ: 2D > A ⇒ D − 0, 5A > 0 ⇒ò.å. B=D,Ïîâûïîëíåíî óñëîâèå òåîðåìû, à çíà÷èò ìåòîäñõîäèòñÿ.Cëåäñòâèå. ÏóñòüA = A∗ > 0mXaii >|aij |, i = 1, m(7)j=1,j6=iÒîãäà ìåòîä ßêîáè ñõîäèòñÿ ïðè ëþáîì íà÷àëüíîì ïðèáëèæåíèèx0Äîêàçàòåëüñòâî.

Âîçüìåì ïðîèçâîëüíûé âåêòîð x, è ðàñïèøåì äëÿ íåãî ñêàëÿðíîå ïðîèçâåäåa2 +b2íèå (Ax, x), èñïîëüçóÿ èçâåñòíîå íåðàâåíñòâî ab ≤:2(Ax, x) =mXaij xi xj ≤i,j=1mX|aij | ∗ |xi | ∗ |xj | ≤i,j=1mm1X1X|aij |x2i +|aij |x2j =2 i,j=12 i,j=1mm1X1X2|aij |xi +|aji |x2i ==2 i,j=12 i,j=1= {aij = aji } =mX|aij |x2i=i,j=1mXx2i (aii+i=1mX|aij |)j=1,j6=iÂîñïîëüçóåìñÿ ñâîéñòâîì äèàãîíàëüíîãî ïðåîáëàäàíèÿ (7)(Ax, x) < 2mXaii x2i = (2Dx, x) ⇒ 2D > Ai=1à çíà÷èò, ïî ñëåäñòâèþ 1 ìåòîä ßêîáè ñõîäèòñÿ ïðè ëþáîìCëåäñòâèå.

Ïóñòüx0A = A∗ > 0Òîãäà ìåòîä Çåéäåëÿ ñõîäèòñÿ ïðè ëþáîì íà÷àëüíîì ïðèáëèæåíèèx0Òåîðåìû î ñõîäèìîñòè èòåðàöèîííûõ ìåòîäîâ21Äîêàçàòåëüñòâî. Ïî îïðåäåëåíèþ ìåòîäà Çåéäåëÿ èìååì:B = R1 + D, τ = 1Äëÿ äîêàçàòåëüñòâà óòâåðæäåíèÿ, â ñèëó òåîðåìû Ñàìàðñêîãî, äîñòàòî÷íî äîêàçàòü, ÷òîB − 0, 5A > 0ÏîñêîëüêóA = R1 + D + R2 ,òî ýòî ñîîòíîøåíèå ïðåîáðàçóåòñÿ ê ñëåäóþùåìó âèäó:2(R1 + D) > R1 + D + R2R1 + D − R2 > 0Ñëåäîâàòåëüíî,((R1 + D − R2 )x, x) > 0, ∀x 6= 0, x ∈ H(R1 x, x) + (Dx, x) − (R2 x, x) > 0 ⇒ (Dx, x) > 0Ïîñëåäíåå ñëåäñòâèå âåðíî, òàê êàêA = A∗ ,à çíà÷èòR1∗ = R2(R1 x, x) = (x, R1∗ x) = (x, R2 x) = (R2 x, x)Ñòàëî áûòü, äëÿ ëþáîãî íåíóëåâîãî âåêòîðà èç0. ñèëó ñàìîñîïðÿæåííîñòè îïåðàòîðàAH òðåáóåòñÿ âûïîëíåíèÿ íåðàâåíñòâà (Dx, x) >ýòî ñîîòíîøåíèå âûïîëíÿåòñÿ, êðîìå òîãî, âñå âû-øåïðèâèäåííûå ïåðåõîäû ðàâíîñèëüíû, à çíà÷èò âûïîëíåíî óñëîâèå òåîðåìû Ñàìàðñêîãî.Cëåäñòâèå.

ÏóñòüAT = A > 0,γ2 = max λAk,20<τ < .γ2Òîãäà ìåòîä ïðîñòîé èòåðàöèè (ðåëàêñàöèè) ñõîäèòñÿ.Äîêàçàòåëüñòâî.  íàøåì ñëó÷àå,B=E. Äîêàæåì, ÷òîE − 0.5τ > 0,òîãäà óòâåðæäåíèå áóäåò ñëåäîâàòü èç òåîðåìû Ñàìàðñêîãî. Çàïèøåì öåïî÷êó íåðàâåíñòâ:τ<2,γ20, 5τ γ2 < 1,÷òî îçíà÷àåò, ÷òî äëÿ ëþáîãîλAk ñîáñòâåííîãî çíà÷åíèÿ ìàòðèöû0, 5τ λAk < 1,1 − 0, 5τ λAk > 0,òî åñòüE − 0.5τ > 0.A âûïîëíåíîÎöåíêà ñêîðîñòè ñõîäèìîñòè èòåðàöèîííûõ ìåòîäîâŸ722Îöåíêà ñêîðîñòè ñõîäèìîñòè èòåðàöèîííûõ ìåòîäîâÐàññìîòðèì ÑËÀÓAx = f,ãäåA ìàòðèöà ðàçìåðàm × m,(1)|A| =6 0.Çàïèøåì îáùèé âèä èòåðàöèîííîãî ìåòîäà ðåøåíèÿ ÑËÀÓ:BãäåB − îáðàòèìàÿìàòðèöà,xn+1 − xn+ Axn = f,τx0τ > 0,- çàäàíî,(2)n = 0, 1, .

. .Ââåäåì îáîçíà÷åíèå:v n = xn − x.Òîãäà äëÿvìîæíî çàïèñàòü:Bv n+1 − v n+ Av n = 0τ(3)Äëÿ îöåíêè ñêîðîñòè ñõîäèìîñòè èòåðàöèîííûõ ìåòîäîâ ìû áóäåì ñòðåìèòüñÿ äëÿ íåêîòîðîãîρè íåêîòîðîé íîðìû äîêàçàòü ò.í.ρ- îöåíêó:kv n+1 k ≤ ρkv n k,0 < ρ < 1.(4)Òîãäàkv n k ≤ ρn kv 0 k,n → ∞ ⇒ kv n k → 0.ÏóñòüH ëèíåéíîå ïðîñòðàíñòâî ðàçìåðíîñòè(x, y) =mXm. ∀x, y ∈ Hîïðåäåëèì:xi y i ,i=1kxk =ÏóñòüD = D∗ > 0.p(x, x).Îïðåäåëèì:(x, y)D = (Dx, y),pkxkD = (x, x)DÍàéäåì ÷èñëî èòåðàöèén0 (), ýíåðãåòè÷åñêàÿ íîðìà âåêòîðàíåîáõîäèìîå äëÿ òîãî, ÷òîáûkxn − xk < kx0 − xk.Èç (4) ñëåäóåò, ÷òîkxn − xk ≤ ρn kx0 − xk.Ïîòðåáóåì, ÷òîáûρn ≤ .Òîãäà1≤n ln n1,ρ11≥ ln ,ρx∀n > n0 ()âûïîëíÿëîñü:Îöåíêà ñêîðîñòè ñõîäèìîñòè èòåðàöèîííûõ ìåòîäîâ23ln 1.n0 () = ln ρ1ln ρ1 íàçûâàåòñÿ ñêîðîñòüþ ñõîäèìîñòè èòåðàöèîííîãî ìåòîäà.∗Ïóñòü D = D > 0.

Òîãäà ∃{ek } îðòîíîðìèðîâàííûé áàçèñ (ÎÍÁ) èç ñîáñòâåííûõ âåêòîðîâD. Ðàçëîæèì âåêòîð x ïî ýòîìó áàçèñó:×èñëîx=mXck ek .k=1Äëÿ âåêòîðàxèìååò ìåñòî ðàâåíñòâî Ïàðñåâàëÿ:2kxk =mXc2k .k=1Òåîðåìà. Ïóñòü 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 èτρ < 1,(6)ñëåäóåò, ÷òîA<2B,τò.å.B − 0.5τ A > 0.Òàêèì îáðàçîì, ïî òåîðåìå Ñàìàðñêîãî, ñõîäèìîñòü èìååò ìåñòî.Äîêàçàòåëüñòâî òåîðåìû.

Èç ïîëîæèòåëüíîé îïðåäåëåííîñòè ìàòðèöû11∃B 2 = (B 2 )∗ > 0,11∃B − 2 = (B − 2 )∗ > 0.Äîìíîæèì îáå ÷àñòè (3) ñëåâà íà1B− 2 :1v n+1 − v nB+ B − 2 Av n = 0.τ12Îáîçíà÷èì1B 2 vn = zn.Òîãäà11z n+1 − z n+ B − 2 AB − 2 z n = 0.τBñëåäóåò, ÷òîÎöåíêà ñêîðîñòè ñõîäèìîñòè èòåðàöèîííûõ ìåòîäîâÂûðàçèìz n+124: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.Ïóñòüsk , k = 1, .

. . , m ñîáñòâåííûå çíà÷åíèÿ ìàòðèöûñòâåííûé âåêòîð, ñîîòâåòñòâóþùèé ñîáñòâåííîìó çíà÷åíèþ(8)S.sk :Çàôèêñèðóåìk,ïóñòüx ñîá-Sx = sk x (x 6= 0).Çàìåòèì, ÷òî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,Ay =1 − skBy.τÈç óñëîâèÿ (5) òåîðåìû ñëåäóåò, ÷òî1−ρ1 − sk1+ρ(By, y) ≤ (Ay, y) =(By, y) ≤(By, y).τττÏîñêîëüêó(By, y) > 0,òî ïðåäûäóùåå íåðàâåíñòâî âëå÷¼ò1−ρ1 − sk1+ρ≤≤.τττÑëåäîâàòåëüíî,|sk | ≤ ρ, k = 1, . . .