Н.И. Ионкин - Электронные лекции (2009) (1135239), страница 6
Текст из файла (страница 6)
. .(ñïåêòðû ýòèõ ìàòðèö ñîâïàäàþò).Çàìåòèì, ÷òî ïîä ãëàâíîé äèàãîíàëüþ ìîãóò è íå ïîëó÷àòüñÿ íóëè â ìàòåìàòè÷åñêîì ñìûñëå. Äîñòàòî÷íî, ÷òîáû çíà÷åíèÿ ïîä ãëàâíîé äèàãîíàëüþ áûëè ïî ìîäóëþ ìåíüøå íåêîòîðîãî ÷èñëà (ò.í. ìàøèííûé íîëü),îïðåäåëÿþùåãî òî÷íîñòü âû÷èñëåíèé.Åñëè ó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 ,Òåïåðü ïîñìîòðèì íà îïðåäåëèòåëü ýòîé ñèñòåìû:11∆=. . .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 )×òî è òðåáîâàëîñü äîêàçàòü.Îïðåäåëåíèå. Íàçîâåì èíòåðïîëÿöèîííûì ïîëèíîìîì Íüþòîíà ôóíê-f (x)öèèïî óçëàì{Xi }n0ïîëèíîì ñòåïåíèn:n−1Nn (x) = f (x0 ) + (x − x0 )f (x0 , x1 ) + .
. . + Πi=0f (x0 , x1 , . . . , xn )Ïîêàæåì, ÷òîNn (x)(2)èíòåðïîëÿöèîííûé ïîëèíîì:i−1Nn (xi ) = f (x0 ) + (xi − x0 )f (x0 , x1 ) + . . . + Πi=0f (x0 , x1 , . . . , xi ) + 0Ýòà ñóììà ïðåäñòàâëÿåò ñîáîé ðàçäåëåííóþ ðàçíîñòü ïîðÿäêà i, ðàâíóþêàê ðàçf (xi ).Çàìå÷àíèå.
Ïîëó÷åííûé ïîëèíîì òîëò æå ïîëèíîì Ëàãðàíæà, òîëüêî çàïèñàííûé â äðóãîé ôîðìå.Ñîîòâåòñòâåííî, åãî ïîãðåøíîñòü òà æå, ÷òî è ó ïîëèíîìà Ëàãðàíæà.Îòëè÷èå ïîëèíîìà Íüþòîíà îò Ëàãðàíæà â òîì, ÷òî äëÿ óâåëè÷åíèÿòî÷íîñòèNn (x)íàäî òîëüêî äîáàâèòü èíôîðìàöèþ î íîâûõ óçëàõ è íåíàäî ïåðåñ÷èòûâàòü çíà÷åíèÿ äëÿ ñòàðûõ.Èíòåðïîëèðîâàíèå ñ êðàòíûìè óçëàìè. Èíòåðïîëÿöèîííàÿ ôîðìóëàÝðìèòà460Èíòåðïîëèðîâàíèå ñ êðàòíûìè óçëàìè. Èíòåðïîëÿöèîííàÿ ôîðìóëà Ýðìèòàx0 , x1 , . .
. , xm , ïðè ýòîì ak ∈ N, k = 1, m a0 + . . . am = n + 1, ãäå n ñòåïåíü èíòåðïîëè-Ïóñòü èìååòñÿ m óçëîâ:êðàòíîñòü êàæäîãî óçëà (ðóþùåãî ïîëèíîìà ).Îïðåäåëåíèå. Íàçîâåì èíòåðïîëÿöèîííûì ïîëèíîìîì Ýðìèòà ïîëèíîì:Hn (x) =m aXk −1Xck,i (x)f (i) (xk ),(1)k=0 i=0ãäåck,i (x)- ïîëèíîìn-éñòåïåíè, êîýôôèöèåíòû êîòîðîãî íàõîäÿòñÿèç óñëîâèÿ:Hn(i) (xk ) = F (i) (xk ), k = 0, n, i = 0, ak − 1Ñóùåñòâîâàíèå è åäèíñòâåííîñòü äàííîãî ïîëèíîìà î÷åâèäíû, ïåðåéäåì ñðàçó ê ïîñòðîåíèþHn (x). îáùåì ñëó÷àå âûðàæåíèå äëÿ ïîëèíî-ìà Ýðìèòà äîñòàòî÷íî ãðîìîçäêî, ïîýòîìó îãðàíè÷èìñÿ ðàññìîòðåíèåìêîíêðåòíîé çàäà÷è:ÏîñòðîèòüH3 (x) = c0 (x)f (x0 ) + c1 (x)f (x1 ) + c2 (x)f (x2 ) + b(x)f 0 (x1 ).Çàïèøåì óñëîâèÿ, ïðè êîòîðûõ äàííûé ïîëèíîì áóäåò èíòåðïîëÿöèîííûì:c0 (x0 ) = 1, c1 (x0 ) = 0, c2 (x0 ) = 0, b(x0 ) = 0,c0 (x1 ) = 0, c1 (x1 ) = 1, c2 (x1 ) = 0, b(x1 ) = 0,c0 (x2 ) = 0, c1 (x2 ) = 0, c2 (x2 ) = 1, b(x2 ) = 0,c00 (x1 ) = 0, c01 (x1 ) = 0, c02 (x1 ) = 0, b0 (x1 ) = 1.Áóäåì èñêàòüc0 (x)â âèäåk(x − x1 )2 (x − x2 ), kâûáèðàåì èç óñëîâèÿc0 (x0 ) = 1:1 = k(x0 − x1 )2 (x0 − x2 ) =⇒ c0 (x) =Àíàëîãè÷íî ïîëó÷àåì âûðàæåíèå äëÿc2 (x) =(x − x1 )2 (x − x2 )(x0 − x1 )2 (x0 − x2 )c2 (x):(x − x1 )2 (x − x0 )(x2 − x1 )2 (x2 − x0 )Èíòåðïîëèðîâàíèå ñ êðàòíûìè óçëàìè.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
