В.Б. Андреев - Численные методы (1113834), страница 11
Текст из файла (страница 11)
ÈÒÅÐÀÖÈÎÍÍÛÅ ÌÅÒÎÄÛÍî° k°°¯ ¡¯ ¡°Y¢¯¢¯° (I − τj C)° = max ¯λl Pk (C) ¯ = max ¯Pk λl (C) ¯.°°ll(8.22)j=1Ïîñêîëüêó ìû õîòèì, ÷òîáû èòåðàöèè ñõîäèëèñü êàê ìîæíî áûñòðåå, òî ìîæíî ïîñòàâèòü çàäà÷ó î ìèíèìèçàöèè kPk (C)k â çàâèñèìîñòè îò èòåðàöèîííûõ ïàðàìåòðîâ τj ,j = 1, k .  ñèëó (8.20), (8.22) ýòà çàäà÷à ýêâèâàëåíòíà çàäà÷å ïîñòðîåíèÿ ìíîãî÷ëåíàPk (t) ñòåïåíè k ñ åäèíè÷íûì ñâîáîäíûì ÷ëåíîì, êîòîðûé â òî÷êàõ ñïåêòðà ìàòðèöû Cíàèáîëåå áëèçîê ê íóëþ. Íî ïîñòàâëåííàÿ çàäà÷à ïðàêòè÷åñêè íå ðàçðåøèìà. Îäíàêîâìåñòî íåå ìîæíî ïîñòàâèòü áëèçêóþ çàäà÷ó î ïîñòðîåíèè Pk (t), íàèìåíåå îòêëîíÿþùåãîñÿ îò íóëÿ íå íà ñïåêòðå, à íà îòðåçêå [λ1 , λn ], ãäå ýòîò ñïåêòð ðàñïîëîæåí. Ýòàçàäà÷à ìíîãî ïðîùå, è ðåøåíèå åå èçâåñòíî.
Íàéäåì ýòî ðåøåíèå.Èòàê, ñðåäè ìíîãî÷ëåíîâ ñòåïåíè k òàêèõ, ÷òî Qk (0) = 1 (ñì. (8.20)), òðåáóåòñÿíàéòè ìíîãî÷ëåí Pk (t), ìàêñèìóì ìîäóëÿ êîòîðîãî íà [λ1 , λn ] ìèíèìàëåí.Ëèíåéíîé çàìåíîé ïåðåìåííîé t = ax + b ïåðåâåäåì îòðåçîê [λ1 , λn ] â îòðåçîê[1, −1]. Èìååì¾λ1 + λnλ1 − λnλ1 =a + b,b=,a=,λn = −a + b22ò.å.·¸λn + λ1 λn − λ1λ1 + λnλn − λ11t=−x=1−x = [1 − ρ0 x],222λn + λ1τ0ãäåτ0 =2,λ1 + λnρ0 =λn − λ1< 1.λn + λ1(8.23)(8.24)Çàìåòèì, ÷òî τ0 ñîâïàäàåò ñ τ èç (8.5), (8.11) äëÿ ñòàöèîíàðíîãî èòåðàöèîííîãî ïðîöåññà, à ρ0 ñîâïàäàåò ñ q èç (8.6), (8.12) è õàðàêòåðèçóåò ñêîðîñòü ñõîäèìîñòè ýòîãîïðîöåññà.ÏóñòüPk (t) = Pbk (x).Ïîñêîëüêó t = 0 îòâå÷àåò òî÷êà x = ρ−10 (ñì.
(8.23)), òî äîëæíî áûòüµ ¶1Pk (0) = Pbk= 1.ρ0(8.25)(8.26)Íàøà çàäà÷à ñâåëàñü ê îòûñêàíèþ ìíîãî÷ëåíà Pbk (x), íàèìåíåå îòêëîíÿþùåãîñÿ îòíóëÿ íà [−1, 1] è óäîâëåòâîðÿþùåãî óñëîâèþ (8.26). Ñ ïîõîæåé çàäà÷åé ìû óæå ñòàëêèâàëèñü íà ïðîøëîé ëåêöèè. Ìû çíàåì, ÷òî ñðåäè ìíîãî÷ëåíîâ ñòåïåíè k âèäà xk +. . .íàèìåíåå îòêëîíÿåòñÿ îò íóëÿ íà [−1, 1] ìíîãî÷ëåíT k (x) =12k−1Tk (x),8.3. ÍÅÑÒÀÖÈÎÍÀÐÍÛÅ ÈÒÅÐÀÖÈÎÍÍÛÅ ÌÅÒÎÄÛ85ãäå Tk (x) ìíîãî÷ëåí ×åáûøåâà ïåðâîãî ðîäà.
Ðàçóìååòñÿ, ñàì ìíîãî÷ëåí ×åáûøåâàTk (x) ÿâëÿåòñÿ íàèìåíåå îòêëîíÿþùèìñÿ îò íóëÿ íà [−1, 1] ñðåäè ìíîãî÷ëåíîâ âèäàPk (x) = 2k−1 xk + . . . .³ ´Ïóñòü Tk ρ10 = q1k . Òîãäà î÷åâèäíî, ÷òî èñêîìîå ðåøåíèå äàåò ìíîãî÷ëåíPbk (x) = qk Tk (x).(8.27)Èç ñâîéñòâà 6◦ ìíîãî÷ëåíîâ Tk·1qk = ch k Archρ0¸−1< 1.(8.28)Ïîëó÷èì åùå îäíî ïðåäñòàâëåíèå äëÿ qk . Èç (8.28)ch k ArchÎòñþäà11= .ρ0qkpp1 + 1 − qk21 + 1 − ρ2011k Arch≡ k ln= Arch≡ ln.ρ0ρ0qkqkÏóñòüρp0ρ1 ==1 + 1 − ρ20rλn −λ1λn +λ1³λn − λ1´2 = λn + λ1 + 2√λ1 λn =λn −λ11 + 1 − λn +λ1p√√1 − λ1 /λnλn − λ1√ =p=√.λn + λ11 + λ1 /λnÒîãäàlnè1+p1 − qk2qk1+p= k ln1 − qk2qk(8.29)1= ln ρ−k1ρ1= ρ−k1 .Îòñþäà, ïåðåõîäÿ ê êâàäðàòíîìó óðàâíåíèþ îòíîñèòåëüíî qk2 , íàõîäèì, ÷òîqk =2ρ−k2ρk11.=1 + ρ2k1 + ρ−2k11Èòàê, ìû íàøëè òàêîé ìíîãî÷ëåíPbk (x) = qk Tk (x),(8.30)86 8.
ÈÒÅÐÀÖÈÎÍÍÛÅ ÌÅÒÎÄÛ÷òmax ¯Pbk (x)¯ = qk[−1,1]è, ñëåäîâàòåëüíî, â ñèëó (8.21), (8.7) èìååì îöåíêó ñõîäèìîñòèkz k k = kx − xk kB 6 qk kx − x0 kB .(8.31)Ïîëó÷èì ôîðìóëû äëÿ èòåðàöèîííûõ³ ïàðàìåòðîâτj . Èç (8.25), (8.27) è (8.23)´1−τ0 tñëåäóåò, ÷òî íóëè ïîëèíîìîâ Pk (t) è Tkñîâïàäàþò. Òàê êàê ïîëèíîì Pk (t)ρ0èìååò íóëè â òî÷êàõ t = 1/τj , j = 1, k , à íóëÿìè ïîëèíîìà ×åáûøåâà Tk (x) ÿâëÿþòñÿ÷èñëà (7.21)(2j − 1)π, j = 1, k,xj = − cos2kòî ñ ó÷åòîì (8.23) íàõîäèì, ÷òîτj =ãäåτ0,1 + ρ 0 µj½µj ∈ Mk =(8.32)j = 1, k,2i − 1− cosπ,2k¾i = 1, k .(8.33)Èç ïîëó÷åííîé ôîðìóëû äëÿ èòåðàöèîííûõ ïàðàìåòðîâ τj âèäíî, ÷òî äëÿ èõ âû÷èñëåíèÿ òðåáóåòñÿ çàäàòü ÷èñëî èòåðàöèé k . Êàê ýòî ñäåëàòü? Îáû÷íî â êà÷åñòâåóñëîâèÿ îêîí÷àíèÿ èòåðàöèîííîãî ïðîöåññà áåðåòñÿ íåðàâåíñòâî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) ñõîäÿòñÿ íåìåäëåííåå, ÷åì â îïòèìàëüíîì ìåòîäå ïðîñòûõ èòåðàöèé.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
