第五章 插值与拟合

1、第第 五五 章章 插值与拟合插值与拟合5.1 插值的基本概念插值的基本概念5.2 Lagrange插值插值5.3 Newton插值插值5.4 差分与等距节点插值差分与等距节点插值5.5 Hermite插值插值5.6 分段低次插值分段低次插值5.7 三次样条插值三次样条插值5.8 曲线拟合的最小二乘法曲线拟合的最小二乘法思考问题思考问题1、有哪些问题涉及到插值、有哪些问题涉及到插值2、插值条件、插值条件3、两点如何插值，如何构造插值函数、两点如何插值，如何构造插值函数4、各种插值方法及插值条件、各种插值方法及插值条件5、插值本质、插值本质5.1 插值的基本概念插值的基本概念插值问题的背景插值问题

2、的背景 在生产和实验中，在生产和实验中，函数函数 f(x)或者其表达式不便或者其表达式不便于计算于计算, 或者或者无表达式而只有函数在给定点的函数无表达式而只有函数在给定点的函数值值(或其或其导数值导数值) ，此时我们希望建立一个简单的而，此时我们希望建立一个简单的而便于计算的近似函数便于计算的近似函数 ( (x) )，来逼近函数来逼近函数 f( (x) )。 常用的函数逼近方法有：常用的函数逼近方法有： 插值法；插值法； 最小二乘法（或称均方逼近）；最小二乘法（或称均方逼近）； 一致逼近等。一致逼近等。5.1 插值的基本概念插值的基本概念已经测得在某处海洋不同深度处的水温如下：深度（M） 4

3、66 741 950 1422 1634水温（oC）7.04 4.28 3.40 2.54 2.13根据这些数据，希望合理地估计出其它深度（如500米，600米，1000米）处的水温举例这就是本章要讨论的“插值问题”插值法插值法 插值法是函数逼近的重要方法之一，有着广泛的应用。简单地说，插值法就是用给定的(未知)函数 f(x)的若干点上的函数值(或其导数值) 来构造 f (x)的近似函数(x)，要求(x)与 f(x)在给定点的函数值相等。 有很多种插值法，其中以拉格朗日(Lagrange)插值和牛顿(Newton)插值为代表的多项式插值最有特点，常用的插值还有Hermite插值，分段插值和样条

4、插值。函数可以未知，函数可以未知，只需已知若干点只需已知若干点上的值。上的值。设设 f(x)为为a，b上的上的函数，函数，在互异点在互异点x0 , x1, . , xn 处处的函数值分别为的函数值分别为 f(x0) , f (x1) , , f (xn) ,构造一个简单函构造一个简单函数数 (x) 作为函数作为函数 f(x) 的近似表达式的近似表达式y= f(x) (x),使使 (xi)f(xi) , i0, 1, 2, ,n (5.0)则称则称 (x) 为关于节点为关于节点x0 , x1, . , xn的的插值函数插值函数；称；称 x0 , x1, . , xn 为为插值节点插值节点；称；称

