Е.Е. Тыртышников - Матричный анализ и линейная алгебра (1112313), страница 72
Текст из файла (страница 72)
Òàêèì îáðàçîì,Ïðîèçâîëüíûé âåêòîðíèæå||x − xk ||A = ||A−1 rk ||A ≤ ||A−1 Φk (A)r0 ||A .Ïóñòüλ1 ≥ . . . ≥ λn > 0 ñîáñòâåííûå çíà÷åíèÿ ìàòðèöûAq1 , . . . , q nèáàçèñ èç ñîáñòâåííûõ âåêòîðîâ:λ1AQ = QΛ,Q = [q1 , . . . , qn ],Λ=....λn345 îðòîíîðìèðîâàííûé346Ëåêöèÿ 63rk =nX||A−1 rk ||2A =⇒ζi qii=1r0 =nXnX|Φk (λi )|2 |ξi |21≤λλini=1ξi qi ⇒ ||A−1 Φk (A)r0 ||2A =||rk ||22,λ1≥maxλmin ≤λ≤λmax|Φk (λ)|2 ||r0 ||22 . 2Îöåíêà ñ ïîìîùüþ ìíîãî÷ëåíîâ ×åáûøåâàÒàêèì îáðàçîì, îöåíêè äëÿ íîðìûk -éíåâÿçêè ìîæíî ïîëó÷àòü ñ ïîìîùüþ ìíîãî÷ëåíîâ. Ïðè ýòîìíàñ èíòåðåñóåò âåëè÷èíà, óæå èçâåñòíàÿ íàì êàêîòðåçêåC -íîðìàâ ïðîñòðàíñòâå íåïðåðûâíûõ ôóíêöèé íà[λmin , λmax ]:||Φk ||C =Êàê âûáðàòü ìíîãî÷ëåí[λmin , λmax ]?Φk (λ)|Φk (λ)|.Φk (0) = 1 è íàèìåíüøåé C -íîðìîéìíîãî÷ëåíû ×åáûøåâà.îòðåçêà [−1, 1] îïðåäåëÿþòñÿ ñëåäóþùèì îáðàçîì:ñ óñëîâèåì íîðìèðîâêèíà îòðåçêåTn+1 (t) = 2tTn (t) − Tn−1 (t), n = 1 2, .
. . , .T0 (t) = 1, T1 (t) = t,Tn (t) = cos(n arccos t)Ýëåìåíòàðíî ïðîâåðÿåòñÿ, ÷òîTn (t)minλmin ≤λ≤λmaxÐåøåíèå ýòîé çàäà÷è äàþòÌíîãî÷ëåíû ×åáûøåâà äëÿäëÿλii=1i=163.3nX|ζi |2ïðè|t| > 1,−1 ≤ t ≤ 1.ïðè×òîáû íàéòè ïðåäñòàâëåíèåðàññìîòðèì îäíîðîäíîå ðåêêóððåíòíîå óðàâíåíèåzn+1 − 2tzn + zn−1 = 0è ïîïðîáóåì èñêàòü åãî ðåøåíèå â âèäåzn = z n , z 6= 0.Òîãäàz 2 − 2tz + 1 = 0 ⇒ z(±) = t ±ßñíî, ÷òîc1 , c2 .nnzn = c1 z(+)+c2 z(−)áóäåò ðåøåíèåì äàííîãî ðåêóððåíòíîãî óðàâíåíèÿ ïðè ëþáûõ êîíñòàíòàõÂûáåðåì èõ òàê, ÷òîáûz0 = T0 (t), z1 = T1 (t).Tn (t) = ñëó÷àå ìíîãî÷ëåíîâ îòλ =pt2 − 1. èòîãå ïîëó÷àåìpp11(t + t2 − 1)n + (t − t2 − 1)n .22λ ∈ [λmin , λmax ]ñäåëàåì çàìåíó ïåðåìåííîéλmax + λminλmax − λmin+ t22⇔t=λmax +λmin2λmax −λmin2λ−.ÏîëîæèìTkΦk (λ) =λmax +λmin2λmax −λmin2λ−⇒max +λminTk (− λλmax−λmin )maxλmin ≤λ≤λmax1|Φk (λ)| ≤Tkmax +λmin− λλmax−λmin.Äàëåå,λmax + λmin|t| =λmax − λminÏðè ýòîìt⇒|t| +pt2√√√√λmax + λmin + 2 λmax λminλmax + λmin√−1== √.λmax − λminλmax − λminïîëó÷àåì|Tk (t)| ≥12√√kλ+ λ√ max √ min.λmax − λminÝòîò ðåçóëüòàò âìåñòå ñ ëåììîé îá îöåíêå íîðì íåâÿçîê ìåòîäà ñîïðÿæåííûõ ãðàäèåíòîâ äîêàçûâàåòñëåäóþùóþ òåîðåìó.Òåîðåìà.
 óñëîâèÿõ ëåììû îá îöåíêå íîðì íåâÿçîê ìåòîäà ñîïðÿæåííûõ ãðàäèåíòîâ ñïðàâåäëèâûíåðàâåíñòâàr||rk ||2≤ 2λmaxλmin√√kλ− λ√ max √ min||r0 ||2 ,λmax + λmink = 1, 2, . . . .Å. Å. Òûðòûøíèêîâ63.4347Ïðåäîáóñëîâëåííûé ìåòîä ñîïðÿæåííûõ ãðàäèåíòîâÏîëó÷åííàÿ òåîðåìà ïîêàçûâàåò, ÷òî íîðìû íåâÿçîê â ìåòîäå ñîïðÿæåííûõ ãðàäèåíòîâ óáûâàþò òåìñèëüíåå, ÷åì ìåíüøå îòíîøåíèåλmax /λmin .Åñëè ýòî îòíîøåíèå âåëèêî, òî ìîæíî ïîïûòàòüñÿ íàéòèáëèçêóþ ýðìèòîâó ïîëîæèòåëüíî îïðåäåëåííóþ ìàòðèöóBíóþ ñèñòåìó B −1 Ax = B −1 b.è ðåøàòü ðàâíîñèëüíóþïðåäîáóñëîâëåí-Ïðîáëåìà, îäíàêî, â òîì, ÷òî ìû ïîëó÷èëè ìåòîä ñîïðÿæåííûõ ãðàäèåíòîâ äëÿ ðåøåíèÿ ñèñòåìñ ýðìèòîâîé ïîëîæèòåëüíî îïðåäåëåííîé ìàòðèöåé, à ïðîèçâåäåíèåB −1 Aâ îáùåì ñëó÷àå íå áóäåòýðìèòîâîé ìàòðèöåé.
