計(jì)算方法-2-插值法

1、2022-3-31第二章 插值法2022-3-32第二章 插值法 2.1 引言引言 2.2 拉格朗日插值拉格朗日插值 2.3 均差與牛頓插值公式均差與牛頓插值公式 2.4 差分與等距節(jié)點(diǎn)插值差分與等距節(jié)點(diǎn)插值 2.5 埃爾米特插值埃爾米特插值 2.6 分段低次插值分段低次插值 2.7 三次樣條插值三次樣條插值2022-3-33本章要點(diǎn)用簡單的函數(shù)(如多項(xiàng)式函數(shù))作為一個復(fù)雜函數(shù)的近似,最簡單實(shí)用的方法就是插值.本章主要介紹有關(guān)插值法的一些基本概念，及多項(xiàng)式插值的基礎(chǔ)理論和幾個常用的插值方法：拉格朗日插值、分段線性插值、牛頓插值、埃爾米特插值和三次樣條插值.2022-3-34 2.1 引言引言且

2、不利于在計(jì)算機(jī)上其函數(shù)形式可能很復(fù)雜對函數(shù),),(xf個不同的點(diǎn)上的一組在區(qū)間可以獲得量假如可以通過實(shí)驗(yàn)或測運(yùn)算1,)(,nbaxfbxxxxan210nixfyii,2 , 1 , 0),(上的函數(shù)值能否存在一個性能優(yōu)良、便于計(jì)算的函數(shù)滿足比如多項(xiàng)式函數(shù)),(xP一、插值問題2022-3-35niyxPii,2 , 1 ,0)()()(xfxP近似代替并且用這就是插值問題，上式為插值條件的插值函數(shù)為函數(shù)稱函數(shù))()(xfxP則稱之為插值多項(xiàng)式為多項(xiàng)式函數(shù)如果,)(xP稱為插值節(jié)點(diǎn)點(diǎn), 2 , 1 , 0,nixi稱為插值區(qū)間區(qū)間,ba個等分點(diǎn)上若給定如函數(shù)5,0,sinxy 其插值函數(shù)的圖象

3、如下圖2022-3-3600.511.522.533.500.10.20.30.40.50.60.70.80.91sinx的 插 值xy00.511.522.533.500.10.20.30.40.50.60.70.80.91sinx的 插 值xy00.511.522.533.500.10.20.30.40.50.60.70.80.91sinx的 插 值xy00.511.522.533.500.10.20.30.40.50.60.70.80.91sinx的 插 值xy)()(xPxf和插值函數(shù)對于被插函數(shù)處的函數(shù)值必然相等在節(jié)點(diǎn)ix)()(xfxP的值可能就會偏離但在節(jié)點(diǎn)外必然存在著誤差近似代

4、替因此)()(xfxP2022-3-37二、插值法的類型上的代數(shù)插值多項(xiàng)式為在區(qū)間設(shè)函數(shù),)(baxfy nnnxaxaxaaxP2210)(且滿足niyxPiin,2 , 1 ,0)(其中 為實(shí)數(shù)，就稱P(x)為插值多項(xiàng)式，相應(yīng)的插值法稱為多項(xiàng)式插值；若P(x)為分段的多項(xiàng)式，就稱為分段插值；若P(x)為三角多項(xiàng)式，就稱為三角插值。ia本章只討論多項(xiàng)式插值與分段插值2022-3-38 2.2 拉格朗日插值拉格朗日插值 此插值問題可表述為如下： 問題問題 求作次數(shù) 多項(xiàng)式 ，使?jié)M足條件 這就是所謂的拉格朗日（拉格朗日（Lagrange）插值）插值。n ), 1 , 0( ,niyxLiin)(

5、xLn 拉格朗日（Lagrange）插值公式(以下統(tǒng)稱為Lagrange插值公式)的基本思想是，把pn(x)的構(gòu)造問題轉(zhuǎn)化為n+1個插值基函數(shù)li(x)(i=0,1,n)的構(gòu)造。2022-3-392022-3-310問題問題 已知函數(shù)y=f(x)在點(diǎn)x0,x1上的值為y0,y1，求 作一次一次式 ，使?jié)M足條件 其幾何意義，就是通過兩點(diǎn) 的一條直線。 2.2.1 線性插值與拋物插值線性插值與拋物插值111001)(,)(yxLyxL),(),(1100yxByxA一、線性插值一、線性插值點(diǎn)斜式點(diǎn)斜式)(1xL2022-3-311L12022-3-312由直線兩點(diǎn)式可知，通過A，B的直線方程為 稱

6、為線性插值(n=1的情況)，分為內(nèi)插與外推。)()(1001010 xLxxxxyyyy適用情況：適用情況：|01xx 很小時2022-3-313)()()11001xlyxly(xL也可表示為如下對稱形式：其中，0101)(xxxxxl1010 xxxx(x)l顯然，;)(xl,)(xl;)(xl,)(xl010101111000為線性插值基函數(shù)及函數(shù)1 0(x)l(x)l2022-3-314 線性插值的局限性線性插值的局限性2022-3-315線性插值舉例線性插值舉例例1: 已知 ， ，求代入點(diǎn)斜式插值多項(xiàng)式得 y=10.71428精確值為 10.723805，故這個結(jié)果有3位有效數(shù)字。1

7、0100 11121 115y)()(0010101xxxxyyyxL2022-3-316 問題問題 求作二次二次式 ，使?jié)M足條件二次插值的幾何解釋是用通過三個點(diǎn) 的拋物線來近似考察曲線，故稱為拋物插值。類似于線性插值，構(gòu)造基函數(shù)，要求滿足下式：)(2xL二、拋物插值二、拋物插值) 1, 1()(2kkkjyxLjj)()()()11kk112xlyxlyxly(xLkkkk2022-3-3172022-3-318x0=100, x1=121, x2=144f(x0)=10, f(x1)=11, f(x2)=12 (121100)(121144)L2(115) =(100121)(100144

8、)(115121)(115144)* 10+(115100)(115144)* 11+(144100)(144121)(115100)(115121)* 12= 10.7228拋物插值拋物插值舉例2(x0 x1)(x0 x2)(xx1)(xx2)f(x0) +(x1x0)(x1x2)(xx0)(xx2)f(x1)+(x2x0)(x2x1)(xx0)(xx1)f(x2)L L2 2(x)=(x)=和用線性插值相比，有效數(shù)字增加一位2022-3-319為了構(gòu)造 ，我們先定義n次插值基函數(shù)。)(xLn2.2.2 拉格朗日n次插值多項(xiàng)式定義：若n次多項(xiàng)式),1 , 0()(nixli在n+1個節(jié)點(diǎn)nx

9、xx10上滿足條件。次插 值插值基上的為節(jié)點(diǎn))(,),(),(次多 項(xiàng)多個1就稱 這1010n,x,xxxlxlxlnnnn2022-3-320)()()()()()()(11101110nkkkkkkknkkkxxxxxxxxxxxxxxxxxxxxxlnkiiikixxxx0)()(), 2 , 1 , 0(nk)()(10nxxxxxx(x)n 1令)(xkn 1則)()()(1110nkkkkkkkxxxxxxxxxxn+1次多項(xiàng)式對n=1及n=2時的情況前面已經(jīng)討論，用類似的推導(dǎo)方法，可得到n次插值基函數(shù)為：2022-3-321)()()()()()()(11101110nkkkkk

10、kknkkkxxxxxxxxxxxxxxxxxxxxxl), 2 , 1 , 0(nk且)(xLnnkknknkxxxxy011)()()()()()(11knknxxxx從而2022-3-322為記為項(xiàng)式為插值基函數(shù)的插值多以上在節(jié)點(diǎn)于是)(), 1 , 0()(,), 1 , 0()(,xLnixlnixxfyniiininijjjijnnnyxxxxxlyxlyxlyxL001100)()()()()()(總總結(jié)結(jié)稱)(xLn為y=f(x)的拉格朗日插值多項(xiàng)式稱), 1 , 0)(nixli為n次拉格朗日插值基函數(shù)2022-3-323例3：求過點(diǎn)(2，0) (4，3) (6，5) (8，

11、4) (10，1)的 拉格朗日插值多項(xiàng)式。2022-3-3242022-3-3252022-3-3262022-3-327拉格朗日插值多項(xiàng)式的缺點(diǎn)：（1）插值基函數(shù)計(jì)算復(fù)雜（2）高次插值的精度不一定高2022-3-328 2.2.3 插值余項(xiàng)與誤差估計(jì)插值余項(xiàng)與誤差估計(jì)一、插值余項(xiàng)插值的從上節(jié)可知Lagrangexfy)(,niiinxlyxL0)()(滿足nixfxLiin, 1 , 0)()(,bax但)()(xfxLn不會完全成立因此，插值多項(xiàng)式存在著截?cái)嗾`差,那么我們怎樣估計(jì)這個截?cái)嗾`差呢？2022-3-329)(xLn)(xRn)()!1()(1)1(xnfnn,)()(01niin

12、xxx其中.,),(xba且依賴于2022-3-330)()()(xLxfxRnn令上顯然在插值節(jié)點(diǎn)為), 1 , 0(nixi)()()(iniinxLxfxRni, 1 , 0,0個零點(diǎn)上至少有在因此1,)(nbaxRn)()()(1xxKxRnn設(shè))()()(101nnxxxxxxx為待定函數(shù))(xK其中)()()()()(1xxKxLxfxRnnn證明：證明：假設(shè)在區(qū)間a,b上f(x)的插值多項(xiàng)式為)(xLn2022-3-331)()()()(1xxKxLxfnn0)(x則有0的區(qū)分與注意xt)(ix且)()()(1ininxxKxR0即個零點(diǎn)上至少有在區(qū)間若令因此,2,)(,nbat

13、xxi,0)(xni, 1 , 0nixi, 2 , 1 , 0,0)()()()()(1xxKxLxfnn)()()()(1ininixxKxLxf)()()()()(1txKtLtftnn若引入輔助函數(shù)2022-3-332根據(jù)羅爾定理,個零點(diǎn)上有至少在區(qū)間1),()(nbat再由羅爾定理,個零點(diǎn)上有至少在區(qū)間nbat),()( 依此類推階導(dǎo)數(shù)為零的使得內(nèi)至少有一個點(diǎn)在區(qū)間1)(,),(ntba0)()1(n)()1(tn)()()()()1(1)1()1(txKtLtfnnnnn由于2022-3-333)!1()()()1(nfxKn)()()(1xxKxRnn)()!1()(1)1(xn

14、fnn所以)()()(截?cái)嗾`差的余項(xiàng)為插值多項(xiàng)式稱xLxRnn)()()()()()1(1)1()1()1(nnnnnnxKLf因此)!1()()()1(nxKfn02022-3-334|)(|xRn則)()!1()(1)1(xnfnn)()!1(11xnMnn注意（1）余項(xiàng)表達(dá)式只有在f(x)的高階導(dǎo)數(shù)存在時 才能應(yīng)用。（2）在ba,內(nèi)的具體位置通常不可能給出，所以，設(shè))() 1(1maxxfMnbxan2022-3-335例1:225,169,144,)(,. 1三個節(jié)點(diǎn)為若中在上節(jié)例xxf線性插值的余項(xiàng)為設(shè)LagrangexR)(1插值的余項(xiàng)為二次LagrangexR)(2解:.)175

15、(截?cái)嗾`差近似值的線性和二次插值做試估計(jì)用fLagrangexxf21)(2341)( xxf2583)( xxf|)(|max2251692xfMx |)169(| f 41014. 1|)(|max2251443xfMx |)144(| f 61051. 12022-3-336| )175(|2|)225175)(169175(|300| )175(|3|)225175)(169175)(144175(|9300| )175(|1R)175(! 2122M3001014. 121421071. 1| )175(|2R)175(! 3133M93001051. 161631035. 2202

16、2-3-337例2.5 , 5,11)(2xxxf設(shè)函數(shù)ninhihxnni, 1 ,0,10,515 , 5個節(jié)點(diǎn)等份取將插值多項(xiàng)式次的作試就Lagrangenxfn)(10, 8 , 6 , 4 ,2并作圖比較.解:211)(iiixxfy插值多項(xiàng)式次作LagrangennjnjiiijijnxxxxxxL002)()(11)(10, 8 , 6 , 4 ,2n2022-3-338-5-4-3-2-1012345-1.5-1-0.500.511.52-5-4-3-2-1012345-1.5-1-0.500.511.52-5-4-3-2-1012345-1.5-1-0.500.511.52-

17、5-4-3-2-1012345-1.5-1-0.500.511.52-5-4-3-2-1012345-1.5-1-0.500.511.52-5-4-3-2-1012345-1.5-1-0.500.511.52n=2n=4n=6n=8n=10f(x)=1/(1+x2)不同次數(shù)的拉格朗日插值多項(xiàng)式的比較圖Runge現(xiàn)象2022-3-339結(jié)果表明,并不是插值多項(xiàng)式的次數(shù)越高,插值效果越好,精度也不一定是隨次數(shù)的提高而升高,這種現(xiàn)象在上個世紀(jì)初由Runge發(fā)現(xiàn),故稱為Runge現(xiàn)象. P44 1、2本章作業(yè)1、給定正弦函數(shù)表如下，試用拉格朗日二次插值，求sin0.57891的近似值并估計(jì)誤差。0.5

18、0.60.70.479340.564640.644222、已知函數(shù)表x1.131.151.171.20y=f(x)1.1911.3951.5931.790應(yīng)用拉格朗日插值公式計(jì)算f(1.16)2022-3-341 2.3 均差與牛頓插值公式均差與牛頓插值公式2022-3-342 2.3.1 均差及其性質(zhì)均差及其性質(zhì))(xljnjiiijixxxx0)()(nj,2 , 1 ,0我們知道,拉格朗日插值多項(xiàng)式的插值基函數(shù)為形式上太復(fù)雜,計(jì)算量很大,并且重復(fù)計(jì)算也很多由線性代數(shù)的知識可知,任何一個n次多項(xiàng)式都可以表示成, 1,0 xx ),)(10 xxxx)()(110nxxxxxx,共n+1個多

19、項(xiàng)式的線性組合2022-3-343)()()()()(110102010nnnxxxxxxaxxxxaxxaaxP具有如下形式設(shè)插值多項(xiàng)式)(xP2022-3-344000)(afxP有)()(011011xxaafxP00fa 01011xxffa)()()(12022021022xxxxaxxaafxP12010102022xxxxffxxffa2022-3-345一、差商(均差)定義2.nifxxfii, 1 ,0,)(處的函數(shù)值為在互異的節(jié)點(diǎn)設(shè)稱)0()()(,000kxxxfxfxxfkkk)(,)(0差商一階均差關(guān)于節(jié)點(diǎn)為kxxxf2022-3-346二、均差具有如下性質(zhì)：2022

20、-3-347,110kkxxxxfkjkjjjjjjjxxxxxxxxxf0110)()()()(2022-3-3482022-3-349)()()()()()(4433221100 xfxxfxxfxxfxxfxxfxkk四階均差三階均差二階均差一階均差三、均差的計(jì)算方法(表格法):,10 xxf,21xxf,32xxf,43xxf,210 xxxf,321xxxf,432xxxf,3210 xxxxf,4321xxxxf,410 xxxf規(guī)定函數(shù)值為零階均差均差表2022-3-3502.3.2 牛頓插值公式2022-3-3512022-3-352)(xRn)()!1()()()(1)1(x

21、nfxNxfnnn)(,110 xxxxxfnn我們稱 為牛頓(Newton)均差插值多項(xiàng)式。)(xNn稱)(xRn 為牛頓均差插值多項(xiàng)式的截?cái)嗾`差。2022-3-3532022-3-3542022-3-355顯然：2022-3-356例1：2022-3-357解：2022-3-3582022-3-359四、拉格朗日插值與牛頓插值的比較2022-3-360P59 13、14本章作業(yè)2022-3-361 2.4 差分與等距節(jié)點(diǎn)插值差分與等距節(jié)點(diǎn)插值2022-3-362一、差分定義3.稱處的函數(shù)值為在等距節(jié)點(diǎn)設(shè), 1 , 0,)(0nkfkhxxxfkkkkkfff1處的一階向前差分在為kxxf)

22、(1, 1 ,0nk1kkkfff處的一階向后差分在為kxxf)(nk,2 , 1 2.4.1 差分及其性質(zhì)差分及其性質(zhì)2022-3-363kmkmkmfff111階向前差分處的在為mxxfk)(階向后差分處的在為mxxfk)(依此類推111kmkmkmfff可以證明mkmkmff1kkff222kkff333kkff如kkkfff12處的二階向前差分在為kxxf)(12kkkfff處的二階向后差分在為kxxf)(2022-3-3644433221100fxfxfxfxfxfxkk四階差分三階差分二階差分一階差分0f1f2f3f02f12f22f03f13f04f差分表4f3f2f1f42f3

23、2f22f43f33f44f2022-3-365二、在等距節(jié)點(diǎn)的前提下,差商與差分有如下關(guān)系,1iixxfhfi,21iiixxxf212hffii222hfihfi 12212hffii2222hfi,321iiiixxxxf312223hffii33! 3 hfiiiiixxff112211,iiiiiixxxxfxxf332121,iiiiiiiixxxxxfxxxf2022-3-3663322223hffii333! 3 hfi,1miiixxxf依此類推mimhmf!mmimhmf!,10kxxxfkkhkf!0kkkhkf!2022-3-367 2.4.2 等距節(jié)點(diǎn)插值公式等距節(jié)點(diǎn)

24、插值公式一、牛頓前插公式2022-3-3682022-3-369二、牛頓向后(差分)插值公式2022-3-3702022-3-371 牛頓插值法的優(yōu)點(diǎn)是計(jì)算較簡單,尤其是增加節(jié)點(diǎn)時,計(jì)算只要增加一項(xiàng),這是拉格朗日插值無法比的. 但是牛頓插值仍然沒有改變拉格朗日插值的插值曲線在節(jié)點(diǎn)處有尖點(diǎn)，不光滑，插值多項(xiàng)式在節(jié)點(diǎn)處不可導(dǎo)等缺點(diǎn).三、牛頓插值公式與拉格朗日插值相比2022-3-372 2.5 埃爾米特插值法埃爾米特插值法2022-3-373 2.5 埃爾米特插值法埃爾米特插值法2022-3-3742022-3-3752022-3-3762022-3-3772022-3-3782022-3-379

25、2022-3-3802022-3-3812022-3-3822022-3-3832022-3-3842022-3-3852022-3-3862022-3-387解：解：1 )2022-3-3882022-3-3892022-3-3902022-3-3912022-3-3922022-3-3932022-3-3942022-3-3952022-3-3962022-3-397P60 15、16本章作業(yè)2022-3-398 2.6 分段插值法分段插值法2022-3-399例2.5 , 5,11)(2xxxf設(shè)函數(shù)ninhihxnni, 1 ,0,10,515 , 5個節(jié)點(diǎn)等份取將插值多項(xiàng)式次的作試就

26、Lagrangenxfn)(10, 8 , 6 , 4 ,2解:211)(iiixxfy插值多項(xiàng)式次作LagrangennjnjiiijijnxxxxxxL002)()(11)(10, 8 , 6 , 4 ,2n 2.6.1 高次插值的病態(tài)性質(zhì)高次插值的病態(tài)性質(zhì)2022-3-3100-5-4-3-2-1012345-1.5-1-0.500.511.52-5-4-3-2-1012345-1.5-1-0.500.511.52-5-4-3-2-1012345-1.5-1-0.500.511.52-5-4-3-2-1012345-1.5-1-0.500.511.52-5-4-3-2-1012345-1

27、.5-1-0.500.511.52-5-4-3-2-1012345-1.5-1-0.500.511.52n=2n=4n=6n=8n=10f(x)=1/(1+x2)-5-4-3-2-1012345-1.5-1-0.500.511.52n=2n=4n=6n=8n=10f(x)=1/(1+x2)不同次數(shù)的拉格朗日插值多項(xiàng)式的比較圖Runge現(xiàn)象2022-3-3101結(jié)果表明,并不是插值多項(xiàng)式的次數(shù)越高,插值效果越好,精度也不一定是隨次數(shù)的提高而升高,這種現(xiàn)象在上個世紀(jì)初由Runge發(fā)現(xiàn),故稱為Runge現(xiàn)象. 2022-3-3102 2.6.2 分段線性插值分段線性插值一、 分段線性插值的構(gòu)造202

28、2-3-3103-4-3-2-101234-1-0.8-0.6-0.4-0.200.20.40.60.81-4-3-2-101234-1-0.8-0.6-0.4-0.200.20.40.60.81-4-3-2-101234-1-0.8-0.6-0.4-0.200.20.40.60.81-4-3-2-101234-1-0.8-0.6-0.4-0.200.20.40.60.81-4-3-2-101234-1-0.8-0.6-0.4-0.200.20.40.60.81的圖象分段線性插值)(1xLy 的一條折線10,實(shí)際上是連接點(diǎn),n, ,i),y(xii也稱折線插值,如右圖曲線的光滑性較差，在節(jié)點(diǎn)處

29、有尖點(diǎn)。但如果增加節(jié)點(diǎn)的數(shù)量。減小步長,會改善插值效果)()(lim10 xfxLh上連續(xù)在若,)(baxf因此則2022-3-31042022-3-31052022-3-3106)()(max1xIxfhxxxkk| )( |max2121kkxxxxxxxMkk228)()(maxhMxIxfhbxa分段線性插值的誤差估計(jì)可利用插值余項(xiàng)得到或二、 分段線性插值的誤差估計(jì)其中)(max2xfMbxa 2022-3-3107 2.6.3 分段三次埃爾米特插值分段三次埃爾米特插值2022-3-31082022-3-31092022-3-31102022-3-31112022-3-31122022

30、-3-31132022-3-31142022-3-3115)(1xI2022-3-3116P59 18、19本章作業(yè)2022-3-3117 2.7 三次樣條插值三次樣條插值2022-3-3118 2.7 三次樣條插值三次樣條插值什么是樣條:是指飛機(jī)或輪船等的制造過程中為描繪出光滑的外形曲線(放樣)所用的工具.樣條本質(zhì)上是一段一段的三次多項(xiàng)式拼合而成的曲線在拼接處,不僅函數(shù)是連續(xù)的,且一階和二階導(dǎo)數(shù)也是連續(xù)的1946年,Schoenberg將樣條引入數(shù)學(xué),即所謂的樣條函數(shù)2022-3-3119 2.7.1 三次樣條插值三次樣條插值2022-3-31202022-3-31212022-3-3122

31、2022-3-3123 2.7.2 樣條插值函數(shù)的建立樣條插值函數(shù)的建立三對角方程組三對角方程組2022-3-3124jjjjjjhxxMhxxMxs 11)(), 1 , 0()(njMxSjj 表達(dá)表達(dá))(xS，由于，由于1,jjxx)(xS 在區(qū)間在區(qū)間上是線性函數(shù)，可表示為上是線性函數(shù)，可表示為)(xs 1)(jjyxs對積分兩次并利用可定出積分常數(shù)，于是得三次樣條表達(dá)式2022-3-3125) 1, 1 , 0()6()6(6)(6)()(211123131njhxxhMyhxxhMyhxxMhxxMxSjjjjjjjjjjjjjjjjjjjjjjjjjjjjhMMhyyhxxMhxxMx