數(shù)值分析 第二章 代數(shù)插值解析

1、數(shù)值分析Numerical Analysis第二章代 數(shù) 插 值鄭州大學(xué)碩士研究生課程（2015-2016學(xué)年第一學(xué)期） 2/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis第二章 代 數(shù) 插 值 2.1 代數(shù)插值問題 問題提出2.2 代數(shù)插值多項(xiàng)式的存在唯一性 可解性2.3 拉格朗日插值方法 解決方法和理論分析 2.4 牛頓(Newton)插值 算法實(shí)現(xiàn) 2.5 分段線性插值 2.6 Hermite插值2.7 樣條插值計(jì)算機(jī)數(shù)值算法設(shè)計(jì)思路3/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysisy

2、= f (x)y=p (x)例2.1.1 設(shè)計(jì)某工件的外形，要求其輪廓線是光滑的，且必須過n+1個(gè)互異的點(diǎn)(xi,yi)(i=0,1,n). 輪廓線應(yīng)如何設(shè)計(jì)呢？2.1 代數(shù)插值問題的提出4/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis解： 滿足要求的輪廓線不妨取為n次多項(xiàng)式Pn(x). 設(shè)這里 Pn(x)是光滑的，且它滿足將(2.1)帶入(2.2)可得下面線性代數(shù)方程組2.1 代數(shù)插值問題的提出5/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis則(2.3)的系數(shù)行列式為范德蒙德行列式因x

3、ixj（ij），故V0. 從而方程組(2.3)的解存在唯一.求出未知量a0,an代入(2.1)即得所求輪廓線. 2.1 代數(shù)插值問題6/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis代數(shù)插值問題： 設(shè)函數(shù) y=f (x)定義在區(qū)間a, b上，而x0, x1, xn是在a, b上取定的n+1個(gè)互異節(jié)點(diǎn), 則在這些點(diǎn)處的函數(shù)值為 yi=f (xi), i=0,1,n. 求一個(gè)次數(shù)不超過 n 的多項(xiàng)式Pn(x)，使它滿足則稱Pn(x)為f (x)的n次代數(shù)插值多項(xiàng)式. 求滿足以上條件多項(xiàng)式Pn(x)的問題叫做代數(shù)插值問題. 稱 x0,x1,xn 為

4、插值節(jié)點(diǎn)， a, b為插值區(qū)間，（）為插值條件.2.1 代數(shù)插值問題的提出7/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis代數(shù)插值問題是否可解？2.2 代數(shù)插值多項(xiàng)式的存在唯一性8/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis多項(xiàng)式局部近似以直代曲以簡(jiǎn)代繁多項(xiàng)式整體近似以直代曲2.2 代數(shù)插值多項(xiàng)式的存在唯一性9/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis定理2.2.1 n次代數(shù)插值問題的解是存在且惟一的.證： 因?yàn)?x0, x1,

5、 xn 是在a, b上取定的n+1個(gè)互異節(jié)點(diǎn),由例中分析過程可知，代數(shù)方程組的解存在唯一，從而滿足插值條件(2.5)的n次代數(shù)插值多項(xiàng)式Pn(x)也是存在唯一的.2.2 代數(shù)插值多項(xiàng)式的存在唯一性10/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis目標(biāo)：設(shè)計(jì)計(jì)算量小、實(shí)現(xiàn)簡(jiǎn)單的計(jì)算機(jī)算法，根據(jù)輸入的n+1個(gè)點(diǎn)生產(chǎn)n次代數(shù)插值多項(xiàng)式.約瑟夫.路易斯.拉格朗日（17351813） 評(píng)價(jià)：采用例中的待定系數(shù)法求n次代數(shù)插值多項(xiàng)式不符合目標(biāo).拉格朗日提出直接構(gòu)造多項(xiàng)式的方法.2.3 代數(shù)插值多項(xiàng)式的存在唯一性11/168鄭州大學(xué)2015-2016學(xué)年

