В.Б. Андреев - Численные методы, страница 10

Êîýôôèöèåíò ïðè ñòàðøåé ñòåïåíè ìíîãî÷ëåíà 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, . . . ,(8.2)ãäå B íåêîòîðàÿ ìàòðèöà, îïðåäåëÿþùàÿ èòåðàöèîííûé ìåòîä, à τ èòåðàöèîííûéïàðàìåòð.  ÷àñòíîñòè, â âèäå (8.2) ìîãóò áûòü çàïèñàíû ìåòîä ßêîáè, ìåòîä ÃàóññàÇåéäåëÿ, ìåòîä ïîñëåäîâàòåëüíîé âåðõíåé ðåëàêñàöèè, ìåòîä ïðîñòûõ èòåðàöèé. Ïðåäïîëîæèì, ÷òîA = AT > 0,B = B T > 0.(8.3)Ïðè ýòèõ ïðåäïîëîæåíèÿõ â êóðñå "Ââåäåíèå â ÷èñëåííûå ìåòîäû"äîêàçàíî, ÷òî åñëèB>τA,2(8.4)ò.å.

åñëè äëÿ ëþáîãî íåíóëåâîãî âåêòîðà x ñïðàâåäëèâî( Bx , x ) > τ2 ( Ax , x ), òî èòåðàöèîííûé ìåòîä (8.2) ÿâëÿåòñÿ ñõîäÿùèìñÿ.Äëÿ ìåòîäà ïðîñòûõ èòåðàöèé, êîòîðûé èìååò âèä (8.2) ñB = I , êðîìå òîãî, äàíà è îöåíêà ñêîðîñòè ñõîäèìîñòè. Èìåííî, åñëè(8.5)τ = 2/(λ1 + λn ),ãäå λ1 è λn , ñîîòâåòñòâåííî, íàèìåíüøåå è íàèáîëüøåå ñîáñòâåííûå çíà÷åíèÿ ìàòðèöûA, òî äëÿ ïîãðåøíîñòè èòåðàöèé ñïðàâåäëèâà îöåíêà°°°°° x − xk °6 q ° x − xk−1 °,q=λn − λ11 − λ1 /λn=< 1,λn + λ11 + λ1 /λn(8.6)ãäå k · k åâêëèäîâà äëèíà.Èç (8.6) ñëåäóåò, ÷òî åñëè λn À λ1 , òî ÷èñëî q î÷åíü áëèçêî ê åäèíèöå, à ñêîðîñòüñõîäèìîñòè èòåðàöèé î÷åíü íèçêàÿ. Íî ïðè óêàçàííîì âûáîðå íîðìû âåêòîðàkAk = max λi (A) = λn ,ikA−1 k = max λi (A−1 ) = λ−11ièλn /λ1 = kAk kA−1 k = cond A := κ(A) := κ.Òàêèì îáðàçîì, åñëè ìàòðèöà A ïëîõî îáóñëîâëåíà, à ýòî òèïè÷íàÿ ñèòóàöèÿ, òî ìåòîäïðîñòûõ èòåðàöèé áóäåò ñõîäèòüñÿ î÷åíü ìåäëåííî.8.2.

