Численные методы. Ионкин (2012) (v1.1) (косяки есть), страница 6

äåéñòâèå íà âåêòîð - ñïåöèôè÷íî2kvk2 = vv T = v12 + v22 + ...vm 2v1 v1 v2 .... v1 vm v2 v1 v22 .... v2 vm  - ñèììåòðè÷íàÿ ìàòðèöàvv T =  ........ .... .... 2vm v1 vm v2 .... vmTÒ.ê. E - òîæå ñèììåòðè÷íàÿ ⇒ H = H , ò.å. H - ñèììåòðè÷íàÿT−1Äîêàæåì, ÷òî H - îðòîãîíàëüíà, ò.å., ÷òî H = HÂîîáùå ãîâîðÿ:ìàòðèöà.H T H = HH = H 2 =2vv T2vv Tvv Tvv T vv T= (E −)(E −)=E−4+4=kvk2kvk2kvk2kvk4vv Tvkvk2 v Tvv Tvv T+4=E−4+4=E=E−4kvk2kvk4kvk2kvk2Ñëåäîâàòåëüíî H - îðòîãîíàëüíà.Ïîÿñíèì, ÷òî îçíà÷àåò òðåòüå ñâîéñòâî.Ïóñòü çàäàí ïðîèçâîëüíûé âåêòîð-ñòîëáåöÒîãäà ìîæíî âûáðàòü âåêòîðvòàêîé, ÷òîx = (x...., xm )T .1 , x2 ,−σ 0 Hx =  ....

, ãäå σ = kxk.0Äîêàçàòåëüñòâî:Ïîëîæèìäëèíûv = x + σz ,ãäåz- âåêòîð ñïåöèàëüíîãî âèäàz = (1, 0, ...., 0)Tm.Hx = (E −2(x + σz)(x + σz)T2vv T)x=x−x=kvk2(x + σz)T (x + σz)41-2(x + σz)T x= x − (x + σz)(x + σz)T (x + σz)÷èñëèòåëü:2(x + σz)T x = 2(xT x + σz T x) = 2(kxk2 + σx1 )çíàìåíàòåëü:(x + σz)T (x + σz) = kxk2 + σx1 + σx1 + σ 2σ = kxk2 ;Òîãäà ÷èñëèòåëü= 2σ 2 + 2σx1 ,çíàìåíàòåëü= 2σ 2 + 2σx1ÒîãäàÒîãäà÷òä.2(x + σz)T x=1(x + σz)T (x + σz) −σ 0 Hx = x − x − σz =  ....

0Òåïåðü äîêàæåì, ÷òî ëþáóþ ìàòðèöóAìîæíî ñâåñòè ê ÂÏÒÔ.A=çäåñüym−1 = (a12 , a13 , ...., a1m ),a11 ym−1xm−1 Am−1,xm−1 = (a21 , a31 , ...., am1 )T .xm−1= (1, 0, ...., 0)Ïî òðåòüåìó ñâîéñòâó ñïåöèôè÷íîñòè äëÿ âåêòîðàv = xm−1 − σzm−1 ,ãäåkxm−1 k = σ,zm−1âûáåðåì âåêòîðHm−1 xm−1 = −σzm−1 = (−σ, 0, ...., 0)TÂâåäåì U1 :1012U1 =021 Hm−1ÒîãäàÇäåñü012 = (0, ...0),Î÷åâèäíî òàêæå, ÷òî021 = (0, ..., 0)TU1 = U1TÏðîâåðèì îðòîãîíàëüíîñòü ìàòðèöûU12= U1 U1 =1012021 Hm−1 âåêòîðà äëèíûm−1U1 :1012021 Hm−1Hm−1 Hm−1 = E−1Çíà÷èò U1= U1T = U1 .ò.ê.ÒîãäàU1−1 A = U1 A =42=10122021 Hm−1= E,v:1012021 Hm−1=a11 ym−1xm−1 Am−1=a11ym−1Hm−1 xm−1 Hm−1 Am−1U1 , ÷òîáû áûëî ïðåîáðàçîâàíèå ïîäîáèÿ:a11ym−11012−1U1 AU1 =Hm−1 xm−1 Hm−1 Am−1021 Hm−1a11ym−1 Hm−1=,−1−σ1 zm−1 Hm−1Am−1 Hm−1äîìíîæèì ñïðàâà íàçäåñüσ1 = kxm−1 k.Òîãäà ìàòðèöà èìååò âèä:xx0U −1 AU = C1 = 0....0Ïåðâûé øàã çàâåðøåí.

