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

. . , xm )T ,f = (f1 , . . . , fm )T .Èç íåâûðîæäåííîñòè ìàòðèöûAñëåäóåò, ÷òî ðåøåíèå ñèñòåìû (1) ñó-ùåñòâóåò è åäèíñòâåííî. Ïåðåïèøåì ñèñòåìó (1) â âèäå:mXaij xj = fi ,i = 1, . . . , mj=1Âûäåëèì èç ñóììûi−1Xi-îåñëàãàåìîå:aij xj + aii xi +j=1Ïóñòüaii 6= 0,mXaij xj = fi ,j=i+1òîãäà ìîæíî âûðàçèòüxi =Îáîçíà÷èì ÷åðåçi = 1, . . . , mfi −xni i-óþxi :Pi−1j=1 aij xj −aiiêîìïîíåíòóPmj=i+1n-îéaij xj(2)èòåðàöèè. Çàïèøåì ìåòîäßêîáè (Ìß):xn+1ii−1mXXfiaij naij n=−xj −xj ,aii j=1 aiiaiij=i+1Çàäàí âåêòîðxn+1=iÂåêòîðx0n = 0, 1, . .

. ; i = 1, . . . , mx0 - íà÷àëüíîå ïðèáëèæåíèå. Çàïèøåì ìåòîä Çåéäåëÿ (ÌÇ):i−1mXXfiaij n+1aij n−xj −xj ,aii j=1 aiiaiij=i+1òàêæå èçíà÷àëüíî çàäàí.n = 0, 1, . . . ; i = 1, . . . , m;Ïðèìåðû è êàíîíè÷åñêèé âèä èòåðàöèîííûõ ìåòîäîâ ðåøåíèÿ ÑËÀÓ19Ïðåäñòàâèì ìàòðèöóAâ âèäå:A = R1 + D + R2 ,(3)ãäå00 ··· 0 a210 · · · 0R1 =  ........ ....am1 am2 · · · 0 íèæíåòðåóãîëüíàÿ ìàòðèöà ñ íóëÿìè íà ãëàâíîé äèàãîíàëè,a11 0 · · ·0 0 a22 · · ·0 D =  .... ....  ....00 · · · amm äèàãîíàëüíàÿ ìàòðèöà,0 a12 · · · a1m0 0 · · · a2m R2 =  .. .. .

.. .. ... 0 0 ···0 âåðõíåòðåóãîëüíàÿ ìàòðèöà ñ íóëÿìè íà ãëàâíîé äèàãîíàëè. Î÷åâèäíî,òàêîå ðàçëîæåíèå âñåãäà îñóùåñòâèìî. Ïîäñòàâèì ïðåäñòâàëåíèå (3) â(1):(R1 + D + R2 )x = fDx = f − R1 x − R2 xÏðåäïîëîæèì òåïåðü, ÷òî∃D−1 .Òîãäà:x = D−1 f − D−1 R1 x − D−1 R2 xÌåòîä ßêîáè ìîæíî çàïèñàòü ñëåäóþùèì îáðàçîì:xn+1 = D−1 f − D−1 (R1 + R2 )xnèëèD(xn+1 − xn ) + Axn = fÏðèìåðû è êàíîíè÷åñêèé âèä èòåðàöèîííûõ ìåòîäîâ ðåøåíèÿ ÑËÀÓ20Ìåòîä Çåéäåëÿ:xn+1 = D−1 f − D−1 R1 xn+1 − D−1 R2 xnèëè(D + R1 )(xn+1 − xn ) + Axn = fÈç ïðèâåäåííûõ çàïèñåé âèäíî, ÷òî èòåðàöèîííûå ìåòîäû ìîæíî çàïèñàòü â ðàçëè÷íîì âèäå. Ïîýòîìó öåëåñîîáðàçíî èìåòü åäèíóþ ôîðìóçàïèñè èòåðàöèîííîãî ìåòîäà.Îïðåäåëåíèå.

Êàíîíè÷åñêîé ôîðìîé çàïèñè äâóõñëîéíîãî èòåðàöèîííîãî ìåòîäà ðåøåíèÿ ÑËÀÓ (1) íàçûâàåòñÿ åãî çàïèñü â âèäå:Bn+1xn+1 − xn+ Axn = f,τn+1n = 0, 1, . . . ; x0 çàäàí(4)τn+1 > 0 - èòåðàöèîííûé ïàðàìåòð,Bn+1 - îáðàòèìàÿ ìàòðèöà.Åñëèτn+1 = τ ,Bn+1 = E ,òî ìåòîä (4) íàçûâàåòñÿ ÿâíûì. ÅñëèBn+1 = B ,òî ìåòîä (4) íàçûâàåòñÿ ñòàöèîíàðíûì.Ìåòîä ïðîñòîé èòåðàöèè (ÏÈ, èëè ìåòîä ðåëàêñàöèè) èìååò ñëåäóþùèé âèä:xn+1 − xn+ Axn = f,ττ >0Ðàññìîòðèì áîëåå ïîäðîáíî ïîïåðåìåííî-òðåóãîëüíûé èòåðàöèîííûé ìåòîä (ÏÒÈÌ):(E + ωR1 )(E + ωR2 )Çäåñüτn+1 > 0, ω > 0xn+1 − xn+ Axn = f,τn+1n = 0, 1, . .