6、碩士研究生課程 數(shù)值分析 Numerical Analysis線性插值（n=1)給定兩個(gè)互異點(diǎn)(x0，y0)，(x1，y1），確定一次插值多項(xiàng)式P1(x)的問題，稱為線性插值問題.稱(2.6)為一次拉格朗日插值多項(xiàng)式或線性插值多項(xiàng)式.2.3 拉格朗日插值方法12/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis線性插值（n=1)引入記號(hào)則它們滿足則 分別稱為節(jié)點(diǎn)x0 ,x1的插值標(biāo)準(zhǔn)基函數(shù). 線性插值多項(xiàng)式可表示為函數(shù)值 y0, y1 與插值基函數(shù)的線性組合 2.3 拉格朗日插值方法13/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值

7、分析 Numerical Analysis線性插值（n=1)2.3 拉格朗日插值方法插值標(biāo)準(zhǔn)基函數(shù)14/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis拋物插值（n=2)給定3個(gè)互異點(diǎn)(xi，yi)(0=0,1,2)，確定一個(gè)不超過2次的插值多項(xiàng)式P2(x)的問題，稱為二次插值問題.受線性插值多項(xiàng)式的啟發(fā)，猜想可通過如下方式構(gòu)造P2(x)構(gòu)造2次插值基函數(shù)li(x)(i=0,1,2),滿足li(xj)=ij(i,j=0,1,2).構(gòu)造2次插值多項(xiàng)式P2(x)=y0l0(x)+y1l1(x)+y2l2(x).2.3 拉格朗日插值方法15/168鄭

8、州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis線性插值（n=1)2.3 拉格朗日插值方法插值標(biāo)準(zhǔn)基函數(shù)16/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis拋物插值（n=2)因?yàn)?是 的兩個(gè)零點(diǎn)，于是 再由另一條件 確定系數(shù) 從而導(dǎo)出 類似可得2.3 拉格朗日插值方法17/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis拋物插值（n=2)則 稱為二次插值基函數(shù). 取 為線性組合系數(shù),將基函數(shù) 線性組合可得 容易看出,P2(x)滿足條件 因其圖形為拋物線

9、，二次插值又稱為拋物插值.2.3 拉格朗日插值方法18/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysisx0 x1x22.3 拉格朗日插值方法19/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysisn次插值由拋物插值中構(gòu)造性方法啟發(fā)，解決一般的n次代數(shù)插值問題.分別構(gòu)造x0 , x1, , xn 上的 n 次插值基函數(shù) l0(x), l1(x), , ln(x),滿足 節(jié)點(diǎn)基函數(shù)x0 x1x2xnl0(x)1000l1(x)0100l2(x)0010ln(x)0001n次插值基函數(shù)2.3 拉格朗日

10、插值方法20/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical AnalysisN次插值由上表， x1 , x2, , xn 為 l0(x) 的零點(diǎn)，設(shè)由l0(x0)=1，得2.3 拉格朗日插值方法21/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical AnalysisN次插值類似可得節(jié)點(diǎn) xi 對(duì)應(yīng)的n次插值基函數(shù)從而可得n次代數(shù)插值多項(xiàng)式顯然Pn(x)是次數(shù)不超過n的多項(xiàng)式，且Pn(xi)=yi(i=0,1,n)2.3 拉格朗日插值方法22/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical An

11、alysisN次插值拉格朗日(Lagrange)插值方法總結(jié)根據(jù)問題特征，構(gòu)造對(duì)應(yīng)每個(gè)節(jié)點(diǎn)的插值 基函數(shù)，是解決問題的關(guān)鍵.其數(shù)學(xué)思想是以直代曲，以簡(jiǎn)代繁，是高 等數(shù)學(xué)思想方法的延伸.直接構(gòu)造n次插值多項(xiàng)式的方法過程簡(jiǎn)單， 容易在計(jì)算機(jī)上實(shí)現(xiàn).2.3 拉格朗日插值方法23/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis插值函數(shù)Pn(x)在n+1個(gè)互異插值節(jié)點(diǎn)xi(i=0,1,n )處與f(xi)相等,在不等于xi的點(diǎn)x處就用Pn(x)的值作為f(x) 的近似值，這一過程稱為插值，點(diǎn)x稱為插值點(diǎn). 誤差函數(shù)Rn(x)=f(x)- Pn(x)稱為