ÍÅßÂÍÛÅ ÌÅÒÎÄÛ818.2 Íåÿâíûå ìåòîäûÊàêèå åñòü ïóòè óâåëè÷åíèÿ ñêîðîñòè ñõîäèìîñòè èòåðàöèîííûõ ìåòîäîâ? Èçó÷èìâëèÿíèå ìàòðèöû B èç (8.2) íà ñêîðîñòü ñõîäèìîñòè.  ñèëó (8.3) ñóùåñòâóåò ìàòðèöàB 1/2 òàêàÿ, ÷òî¡¢TB 1/2 = B 1/2 > 0 è B 1/2 B 1/2 = B.Ýòà ìàòðèöà íàçûâàåòñÿ êâàäðàòíûì êîðíåì èç ìàòðèöû B .Íàïîìíèì ïîñòðîåíèå ìàòðèöû B 1/2 . Ïóñòü λ ñîáñòâåííîå çíà÷åíèå ìàòðèöû B , à ξ îòâå÷àþùèé åìó ñîáñòâåííûé âåêòîð, ò.å. Bξ = λξ . Ïåðåíóìåðóåì âñå ñîáñòâåííûå çíà÷åíèÿ ìàòðèöû B è ââåäåì â ðàññìîòðåíèå äèàãîíàëüíóþ ìàòðèöó Λ = diag (λ1 , λ2 , . .

. , λn ),îáðàçîâàííóþ ýòèìè ñîáñòâåííûìè çíà÷åíèÿìè, è îðòîãîíàëüíóþ ìàòðèöó Ξ = [ξ1 ξ2 . . . ξn ],îáðàçîâàííóþ îðòîíîðìèðîâàííûìè ñîáñòâåííûìè âåêòîðàìè ξi ìàòðèöû B , óïîðÿäî÷åííûìè â ñîîòâåòñòâèè ñ íóìåðàöèåé ñîáñòâåííûõ çíà÷åíèé. Ïîñêîëüêó ΞΛ = [λ1 ξ1 λ2 ξ2 . . . λn ξn ],òî BΞ = ΞΛ. Îòñþäà ñëåäóåò, ÷òî B = ΞΛΞT .√ √√Î÷åâèäíî, ÷òî ìàòðèöà Λ1/2 = diag ( λ1 , λ2 , . .

. , λn ). Ïîýòîìó B 1/2 = ΞΛ1/2 ΞT .Ââåäåì îáîçíà÷åíèåB 1/2 xk = y k ,¡¢−1xk = B 1/2 y k = B −1/2 y k .(8.7)Òîãäà (8.2) ìîæíî ïåðåïèñàòü òàêB 1/2y k+1 − y k+ AB −1/2 y k = b,τà ïîñëå ïðèìåíåíèÿ ê ýòîìó ñîîòíîøåíèþ ìàòðèöû B −1/2 , ïîëó÷èìy k+1 − y k+ B −1/2 AB −1/2 y k = B −1/2 b =: f.τ(8.8)B −1/2 AB −1/2 = C,(8.9)Îáîçíà÷àÿáóäåì èìåòü ñîîòíîøåíèÿy k+1 − y k+ Cy k = f,τk = 0, 1, . . . ,(8.10)êîòîðûå ïî ôîðìå ïîëíîñòüþ ñîâïàäàþò ñ (8.2). Î÷åâèäíî, ÷òî C = C T > 0, è ïîýòîìóäëÿ èòåðàöèîííîãî ìåòîäà (8.10) (à ýòî åñòü ìåòîä ïðîñòûõ èòåðàöèé) ïðèτ=2λ1 (C) + λn (C)(8.11)ñïðàâåäëèâà îöåíêà° k+1°°°°y− y °6 q(C) ° y k − y °,q(C) =λn (C) − λ1 (C)< 1,λn (C) + λ1 (C)(8.12)82Ÿ 8.

ÈÒÅÐÀÖÈÎÍÍÛÅ ÌÅÒÎÄÛãäå λ1 (C) è λn (C) ñîîòâåòñòâåííî ìèíèìàëüíîå è ìàêñèìàëüíîå ñîáñòâåííûå çíà÷åíèÿ ìàòðèöû C :Cξ = λ(C)ξ.(8.13)Çäåñü ξ ñîáñòâåííûå âåêòîðû ìàòðèöû C . Ïîäñòàâëÿÿ â (8.13) ïðåäñòàâëåíèå C èç(8.9), ïîëó÷èìB −1/2 AB −1/2 ξ = λ(C)ξ,à, îáîçíà÷àÿB −1/2 ξ = η,ξ = B 1/2 ηè ïðèìåíÿÿ ê ïîñëåäíåé çàäà÷å ìàòðèöó B 1/2 , áóäåì èìåòü(8.14)Aη = λ(C)Bη.Òàêèì îáðàçîì, λ1 (C) è λn (C) ñóòü ìèíèìàëüíîå è ìàêñèìàëüíîå ñîáñòâåííûå çíà÷åíèÿ îáîáùåííîé çàäà÷è íà ñîáñòâåííûå çíà÷åíèÿ (8.14).Ïîäñòàâëÿÿ â (8.12) y k èç (8.7) è îáîçíà÷àÿ ( Bx , x ) = kxk2B , ïîëó÷èì° k°°°° x − x ° 6 q(C) ° xk−1 − x ° .BBÈòàê, åñëè B = B T > 0 òàêîâà, ÷òîλn /λ1 > λn (C)/λ1 (C),òî èòåðàöèîííûé ìåòîä (8.2), (8.11) ñ ýòîé ìàòðèöåé B áóäåò ñõîäèòüñÿ áûñòðåå (âñìûñëå B -íîðìû), ÷åì ìåòîä ïðîñòûõ èòåðàöèé. Íàèáîëüøóþ ñêîðîñòü ñõîäèìîñòèìû ïîëó÷èì, âûáèðàÿ B = A.

