Численные методы. Ионкин (2009) (формат хуже), страница 6

. Um−2TT−1−1U T = Um−2Um−3. . . U2T U1T = Um−2Um−3. . . U2−1 U1−1 = U −1Ñëåäîâàòåëüíî, ìàòðèöà U - îðòîãîíàëüíà.C = U −1 AU ⇒ C ∼ AÏðè÷åì ïîäîáèå âûïîëíÿåòñÿ ñ ïîìîùüþ îðòîãîíàëüíîé ìàòðèöûUÝëåìåíòû ìàòðèöû C èìåþò âèä:cij = 0, i ≥ j + 2, j = 1, 2, . . . , m − 2Çàìå÷àíèå. Ñîáñòâåííûå çíà÷åíèÿ ìàòðèöû A ñîâïàäàþò ñ ñîáñòâåííûìè çíà÷åíèÿìè ìàòðèöû C, ò.å.:CλAk = λk , k = 1, mÏîíÿòèå î QR-àëãîðèòìå.

Ðåøåíèå ïîëíîé ïðîáëåìû ñîáñòâåííûõçíà÷åíèé.51Äîêàçàòåëüñòâî.Ax = λx, x 6= 0U −1 Ax = λU −1 x, îáîçíà÷èìU −1 x = y 6= 0 ⇒ x = U yU−1 AU y = λy, y 6= 0Cy = λyÇàìå÷àíèå. Åñëè A = AT , òî C = C TÄîêàçàòåëüñòâî.C T = (U −1 AU )T = U T AT (U −1 )T = U −1 AU = CŸ11Ïîíÿòèå î QR-àëãîðèòìå. Ðåøåíèå ïîëíîé ïðîáëåìû ñîáñòâåííûõ çíà÷åíèé.Èçó÷åííûå â ïðåäûäóùåì ïàðàãðàôå ñâîéñòâà ïîçâîëÿò íàì ïðåäñòàâèòü ìàòðèöóAâ âèäå:A = QRãäåQ−1 = QT- îðòîãîíàëüíàÿ ìàòðèöà, à(1)Rèìååò âåðõíåòðåóãîëüíóþôîðìó.x = (a11 , a21 , . . .

, am1 ). Äëÿ íåãî ñóùåñòâóåò òàêàÿVVT, êîòîðàÿ ïîäàâëÿåò âñå êîîðîðòîãîíàëüíàÿ ìàòðèöà H1 = E − 2||V ||2äèíàòû âåêòîðà x, êðîìå ïåðâîé.Ìàòðèöà H1 A èìååò âèä:× × ... × 0 × . . . ×H1 A =  0 × . . . × .. .. . .... ...0 × ... ×1 0Ïîñòðîèì ìàòðèöó H2 = 0 Hïîðÿäêà m × m,òàêóþ, ÷òîÂîçüìåì âåêòîðÏîíÿòèå î QR-àëãîðèòìå.

Ðåøåíèå ïîëíîé ïðîáëåìû ñîáñòâåííûõçíà÷åíèé.52×0H2 H1 A =  0 ...0× × ... ×× × . . . ×0 × . . . ×....... ×..0 × ... ×Î÷åâèäíî, ÷òî çà (m-1) øàã ìû îáíóëèì âñå ýëåìåíòû ïîä ãëàâíîéäèàãîíàëüþ:×0...0Hm−1 Hm−2 . . . H2 H1 A = R =××...0............×!×××−ÂÒÔÏîñòðîèì ìàòðèöó Q ñëåäóþùèì îáðàçîì:Q = H1 H2 . . . Hm−1ÍàéäåìQT :TT−1−1Hm−2.

. . H2T H1T = Hm−1Hm−2. . . H1−1 = Q−1QT = Hm−1Ñëåäîâàòåëüíî, ìàòðèöà Q îðòîãîíàëüíà.Òàêèì îáðàçîì, ìû ïîëó÷èëè ðàçëîæåíèå ìàòðèöû A.Çàìå÷àíèå. Ïðè ôàêòîðèçàöèè â âèäå QR:1. Äëÿ ïðîèçâîëüíîé ìàòðèöû2. Äëÿ ìàòðèöûAAòðåáóåòñÿâèäà ÂÏÒÔ òðåáóåòñÿ3. Äëÿ òðåõäèàãîíàëüíîé ìàòðèöûAO(m3 )O(m2 )òðåáóåòñÿäåéñòâèé.äåéñòâèé.O(m)äåéñòâèé.QR-àëãîðèòìÂîçüìåì ìàòðèöóA0 .