. ; x0 èòåðàöèîííûå ïàðàìåòðû,a1102 a21 a222R1 =  .... ..am1 am2a11a122 0 a222R2 =  .... ..00······...·········...···00 . ,. .amm2a1ma2m . .. .amm2 çàäàí (5)R1 + R2 = A,ãäåÒåîðåìû î ñõîäèìîñòè èòåðàöèîííûõ ìåòîäîâ21Ðåàëèçàöèÿ ïîïåðåìåííî-òðåóãîëüíîãî èòåðàöèîííîãî ìåòîäà ìîæåò áûòüîñóùåñòâëåíà ïî ÿâíûì ôîðìóëàì. Ïóñòü: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 ,âåðõíåòðåóãîëüíàÿ ìàòðèöà,îáðàùàÿ âåðõíåòðåóãîëüíóþ ìàòðèöó ïîv n+1 , è äàëåå:ÿâíûì ôîðìóëàì ìîæíî íàéòè âåêòîðxn+1 = xn + τn+1 v n+1 .Òàêèì îáðàçîì, íåñìîòðÿ íà òî, ÷òî ÏÒÈÌ - íåÿâíûé èòåðàöèîííûéìåòîä, åãî ðåàëèçàöèÿ ïðîñòà è ñâîäèòñÿ ê ïîïåðåìåííîìó îáðàùåíèþíåæíåòðåóãîëüíîé è âåðõíåòðåóãîëüíîé ìàòðèö(îòñþäà - íàçâàíèå ìåòîäà).Ÿ6Òåîðåìû î ñõîäèìîñòè èòåðàöèîííûõ ìåòîäîâÐàññìîòðèì ìàòðè÷íîå óðàâíåíèå âèäàAx = f,ãäåA ìàòðèöà ðàçìåðà(1)(m × m), |A| =6 0Ðàññìîòðèì òàêæå ìàòðè÷íîå óðàâíåíèå âèäàBxn+1 − xn+ Axn = f,τ(2)Òåîðåìû î ñõîäèìîñòè èòåðàöèîííûõ ìåòîäîâãäån = 0, 1, 2, .

. . , ∃B −1 ,22è çàäàí âåêòîð íà÷àëüíîãî ïðèáëèæåíèÿÐàññìîòðèì ëèíåéíîå ïðîñòðàíñòâî H, òàêîå ÷òîx0dim H = mÂîçüìåì 2 ïðîèçâîëüíûõ âåêòîðà x è y èç ýòîãî ïðîñòðàíñòâà:x ∈ H, x = (x1 , x2 , . . . , xm )Ty ∈ H, y = (y1 , y2 , . . . , ym )TÂâåäåì ñêàëÿðíîå ïðîèçâåäåíèå âåêòîðîâ(x, y) =mX(x, y)ïî ôîðìóëå:xi y ii=1Ââåäåì íîðìó âåêòîðà 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Òåîðåìû î ñõîäèìîñòè èòåðàöèîííûõ ìåòîäîâ23èç ýòèõ ñâîéñòâ ñëåäóåò, ÷òî ñóùåñòâóåò òàêîåδ>0:(Dx, x) ≥ δ||x||2 äàëüíåéøåì íàì ïîòðåáóåòñÿ ïîíÿòèå ïîëîæèòåëüíîé èëè íåîòðèöàòåëüíîé îïðåäåëåííîñòè îïåðàòîðà.Îïðåäåëåíèå.C > 0 ⇔ (Cx, x) > 0,∀x 6= 0C ≥ 0 ⇔ (Cx, x) ≥ 0,∀x ∈ HÇàäà÷à.

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

