Ответы на экзаменационные вопросы (1163657), страница 10
Текст из файла (страница 10)
î÷åíü áîëüøîå ÷èñëî).nY(1 − αj A)xj+1 = xj − αj+1 (Axj − b) j = 0, n − 1.j=1α1 , ..., αn íóæíî èõ ïåðåìåøàòü, ÷òîáû ïîäðÿä íå øëî ñëèøêîì ìíîãî αj îäíîãî çíàêà ? ,̈_kÅñëè n = 2 , òî ìîæíî ïðåäëîæèòü ñëåäóþùèé ñïîñîá ïåðåìåøèâàíèÿ èíäåêñîâk = 1 : 1, 2 = (b11 , b12 )k = 2 : (b11 , 22 + 1 − b11 , b12 , 22 + 1 − b12 ) = (1, 4, 2, 3) = (b21 , b22 , b23 , b24 )k = 3 : (b31 , b32 , ...) = (b21 , 23 + 1 − b21 , b22 , 23 + 1 − b22 , ...) = (1, 8, 4, 5, 2, 6, 3)6728Ìåòîä ñêîðåéøåãî ñïóñêà ðåøåíèÿñèñòåì ëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèé.Èç Ëåêöèè 12:Îïðåäåëåíèå.
A1/2 :A1/2 · A1/2 = A.Ñèììåòðè÷íóþ, ïîëîæèòåëüíî îïðåäåëåííóþ ìàòðèöó ìîæíî ïðåäñòàâèòü â âèäå A =TQ ΛQ, ïðàâäà êîíñòðóêòèâíîãî ïîñòðîåíèÿ òàêîãî ðàçëîæåíèÿ @ ,̈_. Ñîîòâåòñòâåííî √λ1 . . . 0λ1 . . . 0..Λ = · · · ... · · · A1/2 = QT · · ·. ··· Q√λN0...0. . . λNÏîñòðîèì íà ìàòðèöå A âåêòîðíóþ íîðìóp−kxkA = (Ax, x)ýíåðãåòè÷åñêàÿ íîðìàÏî÷åìó ýòî íîðìà? : A - ñèììåòðè÷íàÿ ⇒ A1/2 - ñèììåòðè÷íàÿ.qq1/21/2kxkA = (A A x, x) = (A1/2 x, A1/2 x) = kA1/2 xk2Ðàññìàòðèâàåòñÿxn+1 = xn − αn+1 (Axn − b).xn → xn+1çàâèñèò òîëüêî îò αn+1Õîòèì âûáðàòü åãî: ÷òîáû ïîãðåøíîñòü áûëà min.z n = xn − x→xn+1 = xn − αn+1 (Axn − b)n+1nz= z − αn+1 (Az n ),z n+1 = (E − αn+1 A)z n(z n+1 , z n+1 ) = ((E − αn+1 A)z n , (E − αn+1 A)z n )2kz n+1 k22 = kz n k22 − 2αn+1 (Az n , z n ) + αn+1(Az n , Az n )Ïàðàáîëà ïî α, âåòâè ââåðõ (åñëè z n = 0, òî ðåøèëè çàäà÷ó íà ïðåäûäóùåì øàãå).min :αn+1 =(Az n , z n ),(Az n , Az n )z n = xn − x,Az n = Axn − Ax = Axn − b = rnýòè âûêëàäêè íèêóäà íå âåäóò (îñòàíîâèëèñü â øàãå îò îòâåòà).Äåëàåì òàê:A1/2 z n+1 = A1/2 (E − αn+1 A)z n =°A1/2 A = AA1/2 ( = A1/2 A1/2 A1/2 )ò.ê.=° (E − αn+1 A)A1/2 z nÂîçâåäåì â ñêàëÿðí.
êâàäðàò:2kz n+1 k2A = kz n k2A − 2αn+1 (AA1/2 z n , A1/2 z n ) + αn+1kAA1/2 z n k268Îïÿòü ïàðàáîëà. Åå min :αn+1 =(rn , rn )(Az n , z n )(AA1/2 z n , A1/2 z n )←==(rn , Arn )(Az n , AAz n )(AA1/2 z n , AA1/2 z n )âñå ìîæíî âû÷èñëèòü. Áîëåå òîãî, rn âîçíèêàåò êàæäûé ðàç ïî õîäó âû÷èñëåíèÿ (åñòüìîäèôèêàöèÿ àëãîðèòìà, â êîòîðîé ìîæíî íå óìíîæàòü åãî íà ìàòðèöó).Ñ êàêîé ñêîðîñòüþ àëãîðèòì ñõîäèòñÿ?Ìåòîä ïðîñòîé èòåðàöèè (ÌÏÈ):¶µM −m2n+1nn= q0 .,x= x − α0 (Ax − b),α0 =M +mM +mÈìååìkz n+1 kA = k(E − αn+1 A)z n kA≤ò.ê. âûáðàëè íàèëó÷ø.αn+1= kA1/2 (E − α0 A)z n k22 = k(E − α0 A)A1/2 z n k22µ≤ kE −α0 Ak22·kA1/2 z n k22µÒàêèì îáðàçîì,kz n+1 kA≤≤M −mM +mM −mM +m¶2k(E − α0 A)z n kA =≤kxk2A = kA1/2 xk22kBxk ≤ kBkkxkkz n kA¶kz n kA , ò.å.
ñõîäèòñÿ íå õóæå, ÷åì ÌÏÈ (ïðèìåðíî òàêæå) - ýòî ìåòîä ñêîðåéøåãî (ãðàäèåíòíîãî) ñïóñêà.Äðóãîå èçëîæåíèå ýòîãî æå âîïðîñà.Ðàññìàòðèâàåòñÿ çàäà÷à ñ ñèììåòðè÷íîé ïîëîæèòåëüíî îïðåäåëåííîé ìàòðèöåéAx = b,A = AT > 0,êîòîðàÿ ýêâèâàëåíòíà çàäà÷å ìèíèìèçàöèè êâàäðàòè÷íîé (ñèììåòðè÷íîé) ôóíêöèèF (x) = (Ax, x) − 2(b, x) −→ min .xÄëÿ çàäà÷ ìèíèìèçàöèè ôóíêöèè ïðèìåíÿþòñÿ ðàçëè÷íûå ìåòîäû ñïóñêà ïî êàêèìíèáóäü íàïðàâëåíèÿì. Îäèí èç íèõ - ìåòîä ãðàäèåíòíîãî ñïóñêàxk+1 = xk − δk grad(F (xk )) = xk − ∆k (Axk − b), ∆k = 2δk .Çäåñü δk ïàðàìåòð ìåòîäà, è åãî âûáîð îïðåäåëÿåò êîíêðåòíûé àëãîðèòì. Íàïðèìåð, åãîìîæíî îïðåäåëèòü èç óñëîâèÿδk :F (xk+1 ) = F (xk − δ grad(F (xk )) −→ min .δÒàêîé âûáîð ïàðàìåòðà îïðåäåëÿåò ìåòîä íàèñêîðåéøåãî ãðàäèåíòíîãî ñïóñêà.69Çàäà÷à âûáîðà ïàðàìåòðà â ìåòîäå íàèñêîðåéøåãî ãðàäèåíòíîãî ñïóñêà - ýòî çàäà÷àìèíèìèçàöèè ôóíêöèè îäíîé ïåðåìåííîé.
Íåîáõîäèìîå óñëîâèå ìèíèìóìà - ðàâåíñòâî íóëþïåðâîé ïðîèçâîäíîé.Ðàñïèñûâàåì ýòó ôóíêöèþF (xk ) − 2∆(Axk − b, Axk − b) + ∆2 (A(Axk − b), Axk − b), ∆ = 2δ,äèôôåðåíöèðóåì, íàõîäèì ìèíèìóì - ïîëó÷àåì ∆k∆k =(rk , rk ),(Ark , rk )ãäå rk = Axk − b.Ðàñ÷åòíûå ôîðìóëû ìåòîäà íàèñêîðåéøåãî ãðàäèåíòíîãî ñïóñêàxk7→rk = Axk − b7→(rk , rk )(Ark , rk )∆k =7→xk+1 = xk − ∆k rk7→xk+1ïðè ðàñ÷åòàõ çàìåíÿþò íà ôîðìóëû, äàþùèå òîò æå ðåçóëüòàò{xk , rk } 7→ ∆k =(rk , rk )7→ rk+1 = rk − ∆k Ark 7→ xk+1 = xk − ∆k rk 7→ {xk+1 , rk+1 },(Ark , rk )â êîòîðûõ òðåáóåòñÿ òîëüêî îäíî óìíîæåíèå ìàòðèöû íà âåêòîð (Ark ), à íå äâà, êàê â ïåðâîìâàðèàíòå (Ark è Axk ).◦ xkO x2x1:,,,k+1x ,,◦RÒðàåêòîðèÿ èç òî÷êè xk èäåò ïî íàïðàâëåíèþ,ïåðïåíäèêóëÿðíîìó ëèíèè óðîâíÿ â xk ,ò.å.
ïî àíòèãðàäèåíòó â ýòîé òî÷êå.Äâèæåíèå ïðîäîëæàåòñÿ äî òåõ ïîð,ïîêà íå áóäåò äîñòèãíóòà òî÷êàêàñàíèÿ ýòîãî íàïðàâëåíèÿ ñ äðóãîéëèíèåé óðîâíÿ xk+1 .Ìåòîä ïðîñòîé èòåðàöèè ñ îïòèìàëüíûì ïàðàìåòðîì, î÷åâèäíî, ÿâëÿåòñÿ ìåòîäîìãðàäèåíòíîãî ñïóñêàxk7→rk = Axk − b7→∆k =2M +m7→xk+1 = xk − ∆k rk7→xk+1 ,íî íå íàèñêîðåéøåãî. Ñëåäîâàòåëüíî ÌÍÃÑ ñõîäèòñÿ óæ çàâåäîìî íå ìåäëåííåå. Ìîæíîãîâîðèòü, ÷òî ÌÍÃÑ ñõîäèòñÿ ñ òàêîé æå ñêîðîñòüþ, êàê îïòèìàëüíûé îäíîøàãîâûéèòåðàöèîííûé ïðîöåññ, íî â îòëè÷èå îò íåãî â ÌÍÃÑ íå òðåáóåòñÿ çíàòü ãðàíèöû ñïåêòðàìàòðèöû m è M .7029Ìåòîä Çåéäåëà ðåøåíèÿ ëèíåéíûõ ñèñòåì.Äîñòàòî÷íîå óñëîâèå ñõîäèìîñòè.Ïðåäñòàâèì ìàòðèöó ñèñòåìû Ax = b â âèäå A = L + D + R, ãäå D äèàãîíàëüíàÿìàòðèöà, L è R ñîîòâåòñòâåííî íèæíÿÿ è ïðàâàÿ âåðõíÿÿ òðåóãîëüíûå ìàòðèöû ñ íóëåâûìèäèàãîíàëÿìè (ñòðîãî íèæíÿÿ è ñòðîãî âåðõíÿÿ òðåóãîëüíûå ìàòðèöû).
Áóäåì ïðåäïîëàãàòü,÷òî âñå äèàãîíàëüíûå ýëåìåíòû aii îòëè÷íû îò íóëÿ.Ìåòîä Çåéäåëÿ:(D + L)xk+1 + Rxk = b.Åñëè ó ìàòðèöû A åñòü äèàãîíàëüíîå ïðåîáëàäàíèåNX|aij | ≤ q|aii |,0 ≤ q < 1,i = 1, 2, ..., N,j=1j 6= iýòîò ìåòîä ñõîäèòñÿ (ñî ñêîðîñòüþ ãåîìåòðè÷åñêîé ïðîãðåññèè).Ìåòîä Çåéäåëÿ ÷àñòî íàçûâàþò ìåòîäîì ïîêîîðäèíàòíîãî ñïóñêà.x26cccc•¾•c""c"¾c•"•cc """?c?"c""c"c 6c"" c•""•c"c"c"c""Òðàåêòîðèÿ ìåòîäà Çåéäåëÿäëÿ ñèñòåìû èç äâóõ óðàâíåíèé.Ïðè ñìåíå ïîðÿäêà óðàâíåíèéñõîäèìîñòü ìîæåò ïîìåíÿòüñÿ íàðàñõîäèìîñòü.
Ñòðåëêè ïîâåðíóòñÿ!-0x1Ìåòîä Çåéäåëÿ âñåãäà ñõîäèòñÿ äëÿ ñèììåòðè÷íîé ìàòðèöû A.Èç Ëåêöèè 12:Ìåòîä Çåéäåëÿ â ïðåäïîëîæåíèè aii 6= 0iXNXaij xn+1+jj=1Ïóñòü åñòü xn :xn+111=a11xn+1i1=aiiaij xnj = bi , i = 1, N .j=i+1Ãbi −Ãbi −!NPj=2i−1Pj=1aij xnjaij xnj,−Èç Ëåêöèè 13:71NPj=i+1!aij xnj, i = 2, N .Ðåøàåì ñèñòåìó Ax = b.XÓòâåðæäåíèå. Ìåòîä Çåéäåëÿ ñõîäèòñÿ, åñëè|aij | ≤ q|aii |0<q<1i6=j×åì áîëüøå äèàãîíàëüíîå ïðåîáëàäàíèå,òåì ëó÷øå ñõ-ñÿ ìåòîä Çåéäåëÿ.Äîê. z n = xn − x. Ïåðåéäåì ê ÿçûêó ïîãðåøíîñòåéXXaii zin+1 = −aij zjn+1 −aij zjn+1|aii ||zin+1 |≤j<iX|aij ||zjn |j<i+j>iX|aij ||zjn |j>ikz n+1 k∞ = |zkn+1 |,zkn+1 - ñàìàÿ áîëüøàÿ êîìïîíåíòàÐàññìîòðèì äëÿ ñëó÷àÿ i = kXX|akk |kz n+1 k∞ ≤|akj |kz n+1 k∞ +|akj |kz n k∞j<kX⇒ kz n+1 k∞ ≤Xj>k|akk | −j>k|akj |X|akj |kz n k∞ ≤ qkz n k∞ò.ê.XX j<k|akj |).|akj | < q(|akk | −|akj | ≤ q|akk | −÷.ò.ä.j<kj<kj>k30âûíîñèì kz n+1 k∞ ⇒Ñõîäèìîñòü íåÿâíûõ èòåðàöèîííûõ ìåòîäîâ.Ìåòîä âåðõíåé ðåëàêñàöèè.Ëþáîé èòåðàöèîííûé ìåòîä ðåøåíèÿ Ax = b âèäàBxn+1 − xn+ Axn = b,τêîãäà B 6= E íàçûâàåòñÿ íåÿâíûì, ïîñêîëüêó òðåáóåòñÿ ðåøàòü ÑËÀÓ ñ ìàòðèöåé B (õîòüáû äàæå äèàãîíàëüíîé).
Ýòî ïðîñòî âîïðîñ òåðìèíîëîãèè.Èç Ëåêöèè 12:Ìåòîä âåðõíåé ðåëàêñàöèè.Ââîäèì ïàðàìåòð äëÿ óëó÷øåíèÿ ìåòîäà Çåéäåëÿ−(D{zA })| +Bxn+1 − xn+ Axn = bωïðè ω = 1 - ÷àñòíûé ñëó÷àé ìåòîä Çåéäåëÿ.xn+1 − xn+ Axn = b,αz n+1 − z n+ Az n = 0BαB72z n = xn − xx−x+ Ax = b)α¯T >0¯A=A¯³α ´¯ ⇒ krn k → 0n→∞B− A >0 ¯2(òî÷íîå ðåøåíèå îáÿç. óäîâë-åò BÒåîðåìà:Äîê.2ααB(z n+1 − z n ) + αAz n = 0 (B − A)(z n+1 − z n ) + (z n+1 + z n ) = 0 | · (z n+1 − z n )α22α2n+1nn+1nn+12n2− z ), (z− z )) = 0kzkA − kz kA + ((B − A)(z2α|}{z>0Ñ÷èòàåì α > 0.Åñëè z n+1 = z n ⇔ xn+1 = xn ⇒Ñ÷èòàåì z n+1 6= z n ⇒ëèáî ïîëó÷èëè îòâåòëèáî...?kz n+1 k2A − kz n k2A + (> 0) = 0 ⇒ 0 ≤ kz n+1 k2A < kz n k2A ⇒ ∃ ïðåäåë lim kz n k2An→∞óæå õîðîøîÏîêàæåì, ÷òî îí = 0.αA)(z n+1 − z n ), (z n+1 − z n ))2− z n k → 0 â ∀ íîðìå a'la ñõîäèìîñòü è ôóíäàìåíòàëüíîñòü ýêâèâàëåíòíûlim ((B −n→∞kz n+1B(z n+1 − z n ) + αAz n = 01z n = − A−1 B(z n+1 − z n ) ⇒ kz n k → 0.αÈëëþñòðàöèÿ ìåòîäà ðåëàêñàöèèÌåòîä ðåëàêñàöèè èìååò âèä(D + ωL)xk+1 + [ωR + (ω − 1)D]xk = ωb.Ïàðàìåòð ðåëàêñàöèè ω âûáèðàþò èç îòðåçêà (0, 2).
Ïðè 0 < ω < 1 ìåòîä èíîãäà íàçûâàþòìåòîäîì íèæíåé ðåëàêñàöèè. Ïðè 1 < ω < 2 ìåòîä íàçâàåòñÿ ìåòîäîì âåðõíåé ðåëàêñàöèè.Ïðè ω = 1 ïîëó÷èì ìåòîä Çåéäåëÿ.Óòâåðæäåíèå.Ïóñòü A = AT > 0, òîãäà äëÿ ñõîäèìîñòè ìåòîäà ðåëàêñàöèè ñïðîèçâîëüíîãî íà÷àëüíîãî ïðèáëèæåíèÿ íåîáõîäèìî è äîñòàòî÷íî âûïîëíåíèå íåðàâåíñòâà0 < ω < 2.Äëÿ ñèììåòðè÷íîé ìàòðèöû òðàåêòîðèè äâèæåíèÿ ìåòîäà ìîæíî ïîíÿòü èç êàðòèíêè.Ïî íåé æå âèäíî, ÷òî ïðè 0 < ω < 2 èìååò ìåñòî ñõîäèìîñòü.73O x2Òðàåêòîðèÿ ìåòîäà èäåò ïî íàïðàâëåíèÿì,ïàðàëëåëüíûì îñÿì êîîðäèíàò.W9»»•a»»»»◦»»?»»b•W Wx1:Åñëè íà î÷åðäíîì õîäå ïðèøëè â ò. a,òî äëÿ ñõîäèìîñòè ñëåäóþùàÿ òî÷êàïîâîðîòà òðàåêòîðèè äîëæíà áûòü íà (a,b)◦ − ñîîòâåòñòâóåò ìåòîäó Çåéäåëÿ, ω = 1,? − ñîîòâåòñòâóåò ìåòîäó âåðõíåéðåëàêñàöèè, ω ∈ (1, 2).◦?1Ýëëèïñû - ëèíèè óðîâíÿ ôóíêöèè F (x) = (Ax, x)−(b, x). Òî÷êà ìèíèìóìà ýòîé ôóíêöèè2íàõîäèòñÿ â öåíòðå ýëëèïñîâ è ñîâïàäàåò ñ ðåøåíèåì ñèñòåìû Ax = b.Çàìåòèì ïî ïîâîäó êàðòèíêè, ÷òî â òî÷êó a ìîæíî áûëî ïðèéòè òîëüêî ïî ìåòîäóíèæíåé ðåëàêñàöèè.
Ïî ìåòîäó Çåéäåëÿ ïðèøëè áû ïî íàïðàâëåíèþ, ïàðàëëåëüíîìó x2 ,â òî÷êó ◦, à ïî ìåòîäó âåðõíåé ðåëàêñàöèè â òî÷êó ?, êîòîðàÿ åùå äàëüøå.31Èòåðàöèîííûå ìåòîäûñî ñïåêòðàëüíî ýêâèâàëåíòíûìè îïåðàòîðàìè.Ïðè B 6= I, det(B) 6= 0 äâóõñëîéíûé èòåðàöèîííûé ïðîöåññBxk+1 − xk+ Axk = bτíàçûâàþò îáîáùåííûì ìåòîäîì ïðîñòîé èòåðàöèè.Åñëè âçÿòü B = A, τ = 1, òî ìåòîä ñõîäèòñÿ çà îäèí øàã. Îáû÷íî ñòàðàþòñÿ âçÿòüìàòðèöó B òàê, ÷òîáû îíà áûëà áû áëèçêà ïî ñâîèì ñïåêòðàëüíûì ñâîéñòâàì ê ìàòðèöå A,è ÷òîáû ðåøåíèå çàäà÷è Bxk+1 = dk ïðÿìûì ìåòîäîì òðåáîâàëî áû íåáîëüøîãî êîëè÷åñòâàîïåðàöèé.Óòâåðæäåíèå.Ïóñòü A = ³AT > 0, òîãäà îáîáùåííûéìåòîä ïðîñòîé èòåðàöèè´ττñõîäèòñÿ ïðè óñëîâèè B − > 0 (Bx, x) > (Ax, x) ∀x 6= 0 .22Äîêàçàòåëüñòâî ïðîâîäèòñÿ "ýíåðãåòè÷åñêèì" ìåòîäîì.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