Ïðåäñòàâèì åå â âèäå A0 = Q0 R0 , ãäå QT0 = Q−10 ,R - ìàòðèöà ÂÒÔ.ÏîëîæèìA1 = R0 Q0R0 = Q−10 A0(2)Ïîíÿòèå î QR-àëãîðèòìå. Ðåøåíèå ïîëíîé ïðîáëåìû ñîáñòâåííûõçíà÷åíèé.53A1 = Q−10 A0 Q0Òàêèì îáðàçîì, ìàòðèöûA1A0èïîäîáíû ñ îðòîãîíàëüíîé ìàòðèöåé.Àíàëîãè÷íî, ñäåëàåì ñëåäóþùèå øàãè:A1 = Q1 R1 , QT1 = Q−11 , R1 − ÂÒÔ...Óñòðåìèìk → ∞,Ak = Qk Rk , k = 0, 1, . . .(3)Ak+1 = Rk Qk(4)òîãäà:× × ...0 × ...Ak →  ..

.. . .. ..0 0 ...××××Ãäå íà ãëàâíîé äèàãîíàëè áóäóò ñòîÿòü ñîáñòâåííûå çíà÷åíèÿ ìàòðèöA0 , A1 , . . .(ñïåêòðû ýòèõ ìàòðèö ñîâïàäàþò).Çàìåòèì, ÷òî ïîä ãëàâíîé äèàãîíàëüþ ìîãóò è íå ïîëó÷àòüñÿ íóëè â ìàòåìàòè÷åñêîì ñìûñëå. Äîñòàòî÷íî, ÷òîáû çíà÷åíèÿ ïîä ãëàâíîé äèàãîíàëüþ áûëè ïî ìîäóëþ ìåíüøå íåêîòîðîãî ÷èñëà (ò.í.

ìàøèííûé íîëü),îïðåäåëÿþùåãî òî÷íîñòü âû÷èñëåíèé.Åñëè óAkêîìïëåêñíûå ñîáñòâåííûå çíà÷åíèÿ, òî â ìàòðèöå íà ãëàâíîéäèàãîíàëè áóäóò ïîÿâëÿòüñÿ êâàäðàòû2 × 2,×îíà áóäåò èìåòü âèä:X×Ak → λ0 λ1−λ1 λ00...Ïåðå÷èñëèì îñíîâíûå ïëþñû è ìèíóñû QR-àëãîðèòìà:1. (+) Äëÿ ëþáîé ìàòðèöû ìîæíî íàéòè âåñü ñïåêòð.2. (-) Âî âðåìÿ âû÷èñëåíèé íóæíî äåðæàòü âñþ ìàòðèöó â ïàìÿòè.3. (-) Åñëè ñîáñòâåííûå çíà÷åíèÿ êîìïëåêñíû, òî ïîÿâëÿþòñÿ êëåòêè2ãî ïîðÿäêà, êîòîðûå ïðè ïîñëåäóþùèõ èòåðàöèÿõ íå áóäóò ñõîäèòüñÿ ê 0.Ïîíÿòèå î QR-àëãîðèòìå.

