В.Б. Андреев - Численные методы (2 в 1). (2007) (1160465), страница 11
Текст из файла (страница 11)
. . ,(8.2)ãäå B íåêîòîðàÿ ìàòðèöà, îïðåäåëÿþùàÿ èòåðàöèîííûé ìåòîä, à τ èòåðàöèîííûéïàðàìåòð.  ÷àñòíîñòè, â âèäå (8.2) ìîãóò áûòü çàïèñàíû ìåòîä ßêîáè, ìåòîä ÃàóññàÇåéäåëÿ, ìåòîä ïîñëåäîâàòåëüíîé âåðõíåé ðåëàêñàöèè, ìåòîä ïðîñòûõ èòåðàöèé. Ïðåäïîëîæèì, ÷òîA = AT > 0,B = B T > 0.(8.3)Ïðè ýòèõ ïðåäïîëîæåíèÿõ â êóðñå "Ââåäåíèå â ÷èñëåííûå ìåòîäû"äîêàçàíî, ÷òî åñëèB>τA,2(8.4)ò.å.
åñëè äëÿ ëþáîãî íåíóëåâîãî âåêòîðà x ñïðàâåäëèâî( Bx , x ) > τ2 ( Ax , x ), òî èòåðàöèîííûé ìåòîä (8.2) ÿâëÿåòñÿ ñõîäÿùèìñÿ.Äëÿ ìåòîäà ïðîñòûõ èòåðàöèé, êîòîðûé èìååò âèä (8.2) ñB = I , êðîìå òîãî, äàíà è îöåíêà ñêîðîñòè ñõîäèìîñòè. Èìåííî, åñëè(8.5)τ = 2/(λ1 + λn ),ãäå λ1 è λn , ñîîòâåòñòâåííî, íàèìåíüøåå è íàèáîëüøåå ñîáñòâåííûå çíà÷åíèÿ ìàòðèöûA, òî äëÿ ïîãðåøíîñòè èòåðàöèé ñïðàâåäëèâà îöåíêà°°°°° x − xk °6 q ° x − xk−1 °,q=λn − λ11 − λ1 /λn=< 1,λn + λ11 + λ1 /λn(8.6)ãäå k · k åâêëèäîâà äëèíà.Èç (8.6) ñëåäóåò, ÷òî åñëè λn À λ1 , òî ÷èñëî q î÷åíü áëèçêî ê åäèíèöå, à ñêîðîñòüñõîäèìîñòè èòåðàöèé î÷åíü íèçêàÿ.
Íî ïðè óêàçàííîì âûáîðå íîðìû âåêòîðàkAk = max λi (A) = λn ,ikA−1 k = max λi (A−1 ) = λ−11ièλn /λ1 = kAk kA−1 k = cond A := κ(A) := κ.Òàêèì îáðàçîì, åñëè ìàòðèöà A ïëîõî îáóñëîâëåíà, à ýòî òèïè÷íàÿ ñèòóàöèÿ, òî ìåòîäïðîñòûõ èòåðàöèé áóäåò ñõîäèòüñÿ î÷åíü ìåäëåííî.8.2. ÍÅßÂÍÛÅ ÌÅÒÎÄÛ818.2 Íåÿâíûå ìåòîäûÊàêèå åñòü ïóòè óâåëè÷åíèÿ ñêîðîñòè ñõîäèìîñòè èòåðàöèîííûõ ìåòîäîâ? Èçó÷èìâëèÿíèå ìàòðèöû B èç (8.2) íà ñêîðîñòü ñõîäèìîñòè.  ñèëó (8.3) ñóùåñòâóåò ìàòðèöàB 1/2 òàêàÿ, ÷òî¡¢TB 1/2 = B 1/2 > 0 è B 1/2 B 1/2 = B.Ýòà ìàòðèöà íàçûâàåòñÿ êâàäðàòíûì êîðíåì èç ìàòðèöû B .Íàïîìíèì ïîñòðîåíèå ìàòðèöû B 1/2 . Ïóñòü λ ñîáñòâåííîå çíà÷åíèå ìàòðèöû B , à ξ îòâå÷àþùèé åìó ñîáñòâåííûé âåêòîð, ò.å.
Bξ = λξ . Ïåðåíóìåðóåì âñå ñîáñòâåííûå çíà÷åíèÿ ìàòðèöû B è ââåäåì â ðàññìîòðåíèå äèàãîíàëüíóþ ìàòðèöó Λ = diag (λ1 , λ2 , . . . , λn ),îáðàçîâàííóþ ýòèìè ñîáñòâåííûìè çíà÷åíèÿìè, è îðòîãîíàëüíóþ ìàòðèöó Ξ = [ξ1 ξ2 . . . ξn ],îáðàçîâàííóþ îðòîíîðìèðîâàííûìè ñîáñòâåííûìè âåêòîðàìè ξi ìàòðèöû B , óïîðÿäî÷åííûìè â ñîîòâåòñòâèè ñ íóìåðàöèåé ñîáñòâåííûõ çíà÷åíèé. Ïîñêîëüêó ΞΛ = [λ1 ξ1 λ2 ξ2 . . . λn ξn ],òî BΞ = ΞΛ.
Îòñþäà ñëåäóåò, ÷òî B = ΞΛΞT .√ √√Î÷åâèäíî, ÷òî ìàòðèöà Λ1/2 = diag ( λ1 , λ2 , . . . , λn ). Ïîýòîìó B 1/2 = ΞΛ1/2 ΞT .Ââåäåì îáîçíà÷åíèåB 1/2 xk = y k ,¡¢−1xk = B 1/2 y k = B −1/2 y k .(8.7)Òîãäà (8.2) ìîæíî ïåðåïèñàòü òàêB 1/2y k+1 − y k+ AB −1/2 y k = b,τà ïîñëå ïðèìåíåíèÿ ê ýòîìó ñîîòíîøåíèþ ìàòðèöû B −1/2 , ïîëó÷èìy k+1 − y k+ B −1/2 AB −1/2 y k = B −1/2 b =: f.τ(8.8)B −1/2 AB −1/2 = C,(8.9)Îáîçíà÷àÿáóäåì èìåòü ñîîòíîøåíèÿy k+1 − y k+ Cy k = f,τk = 0, 1, . . . ,(8.10)êîòîðûå ïî ôîðìå ïîëíîñòüþ ñîâïàäàþò ñ (8.2). Î÷åâèäíî, ÷òî C = C T > 0, è ïîýòîìóäëÿ èòåðàöèîííîãî ìåòîäà (8.10) (à ýòî åñòü ìåòîä ïðîñòûõ èòåðàöèé) ïðèτ=2λ1 (C) + λn (C)(8.11)ñïðàâåäëèâà îöåíêà° k+1°°°°y− y °6 q(C) ° y k − y °,q(C) =λn (C) − λ1 (C)< 1,λn (C) + λ1 (C)(8.12)82 8.
ÈÒÅÐÀÖÈÎÍÍÛÅ ÌÅÒÎÄÛãäå λ1 (C) è λn (C) ñîîòâåòñòâåííî ìèíèìàëüíîå è ìàêñèìàëüíîå ñîáñòâåííûå çíà÷åíèÿ ìàòðèöû C :Cξ = λ(C)ξ.(8.13)Çäåñü ξ ñîáñòâåííûå âåêòîðû ìàòðèöû C . Ïîäñòàâëÿÿ â (8.13) ïðåäñòàâëåíèå C èç(8.9), ïîëó÷èìB −1/2 AB −1/2 ξ = λ(C)ξ,à, îáîçíà÷àÿB −1/2 ξ = η,ξ = B 1/2 ηè ïðèìåíÿÿ ê ïîñëåäíåé çàäà÷å ìàòðèöó B 1/2 , áóäåì èìåòü(8.14)Aη = λ(C)Bη.Òàêèì îáðàçîì, λ1 (C) è λn (C) ñóòü ìèíèìàëüíîå è ìàêñèìàëüíîå ñîáñòâåííûå çíà÷åíèÿ îáîáùåííîé çàäà÷è íà ñîáñòâåííûå çíà÷åíèÿ (8.14).Ïîäñòàâëÿÿ â (8.12) y k èç (8.7) è îáîçíà÷àÿ ( Bx , x ) = kxk2B , ïîëó÷èì° k°°°° x − x ° 6 q(C) ° xk−1 − x ° .BBÈòàê, åñëè B = B T > 0 òàêîâà, ÷òîλn /λ1 > λn (C)/λ1 (C),òî èòåðàöèîííûé ìåòîä (8.2), (8.11) ñ ýòîé ìàòðèöåé B áóäåò ñõîäèòüñÿ áûñòðåå (âñìûñëå B -íîðìû), ÷åì ìåòîä ïðîñòûõ èòåðàöèé.
Íàèáîëüøóþ ñêîðîñòü ñõîäèìîñòèìû ïîëó÷èì, âûáèðàÿ B = A. ÒîãäàC = I,è (8.2) ïðèíèìàåò âèäλ1 (C) = λn (C) = 1,τ =1Axk = b,÷òî ñ òî÷íîñòüþ äî îáîçíà÷åíèé ñîâïàäàåò ñ (8.1). Ìåòîä ñõîäèòñÿ çà îäíó èòåðàöèþ.Ëó÷øåãî áûòü íå ìîæåò. Íî ìû ïðèøëè ê òîìó, îò ÷åãî õîòåëè óéòè: íàì ñíîâà íóæíîðåøàòü ñèñòåìó (8.1). Îòñþäà ñëåäóåò, ÷òî íà âûáîð ìàòðèöû B íóæíî íàëîæèòüâåñüìà ñåðüåçíûå îãðàíè÷åíèÿ ìàòðèöà B äîëæíà áûòü îòíîñèòåëüíî ëåãêî îáðàòèìà.
Òàêîâûìè, íàïðèìåð, ÿâëÿþòñÿ äèàãîíàëüíûå è òðåóãîëüíûå ìàòðèöû. Õîòÿïîñëåäíèå è íå ÿâëÿþòñÿ ñèììåòðè÷íûìè, ýòî íåóäîáñòâî ëåãêî óñòðàíèòü, âûáèðàÿ â êà÷åñòâå B ïîäõîäÿùåå ïðîèçâåäåíèå òðåóãîëüíûõ ìàòðèö. Îäíàêî ñêîðîñòüñõîäèìîñòè ìåòîäà (8.2) ïðè òàêîì âûáîðå B èç î÷åâèäíûõ ñîîáðàæåíèé îñòàåòñÿñðàâíèòåëüíî íèçêîé. íàñòîÿùåå âðåìÿ íåèçâåñòíî ðåãóëÿðíûõ ñïîñîáîâ õîðîøåãî âûáîðà ìàòðèöûB äëÿ ïðîèçâîëüíîé A.
Âñå óäà÷íûå íàõîäêè òàê èëè èíà÷å ñâÿçàíû ñî ñïåöèôèêîéìàòðèöû A.8.3. ÍÅÑÒÀÖÈÎÍÀÐÍÛÅ ÈÒÅÐÀÖÈÎÍÍÛÅ ÌÅÒÎÄÛ838.3 Íåñòàöèîíàðíûå èòåðàöèîííûå ìåòîäûÄðóãîé ïóòü óâåëè÷åíèÿ ñêîðîñòè ñõîäèìîñòè èòåðàöèîííîãî ìåòîäà (8.2) ñîñòîèòâ òîì, ÷òîáû âìåñòî îäíîãî èòåðàöèîííîãî ïàðàìåòðà τ èñïîëüçîâàòü íåñêîëüêî ñâîé èòåðàöèîííûé ïàðàìåòð íà êàæäîé èòåðàöèè. Èòåðàöèîííûå ìåòîäû òàêîãî òèïàíàçûâàþòñÿ íåñòàöèîíàðíûìè è èìåþò âèäBxk+1 − xk+ Axk = b,τk+1k = 0, 1, . . .(8.15)k = 0, 1, . . . .(8.16)èëè ñ ó÷åòîì (8.7), (8.10)y k+1 − y k+ Cy k = f,τk+1Óêàæåì îäèí èç âîçìîæíûõ ñïîñîáîâ âûáîðà èòåðàöèîííûõ ïàðàìåòðîâ τk . Ââåäåìîáîçíà÷åíèåz k = y k − y,ãäå(8.17)Cy = f,è âû÷òåì (8.17) èç (8.16).
 ðåçóëüòàòå ïîëó÷èì çàäà÷ó äëÿ z k :z k+1 − z k+ Cz k = 0,τk+1Îòñþäàk = 0, 1, . . . ,z 0 = y 0 − y.(8.18)z k+1 = (I − τk+1 C)z k ,è, ñëåäîâàòåëüíî,kz =kY(I − τj C)z 0 ,(8.19)j=1ò.å.z k = Pk (C)z 0 ,ãäåPk (t) =kY(k)(k)(1 − τj t) = 1 + a1 t + · · · + ak tk .(8.20)j=1Èç (8.19) íàõîäèì, ÷òî°° k° ° k°°Y° °Y0° 6 ° (I − τj C)° kz 0 k.(I−τC)zkz k = ky − yk = °j°°° °kkj=1j=1(8.21)84 8. ÈÒÅÐÀÖÈÎÍÍÛÅ ÌÅÒÎÄÛÍî° 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 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