ÒîãäàC = I,è (8.2) ïðèíèìàåò âèäλ1 (C) = λn (C) = 1,τ =1Axk = b,÷òî ñ òî÷íîñòüþ äî îáîçíà÷åíèé ñîâïàäàåò ñ (8.1). Ìåòîä ñõîäèòñÿ çà îäíó èòåðàöèþ.Ëó÷øåãî áûòü íå ìîæåò. Íî ìû ïðèøëè ê òîìó, îò ÷åãî õîòåëè óéòè: íàì ñíîâà íóæíîðåøàòü ñèñòåìó (8.1). Îòñþäà ñëåäóåò, ÷òî íà âûáîð ìàòðèöû B íóæíî íàëîæèòüâåñüìà ñåðüåçíûå îãðàíè÷åíèÿ ìàòðèöà B äîëæíà áûòü îòíîñèòåëüíî ëåãêî îáðàòèìà. Òàêîâûìè, íàïðèìåð, ÿâëÿþòñÿ äèàãîíàëüíûå è òðåóãîëüíûå ìàòðèöû. Õîòÿïîñëåäíèå è íå ÿâëÿþòñÿ ñèììåòðè÷íûìè, ýòî íåóäîáñòâî ëåãêî óñòðàíèòü, âûáèðàÿ â êà÷åñòâå B ïîäõîäÿùåå ïðîèçâåäåíèå òðåóãîëüíûõ ìàòðèö.

Îäíàêî ñêîðîñòüñõîäèìîñòè ìåòîäà (8.2) ïðè òàêîì âûáîðå B èç î÷åâèäíûõ ñîîáðàæåíèé îñòàåòñÿñðàâíèòåëüíî íèçêîé. íàñòîÿùåå âðåìÿ íåèçâåñòíî ðåãóëÿðíûõ ñïîñîáîâ õîðîøåãî âûáîðà ìàòðèöûB äëÿ ïðîèçâîëüíîé A. Âñå óäà÷íûå íàõîäêè òàê èëè èíà÷å ñâÿçàíû ñî ñïåöèôèêîéìàòðèöû A.8.3. ÍÅÑÒÀÖÈÎÍÀÐÍÛÅ ÈÒÅÐÀÖÈÎÍÍÛÅ ÌÅÒÎÄÛ838.3 Íåñòàöèîíàðíûå èòåðàöèîííûå ìåòîäûÄðóãîé ïóòü óâåëè÷åíèÿ ñêîðîñòè ñõîäèìîñòè èòåðàöèîííîãî ìåòîäà (8.2) ñîñòîèòâ òîì, ÷òîáû âìåñòî îäíîãî èòåðàöèîííîãî ïàðàìåòðà τ èñïîëüçîâàòü íåñêîëüêî ñâîé èòåðàöèîííûé ïàðàìåòð íà êàæäîé èòåðàöèè. Èòåðàöèîííûå ìåòîäû òàêîãî òèïàíàçûâàþòñÿ íåñòàöèîíàðíûìè è èìåþò âèäBxk+1 − xk+ Axk = b,τk+1k = 0, 1, .

. .(8.15)k = 0, 1, . . . .(8.16)èëè ñ ó÷åòîì (8.7), (8.10)y k+1 − y k+ Cy k = f,τk+1Óêàæåì îäèí èç âîçìîæíûõ ñïîñîáîâ âûáîðà èòåðàöèîííûõ ïàðàìåòðîâ τk . Ââåäåìîáîçíà÷åíèåz k = y k − y,ãäå(8.17)Cy = f,è âû÷òåì (8.17) èç (8.16).  ðåçóëüòàòå ïîëó÷èì çàäà÷ó äëÿ z k :z k+1 − z k+ Cz k = 0,τk+1Îòñþäàk = 0, 1, . . . ,z 0 = y 0 − y.(8.18)z k+1 = (I − τk+1 C)z k ,è, ñëåäîâàòåëüíî,kz =kY(I − τj C)z 0 ,(8.19)j=1ò.å.z k = Pk (C)z 0 ,ãäåPk (t) =kY(k)(k)(1 − τj t) = 1 + a1 t + · · · + ak tk .(8.20)j=1Èç (8.19) íàõîäèì, ÷òî°° k° ° k°°Y° °Y0° 6 ° (I − τj C)° kz 0 k.(I−τC)zkz k = ky − yk = °j°°° °kkj=1j=1(8.21)84Ÿ 8.