Ðåøåíèå ïîëíîé ïðîáëåìû ñîáñòâåííûõçíà÷åíèé.54Ñâîéñòâà QR-àëãîðèòìàÓòâåðæäåíèå. Ïóñòü ìàòðèöà B ÂÒÔ, à ìàòðèöà A ÂÏÒÔ. ÒîãäàQ = BA ÂÏÒÔ.Äîêàçàòåëüñòâî. Ïî ôîðìóëå óìíîæåíèÿ ìàòðèö:cij =nXbiα cαj .α=1Òàê êàêòî âñåBaαj ÂÒÔ, òî âñåïðèα>j+1biαïðèi>αðàâíû íóëþ, òàê êàêA ÂÏÒÔ,ðàâíû íóëþ. Ìîäèôèöèðóåì ôîðìóëó ñîãëàñíîýòèì óòâåðæäåíèÿì:cij =j+1Xbiα cαj .α=iÒî åñòü åñëè i > j + 1, òîcij = 0.À ýòî è çíà÷èò, ÷òîC âåðõíÿÿ ïî÷òèòðåóãîëüíàÿ ìàòðèöà.Óòâåðæäåíèå. Ïóñòü ìàòðèöà B ÂÏÒÔ, à ìàòðèöà A ÂÒÔ. ÒîãäàQ = BA ÂÏÒÔ.Äîêàçàòåëüñòâî. Äîêàçàòåëüñòâî ïîëíîñòüþ àíàëîãè÷íî ïðåäûäóùåìóóòâåðæäåíèþ.Èñïîëüçóÿ äàííûå óòâåðæäåíèÿ, ìîæíî çíà÷èòåëüíî óñêîðèòü QRðàçëîæåíèå ìàòðèöû.QR-àëãîðèòì ïðåîáðàçóåò ìàòðèöóA→− A0 ÂÏÒÔ:A0 = Q0 R0Q0 = A0 R)−1A1 = R0 Q0 ÂÏÒÔ ïî äîêàçàííîìó óòâåðæäåíèþ ÂÏÒÔ ïî äîêàçàííîìó óòâåðæäåíèþÒî åñòü ôîðìà ìàòðèöûAn (n ∈ N)íå óõóäøàåòñÿ, ñëåäîâàòåëüíî, î÷å2ðåäíàÿ ìàòðèöà ìîæåò áûòü âûïîëíåíà íå áîëåå ÷åì çà n äåéñòâèé.Åñëè æå ìàòðèöàäåéñòâèé.A0- ñèììåòðè÷íàÿ, òî îäèí øàã ïîòðåáóåò âñåãînÃëàâà IIÈíòåðïîëèðîâàíèå èïðèáëèæåíèå ôóíêöèéŸ1Ïîñòàíîâêà çàäà÷è èíòåðïîëèðîâàíèÿf (x) äèñêðåòíàÿ ôóíêöèÿ àðãóìåíòà x, x ∈ [a, b], a, b ∈ R.Ôóíêöèÿ f (x) îïðåäåëåíà â òî÷êàõ x0 , x1 , .

. . , xn , n ∈ N; a ≤ x0 < x1 <. . . < xn ≤ b = {Xi }n0 óçëàõ ôóíêöèè. Âî âñåõ óçëàõ çàäàíû çíà÷åíèÿf (xi ) = yi , ∀i = 0, n. Òðåáóåòñÿ íàéòè çíà÷åíèå ôóíêöèè f (x) â ïðîèçÏóñòüâîëüíîé òî÷êå.Çàìå÷àíèå.  óêàçàííîé ôîðìóëèðîâêå ðåøåíèé çàäà÷è áåñêîíå÷íî ìíîãî. Äëÿ óòî÷íåíèÿ äîïîëíèòåëüíî óêàçûâàþò êëàññ ôóíêöèé, êîòîðûåáóäóò èñïîëüçîâàòüñÿ äëÿ ïîñòðîåíèÿ çíà÷åíèéf (x)â ïðîèçâîëüíîéòî÷êå.Èíòåðïîëèðîâàíèå àëãåáðàè÷åñêèìè ïîëèíîìàìèÎïðåäåëåíèå. Íàçîâåì èíòåðïîëÿöèîííûì ïîëèíîìîì Ëàãðàíæà ôóíêöèèf (x)ïî óçëàì{Xi }n0ïîëèíîì ñòåïåíèn:Pn (x) = a0 + a1 x + . . . + an xn ,a0 . . .

an âûáèðàþòñÿ òàêèìi = 1, n áûëî âûïîëíåíî:ïðè ýòîì çíà÷åíèÿ êîýôôèöèåíòîâçîì, ÷òîáû ïðè ëþáûõ çíà÷åíèÿõPn (xi ) = f (xi )55(1)îáðà-(2)Èíòåðïîëÿöèîííàÿ ôîðìóëà Ëàãðàíæà56Óòâåðæäåíèå. Ïîêàæåì, ÷òî èíòåðïîëÿöèîííûé ïîëèíîì Pn (x) äëÿôóíêöèèf (x)ïî óçëàì{Xi }n0Äîêàçàòåëüñòâî. Ðàñïèøåìñóùåñòâóåò è åäèíñòâåíåí.n+1óðàâíåíèå èç óñëîâèÿ (2). Ïîëó÷èìñèñòåìó ëèíåéíûõ óðàâíåíèé:a0 +a1 x0 +. . .+an xn0 = f0 , a0 +a1 x1 +. . .+an xn1 = f1 , . . . a0 +a1 xn +. . .+an xnn = fn ,Òåïåðü ïîñìîòðèì íà îïðåäåëèòåëü ýòîé ñèñòåìû:11∆=. .

