И.О. Арушунян - Конспект лекций (1160471), страница 6

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 6)

Ïåðåïèøåì çàäà÷óâ ýêâèâàëåíòíîì âèäåAx = b ⇔ x = Bx + cÊàê âûáðàòü B? Îáû÷íî èç ôîðìóëû x = x − D(Ax − b), det D 6= 0.Ïîñòðîèì èòåðàöèîííûé ïðîöåññx0 : xn+1 = Bxn + cÆäåì, ÷òî ñîéäåòñÿ.Äëÿ îöåíêè ñõîäèìîñòè ââåäåì ïîíÿòèå âåêòîðà ïîãðåøíîñòè z n = xn − x . Äëÿïîãðåøíîñòè ïîëó÷èì îäíîðîäíîå óðàâíåíèå: z n+1 = Bz n .Ìîæíî âûäåëèòü êëàññ ìàòðèö, ÷òî ïðîöåññ ñõîäèòñÿ äëÿ ëþáûõ íà÷àëüíûõ óñëîâèékBk ≤ q < 1, ⇒ kz n+1 k = kBz n k ≤ kBk · kz n k, ⇒ kz n k ≤ q n kz 0 k.Òåîðåìà.

Ïóñòü ∃ ! x : x = Bx + c. Òîãäàµxn+1 = Bxn + cñõîäèòñÿ ∀ x0¶⇔|λ(B)| < 1.Äîêàçàòåëüñòâî. ⇒° Îò ïðîòèâíîãî. Ïóñòü |λk | ≥ 1. Bēk = λk ēk , x0 = x + ēkz 0 = x0 − x = ēk , z 1 = Bz 0 = Bēk = λk ēk , ...., z n = λnk ēk .°⇐ ñì. êíèãó.Äàëåå ñ÷èòàåì, ÷òî ìû ðåøàåì ñèñòåìó ñ ñèììåòðè÷íîé ïîëîæèòåëüíî îïðåäåëåííîéìàòðèöåéAx = b A = AT > 0 (Ax, x) > 0 ∀ x 6= 0.Ïóñòü ∃ m, M : 0 < m ≤ λ(A) ≤ M < ∞.

Ñåé÷àñ ìû ïîêàæåì, ÷òî ïðè òàêîì óñëîâèèìîæíî ïîñòîèòü ñõîäÿùèéñÿ èòåðàöèîííûé ïðîöåññ.Íóæíî (äëÿ ñõ-òè), ÷òîáû|λ(E − αA)|p <1kxk2 = p(x, x)kAk2 = λmax (AT A)x = x − α(Ax − b)xn+1 = xn − α(Axn − b)B = E − αAc = αb46|λ(B)| ≤ q < 1kBk2 =rTλmax (B| {zB}) = |λmax (B)| ≤ q < 1.B2nÏðèìå÷àíèå. Pn (A) = an A + an−1 An−1 + ... + a0 E, {λj } - ñîáñòâåííûå çíà÷åíèÿA⇒ {Pn (λj )} - ñîáñòâåííûå çíà÷åíèÿ Pn (A).Ïóñòü B = E − αA, λ - ñîáñòâåííîå çíà÷åíèå A, òîãäà 1 − αλ - ñîáñòâåííîåçíà÷åíèå B.α16|1 − αλ|­­1J­@­J@­J@­J @­J @αJ @­¡ 2­J@¡0| J­ @¡mλMÎïòèìàëüíîå çíà÷åíèå α, îáåñïå÷èâàþùåå íàèáîëüøóþ ñêîðîñòü ñõîäèìîñòè, áóäåòðåøåíèåì çàäà÷è min max |1− αλ| = q < 1. Ïîñêîëüêó òî÷íûå çíà÷åíèÿ ñîáñòâåííûõαλ1 ,...,λN÷èñåë íåèçâåñòíû, à èçâåñòíû òîëüêî ãðàíèöû ñïåêòðà ìàòðèöû A, âûáèðàåì α èçóñëîâèÿ min max |1 − αλ| = q < 1.α λ∈[m,M ]µ¶m+MÃðàôèê, ñîîòâåòñòâóþùèé îïòèìàëüíîìó α, ïðîõîäèò ÷åðåç òî÷êó,0 .2Äëÿ òàêîãî ᵶnM −mM −mnq0 =<1kz k2 ≤kz 0 k2 .M +mM +mÅñëè m è M äîñòèãàþòñÿ, òî ÷èñëî îáóñëîâëåííîñòè cond2 (A) =Ó ýòîé ìàòðèöûM.m...

