В.Б. Андреев - Численные методы (2 в 1). (2007) (1160465), страница 13
Текст из файла (страница 13)
. . 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. Ïóñòü p1 , p2 , . .
. , pk ñóòü íåíóëåâûå A-ñîïðÿæåííûå âåêòîðû. Òîãäà,ëèáî ñóùåñòâóåò A-ñîïðÿæåííûé ê íèì âåêòîð pk+1 , óäîâëåòâîðÿþùèé óñëîâèþ(10.7), ëèáî rk = 0.Äîêàçàòåëüñòâî. Ïóñòü íå ñóùåñòâóåò òàêîãî A-ñîïðÿæåííîãî ñ p1 , p2 , . . . , pk âåê-òîðà pk+1 , äëÿ êîòîðîãî âûïîëíåíî óñëîâèå (10.7), ò.å. äëÿ ëþáîãî âåêòîðàp ⊥ {Ap1 , Ap2 , . . . , Apk } = im APk(10.21)( rk , p ) = 0.(10.22)èìååò ìåñòî ðàâåíñòâîÍàïîìíèì, ÷òî â ñèëó (10.14) äëÿ ëþáîãî âåêòîðà p, óäîâëåòâîðÿþùåãî (10.21),( p , rk ) = ( p , b )è, ñëåäîâàòåëüíî, (ñì. (10.22)),( p , Ax ) = 0.Òåì ñàìûì, ðåøåíèå x ∈ im Pk . Íî xk ìèíèìèçèðóåò J(x) íà im Pk è, ñëåäîâàòåëüíî,xk = x, ò.å. rk = 0. Îòñþäà æå âûòåêàåò, ÷òî, åñëè rk 6= 0, òî ñóùåñòâóåò pk+1 èç (10.21),äëÿ êîòîðîãî âûïîëíåíî óñëîâèå (10.7).
Ëåììà äîêàçàíà.Çàìå÷àíèå 10.3. Ëåììà 10.1 óòâåðæäàåò, ÷òî ëèáî ìû íà k -îé èòåðàöèè çàêîí÷èëèâû÷èñëåíèÿ, ïîëó÷èâ òî÷íîå ðåøåíèå çàäà÷è (10.2), ëèáî èìååì âîçìîæíîñòü âû÷èñëåíèÿ ïðîäîëæèòü.Òåîðåìà 10.3. Ïîñëå k èòåðàöèé ìåòîäà ñîïðÿæåííûõ ãðàäèåíòîâ ïðè êàæäîì jîò 1 äî kspan {p1 , p2 , . . . , pj } = span {r0 , r1 , . . . , rj−1 } ==span {b, Ab, .
. . , Aj−1 b} =: Kj (A, b).(10.23)Äîêàçàòåëüñòâî ïðîâåäåì ìåòîäîì ïîëíîé ìàòåìàòè÷åñêîé èíäóêöèè. Ïðè j = 1ñîîòíîøåíèÿ (10.23) èìåþò ìåñòî, èáî â ñèëó âûáîðà (10.8) íà÷àëüíîãî ïðèáëèæåíèÿr0 = b, à èç (10.16) p1 = r0 . Ïðåäïîëîæèì, ÷òî (10.23) ñïðàâåäëèâû ïðè íåêîòîðîì j ,óäîâëåòâîðÿþùåì íåðàâåíñòâó 1 6 j < k . Äîêàæåì èõ ñïðàâåäëèâîñòü ïðè j + 1. êà÷åñòâå ïåðâîãî øàãà ïîêàæåì, ÷òîspan {p1 , p2 , .
. . , pj+1 } ⊂ span {r0 , r1 , . . . , rj }. ñèëó (10.15)jpj+1 = r⊥= rj − rqj ,rqj ∈ im [APj ](10.24)101è, ñëåäîâàòåëüíî,pj+1 = rj − APj yj ,Èç (10.3) âûòåêàåò, ÷òîyj ∈ Rj .(10.25)Axj = Axj−1 + αj Apj .Âû÷èòàÿ èç îáåèõ ÷àñòåé ýòîãî ðàâåíñòâà ïî b, áóäåì èìåòürj = rj−1 − αj Apjè, ñëåäîâàòåëüíî,(10.26)Apj = −(rj − rj−1 )/αj .Ïîäñòàâëÿÿ ýòî ïðåäñòàâëåíèå â (10.25), íàõîäèì, ÷òî· 1¸rj − rj−1r − r0 r2 − r1j+1jp=r +...yj .α1α2αjÎòñþäà è èç ïðåäïîëîæåíèÿ èíäóêöèè ñëåäóåò âêëþ÷åíèå (10.24).Òåïåðü óñòàíîâèì âêëþ÷åíèåspan {r0 , r1 , . .
. , rj } ⊂ span {b, Ab, . . . , Aj b}.(10.27)Ïî ïðåäïîëîæåíèþ èíäóêöèè âåêòîðû pj ∈ span {b, Ab, . . . , Aj−1 b}. ÏîýòîìóApj ∈ span {b, Ab, . . . , Aj b}.Åñëè òåïåðü ïðèíÿòü âî âíèìàíèå âêëþ÷åíèårj−1 ∈ span {b, Ab, . . . , Aj−1 b}, òî èç (10.26) íàéäåì, ÷òîrj ∈ span {b, Ab, . . . , Aj b}.Âíîâü ïðèíèìàÿ âî âíèìàíèå ïðåäïîëîæåíèå èíäóêöèè, áóäåì èìåòü æåëàåìîå âêëþ÷åíèå (10.27).Èòàê, âìåñòî ðàâåíñòâà (10.23) ìû ïîêà èìååì òîëüêî âêëþ÷åíèÿ (10.24), (10.27)ïðîñòðàíñòâ, ðàçìåðíîñòü êàæäîãî èç êîòîðûõ íå ïðåâûøàåò j+1. Ïîñêîëüêó âåêòîðûp1 , p2 , . . .
, pj+1 íåíóëåâûå è A-ñîïðÿæåííûå, òîdim span {p1 , p2 , . . . , pj+1 } = j + 1.Îòñþäà è èç âêëþ÷åíèé (10.24), (10.27) ñëåäóåò èñêîìîå ðàâåíñòâî (10.23).Ëåììà 10.2. Ïîñëå k èòåðàöèé ïî ìåòîäó ñîïðÿæåííûõ ãðàäèåíòîâ íåâÿçêà rjîðòîãîíàëüíà âñåì âåêòîðàì ñïóñêà p1 , . .
. , pj , ò.å.PjT rj = 0,j = 1, k.(10.28)102 10. ÌÅÒÎÄ ÑÎÏÐßÆÅÍÍÛÕ ÃÐÀÄÈÅÍÒÎÂÄîêàçàòåëüñòâî.  ñèëó (10.9) ñóùåñòâóåò âåêòîð yj ∈ Rj òàêîé, ÷òî xj = Pj yj .Ïîýòîìó1J(xj ) = J(Pj yj ) = (APj yj , Pj yj )n − (b, Pj yj )n =21= [Pj yj ]T [APj yj ] − [Pj yj ]T b =21= yjT PjT APj yj − yjT PjT b =21= ([PjT APj ]yj , yj )j − (PjT b, yj )j ,2ò.å. yj åñòü ðåøåíèå çàäà÷è ìèíèìèçàöèè ñ ìàòðèöåé PjT APj è âåêòîðîì PjT b, è,ñëåäîâàòåëüíî, âåêòîð yj ÿâëÿåòñÿ ðåøåíèåì ñëåäóþùåé ñèñòåìû[PjT APj ]yj = PjT b.ÎòñþäàPjT rj = PjT (b − Axj ) = PjT (b − APj yj ) = 0.Ëåììà äîêàçàíà.Òåîðåìà 10.4.
Ïîñëå k øàãîâ ìåòîäà ñîïðÿæåííûõ ãðàäèåíòîâ íåâÿçêè r0 , r1 , . . . , rkâçàèìíî îðòîãîíàëüíû.Äîêàçàòåëüñòâî.  ñèëó òåîðåìû 10.3pj ∈ span {r0 , r1 , . . . , rj−1 }.Ýòî îçíà÷àåò, ÷òî p1 âûðàæàåòñÿ òîëüêî ÷åðåç r0 , p2 òîëüêî ÷åðåç r0 è r1 è ò.ä., ò.å.Pj = [p1 p2 . . . pj ] = [r0 r1 . . . rj−1 ]Uj =: Rj Uj ,(10.29)ãäå Uj âåðõíÿÿ òðåóãîëüíàÿ (j × j)-ìàòðèöà.Ïîñêîëüêó âåêòîðû p1 , p2 , . .
. , pj , à â ñèëó òåîðåìû 10.3 è âåêòîðû r0 , r1 , . . . , rj−1ëèíåéíî íåçàâèñèìû, òî Uj íåâûðîæäåííàÿ ìàòðèöà. Ïîäñòàâëÿÿ ïðåäñòàâëåíèå(10.29) ìàòðèöû Pj â (10.28), áóäåì èìåòü£¤T0 = UjT RjT rj = UjT (r0 , rj ) (r1 , rj ) . . . (rj−1 , rj ) .Ðàññìàòðèâàÿ ýòî ñîîòíîøåíèå êàê ñèñòåìó ëèíåéíûõ îäíîðîäíûõ óðàâíåíèé îòíîñèòåëüíî (ri , rj ) ñ íåâûðîæäåííîé ìàòðèöåé, ïðèõîäèì ê çàêëþ÷åíèþ, ÷òî (ri , rj ) = 0ïðè i 6= j . Òåîðåìà äîêàçàíà.Ìû òåïåðü èìååì âñå íåîáõîäèìîå äëÿ òîãî, ÷òîáû äîêàçàòü òåîðåìó 10.1, ò.å.pk+1 = rk + βk+1 pk .(10.30)103Äîêàçàòåëüñòâî òåîðåìû 10.1.
 ñèëó (10.15)kpk+1 = r⊥= rk − rqk ,ò.å.k+1pk=r −rqk ∈ im AP k ,kXck+1,j Apj .j=1Ïîñêîëüêó â ñèëó òåîðåìû 10.3 pj ∈ Kj (A, b), òîApj ∈ Kj+1 (A, b),(10.31)à, ñíîâà èñïîëüçóÿ òåîðåìó 10.3 íàõîäèì, ÷òî Apj ∈ span {p1 , p2 , . . . , pj+1 } è, ñëåäîâàòåëüíî,k+1Xk+1kp=r −dk+1,j pjj=1èëèk+1(1 + dk+1,k+1 )pk=γ −kXdk+1,j pj .(10.32)j=1Êîýôôèöèåíò (1 + dk+1,k+1 ) ïðè pk+1 íóëþ íå ðàâåí, èáî â ïðîòèâíîì ñëó÷àåkr =kXdk+1,j pj = Pk [dk+1,1 dk+1,2 . . . dk+1,k ]T = Pk dkj=1è ñ ó÷åòîì ëåììû 10.2TTTTkrk k2 = rk rk = rk Pk dk = (rk Pk dk )T = dk (PkT rk ) = 0,ò.å. rk = 0, ÷òî â ñèëó ëåììû 10.1 âîçìîæíî ëèøü ïî çàâåðøåíèè èòåðàöèé.Òàê êàê âåêòîð pk+1 èç (10.32) äîëæåí áûòü A-îðòîãîíàëåí âåêòîðàì pj , j =1, 2 . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