.1x0x1...xnx20x21...x2n............xn0xn1 . . .xnnÈç êóðñà ëèíåéíîé àëãåáðû èçâåñòíî, ÷òî äàííûé îïðåäåëèòåëü (îïðåäåëèòåëü Âàíäåðìîíäà) ðàâåí ïðîèçâåäåíèþ ðàçíîñòè âñåõ ïàðj.(xi , xj ), i 6=Ïî óñëîâèþ íèêàêèå äâà ðàçëè÷íûõ óçëà íå ìîãóò äàòü íàì íóëåâóþðàçíîñòü, ñëåäîâàòåëüíî, îïðåäåëèòåëü ñèñòåìû íå ðàâåí íóëþ.

À ýòî èîçíà÷àåò, ÷òî ðåøåíèå (ò.å.Pn (x)) ñóùåñòâóåò è åäèíñòâåííî.Çàìå÷àíèå. Ïîñêîëüêó ìû äîêàçàëè ñóùåñòâîâàíèå è åäèíñòâåííîñòüèíòåðïîëèðóþùåãî ïîëèíîìà, òî ïðè åãî ïîèñêå, â êàêîé áû ôîðìå ìûåãî íå ïîëó÷èëè, îí áóäåò òîæåñòâåííî ðàâåí âñåì ñâîèì ïðåäñòàâëåíèÿì â èíûõ ôîðìàõ, ïîëó÷åííûõ ñ ïîìîùüþ äðóãèõ ìåòîäîâ.Ÿ2Èíòåðïîëÿöèîííàÿ ôîðìóëà ËàãðàíæàÁóäåì èñêàòü èíòåðïîëÿöèîííûé ïîëèíîì â âèäåLn (x) =nXck (x)f (xk ), ãäå:(1)k=0ck (x) ïîëèíîìn-éñòåïåíè,f (xk ) èçâåñòíûå çíà÷åíèÿ ôóíêöèè â óç-ëàõ.Çàìå÷àíèå. Ïî îïðåäåëåíèþ Ln (xi ) = f (xi ), ∀i = 1, n.Èíòåðïîëÿöèîííàÿ ôîðìóëà ËàãðàíæàÁóäåì ñòðîèòü ïîëèíîì ñëåäóþùèì îáðàçîì:nÏóñòü ω(x) = (x − x0 )(x − x1 ) · .

. . · (x − xn ) = Πi=0 (xÒîãäà:57− xi ).ω 0 (k) = ([. . .](x − xk )) = [. . .] + [. . .]0 (x − xk ) = Πni=0 (x − xi )i6=k. (ω(k) çíà÷åíèå ôóíêöèè â òî÷êåxk).ω(x)Ïîëèíîìû ck (x) âîëüçìåì ðàâíûìè.(x−xk )ω 0 (x)Îïðåäåëèì ïîãðåøíîñòü ìåòîäà êàê ðàçíîñòü ìåæäó çíà÷åíèåì ïî-ëèíîìà Ëàãðàíæà è çíà÷åíèåì ôóíêöèè:ψn (x) = f (x) − Ln (x)(2)Çàìå÷àíèå. Äëÿ îöåíêè ïîãðåøíîñòè ìåòîäû ìû òðåáóåì f (x) ∈ C n+1 [a, b].Óòâåðæäåíèå.∀x∗ ∈ [a, b] : rn (x∗ ) =f (n+1) (ξ)· ωn+1 (x∗ ), ξ ∈ (a, b)(n + 1)!g(s) = f (s) + Ln (s) − kω(s), ãäå k - êîíñòàíòà.Î÷åâèäíî, ÷òî g(s) èìååò n + 2 íóëÿ: n + 1 çà ñ÷åò îáðàùåíèÿ â íîëü âóçëàõ è ïîñëåäíèé íîëü çà ñ÷åò ñîâïàäåíèÿ f (s) + Ln (s) = kω .  ýòîì(n+1)ñëó÷àå k è åñòü èñêîìàÿ îöåíêà.