0.−1 2 −1 . . 0 .. .. ..N2 ...· · ·0..· · ·. −1 2 −100 . . . −1 22−10÷èñëî îáóñëîâëåííîñòè ∼ N 2⇒ â äàííîì ñëó÷àå òàêîé ìåòîä íå î÷åíü õîðîøèé.Òî, ÷òî ó íàñ áûëî ïåðåä ýòèì - ìåòîä ïðîñòîé èòåðàöèè.47xn+1 = xn − αn+1 (Axn − b)z n+1 = (E − αn+1 A)z nnQzn =(E − αj A)z 0 = Pn (A)z 0|{z}j=1ñèììåòð. ìàòðèöànQkPn (A)k2 ≤ max | (1 − αj λ)|minα∈[m,M ] j=1nQmax |(1 − αj λ)| ≤ q1 < 1.α1 ,...,αn λ∈[m,M ] j=1Pn (λ) : Pn (0) = 1 êëàññå ìíîãî÷ëåíîâ ñòåïåíè n : P (0) = 1 ïîñòðîèòü ìíîãî÷ëåí, íàèìåíåå îòêëîíÿþùèéñÿîò 0 íà îòðåçêå [m, M ].

Äëÿ ýòîãî âîçüìåì ìíîãî÷ëåí ×åáûøåâà íà [m, M ] è ïîäåëèìíà çíà÷åíèå â íóëå. cos(n√arccos x)|x| ≤ 1√nn22Tn (x) =(x + x − 1) + (x − x − 1)|x| ≥ 12T̄n (x) = 21−n Tn (x) = xn +µ...[−1,¶1]2λ − M − m1¶ TnµPn (λ) =M +mM −mTnm−Mπ(2j − 1)M +m M −mπ(2j − 1)xj = cosλj =+cos2n222n1M +m M −m2λ − M − mαj =λ=+xx=λj22M −m1M +m¶¯|Pn (λ)| ≤ ¯¯ µx0 =¯m−M¯Tn M + m ¯¯¯M −msµ¶2pM+mM +m2x0 ± x0 − 1 =±−1=m−Mm−M√√M + m 2 Mm(M ∓ m)2=±=−=m−MM√− mM −m√− M− m= −q1√ √M−m√√=⇒M+ m1√ =− −√q1M− m(−1)n 2⇒ Tn (x0 ) =(q + q1−1 ) ⇒2n 12q1⇒ |Pn (λ)| ≤< 2q n ⇒ kz n k2 ≤ kPn (A)k2 kz 0 k2 ≤1 + q1n √ 1 √M− m≤ 2q1n kz 0 k2 , ãäå q1 = √√ < q0 .M+ m48Óëó÷øèòü ðåçóëüòàò òÿæåëî.Åñëè n áîëüøîå, òî ìîæåì ïîëó÷èòü ïåðåïîëíåíèå (ò.å.

î÷åíü áîëüøîå ÷èñëî).nY(1 − αj A)xj+1 = xj − αj+1 (Axj − b) j = 0, n − 1.j=1α1 , ..., αn íóæíî èõ ïåðåìåøàòü, ÷òîáû ïîäðÿä íå øëî ñëèøêîì ìíîãî αj îäíîãî çíàêà? ,̈_Åñëè n = 2k , òî ìîæíî ïðåäëîæèòü ñëåäóþùèé ñïîñîá ïåðåìåøèâàíèÿ èíäåêñîâ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)12Ëåêöèÿ 12.Ax = b, A = AT > 0.

Áûëè ïîñòðîåíû ìåòîäû, ñõîäÿùèåñÿ√√ ñî ñêîðîñòüþ ãåîìåòðè÷åñêîéM −mM− mïðîãðåññèè ñî çíàìåíàòåëåì q0 =, q1 = √√ , 0 < m ≤ λ(A) ≤ M .M +mM+ mÐàññìàòðèâàåòñÿ íîâàÿ çàäà÷à: íàéòè ìåòîä, íå çàâèñÿùèé îò M è m.Ââåäåì ïðèíöèïèàëüíî íîâóþ íîðìó:Îïðåäåëåíèå. A1/2 : A1/2 · A1/2 = A.Ñèììåòðè÷íóþ, ïîëîæèòåëüíî îïðåäåëåííóþ ìàòðèöó ìîæíî ïðåäñòàâèòü â âèäåA = QT ΛQ, ïðàâäà êîíñòðóêòèâíîãî ïîñòðîåíèÿ òàêîãî ðàçëîæåíèÿ @ ,̈_. Ñîîòâåòñòâåííî √λ1 . . . 0λ1 . .