Íà âòîðîì øàãå áåðåìíåìó îïÿòü âûáèðàåì âåêòîðvè ìàòðèöóHm−2 :1 0U2 =01021012Hm−2xx0−1 −1C2 = U2 U1 AU1 U2 = 00....0Ò.å. ÷åðåçC=(m − 2)xxxXx....xxm−2 = (c32 , c42 , ...., cm2 )T ,Hm−2 xm−2 = −σ2 zm−2xxx00....0øàãà ìû ïîëó÷èì ìàòðèöóxxxxx....x............................xxxxxxxC:−1Um−2...U2−1 U1−1 AU1 U2 ...Um−2 - ìàòðèöó ÂÏÒÔ.Íóæíî óáåäèòüñÿ, ÷òî ïðåîáðàçîâàíèÿ cîõðàíÿëè ñâîéñòâà ïîäîáèÿ.Îáîçíà÷èìÍàéäåìUU = U1 U2 ...Um−2−1:−1U −1 = (U1 U2 ...Um−2 )−1 = Um−2...U2−1 U1−1 =43ò.ê.Uiîðòîãîíàëüíàÿ=ïîT= Um−2...U2T U1T = U TU - îðòîãîíàëüíàÿ.Èìååì C = UAU , ãäå C - èìååò ÂÏÒÔ.Ìû ïîêàçàëè, ÷òî ëþáóþ A ìîæíî ñâåñòè ê ÂÏÒÔ ïðåîáðàçîâàíèÿìè ïîäîáèÿÒàêèì îáðàçîì−1ñ ïîìîùüþ îðòîãîíàëüíîé ìàòðèöû.Çàìå÷àíèå 1:Ñîáñòâåííûå çíà÷åíèÿ ìàòðèöûA:λAk=λCkCðàâíû ñîáñòâåííûì çíà÷åíèÿìè ìàòðèöûk = 1, ...., mÄîêàçàòåëüñòâî:Ax = λx;x 6= 0U −1 : U −1 Ax = λU −1 x;−1îáîçíà÷èì y = Ux òîãäà x = U y−1òîãäà UAU y = λy; y 6= 0çíà÷èò Cy = λy⇒ λ - ñîáñòâåííîå çíà÷åíèå CÄîìíîæèì ñëåâà íà(∀λk ) ÷òä.Çàìå÷àíèå 2:Ñîõðàíÿåòñÿ ñèììåòðèÿ, ò.å.