Ïîãðåøíîñòü èòåðàöèîííîãî ìåòîäàV n = xn − xÎïðåäåëåíèå. Ìåòîä(2) ñõîäèòñÿ, åñëè||V n || → 0(n → ∞)(3)Òåîðåìû î ñõîäèìîñòè èòåðàöèîííûõ ìåòîäîâ24Èç îïðåäåëåíèÿ ïîãðåøíîñòè ÿñíî, ÷òî ðåøåíèþ ìàòðè÷íîãî óðàâíåíèÿ (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(Ñàìàðñêîãî). Ïóñòü îïåðàòîð25A = A∗ > 0 (A∗ = AT )Ïóñòü âûïîëíåíî íåðàâåíñòâîB − 0, 5τ A > 0, (τ > 0)(6)Òîãäà èòåðàöèîííûé ìåòîä (2) ðåøåíèÿ ñèñòåìû (1) ñõîäèòñÿ âñðåäíåêâàäðàòè÷íîé íîðìå ïðè ëþáîì íà÷àëüíîì ïðèáëèæåíèè, òî åñòü||xn − x|| =mX(xni − xi )! 21→ 0, n → ∞i=1Äîêàçàòåëüñòâî.

ÂâåäåìÐàññìîòðèìyn = (AV n , V n )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 ) = ((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Èòàê:yn+1n−y+ 2 ( B − 0, 5τ A )B −1 AV n , B −1 AV n = 0| {z }τ>0 ïî óñëîâèþÑëåäîâàòåëüíî, è âñå ñêàëÿðíîå ïðîèèçâåäåíèå áîëüøå ëèáî ðàâíîíóëþ. À ñòàëî áûòü,y n+1 ≤ y n ,Òåîðåìû î ñõîäèìîñòè èòåðàöèîííûõ ìåòîäîâè ïîñëåäîâàòåëüíîñòü{y n }26íå âîçðàñòàåò è èìååò ïðåäåë.Âîñïîëüçóåìñÿ ñâîéñòâîì ïîëîæèòåëüíî îïðåäåëåííîãî îïåðàòîðà: åñ2ëè îïåðàòîð C >0, òî∃δ > 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 || ñèëó íåçàâèñèìîñòèïðèn→∞A−1 Bîò n è ñòðåìëåíèþ ê íóëþ íîðìû||W n ||ïîëó÷èì, ÷òîlim ||V n || = 0n→∞Òàê êàê ìû íèãäå íå èñïîëüçîâàëè íà÷àëüíîå ïðèáëèæåíèåx0 ,òîôîðìóëèðîâêà òåîðåìû îñòàåòñÿ âåðíîé äëÿ ëþáîãî íà÷àëüíîãî ïðèáëè0æåíèÿ xCëåäñòâèå.

Ïóñòü A = A∗ > 0. (Íàïîìíèì, ÷òî A = R1 + D + R2 ,R1 èR2 - íèæíåòðåóãëüíàÿdiag(a11 , a22 , . . . , amm ) )ãäåè âåðõíåòðåóãîëüíàÿ ìàòðèöû, àD =Òîãäà ìåòîä ßêîáè ñõîäèòñÿ â ñðåäíåêâàäðàòè÷íîé íîðìå ïðè ëþáîì0íà÷àëüíîì ïðèáëèæåíèè x , åñëè 2D > A.Òåîðåìû î ñõîäèìîñòè èòåðàöèîííûõ ìåòîäîâ27Äîêàçàòåëüñòâî.D(xn+1 − xn ) + Axn = fò.å.

B=D,τ =12D > A ⇒ D − 0, 5A > 0 ⇒ âûïîëíåíî óñëîâèå òåîðåìû,Ïî óñëîâèþ:à çíà÷èò ìåòîä ñõîäèòñÿ.Cëåäñòâèå. ÏóñòüA = A∗ > 0mXaii >|aij |, i = 1, m(7)j=1,j6=iÒîãäà ìåòîä ßêîáè ñõîäèòñÿ ïðè ëþáîì íà÷àëüíîì ïðèáëèæåíèèx0Äîêàçàòåëüñòâî. Âîçüìåì ïðîèçâîëüíûé âåêòîð x, è ðàñïèøåì äëÿ íåãîñêàëÿðíîå ïðîèçâåäåíèåa2 +b2:2(Ax, x) =(Ax, x),mXèñïîëüçóÿ èçâåñòíîå íåðàâåíñòâîaij xi xj ≤i,j=1mX|aij | ∗ |xi | ∗ |xj | ≤i,j=1mm1X1X2|aij |xi +|aij |x2j =2 i,j=12 i,j=1=mm1X1X|aij |x2i +|aji |x2i =2 i,j=12 i,j=1= {aij = aji } =mX|aij |x2i=i,j=1mXi=1x2i (aii+mX|aij |)j=1,j6=iÂîñïîëüçóåìñÿ ñâîéñòâîì äèàãîíàëüíîãî ïðåîáëàäàíèÿ (7)(Ax, x) < 2mXaii x2i = (2Dx, x) ⇒ 2D > Ai=1à çíà÷èò, ïî ñëåäñòâèþ 1 ìåòîä ßêîáè ñõîäèòñÿ ïðè ëþáîìx0ab ≤Òåîðåìû î ñõîäèìîñòè èòåðàöèîííûõ ìåòîäîâCëåäñòâèå.

Ïóñòü28A = A∗ > 0Òîãäà ìåòîä Çåéäåëÿ ñõîäèòñÿ ïðè ëþáîì íà÷àëüíîì ïðèáëèæåíèèx0Äîêàçàòåëüñòâî. Ïî îïðåäåëåíèþ ìåòîäà Çåéäåëÿ èìååì: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)Ñòàëî áûòü, äëÿ ëþáîãî íåíóëåâîãî âåêòîðà èçíèÿ íåðàâåíñòâàHòðåáóåòñÿ âûïîëíå-(Dx, x) > 0.  ñèëó ñàìîñîïðÿæåííîñòè îïåðàòîðà A ýòîñîîòíîøåíèå âûïîëíÿåòñÿ, êðîìå òîãî, âñå âûøåïðèâèäåííûå ïåðåõîäûðàâíîñèëüíû, à çíà÷èò âûïîëíåíî óñëîâèå òåîðåìû Ñàìàðñêîãî.Cëåäñòâèå.

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