. 0..Λ =  · · · ... · · · A1/2 = QT  · · ·. ··· Q√0. . . λN0...λNÏîñòðîèì íà ìàòðèöå A âåêòîðíóþ íîðìópkxkA = (Ax, x) − ýíåðãåòè÷åñêàÿ íîðìàÏî÷åìó ýòî íîðìà? : A - ñèììåòðè÷íàÿ ⇒ A1/2 - ñèììåòðè÷íàÿ.qqkxkA = (A1/2 A1/2 x, x) = (A1/2 x, A1/2 x) = kA1/2 xk2Ðàññìàòðèâàåòñÿxn+1 = xn − αn+1 (Axn − b).xn → xn+149çàâèñèò òîëüêî îò αn+1Õîòèì âûáðàòü åãî: ÷òîáû ïîãðåøíîñòü áûëà min.z n = xn − x → xn+1 = xn − αn+1 (Axn − b)z n+1 = z n − α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 k2Îïÿòü ïàðàáîëà. Åå min :αn+1 =(AA1/2 z n , A1/2 z n )(Az n , z n )(rn , rn )==←(AA1/2 z n , AA1/2 z n )(Az n , AAz n )(rn , Arn )âñå ìîæíî âû÷èñëèòü. Áîëåå òîãî, rn âîçíèêàåò êàæäûé ðàç ïî õîäó âû÷èñëåíèÿ (åñòüìîäèôèêàöèÿ àëãîðèòìà, â êîòîðîé ìîæíî íå óìíîæàòü åãî íà ìàòðèöó).Ñ êàêîé ñêîðîñòüþ àëãîðèòì ñõîäèòñÿ?Ìåòîä ïðîñòîé èòåðàöèè (ÌÏÈ):µ¶2M −mn+1nnx= x − α0 (Ax − b),α0 =,= q0 .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≤M −mM +m50¶2kz n kAk(E − α0 A)z n kA =≤kxk2A = kA1/2 xk22kBxk ≤ kBkkxkµÒàêèì îáðàçîì, kzn+1kA ≤M −mM +m¶kz n kA , ò.å.

ñõîäèòñÿ íå õóæå, ÷åì ÌÏÈ (ïðèìåðíîòàê æå) - ýòî ìåòîä ñêîðåéøåãî (ãðàäèåíòíîãî) ñïóñêà.(Ìîæíî ïîñòðîèòü ìåòîä, äàþùèé óñêîðåíèå, íî îí òÿæåëûé)Ïî÷åìó "ãðàäèåíòíîãî":(Ax = b)1(min((Ax, x) − 2(b, x))) ⇔ (min( (Ax, x) − (b, x)))xx|2{z}⇔=Φ(x)dfÏîñòðîèì èòåðàöèîííûé ïðîöåññ:x0 ....xn+1 = xn − αn+1 grad(Φ(xn )),gradΦ(x) = Ax − b.Ìåòîä ñîïðÿæåííûõ ãðàäèåíòîâ. (â ïðîãðàììå íå áóäåò)xn+1 ← xn , xn−1íî òî÷íûé.