12、插值余項(xiàng), 區(qū)間a, b稱為插值區(qū)間, 插值點(diǎn)x在插值區(qū)間內(nèi)時(shí)稱為內(nèi)插, 否則稱外插. (插值誤差屬于截?cái)嗾`差)y= f (x)y=pn (x)y= Rn(x)2.3 拉格朗日插值方法24/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis線性插值誤差定理 設(shè)f(x)在a, b上一階導(dǎo)數(shù)連續(xù)，且存在二階導(dǎo)數(shù), x0, x1為a, b上兩個(gè)互異的節(jié)點(diǎn), P1(x)為滿足 P1(xi) = f(xi) (i=0,1)的線性插值多項(xiàng)式，則對(duì)于任何x a, b , 至少存在一點(diǎn) a, b，使得2.3 拉格朗日插值方法25/168鄭州大學(xué)2015-2016

13、學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis證明： 顯然x0, x1 為R1(x)的兩個(gè)零點(diǎn)，可設(shè)R1(x)為 R1(x) = k(x)(x-x0)(x-x1).固定x，作輔助函數(shù)，令則 (xi )=0, i =0,1,且 (x)=0, 即 (t )有3個(gè)零點(diǎn) x0, x1, x. 不妨設(shè)x0 x x1 , 分別在x0，x和x，x1上應(yīng)用洛爾定理可知 (t)在每個(gè)區(qū)間上至少存在一個(gè)零點(diǎn)1和2，使 (1)=0， (2)=0，即 (t)有2個(gè)零點(diǎn). 再次利用洛爾定理知， (t)在1, 2上至少有一個(gè)零點(diǎn)，使 ()=0. 則由 (t) = f (t) -2!k(x)以及 ()=

14、0可得 k(x) = f () /2!，從而定理得證. 2.3 拉格朗日插值方法26/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis插值誤差定理定理 設(shè)f(x)在a, b上n階導(dǎo)數(shù)連續(xù)，且存在n+1階導(dǎo)數(shù), x0, x1 , xn為a, b上n+1個(gè)互異的節(jié)點(diǎn), Pn(x)為滿足 Pn(xi) = f(xi) (i=0,1,n)的n次插值多項(xiàng)式，則對(duì)于任何x a, b , 至少存在一點(diǎn) a, b，使得2.3 拉格朗日插值方法27/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis例 給定sin1

15、1=0.190809,sin12=0.207912, 求y=sinx的線性插值多項(xiàng)式，計(jì)算sin1130并估計(jì)誤差.解: x0= 11, x1= 12, y0= 0.190809, y1， sin1130P1(11.5)=0.199361,由定理知，誤差為2.3 拉格朗日插值方法28/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis例 已知f (x)的觀測(cè)數(shù)據(jù) x 0 1 2 4 f (x) 1 9 23 3 利用這些節(jié)點(diǎn)構(gòu)造f(x)的Lagrange插值多項(xiàng)式.解: 構(gòu)造三次Lagrange插值多項(xiàng)式的插值基函數(shù) 2.3 拉格朗日插值方法29

16、/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis從而，三次Lagrange插值多項(xiàng)式為 2.3 拉格朗日插值方法30/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis拉格朗日插值算法 31/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysisn 次拉格朗日插值的算法描述.輸入節(jié)點(diǎn)數(shù) n、插值點(diǎn)(xi, yi) (i=0,1,2, ,n)和要計(jì)算的函數(shù)點(diǎn) x。.設(shè)初值 y = 0,k = 0;.實(shí)現(xiàn)基函數(shù) lk(x)和插值多項(xiàng)式 Pn(x) for

17、k=0,1, , n t=1; for i=0, 1, , k1, k+1, , n t=t*(xxi)/(xkxi); y=y+t*yk; .輸出 點(diǎn)x處的函數(shù)值y.2.3 拉格朗日插值方法32/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysisfunction v=polyinterpV2(x,y,u)m=length(u); n=length(x);v=zeros(size(u);for i=1:m v(i)=0; for k=1:n t=1; for j=1:k-1 k+1:n t=t*(u(i)-x(j)/(x(k)-x(j); end

18、 v(i)=v(i)+w*y(k); endend2.3 拉格朗日插值方法x=0:3;y=-5 -6 -1 16;u=-0.25:0.01:3.25;v=polyinterpV2(x,y,u);33/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.3 拉格朗日插值方法x=0:0.12:1;y=(x.2-3*x+5).*exp(-5*x).*sin(x);plot(x,y,o,x,y)x1=0:0.02:1;y0=(x1.2-3*x1+5).*exp(-5*x1).*sin(x1);y1=interp1(x,y,x1); %線性插值y2=in

19、terp1(x,y,x1,cubic); %三次艾米特插值y3=interp1(x,y,x1,spline); %三次樣條插值y4=interp1(x,y,x1,nearest); %最鄰近插值plot(x1,y1 y2 y3 y4,:,x,y,o,x1,y0)legend(linear,cubic,spline,nearest, 樣本點(diǎn),原函數(shù))34/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis例 取節(jié)點(diǎn)x0=0,x1=1,對(duì)函數(shù)y=e-x 建立線性插值多項(xiàng)式.解: 構(gòu)造插值基函數(shù)為 可得線性插值多項(xiàng)式函數(shù)y=e-x滿足定理2的條件，則對(duì)

20、任意x總存在一點(diǎn) 0，1，使得2.3 拉格朗日插值方法35/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis例 取節(jié)點(diǎn)x0=0,x1, x2=1，對(duì)函數(shù) y=e-x 建立拋物插值多項(xiàng)式.解: 構(gòu)造插值基函數(shù)為 可得二次插值多項(xiàng)式2.3 拉格朗日插值方法36/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis函數(shù)y=e-x滿足定理3的條件，則對(duì)任意x總存在一點(diǎn) 0，1，使得拋物插值誤差相對(duì)線性插值誤差減小了一個(gè)數(shù)量級(jí)！2.3 拉格朗日插值方法37/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程

21、數(shù)值分析 Numerical Analysis2.3 拉格朗日插值方法滿足余項(xiàng)估計(jì)式(2.14)的使用條件知道被插值函數(shù)后驗(yàn)誤差估計(jì)38/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.3 拉格朗日插值方法當(dāng) 與 比較接近，且 連續(xù)且變化不大時(shí)，可以認(rèn)為： 后驗(yàn)誤差估計(jì)39/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.3 拉格朗日插值方法則有整理得稱為插值余項(xiàng)的事后估計(jì)式.后驗(yàn)誤差估計(jì)40/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analys

22、is2.3 拉格朗日插值方法例試用線性插值法計(jì)算 的值，并用事后估計(jì)式估計(jì)誤差。解:用結(jié)點(diǎn) 作線性插值，經(jīng)計(jì)算得 再用結(jié)點(diǎn) 作線性插值，經(jīng)計(jì)算得 后驗(yàn)誤差估計(jì)41/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis由事后估計(jì)式得將誤差估計(jì)值加到 中去，可得修正后的近似值2.3 拉格朗日插值方法后驗(yàn)誤差估計(jì)42/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis它作為精確值 的近似值具有四位有效數(shù)字，而 只有三位有效數(shù)字。注：利用后驗(yàn)誤差改進(jìn)計(jì)算結(jié)果的技術(shù)稱為超收斂技術(shù)，在數(shù)值計(jì)算計(jì)算中效果良好。2.

23、3 拉格朗日插值方法后驗(yàn)誤差估計(jì)43/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.4 牛頓插值Lagrange插值多項(xiàng)式的插值基函數(shù)形式復(fù)雜,計(jì)算量大,且重復(fù)計(jì)算很多！并且，當(dāng)增加一個(gè)節(jié)點(diǎn)時(shí)，所有基函數(shù)需要重新計(jì)算。由線性空間的知識(shí),任何一個(gè)n次多項(xiàng)式都可表示成共n+1個(gè)多項(xiàng)式的線性組合.可否將這n+1個(gè)多項(xiàng)式作為插值基函數(shù)呢？答案是肯定的。44/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.4 牛頓插值設(shè)插值多項(xiàng)式P(x)具有如下形式Newton插值公式45/168鄭州大學(xué)201

24、5-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.4 牛頓插值則由插值條件可知P(x)滿足再繼續(xù)下去，待定系數(shù)的形式將更復(fù)雜。46/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.4 牛頓插值差商的定義和性質(zhì)定義2.4.1.稱是f(x)關(guān)于點(diǎn)x0,x1的一階差商。是f(x)關(guān)于點(diǎn)x0,x1,x2的二階差商。設(shè)函數(shù) f(x)在互異的節(jié)點(diǎn)xi處有定義，47/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.4 牛頓插值差商的定義和性質(zhì)一般地，k階差商 定義為：f

25、(x)關(guān)于點(diǎn)xi的0階差商。48/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.4 牛頓插值差商的定義和性質(zhì)性質(zhì)1 k階差商 可表成節(jié)點(diǎn)上函數(shù)值 的線性組合，即 上式可用歸納法證明。例如,k =2時(shí)有 49/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.4 牛頓插值差商的定義和性質(zhì)性質(zhì)2 各階差商具有對(duì)稱性, 即改變差商中節(jié)點(diǎn)的次序不會(huì)改變差商的值。設(shè) 為 的任一排列, 則此性質(zhì)的證明由性質(zhì)(1)可得。例如50/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numer

26、ical Analysis2.4 牛頓插值差商的定義和性質(zhì)性質(zhì)3 若f(x)為n次多項(xiàng)式，則一階差商 為n-1次多項(xiàng)式。 由定義令 ,則分子為0, 說明分子中含有因子 ,與分母約去公因子可得n-1次多項(xiàng)式。51/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.4 牛頓插值差商的定義和性質(zhì)性質(zhì)4 若f(x)在區(qū)間a,b上存在n+1階導(dǎo)數(shù)， ,固定 , 則n+1階差商與導(dǎo)數(shù)之間存在如下關(guān)系：52/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.4 牛頓插值差商的計(jì)算53/168鄭州大學(xué)201

27、5-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.4 牛頓插值k xk f (xk) 一階差商 二階差商 三階差商 n 階差商0 x0 f (x0)1 x1 f (x1) f x0, x12 x2 f (x2) f x1, x2 f x0, x1, x23 x3 f (x3) f x2, x3 f x1, x2, x3 f x0, x1, x2, x3 n xn f (xn) f xn 1, xn f xn 2, xn 1, xn f xn 3, xn f x0, x1, , xnN階差商表54/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Nu

28、merical Analysis2.4 牛頓插值差商的計(jì)算例2.4.1 設(shè) f (x)經(jīng)過點(diǎn)(2, 17), (0, 1), (1, 2), (2, 19)求 f (x)關(guān)于節(jié)點(diǎn)-2,0,1,2的三階差商。k xk f (xk) 一階差商 二階差商 三階差商0 2 171 0 1 82 1 2 1 33 2 19 17 8 5/4解：列出差商表則， f -2,0=-8, f -2,0,1=3, f -2,0,1,2=5/4.55/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.4 牛頓插值線性插值給定兩個(gè)插值點(diǎn)(x0, f (x0), (x

29、1, f (x1), x0 x1, 設(shè) P1(x) = a0 + a1(x x0) 直線的點(diǎn)斜式代入插值點(diǎn)得， 線性Newton插值公式由插值的唯一性知，P1(x)與 Lagrange插值多項(xiàng)式為同一多項(xiàng)式，只是表達(dá)形式不同而已。56/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.4 牛頓插值二次插值 給定三個(gè)互異插值點(diǎn)(xi, f (xi), i =0,1,2, 設(shè) 代入插值條件： P2(xi) = f (xi), i =0,1,2, 得57/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analys

30、is2.4 牛頓插值二次插值二次Newton插值公式為58/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.4 牛頓插值n次插值給定n+1個(gè)插值點(diǎn)(xi, f(xi), i = 0, 1, 2, n, xi互異，類似地，由二階至 n 階差商的定義得上述所有n +1個(gè)等式相加，得59/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.4 牛頓插值n次插值n次Newton插值公式其中Pn(x)為n次Newton插值公式60/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Nume

31、rical Analysis2.4 牛頓插值n次插值n次Newton插值公式的插值誤差為容易驗(yàn)證，Newton插值滿足插值條件： Pn(xi) = f (xi), i = 0, 1, 2, n.61/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.4 牛頓插值n次插值關(guān)于Lagrange插值和Newton插值的幾點(diǎn)說明 1.由插值的唯一性,兩種方法的Pn(x)相同.因此，它們的誤差也相同,即當(dāng)f (x)Cn+1a, b時(shí)，有故得差商的性質(zhì)462/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysi

32、s2.4 牛頓插值n次插值 2.牛頓插值的誤差不要求函數(shù)的高階導(dǎo)數(shù)存在，所以更具有一般性。它對(duì) f(x)是由離散點(diǎn)給出的函數(shù)情形或 f(x)的導(dǎo)數(shù)不存在的情形均適用。 3.Newton插值具有承襲性質(zhì)，即 4.Newton插值公式的計(jì)算量 乘：1+2+ (n1)+ n = n(n+1)/2 除：n + (n1)+ 2+1 = n(n+1)/263/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.4 牛頓插值n次插值 5.引入記號(hào): w0(x) = 1, w1(x) = x x0, w2(x) = (x x0)(x x1), , wn(x)

33、= (x x0)(x x1) (x xn1)，于是n次Newton插值公式可表為稱 w0(x), w1(x), w2(x), , wn(x) 為Newton插值的基函數(shù)64/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.4 牛頓插值n次插值 且滿足如下關(guān)系 wi(x) = wi1(x)(x xi1), i =1,2, n； wi(xj) = 0， j k g(j)=(g(j)-g(j-1)/(x(j)-x(j-k) j=j-1; endend for i=1:m v(i)=y(1); w=1; for k=2:n w=w*(u(i)-x(

34、k-1); v(i)=v(i)+w*g(k); endend74/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.4 牛頓插值n次插值75/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.5 分段線性插值從插值余項(xiàng)的表達(dá)式看到，插值多項(xiàng)式和被插值函數(shù)逼近的程度與插值節(jié)點(diǎn)的數(shù)目、位置和a,b長(zhǎng)度均有關(guān)例2.5.0 設(shè)函數(shù)f(x)在閉區(qū)間a,b上連續(xù)，在(a,b)內(nèi)具有二階導(dǎo)數(shù)，如果當(dāng)x在(a,b)時(shí)，有f”(x)|=x(j) & (u(i)x(j+1) k=j; end end s=u(i

35、)-x(k); v(i)=y(k)+s*delta(k);end93/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.6 Hermite插值拉格朗日插值和牛頓插值 插值函數(shù)與被插值函數(shù)在節(jié)點(diǎn)上的函數(shù)值相等Hermite插值 插值函數(shù)與被插值函數(shù)在節(jié)點(diǎn)上的函數(shù)值相等。 插值函數(shù)與被插值函數(shù)在節(jié)點(diǎn)上的某階導(dǎo)數(shù)值相等。 插值多項(xiàng)式具有更好的光滑性，夠使插值函數(shù)近似程度更好。 94/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.6 Hermite插值 設(shè) f (x)具有一階連續(xù)導(dǎo)數(shù)，已知節(jié)點(diǎn)x

36、i上的函數(shù)值和導(dǎo)數(shù)值，即 (xi, f (xi), (xi, f (xi), i = 0, 1, 2, , n, 若存在 2n+1次多項(xiàng)式 H2n+1(x) 滿足 則稱 H2n+1(x) 為 f (x) 關(guān)于節(jié)點(diǎn)xi (i = 0,1,2,n)的Hermite插值多項(xiàng)式。 記 f (xi) = yi, f (xi) = mi, i = 0,1,2,n .問題描述95/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.6 Hermite插值 給定 f (xi) = yi , f (xi) = mi , i = 0, 1. 設(shè) 代入插值條件: H

37、3(xi) = f (xi), H3(xi) = f (xi), i =0,1. 得其解存在唯一, 解 出 a0, a1, a2, a3, 代入即得 H3(x).三次Hermite插值96/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.6 Hermite插值問題: 如何構(gòu)造節(jié)點(diǎn)插值基函數(shù)？分析基函數(shù)取值：三次Hermite插值 因?yàn)槊總€(gè)節(jié)點(diǎn)對(duì)應(yīng)兩個(gè)插值條件，因此每個(gè)節(jié)點(diǎn)對(duì)應(yīng)兩個(gè)插值基函數(shù)。 節(jié)點(diǎn)x0上對(duì)應(yīng)的兩個(gè)基函數(shù)分別為h0(x),g0(x)， 節(jié)點(diǎn)x1上對(duì)應(yīng)的兩個(gè)基函數(shù)分別為h1(x),g1(x)，97/168鄭州大學(xué)2015-201

38、6學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.6 Hermite插值三次Hermite插值函數(shù)的的形式三次Hermite插值98/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.6 Hermite插值三次Hermite插值表99/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.6 Hermite插值三次Hermite插值四個(gè)插值基函數(shù)的性質(zhì)100/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.6 Hermi

39、te插值三次Hermite插值101/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.6 Hermite插值三次Hermite插值102/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.6 Hermite插值三次Hermite插值103/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.6 Hermite插值三次Hermite插值104/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2

40、.6 Hermite插值例三次Hermite插值105/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.6 Hermite插值三次Hermite插值直接計(jì)算基函數(shù)可得106/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.6 Hermite插值三次Hermite插值于是有由此得到而 ，107/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.6 Hermite插值三次Hermite插值function v=hermite3(x,y,m,

41、u)k=length(u);v=zeros(size(u);h=0 0;g=0 0;for i=1:k v(i)=0; h(1)=(1-2*(u(i)-x(1)/(x(1)-x(2)*(u(i)-x(2)/(x(1)-x(2)2; h(2)=(1-2*(u(i)-x(2)/(x(2)-x(1)*(u(i)-x(1)/(x(2)-x(1)2; g(1)=(u(i)-x(1)*(u(i)-x(2)/(x(1)-x(2)2; g(2)=(u(i)-x(2)*(u(i)-x(1)/(x(2)-x(1)2; v(i)=v(i)+y(1)*h(1)+y(2)*h(2)+m(1)*g(1)+m(2)*g(2

42、);end108/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.6 Hermite插值三次Hermite插值三次Hermite插值誤差定理定理109/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.6 Hermite插值三次Hermite插值例110/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.6 Hermite插值三次Hermite插值111/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical A

43、nalysis2.6 Hermite插值三次Hermite插值112/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.6 Hermite插值分段三次Hermite插值分段插值的優(yōu)點(diǎn)能有效的克服榮格現(xiàn)象。容易構(gòu)造每個(gè)插值節(jié)點(diǎn)上的插值基函數(shù)。 構(gòu)造的算法容易在計(jì)算機(jī)上實(shí)現(xiàn)。113/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.6 Hermite插值分段三次Hermite插值114/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.6 He

44、rmite插值將n重節(jié)點(diǎn)看成n個(gè)獨(dú)立的點(diǎn)，按Newton插值公式直接寫出Newton法構(gòu)造Hermite插值將n重節(jié)點(diǎn)的差商：由差商與導(dǎo)數(shù)之間的關(guān)系因此，可以通過構(gòu)造差商表直接寫出。例：115/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.6 Hermite插值分段三次Hermite插值116/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.6 Hermite插值分段三次Hermite插值構(gòu)造插值基函數(shù)的思路 117/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Num

45、erical Analysis2.6 Hermite插值分段三次Hermite插值構(gòu)造插值基函數(shù)的思路 118/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.6 Hermite插值分段三次Hermite插值119/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.6 Hermite插值分段三次Hermite插值120/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.6 Hermite插值分段三次Hermite插值121/168鄭州大學(xué)

46、2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.6 Hermite插值分段三次Hermite插值分段三次Hermit插值函數(shù)的形式是122/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.6 Hermite插值分段三次Hermite插值誤差定理定理123/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.6 Hermite插值分段三次Hermite插值124/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analy

47、sis2.6 Hermite插值分段三次Hermite插值125/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis分段低次插值的收斂性2.6 Hermite插值分段三次Hermite插值126/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.6 Hermite插值分段三次Hermite插值127/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.6 Hermite插值分段三次Hermite插值function v=piecehermite3

48、(x,y,m,u)k=length(u);v=zeros(size(u);t=length(x);piece=(k-1)/(t-1);partv=zeros(piece+1);for i=1:t-1 partx=x(i) x(i+1); party=y(i) y(i+1); partm=m(i) m(i+1); partu=x(i):(x(i+1)-x(i)/piece:x(i+1); partv=hermite3(partx,party,partm,partu); v(i-1)*piece+1:i*piece+1)=partv;end128/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程

49、 數(shù)值分析 Numerical Analysis 上面介紹的分段低次插值，雖然具有計(jì)算簡(jiǎn)便，收斂性有保證，數(shù)值穩(wěn)定性又好且易在計(jì)算機(jī)上實(shí)現(xiàn)等優(yōu)點(diǎn)，但它卻不能保證整條曲線的光滑性，從而不能滿足某些工程技術(shù)上的要求。從六十年代開始，首先由于航空、造船等工程設(shè)計(jì)的需要而發(fā)展起來的樣條插值(spline)方法，既保留了分段低次插值的各種優(yōu)點(diǎn)，又提高了插值函數(shù)的光滑性，在許多領(lǐng)域有越來越廣泛的應(yīng)用。2.7 樣條插值函數(shù) 129/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.7 樣條插值函數(shù) 分段線性插值構(gòu)造了一個(gè)整體連續(xù)的函數(shù)；分段三次Hermit

50、e插值構(gòu)造了一個(gè)整體上具有一階連續(xù)導(dǎo)數(shù)的函數(shù)。 實(shí)際問題中，給出插值節(jié)點(diǎn)上的函數(shù)值比較方便，而給出插值節(jié)點(diǎn)上的導(dǎo)數(shù)值會(huì)比較困難。? 能否在只給出節(jié)點(diǎn)函數(shù)值的情況下，構(gòu)造一個(gè)整體上光滑性比較好的插值函數(shù)呢？ 樣條插值130/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.7 樣條插值函數(shù) 樣條這一名稱來自于工程實(shí)踐活動(dòng) 樣條插值131/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.7 樣條插值函數(shù) 樣條插值132/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numeri

51、cal Analysis2.7 樣條插值函數(shù) 樣條插值定義133/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.7 樣條插值函數(shù) 樣條插值定義134/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.樣條插值條件分析2.7 樣條插值函數(shù) 135/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.7 樣條插值函數(shù) 樣條插值136/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.7 樣條

52、插值函數(shù) 樣條插值條件137/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.7 樣條插值函數(shù) 樣條插值條件138/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.7 樣條插值函數(shù) 樣條插值條件139/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.7 樣條插值函數(shù) 樣條插值140/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.7 樣條插值函數(shù) 三彎矩插值法141/168鄭州大學(xué)

53、2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.7 樣條插值函數(shù) 三彎矩插值法142/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis2.7 樣條插值函數(shù) 三彎矩插值法143/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis三彎矩插值法2.7 樣條插值函數(shù) 144/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis三彎矩插值法2.7 樣條插值函數(shù) 145/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)

54、值分析 Numerical Analysis三彎矩插值法2.7 樣條插值函數(shù) 146/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis三彎矩插值法2.7 樣條插值函數(shù) 147/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis（2）構(gòu)造三彎矩方程三彎矩插值法2.7 樣條插值函數(shù) 148/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis三彎矩插值法2.7 樣條插值函數(shù) 149/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis三彎矩插值法2.7 樣條插值函數(shù) 150/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis三彎矩插值法2.7 樣條插值函數(shù) 151/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Numerical Analysis三彎矩插值法2.7 樣條插值函數(shù) 152/168鄭州大學(xué)2015-2016學(xué)年碩士研究生課程 數(shù)值分析 Num