В.Б. Андреев - Численные методы (1113834), страница 17
Текст из файла (страница 17)
Ïðè âû÷èñëåíèè L1 (x∗ ) âîñïîëüçóåìñÿ ôîðìóëîé äëÿïîãðåøíîñòè èíòåðïîëÿöèè1f (x) − L1 (x) = f 00 (ηk )(x − xk−1 )(x − xk ),2ηk ∈ (x, xk−1 , xk ),ãäå (x, xk−1 , xk ) îòêðûòûé èíòåðâàë, êîíöàìè êîòîðîãî ÿâëÿþòñÿ êðàéíèå èç óêàçàííûõ òðåõ òî÷åê. Ïîëàãàÿ çäåñü x = x∗ è ïðèíèìàÿ âî âíèìàíèå, ÷òî f (x∗ ) = 0,íàõîäèì èñêîìîå âûðàæåíèå, ïîäñòàâëÿÿ êîòîðîå â (13.3), ñ ó÷åòîì âûøåñêàçàííîãîáóäåì èìåòü1 f 00 (ηk )xk+1 − x∗ =(xk − x∗ )(xk−1 − x∗ ).(13.4)2 f 0 (ξk )Êàê è ïðè èçó÷åíèè ìåòîäà Íüþòîíà, áóäåì ïðåäïîëàãàòü, ÷òî|f 0 (x)| > m1 ,|f 00 (x)| 6 M2 .Òîãäà èç (13.4) áóäåì èìåòü îöåíêó|xk+1 − x∗ | 6M2|xk − x∗ | |xk−1 − x∗ |.2m1(13.5)131Äîìíîæàÿ òåïåðü îáå ÷àñòè ýòîãî íåðàâåíñòâà íà M2 /(2m1 ) è îáîçíà÷àÿM2|xk − x∗ | = ∆k ,2m1(13.6)∆k+1 6 ∆k ∆k−1 .(13.7)íàéäåì, ÷òîÎòìåòèì, ÷òî â ìåòîäå Íüþòîíà ∆k+1 6 ∆2k , è ýòî ïîçâîëèëî íàì ãîâîðèòü î êâàäðàòè÷íîé ñõîäèìîñòè ìåòîäà.
Äëÿ ìåòîäà ñåêóùèõ àíàëîãè÷íîå íåðàâåíñòâî∆k+1 6 ∆νk(13.8)äîêàçûâàåòñÿ ñóùåñòâåííî áîëåå ñëîæíî. Ìû íå áóäåì åãî äîêàçûâàòü, à ïîëó÷èìîöåíêó òèïà (13.8) äëÿ ìàæîðàíòû ïîãðåøíîñòè.Çàìåòèì, ÷òî, åñëèzk+1 = zk zk−1 ,z0 > ∆0 , z1 > ∆1 ,òî∆k+1 6 zk+1 .(13.9)(13.10)Ïîïûòàåìñÿ ñâåñòè íåëèíåéíîå ðàçíîñòíîå óðàâíåíèå (13.9) ê âèäózk+1 = zkν .(13.11)νÅñëè ýòî òàê, òî zk = zk−1, è, ñëåäîâàòåëüíî,1/νzk−1 = zk .Ïîäñòàâëÿÿ ýòî ñîîòíîøåíèå è (13.11) â (13.9), ïîëó÷èì1+1/νzkν = zk.Ïðèðàâíèâàÿ ñòåïåíè zk â ëåâîé è ïðàâîé ÷àñòÿõ, íàõîäèì, ÷òîν = 1 + 1/ν,ò.å. ν 2 − ν − 1 = 0.(13.12)Îòñþäà âûòåêàåò, ÷òî√1± 5ν1,2 =.2√Êîðíþ ν = (1 − 5)/2 îòâå÷àåò íåóáûâàþùåå ðåøåíèå óðàâíåíèÿ (13.11), êîòîðîå íåìîæåò îïèñûâàòü ñõîäÿùèéñÿ èòåðàöèîííûé ïðîöåññ. Ïîýòîìó ñëåäóåò âçÿòü√1+ 5≈ 1.6180339.(13.13)ν=2Èòàê, âìåñòî (13.8) èìååì (13.10), (13.11), (13.13), ÷òî ïîçâîëÿåò ãîâîðèòü î ñõîäèìîñòè ìåòîäà ñåêóùèõ ñî ñêîðîñòüþ (13.13).
Ýòà ñêîðîñòü ìåíüøå, ÷åì ó ìåòîäàÍüþòîíà.132 13. ÌÅÒÎÄ ÑÅÊÓÙÈÕÏðèìåð 13.1. Ïóñòü òðåáóåòñÿ íàéòè êîðåíü ôóíêöèè f (x) = x2 − a. Ìåòîä ñåêóùèõïðèìåíèòåëüíî ê ýòîé ôóíêöèè ïðèíèìàåò âèäxk+1 = xk −x2k − axk xk−1 + a=.22xk − xk−1xk + xk−1Åñëè a = 3 è ïîëîæèòü x0 = 3, à x1 = 2, òîx2 = 1.8,x3 =33≈ 1.7368,19x4 ≈ 1.7321428ïðè x∗ = 1.732051 . . . .Çàìå÷àíèå 13.1. Íåëèíåéíîå ðàçíîñòíîå óðàâíåíèå (13.11) èìååò î÷åâèäíîå ðåøåíèåkzk = z0ν ,(13.14)äëÿ êîòîðîãî, â ÷àñòíîñòè, z1 = z0ν . Íî â èòåðàöèîííîì ìåòîäå (13.1) èñïîëüçóþòñÿ äâàíà÷àëüíûõ óñëîâèÿ, è ïîýòîìó âåëè÷èíà z1 íå äîëæíà çàâèñåòü îò z0 .
Ìû âûíóæäåíûêîíñòàòèðîâàòü, ÷òî íàéäåííîå ðåøåíèå (13.14) íå ñîâñåì ïðàâèëüíî îïèñûâàåò ýòîòïðîöåññ. Òî, ÷òî ìû íå ïîëó÷èëè ðåøåíèÿ óðàâíåíèÿ (13.9), óäîâëåòâîðÿþùåãî îáîèìíà÷àëüíûì óñëîâèÿì, íå äîëæíî âûçûâàòü óäèâëåíèÿ: ìû âåäü íàøëè ðåøåíèå, îáùååäëÿ (13.9) è (13.11), à èíòåðåñóþùåå íàñ ðåøåíèå ìîæåò (13.11) è íå óäîâëåòâîðÿòü.Âåðíåìñÿ ê çàäà÷å (13.9) è íàéäåì åå ðåøåíèå. Ëîãàðèôìèðóÿ óðàâíåíèå (13.9),áóäåì èìåòüln zk+1 = ln zk + ln zk−1 .Îáîçíà÷àÿ(13.15)ln zk = yk ,äëÿ yk ïîëó÷èì ëèíåéíîå ðàçíîñòíîå óðàâíåíèå ñ ïîñòîÿííûìè êîýôôèöèåíòàìèyk+1 = yk + yk−1 .Åãî õàðàêòåðèñòè÷åñêîå óðàâíåíèå åñòüq2 − q − 1 = 0(ñðàâíè ñ (13.12)) ñ êîðíÿìè√1+ 5q1 =,2Ïîýòîìó√1− 5q2 =,2q1 + q2 = 1,yk = c1 q1k + c2 q2k .q2−3 +=q12√5≈ −0.38.(13.16)133Óäîâëåòâîðÿÿ íà÷àëüíûì óñëîâèÿì (13.9), áóäåì èìåòüc1 + c2 = y0 = ln z0 ,q1 c1 + q2 c2 = y1 = ln z1 .Îòñþäà íàõîäèì, ÷òîy1 − y0 q2y1 − y0 + y0 q1√√=,55y1 − y0 + y0 q2y1 − y0 q1√=−c2 = − √55c1 =è, ñëåäîâàòåëüíî,y1 + (q1 − 1)y0 k y1 + (q2 − 1)y0 k√√q1 −q2 =55ln(z1 z0q1 −1 ) k ln(z1 z0q2 −1 ) k√√=q1 −q2 ,55yk =à ñ ó÷åòîì (13.15)¾½kkq2 −1 q2q1 −1 q1=zk = exp ln(z1 z0 ) √ − ln(z1 z0 ) √55¡¢qk /√5 ± ¡ q2 −1 ¢q2k /√5= z1 z0q1 −1 1.z1 z0Îòñþäà, â ÷àñòíîñòè, ñëåäóåò, ÷òî, åñëèz1 = z0q1 ,òîz1 z0q2 −1 = z0q1 +q2 −1 = 1,è, ñëåäîâàòåëüíî,√z1 z0q1 −1 = z02q1 −1 = z0 5qkzk = z01 ,÷òî ñîâïàäàåò ñ (13.14), èáî q1 = ν . áîëåå æå ðåàëèñòè÷åñêîì ñëó÷àå, êîãäà z1 = z0 ,√(q k+1 −q2k+1 )/ 5zk = z0 1√q k+1 (1−(q2 /q1 )k+1 )/ 5= z01.Ýòî ñîîòíîøåíèå äàåò ïðåäñòàâëåíèå ïîãðåøíîñòè íà k -îé èòåðàöèè ÷åðåç ïîãðåøíîñòè z0 è z1 = z0 .Íåáåçûíòåðåñåí âîïðîñ î ñêîðîñòè óáûâàíèÿ ïîãðåøíîñòè íà äâóõ ñîñåäíèõ èòåðàöèÿõ.
Ïóñòüzk+1 = zkνk .Îòñþäàνk = (ln zk+1 )/(ln zk ) = yk+1 /yk ,134 13. ÌÅÒÎÄ ÑÅÊÓÙÈÕà ñ ó÷åòîì (13.16)yk+1c1 q1k+1 + c2 q2k+1==ykc1 q1k + c2 q2k"µ ¶kµ ¶k+1 #1 + cc21 (q2 /q1 )k+1c 2 q2q2= q1= q1 1 −+O=c2k1 + c1 (q2 /q1 )c 1 q1q1¡¢= q1 + O (q2 /q1 )k .νk =Îòñþäà ñëåäóåò, ÷òî ïðè ëþáûõ íà÷àëüíûõ ïðèáëèæåíèÿõ óáûâàíèå ïîãðåøíîñòè âìàëîé îêðåñòíîñòè êîðíÿ ïðîèñõîäèò ñî ñêîðîñòüþ ∼ q1 .Çàìå÷àíèå 13.2. Ìû óæå îòìå÷àëè, ÷òî ñêîðîñòü ñõîäèìîñòè ìåòîäà ñåêóùèõ íèæå,÷åì ìåòîäà Íüþòîíà. È, òåì íå ìåíåå, ìåòîä ñåêóùèõ ìîæåò îêàçàòüñÿ áîëåå ïðåäïî÷òèòåëüíûì ïî ñðàâíåíèþ ñ ìåòîäîì Íüþòîíà. Äëÿ ðåàëèçàöèè êàæäîé èòåðàöèèâ ìåòîäå Íüþòîíà íóæíî âû÷èñëÿòü çíà÷åíèå ôóíêöèè è åå ïðîèçâîäíîé â íîâîéòî÷êå.  ìåòîäå ñåêóùèõ íà êàæäîé èòåðàöèè íóæíî çíàòü òîëüêî îäíî íîâîå çíà÷åíèåôóíêöèè.
Åñëè ýòè îïåðàöèè òðóäîåìêèå, òî äâå îïåðàöèè ïî ìåòîäó ñåêóùèõ ìîãóòáûòü ñðàâíèìû ïî òðóäîåìêîñòè ñ îäíîé èòåðàöèåé ïî ìåòîäó Íüþòîíà, à ýòî ïðèâîäèòê áîëüøåìó óìåíüøåíèþ íà÷àëüíîé ïîãðåøíîñòè.Ãëàâà III×èñëåííîå äèôôåðåíöèðîâàíèå135 14×èñëåííîå äèôôåðåíöèðîâàíèå14.1 Ââåäåíèå×èñëåííîå äèôôåðåíöèðîâàíèå ïðèìåíÿåòñÿ, åñëè ôóíêöèÿ çàäàíà òàáëèöåé èëè åñëèåå òðóäíî ïðîäèôôåðåíöèðîâàòü àíàëèòè÷åñêè. Äîïóñòèì, ÷òî â îêðåñòíîñòè íåêîòîðîé òî÷êè x ó ôóíêöèè f (x) ñóùåñòâóåò ïðîèçâîäíàÿ. Ïî îïðåäåëåíèþf (x + ∆x) − f (x).∆x→0∆xf 0 (x) = limÅñëè îòêàçàòüñÿ îò ïðåäåëüíîãî ïåðåõîäà, òî ìîæíî ïîëîæèòüf (x + ∆x) − f (x).(14.1)∆xÝòî è åñòü ïðîñòåéøàÿ ôîðìóëà ÷èñëåííîãî äèôôåðåíöèðîâàíèÿ. Îöåíèì åå ïîãðåøíîñòü â ïðåäïîëîæåíèè, ÷òî çíà÷åíèÿ ôóíêöèè f (x) âû÷èñëÿþòñÿ òî÷íî, è îíà äâàæäû íåïðåðûâíî äèôôåðåíöèðóåìà.
Èñïîëüçóÿ ôîðìóëó Òåéëîðà, íàõîäèì, ÷òîf 0 (x) ≈2f (x) + ∆xf 0 (x) + (∆x)f 00 (ξ) − f (x)f (x + ∆x) − f (x)2==∆x∆x∆x 00= f 0 (x) +f (ξ), ξ ∈ (x, x + ∆x).2(14.2)Îòñþäà çàêëþ÷àåì, ÷òî ôîðìóëà (14.1) äëÿ ôóíêöèè f (x) ∈ C 2 èìååò ïîãðåøíîñòüïåðâîãî ïîðÿäêà ìàëîñòè îòíîñèòåëüíî ∆x.Ïóñòü xi = x0 + ih, ãäå i ∈ Z, à h > 0 øàã ñåòêè. Òîãäà, ïîëàãàÿ â (14.2) x = xi ,à ∆x = h, ïîëó÷èìhf (xi+1 ) − f (xi )= f 0 (xi ) + f 00 (ξi ).(14.3)h2Åñëè æå â (14.2) ïîëîæèòü ∆x = −h è ñíîâà x = xi , òîf (xi−1 ) − f (xi )h= f 0 (xi ) − f 00 (ξ˜i ).−h2137(14.4)138 14.
×ÈÑËÅÍÍÎÅ ÄÈÔÔÅÐÅÍÖÈÐÎÂÀÍÈÅÈç (14.3), (14.4) âûòåêàåò, ÷òî è ïðèáëèæåííàÿ ôîðìóëàf 0 (xi ) ≈f (xi+1 ) − f (xi )h(14.5)è ïðèáëèæåííàÿ ôîðìóëàf (xi ) − f (xi−1 )(14.6)hÿâëÿþòñÿ ôîðìóëàìè ïåðâîãî ïîðÿäêà òî÷íîñòè, îäíàêî èõ ïîãðåøíîñòè, âîîáùå ãîâîðÿ, èìåþò ðàçíûå çíàêè. Ïîýòîìó åñòü íàäåæäà, ÷òî ó ïîëóñóììû ïðàâûõ ÷àñòåé(14.5), (14.6) ïîãðåøíîñòü áóäåò èìåòü áîëüøèé ïîðÿäîê ìàëîñòè îòíîñèòåëüíî h (ïðèáîëüøåé ãëàäêîñòè).  ñàìîì äåëå, èñïîëüçóÿ ôîðìóëó Òåéëîðà, íàõîäèì, ÷òî·¸1 f (xi+1 ) − f (xi ) f (xi ) − f (xi−1 )f (xi+1 ) − f (xi−1 )=+=2hh2h·µ¶¸±h2 00 h3 000 ¯h2 00 h3 000 ¯00(14.7)= fi + hfi + fi + f (ξi ) − fi − hfi + fi − f (ξi )2h2626h2 f 000 (ξ¯i ) + f 000 (ξ¯i )h2= fi0 += fi0 + f 000 (ξi ), ξi ∈ (ξ¯i , ξ¯i ) ⊂ (xi−1 , xi+1 ).626f 0 (xi ) ≈Îòñþäà çàêëþ÷àåì, ÷òî äëÿ f (x) ∈ C 3 ôîðìóëàf 0 (xi ) ≈f (xi+1 ) − f (xi−1 )2h(14.8)èìååò ïîãðåøíîñòü O(h2 ).Òåïåðü âû÷òåì èç (14.3) ñîîòíîøåíèå (14.4)f (xi+1 ) − 2f (xi ) + f (xi−1 )f 00 (ξi ) + f 00 (ξ˜i )=h= f 00 (ξ˜˜i )h.h2Ñëåäîâàòåëüíî,fi+1 − 2fi + fi−1= f 00 (ξ˜˜i ),ξ˜˜i ∈ (xi−1 , xi+1 ),(14.9)h2ò.å.
ëåâàÿ ÷àñòü ýòîãî ñîîòíîøåíèÿ àïïðîêñèìèðóåò âòîðóþ ïðîèçâîäíóþ ôóíêöèèf (x). Èññëåäóåì ïîãðåøíîñòü ýòîé àïïðîêñèìàöèè â òî÷êå xi :·h2 00 h3 000 h4 IV ¯1fi+1 − 2fi + fi−10= 2 fi + hfi + fi + fi + f (ξi )−h2h2!3!4!¸234hhh(14.10)− 2fi + fi − hfi0 + fi00 − fi000 + f IV (ξ¯i ) =2!3!4!h2 f IV (ξ¯i ) + f IV (ξ¯i )h2 IV0000= f (xi ) + f (ξi ).= fi +12212Îòñþäà ñëåäóåò, ÷òî ëåâàÿ ÷àñòü ñîîòíîøåíèÿ (14.10) àïïðîêñèìèðóåò âòîðóþ ïðîèçâîäíóþ ôóíêöèè f (x) ∈ C 4 ñ ïîãðåøíîñòüþ O(h2 ).14.2. ÌÅÒÎÄ ÍÅÎÏÐÅÄÅËÅÍÍÛÕ ÊÎÝÔÔÈÖÈÅÍÒÎÂ139Çàìå÷àíèå 14.1. Ìû óæå òðèæäû (â (14.7), (14.10) è â ôîðìóëå ïîñëå ñîîòíîøåíèÿ(14.8)) âîñïîëüçîâàëèñü óòâåðæäåíèåì î òîì, ÷òî äëÿ íåïðåðûâíîé ôóíêöèè 0.5(f (x)+f (y)) = f (z), ãäåz ∈ (x, y). Äîêàæåì ýòî óòâåðæäåíèå â áîëåå îáùåì âèäå.
Ïóñòü f (x) ∈ C[a, b], m =min[a,b] f (x), M = max[a,b] f (x), x1 , x2 ∈ [a, b], α > 0, β > 0. Òîãäàη=αf (x1 ) + βf (x2 )= f (x3 ),α+β ñàìîì äåëå,m6x3 ∈ [a, b].αf (x1 ) + βf (x2 )= η 6 M.α+βè ïî òåîðåìå î ïðîìåæóòî÷íûõ çíà÷åíèÿõ η = f (x3 ).Ââåäåì ñëåäóþùèå îáîçíà÷åíèÿfx,i =fi+1 − fi,hfx̄,i =fi − fi−1,h1◦fx,i= (fx,i + fx̄,i ).2Òîãäàfi+1 − 2fi + fi−1.h2Îòñþäà è èç (14.3), (14.4), (14.7), (14.10) íàõîäèì, ÷òîfx̄x,i =fx,i = fi0 + O(h),fx̄,i = fi0 + O(h),◦fx,i= fi0 + O(h2 ),(14.11)fx̄x,i = fi00 + O(h2 ).14.2 Ìåòîä íåîïðåäåëåííûõ êîýôôèöèåíòîâÐàññìîòðåííûå ïðîñòåéøèå ôîðìóëû ÷èñëåííîãî äèôôåðåíöèðîâàíèÿ áûëè ïîñòðîåíû èç íåêèõ ýâðèñòè÷åñêèõ ñîîáðàæåíèé.
Ñóùåñòâóþò è ðåãóëÿðíûå ñïîñîáû ïîñòðîåíèÿ ôîðìóë ÷èñëåííîãî äèôôåðåíöèðîâàíèÿ. Îäèí èç íèõ ìåòîä íåîïðåäåëåííûõêîýôôèöèåíòîâ.Áóäåì èñêàòü ôîðìóëó ÷èñëåííîãî íàõîæäåíèÿ k -îé ïðîèçâîäíîé â ñëåäóþùåìâèäånXf (k) (x) ≈cj f (xj ), k 6 n(14.12)j=0è âûáåðåì cj èç òåõ óñëîâèé, ÷òîáû ôîðìóëà áûëà òî÷íà íà ìíîãî÷ëåíàõ íåêîòîðîéñòåïåíè. Ðàññìîòðèì140 14. ×ÈÑËÅÍÍÎÅ ÄÈÔÔÅÐÅÍÖÈÐÎÂÀÍÈÅÏðèìåð 14.1. Ïóñòüf 0 (h) ≈ c0 f (0) + c1 f (h) + c2 f (2h).(14.13)Ïîòðåáóåì, ÷òîáû ôîðìóëà áûëà òî÷íà íà ëèíåéíûõ ôóíêöèÿõ. Ïîäñòàâëÿÿ â (14.13)f (x) ≡ 1 è f (x) ≡ x è òðåáóÿ âûïîëíåíèÿ òî÷íîãî ðàâåíñòâà, áóäåì èìåòü0 = c0 + c11 =+ c2 ,c1 h + c2 2h.Ïðèíèìàÿ c0 çà ïàðàìåòð, äëÿ c1 è c2 ïîëó÷èì ñèñòåìóc1 +c2 = −c0 ,hc1 + 2hc2 =1.Îïðåäåëèòåëü ýòîé ñèñòåìû ðàâåí h è ïîýòîìó¯¯Á¯−co 1 ¯¯c1 = ¯¯h = (−2hc0 − 1)/h,1 2h¯¯¯Á¯ 1 −c0 ¯¯¯c2 = ¯h = (1 + c0 h)/h.h 1 ¯(14.14)(14.15)Èòàê, ìû ïîñòðîèëè îäíîïàðàìåòðè÷åñêîå ñåìåéñòâî òðåõòî÷å÷íûõ ôîðìóë ÷èñëåííîãî íàõîæäåíèÿ ïåðâîé ïðîèçâîäíîéf 0 (h) ≈ c0 f (0) −Ïðè c0 = 0 èìååì1 + c0 h1 + 2c0 hf (h) +f (2h).hhf 0 (h) ≈f (2h) − f (h)= fx (h).hf 0 (h) ≈f (h) − f (0)= fx̄ (h).hÏðè c0 = −1/hÝòî óæå èçâåñòíûå íàì ôîðìóëû.Ïîòðåáóåì òåïåðü, ÷òîáû (14.13) áûëà òî÷íà íà ìíîãî÷ëåíàõ âòîðîé ñòåïåíè.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