åñëèA = AT ,òîC = CTÄîêàçàòåëüñòâî:C = U −1 AUC T = (U −1 AU )T = U T AT (U −1 )T = U −1 AU = C÷òä.Ÿ 12. Ïîíÿòèå î QR-àëãîðèòìå. Ðåøåíèå ïîëíîéïðîáëåìû ñîáñòâåííûõ çíà÷åíèéÈìååòñÿ ïðîèçâîëüíàÿ ìàòðèöà - êâàäðàòíàÿ, ïîðÿäêàm.Am×mÏîñòàâèì çàäà÷ó - ôàêòîðèçîâàòü ìàòðèöóãäåQ- îðòîãîíàëüíàÿ,RAâ âèä:A = QR,- èìååò âåðõíþþ òðåóãîëüíóþ ôîðìóÁåðåì îáîçíà÷åíèÿ:x = (a11 , a21 , ...., am1 )Tv = x + σz , ãäå z = (1, 0, 0, ...., 0)ñòðîèì âåêòîð ðàçìåðàmH1m×m :2vv T: H1 = H1T = H1−1=E−2kvkH1 íà ìàòðèöó A:H1m×mïîäåéñòâóåì ìàòðèöåé44x00H1 A = 0....0xxxXx....x(m−1)×(m−1)H21 012H2 =021 HÒåïåðü ïî âòîðîìó ñòîëáöó ñòðîèì:H2−1 = H2T = H2Òîãäàx00H2−1 H1−1 A = 0....0×åðåçm−1xx0X0....0øàã ïîëó÷èì âåðõíþþ òðåóãîëüíóþ ìàòðèöó.R = Hm−1 Hm−2 ....H2 H1 AQ = H1 H2 ...Hm−1Ïîëó÷èëè ìàòðèöóÎáîçíà÷èì ÷åðåçÍàéäåìQ−1 :−1TQ−1 = (H1 H2 ...Hm−1 )−1 = Hm−1....H1−1 = Hm−1....H2T H1T = QTÒàêèì îáðàçîìA = QR.Q- îðòîãîíàëüíàÿ, çíà÷èò:Ñëåäîâàòåëüíî ëþáóþ ìàòðèöó ìîæíîQRðàçëîæèòü.Ak+1 = Q−1k Ak Qk ïðåîáðàçîâàíèå ïîäîáèÿ ñ îðòîãîíàëüíîéÏðè k → ∞ è âåùåñòâåííûõ λk :x x ...

x 0 x ... x Ak → ... ... ... ...0 0 ... xÏðè êîìïëåêñíûõλk :45ìàòðèöåéx0...Ak → 000QR-àëãîðèòìxx...000..................xx...xx0xx...xx0xx...xxxñõîäèòñÿ ê ìàòðèöå (âåðõíåòðåóãîëüíîé, åñëèè êâàçèâåðõíåòðåóãîëüíîé, åñëèλkλkâåùåñòâåííûå,êîìïëåêñíûå). Òàêèì îáðàçîì, îí ïðèìåíèì êëþáîé ìàòðèöå.Ÿ 13. Ïðåäâàðèòåëüíîå ïðåîáðàçîâàíèå ìàòðèöû êÂÏÒÔAk = Qk Rk(1.57)Ak+1 = Rk Qk k = 0, 1, ...(1.58)A → A0Ëåììà 1:ïóñòüóãîëüíóþ ôîðìó,AA, B ìàòðèöû îäíîãî ïîðÿäêà,Bèìååò âåðõíþþ òðå- âåðõíþþ ïî÷òè òðåóãîëüíóþ ôîðìó,C = BA.ÒîãäàCèìååò âåðõíþþ ïî÷òè òðåóãîëüíóþ ôîðìó.Äîêàçàòåëüñòâî: Bâ âåðõíåé òðåóãîëüíîé òî åñòücij =mXbil = 0ïðèi > l.bil aljl=1Aâ âåðõíåé ïî÷òè òðåóãîëüíîé òî åñòücij =j+1Xalj = 0ïðèl > j + 1.bil aljl=1cij = 0ïðèÇàäà÷à: AÄîêàçàòü:Ci>j+1 òî åñòüCâ âåðõíåé ïî÷òè òðåóãîëüíîé ôîðìå.

