《计算方法》第四章 插值方法

1、1计 算 方 法华中科技大学数学与统计学院第四章第四章 插值方法插值方法计算方法课程组24 插值方法插值方法4.1 1多项式插值问题的一般提法多项式插值问题的一般提法 4.2 拉格朗日拉格朗日(Lagrange)插值插值4.3 差商与差分及其性质差商与差分及其性质4.4 牛顿插值公式牛顿插值公式 4.5 分段插值法分段插值法4.6曲线拟合的最小二乘法曲线拟合的最小二乘法34.0 引言引言 插值法是广泛应用于理论研究和生产实践的重插值法是广泛应用于理论研究和生产实践的重要数值方法要数值方法, 它是用简单函数它是用简单函数(特别是多项式或分特别是多项式或分段多项式段多项式)为各种离散数组建立连续模

2、型；为各种为各种离散数组建立连续模型；为各种非有理函数提供好的逼近方法。众所周知，反映非有理函数提供好的逼近方法。众所周知，反映自然规律的数量关系的函数有三种表示方法：自然规律的数量关系的函数有三种表示方法： 解析表达式52)(3xxxfyyxsin 图象法 表格法44.0 引言引言 许多数据都是用表格法给出的许多数据都是用表格法给出的(如观测和实验而得到的函数如观测和实验而得到的函数数据表格数据表格)，可是，从一个只提供离散的函数值去进行理论，可是，从一个只提供离散的函数值去进行理论分析和进行设计，是极不方便的分析和进行设计，是极不方便的, 甚至是不可能的。因此需甚至是不可能的。因此需要设法

3、去寻找与已知函数值相符，并且形式简单的插值函要设法去寻找与已知函数值相符，并且形式简单的插值函数数(或近似函数或近似函数)。 另外一种情况是，另外一种情况是，函数表达式完全给定，但其形式不适宜函数表达式完全给定，但其形式不适宜计算机使用计算机使用，因为计算机只能执行算术和逻辑操作，因此，因为计算机只能执行算术和逻辑操作，因此涉及连续变量问题的计算都需要经过离散化以后才能进行。涉及连续变量问题的计算都需要经过离散化以后才能进行。如数值积分方法、数值微分方法、差分方程以及有限元法如数值积分方法、数值微分方法、差分方程以及有限元法等，都必须直接或间接地应用到插值理论和方法等，都必须直接或间接地应用到

4、插值理论和方法。54.1 多项式插值问题的一般提法多项式插值问题的一般提法 当精确函数当精确函数 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) 的插值函数。的插值函数。最常用的插值函数是最常用的插值函数是 ? 代数多项式、三角多项式、有理分式代数多项式、三角多项式、有理

5、分式6 插值函数插值函数 p (x) 作为作为 f (x) 的近似，可以选自不同类型的的近似，可以选自不同类型的函数函数, 如如 p (x) 为代数多项式、三角多项式、有理分式为代数多项式、三角多项式、有理分式；其函数性态可以是光滑的、亦可以是分段光滑的。其其函数性态可以是光滑的、亦可以是分段光滑的。其中，代数多项式类的插值函数占有重要地位：中，代数多项式类的插值函数占有重要地位： (a) 结构简单、计算机容易处理、任何多项式的导数结构简单、计算机容易处理、任何多项式的导数和积分也易确定，并且仍是多项式。和积分也易确定，并且仍是多项式。(b) 著名的著名的Weierstrass逼近定理逼近定理

6、(定义在闭区间上的定义在闭区间上的任何连续函数任何连续函数 f(x) , 存在代数多项式存在代数多项式p(x)一致逼近一致逼近f(x),并达到所要求的精度并达到所要求的精度)。因此，我们主要考虑代数多项式的插值问题。因此，我们主要考虑代数多项式的插值问题。7x0 , x1, , xn 插值节点插值节点, 函数函数 P(x) 称为函数称为函数 y=f(x) 的插值函数，的插值函数，区间区间 a, b 称为插值区间。称为插值区间。 8例题例题: :已知函数已知函数 f(x) 有如下数据有如下数据:求求 f(x) 的插值多项式的插值多项式 p(x)，并求并求 f(x) 在在 x=0.5 处的近似值。