Òåì íå ìåíåå, ñïðàâåäëèâî ñëåäóþùååÓòâåðæäåíèå. Ïóñòü A è B ýðìèòîâû ïîëîæèòåëüíî îïðåäåëåííûå ìàòðèöû. Òîãäà îïåðàòîðóìíîæåíèÿ íà ìàòðèöó B −1 A ÿâëÿåòñÿ ñàìîñîïðÿæåííûì ïîëîæèòåëüíî îïðåäåëåííûì îïåðàòîðîì îòíîñèòåëüíî ñêàëÿðíîãî ïðîèçâåäåíèÿ (x, y)B = (Bx, y).Äîêàçàòåëüñòâî. (B −1 Ax, y)B = (Ax, y) = (x, Ay) = (x, B(B −1 A)y) = (Bx, B −1 Ay) = (x, B −1 Ay)B .Ïîëîæèòåëüíàÿ îïðåäåëåííîñòü î÷åâèäíà:(B −1 Ax, x)B = (Ax, x) > 0ïðèx 6= 0. 2Òåïåðü ìû ìîæåì ïîâòîðèòü âñå ðàññóæäåíèÿ è âûêëàäêè, ïðèâåäøèå ê äâó÷ëåííûì ôîðìóëàììåòîäà ñîïðÿæåííûõ ãðàäèåíòîâ, ñ çàìåíîé åñòåñòâåííîãî ñêàëÿðíîãî ïðîèçâåäåíèÿ íàx̂k = x̂k−1 + αk p̂k ,αk =(· , ·)B :(r̂k−1 , r̂k−1 )B(Br̂k−1 , r̂k−1 )=,(B −1 Ap̂k , p̂k )B(Ap̂k , p̂k )r̂k = r̂k−1 − αk B −1 Ap̂k ,βk = −p̂k+1 = r̂k + βk p̂k ,(Br̂k , r̂k )(r̂k , r̂k )B=−.(r̂k−1 , r̂k−1 )B(Br̂k−1 , r̂k−1 )r̂k = B −1 (b − Ax̂k ) ýòî íåâÿçêà ïðåäîáóñëîâëåííîé ñèñòåìû.
Ñîîòâåòñòâóþùàÿ íåâÿçêàèñõîäíîé ñèñòåìû èìååò âèä rk = Br̂k . Ïðåäîáóñëîâëåííûé ìåòîä ñîïðÿæåííûõ ãðàäèåíòîâ, âû÷èñëÿþùèé íàñòîÿùèå íåâÿçêè rk è òå æå âåêòîðû xk = x̂k è pk = p̂k , ïðèíèìàåò òàêóþ ôîðìó:Çàìåòèì, ÷òîr0 = b − Ax0 ,p1 = B −1 r0 ;xk = xk−1 + αk pk ,αk =(B −1 rk−1 , rk−1 ),(Apk , pk )rk = rk−1 − αk Apk ,pk+1 = B −1 rk + βk pk ,63.5βk = −(B −1 rk , rk ).(B −1 rk−1 , rk−1 )Îáîáùåíèÿ ìåòîäà ñîïðÿæåííûõ ãðàäèåíòîâ ñëó÷àå áîëüøèõ íåýðìèòîâûõ ìàòðèö îñíîâíûì ÿâëÿåòñÿ ìåòîä ìèíèìèçàöèè íîðìû íåâÿçêè íàïîäïðîñòðàíñòâàõ Êðûëîâà.
 îòëè÷èå îò ìåòîäà ñîïðÿæåííûõ ãðàäèåíòîâ, â äàííîì ñëó÷àå â ïîäïðîñòðàíñòâàõ Êðûëîâà òðåáóåòñÿ ñòðîèòü è õðàíèòü ïîëíûå áàçèñû. Ñóùåñòâóþò ëè ìåòîäû ñ êîðîòêèìè ðåêóððåíòíûìè ñîîòíîøåíèÿìè â íåýðìèòîâîì ñëó÷àå?Ax = b ñèñòåìà ñ íåâûðîæäåííîé è â îáùåì ñëó÷àåx0 , íàõîäèì íà÷àëüíóþ íåâÿçêó r0 , â ñëó÷àå r0 6= 0äîïîëíÿåì áàçèñ p1 , . . . , pk â ïðîñòðàíñòâàõ ÊðûëîâàÏðåæäå âñåãî, óòî÷íèì âîïðîñ. Ïóñòüíåýðìèòîâîé ìàòðèöåé. Âûáðàâ íà÷àëüíûé âåêòîðïîëàãàåìp1 = r 0è ïîñëåäîâàòåëüíîLk = L(r0 , Ar0 , . . .
, Ak−1 r0 ) = L(p1 , . . . , pk ),ïðè÷åì òàêèì îáðàçîì, ÷òîáû âåêòîðû óäîâëåòâîðÿëè óñëîâèÿì(Api , pj ) = 0,Êàê òîëüêî ïîëó÷åíî ïðîñòðàíñòâîìèíèìèçàöèè íåâÿçêèrk = b − Axki 6= j,Lk ,1 ≤ i, j ≤ k;èùåìxkâ âèäåôîðìàëüíîé A-îðòîãîíàëüíîñòè(Api , pi ) 6= 0, 1 ≤ i ≤ k.xk = x0 + y, y ∈ Lk . Ïðè ýòîì îòêàæåìñÿ îòy ïðîåêöèîííûì óñëîâèåìâ êàêîé-ëèáî íîðìå è áóäåì îïðåäåëÿòürk ⊥ Lk .Èç ñêàçàííîãî âûòåêàåò, ÷òîxk = xk−1 + αk pk ,rk = rk−1 − αk Apk ,348ãäåαkËåêöèÿ 63îïðåäåëÿåòñÿ ïðîåêöèîííûì óñëîâèåì.Åñëèrk = 0,òî ðåøåíèå óæå íàéäåíî.
Åñëèrk 6= 0,òî èùåìâ âèäåγjk = −(rk , A∗ pj )/(Apj , pj ).⇒pk+1 = rk + γ11 p1 + . . . + γk1 pkpk+1A-îðòîãîíàëüíûé áàçèñ p1 , . . . , pk(Apk+1 , pj ) = 0, 1 ≤ j ≤ k .Òàêèì îáðàçîì, åñëè ó íàñ åñòü ôîðìàëüíîâåêòîðpk+1òàêîé, ÷òîâLk , òî ìû ìîæåì íàéòèíèîòêóäà íå ñëåäóåò,(Apk+1 , pk+1 ) 6= 0. Ýòî ñâîéñòâî îòíåñåì ê îñíîâíûì ïðåäïîëîæåíèÿì; â ÷àñòíîñòè, ìû ïðåäïîëàãàåì, ÷òî (Ar0 , r0 ) 6= 0. Åñëè íåâÿçêè r0 , r1 , . . . , rk−1 íåíóëåâûå è ôîðìàëüíî A-îðòîãîíàëüíûé áàçèñp1 , . .
. , pk â Lk ïîñòðîåí, òî áóäåì ãîâîðèòü, ÷òî ïðîöåññ íå îáðûâàåòñÿ íà k -ì øàãå. Åñëè ïðè ýòîìrk = 0, òî áóäåì ãîâîðèòü, ÷òî ïðîöåññ óñïåøíî çàâåðøàåòñÿ íà k -ì øàãå. îòëè÷èå îò ñëó÷àÿ ïîëîæèòåëüíî îïðåäåëåííîé ìàòðèöû òåïåðü, îäíàêî,÷òîËåììà 1. Åñëè ïðîöåññ íå îáðûâàåòñÿ íà k-ì øàãå, òî íåâÿçêè r0 , . . . , rk−1 îáðàçóþò îðòîãîíàëüíûéáàçèñ â Lk .Äîêàçàòåëüñòâî.Äåéñòâèòåëüíî,rj ⊥ r0 , .
. . , rj−1 . 2rj ∈ Lj+1 ⊂ Lkïðè0 ≤ j ≤ k−1è, â ñèëó ïðîåêöèîííîãî óñëîâèÿ,Âîïðîñ î êîðîòêèõ ðåêóððåíòíûõ ñîîòíîøåíèÿõ ïîñòàâèì ñëåäóþùèì îáðàçîì.ðîâàíî1 Ïóñòü ôèêñè-1 ≤ s ≤ n − 1, è ïðåäïîëîæèì, ÷òî âñÿêèé ðàç, êîãäà ïðîöåññ íå îáðûâàåòñÿ íà k -ì øàãå, èìåþòìåñòî ðàâåíñòâàγjk = (rk , A∗ pj ) = 0Ýòî îçíà÷àåò, ÷òîpk+1âûðàæàåòñÿ ÷åðåçsïðè1 ≤ j ≤ k − s.(1)ïîñëåäíèõ âåêòîðîâ áàçèñà:kXpk+1 = rk +γjk pj .j=k−s+1Êàêèìè ñâîéñòâàìè ïðè ýòîì äîëæíà îáëàäàòü ìàòðèöàÐàññìîòðèì òàêèå ìàòðèöû, äëÿ êîòîðûõA∗A∗ =A?åñòü ìíîãî÷ëåí îòs−1XAâèäàaj Aj .(2)j=0Ëåììà 2.
Ïóñòü èìååò ìåñòî (2). Òîãäà äëÿ ëþáîé íà÷àëüíîé íåâÿçêè r0 6= 0, íå äàþùåé îáðûâàïðîöåññà íà k -ì øàãå, âûïîëíÿþòñÿ ðàâåíñòâà (1).Äîêàçàòåëüñòâî.(2), A∗ pj åñòü ëèíåéíàÿ êîìáèíàöèÿ âåêòîðîâ p1 , . . . , pj+s .rk ⊥ p1 , . . . , pj+s ïðè j + s ≤ k ⇒ (1). 2 ñèëóåêöèîííîìó óñëîâèþ,Ñîãëàñíî ïðî-Ëåììà 3. Ïðåäïîëîæèì, ÷òî íà÷àëüíàÿ íåâÿçêà r0 6= 0 òàêîâà, ÷òî ïðîöåññ íå îáðûâàåòñÿ íà nì øàãå è ïðè ýòîì âûïîëíÿþòñÿ ðàâåíñòâà (1) äëÿ âñåõ 1 ≤ k ≤ n. Òîãäà äëÿ íåêîòîðûõ ÷èñåëαj = αj (r0 ) èìååò ìåñòî ñîîòíîøåíèåA∗ r0 =s−1Xαj Aj r0 .j=01 Äàííûé âîïðîñ óñèëåííî äèñêóòèðîâàëñÿ â êîíöå 1970-õ ãîäîâ. Ïðîñòîå è ÿñíîå ðåøåíèå, êîòîðîåìû çäåñü èçëàãàåì, îñíîâàíî íà èäåÿõ ñòàòüè: Â. Â.
Âîåâîäèí, Å. Å. Òûðòûøíèêîâ, Îá îáîáùåíèè ìåòîäîâ ñîïðÿæåííûõ íàïðàâëåíèé,×èñëåííûå ìåòîäû àëãåáðû, Èçäàòåëüñòâî Ìîñêîâñêîãî óíèâåðñèòåòà,1981, ñ. 39.  2004 ã. Éîðã Ëèåçåí è Ïoëü Ñýéëîð çàìåòèëè, ÷òî èñïîëüçîâàííîå â ýòîé ñòàòüå äîïîëíèòåëüíîå îãðàíè÷åíèå íà ïîðÿäîê ìàòðèöû ëåãêî ñíèìàåòñÿ. Çàìåòèì, ÷òî äðóãîå, ïðè÷åì âåñüìàñëîæíîå, äîêàçàòåëüñòâî íåîáõîäèìîñòè óñëîâèÿ(2)áûëî îïóáëèêîâàíî â 1984 ã.
Ôàáåðîì è Ìàíòåôå-ëåì (V. Faber, T. Manteuffel, Necessary and sufficient conditions for the existence of a conjugate gradientmethod,SIAM J. Numer. Anal.,vol. 21, no. 2, 1984, pp. 352362).Å. Å. Òûðòûøíèêîâ349Äîêàçàòåëüñòâî. Òî, ÷òî ïðîöåññ íå îáðûâàåòñÿ íà n-ì øàãå, îçíà÷àåò îðòîãîíàëüíîñòü íåâÿçîêr0 , .
. . , rn−1 è ëèíåéíóþ íåçàâèñèìîñòü âåêòîðîâ r0 , Ar0 , . . . , An−1 r0 . Ðàâåíñòâà (Ark , pj ) = 0 ïðè 1 ≤j ≤ k − s îçíà÷àþò, ÷òî (Ark , rj ) = 0 ïðè 0 ≤ j ≤ k − s − 1. Ñëåäîâàòåëüíî, A∗ r0 ⊥ rk ïðè k ≥ s − 1 ⇒A∗ r0 åñòü ëèíåéíàÿ êîìáèíàöèÿ âåêòîðîâ r0 , . . . , rs−2 ⇒ A∗ r0 åñòü ëèíåéíàÿ êîìáèíàöèÿ âåêòîðîâr0 , Ar0 , . . . , As−1 r0 . 2Òåîðåìà.
Ïóñòü 1 ≤ s < n è ìàòðèöà A òàêîâà, ÷òî õîòÿ áû äëÿ îäíîé íà÷àëüíîé íåâÿçêè r0 6= 0ïðîöåññ íå îáðûâàåòñÿ íà n-ì øàãå. Òîãäà äëÿ âñåõ íà÷àëüíûõ íåâÿçîê ñ òåì æå ñâîéñòâîì äëÿâûïîëíåíèÿ óñëîâèÿ (1) íåîáõîäèìî è äîñòàòî÷íî, ÷òîáû ìàòðèöà A óäîâëåòâîðÿëà ñîîòíîøåíèþ(2).Äîêàçàòåëüñòâî.Äîñòàòî÷íîñòü ïîëó÷åíà â ëåììå 2, ïîýòîìó ïåðåéäåì ñðàçó ê äîêàçàòåëüñòâó íåîá-õîäèìîñòè. Ëèíåéíàÿ íåçàâèñèìîñòü âåêòîðîâA ðàâíà n ⇒x = r0 è y = Ar0 .ìíîãî÷ëåíà ìàòðèöûíîâà êëåòêà. Ïóñòüíå îáðûâàåòñÿ íàn-ìn-ãî øàãà ëèøü äëÿ êàêîãî-òîA). Ñîãëàñíî ëåììå 3, èìååìA∗ x =ßñíî, ÷òî â ñëó÷àå íà÷àëüíîé íåâÿçêè, ðàâíîés−1Xαj Aj x,êîíå÷íîãî ÷èñëà çíà÷åíèéA∗ y =j=0Îòñþäà, ñ ó÷åòîì ðàâåíñòâàα0 x +s−1Xîçíà÷àåò, ÷òî ñòåïåíü ìèíèìàëüíîãîäëÿ êàæäîãî ñîáñòâåííîãî çíà÷åíèÿ èìååòñÿ ðîâíî îäíà æîðäà-øàãå. Áîëåå òîãî, äëÿ íà÷àëüíîé íåâÿçêè âèäàðàíååäëÿr0 , Ar0 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