âåðõíÿÿ ïî÷òè òðåóãîëüíàÿ,B âåðõíÿÿ òðåóãîëüíàÿ,C = AB . âåðõíÿÿ ïî÷òè òðåóãîëüíàÿ.Òåïåðü ìû çíàåì, ÷òîQR-àëãîðèòìíå ïîðòèò ÂÏÒÔ. Ïåðåïèøåì (1.57) è(1.58):46Qk = Ak Rk−1 = {ÂÏÒÔ} × {ÂÒÔ} = Qk = {ÂÏÒÔ}Ak+1 = Rk Qk47 ÂÏÒÔÃëàâà 2Èíòåðïîëèðîâàíèå èïðèáëèæåíèå ôóíêöèéŸ 1. Ïîñòàíîâêà çàäà÷è èíòåðïîëèðîâàíèÿÈíòåðïîëèðîâàíèå è ïðèáëèæåíèå ôóíêöèé - ýòî î÷åíü ¼ìêîå ïîíÿòèå. Ýòîìîæíî ðåøàòü áåñ÷èñëåííûì êîëè÷åñòâîì ñïîñîáîâ, â çàâèñèìîñòè îò ïîñòàâëåííîé öåëè.Ñåé÷àñ ìû âñïîìíèì è ïîëèíîì Ëàãðàíæà, çàòåì ðàññìîòðèì èíòåðïîëÿöèîííûé ïîëèíîì Íüþòîíà. Äàëåå íà÷í¼ì ñòðîèòü ïîëèíîì Ýðìèòà è ïîêàæåì,äëÿ ÷åãî íóæíû îíè. Íó è íàèëó÷øåå êâàäðàòè÷íîå ïðèáëèæåíèå ôóíêöèè.Ýòî íàèáîëåå äðåâíÿÿ îáëàñòü, íî îíà àêòóàëüíà è ïîíûíå, ïîñêîëüêó áåçèíòåðïîëèðîâàíèÿ ìàòåìàòèê îáîéòèñü íå ìîæåò.

Ýòî àêòóàëüíî äëÿ ñïåöèàëüíûõ ôóíêöèé, êîòîðûå íå âûðàæàþòñÿ ÷åðåç ýëåìåíòàðíûå, íî èñïîëüçóþòñÿäëÿ ðåøåíèÿ äèôóðîâ. Îáû÷íî èñïîëüçóþòñÿ òàáëèöû, íî âîçíèêàåò âîïðîñ, ÷òîäåëàòü, êîãäà íóæíî ïîëó÷èòü çíà÷åíèå äëÿ àðãóìåíòà, êîòîðîãî íåò â òàáëèöå.Ïåðâîå ðåøåíèå ñãóùàòü òàáëèöû. Åù¼ îäíî ïîëüçîâàòüñÿ èíòåðïîëèðîâàíèåì.Ãäå åù¼ òðåáóåòñÿ èíòåðïîëèðîâàíèå åñòü äîìíà, çà íåé íàäî ñëåäèòü. Íàäî íàñòàâèòü äàò÷èêîâ, íî ìíîãî èõ ïîñòàâèòü íåëüçÿ, èíà÷å îíà ðàçðóøèòñÿ, àèíôîðìàöèþ íàäî ïîëó÷àòü ïî âñåìó ïðîôèëþ. Ïîýòîìó íàäî èñïîëüçîâàòü èíòåðïîëÿöèþ.Åø¼ îäíî ïðèìåíåíèå ðàçíîñòíûå ñõåìû.Åù¼ îäíî ïðèìåíåíèå ýêñòðàïîëèðîâàíèå.Îáû÷íî áóäåì èñïîëüçîâàòü ïðèáëèæåíèå ïîëèíîìîì.f (x) x ∈ [a, b] a ≤ x0 < x1 < ... < xn ≤ b48{xi }n0 óçëû èíòåðïîëÿöèè.f (xi ) = fi , i = 0...n(2.1)Pn (x) = a0 + a1 x + ...