Ñõîäèòñÿ êàê ãåîìåòðè÷åñêàÿ ïðîãðåññèÿ√ çàìûñëîâàòûé,√M− mñî çíàìåíàòåëåì √√ . Äëÿ A = AT > 0 íàèëó÷øèé ìåòîä.M+ mÏóñòü åñòü îãðîìíàÿ, íå ðåøàþùàÿñÿ íà ÝÂÌ öåëèêîì ñèñòåìà Ax = b. Èòåðàöèîííûéïðîöåññxn+1 = xn − αn+1 (Axn − b)λmax (A)M=À 1.λmin (A)mÏðåäïîëîæèì èìååòñÿ ìàòðèöà B - ïåðåîáóñëîâëèâàòåëü:ñõîäèòñÿ ìåäëåííî, åñëèB > 0, 0 < m1 ≤(Ax, x)M1M≤ M1≤(Bx, x)m1mM1íå çàâèñèò îò ðàçìåðíîñòè çàäà÷è). È ïóñòü ñèñòåìó Bx = ...m1ðåøàòü ëåã÷å, ÷åì Ax = b.Òîãäà ïðåäëàãàåì ñëåäóþùèé èòåðàöèîííûé ïðîöåññ:(â èäåàëüíîì ñëó÷àåBxn+1xn+1 − xn+ Axn = b= Bx − αn+1 (Ax − b) ⇔ Bαn+1nn///Òâîð÷åñêèå .....: ïîñòðîèòü îáóñëî(à)âëèâàòåëü, îöåíèòü îòíîøåíèåM1- ñàìîåm1ìîäíîå íàïðàâëåíèå â ñîâð. âû÷èñë-îé ìàò-êå (îáòåêàíèå ñàìîëåòà,...)Ïåðâûé ïðåäñòàâèòåëü ìåòîäîâ: Ìåòîä Çåéäåëÿ â ïðåäïîëîæåíèè aii 6= 0iXj=1aij xn+1j+NXaij xnj = bi , i = 1, N .j=i+151Ïóñòü åñòü xn :xn+11xn+1i1=a111=aiiÃ!NPbi −j=2Ãbi −i−1Pj=1aij xnj ,aij xnj −NPj=i+1!aij xnj, i = 2, N .Ïî÷åìó îí çàï.

â âèäå....(êàê â àíîíñå):a110..A = A− + D + A+ , D =  ⇒ (D + A− )(xn+1 − xn ) + Axn = b ⇔.aN N− n+1⇔ (D+ A+ xn = b, αn+1 = 1 âñåãäà.| +{zA })xBÌåòîä âåðõíåé ðåëàêñàöèè.Ââîäèì ïàðàìåòð äëÿ óëó÷øåíèÿ−(D| +{zA })Bxn+1 − xn+ Axn = bωïðè ω = 1 - ÷àñòíûé ñëó÷àé ìåòîä Çåéäåëÿ.xn+1 − xnB+ Axn = b,z n = xn − xαz n+1 − z nB+ Az n = 0αx−x(òî÷íîå ðåøåíèå îáÿç.

óäîâë-åò B+ Ax = b)αÒåîðåìà:¯T¯A=A>0¯³α ´¯ ⇒ krn k → 0B− A >0 ¯n→∞2Äîê.αα2B(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+1 2n 2− z ), (z− z )) = 0kz kA − kz kA + + ((B − A)(zα |2{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→∞óæå õîðîøî52Ïîêàæåì, ÷òî îí = 0.αA)(z n+1 − z n ), (z n+1 − z n ))2− z n k → 0 â ∀ íîðìålim ((B −n→∞n+1kzB(z n+1 − z n ) + αAz n = 01z n = − A−1 B(z n+1 − z n ) ⇒ kz n k → 0.ααÌÏÈ: B = E.

Äëÿ ñõ-òè íóæíî: E − A > 0.xn+1 = xn − α(Axn − b).22!Ä/Ç : ïîêàçàòü, ÷òî ýòî âûï-íî ïðè α <∀ k.kkAkαÌ.Çåéäåëÿ. Ä/Ç : A = AT ≥ 0 ⇔ B − A > 02Ì.âåðõíåé ðåëàêñàöèè. Ä/Ç : 0 < ω < 2.13Ëåêöèÿ 13.A = AT > 0Ax = bBxn+1 − xn+ Axn = bααA > 0.2αÌåòîä Çåéäåëÿ: A = AT > 0 ⇔ B − A > 0, ãäå B = D + A− , α = 1.2Äîê.B − 1/2A = D + A− − 21 (A− + D + A+ ) = 1/2D + 1/2(A− + A+ )Òåîðåìà. B −(A− )T = A+(A+ )T = A−111((B − A)x, x) = (Dx, x) + ((A− − A+ )x, x)°=222=0akk = 0x = (0, ..., 1, ...0) 6= 0(Ax, x) = akk > 0 ⇒ ïðåäïîëîæåíèå íå âåðíî⇒ akk > 0 ⇒N11X°= (Dx, x) =aii x2i > 0÷.ò.ä.22 i=1Ðåøàåì ñèñòåìó XAx = b.Óòâåðæäåíèå.|aij | ≤ q|aii |0<q<1i6=j×åì áîëüøå äèàãîíàëüíîå ïðåîáëàäàíèå,òåì ëó÷øå ñõ-ñÿ ìåòîä Çåéäåëÿ.Äîê.

z n = xn − x. Ïåðåéäåì ê ÿçûêó ïîãðåøíîñòåéXXaij zjn+1aij zjn+1 −aii zin+1 = −|aii ||zin+1 |≤j<iXj<i|aij ||zjn |kz n+1 k∞ = |zkn+1 |,+j>iXj>i|aij ||zjn |zkn+1 - ñàìàÿ áîëüøàÿ êîìïîíåíòà53Ðàññìîòðèì äëÿ ñëó÷àÿ i = kXX|akk |kz n+1 k∞ ≤|akj |kz n+1 k∞ +|akj |kz n k∞j<k X⇒ kz n+1 k∞ ≤Xj>k|akk | −âûíîñèì kz n+1 k∞ ⇒j>k|akj |X|akj |kz n k∞ ≤ qkz n k∞ò.ê.X j<kX|akj | ≤ q|akk | −|akj | < q(|akk | −|akj |).j>kj<kA = AT > 0Ax = b÷.ò.ä.j<km ≤ λ(A) ≤ M(Ax, x)≤ M1B = B T > 0,0 < m1 ≤(Bx, x)Bxn+1 = Bxn − α(Axn − b)MÀ1mM1M¿m1mÒî÷íîå ðåøåíèå: Bx = Bx − α(Ax − b).

Характеристики

Список файлов лекций