В.Б. Андреев - Численные методы (2 в 1). (2007) (1160465), страница 10
Текст из файла (страница 10)
. . , n − 1.−1Çàìåíîé ïåðåìåííîé èíòåãðèðîâàíèÿ x = −t ýòè óñëîâèÿ ïðèâîäÿòñÿ ê âèäóZ1ρ(t)Pn (−t)Pm (−t)dt = 0,−1m = 0, . . . , n − 1,72 7. ÎÐÒÎÃÎÍÀËÜÍÛÅ ÌÍÎÃÎ×ËÅÍÛò.å. Pm (−t) òîæå îðòîãîíàëüíûå ìíîãî÷ëåíû. Íî â ñèëó ëåììû 7.2 ëþáîé îðòîãîíàëüíûé ìíîãî÷ëåí îïðåäåëåí ñ òî÷íîñòüþ äî ìíîæèòåëÿ, è ïîýòîìóPn (−x) = cn Pn (x).Îòñþäà â ÷àñòíîñòè ñëåäóåò, ÷òî(−1)n an xn = cn an xn ,ò.å.
cn = (−1)n è ïîýòîìóPn (−x) = (−1)n Pn (x).Ëåììà äîêàçàíà.Òåîðåìà 7.1. Äëÿ ëþáûõ òðåõ ïîñëåäîâàòåëüíûõ îðòîãîíàëüíûõ ìíîãî÷ëåíîâ ñïðàâåäëèâà ðåêóððåíòíàÿ ôîðìóëà(7.5)αn Pn+1 (x) = (x − βn )Pn (x) − γn Pn−1 (x).Äîêàçàòåëüñòâî. Ïåðåïèøåì (7.5) â âèäåxPn (x) = αn Pn+1 (x) + βn Pn (x) + γn Pn−1 (x). ëåâîé ÷àñòè ýòîãî ðàâåíñòâà ñòîèò ìíîãî÷ëåí ñòåïåíè n + 1.  ñèëó ëåììû 7.1 îíìîæåò áûòü ðàçëîæåí ïî ìíîãî÷ëåíàì P0 , . . .
, Pn+1xPn (x) =n+1X(n+1)ck(7.6)Pk (x),k=0ãäå â ñèëó çàìå÷àíèÿ 7.1(n+1)ck=( xPn , Pk ).kPk k2Íî òîãäà ñ ó÷åòîì (7.6)(n+1)ck11=(P,xP)=nkkPk k2kPk k2=1kPk k2k+1X(k+1)cjÃPn ,(7.7)k+1X!(k+1)cjPj=j=0( Pn , Pj ) .j=0Îòñþäà ñëåäóåò, ÷òî åñëè k + 1 < n, òî(n+1)ckè ïîýòîìó= 0,k+1<n(n+1)(n+1)xPn (x) = cn+1 Pn+1 (x) + cn(n+1) Pn (x) + cn−1 Pn−1 (x),ò.å.(n+1)αn = cn+1 ,Òåîðåìà äîêàçàíà.βn = cn(n+1) ,(n+1)γn = cn−1 .(7.8)(7.9)7.2. ÌÍÎÃÎ×ËÅÍÛ ×ÅÁÛØÅÂÀ ÏÅÐÂÎÃÎ ÐÎÄÀ73Òåîðåìà 7.2. Âñå íóëè îðòîãîíàëüíîãî ìíîãî÷ëåíà Pn (x) äåéñòâèòåëüíû, ðàçëè÷íûè ðàñïîëîæåíû íà èíòåðâàëå (−1, 1).Äîêàçàòåëüñòâî.
Äîñòàòî÷íî ïîêàçàòü, ÷òî ìíîãî÷ëåí Pn (x) íà (−1, 1) ìåíÿåòçíàê n ðàç. Äîïóñòèì ïðîòèâíîå, ò.å. ÷òî ìíîãî÷ëåí Pn (x) ìåíÿåò çíàê òîëüêî â òî÷êàõξ1 , ξ2 , . . . , ξm , ãäå m < n. Òîãäà ìíîãî÷ëåíQm (x) = (x − ξ1 )(x − ξ2 ) . . . (x − ξm )òàêæå ìåíÿåò çíàê òî÷íî â ýòèõ æå ñàìûõ òî÷êàõ. Ñëåäîâàòåëüíî, ïðîèçâåäåíèåPn (x)Qm (x) 6≡ 0 ñîõðàíÿåò çíàê íà (−1, 1) è ñëåäîâàòåëüíîZ1ρ(x)Pn (x)Qm (x)dx 6= 0,−1÷òî ïðîòèâîðå÷èò ëåììå 7.3.
Ïðîòèâîðå÷èå ñíèìàåòñÿ, åñëè n = m. Òåîðåìà äîêàçàíà.Çàìå÷àíèå 7.2.  ñèëó äîêàçàííîé òåîðåìû äëÿ íóëåé x(n)îðòîãîíàëüíîãî ìíîãîk÷ëåíà Pn (x) èìåþò ìåñòî íåðàâåíñòâà(n)(n)(n)−1 < x1 < x2 < · · · < xk < · · · < x(n)n < 1.(7.10)7.2 Ìíîãî÷ëåíû ×åáûøåâà ïåðâîãî ðîäàÐàññìîòðèì ñëåäóþùåå îäíîðîäíîå ðàçíîñòíîå óðàâíåíèå âòîðîãî ïîðÿäêà ñ ïîñòîÿííûìè êîýôôèöèåíòàìèyn − 2xyn−1 + yn−2 = 0.(7.11)Çäåñü x ïàðàìåòð. Ïîñòàâèì äëÿ (7.11) íà÷àëüíûå óñëîâèÿy0 = 1,Òîãäày1 = x.y2 = 2x · x − 1 = 2x2 − 1,y3 = 2x(2x2 − 1) − x = 4x3 − 3x,y4 = 8x4 − 8x2 + 1, . .
. .(7.12)(7.13)Î÷åâèäíî, ÷òî çíà÷åíèå ðåøåíèÿ çàäà÷è (7.11), (7.12) â óçëå n åñòü ìíîãî÷ëåí îò xñòåïåíè n.Íàéäåì ðåøåíèå çàäà÷è (7.11), (7.12) â ÿâíîì âèäå. Õàðàêòåðèñòè÷åñêîå óðàâíåíèåðàçíîñòíîãî óðàâíåíèÿ (7.11) èìååò âèäq 2 − 2xq + 1 = 0,74 7. ÎÐÒÎÃÎÍÀËÜÍÛÅ ÌÍÎÃÎ×ËÅÍÛà åãî êîðíè ñóòüq1 = q = x +√x2 − 1 è q2 = 1/q.(7.14)Ïîýòîìó îáùåå ðåøåíèå óðàâíåíèÿ (7.11) åñòüyn = c1 q n + c2 q −n .Ïîëàãàÿ çäåñü n = 0 è n = 1 è ïðèíèìàÿ âî âíèìàíèå íà÷àëüíûå óñëîâèÿ (7.12),íàõîäèì, ÷òîy0 = c1 + c2 = 1,(7.15)y1 = c1 q + c2 q −1 = x.Ïðåîáðàçåì âòîðîå èç óðàâíåíèé (7.15) ñ ó÷åòîì (7.14) è ïåðâîãî óðàâíåíèÿ,√√y1 = c1 (x + x2 − 1) + c2 (x − x2 − 1) =√√= (c1 + c2 )x + (c1 − c2 ) x2 − 1 = x + (c1 − c2 ) x2 − 1 = x.Îòñþäà ñëåäóåò, ÷òî c1 = c2 , à ñ ó÷åòîì (7.15) íàõîäèì, ÷òîc1 = c2 = 1/2,è ïîýòîìóyn =q n + q −n2(7.16)åñòü ðåøåíèå çàäà÷è (7.11), (7.12).Êàê áûëî çàìå÷åíî ðàíüøå, ýòî åñòü ìíîãî÷ëåí îò x ñòåïåíè n.
Ïóñòü |x| < 1.Òîãäà â ñèëó (7.14)√q = x + i 1 − x2è, ñëåäîâàòåëüíî, |q| = 1. Ïóñòü q = eiϕ . Òîãäàx = cos ϕ, ϕ = arccos x,einϕ + e−inϕyn == cos nϕ = cos[n arccos x].2(7.17)Îïðåäåëåíèå 7.1. Àëãåáðàè÷åñêèå ìíîãî÷ëåíûTn (x) = cos[n arccos x],|x| < 1,n = 0, 1, . . .(7.18)íàçûâàþòñÿ ìíîãî÷ëåíàìè ×åáûøåâà ïåðâîãî ðîäà.Îíè ïðèíàäëåæàò ê ñåìåéñòâó îðòîãîíàëüíûõ ìíîãî÷ëåíîâ.
Îïðåäåëèì âåñîâóþôóíêöèþ ρ(x), ïðè êîòîðîé ìíîãî÷ëåíû Tn (x) áóäóò îðòîãîíàëüíûìè. Èç (7.17) ñëåäóåò, ÷òîdx, x = 1 ïðè ϕ = 0 è x = −1 ïðè ϕ = π.dϕ = − √1 − x27.3. ÑÂÎÉÑÒÂÀ ÌÍÎÃÎ×ËÅÍΠ×ÅÁÛØÅÂÀ75Ïðèíèìàÿ òåïåðü âî âíèìàíèå (7.18), íàõîäèì, ÷òî ïðè m 6= nZπ0=Z10Òåì ñàìûì√cos mϕ cos nϕ dϕ =−11Tm (x)Tn (x)dx.1 − x2ρ(x) = (1 − x2 )−1/2 .(7.19)7.3 Ñâîéñòâà ìíîãî÷ëåíîâ ×åáûøåâà1◦ . Ïðè ÷åòíîì n ìíîãî÷ëåí Tn (x) ÿâëÿåòñÿ ÷åòíîé ôóíêöèåé x, à ïðè íå÷åòíîì n íå÷åòíîé.Äîêàçàòåëüñòâî ñëåäóåò èç (7.19) è ëåììû 7.4.◦2 . Êîýôôèöèåíò ïðè ñòàðøåé ñòåïåíè ìíîãî÷ëåíà Tn (x) äëÿ n > 1 ðàâåí 2n−1 , ò.å.µn = 2n−1 , àTn (x) = 2n−1 xn + . . .
.Äîêàçàòåëüñòâî. Ñì. ðåêóððåíòíóþ ôîðìóëó (7.11).3 . Íóëè ìíîãî÷ëåíà Tn (x) ðàñïîëîæåíû â òî÷êàõ◦xk = − cos(2k − 1)π,2nk = 1, 2, . . . , n.(7.20)Äîêàçàòåëüñòâî. Èç (7.18) íàõîäèì, ÷òîn arccos xk = −π(2k − 1)π+ kπ =22èëèarccos xk =ò.å.(2k − 1)π,2n(2k − 1)π, k = 1, n.2nÒàê êàê ôóíêöèè Tn (x) ÿâëÿþòñÿ ëèáî ÷åòíûìè, ëèáî íå÷åòíûìè, òî íóëè Tn (x)ðàñïîëîæåíû ñèììåòðè÷íî îòíîñèòåëüíî íà÷àëà êîîðäèíàòxk = cosxn+1−k = −xk = − cos(2k − 1)π.2nÏåðåíóìåðîâûâàÿ íóëè â îáðàòíîì ïîðÿäêå, ïðèõîäèì ê (7.20).4◦ . max |Tn (x)| = 1, ïðè÷åì[−1,1]Tn (xm ) = (−1)m ,76 7. ÎÐÒÎÃÎÍÀËÜÍÛÅ ÌÍÎÃÎ×ËÅÍÛãäåxm = − cosmπ,n(7.21)m = 0, .
. . , n.Äîêàçàòåëüñòâî î÷åâèäíî.5 . Ñðåäè âñåõ ìíîãî÷ëåíîâ ñòåïåíè n ñ åäèíè÷íûì êîýôôèöèåíòîì ïðè ñòàðøåéñòåïåíè ìíîãî÷ëåí1T n (x) = n−1 Tn (x), n > 12íà [−1, 1] èìååò íàèìåíüøåå çíà÷åíèå ìàêñèìóìà ìîäóëÿ.Äîêàçàòåëüñòâî. Äîïóñòèì ïðîòèâíîå, ò.å. äîïóñòèì ñóùåñòâîâàíèå òàêîãî ìíîãî÷ëåíà P n (x) = xn + . . . , ÷òî◦(7.22)max |P n (x)| < max |T n (x)|.[−1,1][−1,1]Òîãäà T n (x) − P n (x) 6≡ 0 è ýòî åñòü ìíîãî÷ëåí ñòåïåíè íå âûøå (n − 1). Áîëååòîãî, â (n + 1) òî÷êå (7.21) ýòîò ìíîãî÷ëåí ïðèíèìàåò îòëè÷íûå îò íóëÿ çíà÷åíèÿñ ÷åðåäóþùèìèñÿ çíàêàìè.TPn−1×xm−1×xm×xm+1Ðèñ.
1Íî ýòî îçíà÷àåò, ÷òî àëãåáðàè÷åñêèé ìíîãî÷ëåí T n (x) − P n (x) ñòåïåíè ìåíüøåé nîáðàùàåòñÿ â íóëü ïî êðàéíåé ìåðå â n òî÷êàõ, ÷òî íåâîçìîæíî.Çàìå÷àíèå 7.3. Ìîæíî äîêàçàòü, ÷òî åñëè P n (x) = xn + . . . ,max |P n (x)| = 2−n+1 ,[−1,1]òî P n (x) ≡ T n (x) = 2−n−1 Tn (x).n > 1, è7.4. ÌÍÎÃÎ×ËÅÍÛ ËÅÆÀÍÄÐÀ77Áëàãîäàðÿ ñâîéñòâó 5◦ ìíîãî÷ëåíû ×åáûøåâà Tn (x) íàçûâàþòñÿ ìíîãî÷ëåíàìè,íàèìåíåå óêëîíÿþùèìèñÿ îò íóëÿ.6◦ . Åñëè x > 1, òîTn (x) = ch n Arch x,ãäåArch x = ln(x +√x2 − 1).Äîêàçàòåëüñòâî.
 ñèëó (7.16)√q n + q −nen ln q + e−n ln qTn (x) === ch n ln q = ch n ln(x + x2 − 1).22Çàìå÷àíèå 7.4. Arch x îáðàòíàÿ ôóíêöèÿ ê ch x.Óïðàæíåíèå 7.1. Äîêàçàòü, ÷òîch Arch x = x,Arch ch x = x.7.4 Ìíîãî÷ëåíû ËåæàíäðàÌíîãî÷ëåíàìè Ëåæàíäðà íàçûâàþòñÿ ìíîãî÷ëåíû, êîòîðûå îðòîãîíàëüíû äðóã äðóãóíà [−1, 1] ñ âåñîì ρ ≡ 1. Îáîçíà÷àþòñÿ îíè ÷åðåç Pn (x)Z1Pm (x)Pn (x)dx = 0,m 6= n.−1Åñëè P0 (x) ≡ 1, òî P1 (x) ≡ x.Òðåõòî÷å÷íîå ðåêóððåíòíîå ñîîòíîøåíèå äëÿ ìíîãî÷ëåíîâ Ëåæàíäðà èìååò âèä(n + 1)Pn+1 (x) − (2n + 1)xPn (x) + nPn−1 (x) = 0è ñëåäîâàòåëüíîè ò.ä.11P2 (x) = (3x2 − 1), P3 (x) = (5x3 − 3x),221P4 (x) = (35x4 − 30x2 + 3),81P5 (x) = (63x5 − 70x3 + 15x)878 7.