Ïî òåîðåìå Ðîëëÿ g(ξ) = 0. ÍàéäåìÄîêàçàòåëüñòâî. Ïóñòüýòó ïðîèçâîäíóþ:g (n+1) (s) = (f (s) + Ln (s) − kω(s))(n+1) =f (n+1) (ξ) + 0 − k · n!Îòêóäà è ïîëó÷àåì:f (n+1) (ξ)ω(x)f (x) + Ln (x) =(n + 1)!Çàìå÷àíèå. Ïîëèíîì Ëàãðàíæà, âîîáùå ãîâîðÿ, íå ñõîäèòñÿ ê f (x).Èíòåðïîëÿöèîííàÿ ôîðìóëà ÍüþòîíàŸ358Èíòåðïîëÿöèîííàÿ ôîðìóëà ÍüþòîíàÎïðåäåëåíèå. Íàçîâåì ðàçäåëåííîé ðàçíîñòüþ ïåðâîãî ïîðÿäêà, ïîñòðîåííîé ïî óçëàìxièxj ,ñëåäóþùåå ñîîòíîøåíèå:f (xi , xj ) =f (xj ) − f (xi )xj − xiÐàçäåëåííîé ðàçíîñòüþ âòîðîãî ïîðÿäêà ïî óçëàì(1)xi−1 , xi , xi+1íàçûâà-åòñÿ ñîîòíîøåíèå:f (xi−1 , xi , xi+1 ) =f (xi−1 xi ) − f (xi xi+1 )xi−1 − xi+1Àíàëîãè÷íî îïðåäåëÿåì ðàñïðåäåëåííóþ ðàçíîñòü áîëüøèõ ïîðÿäêîâ.Óòâåðæäåíèå. Ðàñïðåäåëåííóþ ðàçíîñòü k ãî ïîðÿäêà ìîæíî ïðåäñòàâèòü â âèäå:f (x0 , x1 , .

. . , xk ) =Ïðè÷åì çàïèñüωa,b (x)kXf (xi )0ω0,k(xi )i=0îçíà÷àåò:ωa,b (x) = (x − xa )(x − xa+1 ) · . . . · (x − xb ), a < bÄîêàçàòåëüñòâî. Íå îãðàíè÷èâàÿ îáùíîñòè, áóäåì ðàññìàòðèâàòü óçëûñ èíäåêñàìè0..k, k ∈ N.Áàçà:Äîêàæåì óòâåðæäåíèå ïî èíäóêöèè.f (x0 )f (x1 )+=x0 − x1 x1 − x0f (x0 )f (x1 )+ 00ω0,1 (x0 ) ω0,1 (x1 )k = 1 : f (x0 , x1 ) =Ïåðåõîä:Ïîêàæåì ÷òîk=l:lXf (xi )f (x0 , .

. . , xl ) =0ω0,l(xi )i=0Pf (x0 , . . . , xl+1 ) = li=0 ωf0 (x(xi )i ) :0,lf (x0 , . . . , xl+1 ) =f (x1 , . . . , xl+1 ) − f (x0 , . . . , xl )=xl+1 − x0Èíòåðïîëÿöèîííàÿ ôîðìóëà Íüþòîíà59l+1lXX1f (xi )f (xi )(−)=00xl+1 − x0 i=1 ω1,l+1 (xi ) i=0 ω0,l(xi )lXf (x0 )111f (xl+1 )− 0+− 0)( 00xl+1 − x0 ω1,l+1 (xl+1 ) ω0,l (x0 ) i=1 ω1,l+1 (xi ) ω0,l (xi )Ðàññìîòðèì ñëàãàåìûå îòäåëüíî:00(xl+1 − x0 )ω1,l+1(xl+1 ) = ω0,l+1(xl+1 )00(xl+1 − x0 )ω0,l(x0 ) = ω0,l+1(x0 )10ω1,l+1(xi )−10ω0,l(xi )=(xi − x0 ) (xi − xl+1 )− 0= (xl+1 − x0 )0ω0,l+1(xi )ω0,l+1 (xi )Ïîäñòàâèâ ïðåîáðàçîâàííûå ñëàãàåìûå, ïîëó÷èì:lX f (xi )f (xl+1 )f (x0 )++)000ω0,l+1(x0 ) ω0,l+1(xl+1 ) i=1 ω0,l+1(xi )×òî è òðåáîâàëîñü äîêàçàòü.Îïðåäåëåíèå.