+ an xn(2.2)Pn (xi ) = fi , x = 0...n(2.3)na0 + a1 x0 + ... + an xn0 = f0 ...a0 + a1 xn + ... + an xnn = fn(2.4)Îïðåäåëèòåëü ñèñòåìû îïðåäåëèòåëü Âàíäåðìîíäà:11...1x0x1...xnx20x21...x2n............xn0 Yxn1 =(xi − xj ) 6= 0... n≥i>j≥0xnn Òàê êàê îí íåíóëåâîé, ñèñòåìà èìååò åäèíñòâåííîå ðåøåíèå.Ÿ 2. Èíòåðïîëÿöèîííàÿ ôîðìóëà ËàãðàíæàLn (xi ) = fi , i = 0...nck (x) ïîëèíîìn-é(2.5)ñòåïåíè.Ln (x) =nXck (x)f (xk )(2.6)k0nYω(x) =(x − xi )(2.7)i=0Ïðîäèôôåðåíöèðóåìω(x):ω(x) = [...](x − xk )nY00ω (x) = [...] + [...] (x − xk ) =(xk − xj )k6=jÂîçüì¼ìck (x) =ω(x)(x−xk )ω 0 (xk ) . ÒîãäàLn (x) =nXk=0ω(x)f (xk )(x − xk )ω 0 (xk )49(2.8)Ln (x):Ïîãðåøíîñòü äëÿΨLn (x) = f (x) − Ln (x)g(s) = f (s) − Ln (s) − Kw(s)g(x) = 0; K =f (x)−Ln (x)w(x)ΨLn (x) =f (n+1) (ξ)ω(x)(n + 1)!|ΨLn (x) | =Mn+1|ω(x)|(n + 1)!(2.9)Mn+1 = sup |f (n+1) (x)|.Çàìå÷àíèå: åñëè f (x) ïîëèíîì ñòåïåíè n èëè ìåíüøå, òî ïîãðåøíîñòü áóäåòðàâíà íóëþ, è ìû ïîëó÷èì â òî÷íîñòè åãî.Åù¼ çàìå÷àíèå:âîîáùå ãîâîðÿ,Ln (x) 6→ f (x).Ÿ 3.

