1、计算方法第四章插值方法计算方法第四章插值方法4 插值方法插值方法4.1 1多项式插值问题的一般提法多项式插值问题的一般提法 4.2 拉格朗日拉格朗日(Lagrange)插值插值4.3 差商与差分及其性质差商与差分及其性质4.4 牛顿插值公式牛顿插值公式 4.5 分段插值法分段插值法4.6曲线拟合的最小二乘法曲线拟合的最小二乘法4.0 引言引言 插值法是广泛应用于理论研究和生产实践的重插值法是广泛应用于理论研究和生产实践的重要数值方法要数值方法,它是用简单函数它是用简单函数(特别是多项式或分特别是多项式或分段多项式段多项式)为各种离散数组建立连续模型；为各种为各种离散数组建立连续模型；为各种非有
2、理函数提供好的逼近方法。众所周知，反映非有理函数提供好的逼近方法。众所周知，反映自然规律的数量关系的函数有三种表示方法：自然规律的数量关系的函数有三种表示方法：解析表达式52)(3xxxfyyxsin 图象法 表格法4.0 引言引言 许多数据都是用表格法给出的许多数据都是用表格法给出的(如观测和实验而得到的函数如观测和实验而得到的函数数据表格数据表格)，可是，从一个只提供离散的函数值去进行理论，可是，从一个只提供离散的函数值去进行理论分析和进行设计，是极不方便的分析和进行设计，是极不方便的,甚至是不可能的。因此需甚至是不可能的。因此需要设法去寻找与已知函数值相符，并且形式简单的插值函要设法去寻
3、找与已知函数值相符，并且形式简单的插值函数数(或近似函数或近似函数)。另外一种情况是，函数表达式完全给定，但其形式不适宜另外一种情况是，函数表达式完全给定，但其形式不适宜计算机使用，因为计算机只能执行算术和逻辑操作，因此计算机使用，因为计算机只能执行算术和逻辑操作，因此涉及连续变量问题的计算都需要经过离散化以后才能进行。涉及连续变量问题的计算都需要经过离散化以后才能进行。如数值积分方法、数值微分方法、差分方程以及有限元法如数值积分方法、数值微分方法、差分方程以及有限元法等，都必须直接或间接地应用到插值理论和方法等，都必须直接或间接地应用到插值理论和方法。4.1 多项式插值问题的一般提法多项式插
4、值问题的一般提法 当精确函数当精确函数 y=f(x)非常复杂或未知时，在一系非常复杂或未知时，在一系列节点列节点 x0 xn 处测得函数值处测得函数值 y0=f(x0),yn=f(xn)，由此构造一个简单易算的近似函数由此构造一个简单易算的近似函数 p(x)f(x)，满足条件，满足条件:p(xi)=f(xi)(i=0,n)。这里的这里的 p(x)称为称为f(x)的插值函数。的插值函数。最常用的插值函数是最常用的插值函数是?代数多项式、三角多项式、有理分式代数多项式、三角多项式、有理分式 插值函数插值函数 p(x)作为作为 f(x)的近似，可以选自不同类型的的近似，可以选自不同类型的函数函数,如
5、如 p(x)为代数多项式、三角多项式、有理分式；为代数多项式、三角多项式、有理分式；其函数性态可以是光滑的、亦可以是分段光滑的。其其函数性态可以是光滑的、亦可以是分段光滑的。其中，代数多项式类的插值函数占有重要地位：中，代数多项式类的插值函数占有重要地位：(a)结构简单、计算机容易处理、任何多项式的导数结构简单、计算机容易处理、任何多项式的导数和积分也易确定，并且仍是多项式。和积分也易确定，并且仍是多项式。(b)著名的著名的Weierstrass逼近定理逼近定理(定义在闭区间上的定义在闭区间上的任何连续函数任何连续函数 f(x),存在代数多项式存在代数多项式p(x)一致逼近一致逼近f(x),并
6、达到所要求的精度并达到所要求的精度)。因此，我们主要考虑代数多项式的插值问题。因此，我们主要考虑代数多项式的插值问题。x0,x1,xn 插值节点插值节点,函数函数 P(x)称为函数称为函数 y=f(x)的插值函数，的插值函数，区间区间 a,b 称为插值区间。称为插值区间。例题例题:已知函数已知函数 f(x)有如下数据有如下数据:求求 f(x)的插值多项式的插值多项式 p(x)，并求并求 f(x)在在 x=0.5 处的近似值。处的近似值。插值的几何意义插值的几何意义 从几何上看，插值就是求一条曲线从几何上看，插值就是求一条曲线 使其通过给定的使其通过给定的 个点个点 ，并且与已知曲线并且与已知曲
7、线 有一定的近似度。有一定的近似度。()yP x1n(,)iix y(0,1,)in()yf xx 0 y y=p(x)a=x0 x1 x2 x3 xn=b (xi,yi)y=f(x)曲线曲线 P(x)近似近似 f(x)要数值方法,它是用简单函数(特别是多项式或分sin 50=0.a=x0 x1 x2 x3 xn=b埃尔米特插值的一般提法解:在每个分段区间自然规律的数量关系的函数有三种表示方法：但如能求出 ，那么用 逼近71428 有3 位有效数字.以如下数据构建埃尔米特插值Lagrange插值多项式代数多项式、三角多项式、有理分式利用Lagrange插值法有已知连续函数f(x)的函数表如下：
8、Lagrange插值法20 世纪初，Runge就给出了一个等距节点插值多项式5，利用牛顿法求解可得 f(x)在(-1,2)内的近似根插值方法的研究问题插值方法的研究问题（1）满足插值条件的）满足插值条件的P(x)是否存在唯一？是否存在唯一？（2）若满足插值条件的）若满足插值条件的P(x)存在，如何构造存在，如何构造P(x)？（3）如何估计用）如何估计用P (x)近似替代近似替代 f(x)产生的误差？产生的误差？x 0 y y=p(x)a=x0 x1 x2 x3 xn=b (xi,yi)y=f(x)曲线曲线 P(x)近似近似 f(x)求求 n 次多项式次多项式 使得使得:nnnxaxaaxP 1
9、0)(条件：无重合节点，即条件：无重合节点，即jixx ji 4.2 拉格朗日多项式拉格朗日多项式 /*Lagrange Polynomial*/根据插值条件，有：根据插值条件，有：nnnnnnnnnnyxaxaaxPyxaxaaxPyxaxaaxP10111101000100)()()(其系数矩阵的行列式为其系数矩阵的行列式为nnnnnnnxxxxxxxxxV111),(110010(),0,1,niipxyinVandermonde行列式行列式),2,1(nixi0)(),(010nijjinnxxxxxVnaaa,10注意到插值节点注意到插值节点两两相异，而两两相异，而故方程组故方程组(
10、1)(1)有惟一解有惟一解于是满足插值条件的多项式存在且惟一。于是满足插值条件的多项式存在且惟一。nxxx,10nnnxaxaaxP10)(iinyxP)(由由n+1个不同插值节点个不同插值节点可以惟一确定一个可以惟一确定一个n次多项式次多项式满足插值条件满足插值条件(唯一性唯一性)ReturnReturnn=1已知已知 x0,x1;y0,y1，求，求101()Lxaa x=+使得使得111001)(,)(y1x1Ly0 x0L 可见可见 L1(x)是过是过(x0,y0)和和(x1,y1)两点的直线。两点的直线。l0(x)l1(x)4.2 拉格朗日多项式拉格朗日多项式 /*Lagrange P
11、olynomial*/线性插值线性插值基函数基函数1.构造线性插值基函数的方法构造线性插值基函数的方法:iiiyxlyxxxxyxxxxxxxxyyyxL)()()(10101001010010101线性插值与其基函数示意图线性插值与其基函数示意图xy0 0()yy lx1 1()yy l x0 x1xO10 01 1()()()L xy lxy l x0 x1xxy0y1y()yf x1()yL xO显然显然,是过是过 、三点的一条三点的一条抛物线。抛物线。),(11yx),(22yx已知已知 ,求求 ，n=2)(2xL使得使得200211222()()()L xyL xyL xy=2()L
12、 x00(,)xy210210,yyyxxx以如下数据构建埃尔米特插值其中,.并且与已知曲线 有一定的近似度。其matlab的lagrange.解：利用Lagrange插值法有在a,b内存在,截断误差(或插值余项):，%lagrange.解:在每个分段区间Lagrange插值法不变算子 I、移位算子 EP(x)应满足插值条件：04705882352941可见 L1(x)是过(x0,y0)和(x1,y1)两点的直线。显然,是过 、三点的一条抛物线。a=x0 x1 x2 x3 xn=b可以惟一确定一个n次多项式047058823529412 拉格朗日多项式 /*Lagrange Polynomia
13、l*/显然显然,是过是过 、三点的一条三点的一条抛物线。抛物线。),(11yx),(22yx已知已知 ,求求 ，n=2210210,yyyxxx)(2xL使得使得200211222()()()L xyL xyL xy=仿照线性插值基函数的构造方法，令仿照线性插值基函数的构造方法，令)()()()()()()()()(120210221012012010210 xxxxxxxxxlxxxxxxxxxlxxxxxxxxxl抛物线基抛物线基函数函数2()Lx称其为抛物线插值基函数称其为抛物线插值基函数(如上右图所示如上右图所示)。2()L x00(,)xy)()()()()()()()()(1202
14、10221012012010210 xxxxxxxxxlxxxxxxxxxlxxxxxxxxxl抛物线插值基函数抛物线插值基函数于是于是抛物线基函数抛物线基函数020112201201021012202120()()()()()()()()()()()()()()iiixxxxxxxxxx xxL xyyyxx xxxxxxxxxxl x y=-=+-=希望找到希望找到 li(x)，i=0,n 使得使得 li(xj)=ij；然后令；然后令，则显然有，则显然有 Pn(xi)=yi。每个每个 li 有有 n 个根个根 x0,xi ,xn一般情形一般情形)()()()()()()()()(11011
15、0nkkkkkknkkkxxxxxxxxxxxxxxxxxl ，k=0,1,n.,)()()()()(110nkkkxxxxxxxxAxl 令令k=0,1,n.0111()()()()knkkkkkAxxxxxxxx()1,kkl x由由 得得:0()()）nnkkkLxfxlx0()()）nnkkkLxfxlx设设 函数表函数表 则满足插值条件的多项式则满足插值条件的多项式（Lagrange）插值多项式）插值多项式 nkkknxlxfxL0)()(）()yf x,(,(,()(0 1.),ijiixxxf xinij()()(0,1.)，niiLxf xin其中其中,.,.0()(0,1,.
16、)njkjkjjkxxlxknxx以下的问题：如何分析插值的余项？以下的问题：如何分析插值的余项？(1)(1)先求插值基函数先求插值基函数.(2)(2)构造插值多项式构造插值多项式.构造插值多项式的方法：构造插值多项式的方法：x -1 0 1 2f(x)-2 -2 1 2 已知连续函数已知连续函数 f(x)的函数表如下：的函数表如下：求方程求方程 f(x)=0 在在(-1,2)内的近似根。内的近似根。例题例题解：解：利用利用Lagrange插值法有插值法有 取初值取初值x=0.5，利用牛顿法求解可得，利用牛顿法求解可得 f(x)在在(-1,2)内的近似根内的近似根为为0.67433。32591
17、412 0 xxx解方程解方程x -1 0 1 2f(x)-2 -2 1 2 已知连续函数已知连续函数f(x)的函数表如下：的函数表如下：求方程求方程 f(x)=0 在在(-1,2)内的近似根。内的近似根。例题例题30121122210111201 01 021211122 1 121 20 21xxxxxxL xxx xxx x()()()()()()()()()()()()()()()()()()()()()()()-+-=-+-+-+-+-+-+-3215914126xxx=-+-，且，且 f 满足条件满足条件 ,Lagrange插值法插值余项插值法插值余项设节点设节点)1(nf在在a,
18、b内存在内存在,考察截断误差考察截断误差:)()()(xLxfxRnn ,baCfn bxxxan 10在该区间 上取 个等距节点,构造 的 次 拉格朗日插值多项式为内插/*interpolation*/的实际误差 0.Lagrange插值法于是,已知连续函数f(x)的函数表如下：称其为抛物线插值基函数(如上右图所示)。for j=1:n用线性插值及抛物线插值计算这样 可表示为：性质2：差商关于所含节点是对称的，即：4 万物？全部信息量?!其中 是正整数，寻求一个次数尽可能低的多f(x)-2 -2 1 2，且 f 满足条件 ,从几何上看，插值就是求一条曲线可以惟一确定一个n次多项式当认识到这一
19、点时，在数直线应该与所有点靠得比较近一般地，关于 的 n 阶差商:(a)结构简单、计算机容易处理、任何多项式的导数和积分也易确定，并且仍是多项式。已知 的函数表，求4 次牛顿插值多项式,Lagrange插值法的插值余项插值法的插值余项 ，且，且 f 满足条件满足条件 ,设节点设节点)1(nf在在a,b内存在内存在,截断误差截断误差(或插值余项或插值余项):,baCfn bxxxan 10(1)1()()()()()(1)!nnnnfRxfxLxxn,(,)a b Lagrange插值法的插值余项插值法的插值余项 ，且，且 f 满足条件满足条件 ,设节点设节点)1(nf在在a,b内存在内存在,截
20、断误差截断误差(或插值余项或插值余项):,baCfn bxxxan 10(1)1()()()()()(1)!nnnnfRxfxLxxn,(,)a b证明：由已知条件得到：证明：由已知条件得到：()0,0,1,nkR xkn于是有：于是有：011()()()()()()()nnnR xk x x xx xx xkxx其中其中 是与是与 x 有关的待定函数。有关的待定函数。()k x任意固定任意固定 x xi (i=0,n),考察考察01()()()()()()()nntf tL tk x txtxtx根据插值条件及余项定义，可知根据插值条件及余项定义，可知()t在点在点01,nxxxx故故处均为
21、零，处均为零，在在()t,a b上有上有n+2个个零点，根据个个零点，根据 Roll 定理定理 在在 的每两个零点间至少有一个零点，故的每两个零点间至少有一个零点，故在在 内至少有内至少有 一一 个零点，对个零点，对 再用再用Roll 定理，可定理，可知知 在在 内至少有内至少有 n 个零点，依此类推，个零点，依此类推，在在 内至少有一个零点，记为内至少有一个零点，记为()t()t()t,a b()t()t,a b(1)()nt,a b(,)a b使得使得:(1)(1)()()(1)!()0nnfnk x(1)()(),(,)(1)!nfk xa bn由于由于 是不能确定，因此我们并不能确定误
22、差的大小是不能确定，因此我们并不能确定误差的大小但如能求出但如能求出 ，那么用，那么用 逼近逼近 的截断误差限是：的截断误差限是：当当 时，时，当当 时时()nL x()f x1n 12010111()()()()()(),22R xfxfxxxxx x 2n 230120211()()()()()()(),66,R xfxfxxxxxxx x(1)1()nnaxbm ax fxM11()()(1)!nnnMRxxn当当 f(x)为任一个次数为任一个次数 n 的多项式时，的多项式时，,可知，可知，即插值多项式对于次数即插值多项式对于次数 n 的的多项式是精确的。多项式是精确的。0)()1(xf
23、n0)(xRn注意注意 给定给定 xi=i+1,i=0,1,2,3,4,5.下面哪个是下面哪个是 l2(x)的图像？的图像？问题问题算例算例1 1LagrangeLagrange插值法插值法已知已知 ，用线性插值及抛物线插值计算用线性插值及抛物线插值计算 的值并估计截断误差。的值并估计截断误差。sin0.320.314567sin0.340.333487sin0.360.352274sin0.3367算例算例1 1LagrangeLagrange插值法插值法已知已知 ，用线性插值及抛物线插值计算用线性插值及抛物线插值计算 的值并估计截断误差。的值并估计截断误差。sin0.320.314567s
24、in0.340.333487sin0.360.352274sin0.33670120.320.340.36xxx0120.3145670.3334870.352274yyy线性插值时取线性插值时取 解解:010.32,0.34xx1sin0.3367(0.3367)0.3367 0.320.3367 0.340.3145670.3334870.34 0.320.32 0.340.330365L其截断误差为：其截断误差为：其中其中,因为因为可取可取于是：于是：2101()()(),2MR xxxxx012max()xx xMf ()sin,()sinf xx fxx0121max sinsin0
25、.3335xx xMxx 115sin0.3367(0.3367)10.3335 0.0167 0.00332(0.3367)0.92 10RL用抛物线插值时，取所有节点，得到用抛物线插值时，取所有节点，得到2sin0.3367(0.3367 0.34)(0.3367 0.36)(0.3367 0.32)(0.3367 0.36)0.3145670.333487(0.32 0.34)(0.32 0.36)(0.34 0.32)(0.34 0.36)(0.3367 0.32)(0.3367 0.34)0.352274(0.36 0.32)(0.36 0.3(0.4)0.3133674567)L4
26、440.7689 103.89 100.5511 100.3334870.3522740.00080.00040.0000.3303 487余项讨论：余项讨论：其中：其中：32012()()()(),6MRxxxxxxx0120max()cos0.828xx xMfxx 226(0.3367)sin 0.3367(0.3367)10.8280.01670.0330.023360.17810RL算例算例2 2LagrangeLagrange插值法插值法利用利用 100，121 的开方计算的开方计算 .由于由于:解解:115利用利用Lagrange插值法有插值法有 1110012110010121
27、100121)(1xxxL于是于是,71428.101110012110011510121100121115)115(1151 L115的精确值为的精确值为 10.72380529,因此因此,近似值近似值 10.71428 有有3 位有效数字位有效数字.ReturnReturn4.3 差商与差分差商与差分 Lagrange 插值虽然易算，但若要增加一个节点时，插值虽然易算，但若要增加一个节点时，全部基函数全部基函数 li(x)都需重新算过。都需重新算过。寻求如下形式的插值多项式：寻求如下形式的插值多项式：01020101()()()()()()nnnP xaa xxa xxxxaxxxx其中的
28、其中的 为待定系数，由插值条件确定为待定系数，由插值条件确定.ia由线性代数的知识可知：任何一个由线性代数的知识可知：任何一个n次多项式都可以表示成次多项式都可以表示成011()()()nx xx xx x共共 n+1 个线性无关的多项式的线性组合。个线性无关的多项式的线性组合。那么，是否可以将这那么，是否可以将这 n+1 个多项式作为插值基函数呢？个多项式作为插值基函数呢？1,0,x x01()(),x x x x)()()()()(110102010nnxxxxxxaxxxxaxxaaxP设插值多项式设插值多项式P(x)具有如下形式：具有如下形式：(),0,1,iiP xfin000()P
29、 xfa)()(011011xxaafxP00fa 01011xxffa22012022021()()()()P xfaa xxaxxxx12010102022xxxxffxxffa 再继续下去再继续下去,待定系数的形式将更复杂待定系数的形式将更复杂,为此引入为此引入 差差商和差分的概念商和差分的概念.P(x)应满足插值条件：应满足插值条件：有：有：4.3.1 4.3.1 差商的概念差商的概念从零阶差商出发，归纳地定义各阶差商从零阶差商出发，归纳地定义各阶差商:称称 为函数为函数 关于点关于点 的一阶差商的一阶差商.()f x111 ,iiiiiif xf xf x xxx1,iix x 一般
30、地，一般地，关于关于 的的 k 阶差商阶差商:()f x1,iii kx xx12111,iii kiii kiii ki kif xxxf x xxf x xxxx 记函数记函数 在在 的值的值 ，称称 为为 关于关于 的零阶差商。的零阶差商。()f xix()iif xf x if xix()f x 一般地，一般地，关于关于 的的 n 阶差商阶差商:()f x01,nx xx12011010,nnnnf x xxf x xxf x xxxx n 阶差商的概念阶差商的概念差商的基本性质差商的基本性质性质性质1 1：差商可表示为函数值的线性组合，即：差商可表示为函数值的线性组合，即：性质性质2
31、 2：差商关于所含节点是对称的，即：差商关于所含节点是对称的，即：010011(),()()()()njnjjjjjjjnf xf x xxxxxxxxxx011010,nnnnf x xxf x xxf xxx可用归纳法证明差商的基本性质差商的基本性质性质性质3：性质性质4：设：设 在在 存在存在 n 阶导数，且阶导数，且 则则 ，使得，使得:12011011,imiimmif xxxf x xxf xxxxx()01(),!nnff x xxn(,)a b()f x,a b,jxa b差商的计算差商的计算-差商表差商表一阶差商一阶差商 二阶差商二阶差商三阶差商三阶差商四阶差商四阶差商ix0
32、 x1x2x3x4x()if x1()f x2()f x3()f x4()f x0()f x01,f x x12,f x x23,f x x34,f x x012,f x x x123,f x x x234,f x x x0123,f x x x x1234,f x x x x01234,f x x x x x已知已知ix()if x计算三阶差商计算三阶差商1,2,4,7 f解：列表计算解：列表计算 ix()ifx算例算例 1,2,4,7 1/2f4.3.2 4.3.2 差分差分 在前面的讨论中，节点是任意分布的，但实际上经常遇在前面的讨论中，节点是任意分布的，但实际上经常遇到等距节点的情况，
33、这时插值公式可以得到简化，为此，我到等距节点的情况，这时插值公式可以得到简化，为此，我们先介绍差分的概念。们先介绍差分的概念。设函数设函数 在等距节点在等距节点上的值上的值 为已知，这里为已知，这里 为常数，称为步长。为常数，称为步长。()f x0(0,1,)ixxih in()iiff xh 下面来讨论差分的定义。下面来讨论差分的定义。sin 50 0.即:求 a0,a1,使误差平方和取最小值!设 是区间 上的函数，在节点 Lagrange插值法插值余项代数多项式、三角多项式、有理分式2 拉格朗日多项式 /*Lagrange Polynomial*/求方程 f(x)=0 在(-1,2)内的近
34、似根。Lagrange插值法 Lagrange插值法的插值余项由n+1个不同插值节点其中,从零阶差商出发，归纳地定义各阶差商:x0=linspace(-5,5,n+1);y0=1.解出 a0,a1,am已知连续函数f(x)的函数表如下：下表列出了 和 的值。设 是区间 上的函数，在节点在每个节点上的差异(理论上)应该为零。埃尔米特插值的一般提法为：差分的定义差分的定义记号记号分别称为分别称为 在在 处以处以 为步长的为步长的 向前差分、向后差分、中心差分向前差分、向后差分、中心差分符号符号 、分别称为向前差分算子、向后差分算子、分别称为向前差分算子、向后差分算子、中心差分算子中心差分算子.1i
35、iifff1iiifff1122()()22iiiiihhff xf xff()f xixh高阶差分高阶差分用一阶差分可以定义二阶差分用一阶差分可以定义二阶差分一般地可定义一般地可定义 m 阶差分为：阶差分为：中心差分定义为中心差分定义为:以此类推。以此类推。21212iiiiiiffffff 111mmmiiifff 111mmmiiifff121iiifff 121iiifff 11222iiifff 不变算子不变算子 I、移位算子、移位算子 E定义定义从而可得：从而可得：于是得到：于是得到：同理，由于：同理，由于：得到：得到：由于：由于：得到：得到：由差分的定义及不变算子和移位算子有如下
36、性质由差分的定义及不变算子和移位算子有如下性质:kkIff1kkEff1()kkkkkkfffEfIfEI fEI 1IE 1122EE111()kkkkkkfffIfEfIEf111122221122()kkkkkkfffE fEfEEf差分的性质差分的性质性质性质1 1：各阶差分均可用函数值表示，如：各阶差分均可用函数值表示，如：性质性质2 2：某点的函数可用各阶差分来表示：某点的函数可用各阶差分来表示：00()(1)(1)nnnnjnjjkkkk njjjnnfEIfEffjj 100()(1)(1)nnnnn jj nn jkkkk j njjnnfIEfEffjj 00()nnnnj
37、jn kkkkkjjnnfE fIfffjj 性质性质3 3：差商与差分有如下关系：差商与差分有如下关系：性质性质4 4：差分与导数有如下关系：差分与导数有如下关系：111,(1,2,)!mkkk mkmf xxxfmnm h11 1,(1,2,)!mkkk mkmf x xxfmnm h()(),(,)nnnkkk nfh fxx差分的计算差分的计算kf()22()33()44()0f1f2f3f4f23()ff34()ff01()ff12()ff2224()ff2202()ff2213()ff3314()ff3303()ff4404()ffReturnReturn4.4 牛顿插值公式牛顿插
38、值公式根据差商的定义，把根据差商的定义，把 看成看成 上的一点，上的一点，可得：可得：x,a b000()(),()f xf xf x xxx001011,()f x xf x xf x x xxx010101,()nnnnf x xxf x xxf x x xxxx4.4 牛顿插值公式牛顿插值公式根据差商的定义，把根据差商的定义，把 看成看成 上的一点，上的一点，可得：可得：x,a b000()(),()f xf xf x xxx001011,()f x xf x xf x x xxx010101,()nnnnf x xxf x xxf x x xxxx0010()(),()f xf xf
39、x xxx01201,()()f x x xxxxx0101,()()nnf x xxxxxx011,()()()nnnnf x x xxxNxR x把后一式代入前一式把后一式代入前一式其中其中 显然显然 满足插值条件，且次数不超过满足插值条件，且次数不超过 ,它就它就是插值多项式，其系数为：是插值多项式，其系数为：我们称我们称 为牛顿插值多项式为牛顿插值多项式.0010()(),()nNxf xf x xxx01201,()()f x x xxxxx0101,()()nnf x xxxxxx01101()()()(1()()(),()!nnnnnnR xf xNxf x x xxxfxxxx
40、n ()nNxn01,iiaf x xx0,1,in()nNx()f x 已知已知 的函数表，求的函数表，求4 次牛顿插值多项式次牛顿插值多项式,并求并求算例算例(0.596).f从表中可以看到从表中可以看到4 阶差商阶差商几乎为几乎为0 0，故取，故取4 4次插值多项式即可，次插值多项式即可，于是：于是：0.400.400.410750.410750.550.550.578150.578151.116001.116000.650.650.696750.696751.186001.186000.280000.280000.800.800.888110.888111.275731.275730.
41、358930.358930.197330.197330.900.901.026521.026521.384101.384100.433480.433480.213000.213000.031340.031341.051.051.253821.253821.515331.515330.524930.524930.228630.228630.031260.03126-0.00012-0.00012解：列表计算解：列表计算 4()(0.4)(0.4)(0.55)(0.4)(0.55)(0.60.41075 1.1665)(0.4)(0.55)(0.65)(0.8)0.280.197330.03134
42、N xxxxxxxxxxx 已知已知 的函数表，求的函数表，求4 次牛顿插值多项式次牛顿插值多项式,并求并求算例算例(0.596).f()f x4(0.596)(0.596)0.63192fN0.400.400.410750.410750.550.550.578150.578151.116001.116000.650.650.696750.696751.186001.186000.280000.280000.800.800.888110.888111.275731.275730.358930.358930.197330.197330.900.901.026521.026521.384101.3
43、84100.433480.433480.213000.213000.031340.031341.051.051.253821.253821.515331.515330.524930.524930.228630.228630.031260.03126-0.00012-0.00012解：列表计算解：列表计算 已知已知 的函数表，求的函数表，求4 次牛顿插值多项式次牛顿插值多项式,并求并求算例算例(0.596).f()f x截断误差为：截断误差为：40459(),(0.596)3.63 10R xf xx4()(0.4)(0.4)(0.55)(0.4)(0.55)(0.60.41075 1.1665
44、)(0.4)(0.55)(0.65)(0.8)0.280.197330.03134N xxxxxxxxxxx4(0.596)(0.596)0.63192fN 和和 均是均是 n 次多项式次多项式,且均满足插值条件且均满足插值条件:由多项式的唯一性由多项式的唯一性,因而因而,两个公式两个公式的余项是相等的的余项是相等的,即即 当插值多项式从当插值多项式从 n-1 次增加到次增加到 n 次时次时,拉格朗日型插值必须重新计算所有的基本插值多项式拉格朗日型插值必须重新计算所有的基本插值多项式;而对于牛顿型插值而对于牛顿型插值,只需用表格再计算一个只需用表格再计算一个 n 阶差商阶差商,然后加上一项即可
45、。然后加上一项即可。牛顿插值公式和牛顿插值公式和Lagrange插值公式比较插值公式比较()nL x()nNx ()()(),0,1,niniiL xNxf xin()()nnLxNx(1)01(),()()(1)!nnnnff x x xxxxn ReturnReturn在区间 a,b 上用插值多项式 P 逼近函数 f 时，f 和Pf(x)-2 -2 1 2从表中可以看到4 阶差商几乎为0，故取4次插值多项式即可，x0=linspace(-5,5,n+1);y0=1.解:在每个分段区间其函数性态可以是光滑的、亦可以是分段光滑的。函数,如 p(x)为代数多项式、三角多项式、有理分式；共 n+1
46、 个线性无关的多项式的线性组合。而对于牛顿型插值,只需用表格再计算一个 n 阶差商,Lagrange插值多项式设 函数表内插/*interpolation*/的实际误差 0.可以惟一确定一个n次多项式节点（如下表），求区间上分段线性插值函数，并利用求出 a0,a1函数 P(x)称为函数 y=f(x)的插值函数，根据插值条件及余项定义，可知上的值 为已知，这里 为常数，称为步长。由于 是不能确定，因此我们并不能确定误差的大小说明:并不是插值多项式的次数越高,插值效果越好,精度也不一定是随次数的提高而升高,这种现象在上个世纪初由Runge发现,故称为Runge现象.当 时,4.5 分段插值公式分段
47、插值公式 在区间在区间 a,b 上用插值多项式上用插值多项式 P 逼近函数逼近函数 f 时，时，f 和和P 在每个节点上的差异在每个节点上的差异(理论上理论上)应该为零。自然，我们期望应该为零。自然，我们期望在一切中间点上也能很好地逼近在一切中间点上也能很好地逼近 f，并且当插值点增加时，并且当插值点增加时这种逼近效果应该越来越好。这种逼近效果应该越来越好。但上述的期望不可能实现的。当认识到这一点时，在数但上述的期望不可能实现的。当认识到这一点时，在数学界曾引起强烈的震动。学界曾引起强烈的震动。20 世纪初，世纪初，Runge就给出了一个等距节点插值多项式就给出了一个等距节点插值多项式 不收敛
48、到不收敛到 的例子。的例子。()nLx()f x 设函数设函数 ，在该区间在该区间 上取上取 个等距节点个等距节点,构造构造 的的 次次 拉格朗日插值多项式为拉格朗日插值多项式为21(),5,51f xxx 5,51n()f xn5 10(0,1,)iixinn 2,4,6,8,20n 其其matlab的的lagrange.m文件及相关图形如下文件及相关图形如下.njnjiiijijnxxxxxxL002)()(11)(Runge 现象现象%lagrange.mfunction y=lagrange(x0,y0,x)n=length(x0);m=length(x);for i=1:m z=x(
49、i);s=0;for k=1:n L=1;for j=1:n if j=k L=L*(z-x0(j)/(x0(k)-x0(j);end end s=s+L*y0(k);end y(i)=s;endy;Lagrange插值多项式插值多项式求插值的求插值的Matlab程序程序.%Compare_Runge.mx=-5:0.1:5;z=0*x;y=1./(1+x.2);plot(x,z,k,x,y,r)axis(-5 5-1.5 2);pause,hold onfor n=2:2:20 x0=linspace(-5,5,n+1);y0=1./(1+x0.2);x=-5:0.1:5;y1=lagran
50、ge(x0,y0,x);plot(x,y1),pauseendy2=1./(1+x0.2);y=interp1(x0,y2,x);plot(x,y,k),hold offgtext(n=2),gtext(n=4),gtext(n=6)gtext(n=8),gtext(n=10)gtext(f(x)=1/(1+x2)比较不同的插值多项式次数对插值的影响比较不同的插值多项式次数对插值的影响-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-