7、处的近似值。910 插值的几何意义插值的几何意义 从几何上看，插值就是求一条曲线从几何上看，插值就是求一条曲线 使其通过给定的使其通过给定的 个点个点 ， 并且与已知曲线并且与已知曲线 有一定的近似度。有一定的近似度。( )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) 11插值方法的研究问题插值方法的研究问题（1）满足插值条件的）满足插值条件的P ( x) 是否是否存在唯一？存在唯一？（2）若满足插值条件的）若满足插值条件的P (

8、 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) 12求求 n 次多项式次多项式 使得使得:nnnxaxaaxP 10)(条件：无重合节点，即条件：无重合节点，即jixx ji 4.2 拉格朗日多项式拉格朗日多项式 /* Lagrange Polynomial */ 根据插值条件，有：根据插值条件，有：nnnnnnnnnnyxaxaaxPyxaxaax

9、PyxaxaaxP10111101000100)()()(其系数矩阵的行列式为其系数矩阵的行列式为nnnnnnnxxxxxxxxxV111),(110010(),0,1,niipxyinVandermonde行列式行列式13), 2 , 1(nixi0)(),(010nijjinnxxxxxVnaaa,10注意到插值节点注意到插值节点两两相异，而两两相异，而故方程组故方程组(1)(1)有惟一解有惟一解于是满足插值条件的多项式存在且惟一。于是满足插值条件的多项式存在且惟一。nxxx,10nnnxaxaaxP10)(iinyxP)(由由n+1个不同插值节点个不同插值节点可以惟一确定一个可以惟一确定

10、一个n次多项式次多项式满足插值条件满足插值条件( (唯一性唯一性) )ReturnReturn14n = 1已知已知 x0 , x1 ; y0 , y1 ，求，求101( )Lxaa x=+使得使得111001)(,)(y1x1Ly0 x0L 可见可见 L1(x) 是过是过 ( x0 , y0 ) 和和 ( x1, y1 ) 两点的直线。两点的直线。l0(x)l1(x)4.2 拉格朗日多项式拉格朗日多项式 /* Lagrange Polynomial */ 线性插值线性插值基函数基函数1. 构造线性插值基函数的方法构造线性插值基函数的方法:iiiyxlyxxxxyxxxxxxxxyyyxL)(

11、)()(1010100101001010115线性插值与其基函数示意图线性插值与其基函数示意图xy0 0( )yy lx1 1( )yy l x0 x1xO10 01 1( )( )( )L xy lxy l x0 x1xxy0y1y( )yf x1( )yL xO16显然显然, , 是过是过 、 、 三点的一条三点的一条抛物线。抛物线。),(11yx),(22yx已知已知 , , 求求 ，n = 2)(2xL使得使得200211222( )( )( )L xyL xyL xy=2( )L x00( ,)xy210210,yyyxxx17显然显然, , 是过是过 、 、 三点的一条三点的一条抛

12、物线。抛物线。),(11yx),(22yx已知已知 , , 求求 ，n = 2210210,yyyxxx)(2xL使得使得200211222( )( )( )L xyL xyL xy=仿照线性插值基函数的构造方法，令仿照线性插值基函数的构造方法，令)()()()()()()()()(120210221012012010210 xxxxxxxxxlxxxxxxxxxlxxxxxxxxxl抛物线基抛物线基函数函数2()Lx称其为抛物线插值基函数称其为抛物线插值基函数(如上右图所示如上右图所示)。 2( )L x00( ,)xy18)()()()()()()()()(1202102210120120

13、10210 xxxxxxxxxlxxxxxxxxxlxxxxxxxxxl抛物线插值基函数抛物线插值基函数于是于是抛物线基函数抛物线基函数020112201201021012202120()()()()()()( )()()()()()()( )iiixxxxxxxxxx xxL xyyyxx xxxxxxxxxxl x y=-=+-=19希望找到希望找到 li (x)，i = 0, , n 使得使得 li (xj) = ij ；然后令；然后令，则显然有，则显然有 Pn(xi) = yi 。每个每个 li 有有 n 个根个根 x0 , xi , xn一般情形一般情形)()( )()()()( )