5、(xi, f (xi), i=1,2, , n 为为插值点插值点；f(x) 称为称为被插值函数被插值函数。 (5.0)式称为式称为插值条件插值条件。这类问题称为这类问题称为插值问题插值问题。 构造出构造出 ( (x) )，对，对 f( (x) )在在 a, ,b 上函数值的计算，就转化为上函数值的计算，就转化为 ( (x) )在在对应点上的计算。对应点上的计算。插值法的定义插值法的定义5.2 Lagrange插值插值 选用代数多项式作为插值函数。Lagrange插值就是选用节点上的函数值作为插值条件。5.2.1 线性插值线性插值 给定两个点(x0，y0)，(x1，y1），x0 x1，确定一个一

6、次多项式插值函数，简称线性插值线性插值。待定系数法待定系数法 设 L1(x)=a0+a1x, 代入插值点当x0 x1时，方程组的解存在唯一。01000111aa xyaa xy即插值条件：L1(xi)= f(xi)=yi,i=0,1解之得解之得， 因此，因此， （5.1）式称为一次Lagrange插值插值。 由求解过程知，用待定系数法，需要求解线性方程组，当已知节点较多时，即方程的未知数多，计算量较大，不便向高阶插值推广。011001010101,.x yx yyyaaxxxx0110011010101010110( )(5.1)x yx yyyL xxxxxxxxxxyyxxxx插值基函数法

7、插值基函数法 分别构造两个节点上的一次函数，使其在本节点上的函数值为1，而在其他节点上的函数值为0。设l0(x), l1(x)分别为满足上述条件的一次函数，即 或简单地记为 对于过两个节点x0 , x1的线性插值（5.1），令00100111()1,()0()0,()1lxl xlxl x1,()0,.ijijijlxij01010110( ), ( ),xxxxlxl xxxxx显然， l0(x), l1(x) 满足：线性插值函数可以写成节点上函数值的线性组合，即 L1(x) = l0(x) y0 + l1(x) y1 称l0(x), l1(x) 分别为x0, x1的插值基函数。线性插值误差

8、线性插值误差定理定理 1 设L1(x)为一次Lagrange插值函数, 若 f (x) 一阶连续可 导，f “(x)在(a, b)上存在，则对任意给定的x(a ,b), 至少存在一点(a,b),使得证明证明 因为L(xi)= f(xi),i=0,1,所以，R1(x0)=R1(x1)=0, 即 x0,x1为R1(x)的两个根。因此，可设R1(x)为(), ,0,1.ijijl xi j易知满足插值条件：L1(xi) = yi , i=0,11101( )( )( )( )()()(5.3)2!fR xf xL xxxxx可设 R1(x) = k(x)(x-x0)(x-x1). 固定任一 x，作辅

9、助函数，令 则 (xi )=0, i =1,2, (x)=0, 即 (t)有3个零点x0, x1, x。 假定，x0 x x1 , 分别在x0，x和x，x1上应用洛尔（Rolle）定理，可知， (t)在每个区间上至少存在一个零点，1，2，使(1)=0，(2)=0(此即(t)有2个零点)。再利用洛尔定理知， (t)在1,2上至少有一个零点，使 ()=0。 对 (t)求2阶导数得， (t) = f (t) - -2!k(x), 因为 ()=0，所以，有 k(x) = f () / /2!。 证毕。101( )( )( )( )()(),tf tL tk x txtx5.2.2 二次插值二次插值 给

10、定3个互异插值点(xi, f (xi), i = 0,1,2，确定一个二次插值多项式函数，即抛物线插值（如图）。待定系数法 设L2(x)=a0+a1x+a2x2, 代入3个插值条件： L2(xi)= f(xi), i = 0,1,2，解线形方程组可得a0, a1, a2。 插值基函数法插值基函数法 构造3个节点上2次插值基函数 l0(x), l1(x), l2(x), 使满足 li(xj)=ij ， i, j = 0,1,2。 因为l0(x) 为2次插值基函数, 且l0(x1) = l0(x2) = 0, 所以可设 l0(x) = A (x - x1)(x - x2)。 由条件：l0(x0)

11、= 1，得同理可得，二次Lagrange插值多项式为01021,()()Axxxx1200102()()( ).()()xxxxlxxxxx02011210122021()()()()( ),( ).()()()()x xx xx xx xl xl xxxxxxxxx220011220( )( ) ()( ) ()( ) ()( ) ()(5.4)iiiLxlx f xl x f xlx f xl x f x 容易验证满足插值条件二次插值的误差二次插值的误差22012( )( )( )( )()()()(5.5)3!fRxf xLxxxxxxx 定理定理 设设L2(x)为二次Lagrange插

12、值函数, 若 f (x) C3a，b ， 则任给x(a ,b),至少存在一点=(x) (a,b),使 提示提示：因为R2(x0)=R2(x1)=R2(x2)=0,可设 作辅助函数 易知，x0, x1, x2, x为(t)的4个零点，在4个点两两组成的区 间上，应用Rolle定理，然后再反复应用Rolle定理即得证。 2012( )( )()()().Rxk x xxxxxx2012( )( )( )( )()()(),tf tL tk x txtxtx例例5.1 给定sin11=0.190809,sin12=0.207912,求线性插 值，并计算sin1130和sin1030 。解解 x0=

13、11, x1= 12, y0= 0.190809, y1= 0.207912， sin1130L1(11.5)=0.199361, sin1030L1(10.5)=0.182258.由定理1知，误差为10101(12)(11)( )(12)(11).11 1212 11xxL xyyx yxy准确值为：sin1130=0.199368sin1030=0.182236101( )sin( )( )()()(11)(12).2!2fR xxxxxxx11( )(11)(12)21(11.5 11)(11.5 12)0.125.2R xxx0111 1211.522xxx例例5.2 给定sin11=

14、0.190809,sin12=0.207912, sin13=0.224951,构造二次插值，并计算 sin1130。 解解 x0= 11, x1= 12, x2= 13, y0= 0.190809, y1= 0.207912,y2= 0.224951， sin1130L2(11.5) = 0.199369, sin1130= 0.199368. sin1130L1(11.5)=0.199361,2(12)(13)(11)(13)( )0.1908090.207912(11 12)(11 13)(12 11)(12 13)(11)(12)0.224951(13 12)(13 12)xxxxLx

15、xx 例例5.3 要制作三角函数sin x的值表，已知表值有四位小数，要求用线性插值引起的截断误差不超过表值的舍入误差，试确定其最大允许的步长。解解 f(x)=sin x, 设xi, xi为任意两个插值节点，最大允许步长记为 h = hi = xi xi，111111121124( )sin( )()()()()2!211()()()()22221()(),88110 ,0.02.82iiiiiiiiiiiiiiiifR xxxxxxxxxxxxxxxxxxxhxxxxhh5.2.3 n次次Lagrange插值多项式插值多项式 已知 n+1个互异插值节点 (xi, f(xi), i=0, 1,

16、 2, , n , 研究n次插值多项式的存在性及其表示形式。 存在性存在性 设 n 次多项式为 代入插值点，即插值条件：Pn (xi) = f (xi), i = 0, 1,2, , n , 得 其范德蒙德(Vandermonde)行列式为：20121( ),(5.6)nnnP xaa xa xa x20102000201121112012()()(5.6)()nnnnnnnnnnaa xa xa xf xaa xa xa xf xaa xa xa xf x 所以，(5.6)的解存在唯一。 解出(5.6)的解a0 , a1, , an ，代入(5.6)1即得 n 次插值多项式Pn(x)。 n

17、次插值多项式的构造次插值多项式的构造 有上面的讨论知，用待定系数法要求解一个线性方程组，计算量大，实际中不可取。20002111012011(,)1()0,nnnnnnnijj i nxxxxxxV xxxxxxxx 插值基函数法插值基函数法 分别构造x0 , x1, , xn 上的 n 次插值基函数 l0(x), l1(x), , ln(x),满足性质： 即1,0,1,2,()0ijijijnl xij， 节点基函数x0 x1x2xnl0(x)1000l1(x)0100l2(x)0010ln(x)0001先构造 l0(x)。有上表知， x1 , x2, , xn 为 l0(x) 的零点，设由

18、l0(x0)=1，得同理可设由li (xi)=1，得0012( )()()(),nlxaxxxxxx001020120010201,()()()()()()( ).()()()nnnaxxxxxxxxxxxxlxxxxxxx011( )()()()(),iiiinl xa xxxxxxxx1111,()()()()iiiiiinaxxxxxxxx于是，所以我们得到 n 次Lagrange插值多项式： 容易验证， Ln(xi) = f (xi), i = 0, 1, 2, n.0110111()()()()( )()()()(),1,2,(5.7)iiniiiiiinnjijjj ixxxxxx

19、xxl xxxxxxxxxxxinxx00110( )( ) ()( ) ()( ) ()( ) ()(5.8)nnnniiiLxlx f xl x f xlx f xl x f x例例5.4 已知插值点 (-2.00,17.00), (0.00,1.00), (1.00,2.00), (2.00,17.00), 求三次插值，并计算 f (0.6)。解解 先计算4个节点上的基函数：1230010203()()()( )()()()(0)(1.00)(2.00)( 2.000)( 2.00 1.00)( 2.002.00)1(1)(2),24xxxxxxlxxxxxxxxxxx xx 02311

20、01213()()()1( )(2)(1)(2),()()()4xxxxxxl xxxxxxxxxx0132202123()()()1( )(2) (2),()()()3xxxxxxlxxx xxxxxxx 三次Lagrange插值多项式为： f (0.6) L3(0.6) = -0.472.0123303132()()()1( )(2) (1).()()()8xxxxxxlxxx xxxxxxx3171( )(1)(2)(2)(1)(2)244217(2) (2)(2) (1).38L xx xxxxxxx xxx x n 次插值多项式的误差次插值多项式的误差 定理定理 2 2 设Ln(x)

21、是a,b上过插值点(xi, f(xi)的 n 次 Lagrange插值多项式，节点xi两两互异，若 f(x)Cn+1a,b, 则 x a,b,存在=(x) a,b,使得 证明提示：因为Rn(xi)=0, i =0, 1, 2, , n, 令 作辅助函数 显然， (t)有 n+2 个零点x0，x1，xn，x，反复应用Rolle 定理，由(n+1)()=0,定理得证。(1)01( )( )()()()(5.9)(1)!nnnfRxxxxxxxn01( )( )()()().nnRxk x xxxxxx01( )( )( )( )()()(),nntf tL tk x txtxtx n 次插值多项式

22、的几点说明次插值多项式的几点说明 若| f (n+1)(x)|M,xa,b,则由(5.9)得 当 f(x)为不高于n次的多项式时，因为Rn(x)=0,则 Ln(x) = f (x). 特别地，取 f(x) = xk, k = 0,1,2,n, 则 令 k =0，可知 n 次Lagrange基函数li(x)满足0( )(5.12)(1)!nniiMRxxxn 即 f(x)为不超过n次的多项式时，插值多项式就是被插函数本身00( )( ) ()( )( ),0,1,2, .nnkkniiiiiiLxl x f xl x xf xxkn0( )1.niil x 实际计算中，如果 f (x)的形式未知

23、，也就无法求出 f (n+1)(x)或估计出其较精确的上界。所以也就无法估计|Rn(x)|。 我们采用事后估计，即给定 n+2个节点，x0, x1, xn, xn+1,构造两个n次插值多项式Ln(x)和 ，用它们来估计|Rn(x)|。 由定理 2，得( )nLx( )0121nLxnnxxxxx ( )nLx (1)101()( )( )()()()(5.13)(1)!nnnff xLxxxxxxxn(1)211()( )( )()()()(5.14)(1)!nnnnff xLxxxxxxxn假定 f (n+1)(x) 在 a, b内连续, 且变化不大, 即 f (n+1)(1) f (n+1

24、)(2).(5.13)和(5.14)两式相除，得解之得，于是，得误差01( )( ),( )( )nnnf xLxxxxxf xLx100110( )( )( ).nnnnnxxxxf xLxLxxxxx001( )( )( )( )( )(5.16)nnnnnxxRxf xLxLxLxxx事后估计：即用求出的插值多项式来估计误差。所以我们得到 n 次Lagrange插值多项式： 0110111()()()()( )()()()(),1,2,(5.7)iiniiiiiinnjijjj ixxxxxxxxl xxxxxxxxxxxinxx00110( )( ) ()( ) ()( ) ()( )

25、 ( )(5.8)nnnniiiL xlx f xl x f xlx f xl x f x n 次插值多项式的算法描述次插值多项式的算法描述 输入节点数 n、插值点(xi, yi) (i=0,1,2, ,n)和要计算的函数点 x。 实现基函数 li(x)和插值 Ln(x): FOR i=0,1, , n tmp=1; FOR j=0, 1, , i1, i+1, , n tmp=tmp*(xxj)/(xixj); (实现 li(x) ) fx=fx+tmp*yi; (实现Ln(x) ) 输出 fx。5.3 Newton插值插值 Lagrange插值的优缺点：插值的优缺点： 优点：优点：形式整齐

26、、规范，理论上保证插值存在唯一性。 缺点：缺点：计算量大、不具有承袭性。 函数未知时，无法计算其精度5.3.1 差商及其性质差商及其性质一阶差商一阶差商：f (x)关于点x0，x1的一阶差商记为 f x0, x1，二阶差商：二阶差商： f (x)关于点x0，x1， x2的二阶差商记为 f x0, x1, x2,010101()(),.f xf xf xxxx011201202,.f xxf x xf xx xxx 一般地，k 阶差商 f x0, x1, xn 定义为： 差商的性质差商的性质 性质性质1 k 阶差商 f x0, x1, xk可表成节点上函数值 f(x0), f(x1), , f(

27、xk) 的线性组合，即 例如例如，k = 2时， (5.17)011120110,.kkkkkf xxxf x xxf xxxxxx0101101,().()()()()kkiiiiiiikif xxxf xxxxxxxxx011201202012010210122021,()()().()()()()()()f xxf x xf xx xxxf xf xf xxxxxxxxxxxxx性质性质 2 各阶差商具有对称性, 即改变差商中节点的次序不会 改变差商的值。设i0, i1, , ik为0, 1, , k的任一排列, 则 由性质1知，任意改变节点的次序，只改变(5.17)式右端求和的次序，故

28、其值不变。例如,由定义知，性质性质 3 若 f (x)为 n 次多项式，则一阶差商 f x, xi为n 1次 多项式。 由定义令x = xi, 则分子为0, 说明分子中含有因子x xi, 与分母约去。0101,.kkiiif xxxf xxx01011001()(),.f xf xf xxf x xxx( )() ,.iiif xf xf x xxx性质性质 4 若 f (x)在 a, b 存在 n +1阶导数，xi a, b , i = 0,1,n, 固定 xa, b, 则 n+1 阶差商与导数 存在如下关系：(1)01( ) ,( , ).(1)!nnff x xxxa bn 差商的计算差

29、商的计算 由差商的定义由差商的定义 一阶差商是由节点上函数值定义的，二阶差商是由一阶差商定义的，依此构造差商表：i xi f (xi) 一阶差商一阶差商 二阶差商二阶差商 三阶差商三阶差商 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, , xn例例5.5 计算 (2, 17),

30、 (0, 1), (1, 2), (2, 19)的一至三阶差商。i xi f (xi) f xi 1, xi f xi 2, xi 1, xi f xi 3, xi 2, xi 1, xi0 2 171 0 1 2 1 2 3 2 19 例例5.5 计算 (2, 17), (0, 1), (1, 2), (2, 19)的一至三阶差商。解解 由表易知， f x0, x1 = f 2, 0 = 8 f x0, x1, x2 = f 2, 0, 1 =(8 1)/(2 1) = 3 f x0, x1, x2, x3 = f 2, 0, 1, 2 =(3 8)/(2 2) = 5/4i xi f (x

31、i) f xi 1, xi f xi 2, xi 1, xi f xi 3, xi 2, xi 1, xi0 2 171 0 1 82 1 2 1 33 2 19 17 8 5/4 由差商与导数的关系（性质由差商与导数的关系（性质4）例例 5.6 对 f (x) = x7x4+3x+1， 求 f 20,21， f x,20,21,26 和 f x,20,21,27。解解 显然， f (7) (x) = 7!, f (8) (x) = 0, 由性质4得(7)016( ) ,2 ,2 ,2 1,7!ff x(8)017( ) ,2 ,2 ,2 0.8!ff x01(1)(2)4 1192 ,2 1

32、15,1 21fff5.3.2 Newton插值插值 线性插值线性插值 给定两个插值点(x0, f(x0), (x1, f(x1), x0 x1, 设 N1(x) = a0 + a1(x x0) 直线的点斜式直线的点斜式 代入插值点得， 于是得线性Newton插值公式010010101()()(),.f xf xaf xaf xxxx10010( )(),()(5.18)N xf xf xxxx由插值的唯一性知，L1(x)与 N1(x)为同一多项式，只是表达形式不同而已。 二次二次Newton插值插值 给定三个互异插值点(xi, f (xi), 设代入插值条件： N2(xi) = f (xi)

33、, i =0,1,2, 得二次Newton插值公式为2010201( )()()().Nxaa xxaxxxx0010120012022021020101221(),()(),()()(),.af xaf xxf xf xf xxxxaxxxxf xxf xxf xx xxx2001001201( )(),(),()()(5.19)Nxf xf xxxxf xx xxxxx n 次次Newton插值公式插值公式 给定n+1个插值点(xi, f(xi), i = 0, 1, 2, n, xi互异， 类似地，有二阶至 n 阶差商的定义得(xx0)(xx0)(xx1) (xx0)(xxn1) 上述所

34、有n +1个等式相加，得000( )()() ,f xf xxxf x x000( )() ,f xf xf x xxx00110101012201201010 ,() , ,() , ,() ,nnnnf x xf xxxxf x xxf x xxf xx xxxf x xx xf x xxf xxxxxf x xx其中，插值误差为：000101012011010101( )()() ,()() ,()()() ,()()() ,( )( ).nnnnnnf xf xxxf xxxxxxf xx xxxxxxxf xxxxxxxxxf x xxxNxRx00010101201101( )()

35、() ,()() ,()()() ,nnnNxf xxxf xxxxxxf xx xxxxxxxf xxx0101010( )()()() , ,().nnnnniiRxxxxxxxf x xxxf x xxxxxn次Newton插值公式容易验证，Newton插值满足插值条件： Nn(xi) = f (xi), i = 0, 1, 2, n. 关于关于Lagrange插值和插值和Newton插值的几点说明插值的几点说明1.由插值的唯一性质，Ln(x) = Nn(x)。因此，他们的误差也相同，即当 f(x)Cn+1a, b时，有 故得差商的性质4 此外，比较Nn(x) 和Ln(x) 中xn的系数

36、，即得性质1。(1)0100( ) ,()()(1)!nnnniiiiff x xxxxxxxn(1)01( ) , , ,( , )(1)!nnff x xxxxa ba bn 差商的性质差商的性质 性质性质1 k 阶差商 f x0, x1, xk可表成节点上函数值 f(x0), f(x1), , f(xk) 的线性组合，即 例如例如，k = 2时， (5.17)0101101,().()()()()kkiiiiiiikif xxxf xxxxxxxxx011201202012010210122021,()()().()()()()()()f xxf x xf xx xxxf xf xf x

37、xxxxxxxxxxxx 2. 牛顿插值的误差不要求函数的高阶导数存在，所以更具有一般性。它对 f(x)是由离散点给出的函数情形或 f(x)的导数不存在的情形均适用。3. 引入记号: f x0 = f (x0) , t0(x) = 1, t1(x) = x x0, t2(x) = (x x0)(x x1), , tn(x) = (x x0)(x x1) (x xn1)， 于是 n 次Newton插值公式可表为称 t0(x), t1(x), t2(x), , tn(x) 为Newton插值的基函数，而且满001010100( )( ) ( ) ,( ) ,( ) ,nnnniiiNxtx f x

38、t x f xxtx f xxxt x f xx 足如下关系： ti(x) = ti1(x)(x xi1), i =1,2, n； ti(xj) = 0， j i， ti(xj) 0，j i。4. Newton插值具有承袭性质，即5. Newton插值公式的计算量 乘：1+2+ (n1)+ n = n(n+1)/2 除：n + (n1)+ 2+1 = n(n+1)/2第 i 个节点以后非零101( )( )( ) ,.kkkkNxNxtx f xxx(1)n n例例 5.7 给定四个插值点(2,17), (0,1), (1,2), (2,19), 计算 N2(0.9), N3(0.9)。解解

39、x0= 2，x1=0，x2=1，x3=2，由例5.5知， f x0, x1 = 8， f x0, x1, x2 = 3，f x0, x1, x2, x3 = 5/4，所以， N2(0.9) = 17 8(0.9+2)+3(0.9+2)0.9 = 1.63; N3(0.9) = N2(0.9)+1.250.9(0.9+2)(0.9 1)= 1.30375.2000101012( )()() ,()() ,178(2)3(2) .Nxf xxxf xxxxxxf xx xxxx320120123( )( )()()() ,5178(2)3(2)(2) (1).4NxNxxxxxxxf xx xxx

40、xxxx x Newton插值的算法插值的算法 用牛顿插值公式，首先要计算各阶差商值，然后再计算插值。牛顿插值由承袭性质容易实现，关键是实现差商。 1. 输入初始数据:节点数 n, 插值点序列xi，f(xi), i =0,1,2, n, 及要计算的函数点u； 2. 形成差商表 g k, k =1,2, , n ;（ g k = f x0,xk） 3. 形成插值基函数及插值 t =1, newton = f(x0) 对 i =1,2, , n t = (uxi1) t ; (由tk = (uxk1)tk 1 形成(ux0) (uxi1) ) newton = newton + tgi 4. 输出

41、牛顿插值 Nn(u)=newton。 牛顿插值公式中只用到差商表中对角线上的差商，即 f x0, f x0, x1, f x0, x1, x2, , f x0, x1, xn.可以分别用一维数组 gi 来存放这些差商，i = 0, 1, 2, , n.形成差商具体步骤：形成差商具体步骤：(1) 对gi初始化，即 gi = f (i), i = 0, 1, 2, , n.(2) 除了g0(即 f (x0) 以外，其余函数值在计算一阶差商后 不再使用，因此可用来存放一阶差商，即 g j = f xj 1, xj, j = n, n 1, 2, 1(3) 类似地，计算二阶差商后，除g 1 = f x

42、0, x1外, 其余一 阶差商也不再使用, 可用g j存放二阶差商 f xj 2, xj 1, xj, 即 g j = f xj 2, xj 1, xj, j = n, n 1, 2，(4) 最后， gn = f x0, x1, , xn. 差商表差商表程序 1 计算差商算法：计算差商算法： for i = 0 to n gi = f (xi) for k = 1 to n for j = n to k g j = (g j g j 1)/(xj xj k) 5.4 差分与等距节点插值差分与等距节点插值 设插值节点为等距节点：设插值节点为等距节点： 其中，其中，h称为步长，函数称为步长，函数

43、在在 的函数值为的函数值为 。 5.4.1 差分及性质差分及性质 一阶差分一阶差分: ； 二阶差分二阶差分: 一般地，一般地，m阶差分用阶差分用m-1阶差分来定义：阶差分来定义： k0 xxkh ( )yf x kx()kkyf x kk 1kyyy ()()2kk 1kk 2k 1k 1kyyyyyyy mm 1m 1kk 1kyyy 以上定义的是前差以上定义的是前差,称为向前差分算子。称为向前差分算子。 下面定义向后差分下面定义向后差分,表示向后差分算子：表示向后差分算子： 一般地一般地， 分别称为一阶，二阶，分别称为一阶，二阶，. . . ，m阶向后差分。阶向后差分。kkk 1yyy (

44、)()2kkk 1kk 1k 1k 2yyyyyyy mm 1m 1kkk 1yyy 差分的性质差分的性质 性质性质1. (差分与函数值的关系差分与函数值的关系)n阶差分是阶差分是n+1个函个函数值的线性组合。数值的线性组合。 证明证明: 用数学归纳法立即可得。用数学归纳法立即可得。 性质性质2. (前差与后差的关系前差与后差的关系) ： 证明：在性质证明：在性质1的前差中的前差中, 用用k-n取代取代k即得。即得。 ()nniiknk ii 0y1 C y (),nniiknk n ii 0y1 C y nnk nkyy 性质性质3. (差分与差商的关系差分与差商的关系) 证明：利用差商性质

45、及性质证明：利用差商性质及性质1,得得 性质性质4. (差分与导数的关系差分与导数的关系): 证明：证明：nnk nkyy ,!mkk 1kmkm1f xxxym h ,()()()()()()!()!()()! !()!mk ikk 1k mi 0ikii 1ii 1immmlk ik m lm immi 0l 0mllmmk m lkmml 0yf x xxxxxxxxxxyyiml1i mi1hml l h111 C yym hm h 令令( )( )(,)nnniinyh fx x ( )( )( )!,!( )!nnnnnniii nfyn h f xxn hh fn 差分的计算差分

46、的计算-由差分的定义由差分的定义一阶差分是由节点上函数值定义的，二阶差分是由一阶差分定义的，依此构造差分表：i xi f (xi) 一阶差一阶差分分 二阶差二阶差分分 三阶差三阶差分分 n 阶差阶差分分0 x0 f (x0) 1 x1 f (x1) f0 2 x2 f (x2) f1 2f03 x3 f (x3) f2 2f1 3f0 n xn f (xn) fn-1 2fn-2 3fn-3 nf0 5.4.2 等距节点的牛顿插值公式等距节点的牛顿插值公式 将牛顿插值公式中的差商用差分代替将牛顿插值公式中的差商用差分代替 从而从而,牛顿插值公式在等距插值节点下的形式为：牛顿插值公式在等距插值节

47、点下的形式为： -称牛顿前插公式。称牛顿前插公式。 余项为：余项为： 下面来推导等距牛顿向后插值公式：下面来推导等距牛顿向后插值公式：()()() ,k00 xxxthxkhtk h ( )()()()!2nn000011Nxyt yt t1yt t1tn1y2n ()()( )( )( )( )()()()!()!n 1n 1n 1nn 1ffR xxht t1tnn 1n 1 令 则 ,于是 -称牛顿后插公式。称牛顿后插公式。 余项为：余项为：()nxxthnt0 ()n knn kxxkhxxtk h ( )()()()!2nnnnnn11Nxyt yt t1yt t1tn1y2n ()

48、( )()()()()!n1n1nfRxht t1tnn1 例例: 设设 插值节点为插值节点为 相应的函数值如下表相应的函数值如下表,求求f(2.2)。 ( )xyf xe ,. ,. ,x1 1 5 2 2 5 3 xiyiyi2 2yi3 3yi4 4yi12.718281.54.481691.7634127.289062.907371.143962.512.182494.793431.886060.74210320.085547.903053.109621.223560.48146 解：精确值解：精确值f(2.2)=e2.2=9.025011, 此时此时 .( . )()!2200018

49、 87232N2 2yt yt t1y2 ( . )( . )()()( . ).!332021N 22N 22t t1 t2yN 220166239038553 ( . )( . )()()().!44301N 22N 22t t1 t2 t3y9022374 . , . , .234R015269R001354R000264 .0 xxth22105tt24 5.5 埃尔米特埃尔米特(Hermite) 插值插值 Hermite插值描述：插值描述： 设 f (x)具有一阶连续导数，已知节点上的函数值和导数值，即 (xi, f (xi), (xi, f (xi), i = 0, 1, 2, ,

50、 n, 若存在 2n+1次多项式 H2n+1(x) 满足 则称 H2n+1(x) 为 f (x) 关于节点xi (i = 0,1,2,n)的Hermite插值多项式。 记 f (xi) = yi, f (xi) = mi, i = 0,1,2,n .2121( )(),( )(),0,1,2, ,niniHxf xHxfxin 三次三次Hermite插值的构造插值的构造 存在性存在性 给定 f (xi) = yi, f (xi) = mi, i = 0, 1. 设 代入插值条件: H3(xi) = f(xi), H3(xi) = f (xi), i =0,1,得2330123( ),Hxaa

51、xa xa x23010203002301121311212030021213112323aa xa xa xyaa xa xa xyaa xa xmaa xa xm230002341110120021111()0.01230123xxxxxxxxxxxx 其解存在唯一其解存在唯一, 解解 出出 a0, a1, a2, a3, 代代入即得入即得 H3(x). 基函数法基函数法 每个节点上对应两套基函数：x0: h0(x), g0(x); x1: h1(x), g1(x),满足 或简记为 函数值导数值x0 x1x0 x1 h0(x) h1(x)g0(x)g1(x)1000010000100001

52、(),()0,0,1()0,(),0,1.ijijijijijijh xh xi jg xg xi j 三次Hermite插值多项式为300110011( )( )( )( )( )(5.22)Hxh x yh x ygx mg x m 先构造 h0(x), 设 h0(x) = (a + bx)(x x1)2 ,为方便计算，可设由h0(x0) = 1, 得 a =1；由 所以，同理设h0(x1)=h0(x1)=0210001( )().xxh xab xxxx00012()0,h xbxx 20100101( )1 2.xxxxh xxxxx20111010( )1 2.xxxxh xxxxx

53、210001( )(),xxgxa xxxxg0(x0)=g0(x1)=0, g0(x1)=0由 g0(x0) =1, 得 a =1。所以注：注：我们知道，过 x0, x1 两点的Lagrange插值基函数为 显然， 于是，三次Hermite插值的基函数可表为220100110110( )(),( )().xxxxgxxxg xxxxxxx01010110( ),( ).xxxxlxl xxxxx0011011011(),().lxl xxxxx20000021111122000111( )12 ()()( ),( )12 ()()( ),( )()( ),( )()( ).h xlxxxlx

54、h xl xxxlxgxxx lxg xxx lx 三次Hermite插值多项式为 容易验证，当 f(x)C4a, b时, 三次Hermite插值的误差为 提示：设 作辅助函数 固定x a, b，则(t) 有三个零点 x0, x1, x, 且 x0, x1为二重零 点。反复应用Rolle定理可证。300110011( )( )( )( )( )(5.22)Hxh x yh x ygx mg x m3(4)2201( )( )( )( )() () ,( , )(5.23)4!R xf xHxfxxxxa b 2201( )( )() () .R xk x xxxx22301( )( )( )(

55、 )() () ,xf tHtk x txtx 高次高次Hermite插值的构造插值的构造插值基函数法插值基函数法 给定 n+1个节点 x0, x1,xn 上的函数值 f (xi)和导数值 f(xi) ，可以构造 2n+1 次Hermite插值多项式 满足 其中，hi(x), gi(x)分别为对应于函数值和导数值的不高于 2n+1 次插值基函数，它们满足210( ) ( ) ()( )()nniiiiiHxh x f xg x fx2121()(),()(),0,1,2, .niiniiHxf xHxfxin(),()0,0,1, ,()0,(),0,1, .ijijijijijijh xh

56、xi jng xg xi jn完全仿照三次Hermite插值基函数的求法，可得 容易验证， Hermite插值的误差(定理定理)： 当 f(x)C2n+2a, b时, 则存在(a, b), 使 22( )(1 2 ()()( ),(5.24)( )()( ),0,1,2,iiiiiiiih xl xxxlxg xxx lxin01().niiijjj il xxx提示：对li(x)取对数ln，并注意li(xi)=121(22)22201( )( )( )( )() ()()(5.25)(22)!nnnR xf xHxfxxxxxxn例例5.8 给定 f ( 1)=0, f (1)=4, f (

57、 1)=2, f (1)=0, 求H3(x), 并计算 f (0.5).解解 x0 = 1, x1 = 1, f(0.5)H3(0.5) = 3.5625.3010110( )( ) 0( ) 4( ) 2( ) 04( )2( ).Hxh xh xgxg xh xgx 221220( 1)11( )12(2)(1) ,1 11 ( 1)411( )( 1)(1)(1) ,1 14xxh xx xxgxxxx 2231( )(2)(1)(1)(1) ,2Hxx xxx例例5.9 给定 f(0) = 1, f(1) = 2, f (0) = 2, 构造二次插值函数。解解 (1) 公式法公式法 设

58、 f (1) = m1，由三次Hermite插值公式得， 令 m1 = 0，得到二次Hermite插值函数 P2(x) = x2 + 2x + 1.3010112222122221311( )( )2( )2( )( )0110122 121 00 10 11 0102(0)(1)0 11 0(12 )(1)2(32 )2 (1)(1)(1)Hxh xh xgxm g xxxxxxxxm xx xx xx xm xxm xm221.xx (2) 插值基函数法插值基函数法 设节点 x0上的二次基函数为t0(x), g0(x),节点 x1上的二次基函数为t1(x), 它们满足 设 由t0(x0)

59、=1,即 b(0 1)=1, 得 b = 1。 由t0(x0) =0,即 a(0 1) + a0 +b=0, 得 a = 1 。所以 同理可设， 分别由条件 001000011101001000()1()0()0()0()1()0()0()0()1txt xgxtxt xgxtxt xgx01( )()(),txaxb xx01( )()(),txa xxaxb20( )(1)(1)1,txxxx 210001( )() ,( )()(),t xa xxgxb xxxx22110010()1, ()1( ), ( ).t xgxt xxgxxx 22010( )( )2 ( )2( )21.P

60、 xtxt xgxxx (3) 扩展牛顿法扩展牛顿法 写成差商表的形式，将带导数的节点X0及其上的函数值重复一遍，无导数的节点X1不重复，即 x f(x) f (x) x0 0 1 x1 0 1 2 X1 x2 1 2 1 1 20010012012( )(),(),()()12( 1)(0)(0)21.P xf xf xxxxf xx xxxxxxxxxx 121212()()1 2,10 1f xf xf x xxx011201202,2 1,10 1f xxf x xf xx xxx 0X 扩展牛顿法扩展牛顿法用牛顿差商表构造Hermite插值 给定插值点 (xi, f(xi), f (