ÎÐÒÎÃÎÍÀËÜÍÛÅ ÌÍÎÃÎ×ËÅÍÛ 8Èòåðàöèîííûå ìåòîäû ïðåäûäóùèõ ëåêöèÿõ äëÿ ñèñòåìû ëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèéAx = b(8.1)ñ êâàäðàòíîé íåâûðîæäåííîé ìàòðèöåé áûëè ðàññìîòðåíû ÷åòûðå ïðÿìûõ ìåòîäàîòûñêàíèÿ ðåøåíèÿ:à) ìåòîä Ãàóññà (LU -ðàçëîæåíèå, òðåóãîëüíîå ðàçëîæåíèå) è åãî ìîäèôèêàöèÿ ñâûáîðîì âåäóùåãî ýëåìåíòà,á) ìåòîä Õîëåöêîãî, ïðèìåíÿåìûé â ñëó÷àå ñèììåòðè÷íîé ïîëîæèòåëüíî îïðåäåëåííîé ìàòðèöû,â) ìåòîä âðàùåíèé,ã) ìåòîä îòðàæåíèé.Âñå ýòè ìåòîäû ïîçâîëÿþò â ïðèíöèïå (ïðè îòñóòñòâèè îøèáîê îêðóãëåíèÿ) íàéòèòî÷íîå ðåøåíèå çà êîíå÷íîå ÷èñëî äåéñòâèé.
Ýòî ÷èñëî äåéñòâèé áûëî îöåíåíî íàìèâåëè÷èíîé O(n3 ), ãäå n ïîðÿäîê ñèñòåìû. Åñëè ìàòðèöà A ñèñòåìû èìååò ëåíòî÷íóþñòðóêòóðó ñ ïîëóøèðèíîé ëåíòû p ìíîãî ìåíüøåé n, òî ëåíòî÷íûå âàðèàíòû ïåðâûõäâóõ ìåòîäîâ ïîçâîëÿþò íàéòè òî÷íîå ðåøåíèå ñ ìåíüøåé, ÷åì O(n3 ), çàòðàòîé äåéñòâèé. ýòîé ëåêöèè ìû ðàññìîòðèì äðóãîé êëàññ ìåòîäîâ ðåøåíèÿ ñèñòåìû (8.1) èòåðàöèîííûõ. Ýòè ìåòîäû, êàê ïðàâèëî, åñëè è ïîçâîëÿþò íàéòè òî÷íîå ðåøåíèåñèñòåìû (8.1), òî òîëüêî êàê ïðåäåë ïðè ñòðåìëåíèè ÷èñëà èòåðàöèé (à, ñëåäîâàòåëüíî,è äåéñòâèé) ê áåñêîíå÷íîñòè. Îäíàêî äëÿ øèðîêîãî êëàññà çàäà÷, âñòðå÷àþùèõñÿ âïðèëîæåíèÿõ, òå èëè èíûå èòåðàöèîííûå ìåòîäû ìîãóò îêàçàòüñÿ ïðåäïî÷òèòåëüíååñ òî÷êè çðåíèÿ èñïîëüçóåìûõ òðóäîçàòðàò, ÷åì îïèñàííûå ïðÿìûå.7980 8. ÈÒÅÐÀÖÈÎÍÍÛÅ ÌÅÒÎÄÛ8.1 Îäíîøàãîâûå èòåðàöèîííûå ìåòîäûÈç êóðñà "Ââåäåíèå â ÷èñëåííûå ìåòîäû" èçâåñòíî, ÷òî ìíîãèå îäíîøàãîâûå èòåðàöèîííûå ìåòîäû ìîãóò áûòü çàïèñàíû â òàê íàçûâàåìîé êàíîíè÷åñêîé ôîðìåBxk+1 − xk+ Axk = b,τk = 0, 1, .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
