Н.И. Ионкин - Электронные лекции (2009) (1135239), страница 3
Текст из файла (страница 3)
Ïîýòîìó öåëåñîîáðàçíî èìåòü åäèíóþ ôîðìóçàïèñè èòåðàöèîííîãî ìåòîäà.Îïðåäåëåíèå. Êàíîíè÷åñêîé ôîðìîé çàïèñè äâóõñëîéíîãî èòåðàöèîííîãî ìåòîäà ðåøåíèÿ ÑËÀÓ (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 a222R1 = .... ..am1 am2a11a122 0 a222R2 = .... ..00······...·········...···00 . ,. .amm2a1ma2m . .. .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, .
. .Ââåäåì îáîçíà÷åíèå:v n = xn − x.Òîãäà äëÿvìîæíî çàïèñàòü:Bv n+1 − v n+ Av n = 0τ(3)Îöåíêà ñêîðîñòè ñõîäèìîñòè èòåðàöèîííûõ ìåòîäîâ30Äëÿ îöåíêè ñêîðîñòè ñõîäèìîñòè èòåðàöèîííûõ ìåòîäîâ ìû áóäåìñòðåìèòüñÿ äëÿ íåêîòîðîãîρ è íåêîòîðîé íîðìû äîêàçàòü ò.í. ρ - îöåíêó: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 yi ,i=1kxk =ÏóñòüD = D∗ > 0.p(x, x).Îïðåäåëèì:(x, y)D = (Dx, y),kxkD =p(x, x)DÍàéäåì ÷èñëî èòåðàöèé ýíåðãåòè÷åñêàÿ íîðìà âåêòîðàxn0 (), íåîáõîäèìîå äëÿ òîãî, ÷òîáû ∀n > n0 ()âûïîëíÿëîñü:kxn − xk < kx0 − xk.Èç (4) ñëåäóåò, ÷òîkxn − xk ≤ ρn kx0 − xk.Ïîòðåáóåì, ÷òîáûρn ≤ .Òîãäà1≤ n1,ρ11≥ ln ,ρln 1.n0 () = ln ρ1n ln×èñëîln ρ1íàçûâàåòñÿ ñêîðîñòüþ ñõîäèìîñòè èòåðàöèîííîãî ìåòîäà.Îöåíêà ñêîðîñòè ñõîäèìîñòè èòåðàöèîííûõ ìåòîäîâÏóñòüD = D∗ > 0.Òîãäàèç ñîáñòâåííûõ âåêòîðîâD.∃{ek } îðòîíîðìèðîâàííûé áàçèñ (ÎÍÁ)Ðàçëîæèì âåêòîðx=31mXxïî ýòîìó áàçèñó:ck ek .k=1Äëÿ âåêòîðàxèìååò ìåñòî ðàâåíñòâî Ïàðñåâàëÿ:kxk2 =mXc2k .k=1Òåîðåìà.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
