В.Б. Андреев - Численные методы (2 в 1). (2007) (1160465), страница 12
Текст из файла (страница 12)
Êàê ýòî ñäåëàòü? Îáû÷íî â êà÷åñòâåóñëîâèÿ îêîí÷àíèÿ èòåðàöèîííîãî ïðîöåññà áåðåòñÿ íåðàâåíñòâîkz k kB 6 εkz 0 kBè ÷èñëîì èòåðàöèé íàçûâåòñÿ íàèìåíüøåå èç ÷èñåë k , äëÿ êîòîðûõ ýòî íåðàâåíñòâîâûïîëíÿåòñÿ. Èç (8.31) ñëåäóåò, ÷òî äëÿ ðàññìàòðèâàåìîãî èòåðàöèîííîãî ìåòîäà÷èñëî èòåðàöèé íàõîäèòñÿ èç íåðàâåíñòâà qk 6 ε. Ðåøèì ýòî íåðàâåíñòâî, èñïîëüçóÿ(8.30):2ρk16 ε.1 + ρ2k1Ýòî íåðàâåíñòâî ýêâèâàëåíòíî ñëåäóþùåìó íåðàâåíñòâó√√µ¶µ¶1 + 1 − ε21 − 1 − ε2kkρ1 −ρ1 −> 0.εεÏîñêîëüêó ρ1 < 1, òî ïåðâûé ñîìíîæèòåëü îòðèöàòåëåí, è äîëæíî âûïîëíÿòüñÿóñëîâèå√1−ε1 − ε2√=ρk1 6.ε1 + 1 − ε28.3.
ÍÅÑÒÀÖÈÎÍÀÐÍÛÅ ÈÒÅÐÀÖÈÎÍÍÛÅ ÌÅÒÎÄÛÎòñþäà87√1 − ε2εk>.ln 1/ρ1Ïîñêîëüêó ε îáû÷íî ìàëî, òî ïîëüçóþòñÿ ñëåäóþùåé ôîðìóëîéln1+k>ln 2/ε.ln 1/ρ1Ñðàâíèì ñêîðîñòè ñõîäèìîñòè ïîñòðîåííîãî íåñòàöèîíàðíîãî èòåðàöèîííîãî ìåòîäà ñ îïòèìàëüíûì ìåòîäîì ïðîñòûõ èòåðàöèé. Èç (8.6) ñëåäóåò, ÷òî äëÿ îïòèìàëüíîãîìåòîäà ïðîñòûõ èòåðàöèékx − xk k 6 qkx − xk−1 k,ãäå1 − λ1 /λn= ρ01 + λ1 /λnq=è, ñëåäîâàòåëüíî,kx − xk k 6 q k kx − x0 k.Åñëè ìû è çäåñü ïîòðåáóåì, ÷òîáûkx − xk k 6 εkx − x0 k,òî äëÿ ÷èñëà èòåðàöèé k áóäåì èìåòük ln11> ln ,ρ0εò.å.k>ln 1/ε.ln 1/ρ0(8.34)Äëÿ ïëîõî îáóñëîâëåííîé ìàòðèöû Aλ1 /λn = [cond A]−1 ¿ 1,è ïîýòîìó1= 1 + 2(cond A)−1 + O((cond A)−2 ).ρ0Îòñþäà è èç (8.34)1cond A ln 1/ε.2Äëÿ îïòèìàëüíîãî èòåðàöèîííîãî ìåòîäà áóäåì èìåòüpp1+(cond A)−1p=ρ−1=1+2(cond A)−1 + O((cond A)−1 )11 − (cond A)−1k≈èk≈÷òî ìíîãî ëó÷øå, ÷åì (8.35).1(cond A)1/2 ln 2/ε.
,2(8.35)88 8. ÈÒÅÐÀÖÈÎÍÍÛÅ ÌÅÒÎÄÛ8.4 Îá óñòîé÷èâîñòèÊ ñîæàëåíèþ, âû÷èñëåíèÿ ïî ôîðìóëàì (8.15) ïðè ïðîèçâîëüíîì èñïîëüçîâàíèè èòåðàöèîííûõ ïàðàìåòðîâ íå ÿâëÿþòñÿ óñòîé÷èâûìè.M0 = 10−p ìàøèííûé íóëü.M∞ = 10p áåñêîíå÷íîñòü.103p/4 ,10p/2 ,Y10p/4 ,10−p/2 ,10−3p/4= 10p/4 ∈ [M0 , M∞ ]p/4−p/23p/4p/210· 10−3p/4} = M∞|{z· 10 } ·10 · 10|{z−p/210· 10−3p/4} ·10p/4 · |103p/4{z· 10p/2} = M0{z|10−3p/4 10p/2 103p/4 10−p/2 10p/4 9Èòåðàöèîííûå ìåòîäû âàðèàöèîííîãîòèïà9.1 Ìåòîä ñêîðåéøåãî ñïóñêàÂíîâü îáðàòèìñÿ ê ðåøåíèþ ñèñòåìûAx = b,A = AT > 0.(9.1)Áóäåì äëÿ ïðîñòîòû èñïîëüçîâàòü ÿâíûé íåñòàöèîíàðíûé ìåòîäxk+1 − xk+ Axk = b,τk+1k = 0, 1, . .
. .(9.2) ïðåäûäóùåé ëåêöèè áûë óêàçàí ñïîñîá âûáîðà èòåðàöèîííûõ ïàðàìåòðîâ τk , èñïîëüçóþùèé àïðèîðíóþ èíôîðìàöèþ î ðàñïîëîæåíèè ñïåêòðà ìàòðèöû A. Ñåé÷àñìû ðàññìîòðèì äðóãîé ñïîñîá âûáîðà ýòèõ ïàðàìåòðîâ.Ïóñòü, êàê îáû÷íî, z k = xk − x. Òîãäàz k+1 = z k − τk+1 Az k .(9.3)Âû÷èñëèì A-íîðìó ïîãðåøíîñòè z k+1 è âûðàçèì åå ÷åðåç z k . Èñïîëüçóÿ (9.3), íàõîäèì,÷ò ¡¡kz k+1 k2A := Az k+1 , z k+1 = A(z k − τk+1 Az k ), z k − τk+1 Az k =¡¢¡ 2 k¢2A z , Az k .= kz k k2A − 2τk+1 Az k , Az k + τk+1Âûáåðåì τk+1 èç óñëîâèÿ ìèíèìóìà kz k+1 k2A . Äèôôåðåíöèðóÿ ïî τk+1 è ïðèðàâíèâàÿïðîèçâîäíóþ íóëþ, íàéäåì, ÷òî¡¢¡¢−2 Az k , Az k + 2τk+1 A2 z k , Az k = 0,ò.å.τk+1 =(Az k , Az k ).(A2 z k , Az k )89(9.4)90 9.
ÈÒÅÐÀÖÈÎÍÍÛÅ ÌÅÒÎÄÛ ÂÀÐÈÀÖÈÎÍÍÎÃÎ ÒÈÏÀÊàçàëîñü áû, ÷òî ýòî ñîîòíîøåíèå íå ïîçâîëÿåò íàéòè èíòåðåñóþùèé íàñ ïàðàìåòðτk+1 , ïîñêîëüêó z k+1 = xk − x íå èçâåñòíà. Íî íàì îíà è íå íóæíà. Íàì íóæíàAz k = Axk − Ax = Axk − b = −rk .Âåëè÷èíà rk íàçûâàåòñÿ íåâÿçêîé. Òåì ñàìûì,τk+1 =(rk , rk ),(Ark , rk )rk = b − Axk .(9.5)Ìåòîä (9.2), (9.5) íàçûâåòñÿ ìåòîäîì ñêîðåéøåãî ñïóñêà.Äàäèì ãåîìåòðè÷åñêóþ èíòåðïðåòàöèþ ýòîãî ìåòîäà, êîòîðàÿ è îáúÿñíèò åãî íàçâàíèå. Ïóñòü1J(x) = (Ax, x) − (b, x)(9.6)2 êâàäðàòè÷íàÿ ôóíêöèÿ n ïåðåìåííûõ x1 , x2 , . . .
, xn . Ïîñòàâèì çàäà÷ó îá îòûñêàíèè òî÷êè ìèíèìóìà ýòîé ôóíêöèè. Äëÿ ðåøåíèÿ ýòîé çàäà÷è íóæíî íàéòè ïåðâûåïðîèçâîäíûå (9.6) ïî x1 , x2 , . . . , xn è ïðèðàâíÿòü èõ íóëþ. Ýòî è áóäóò óðàâíåíèÿ äëÿíàõîæäåíèÿ òî÷êè ìèíèìóìà. Ïåðåïèøåì (9.6) â êîîðäèíàòíîì âèäåJ(x) =nnX1 Xakj xk xj −b k xk2 k,j=1k=1è ïðîäèôôåðåíöèðóåì ïî xinnnX∂J(x)1X1Xaki xk − bi =aij xj − bi ,=aij xj +∂xi2 j=12 k=1j=1i = 1, . . . , n.Çàìå÷àíèå 9.1.
grad J = Ax − b.Èç ìàòåìàòè÷åñêîãî àíàëèçà èçâåñòíî, ÷òî ôóíêöèÿ íàèáîëåå áûñòðî óáûâàåò âíàïðàâëåíèè àíòèãðàäèåíòà.Èòàê, çàäà÷à îòûñêàíèÿ òî÷êè ìèíèìóìà ôóíêöèè (9.6) ýêâèâàëåíòíà ðåøåíèþñèñòåìû (9.1) ñ ñèììåòðè÷íîé ìàòðèöåé. Åñëè ìû íàéäåì ñïîñîá ïðèáëèæåííîãîíàõîæäåíèÿ òî÷êè ìèíèìóìà ôóíêöèè (9.6), òî ìû áóäåì èìåòü ìåòîä ïðèáëèæåííîãîíàõîæäåíèÿ ðåøåíèÿ ñèñòåìû (9.1).Ïîñòðîèì ìåòîä ìèíèìèçàöèè (9.6).
Ïðèìåíèòåëüíî ê (9.6)∇J(x) = Ax − b,è ïðîöåññ ìèíèìèçàöèè ïðèíèìàåò âèäxk+1 = xk − α∇J(xk ) = xk − α(Axk − b) = xk + αrk(9.7)9.1. ÌÅÒÎÄ ÑÊÎÐÅÉØÅÃÎ ÑÏÓÑÊÀ91èëèxk+1 − xk+ Axk = b,α÷òî ñîâïàäàåò ñ (9.2) ñ òî÷íîñòüþ äî îáîçíà÷åíèÿ èòåðàöèîííîãî ïàðàìåòðà. Äëÿîïðåäåëåíèÿ çíà÷åíèÿ α ðàññìîòðèìJ(xk+1 ) = J(xk − α∇J(xk ))(9.8)êàê ôóíêöèþ α è íàéäåì òàêîå çíà÷åíèå α, ïðè êîòîðîì J ïðèíèìàåò íàèìåíüøååçíà÷åíèå.  íàøåì ñëó÷àå¢1¡A(xk − α(Axk − b)), xk − α(Axk − b) − (b, xk − α(Axk − b)) =2¢1¡=A(xk + αrk ), xk + αrk − (b, xk + αrk ).2J(xk − α∇J(xk )) =Äèôôåðåíöèðóÿ ïî α è ïðèðàâíèâàÿ ïðîèçâîäíóþ íóëþ, íàõîäèì, ÷òî¡¢A(xk + αrk ), rk − (b, rk ) = 0,îòêóäàα = αk+1 =(rk , rk ),(Ark , rk )÷òî ñîâïàäàåò ñ ðàíåå ïîëó÷åííûì çíà÷åíèåì (9.5) èòåðàöèîííîãî ïàðàìåòðà.
Òåìñàìûì, îáà ìåòîäà ñîâïàäàþò, à âòîðîé ìåòîä äàåò èì íàçâàíèå.Èìååò ìåñòîÒåîðåìà 9.1. Èòåðàöèè ïî ìåòîäó ñêîðåéøåãî ñïóñêà (9.2), (9.5) ñõîäÿòñÿ íåìåäëåííåå, ÷åì â îïòèìàëüíîì ìåòîäå ïðîñòûõ èòåðàöèé. Èìåíí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 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