14、()()(110110nkkkkkknkkkxxxxxxxxxxxxxxxxxl ， k = 0, 1 , n ., )()( )()()(110nkkkxxxxxxxxAxl 令令k = 0, 1 , n .0111()()()()knkkkkkAxxxxxxxx() 1,kkl x由由 得得: :0()()）nnkkkLxfxlx0()()）nnkkkLxfxlx20设设 函数表函数表 则满足插值条件的多项式则满足插值条件的多项式（Lagrange）插值多项式）插值多项式 nkkknxlxfxL0)()( ）( )yf x, , ,(,(,()(0 1.),ijiixxxf xinij()

15、() (0,1. )，niiLxf xin其中其中, ., .0()(0,1,. )njkjkjjkxxlxknxx21以下的问题：如何分析以下的问题：如何分析插值的余项？插值的余项？ (1) (1) 先求先求插值基函数插值基函数. . (2) (2) 构造构造插值多项式插值多项式. .构造插值多项式的方法：构造插值多项式的方法：22 x -1 0 1 2f (x) -2 -2 1 2 已知连续函数已知连续函数 f (x) 的函数表如下：的函数表如下：求方程求方程 f (x)=0 在在(-1,2)内的近似根。内的近似根。例题例题23解：解：利用利用Lagrange插值法有插值法有 取初值取初值

16、x=0.5，利用牛顿法求解可得，利用牛顿法求解可得 f (x) 在在(-1,2)内的近似根内的近似根为为0.67433。 32591412 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()()()()()()( )( )( )()()()()()()() ()() ()( )()()()-+-=-+- - - -

17、+-+-+-+-+-3215914126xxx=-+-24 ，且，且 f 满足条件满足条件 , Lagrange插值法插值余项插值法插值余项设节点设节点)1( nf在在a , b内存在内存在, 考察截断误差考察截断误差:)()()(xLxfxRnn , baCfn bxxxan 1025 Lagrange插值法的插值余项插值法的插值余项 ，且，且 f 满足条件满足条件 ,设节点设节点)1( nf在在a , b内存在内存在 , 截断误差截断误差(或插值余项或插值余项):, baCfn bxxxan 10(1)1( )( )( )( )( )(1)!nnnnfRxfxLxxn,( , )a b26

18、 Lagrange插值法的插值余项插值法的插值余项 ，且，且 f 满足条件满足条件 ,设节点设节点)1( nf在在a , b内存在内存在 , 截断误差截断误差(或插值余项或插值余项):, baCfn bxxxan 10(1)1( )( )( )( )( )(1)!nnnnfRxfxLxxn,( , )a b证明：由已知条件得到：证明：由已知条件得到：()0,0,1,nkR xkn于是有：于是有：011( )( )()()( )()( )nnnR xk x x xx xx xkxx其中其中 是与是与 x 有关的待定函数。有关的待定函数。( )k x27任意固定任意固定 x xi (i = 0,

19、, n), 考察考察01( )( )( )( )()()()nntf tL tk x txtxtx根据插值条件及余项定义，可知根据插值条件及余项定义，可知( ) t在点在点01,nxxxx故故处均为零，处均为零，在在( ) t , a b上有上有n+2个个零点，根据个个零点，根据 Roll 定理定理 在在 的每两个零点间至少有一个零点，故的每两个零点间至少有一个零点，故在在 内至少有内至少有 一一 个零点，对个零点，对 再用再用Roll 定理，可定理，可知知 在在 内至少有内至少有 n 个零点，依此类推，个零点，依此类推， 在在 内至少有一个零点，记为内至少有一个零点，记为( ) t( ) t

20、( ) t , a b( ) t( ) t , a b(1)( )nt , a b( , )a b使得使得:(1)(1)( )( )(1)! ( )0nnfnk x(1)()( ),( ,)(1)!nfk xa bn28由于由于 是不能确定，因此我们并不能确定误差的大小是不能确定，因此我们并不能确定误差的大小但如能求出但如能求出 ，那么用，那么用 逼近逼近 的截断误差限是：的截断误差限是：当当 时，时，当当 时时( )nL x( )f x1n 12010111( )( )( )( )()(),22R xfxfxxxxx x 2n 230120211( )( )( )( )()()(),66,R

21、 xfxfxxxxxxx x (1)1()nnaxbm ax fxM11( )( )(1)!nnnMRxxn29当当 f (x) 为任一个次数为任一个次数 n 的多项式时，的多项式时， , 可知，可知，即插值多项式对于次数即插值多项式对于次数 n 的的多项式是精确的。多项式是精确的。0)()1( xfn0)( xRn注意注意30 给定给定 xi = i +1, i = 0, 1, 2, 3, 4, 5. 下面哪个是下面哪个是 l2(x) 的图像？的图像？问题问题31算例算例1 1LagrangeLagrange插值法插值法已知已知 ， ，用线性插值及抛物线插值计算用线性插值及抛物线插值计算 的

22、值并估计截断误差。的值并估计截断误差。sin0.320.314567sin0.340.333487sin0.360.352274sin0.336732算例算例1 1LagrangeLagrange插值法插值法已知已知 ， ，用线性插值及抛物线插值计算用线性插值及抛物线插值计算 的值并估计截断误差。的值并估计截断误差。sin0.320.314567sin0.340.333487sin0.360.352274sin0.33670120.320.340.36xxx0120.3145670.3334870.352274yyy线性插值时取线性插值时取 解解: :010.32,0.34xx1sin0.33

23、67(0.3367)0.3367 0.320.3367 0.340.3145670.3334870.34 0.320.32 0.340.330365L33其截断误差为：其截断误差为：其中其中, , 因为因为可取可取于是：于是： 2101( )()() ,2MR xxxxx012max( )xx xMf ( )sin ,( )sinf xx fxx0121max sinsin0.3335xx xMxx 115sin0.3367(0.3367)10.3335 0.0167 0.00332(0.3367)0.92 10RL34用抛物线插值时，取所有节点，得到用抛物线插值时，取所有节点，得到2sin0

24、.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)L4440.7689 103.89 100.5511 100.3334870.3522740.00080.00040.0000.3303 487余项讨论：余项讨论：其中：其中：32012( )()()() ,6MRxxxx

25、xxx0120max( )cos0.828xx xMfxx 226(0.3367)sin 0.3367(0.3367)10.8280.01670.0330.023360.17810RL35算例算例2 2LagrangeLagrange插值法插值法利用利用 100，121 的开方计算的开方计算 .由于由于: 解解: :115利用利用Lagrange插值法有插值法有 1110012110010121100121)(1xxxL于是于是, 71428.101110012110011510121100121115)115(1151 L115的精确值为的精确值为 10.72380529, 因此因此, 近似

26、值近似值 10.71428 有有3 位有效数字位有效数字. ReturnReturn364.3 差商与差分差商与差分 Lagrange 插值虽然易算，但若要增加一个节点时，插值虽然易算，但若要增加一个节点时， 全部基函数全部基函数 li (x) 都需重新算过。都需重新算过。寻求如下形式的插值多项式：寻求如下形式的插值多项式：01020101( )()()()()()nnnP xaa xxa xxxxaxxxx其中的其中的 为待定系数，由插值条件确定为待定系数，由插值条件确定.ia由线性代数的知识可知：任何一个由线性代数的知识可知：任何一个n次多项式都可以表示成次多项式都可以表示成011()()

27、()nx xx xx x共共 n+1 个线性无关的多项式的线性组合。个线性无关的多项式的线性组合。那么，是否可以将这那么，是否可以将这 n+1 个多项式作为插值基函数呢？个多项式作为插值基函数呢？1,0,x x01()(),x x x x37)()()()()(110102010nnxxxxxxaxxxxaxxaaxP设插值多项式设插值多项式P(x)具有如下形式：具有如下形式：(),0,1,iiP xfin000()P xfa)()(011011xxaafxP00fa 01011xxffa22012022021()()()()P xfaa xxaxxxx12010102022xxxxffxxf

28、fa 再继续下去再继续下去, ,待定系数的形式将更复杂待定系数的形式将更复杂, ,为此引入为此引入 差差商和差分商和差分的概念的概念. .P(x)应满足插值条件：应满足插值条件：有：有：384.3.1 4.3.1 差商的概念差商的概念从零阶差商出发，归纳地定义各阶差商从零阶差商出发，归纳地定义各阶差商:称称 为函数为函数 关于点关于点 的的一阶差商一阶差商.( )f x111 ,iiiiiif xf xf x xxx1,iix x 一般地，一般地， 关于关于 的的 k 阶差商阶差商:( )f x1,iii kx xx12111, , ,iii kiii kiii ki kif xxxf x x

29、xf x xxxx 记函数记函数 在在 的值的值 ，称称 为为 关于关于 的的零阶差商零阶差商。( )f xix ( )iif xf x if xix( )f x39 一般地，一般地， 关于关于 的的 n 阶差商阶差商:( )f x01, ,nx xx12011010 , , , , ,nnnnf x xxf x xxf x xxxx n 阶差商的概念阶差商的概念40差商的基本性质差商的基本性质性质性质1 1：差商可表示为函数值的线性组合，即：差商可表示为函数值的线性组合，即：性质性质2 2：差商关于所含节点是对称的，即：差商关于所含节点是对称的，即：010011(),()()()()njnj

30、jjjjjjnf xf x xxxxxxxxxx011010, ,nnnnf x xxf x xxf xxx可用归纳法证明41差商的基本性质差商的基本性质性质性质3：性质性质4：设设 在在 存在存在 n 阶导数，且阶导数，且 则则 ，使得，使得:12011011 ,imiimmif xxxf x xxf xxxxx( )01( ),!nnff x xxn( , )a b ( )f x , a b , jxa b42差商的计算差商的计算-差商表差商表一阶差商一阶差商 二阶差商二阶差商三阶差商三阶差商四阶差商四阶差商ix0 x1x2x3x4x( )if x1()f x2()f x3()f x4()

31、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 x43已知已知ix()if x计算三阶差商计算三阶差商1 , 2 , 4 , 7 f解：列表计算解：列表计算 ix()ifx算例算例 1 , 2 , 4 , 7 1 / 2f444.3.2 4.3.2 差分差分 在前面的讨论中，节点是任意分布的，但实际上在前面的讨论中，节点是任意分布的，但实际上经常遇经常遇到等距节点的情况，这时插值公式可以得到简

32、化到等距节点的情况，这时插值公式可以得到简化，为此，我，为此，我们先介绍差分的概念。们先介绍差分的概念。 设函数设函数 在等距节点在等距节点上的值上的值 为已知，这里为已知，这里 为常数，称为步长。为常数，称为步长。( )f x0(0,1, )ixxih in( )iiff xh 下面来讨论差分的定义。下面来讨论差分的定义。45差分的定义差分的定义记号记号分别称为分别称为 在在 处以处以 为步长的为步长的 向前差分、向后差分、中心差分向前差分、向后差分、中心差分符号符号 、 、 分别称为向前差分算子、向后差分算子、分别称为向前差分算子、向后差分算子、中心差分算子中心差分算子. .1iiifff

33、1iiifff1122()()22iiiiihhff xf xff ( )f xixh46高阶差分高阶差分用一阶差分可以定义二阶差分用一阶差分可以定义二阶差分一般地可定义一般地可定义 m 阶差分为：阶差分为：中心差分定义为中心差分定义为: : 以此类推。以此类推。21212iiiiiiffffff 111mmmiiifff 111mmmiiifff121iiifff 121iiifff 11222iiifff 47不变算子不变算子 I、移位算子、移位算子 E定义定义从而可得：从而可得：于是得到：于是得到：同理，由于：同理，由于：得到：得到：由于：由于：得到：得到：由差分的定义及不变算子和移位算

34、子有如下性质由差分的定义及不变算子和移位算子有如下性质: : kkIff1kkEff1()kkkkkkfffEfIfEI fEI 1IE 1122EE111()kkkkkkfffIfEfIEf111122221122()kkkkkkfffE fEfEEf48差分的性质差分的性质性质性质1 1：各阶差分均可用函数值表示，如：各阶差分均可用函数值表示，如：性质性质2 2：某点的函数可用各阶差分来表示：某点的函数可用各阶差分来表示：00()( 1)( 1)nnnnjnjjkkkk njjjnnfEIfEffjj 100()( 1)( 1)nnnnn jj nn jkkkk j njjnnfIEfEf

35、fjj 00()nnnnjjn kkkkkjjnnfE fIfffjj 49性质性质3 3：差商与差分有如下关系：差商与差分有如下关系：性质性质4 4：差分与导数有如下关系：差分与导数有如下关系：111,(1,2, )!mkkk mkmf xxxfmnm h11 1,(1,2, )!mkkk mkmf x xxfmnm h( )( ),(,)nnnkkk nfh fxx50差分的计算差分的计算kf( ) 22() 33() 44() 0f1f2f3f4f23()ff34()ff01()ff12()ff2224()ff2202()ff2213()ff3314()ff3303()ff4404()f

36、fReturnReturn514.4 牛顿插值公式牛顿插值公式根据差商的定义，把根据差商的定义，把 看成看成 上的一点，上的一点，可得：可得：x , a b000( )() ,()f xf xf x xxx001011 , ,()f x xf x xf x x xxx010101 , ,()nnnnf x xxf x xxf x x xxxx524.4 牛顿插值公式牛顿插值公式根据差商的定义，把根据差商的定义，把 看成看成 上的一点，上的一点，可得：可得：x , a b000( )() ,()f xf xf x xxx001011 , ,()f x xf x xf x x xxx010101

37、, ,()nnnnf x xxf x xxf x x xxxx0010( )(),()f xf xf x xxx01201,()()f x x xxxxx0101,()()nnf x xxxxxx011 ,( )( )( )nnnnf x x xxxNxR x把后一式代入前一式把后一式代入前一式53其中其中 显然显然 满足插值条件，且次数不超过满足插值条件，且次数不超过 , ,它就它就是插值多项式，其系数为：是插值多项式，其系数为： 我们称我们称 为牛顿插值多项式为牛顿插值多项式. .0010( )(),()nNxf xf x xxx01201,()()f x x xxxxx0101,()()

38、nnf x xxxxxx01101( )()()(1( )( )( ) ,( )!nnnnnnR xf xNxf x x xxxfxxxxn ( )nNxn01,iiaf x xx0,1,in( )nNx54( )f x 已知已知 的函数表，求的函数表，求4 次牛顿插值多项式次牛顿插值多项式, , 并求并求算例算例(0.596).f55从表中可以看到从表中可以看到4 阶差商阶差商几乎为几乎为0 0，故取，故取4 4次插值多项式即可，次插值多项式即可，于是：于是：0.400.400.410750.410750.550.550.578150.578151.116001.116000.650.650

39、.696750.696751.186001.186000.280000.280000.800.800.888110.888111.275731.275730.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)(

40、0.4)(0.55)(0.4)(0.55)(0.60.41075 1.1665)(0.4)(0.55)(0.65)(0.8)0.280.197330.03134N xxxxxxxxxxx 已知已知 的函数表，求的函数表，求4 次牛顿插值多项式次牛顿插值多项式, , 并求并求算例算例(0.596).f( )f x4(0.596)(0.596)0.63192fN560.400.400.410750.410750.550.550.578150.578151.116001.116000.650.650.696750.696751.186001.186000.280000.280000.800.800.

41、888110.888111.275731.275730.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.596).f( )f

42、x截断误差为：截断误差为：40459( ),(0.596)3.63 10R xf xx4( )(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.03134N xxxxxxxxxxx4(0.596)(0.596)0.63192fN57 和和 均是均是 n 次多项式次多项式, ,且均满足插值条件且均满足插值条件: : 由多项式的唯一性由多项式的唯一性, , ,因而因而, ,两个公式两个公式的余项是相等的的余项是相等的, ,即即 当插值多项式从当插值多项式从 n-1 次增加到次增加到 n

43、次时次时, ,拉格朗日型插值必须重新计算所有的基本插值多项式拉格朗日型插值必须重新计算所有的基本插值多项式; ;而对于牛顿型插值而对于牛顿型插值, ,只需用表格再计算一个只需用表格再计算一个 n 阶差商阶差商, , 然后加上一项即可。然后加上一项即可。牛顿插值公式和牛顿插值公式和Lagrange插值公式比较插值公式比较( )nL x( )nNx ()()(), 0,1,niniiL xNxf xin ( )( )nnLxNx(1)01( ) ,( )( )(1)!nnnnff x x xxxxn ReturnReturn584.5 分段插值公式分段插值公式 在区间在区间 a, b 上用插值多项

44、式上用插值多项式 P 逼近函数逼近函数 f 时，时，f 和和P 在每个节点上的差异在每个节点上的差异(理论上理论上)应该为零。自然，我们期望应该为零。自然，我们期望在一切中间点上也能很好地逼近在一切中间点上也能很好地逼近 f ，并且当插值点增加时，并且当插值点增加时这种逼近效果应该越来越好。这种逼近效果应该越来越好。 但上述的期望不可能实现的。当认识到这一点时，在数但上述的期望不可能实现的。当认识到这一点时，在数学界曾引起强烈的震动。学界曾引起强烈的震动。 20 世纪初，世纪初，Runge就给出了一个等距节点插值多项式就给出了一个等距节点插值多项式 不收敛到不收敛到 的例子。的例子。( )nL

45、x( )f x59 设函数设函数 ，在该区间在该区间 上取上取 个等距节点个等距节点, 构造构造 的的 次次 拉格朗日插值多项式为拉格朗日插值多项式为21( ), 5,51f xxx 5,51n( )f xn5 10(0,1, )iixinn 2,4,6,8,20n 其其matlab的的lagrange.m文件及相关图形如下文件及相关图形如下.njnjiiijijnxxxxxxL002)()(11)(Runge 现象现象60% lagrange.mfunction y=lagrange (x0,y0,x)n=length(x0);m=length(x);for i=1:m z=x(i);s=0

46、; 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程序程序.61%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=l

47、agrange(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)比较不同的插值多项式次数对插值的影响比较不同的插值多项式次数对插值的影响62-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.5

48、00.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.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)不同次数的不同次数的Lagrange插值多项式的比较图插值多项式的比较图Runge现象现象 63令令 ，则，则 ， 下表列出了下表列出了 和和 的值。的值。1/211()2nnnxxx1

49、/255nxn2,4,20n 1/2()nnL x1/2()nR x64 结果表明结果表明,随着随着 的增加，的增加， 的绝对值几乎成倍地增的绝对值几乎成倍地增加，这说明当加，这说明当 时时 在在 上不收敛。上不收敛。 Runge证明了，存在一个常数证明了，存在一个常数 , 使得当使得当 时，时， ; 而当而当 时时 发散。发散。 说明说明: 并不是插值多项式的次数越高并不是插值多项式的次数越高, 插值效果越好插值效果越好, 精度精度也不一定是随次数的提高而升高也不一定是随次数的提高而升高, 这种现象在上个世纪初由这种现象在上个世纪初由Runge发现发现, 故称为故称为Runge现象现象.n1

50、/2()nR xn nL 5,53.63cxclim ( )( )nnL xf x xc ( )nL x65 分段线性插值特别简单，从几何上看，就是用分段线性插值特别简单，从几何上看，就是用折线逼近折线逼近曲线曲线。 分段线性插值的数学定义分段线性插值的数学定义 设设 是区间是区间 上的函数，在节点上的函数，在节点 上的函数值为上的函数值为 ，求一分段折线函数求一分段折线函数 满足：满足：（1 1） （2 2） 在在 上，上， 是一次多项式。是一次多项式。（3 3）则称则称 为为 的的分段线性插值函数分段线性插值函数。4.5.1 分段线性插值分段线性插值( )f x , a b01naxxxb

51、01,nfff( ) , P xC a b(),0,1,iiP xf in1,iixx( )P x1,iixx( )P x( )P x66 1,iixx0,1,1in( )P x易知易知, P(x) 是个折线函数，在每个区间是个折线函数，在每个区间上上,有有在在 a,b 上是连续的，但其一阶导数是不连续的上是连续的，但其一阶导数是不连续的. 1111( )iiiiiiiixxxxyyxxxxp x67 当当 时时, , 当当 时时, ,4.5.1 分段线性插值的基函数分段线性插值的基函数0i 10101001,( )0,xxxxxxxlxxxx1,2,1in11111111,( )( ,0,i

52、iiiiiiiiiiiixxxxxxxl xxxxx xxxxxx 当当 时时, ,11110,( ),nnnnnnnnxxxlxxxxxxxxin68显然显然 是是 的线性组合：的线性组合： 在区间在区间 上的值为：上的值为：( )P x( )il x0( )( )niiiP xf l x11111( )iiiiiiiiiixxxxP xffxxxxxxx1,iixx，表达式表达式 在区间在区间上，只有上，只有是非零的，其它基函数均为零。即是非零的，其它基函数均为零。即注意注意( )P x1,iixx1( ) ,ilx( )il x11( )( )( )iiiiP xflxf l x69算例

53、算例节点（如下表），求区间上分段线性插值函数，并利用节点（如下表），求区间上分段线性插值函数，并利用它求出它求出21()1yfxx (4.5)f已知函数已知函数近似值。近似值。在区间在区间 0,5 上取等距插值上取等距插值70 ,1k k 11(1)( )(1)(1)(1)()kkkkxkx kP xyykkkky x kyx k (1) 0.5 , 0,10.5(2) 0.2(1), 1,2( )0.2(3) 0.1(2), 2,30.1(4) 0.05882(3), 3,40.05882(5) 0.038xxxxxxP xxxxxxxx 46(4),4,5xx (4.5)0.05882 (

54、4.5 5) 0.03846 (4.5 4)0.04864P (4.5)0.04705882352941f解解: : 在每个分段区间在每个分段区间于是，于是，实际值实际值: : 当当n=7 时，时， P(4.5)=0.04762270321996 ; 当当n=10时，时，P(4.5)=0.04705882352941由此可见，对于光滑性要求不高的插值问题，分段线性插值的由此可见，对于光滑性要求不高的插值问题，分段线性插值的效果非常好！计算也简单效果非常好！计算也简单!714.5.2 埃尔米特埃尔米特 (Hermite) 插值插值拉格朗日和牛顿均只保证函数插值；拉格朗日和牛顿均只保证函数插值；实

55、际问题有时需要导数也插值；实际问题有时需要导数也插值；满足这种需要的插值称为埃尔米特插值满足这种需要的插值称为埃尔米特插值. .72埃尔米特插值的一般提法为：埃尔米特插值的一般提法为： 设函数在节点设函数在节点 的函数值与导数值为：的函数值与导数值为：其中其中 是正整数，是正整数，寻求一个次数尽可能低的多寻求一个次数尽可能低的多项式项式 ，满足：，满足：埃尔米特插值的一般提法埃尔米特插值的一般提法01,nxxx( ),iif xf( ),iifxf ,(1)(1)( ),iimmiifxf0,1,in01,nm mm( )H x( )( )( ),kkiiHxf0,1,in0,1,1;ikm7

56、3 以如下数据构建埃尔米特插值以如下数据构建埃尔米特插值 埃尔米特插值埃尔米特插值算例算例74 以如下数据构建埃尔米特插值以如下数据构建埃尔米特插值 埃尔米特插值埃尔米特插值算例算例共有共有 个条件，可唯一确定一个次数个条件，可唯一确定一个次数不超过不超过 的多项式的多项式 ，其形，其形式为：式为：目标：求出所有的目标：求出所有的 , ,方法：基函数法方法：基函数法. .22n21n21( )nHx21210121( )nnnHxaa xaxia(0,1, )in75可如下构造：可如下构造： 2100( )( )( )nnniiiiiiHxyxyx( ),( )iixx 均为均为 2 n+1

57、次插值基函数次插值基函数. . (),()0ikikikxx()0,()ikikikxx 这样这样 可表示为：可表示为：21( )nHx210( )( )( )nniiiiiHxyxyx显然有：显然有：21()nkkHxy21()nkkHxy76现在求现在求 及及 ，令令其中其中从而有：从而有：由此得：由此得： ，故：故： ，( )ix ( )ix 2( )() ( )iixaxb lx 011011()()()()( )()()()()iiniiiiiiinxxxxxxxxl xxxxxxxxx2( )() ( )1iiiiixaxb lx ()()()2() ()0iiiiiiiiixl

58、xal xaxb l x ()1iaxb2 ( )1iial x2 ( )iial x 12( )i iibxl x 77由由 的表达式可得：的表达式可得：于是得到：于是得到：同理可得同理可得( )il x01( )niikikk il xxx201( )12()( )niiikikk ixxxlxxx 2( )() ( )iiixxx lx 78例：例：已知已知233sin,214sin,216sin 分别利用分别利用 sin x 的的1次、次、2次次 Lagrange 插值计算插值计算 sin 50 并估计误差。并估计误差。 解：解：0 x1x2x185500 n = 1分别利用分别利用x

59、0, x1 以及以及 x1, x2 计算计算4,610 xx利用利用216/4/6/214/6/4/)(1 xxxL这里这里)3,6(,sin)(,sin)()2( xxxfxxf而而)4)(6(!2)()(,23sin21)2(1 xxfxRxx00762. 0)185(01319. 01 Rsin 50 = 0.7660444)185(50sin10 L0.77614外推外推 /* extrapolation */ 的实际误差的实际误差 0.010010.010013,421 xx 利用利用sin 50 0.76008, 00660. 018500538. 01 R内插内插 /* interpolation */ 的实际误差的实际误差 0.00596 0.00596内插通常优于外推。选择内插通常优于外推。选择要计算的要计算的 x 所在的区间的所在的区间的端点，插值效果较好。端点，插值效果较好。79n = 223)()(21)()(21)()()(4363463464363646342 xxxxxxxL)185(50sin20 L0.7654323cos21;)3)(4)(6(!