Н.И. Ионкин - Электронные лекции (2008) (1135232), страница 5
Текст из файла (страница 5)
. . .×Ïðåîáðàçîâàíèå Õàóñõîëäåðà âåêòîðàH =E−2VV TkVk2V(1.54)1.10. Ïðèâåäåíèå ìàòðèöû ê âåðõíåé ïî÷òè òðåóãîëüíîé ôîðìåÇàìå÷àíèå:v1 v2V= . ..vmVV T35 , V T = (v1 , v2 , . . . vm )v12 v2 v1= ...vm v1v1 v2v22...vm v2. . . v 1 vn. . . v 2 vn ... ... 2. .
. vmÑâîéñòâà H:1.H = HT ,òàê êàêVV T ñèììåòðè÷íà.2. H îðòîãîíàëüíà, òî åñòüH −1 = H TÄîêàçàòåëüñòâî.H T H = H 2 = (E − 2òàê êàêVV TVV TVV T VV TVV T)(E−2)=E+4−4= E,kVk2kVk2kVk4kVk2V T V = kVk2Óòâåðæäåíèå 4. Ïóñòü çàäàí ïðîèçâîëüíûé âåêòîð x = (x1 , . . . , xn )T .Òîãäà ìîæíî âûáðàòü âåêòîð V = (v1 , v2 , . . .
vm )T òàêèì îáðàçîì, ÷òîïîñòðîåííîå ïî íåìó ïðåîáðàçîâàíèå H ïîäàâëÿåò âñå êîîðäèíàòû âåêòîðàêðîìå ïåðâîãî.−σ 0Hx = . , σ = kxk ..0Äîêàçàòåëüñòâî.Hx = x −V = x + σz, z = (1, 0, . . . , 0)TÂûáåðåì âåêòîðÒîãäà2(x + σz)(x + σz)T(x + σz)Tx = x − (x + σz)=T(x + σz) (x + σz)(x + σz)T (x + σz)Òàê êàê(x + σz)T x = kxk2 + σx1(x + σz)T (x + σz) = kxk2 + σx1 + σx1 + σ 2kxk = σ ïî óñëîâèþÏîýòîìó2kxk2 − 2σx1= σz2kxk2 − 2σx1−σ 0Hx = . ..0= x − (x + σz)Ãëàâà 1. ×èñëåííûå ìåòîäû ëèíåéíîé àëãåáðû36Äëÿ ñâåäåíèÿ ìàòðèöû A ê ÂÏÒÔ ïðåäñòàâèì åå â áëî÷íîì âèäå:|a11ym−1 , xm−1 = (a21 , a31 , . . . , am1 )T , ym−1 = (a12 , a13 , . . .
, a1m )A=| Am−1xm−1Èç óòâåðæäåíèÿ ñëåäóåò, ÷òî ñóùåñòâóåò ìàòðèöàHm−1 :Hm−1 xm−1 = (−kxm−1 k, 0, . . . , 0)THm−1 ïîñòðîèì áëî÷íóþ ìàòðèöó:1 |a12 , a12 = (0, . . . , 0), a21 = (0, . . . , 0)TU1 = a21 | Hm−1Ïî ìàòðèöåÑâîéñòâà ìàòðèöû1.U1 = U1T2.U1U1 : ñèììåòðè÷íàÿ.- îðòîãîíàëüíàÿ.Äîêàçàòåëüñòâî.1|0U12 = U1 U1T = êàêH| Hm−1|0U−1 A = U1 A = 2Hm−1a11|| Hm−11= E} =0ym−1× × ... × × ...= 0 × ... .... ..0 × ...| Hm−1×× × . .
.×1001|0|2Hm−1= E = U1 U1−1|a11ym−1=00=0 îðòîãîíàëüíàÿ, òî1|10= {òàêxm−1| Am−1C1 = U −1 AU1 =a11|ym−11 |0Hm−1 xm−1 | Hm−1 Am−10 | Hm−1× × × ... × × × ...(1)= {Cij } = 0 ∗ × . . . .. .... . ..0 ∗ × ...=Hm−1 xm−1a11|| Hm−1 Am−1ym−1 Hm−1==Hm−1 ym−1×××...×| Hm−1 Am−1 Hm−11.10. Ïðèâåäåíèå ìàòðèöû ê âåðõíåé ïî÷òè òðåóãîëüíîé ôîðìå(1)(1)1xm−2 = (C32 , C42, .
. . , Cm2 )TÏî âåêòîðóïîìå÷åí êàê37∗xm−2 ìû ìîæåì ïîñòðîèòü ïðåîáðàçîâàíèå Õàóñõîëäåðà Hm−1 :Hm−2 xm−2 = (−σ2 , 0, . . . , 0)TE2|0 , U2 = U2T = U2−1 , U22 = EU2 = 0| Hm−2−1C2 = U2 C1 U2 = × × × ...× × × ...0 × × ...0 0 × .........00...××××...× ...×C2 = U2−1 U1−1 AU1 U2Ñäåëàâ åùå(m − 2)àíàëîãè÷íûõ øàãà, ïîëó÷èì:−1−1C = Um−2Um−3. .
. U2−1 U1−1 AU1 U2 . . . Um−2 =× × × ... × × × × ... × . ..... ÂÏÒÔ= 0 × × . . .. ..... .. ....0 0 ... × ×U = U1 U2 . . . Um−2 ⇒Îáîçíà÷èì−1−1TTU −1 = Um−2Um−3. . . U2−1 U1−1 = Um−2Um−3. . . U2T U1T == (U1 U2 . . . Um−2 )T = U T ⇒ U −1 îðòîãîíàëüíàÒàêèì îáðàçîì:C = U −1 AUÓòâåðæäåíèå 5. Ïðåîáðàçîâàíèå ïîäîáèÿ ñîõðàíÿþò ñïåêòð ìàòðèöûÄîêàçàòåëüñòâî.x 6= 0 : Ax = λx ⇒ U −1 Ax = λU −1 xx = U y ⇒ y = U −1 x, y 6= 0Îáîçíà÷èìU −1 AU y = λy, Cy = λy, y 6= 0 ⇒ ñïåêòðÇàìå÷àíèå:ÅñëèC = CTñîõðàíÿíòñÿè îíà ÂÏÒÌ, òî îíà òðåõäèàãîíàëüíàÿ.Ãëàâà 1.
×èñëåííûå ìåòîäû ëèíåéíîé àëãåáðû381.11Ïîíÿòèå QR àëãîðèòìîâ ðåøåíèÿ ïðîáëåìû ñîáñòâåííûõ çíà÷åíèéA(m × m)Ëþáóþ ìàòðèöó A ìîæíî ïðåäñòàâèòü â âèäåA = QR,ãäåQ−1 = QT R-âåðõíåòðåóãîëüíàÿ.Ðàññìîòðèì âåêòîðxm = (a11 , . . . , am1 )T .Äëÿ íåãî íàéäåòñÿ ìàòðèöàH1 :H1 xm = (kxm k0, . .
. , 0)TÏîñëå ïåðâîãî øàãà ìû ïîëó÷èì ìàòðèöó:× 0 .. .0Âåêòîðxm−1ïîìå÷åí∗.×∗× ...× .........∗× ...Äëÿ âåêòîðàxm−1×× . . .×ìû ìîæåì âûáðàòü ìàòðèöóH:Hxm−1 = (kxm−1 k0, . . . , 0)1 0H2 =0 HÒîãäà, ïîäåéñòâîâàâ íà ìàòðèöó À ïðåîáðàçîâàíèåìH1 , ïîòîì H2 , ðîëó÷èììàòðèöó âèäà:Ïðîäåëàâ ýòè øàãè(m − 1)××0× × ...× × ...0 × .........00...× ...×××...×ðàç ïîëó÷èì:Hm−1 Hm−2 . . . H2 H1 = R|{z}QQ îðòîãîíàëüíà:−1TQ−1 = Hm−1. .
. H2−1 H1−1 = Hm−1. . . H2T H1T = QT1.11.11.A0A1...AkAkQR - àëãîðèòì= A. Ïðåäñòàâèì A0 = Q0 R0 , R0 ÂÒÔ, QT0 = Q−10−1= R0 Q0 ⇒ R0 = Q−10 A0 ⇒ A1 = Q0 A0 Q0= Qk Rk= Rk Qk = Q−1k Ak QkÑïåêòðû ó ìàòðèö Ak è Ak+1 îäèíàêîâûåλ1λ2lim An = ..n→∞ O.Xλm1.12. Ïðåäâàðèòåëüíîå ïðåîáðàçîâàíèå ìàòðèöû ê ÂÏÒÔ. Íåóõóäøåíèå ÂÒÏÔ ïðè QR-àëãîðèòìå 39Åñëè æå åñòü êîìïëåêñíûå ñîáñòâåííûå çíà÷åíèÿ, òî ìàòðèöà, ê êîòîðîé ñõîäèòñÿ ïðîöåññ èìååò âèä:×X×C=∗∗∗∗..O.Çàìå÷àíèå 1: Íà÷àëüíîå ïðèáëèæåíèå A0 íóæíî âûáèðàòüÇàìå÷àíèå 2: QR àëãîðèòì òðåáóåò3ÅñëèA - ïðîèçâîëüíàÿ O(m ) äåéñòâèé .2ÅñëèA ÂÏÒÌ O(m ) äåéñòâèé .ÅñëèA òðåõäèàãîíàëüíàÿ O(m) äåéñòâèé .1.12â âèäå ÂÏÒÌ.Ïðåäâàðèòåëüíîå ïðåîáðàçîâàíèå ìàòðèöû ê ÂÏÒÔ. Íåóõóäøåíèå ÂÒÏÔ ïðè QRàëãîðèòìåËåììà 1.
Ïóñòü çàäàíî ïðîèçâåäåíèå ìàòðèö C = BA, ãäå B âåðõíåòðåóãîëüíàÿ, A ÂÏÒÔ. Òîãäà C ÂÏÒÔ.Äîêàçàòåëüñòâî.cij =mXbiα aαj =i−1Xα=1α=1biα = 0,Ýòî îçíà÷àåò, ÷òîCbiα aαj +|{z}j+1Xbiα aαj +0α=iåñëèi > α, aαj = 0,j+1Xbiα aαj =biα aαj|{z} α=iα=j+2mX0åñëèα>j+1 ÂÏÒÔ.Ëåììà 2. Ïóñòü C = BA, ãäå A âåðõíåòðåóãîëüíàÿ, B ÂÏÒÔ.
ÒîãäàC ÂÏÒÔ.Äîêàçàòåëüñòâî àíàëîãè÷íîå.Ïðèìåíèòåëüíî ê QR-àëãîðèòìó, ýòî îçíà÷àåò ñëåäóþùåå:A0 = Q0 R0 , R0Åñëè ìû ïðèâåäåìA0ê ÂÏÒÔ, òî ÂÒÔQ0 ÂÏÒÔ èA1 = R0 Q0òàê-æå ÂÏÒÔ. Ïîëó÷àåì íà êàæäîé èòåðàöèè ÂÏÒÔ, åñëè ïåðâàÿ ìàòðèöàA0ïðèâåäåíà ê ÂÏÒÔ. Òàêèì îáðàçîì, íàì äîñòàòî÷íî îäèí ðàç ïðèâåñòè ìàòðèöóA0ê ÂÏÒÔ, à ïîñëå ýòîãî áóäåò ïîëó÷àòüñÿ òîëüêî ÂÏÒÔ, òî åñòüQR-àëãîðèòì íå ïîðòèò ÂÏÒÔ.  ñèëó òîãî, ÷òî QR-ðàçëîæåíèå ìàòðèöû,èìåþùåé ÂÏÒÔ, òðåáóåòO(m2 )äåéñòâèé, ïðèâåäÿA0ê ÂÏÒÔ, ïîëó÷àåìáîëåå áûñòðîå ðåøåíèå ïîëíîé ïðîáëåìû ñîáñòâåííûõ çíà÷åíèé.40Ãëàâà 1. ×èñëåííûå ìåòîäû ëèíåéíîé àëãåáðûÃëàâà 2Èíòåðïîëèðîâàíèå èïðèáëèæåíèå ôóíêöèé2.1Ïîñòàíîâêà çàäà÷è èíòåðïîëèðîâàíèÿx ∈ [a, b], a ≤ x0 < .
. . < xn ≤ b{xi }n0 − óçëûÇàäàíà ôóíêöèÿ, ó êîòîðîé èçâåñòíû çíà÷åíèÿ â óçëàõf (xi ) = fi i = 0, nÍàäî ïîñòðîèòü ôóíêöèþ, ñîâïàäàþùóþ ñ ýòîé ôóíêöèåé â óçëàõ è îáëàäàþùóþ íåêîòîðûìè ñâîéñòâàìè. Èíòåðïîëèðîâàíèå ïîëèíîìàìè ñàìûéðàçðàáàòûâàåìûé è ñàìûé ïðîñòîé ñïîñîá.Pn (x) = a0 + a1 x + . .
. + an xn(2.1)Çàäà÷à èíòåðïîëèðîâàíèå ïîëèíîìàìè çàêëþ÷àåòñÿ â íàõîæëåíèèPn (x) = fi , i = 1, mPn (x):(2.2)Ïîêàæåì ÷òî èíòåðïîëÿöèÿ ïîëèíîìîì (2.1) ñóùåñòâóåò, åäèíñòâåííàè óäîâëåòâîðÿåò óñëîâèþ (2.2) Ïîäñòàâèì âPn (x)óçëû. Ïîëó÷èì ñèñòåìóëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèé, îòíîñèòåëøüíî ïåðåìåííûõPn (x0 ) = a0 + a1 x0 + . .
. +Pn (x1 ) = a1 + a1 x1 + . . . +an xn0an xn1a0 , . . . , an= f0= f1...Pn (xn ) = an + a1 xn + . . . + an xnn = fnÎïðåäåëèòåëåì ïîëó÷åííîé ñèñòåìû ÿâëÿåòñÿ îïðåäåëèòåëü Âàíäåðìîíäà: 1 1|A| = 1x0x1...xnx20x21x2n. . . xn0. . . xn1.... . . xnnY=(xi − xj ) 6= 0, n≥i≥j≥0òàê êàêxi 6= xj , i 6= jÑëåäîâàòåëüíî, ñèñòåìà âñåãäà èìååò åäèíñòâåííîå ðåøåíèå ïðè ëþáûõïðàâûõ ÷àñòÿõ. Ñëåäîâàòåëüíî, êîýôôèöèåíòû èíòåðïîëÿöèîííîãî ïîëèíîìà îïðåäåëÿþòñÿ îäíîçíà÷íî. Òàêèì îáðàçîì, èíòåðïîëÿöèîííûé ïîëèíîìñóùåñòâóåò è åäèíñòâåíåí.41Ãëàâà 2. Èíòåðïîëèðîâàíèå è ïðèáëèæåíèå ôóíêöèé422.2Èíòåðïîëÿöèîííàÿ ôîðìóëà Ëàãðàíæà. Ïîãðåøíîñòü ôîðìóëû Ëàãðàíæà{xi }n0 − óçëûLn (xi ) = fi 0, nÎïðåäåëåíèå 13.
èñêîìûé ïîëèíîì n-é ñòåïåíè(2.3)Èíòåðïîëÿöèîííûì ïîëèíîìîì Ëàãðàíæà íàçûâàåòñÿïîëèíîì âèäà:Ln (x) =nXck (x)f (xk ), ck ïîëèíîì n-é ñòåïåíèk=0Ââåäåì ïîëèíîì(n + 1)ñòåïåíè:ω(x) = (x − x0 )(x − x1 ) . . . (x − xn ) =nY(x − xi )i=0Åãî ïðîèçâîäíàÿ â óçëàõ ìîæåò áûòü íàéäåíà èç:0ω 0 (x) = [ ] + (x − xk )[ ] ⇒⇒ ω 0 (xk ) = (xk − x0 )(xk − x1 ) . . . (xk − xk−1 )(xk − xk+1 ) . . . (xk − xn )Òîãäà, ïîëèíîì Ëàãðàíæà ìîæíî çàïèñàòü â âèäå:Ln (x) =nXk=0ω(x)f (xk )(x − xk )ω 0 (xk )Äîãîâîðèìñÿ, ÷òî ôóíêöèÿ âñåãäà îáëàäàåò òîé ãëàäêîñòüþ, êîòîðàÿíåîáõîäèìà íàì äëÿ ïðîâåäåíèÿ ðàññóæäåíèé.ψLn (x) = f (x) − Ln (x)ïðîãðåøíîñòüÎöåíêà íàψLn (x)ïîëó÷àåòñÿ ïðèìåíåíèåì òåîðåìû ÐîëëÿψLn (x) =Îáîçíà÷èì(n + 1)ðàç.f (n+1) (ξ)ω(x), ξ ∈ [a, b](n + 1)!Mn+1 = sup kf (n+1) (x)k[a,b]|ψLn (x)| ≤Çàìå÷àíèå:Åñëèf (x) Mn+1|ω(x)|(n + 1)!ïîëèíîì n-é ñòåïåíè, òî ïîãðåøíîñòü âñþäó 0, òàêêàê (n+1) ïðîèçâîäíàÿ îò n-é ñòåïåíè ðàâíà 0, ñëåäîâàòåëüíîψLn = 0Çàìå÷àíèå:Çà ñ÷åò âûáîðà óçëîâxnMn+1 = 0 ⇒ìîæíî ïîñòðîèòü ïîëèíîì, ó êîòî-ðîãî ïîãðåøíîñòü íå áóäåò ñòðåìèòüñÿ ê 0.
Èíòåðïîëèðîâàíèå ïîëèíîìîìïðèìåíÿþò ïðè íåáîëüøîì n.2.3. Ðàçäåë¼ííûå ðàçíîñòè2.343Ðàçäåë¼ííûå ðàçíîñòèÏóñòü íà îòðåçêå[a, b]çàäàíû íåêîòîðûå çíà÷åíèÿ:a ≤ x0 < x1 < x2 < . . . < xN ≤ b,Nãäå {xi }0 - óçëû,f (xi ) = fi , i = 0, N .Îïðåäåëåíèå 14.f (x),(2.4)Ðàçäåë¼ííîé ðàçíîñòüþ ïåðâîãî ïîðÿäêà äëÿ ôóíêöèèïîñòðîåííîé ïî óçëàìf (xi , xj ) =xi , xj ,íàçûâàåòñÿ îòíîøåíèå:f (xi ) − f (xj ), i = 0, N , j = 0, N , i 6= j.xi − xj(2.5)Ðàçäåë¼ííàÿ ðàçíîñòü ýòî äèñêðåòíûé àíàëîã ïåðâîé ïðîèçâîäíîé.Íà ïðàêòèêå ðàçäåë¼ííûå ðàçíîñòè â ïîäàâëÿþùåì áîëüøèíñòâå ñëó÷àåâñòðîÿòñÿ ïî ñîñåäíèì óçëàì, íàïðèìåð:f (x0 , x1 ) =Îïðåäåëåíèå 15.f (x, y),f (x1 ) − f (x0 )f (x2 ) − f (x1 ), f (x1 , x2 ) =.x1 − x0x2 − x1Ðàçäåë¼ííîé ðàçíîñòüþ âòîðîãî ïîðÿäêà äëÿ ôóíêöèèïîñòðîåííîé ïî óçëàìf (xk−1 , xk , xk+1 ) =xk−1 , xk , xk+1 ,íàçûâàåòñÿîòíîøåíèå:f (xk , xk+1 ) − f (xk−1 , xk ), k = 1, N − 1.xk+1 − xk−1Òåïåðü, ïóñòü îïðåäåëåíà ðàçäåë¼ííàÿ ðàçíîñòü ïîðÿäêàxj , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
