В.Б. Андреев - Численные методы (1113834), страница 12
Текст из файла (страница 12)
Èìåíík1 − λ1 /λnkkx − xkA 6kx0 − xkA ,1 + λ1 /λnãäå λ1 è λn ñóòü ìèíèìàëüíîå è ìàêñèìàëüíîå ñîáñòâåííûå çíà÷åíèÿ ìàòðèöû A.Äîêàçàòåëüñòâî. Èç (9.3)kz k+1 kA = k(I − τk+1 A)z k kA ,ïðè÷åì ïðàâàÿ ÷àñòü ïðèíèìàåò ìèíèìàëüíîå çíà÷åíèå èìåííî ïðè τk+1 èç (9.5).Òåì ñàìûì, ïðè ëþáîì äðóãîì çíà÷åíèè τk+1 ïðàâàÿ ÷àñòü áóäåò òîëüêî áîëüøå, è,ñëåäîâàòåëüíî,kz k+1 k2A 6 k(I − τ A)z k k2Aäëÿ ëþáîãî τ è, â ÷àñòíîñòè, äëÿτ=2λ1 + λn92 9. ÈÒÅÐÀÖÈÎÍÍÛÅ ÌÅÒÎÄÛ ÂÀÐÈÀÖÈÎÍÍÎÃÎ ÒÈÏÀ èòåðàöèîííîãî ïàðàìåòðà ìåòîäà ïðîñòûõ èòåðàöèé.Íî¡¢k(I − τ A)z k k2A = (I − τ A)z k , (I − τ A)Az k =¡¢= (I − τ A)A1/2 z k , (I − τ A)A1/2 z k == k(I − τ A)A1/2 z k k2 6 kI − τ Ak kz k k2A ,à â ñèëó (8.22), (8.27), (8.28), ïðè k = 1kI − τ Ak 6 max |1 − τ λ| = q1 = ρ0 =λ∈[λ1 ,λn ]1 − λ1 /λn.1 + λ1 /λnÑîáèðàÿ îöåíêè äëÿ âñåõ k , ïîëó÷èì óòâåðæäåíèå òåîðåìû.Èç òåîðåìû 9.1 ñëåäóåò, ÷òî íåñòàöèîíàðíûé ìåòîä (9.2), (9.5) ñðàâíèì ïî ñêîðîñòèñõîäèìîñòè ñ ìåòîäîì ïðîñòûõ èòåðàöèé, è, êàçàëîñü áû, ìû ñ ýòèì ìåòîäîì íåïðîäâèíóëèñü âïåðåä.
Îäíàêî, ó ýòèõ ìåòîäîâ èìååòñÿ ñóùåñòâåííîå ðàçëè÷èå. Äëÿèñïîëüçîâàíèÿ ìåòîäà ïðîñòûõ èòåðàöèé òðåáóåòñÿ èíôîðìàöèÿ î ãðàíèöàõ ñïåêòðàìàòðèöû A.  ñëó÷àå æå ìåòîäà (9.2), (9.5) òàêàÿ èíôîðìàöèÿ íå òðåáóåòñÿ.9.2 Íåóëó÷øàåìîñòü îöåíêèÏîêàæåì íà ïðèìåðå, ÷òî ïîëó÷åííàÿ îöåíêà ñõîäèìîñòè äîñòèãàåòñÿ, åñëè íà÷àëüíîåïðèáëèæåíèå çàäàíî ñïåöèàëüíûì îáðàçîì.
Äîïóñòèì, ÷òî x0 òàêîâî, ÷òîÃrx0 − x = z 0 = cλnξ1 +λ1rλ1ξnλn!,ãäå λ1 è λn ñóòü ìèíèìàëüíîå è ìàêñèìàëüíîå ñîáñòâåííûå çíà÷åíèÿ ìàòðèöû A èç(9.1), à ξ1 è ξn îòâå÷àþùèå èì îðòîíîðìèðîâàííûå ñîáñòâåííûå âåêòîðû. ÒîãäàAz 0 = cpλ1 λn (ξ1 + ξn ),pA2 z 0 = c λ1 λn (λ1 ξ1 + λn ξn ),(Az 0 , Az 0 ) = c2 λ1 λn 2,(A2 z 0 , Az 0 ) = c2 λ1 λn (λ1 + λn ). ñèëó (9.4)τ1 =2(Az 0 , Az 0 )=,2020(A z , A z )λ1 + λn9.2. ÍÅÓËÓ×ØÀÅÌÎÑÒÜ ÎÖÅÍÊÈ93à â ñèëó (9.3)rrpλnλ12z =cξ1 + cξn −c λ1 λn (ξ1 + ξn ) =λλnλ1 + λn"r 1 µ¶ rµ¶#λn2λ1λ12λn=cξ1 1 −+ξn 1 −=λ1λ1 + λnλnλ1 + λn"r#"r#rrλn − λ1λnλ1λnλ1=cξ1 −ξn = c ρξ1 −ξn .λn + λ1λ1λnλ1λn1Ïîñêîëüêókz 0 k2A = (Az 0 , z 0 ) = c2àpAz 1 = c ρÃrλ1 λnλn+λ1³pλ1 λn ξ1 −prλ1λn!= c2 (λ1 + λn ),´λ1 λn ξn ,kz 1 k2A = c2 ρ2 (λn + λ1 ) = ρ2 kz 0 k2A ,òîkz 1 kA = ρkz 0 k.Äåëàÿ ñëåäóþùóþ èòåðàöèþ, íàéäåì, ÷òîz 2 = ρ2 z 0è ò.ä.
Îòñþäà âûòåêàåò, ÷òîkz k kA = ρk kz 0 kA ,ò.å. ïîëó÷åííàÿ îöåíêà òî÷íàÿ.Ñëåäóåò, îäíàêî, çàìåòèòü, ÷òî òàêèå ïëîõèå íà÷àëüíûå ïðèáëèæåíèÿ â ðåàëüíûõ çàäà÷àõ ïðàêòè÷åñêè íå âñòðå÷àþòñÿ, è èòåðàöèè, îñîáåííî íà íà÷àëüíîì ýòàïå,ñõîäÿòñÿ ìíîãî áûñòðåå. Ïî ìåðå óâåëè÷åíèÿ ÷èñëà èòåðàöèé ñêîðîñòü ñõîäèìîñòèóìåíüøàåòñÿ è âûõîäèò íà òó, êîòîðàÿ ãàðàíòèðóåòñÿ îöåíêîé. Èìåÿ õîðîøåå íà÷àëüíîå ïðèáëèæåíèå, ìîæíî ïîëó÷èòü ïðèáëèæåííîå ðåøåíèå ñ õîðîøåé òî÷íîñòüþ ïðèñóùåñòâåííî ìåíüøèõ òðóäîçàòðàòàõ.94 9.
ÈÒÅÐÀÖÈÎÍÍÛÅ ÌÅÒÎÄÛ ÂÀÐÈÀÖÈÎÍÍÎÃÎ ÒÈÏÀ 10Ìåòîä ñîïðÿæåííûõ ãðàäèåíòîâÏîñòðîèì äðóãîé ìåòîä ìèíèìèçàöèè ôóíêöèè1J(x) = (Ax, x) − (b, x),2òî÷êà ìèíèìóìà êîòîðîé ñîâïàäàåò ñ ðåøåíèåì ñèñòåìûAx = b,A = AT > 0.(10.1)(10.2) ìåòîäå ñêîðåéøåãî ñïóñêà íà êàæäîì øàãå ïðîèñõîäèëà îäíîìåðíàÿ ìèíèìèçàöèÿâäîëü íàïðàâëåíèÿ, çàäàâàåìîãî àíòèãðàäèåíòîì, êîòîðûé ñîâïàäàåò ñ íåâÿçêîé rk =b−Axk . Ðàññìîòðèì òåïåðü ïîñëåäîâàòåëüíóþ ìèíèìèçàöèþ J(x) âäîëü ñîâîêóïíîñòèíàïðàâëåíèé {p1 , p2 , . . . }, êîòîðûå íå îáÿçàíû ñîâïàäàòü ñ íàïðàâëåíèÿìè íåâÿçîê{r0 , r1 , . .
. }.Ïóñòü íàïðàâëåíèÿ p1 , p2 , . . . çàäàíû, è (ñð. ñ (9.7))xk+1 = xk + αk+1 pk+1 ,k = 0, 1, . . . .(10.3)ÏîñêîëüêóJ(xk+1 ) = J(xk + αpk+1 ) =¢1¡=A(xk + αpk+1 ), xk + αpk+1 − (b, xk + αpk+1 ) =2α21= A(xk , xk ) + α(Axk , pk+1 ) + (Apk+1 , pk+1 ) − (b, xk ) − α(b, pk+1 ) =(10.4)222£¤ α= J(xk ) + α (Axk , pk+1 ) − (b, pk+1 ) + (Apk+1 , pk+1 ) =22α= J(xk ) − α(rk , pk+1 ) + (Apk+1 , pk+1 ),2òî, äèôôåðåíöèðóÿ ýòî âûðàæåíèå ïî α è ïðèðàâíèâàÿ ïðîèçâîäíóþ íóëþ, íàõîäèìèòåðàöèîííûé ïàðàìåòð(rk , pk+1 )αk+1 = k+1.(10.5)(p , Apk+1 )9596 10. ÌÅÒÎÄ ÑÎÏÐßÆÅÍÍÛÕ ÃÐÀÄÈÅÍÒÎÂÏîäñòàâëÿÿ (10.5) â (10.4), íàéäåì, ÷òîJ(xk+1 ) = J(xk )−(rk , pk+1 )1 (rk , pk+1 )2k k+1(r,p)+(Apk+1 , pk+1 ) =(pk+1 , Apk+1 )2 (pk+1 , Apk+1 )21 (rk , pk+1 )2= J(xk ) −,2 (pk+1 , Apk+1 )−(10.6)ò.å.
íà (k + 1) èòåðàöèè äåéñòâèòåëüíî áóäåò ïðîèñõîäèòü óìåíüøåíèå ôóíêöèè J(x),åñëè âûïîëíåíî óñëîâèå(rk , pk+1 ) 6= 0.(10.7)Çàìå÷àíèå 10.1. Áåç îãðàíè÷åíèÿ îáùíîñòè ìîæíî ïðåäïîëàãàòü, ÷òîx0 = 0.(10.8)Åñëè áû íàì áûëî èçâåñòíî õîðîøåå ïðèáëèæåíèå xe, òî, äåëàÿ çàìåíó x = xe +z , ìû áûíàøëè, ÷òî Az + Aex = b è Az = b − Aex. Òåì ñàìûì, äëÿ z íà÷àëüíûì ïðèáëèæåíèåìáûëî áû z 0 = 0.Èç (10.3) ñëåäóåò, ÷òî ïðè íà÷àëüíîì ïðèáëèæåíèè (10.8) âåêòîðû xk ÿâëÿþòñÿëèíåéíûìè êîìáèíàöèÿìè âåêòîðîâ p1 , p2 , . .
. , pk , ò.å.xk ∈ span{p1 , p2 , . . . , pk }.(10.9)Ïðè âûáîðå íàïðàâëåíèé pi íàøà çàäà÷à ñîñòîèò â òîì, ÷òîáû ãàðàíòèðîâàòüñõîäèìîñòü è äîáèòüñÿ ñêîðîñòè ñõîäèìîñòè áîëüøåé, ÷åì ó ìåòîäà ñêîðåéøåãî ñïóñêà.Ïðåäñòàâëÿåòñÿ, ÷òî íàèëó÷øèì ñïîñîáîì âûáîðà pi áûë áû òàêîé, ïðè êîòîðîì xk+1ìèíèìèçèðîâàë áû ôóíêöèþ J(x) íå òîëüêî ïî íàïðàâëåíèþ pk+1 , íî è ïî âñåìóïîäïðîñòðàíñòâóspan{p1 , p2 , . . . , pk+1 } ⊂ Rn , ò.å.J(xk+1 ) =minx∈span{p1 ,p2 ,...,pk+1 }J(x).(10.10)Åñëè áû òàêîé âûáîð pi óäàëîñü îñóùåñòâèòü, òî ýòî íå òîëüêî ãàðàíòèðîâàëî áûñõîäèìîñòü, íî ïðèâåëî áû ê êîíå÷íîñòè èòåðàöèîííîãî ïðîöåññà, èáî ïðè k + 1 = n èëèíåéíî íåçàâèñèìûõ pi çàäà÷à (10.10) ïðåäñòàâëÿåò ñîáîé èñõîäíóþ çàäà÷ó ãëîáàëüíîé ìèíèìèçàöèè, è, ñëåäîâàòåëüíî, Axn = b.Ïîïûòàåìñÿ ðåøèòü ïîñòàâëåííóþ çàäà÷ó. Ïóñòü¤£Pk = p1 p2 .
. . pkåñòü (n × k)-ìàòðèöà, ñòîëáöàìè êîòîðîé ÿâëÿþòñÿ èñêîìûå íàïðàâëåíèÿ. Ïóñòü x =Pk y + αpk+1 ∈ im Pk+1 ,1 y ∈ Rk , α ∈ R. Òîãäà (ñì. (10.4))J(x) = J(Pk y) + α(APk y, pk+1 ) +1 Íàïîìíèì,α2(Apk+1 , pk+1 ) − α(b, pk+1 ).2(10.11)÷òî ìíîæåñòâî âñåõ âåêòîðîâ x, ïðåäñòàâèìûõ â âèäå x = By , íàçûâàåòñÿ îáðàçîììàòðèöû B è îáîçíà÷àåòñÿ im B .97Åñëè áû â (10.11) îòñóòñòâîâàë "ïåðåêðåñòíûé"÷ëåíα(Pk y, Apk+1 ),òî çàäà÷à ìèíèìèçàöèè J(x) íà span {p1 , p2 , . . . , pk+1 } = im Pk+1 , ò.å.
çàäà÷à (10.10),ðàñïàëàñü áû íà ìèíèìèçàöèþ ïî im Pk , ãäå ðåøåíèå xk ïðåäïîëàãàåòñÿ èçâåñòíûì, èïðîñòóþ ìèíèìèçàöèþ äëÿ îïðåäåëåíèÿ ñêàëÿðíîé âåëè÷èíû α. ñàìîì äåëå, ïóñòü âûïîëíåíû óñëîâèÿ(pi , Apj ) = 0,i 6= j.(10.12)(Âåêòîðû, óäîâëåòâîðÿþùèå óñëîâèþ (10.12), íàçûâàþòñÿA-ñîïðÿæåííûìè èëè A-îðòîãîíàëüíûìè.) Îïðåäåëèì âåêòîð xk ∈ im Pk è αk+1 ∈ Rñëåäóþùèì îáðàçîìJ(xk ) = min J(Pk y),yαk+1 =(b, pk+1 ).(pk+1 , Apk+1 )(10.13)Òîãäà (ñì. (10.11))½min J(Pk y + αpy,αk+1) = min J(Pk y) + minyα¾α2k+1 k+1k+1(Ap , p ) − α(b, p )2íàõîäèòñÿ ïðè Pk y = xk è α = αk+1 èç (10.13).
Ïîêàæåì, ÷òî íà ñàìîì äåëå αk+1 èç(10.13) ñîâïàäàåò ñ (10.5).  ñèëó (10.9) è (10.12)(Apk+1 , xk ) = 0è, ñëåäîâàòåëüíî,(pk+1 , b) = (pk+1 , b − Axk + Axk ) = (pk+1 , rk ),(10.14)÷òî âìåñòå ñ (10.13) ïðèâîäèò ê (10.5).Èòàê, äëÿ ðåàëèçàöèè çàäóìàííîãî ìåòîäà íóæíî ïîñëåäîâàòåëüíî íàõîäèòü Añîïðÿæåííûå âåêòîðû p1 , p2 , . . . , pk+1 , äëÿ êîòîðûõ âûïîëíåíî óñëîâèå (10.7), è ïðîâîäèòü âû÷èñëåíèÿ ïî ôîðìóëå (10.3) ñ ïàðàìåòðîì αk+1 èç (10.5).Îáðàòèìñÿ ê íàèáîëåå öåëåñîîáðàçíîìó âûáîðó âåêòîðîâ pk+1 . Ïðè âûáîðå pk+1íàøà öåëü ñîñòîèò â áûñòðåéøåé ìèíèìèçàöèè ôóíêöèè J(x), è â ñèëó (10.6) ìûäîëæíû ìàêñèìèçèðîâàòü(rk , pk+1 )2.(pk+1 , Apk+1 )Çàìå÷àíèå 10.2. Ýòà âåëè÷èíà íå çàâèñèò îò äëèíû âåêòîðà pk+1 , à çàâèñèò òîëüêî îòåãî íàïðàâëåíèÿ.
Ïîýòîìó ïðè îòûñêàíèè pk+1 äîñòàòî÷íî îãðàíè÷èòüñÿ íàõîæäåíèåìåãî íàïðàâëåíèÿ.98 10. ÌÅÒÎÄ ÑÎÏÐßÆÅÍÍÛÕ ÃÐÀÄÈÅÍÒÎÂÏîñêîëüêó pk+1 äîëæåí åùå óäîâëåòâîðÿòü óñëîâèÿì A-ñîïðÿ-æåííîñòè (10.12),ò.å. áûòü îðòîãîíàëüíûì ê {Ap1 , Ap2 , . . . , Apk }, òî èñêîìûé âåêòîð¡¢⊥pk+1 ∈ span {Ap1 , Ap2 , . . . , Apk } = (im APk )⊥ .kkÏóñòü rk = rkk + r⊥, ãäå rkk ∈ im (APk ), à r⊥∈ (im (APk ))⊥ .
Òîãäàkkkk, pk+1 )k kpk+1 k cos(r⊥, pk+1 ) = kr⊥, pk+1 ) = (r⊥(rk , pk+1 ) = (rkk + r⊥k, pk+1 )| = 1, ò.å., íàïðèìåð, ïðèè èñêîìûé ìàêñèìóì áóäåò äîñòèãàòüñÿ ïðè | cos(r⊥k∈ (im (APk ))⊥pk+1 = r⊥(10.15) îðòîãîíàëüíîé ïðîåêöèè rk íà (im (APk ))⊥ . Îòìåòèì, ÷òî îòñþäà ñëåäóåò ñîîòíîøåíèåp1 = r 0 .(10.16)Ïîñòðîåíèå ïðîöåññà ìèíèìèçàöèè J(x) â ïåðâîì ïðèáëèæåíèè áóäåò çàêîí÷åíî, åñëèïðèíÿòü âî âíèìàíèå, ÷òî èìååò ìåñòîÒåîðåìà 10.1. Äâà ïîñëåäîâàòåëüíûõ íàïðàâëåíèÿ ñïóñêà â ìåòîäå ñîïðÿæåííûõãðàäèåíòîâ ñâÿçàíû ñîîòíîøåíèåìpk+1 = rk + βk+1 pk .(10.17)Äîêàçàòåëüñòâî ýòîé òåîðåìû ìû îòëîæèì íà ïîòîì, à ñåé÷àñ çàìåòèì, ÷òî ïîñêîëüêó âåêòîðû pk è pk+1 äîëæíû áûòü A-ñîïðÿæåíû, òî äëÿ ïàðàìåòðà βk+1 èç(10.17) èìååò ìåñòî ïðåäñòàâëåíèåβk+1 = −(rk , Apk ).(pk , Apk )(10.18)Èòàê, ìåòîä ñîïðÿæåííûõ ãðàäèåíòîâ ñîñòîèò â âû÷èñëåíèÿõ ïî ñëåäóþùèì ôîðìóëàìrk = b − Axk ,k = 0, 1, . .
. ,pk+1 = rk + βk+1 pk ,k = 1, 2, . . . ,xk+1 = xk + αk+1 pk+1 ,k = 0, 1, . . . ,αk+1 = (rk , pk+1 )/(pk+1 , Apk+1 ),kkkkβk+1 = −(Ap , r )/(Ap , p ),p1 = r 0 ,x0 = 0,(10.19)k = 0, 1, . . . ,k = 1, 2, . . . ,Äàäèì îöåíêó ñêîðîñòè ñõîäèìîñòè ìåòîäà ñîïðÿæåííûõ ãðàäèåíòîâ. Èìååò ìåñòîÒåîðåìà 10.2.
Ìåòîä ñîïðÿæåííûõ ãðàäèåíòîâ (10.19)ñõîäèòñÿ íå õóæå, ÷åì÷åáûøåâñêèé èòåðàöèîííûé ìåòîä, ò.å.ikhpp±kkx − xkA 6 2 (1 − λ1 /λn ) (1 + λ1 /λn ) kxkA ,ãäå λ1 è λn ìèíèìàëüíîå è ìàêñèìàëüíîå ñîáñòâåííûå çíà÷åíèÿ ìàòðèöû A.99Äîêàçàòåëüñòâî. Ïîêàæåì ñíà÷àëà, ÷òî ìèíèìèçàöèÿ J(xk ) âåäåò ê ìèíèìèçàöèèkxk − xkA .  ñàìîì äåëå, ïóñòüz k = xk − x.Òîãäà, ïîäñòàâëÿÿ xk = x + z k â J(xk ) è ïðèíèìàÿ âî âíèìàíèå (10.4) ñ çàìåíîé xk íàx, αk+1 pk+1 íà z k , à xk+1 íà xk , áóäåì èìåòü1J(xk ) = kz k k2A + J(x).2(10.20)Óñòàíîâèì òåïåðü ñâÿçü ìåæäó z k íà ïîñëåäîâàòåëüíûõ èòåðàöèÿõ.
Èç òðåòüåãîñîîòíîøåíèÿ (10.19) íàõîäèì, ÷òîpk+1 = (xk+1 − xk )/αk+1 .Ïîäñòàâèì ýòî ïðåäñòàâëåíèå pk+1 âî âòîðîå ñîîòíîøåíèå (10.19)xk+1 − xkxk − xk−1− βk+1= b − Axk .αk+1αkÎòñþäà íàõîäèì, ÷òîz k+1 − z kz k − z k−1− βk+1+ Az k = 0.αk+1αkÄàëåå,z 1 = z 0 + α1 p1 = z 0 + α1 r0 = z 0 + α1 b = z 0 + α1 Ax = z 0 − α1 Az 0 .Òåì ñàìûì,èz k = pk (A)z 0 ,pk (0) = 1kz k kA = kpk (A)z 0 kA .Íî ïî ïîñòðîåíèþ xk è ñ ó÷åòîì (10.20)kz k kA = min kqk (A)z 0 kA ,qkq(0) = 1è, ñëåäîâàòåëüíî,kz k kA 6 kqk (A)z 0 kA = kqk (A) A1/2 z 0 k2 6 kqk (A)k kz 0 kA 6 max |qk (t)|kz 0 kA =λ1 6t6λn¯ µ¶¯¯¯¯¯λn + λ1 λn − λ1= max ¯¯ qk−y ¯¯ kz 0 kA = max ¯ q̂k (y) ¯ kz 0 kA .y∈[−1,1]y∈[−1,1]22Åñëè ïîëîæèòü Q̂k (y) = qk Tk (y) (ñì.
ëåêöèþ 8), òî!kÃpk1−λ/λ2ρ1n1pkz 0 kA .kz k kA 6 qk kz 0 kA =kz 0 kA 6 21 + 2ρ2k1+λ/λ11nÒåîðåìà äîêàçàíà.100 10. ÌÅÒÎÄ ÑÎÏÐßÆÅÍÍÛÕ ÃÐÀÄÈÅÍÒÎÂ×òîáû îïèñàíèå ìåòîäà ñîïðÿæåííûõ ãðàäèåíòîâ (10.19) áûëî êîððåêòíûì, íóæíî äîêàçàòü òåîðåìó 10.1 (î ñâÿçè ìåæäó äâóìÿ ïîñëåäîâàòåëüíûìè íàïðàâëåíèÿìèñïóñêà). Äëÿ ýòîãî íàì ïîíàäîáèòñÿ ðÿä âñïîìîãàòåëüíûõ óòâåðæäåíèé.Ëåììà 10.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
