Буслов, Яковлев - Численные методы. 2. Решение уравнений (947496)
Текст из файла
ÑÀÍÊÒÏÅÒÅÐÁÓÐÃÑÊÈÉ ÃÎÑÓÄÀÐÑÒÂÅÍÍÛÉ ÓÍÈÂÅÐÑÈÒÅÒÔÈÇÈ×ÅÑÊÈÉ ÔÀÊÓËÜÒÅÒÊÀÔÅÄÐÀ ÂÛ×ÈÑËÈÒÅËÜÍÎÉ ÔÈÇÈÊÈÂ.À.ÁÓÑËΠ,Ñ.Ë.ßÊÎÂËÅÂ×ÈÑËÅÍÍÛÅ ÌÅÒÎÄÛ II.ÐÅØÅÍÈÅ ÓÐÀÂÍÅÍÈÉÊÓÐÑ ËÅÊÖÈÉÑÀÍÊÒÏÅÒÅÐÁÓÐÃ2001Óòâåðæäåíî íà çàñåäàíèè êàôåäðûâû÷èñëèòåëüíîé ôèçèêèïå÷àòàåòñÿ ïî ðåøåíèþ ìåòîäè÷åñêîé êîìèññèèôèçè÷åñêîãî ôàêóëüòåòà ÑÏáÃÓÀ Â Ò Î Ð Û : Â.À.ÁÓÑËÎÂ, Ñ.Ë.ßÊÎÂËÅÂÐ Å Ö Å Í Ç Å Í Ò : äîêò. ôèç.-ìàò. íàóê Ñ.Þ.ÑËÀÂßÍÎÂÍàñòîÿùåå èçäàíèå ÿâëÿåòñÿ âòîðîé ÷àñòüþ êóðñà ëåêöèé ïî ÷èñëåííûì ìåòîäàì, ÷èòàâøèõñÿ íà ïðîòÿæåíèè ðÿäà ëåò àâòîðàìè â ïåðâîì ñåìåñòðå II êóðñà ôèçè÷åñêîãî ôàêóëüòåòà ÑÏáÃÓ. ïîñîáèè ïðèíÿòà íóìåðàöèÿ ôîðìóë ïî ãëàâàì.
Ïðèâåäåííàÿ áèáëèîãðàôèÿ ÷àñòè÷íî ïðåäñòàâëÿåòñîáîé èñòî÷íèê ñïðàâî÷íîãî ìàòåðèàëà, íî, â îñíîâíîì, ðàññ÷èòàíà íà äàëüíåéøåå èçó÷åíèå ÷èñëåííûõìåòîäîâ.2Ãëàâà 1Ñèñòåìû óðàâíåíèé1.1 Ðåøåíèå íåëèíåéíûõ óðàâíåíèéÇàäà÷ó íàõîæäåíèÿ ðåøåíèé óðàâíåíèé ìîæíî ôîðìóëèðîâàòü ðàçëè÷íûìè ñïîñîáàìè. Íàïðèìåð, êàêçàäà÷ó íà íàõîæäåíèå êîðíåé: f (x) = 0, èëè êàê çàäà÷ó íà íàõîæäåíèå íåïîäâèæíîé òî÷êè: F (x) = x. Ïðèýòîì, â çàâèñèìîñòè îò ôîðìóëèðîâêè çàäà÷è, óäîáíî ïðèìåíÿòü òå èëè èíûå ñïîñîáû ðåøåíèÿ. Ðàññìîòðèìñíà÷àëà îäíîìåðíóþ ñèòóàöèþ.1.1.1 Îäíîìåðíûé ñëó÷àéÌåòîä äåëåíèÿ ïîïîëàìÏðîñòåéøèì ìåòîäîì íàõîæäåíèÿ êîðíåé óðàâíåíèÿ f (x) = 0 ÿâëÿåòñÿ ìåòîä äåëåíèÿ ïîïîëàì èëèäèõîòîìèÿ.
Ïðåäïîëîæèì, ìû íàøëè äâå òî÷êè x0 è x1 , òàêèå ÷òî f (x0 ) è f (x1 ) èìåþò ðàçíûåçíàêè, òîãäà ìåæäó ýòèìè òî÷êàìè, åñëè f ∈ C 0 , íàõîäèòñÿ õîòÿ áû îäèí êîðåíü ôóíêöèè f . Ïîäåëèìîòðåçîê [x0 , x1 ] ïîïîëàì è ââåäåì òî÷êó x2 =x0 +x1.2Ëèáî f (x2 )f (x0 ) ≤ 0, ëèáî f (x2 )f (1 ) ≤ 0. Îñòàâèìòó ïîëîâèíó îòðåçêà, äëÿ êîòîðîé çíà÷åíèÿ íà êîíöàõ èìåþò ðàçíûå çíàêè. Òåïåðü ýòîò îòðåçîê äåëèìïîïîëàì è îñòàâëÿåì òó åãî ÷àñòü, íà ãðàíèöàõ êîòîðîé ôóíêöèÿ èìååò ðàçíûå çíàêè, è òàê äàëåå, äîäîñòèæåíèÿ òðåáóåìîé òî÷íîñòè.Ê äîñòîèíñòâàì ìåòîäà äåëåíèÿ ïîïîëàì ñëåäóåò îòíåñòè åãî âûñîêóþ íàäåæíîñòü è ïðîñòîòó, ïðèýòîì îò ôóíêöèè òðåáóåòñÿ òîëüêî íåïðåðûâíîñòü. Ïîðÿäîê ñõîäèìîñòè ìåòîäà ëèíåéíûé, íà êàæäîì øàãåòî÷íîñòü âîçðàñòàåò âäâîå.Íåäîñòàòêîì ìåòîäà ÿâëÿåòñÿ òîò ôàêò, ÷òî ïðåæäå ÷åì íà÷àòü åãî ïðèìåíåíèå, íåîáõîäèìî ïðåäâàðèòåëüíî íàéòè äâå òî÷êè, çíà÷åíèÿ ôóíêöèè â êîòîðûõ èìåþò ðàçíûå çíàêè.
Î÷åâèäíî, ÷òî ìåòîä íåïðèìåíèì äëÿ êîðíåé ÷åòíîé êðàòíîñòè. Îí òàêæå íå ìîæåò áûòü îáîáùåí íà ñëó÷àé êîìïëåêñíûõ êîðíåé è íàñèñòåìû óðàâíåíèé.Ìåòîä ïðîñòûõ èòåðàöèéÏóñòü F : [a, b] → [a, b] è F ñæàòèå: |F (x) − F (y)| ≤ q|x − y| , q < 1 (â ÷àñòíîñòè, òîò ôàêò, ÷òîF ñæàòèå, êàê ëåãêî âèäåòü, îçíà÷àåò, ÷òî F ∈ C[a,b] ). Ïî òåîðåìå Áàíàõà ñóùåñòâóåò è åäèíñòâåííà3íåïîäâèæíàÿ òî÷êà x∗ . Îíà ìîæåò áûòü íàéäåíà êàê ïðåäåë ïðîñòîé èòåðàöèîííîé ïðîöåäóðûx∗ = lim xn , xn+1 = F (xn ) ,n→∞ãäå íà÷àëüíîå ïðèáëèæåíèå x0 ïðîèçâîëüíàÿ òî÷êà ïðîìåæóòêà [a, b]. Åñëè ôóíêöèÿ F äèôôåðåíöèðóåìà,òî óäîáíûì êðèòåðèåì ñæàòèÿ ÿâëÿåòñÿ ÷èñëî q = sup |F 0 (x)| = ||F 0 ||C < 1. Äåéñòâèòåëüíî, ïî òåîðåìåx∈[a,b]Ëàãðàíæà|F (x) − F (y)| = |F 0 (ξ)||x − y| ≤ ||F 0 ||C |x − y| = q|x − y| .Òàêèì îáðàçîì, åñëè ïðîèçâîäíàÿ ìåíüøå åäèíèöû, òî F ÿâëÿåòñÿ ñæàòèåì.Óñëîâèå F ([a, b]) ⊆ [a, b] ñóùåñòâåííî, èáî åñëè, íàïðèìåð, F (x) ≡ 2 íà [0,1] , òî íåïîäâèæíàÿ òî÷êàîòñóòñòâóåò, õîòÿ ïðîèçâîäíàÿ ðàâíà íóëþ.
Ñêîðîñòü ñõîäèìîñòè çàâèñèò îò âåëè÷èíû q . ×åì ìåíüøå q ,òåì áûñòðåå ñõîäèìîñòü.Ïpèìåp. Ðåøèòü óðàâíåíèå: x2 = a. Çäåñü, åñëè â êà÷åñòâå Fîòâåòñòâóþùàÿ èòåðàöèîííàÿ ïðîöåäóðà áóäåò èìåòü âèä: xn+1 =âçÿòü ôóíêöèþ F (x) =axnax,òî ñî-. Êàê íåòðóäíî óáåäèòüñÿ, ìåòîäèòåðàöèé â äàííîì ñëó÷àå ðàñõîäèòñÿ ïðè ëþáîé íà÷àëüíîé òî÷êå x0 , íå ñîâïàäàþùåé ñ ñîáñòâåííî íåïî√äâèæíîé òî÷êîé x∗ = a. Îäíàêî ìîæíî â êà÷åñòâå F ïðåäëîæèòü è áîëåå õèòðóþ ôóíêöèþ ñ òîé æåíåïîäâèæíîé òî÷êîé. Ïóñòü F (x) = 21 [x + xa ].
Ñîîòâåòñòâóþùàÿ èòåðàöèîííàÿ ïðîöåäóðà çäåñü èìååò âèä:xn+1 =12 [xn+ax n ].Ýòè èòåðàöèè ñõîäÿòñÿ ê íåïîäâèæíîé òî÷êå äëÿ ëþáîãî íà÷àëüíîãî ïðèáëèæåíèÿx0 ∈ (0, ∞): F (x) = F (x) =ax,12 [xxn+1 =+ xa ] ,axn,xn+1 = 21 [xn +axn ], xn → x∗ .Äåéñòâèòåëüíî, â ïåðâîì ñëó÷àå F 0 (xn ) = − xa2 , ò.å. äëÿ âûïîëíåíèÿ óñëîâèÿ F 0 (xn ) < 1 íåîáõîäèìîn÷òîáû x2n > a, íî òîãäà |F 0 (xn+1 )| = | x2a | =n+1íå ÿâëÿåòñÿ.Äëÿ F (x) =12 [xaa2x2n=x2na> 1. Òàêèì îáðàçîì, îòîáðàæåíèå F (x) =axñæàòèåì+ xa ], ãäå íåïîäâèæíàÿ òî÷êà òà æå ñàìàÿ, ñèòóàöèÿ äðóãàÿ.
Çäåñü, õîòÿ ôîðìàëüíîïðîèçâîäíàÿ ìîæåò áûòü äîâîëüíî áîëüøîé (ïðè ìàëûõ x), îäíàêî óæå íà ñëåäóþùåì øàãå îíà áóäåòìåíüøå 1. Óáåäèìñÿ â ýòîì:"¸·11aa=F (xn+1 ) =1− 21− 12xn+12(x+n2#0a 2xn )=¡ a ¢2"#aa 22a11 (1 + x2n ) − x2n1 1 + x2n1x2n1− 1===,a 2a 2 <a222 (1 + x2 )2 (1 + x2 )22 (1 + x2 )nnnò.å.
òàêîé èòåðàöèîííûé ïðîöåññ âñåãäà ñõîäèòñÿ.1.1.2 Ìåòîä ÍüþòîíàÌåòîä Íüþòîíà èëè êàñàòåëüíûõ çàêëþ÷àåòñÿ â òîì, ÷òî åñëè xj íåêîòîðîå ïðèáëèæåíèå ê êîðíþ x∗óðàâíåíèÿ f (x) = 0 , f ∈ C 1 , òî ñëåäóþùåå ïðèáëèæåíèå îïðåäåëÿåòñÿ êàê êîðåíü êàñàòåëüíîé ê ôóíêöèèf (x), ïðîâåäåííîé â òî÷êå xj . Òàêèì îáðàçîì, â óðàâíåíèè êàñàòåëüíîé f 0 (xj ) =ïîëîæèòü y = 0 è x = xj+1 , òî åñòüxj+1 = xj −4f (xj ).f 0 (xj )y−f (xj )x−xjíåîáõîäèìîÏîñêîëüêó ìåòîä Íüþòîíà ïðåäñòàâëÿåò ñîáîé ìåòîä ïðîñòûõ èòåðàöèé ïðè F (x) = x −f (x)f 0 (x), òîíåòðóäíî óáåäèòüñÿ, ÷òî ïðè f ∈ C 2 ñóùåñòâóåò îêðåñòíîñòü êîðíÿ, â êîòîðîé |F 0 | < 1 . Äåéñòâèòåëüíî,F0 = 1 −(f 0 )2 − f f 00f f 00=,(f 0 )2(f 0 )2òî åñëè x∗ êîðåíü êðàòíîñòè α , òî â åãî îêðåñòíîñòè f (x) ≈ a(x − x∗ )α è, ñëåäîâàòåëüíî, F 0 (x∗ ) =α−1α.Çàìåòèì, ÷òî åñëè x∗ ïðîñòîé êîðåíü, òî ñõîäèìîñòü ìåòîäà êàñàòåëüíûõ êâàäðàòè÷íàÿ (òî åñòü ïîðÿäîêñõîäèìîñòè ðàâåí 2).
Óáåäèìñÿ â ýòîì. Ïîñêîëüêó xj+1 − x∗ = xj − x∗ −f (xj )f 0 (xj ), òîxj+1 − x∗1f (xj )1=− 0=−(xj − x∗ )2xj − x∗f (xj )(xj − x∗ )2xj − x∗¢¡f 0 (x∗ )(xj − x∗ ) + 12 f 00 (x∗ )(xj − x∗ )2 + o (xj − x∗ )2−,(xj − x∗ )2 [f 0 (x∗ ) + f 00 (x∗ )(xj − x∗ ) + o(xj − x∗ )]îòêóäàf 00 (x∗ )xj+1 − x∗=.j→∞ (xj − x∗ )22f 0 (x∗ )limÒàêèì îáðàçîì, ñõîäèìîñòü ìåòîäà Íüþòîíà î÷åíü áûñòðàÿ.
Ïðè ýòîì áåç âñÿêèõ èçìåíåíèé ìåòîä îáîáùàåòñÿ íà êîìïëåêñíûé ñëó÷àé. Åñëè êîðåíü x∗ ÿâëÿåòñÿ êîðíåì âòîðîé êðàòíîñòè è âûøå, òî, êàê íåòðóäíîóáåäèòüñÿ, ïîðÿäîê ñõîäèìîñòè ñðàçó ïàäàåò è ñòàíîâèòñÿ ëèíåéíûì.Ê íåäîñòàòêàì ìåòîäà Íüþòîíà ñëåäóåò îòíåñòè åãî ëîêàëüíîñòü, ïîñêîëüêó îí ãàðàíòèðîâàííî ñõîäèòñÿ2ïðè ïðîèçâîëüíîì ñòàðòîâîì ïðèáëèæåíèè òîëüêî, åñëè âåçäå âûïîëíåíî |f f 00 |/(f 0 ) < 1, â ïðîòèâíîéñèòóàöèè ñõîäèìîñòü åñòü ëèøü â íåêîòîðîé îêðåñòíîñòè êîðíÿ. Äðóãèì íåäîñòàòêîì ìåòîäà Íüþòîíàÿâëÿåòñÿ òîò ôàêò, ÷òî íà êàæäîì øàãå íåîáõîäèìî çàíîâî âû÷èñëÿòü ïðîèçâîäíóþ.1.1.3 Ìåòîä ñåêóùèõ×òîáû èçáåæàòü âû÷èñëåíèÿ ïðîèçâîäíîé, ìåòîä Íüþòîíà ìîæíî óïðîñòèòü, çàìåíèâ ïðîèçâîäíóþ íàðàçíîñòíóþ, âû÷èñëåííóþ ïî äâóì ïðåäûäóùèì èòåðàöèÿì, ÷òî ýêâèâàëåíòíî çàìåíå ôóíêöèè f (x) íàèíòåðïîëÿöèîííûé ïîëèíîì, ïðîõîäÿùèé ÷åðåç òî÷êè xjïðèíèìàåò âèäxj+1 = xj −è xj−1 . Ïðè ýòîì, èòåðàöèîííûé ïðîöåññfj (xj − xj−1 ),fj − fj−1ãäå fj = f (xj ) . Ýòî äâóõøàãîâûé èòåðàöèîííûé ïðîöåññ, ïîñêîëüêó èñïîëüçóåò äëÿ íàõîæäåíèÿ ïîñëåäóþùåãî ïðèáëèæåíèÿ äâà ïðåäûäóùèõ.
Ïîðÿäîê ñõîäèìîñòè ìåòîäà ñåêóùèõ, åñòåñòâåííî, íèæå, ÷åì óìåòîäà êàñàòåëüíûõ è ðàâåí â ñëó÷àå îäíîêðàòíîãî êîðíÿ d =÷òî x∗ = 0 .√5+12 .Óáåäèìñÿ â ýòîì, ñ÷èòàÿ äëÿ óäîáñòâà,[f∗0 xj + 12 f∗00 x2j + O(x3j )](xj − xj−1 )fj (xj − xj−1 )= 0=fj − fj−1f∗ (xj − xj−1 ) + 12 f∗00 (x2j − x2j−1 ) + O(x3j − x3j−1 )f 00¸·1 + 2f∗0 xj + O(x2j )f∗002∗x+O(x).=x1−= xj j−1jjf 002f∗01 + 2f∗0 (xj + xj−1 ) + O(x2j )∗Òàêèì îáðàçîì, ñ òî÷íîñòüþ äî áåñêîíå÷íî ìàëûõ áîëåå âûñîêîãî ïîðÿäêàxj+1 = xj −fj (xj − xj−1 )f 00= ∗0 xj xj−1 + O(x3j ) .fj − fj−12f∗Îòáðàñûâàÿ îñòàòî÷íûé ÷ëåí, ïîëó÷àåì ðåêóððåíòíîå ñîîòíîøåíèå xj+1 = αxj xj−1 , α =f∗002f∗0, ðåøåíèåêîòîðîãî åñòåñòâåííî èñêàòü â âèäå xj+1 = αc xdj . Ïîñëå ïîäñòàíîâêè èìååì: cd = 1 è d2 −d−1 = 0 , îòêóäàâ ñèëó òîãî, ÷òî äëÿ ñõîäèìîñòè íåîáõîäèìî, ÷òîáû d áûëî ïîëîæèòåëüíûì, çàêëþ÷àåì, ÷òî d =5√5+12 .Ïîñêîëüêó çíàíèå ïðîèçâîäíîé íå òðåáóåòñÿ, òî ïðè òîì æå îáú¼ìå âû÷èñëåíèé â ìåòîäå ñåêóùèõ(íåñìîòðÿ íà ìåíüøèé ïîðÿäîê ñõîäèìîñòè) ìîæíî äîáèòüñÿ áîëüøåé òî÷íîñòè, ÷åì â ìåòîäå êàñàòåëüíûõ.
Îòìåòèì, ÷òî âáëèçè êîðíÿ ïðèõîäèòñÿ äåëèòü íà ìàëîå ÷èñëî, è ýòî ïðèâîäèò ê ïîòåðå òî÷íîñòè(îñîáåííî â ñëó÷àå êðàòíûõ êîðíåé), ïîýòîìó, âûáðàâ îòíîñèòåëüíî ìàëîå δ , âûïîëíÿþò âû÷èñëåíèÿ äîâûïîëíåíèÿ |xj+1 − xj | < δ è ïðîäîëæàþò èõ ïîêà ìîäóëü ðàçíîñòè ñîñåäíèõ ïðèáëèæåíèé óáûâàåò. Êàêòîëüêî íà÷íåòñÿ ðîñò, âû÷èñëåíèÿ ïðåêðàùàþò è ïîñëåäíþþ èòåðàöèþ íå èñïîëüçóþò. Ìåòîä ñåêóùèõ ñòàíîâèòñÿ íåïðèìåíèìûì. Òàêàÿ ïðîöåäóðà îïðåäåëåíèÿ ìîìåíòà îêîí÷àíèÿ èòåðàöèé íàçûâàåòñÿ ïðèåìîìÃàðâèêà.Ìåòîä ïàðàáîëÐàññìîòðèì òðåõøàãîâûé ìåòîä, â êîòîðîì ïðèáëèæåíèå xj+1 îïðåäåëÿåòñÿ ïî òðåì ïðåäûäóùèì òî÷êàìxj , xj−1 è xj−2 . Äëÿ ýòîãî çàìåíèì, àíàëîãè÷íî ìåòîäó ñåêóùèõ, ôóíêöèþ f (x) èíòåðïîëÿöèîííîéïàðàáîëîé ïðîõîäÿùåé ÷åðåç òî÷êè xj , xj−1 è xj−2 .
 ôîðìå Íüþòîíà îíà èìååò âèäp2 (x) = fj + fj−1,j (x − xj ) + fj−2,j−1,j (x − xj )(x − xj−1 ) .Òî÷êà xj+1 îïðåäåëÿåòñÿ êàê òîò èç êîðíåé ýòîãî ïîëèíîìà, êîòîðûé áëèæå ïî ìîäóëþ ê òî÷êå xj .Ïîðÿäîê ñõîäèìîñòè ìåòîäà ïàðàáîë âûøå, ÷åì ó ìåòîäà ñåêóùèõ, íî íèæå, ÷åì ó ìåòîäà Íüþòîíà. Âàæíûìîòëè÷èåì îò ðàíåå ðàññìîòðåííûõ ìåòîäîâ, ÿâëÿåòñÿ òî îáñòîÿòåëüñòâî, ÷òî äàæå åñëè f (x) âåùåñòâåííàïðè âåùåñòâåííûõ x è ñòàðòîâûå ïðèáëèæåíèÿ âûáðàíû âåùåñòâåííûìè, ìåòîä ïàðàáîë ìîæåò ïðèâåñòèê êîìïëåêñíîìó êîðíþ èñõîäíîé çàäà÷è. Ýòîò ìåòîä î÷åíü óäîáåí äëÿ ïîèñêà êîðíåé ìíîãî÷ëåíîâ âûñîêîéñòåïåíè.Ïîèñê âñåõ êîðíåéÎáùèì íåäîñòàòêîì ïî÷òè âñåõ èòåðàöèîííûõ ìåòîäîâ íàõîæäåíèÿ êîðíåé ÿâëÿåòñÿ òî, ÷òî îíè ïðè îäíîêðàòíîì ïðèìåíåíèè ïîçâîëÿþò íàéòè ëèøü îäèí êîðåíü ôóíêöèè, ïðè òîì íåèçâåñòíî êàêîé. ×òîáûíàéòè äðóãèå êîðíè, ìîæíî áûëî áû áðàòü íîâûå ñòàðòîâûå òî÷êè è ïðèìåíÿòü ìåòîä çàíîâî, íî íåò íèêàêîé ãàðàíòèè, ÷òî ïðè ýòîì èòåðàöèè ñîéäóòñÿ ê íîâîìó êîðíþ, à íå ê óæå íàéäåííîìó (åñëè âîîáùåñîéäóòñÿ, êàê, ñêàæåì, âîçìîæíî â ìåòîäå Íüþòîíà).Äëÿ ïîèñêà äðóãèõ êîðíåé èñïîëüçóåòñÿ ìåòîä óäàëåíèÿ êîðíåé.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