Ðàçäåëåííûå ðàçíîñòèf (x) x ∈ [a, b] a ≤ x0 < x1 < ... < xn ≤ bÐàçäåë¼ííàÿ ðàçíîñòü ïåðâîãî ïîðÿäêà îïðåäåëÿåòñÿ êàêf (xi , xj ) =f (xj ) − f (xi )xj − xif (x0 , x1 ) =f (x1 ) − f (x0 )x1 − x0 ÷àñòíîñòè,Ðàçäåë¼ííàÿ ðàçíîñòü âòîðîãî ïîðÿäêà:f (x0 , x1 , x2 ) =f (x1 , x2 ) − f (x1 , x0 )x2 − x0Ðàçäåë¼ííàÿ ðàçíîñòü âûñøèõ ïîðÿäêîâ îïðåäåëÿåòñÿ àíàëîãè÷íî.Âûðàçèì îïðåäåëÿþùóþ ðàçíîñòük -ãîïîðÿäêà ÷åðåç êðàòíîñòü óçëà.Óòâåðæäåíèå:Ðàçäåëåííàÿ ðàçíîñòük -ãîïîðÿäêà ïðåäñòàâèì â âèäåkXf (xi )f (x0 , x1 , .

. . , xk ) =,0w(x)ii=050ãäåw(x) = (x − x0 )(x − x1 ) . . . (x − xn );wα,β (x) = (x − xα )(x − xα+1 ) . . . (x − xβ );00w (xi ) = w0,k (xi ) = Πkj=0 (xi − xj )j6=iÄîêàçàòåëüñòâî:Ïî èíäóêöèè:1)Ïî îïðåäåëåíèþ:f (x0 , x1 ) =f (x0 )f (x1 )f (x1 ) − f (x0 )=+x1 − x0x0 − x1 x1 − x02)ÏóñòülXf (xi )f (x0 , . . . , xl+1 ) =0w0,l (xi )i=0f (x1 , . . . , xl+1 ) =l+1Xf (xi )w1,l+1 (xi )0i=03)f (x0 , x1 , . . . , xl+1 ) =f (x1 , . .

. , xl+1 ) − f (x0 , . . . , xl )xl+1 − x0Â ñóììèðîâàíèè ïðåäåëû ðàçíûå. Âûäåëèì èõ:⇒ f (x0 , x1 , . . . , xl+1 ) =+lXi=1Òàêæåf (xl+1 )f (x0 )++00(x0 − xl+1 )w0,l (x0 ) (xl+1 − x0 )w1,l+1 (xl+1 )f (xi )11( 0−)xl+1 − x0 w1,l+1 (xi ) w0,l (xi )0(xl+1 − x0 )w1,l+1 (xl+1 ) = w0,l+1 (xl+1 ),0(x0 − xl+1 )w0,l 0 (x0 ) = w0,l+1 (x0 ),111( 0− 0)=xl+1 − x0 w1,l+1 (xi ) w0,l (xi )==1xi − x0x0 − xi( 0− 0)=xl+1 − x0 w1,l+1 (xi )(xi − x0 ) w0,l (xi )(x0 − xi )1(xi − x0 )xi − xl+11(− 0)= 0⇒0xl+1 − x0 w0,l+1 (xi ) w0,l+1 (xi )w0,l+1 (xi )51kXf (xi )f (x0 , . .

. , xl+1 ) =0w(xi )0,ki=0Âûðàçèì çíà÷åíèå ôóíêöèè âëåííîé ðàçíîñòèk -ãîk -îéòî÷êå ÷åðåç çíà÷åíèå â íóëåâîé è ðàçäå-ïîðÿäêà.Äîêàçûâàåì ïî ïî èíäóêöèè:1)k=1:f (x1 )f (x1 ) − f (x0 )f (x0 )+=x0 − x1 x1 − x0x1 − x0(x1 − x0 )f (x0 , x1 ) = f (x1 ) − f (x0 )f (x1 ) = f (x0 ) + (x − x0 )f (x0 , x1 )f (x0 , x1 ) =2)k=2:f (x0 , x1 , x2 ) =f (x0 )f (x1 )f x2++(x0 − x1 )(x0 − x2 ) (x1 − x0 )(x1 − x2 ) (x2 − x0 )(x2 − x1 )(x2 − x0 )(x2 − x1 )f (x0 , x1 , x2 ) = −f (x0 )(x2 − x1 ) f (x1 )(x2 − x0 )++ f (x2 )x0 − x1x0 − x1Çàìåòèì, ÷òîf (x1 )(x2 − x0 ) f (x0 )(x2 − x0 )=− f (x0 , x1 )(x2 − x0 )−x0 − x1x0 − x1−f (x0 )(x2 − x1 ) f (x0 )(x2 − x0 )f (x0 )+=(x2 − x0 − x2 + x1 ) = −f (x0 )x0 − x1x0 − x1x0 − x1f (x2 ) = f (x0 ) + (x2 − x0 )f (x0 , x1 ) + (x2 − x0 )(x2 − x1 )f (x0 , x1 , x2 ) ⇒f (xk ) = f (x0 )+(xk −x0 )f (x0 , x1 )+(xk −x1 )(xk −x2 )f (x0 , x1 , x2 )+· · ·+(xk −x0 )(xk −x1 ) .

. .Ÿ 4. Èíòåðïîëÿöèîííàÿ ôîðìóëà ÍüþòîíàÎáîçíà÷èìn+1óçåë êàê{xi }n0 ,â ýòèõ óçëàõ îïðåäåëåíà ôóíêöèÿf (xi ) = fi .Îáùèé âèä ïîëèíîìà Íüþòîíà n-îé ñòåïåíè:Nn (x) = f (x0 ) + (x − x0 )f (x0 , x1 ) + (x − x0 )(x − x1 )f (x0 , x1 , x2 ) + · · ·+(x − x0 )(x − x1 ) . . .