第四章 插值方法(1)

1、计算方法 (力学系本科生)4.1 问题的提出 第四章插值方法实际背景4.1 问题的提出表4-1xy0 x0y1x2xnx1y2yny 实验和观察得到的一些离散数据点 需要用这些离散数据点给出简单的函数表达式 来近似原来函数 。 ( ,),( ),0,1,2,., ,iiiix yyf xin( ) x( )f xRemark: 函数 的类型有多种选择，例如代数多项式、三角函数，有理函数等，相应的插值多项式叫代数插值，三角多项式插值，有理函数插值。最常用的类型是代数多项式 。( ) x4.1 问题的提出 函数 有明确表达式，但比较复杂,不易计算和使用,希望用简单函数 近似原来函数 ，便于计算函数

2、值和研究函数特性 。( ) x( )f x( )f x4.1 问题的提出拉格朗日插值的提法 已知离散数据(xi,yi),i=0,1,2,n，其中a=x0 x1 x2 xn =b，寻求一个次数尽可能低的多项式函数P(x)，满足条件P(xi)=yi, i=0,1,2,n 从几何上看，就是在通过给定的n+1个点(xi,yi),i=0,1,2,n，的所有多项式曲线，寻找出次数最低的一个,如图4-1所示。 4.1 问题的提出yxo(x0,y0)(xn,yn)图4-1 有无数条曲线经过n+1个点4.1 问题的提出 定义：如果P(x)是满足P(xi)=yi=f(xi)，i=0,1,n，的次数最低的代数多项式

3、，并且用P(x)来近似函数f(x) ，则称P(x)是f(x)的拉格朗日插值多项式，x0,x1,xn称为插值节点，简称节点；节点所在区间a,b称为插值区间，条件P(xi)=yi ，称为插值条件， f(x)称为被插函数。 4.1 问题的提出【历史注记】插值法历史悠久。据考证，在公元六世纪时，我国刘焯(zhuo)已经把等距二次插值法应用于天文计算。十七世纪时，Newton和Gregory(格雷格里)建立了等距节点上的一般插值公式，十八世纪时，Lagrange(拉格朗日)给出了更一般的非等距节点插值公式。4.1 问题的提出(1) 寻找满足插值条件的分段多项式; 插值问题的进一步提法有：(2) 在插值条

4、件中附加某些节点上的导数值，寻找相应的多项式。 4.1 问题的提出本章主要学习内容 拉格朗日插值多项式存在性和唯一性；拉格朗日插值多项式构造法；误差估计(插值余项)。v拉格朗日插值多项式4.1 问题的提出v差商与差分及其性质v牛顿插值公式牛顿插值多项式构造法；误差估计(插值余项)。4.1 问题的提出v分段插值法分段线性插值；分段三次插值 (Hermite)。v三次样条插值v曲线拟合的最小二乘法4.2 拉格朗日插值(Lagrange interpolation)第四章插值方法4.2.1 拉格朗日插值多项式存在性和唯一性4.2 拉格朗日插值v 定理4-1:满足条件P(xi)=yi, xixj,(i

5、 j) i=0,1,2,n 的拉格朗日插值多项式0( ),nknkkkP xc xcR存在且唯一。4.2.1 存在性和唯一性证明：由插值条件知1110.,0,1,.,nnniniiic xcxc xcyin 这是一个关于c0,c1,cn 的线性方程组，如果方程组系数行列式不为零，则能唯一确定出c0,c1,cn 方程组行系数列式是Vandermonde(范德蒙)行列式：4.2.1 存在性和唯一性10001111111111.1.1().1.1nnnnijj i nnnnnnnnnnnxxxxxxxxxxxxxx 由于节点xixj,(i j),所以上面行列式不为零。于是插值多项式存在且唯一。4.2

6、.1 存在性和唯一性4.2 拉格朗日插值多项4.2.2 拉格朗日插值多项式的构造4.2.2 插值多项式的构造 给定两个节点(x0,y0), (x1,y1)，构造线性多项式L1(x)，使得L1(x0)=y0, L1(x1)=y1。 L1(x)的几何意义是过两点(x0,y0), (x1,y1)的直线。 线性插值(两点插值)yx0oxx1y=L1(x)y=f(x)4.2.2 插值多项式的构造 由解析几何易知该直线方程是：1010010( )(), (yyL xyyxxxx点斜式)011010110( ), ()xxxxL xyyyxxxx两点式4.2.2 插值多项式的构造001010 xxyyxxy

7、y其中 l0(x), l1(x) 为次数不高于1的多项式 ，且满足将 L1(x) 写成10 01 1( )( )( )L xy l xy l x0011( )0 xxlxxx0110( )1xxl xxx显然， L1(x)满足插值条件。 4.2.2 插值多项式的构造因为 l0(x1)=0, l1(x0)=0，故可设 001110( )(),( )()lxxxl xxx由 l0(x0)=1, l1(x1)=1，得 01011011,xxxx所以01010110( ),( )xxxxlxl xxxxx4.2.2 插值多项式的构造 l0(x), l1(x)称为线性插值基函数。于是得到线性插值多项式：

8、10 01 101010110( )( )( )L xy lxy l xxxxxyyxxxx4.2.2 插值多项式的构造抛物线插值(三点二次插值) 设插值节点为(x0,y0), (x1,y1), (x2,y2), 求次数不高于二次的插值多项式 L2(x)，使它满足 L2(xi)=yi, i=0,1,2 使用构造法，设2001122( )( )( )( )L xlx yl x ylx y其中li(x), i=0,1,2, 是二次插值基函数， 4.2.2 插值多项式的构造且在节点上满足00121( )00 xxl xxxxx01120( )10 xxl xxxxx02120( )01xxl xxx

9、xx由此可以求出 li(x), i=0,1,2于是得到抛物线插值多项式0201122012010210122021()()()()()()( )()()()()()()xxxxxxxxxxxxL xyyyxxxxxxxxxxxx4.2.2 插值多项式的构造一般情形的拉格朗日插值多项式设离散数据为(xk,ik), k=0,1,2,n, i 是固定的非零整数 ,且 , ik是Kronecher记号 0in 01.nxxx1,0,ikikik4.2.2 插值多项式的构造现在求插值多项式，记为ln,i(x)，满足插值条件 ln,i(xk)=ik, k=0,1,n，即 ,1,()0,n ikkilxki

10、这说明 x0,xi-1 , xi+1, xn 是 ln,i(x)=0 的根，因而 ln,i(x) 必然有形式：,011( )().()().()n iiinlxa xxxxxxxx4.2.2 插值多项式的构造利用 ln,i(xi)=1 确定系数 a0111().()().()iiiiiinaxxxxxxxx于是011,011().()().()().()().()iinn iiiiiiinxxxxxxxxlxxxxxxxx4.2.2 插值多项式的构造 n+1 个 n 次多项式 ln,0, ln,1, ln,n 称为以 x0, x1, xn 为节点的拉格朗日n次插值基函数，简记为 l0, l1,

11、 ln v 定义：4.2.2 插值多项式的构造 现在考虑一般情况。已知节点 (xi, yi), i=0,1,n, x0 x1xn, 则 00110011( )( )().()().()().()().()nni iiniiniiiiiiiinL xyl xxxxxxxxxyxxxxxxxx是节点(xi, yi), i=0,1,n, 的拉格朗日插值多项式。4.2.2 插值多项式的构造 Ln(x)是次数不超过 n 的多项式，且满足插值条件，由拉格朗日插值多项式存在唯一性定理知 Ln(x) 为拉格朗日插值多项式。4.2.2 插值多项式的构造4.2.3 拉格朗日插值余项(插值误差) 4.2 拉格朗日插

12、值4.2.3 拉格朗日插值余项 如果仅仅知道离散数据，利用插值来得到连续模型，那么对于得到的插值多项式不存在截断误差分析。 如果用插值多项式逼近已知函数，存在用插值多项式代替已知函数时的精度问题，需要截断误差分析。 a,b上用拉格朗日插值多项式 Ln(x) 逼近已知函数 f(x)，节点为 x0,x1,xna,b，xixj, (ij) ,f(xi)=yi, i=0,1,n4.2.3 拉格朗日插值余项 则截断误差Rn(x)是a,b上的函数，Rn(x)=f(x)-Ln(x)，Rn(x)也叫Ln(x)的余项。v 定理 如果f(x) Cna,b,且在(a,b)上有n+1阶导数,则对任何xa,b,存在(

13、)( , )xa b(1)0( )( )( )( )()(1)!nnnniifR xf xL xxxn成立。4.2.3 拉格朗日插值余项 使罗尔(Rolle)定理：若f(x)在a,b上连续,在(a,b)上可导, 且f(a)=f(b), 则存在 满足 。( , )a b( )0f4.2.3 拉格朗日插值余项证明： Rn(xi)=f(xi)-Ln(xi)=0, i=0,1,n可以假定010( )( )()().()( )()nnniiRxk x xxxxxxk xxx于是，问题变为确定k(x)的形式。考虑任一固定xa,b, xxi, i=0,1,n, 求k(x) 。 做辅助函数g(t)00( )(

14、 )( )()( )( )( )()nnniniiig tR tk xtxf tL tk xtx4.2.3 拉格朗日插值余项 t=x时，有000( )( )( )()( )()( )()0nnnniiiiiig xR xk xxxk xxxk xxx所以 g(t)有 x,x0,x1,xn共n+2个相异零点, 且g(t)在(a,b) 上存在n+1阶导数,依次对函数g,g,g,g(n)分别运用罗尔定理,至少有n+1,n,1个相异零点,于是 使( , )a b 1(1)(1)(1)10( )( )( )( )()0nnnnnnitnidgfLk xtxdt4.2.3 拉格朗日插值余项Ln(x)是n次

15、多项式，(1)( )0nnL 的首项为 ，0()niitx1nt110()(1)!nnitnidtxndt于是(1)( )( )(1)!nfk xn故(1)0( )( )()(1)!nnniifR xxxn4.2.3 拉格朗日插值余项Remark(1) 余项表达式只有在 f(x) 的高阶导数存在时才能应用。 (2) 虽然 在(a,b)内不可能具体给出，但我们可以求出 ，于是用插值多项式Ln(x)近似f(x)的截断误差限是 (1)1max( )nna x bfxM 11( )( )(1)!nnnMR xxn由此可以看出4.2.3 拉格朗日插值余项(3) 的大小除了与 Mn+1 有关外，还与 有关

16、，此值与x0,x1,xn的选择和x的位置有关。( )nR x1( )nx(4) 如果f(x)本身为次数不超过n的多项式，则余项为0，插值多项式为其本身。特别地，若f(x)=1，可以得到01( )( ).( )1nlxl xlx4.2.3 拉格朗日插值余项(5) 插值多项式只与数据点(xi,yi)有关，而余项却与整个区域上的f(x)有关。(6) 拉格朗日插值适用于非等步长情形。(7) 当节点数目变化时，需要重新计算全部拉格朗日基函数，因为基函数和每一个节点有关。(8) n+1个节点插值多项式次数不超过n。4.2.3 拉格朗日插值余项例4-1 利用100，121的开方求 。4.2.4 拉格朗日插值

17、例题115解：设 ，已知两个节点x0=100, x1=121，构造线性插值函数并求在点115处的函数值。插值函数为 ( )yf xx211121221( )1211001011100 121121 100 xxxxL xyyxxxxxx于是1115(115)10.71428L例4-2 对任意x，以表距为0.02的正弦表，如果使用线性插值求sin(x)的近似值，试估计其误差。4.2.4 拉格朗日插值例题解： 设x在区间xi, xi+1上, xi+1- xi=0.02,作线性插值，其误差限为12121211( )max ()()(0.02)22iiiixx xR xMxxxxM 其中112max(

18、 )maxsin( )1iiiixx xxx xMfxx 于是4112( )10R x例4-3 设f(x)=e-x在x0=0.10, x1=0.15, x2=0.25, x3=0.30的值分别为0.904837, 0.860708, 0.778801, 0.740818,试构造拉格朗日插值多项式，求e-x在x=0.20的近似值并估计误差。4.2.4 拉格朗日插值例题解：拉格朗日插值多项式为30 01 12 23 3( )( )( )( )( )L xy lxy l xy lxy l x于是30 0112 23 3(0.20)(0.20)(0.20)(0.20)(0.20)0.818730Lyl

19、ylylyl4.2.4 拉格朗日插值例题插值余项(4)34( )( )( )4!fR xx所以(4)30123( )(0.20)(0.20)(0.20)(0.20)(0.20)4!fRxxxx由于(4)0.10.10.3( )max0.91xxfeee 所以63(0.20)0.95 10R例4-4 设x0, x1, ,xn,为n+1个互异节点，li(x)为拉格朗日插值基函数，即 4.2.4 拉格朗日插值例题0,( )njijj iijxxl xxx试证：0(1)( ),1,2,.,nkkiiix l xxkn0(2)()( )0,1,2,.,nkijixxlxkn00( )( ) ( )()n

20、niiiiip xp x l xxx(3) p(x)是最高次项系数为1的n+1次多项式， 则4.2.4 拉格朗日插值例题且有插值余项证：(1)记 ， 则 以 为插值节点的拉格朗日插值多项式为( ),0,1,.,kkxxkn( )kx012,.,nx x xx0( ) ( )nkiiix l x(1)00( )( )( ) ( )()(1)!nnnkkkiiiiixx l xxxn由于 是次数不超过n的多项式 ，则 ( )kx(1)00()( )()0(1)!knnnxkkiiiiixxx l xxxn4.2.4 拉格朗日插值例题于是0( ),0,1,2,.,nkkiiix l xxkn (2)

21、记 , 则 以 为插值节点的拉格朗日插值多项式为( )() ,0,1,.,kkxxtkn( )kx012,.,nx x xx0( ) ( )nkiiix l x且有插值余项(1)00( )( )( ) ( )()(1)!nnnkkiiiiixx l xxxn4.2.4 拉格朗日插值例题由于 是次数不超过n的多项式 ，则 ( )kx(1)00() ()()( )()0(1)!knnnixkkiiiiixtxtxt l xxxn于是0()( )() ,1,2.,nkkiiixtl xxtkn在上式中，令 t=x，即得0()( )0,1,2,.,nkiiixxl xkn(3) 由插值余项公式有 4.

22、2.4 拉格朗日插值例题(1)0000( )( )( ) ( )()(1)!(1)!()()(1)!nnniiiiinniiiipp xp x l xxxnnxxxxn4 插值方法4.3 差商与差分及其性质Difference quotient and difference 4.3 差商和差分差商v 定义函数f(x)在xi处的值fxi=f(xi)，fxi称为f关于xi的零阶差商；f(x)关于xi与xi+1的一阶差商记为fxi,xi+1, 一般地，f(x)关于 xi, xi+1, ., xi+k,的k阶差商记为fxi,xi+1,.,xi+k12111,., ,., ,.,iii kiii kii

23、i ki kif xxxf x xxf x xxxx 111 ,iiiiiif xf xf x xxx 差商的性质： 性质1：差商和函数值有关系0100111(),.,()().()().()njnjjjjjjjjnf xf xxxxxxxxxxxxx证明：用数学归纳法。n=1时010101010110()()()(),f xf xf xf xf xxxxxxxx所以n=1时成立。4.3 差商和差分设n=m-1时成立，即有 101100111(),.,().()().()mjmjjjjjjjmf xf xxxxxxxxxxx121111() ,.,().()().()mjmjjjjjjjmf

24、xf x xxxxxxxxxx于是由差商定义有：01112020,. ,.,.,mmmmf x xxf x xxf x xxxx4.3 差商和差分10001111111()1().()().()()().()().()mjjmjjjjjjmmjjjjjjjjmf xxxxxxxxxxxf xxxxxxxxx4.3 差商和差分1100111001020111111121()1().()().()()()().()()().()().()()()().()mjjmjjjjjjmmmjjjjjjjjmmmmmmf xxxxxxxxxxxf xxxxxxxf xxxxxxxxxf xxxxxxx4.3

25、 差商和差分11011110001020100121()1().()().()11()()()().()()()()()().()mjjmjjjjjjmjjmmmmmmmmmf xxxxxxxxxxxxxxxf xxxxxxxxxf xxxxxxxxx4.3 差商和差分1101110010010011()().()().()()()()().()().()()().()().()mjjjjjjjjmjmmmmmmmjjjjjjjjmf xxxxxxxxxxxf xf xxxxxxxxxf xxxxxxxxx4.3 差商和差分差商性质2：差商关于所含节点对称，即 0110,., ,.,.nnf

26、x xxf x xx即可以任意调换xi,xj的次序而值不变。4.3 差商和差分例 4.3 差商和差分Remark: 一阶差商实际上是微商的离散形式 4.3 差商和差分( )()()limlim ,ijijijjijxxxxijf xf xfxf x xxxv定义：设有等距节点xi=x0+ih, i=0,1,2，其中h是常数，称为步长，记函数f的值 ( )iiff x12(),0,1,2,.2iihff xi令1iiifff1iiifff1122iiifff4.3 差商和差分称 为f在xi的一阶向前差分， 为f在xi的一阶向后差分， 为f在xi的一阶中心差分，分别称为 (向前，向后，中心)差分算

27、子。ififif, n阶(向前,向后,中心)差分分别为 111nnniiifff 111nnniiifff 112211nnniiifff4.3 差商和差分零阶差分为 000iiiiffff 位移算子 ()tEtRtii tE ff即 ( )()tiE f xf xth单位算子I iiIff由 1()iiiiiifffEfIfEI f得 EI 4.3 差商和差分由111()iiiiiifffIfEfIEf得1IE 由得111122221122()iiiiiifffE fEfEEf1122EE4.3 差商和差分一阶差分4.3 差商和差分010fff121fff11nnnfff二阶差分201021

28、02ffffff 21213212ffffff 2212122nnnnnnffffff 用数学归纳法可以证明:4.3 差商和差分12(1)1!2!.( 1)mkk mk mk mmkmm mfffff n4:4.3 差商和差分 证明当节点是等距时，差分与差商存在关系 001(),.,!nnnf xf x xxn h证明：用数学归纳法。 n=1时1000110()()(),f xf xf xf xxxxh 假设n=m-1时成立，即有 4.3 差商和差分于是100111(),.,(1)!mmmf xf x xxmh11121( ) ,.,(1)!mmmf xf x xxmh12011010 ,.,

29、.,.,mmmmf x xxf x xxf x xxxx证毕。4.3 差商和差分1101110()()1(1)!(1)!mmmmmf xf xxxmhmh111001()()()(1)!mmmmmf xf xf xmhmhm h 如果f(x)是x的n次多项式，记()( )ff xhf x 则其k阶差分 是x的n-k次多项式，高于n阶的差分均为零。 ( ), (0)kf xkn(用数学归纳法和泰勒公式 证明)21( )(1)( )()( )( )( ).( )( )2!(1)!nnnnf xf xhf xhhhhfxfxfxfnn4.3 差商和差分4.4 牛顿插值公式 Newton interp

30、olation4 插值方法由差商定义知： 4.4 牛顿插值公式000( )() ,()f xf xf x xxx001011 , ,()f x xf x xf x x xxx010120122 , ,()f x x xf x x xf x x x xxx01010 ,.,., ,.,()nnnnf x xxf x xxf x xxxx.从最后一个式子开始, 把后一个式子代入前一个式子，得 000100112010101110 ,.( )(),(),()().,.,()().(.,()().)()nnnnnnf xf xf x xxxf x x xxxxxf xf x x xxxxxxxxRxx

31、xxxxxxxNx4.4 牛顿插值公式其中Nn(x)叫n次牛顿插值多项式，Rn(x)为插值余项。4.4 牛顿插值公式00100120101011( )(),(),()().,.,()().()nnnNxf xf x xxxf x x xxxxxf x xxxxxxxx4.4 牛顿插值公式 Nn(x)的次数小于等于nRn(xi)=0 Nn(xi)=f(xi), i=0,1,2,n 101210( )( ),.,()nnnniiNxNxf x x xxxx Remark: 4.4 牛顿插值公式牛顿向前插值公式001,.,!nnnyf x xxn h代入牛顿插值公式得200100020110()()

32、( )()()().2!()().()()!nnnnxxxxxxNxf xf xf xhhxxxxxxf xn h如果节点等距，xi=x0+ih, i=0n利用4.4 牛顿插值公式牛顿向后插值公式11211010( )(),(),()().,.,()().()nnnnnnnnnnnnnnNxf xf xxxxf xxxxxxxf xxxxxxxxx120,.,nnnxxxx节点逆序排列4.4 牛顿插值公式01,.,!nnnnyf x xxn h代入牛顿插值公式得利用21210()()( )()()().2!()().()()!nnnnnnnnnnnnxxxxxxNxf xf xf xhhxxx

33、xxxf xn h由于插值多项式的唯一性，所以L(x)=N(x)，即拉格朗日插值多项式等价于牛顿插值多项式。4.4 牛顿插值公式同时，拉格朗日插值的插值余项和牛顿插值余项也相等。 0011(1)00( ) ,.,()().()( )(),(1)!nnnnniniR xf x xxxxxxxxfxxx xn 如果插值节点xi=x0+ih, i=0,1,n为等距节点并要计算x0附近点x (x0 xx1)的函数值，令 4.4 牛顿插值公式0, 01xxtht 代入牛顿向前插值公式，即得200000(1)(1).(1)().2!nt tt ttnN xthyt yyyn 由余项公式得余项 1(1)0(

34、1).()( )( ),(,)(1)!nnnnt ttnR xhfx xn 如果要xn计算附近点x (xn-1xxn)的函数值，令x=xn+th, (-1t0)，代入牛顿向后插值公式得 4.4 牛顿插值公式2(1)().2!(1).(1)!nnnnnnt tNxthyt yyt ttnyn 1(1)0(1).()( )( ),(,)(1)!nnnnt ttnR xhfx xn牛顿插值多项式的另一种解释 4.4 牛顿插值公式记Lk(x)为以(xi,yi),i=0,1,k为插值数据点的k次拉格朗日插值多项式，则可以把n次拉格朗日多项式写为 010211( )( )( )( )( )( ) . (

35、)( )nnnL xL xL xL xL xL xL xLx若记 ，则它是一个k次多项式。1( )( )( )kkkQ xL xLx于是4.4 牛顿插值公式01( )( )nnkkLL xQ x为计算Qk(x)，注意到1( )( )( )0,0,1,.,1kininiiiQ xL xLxyyik而Qk(x)为k次多项式，故Qk(x)有形式011( )()().()kkkQ xaxxxxxx4.4 牛顿插值公式代入 得01( )( )( )nnkkL xL xQx010201011( )()()().()().()nnkL xaa xxaxxxxaxxxxxx由插值条件Pn(xi)=yi知00a

36、y01101()aa xxy0120220212()()()aa xxaxxxxy于是可以逐个解出 4.4 牛顿插值公式01020101()()().().()nnnnnnnnaa xxaxxxxaxxxxy00ay11010()/()ayyxx22020101021()/()()/()/()ayyxxyyxxxx注意到 4.4 牛顿插值公式00af x101,af x x2012,af x x x01,.,nnaf x xx于是把上式代入Ln得到牛顿插值多项式 001001011( ),().,.,()().()nnnNxf xf x xxxf x xxxxxxxx例4-5: (中南大学20

37、01年博士研究生入学试题)求一个次数不高于3的多项式P3(x) ,满足:4.4 牛顿插值公式3333(1)2;(2)4;(3)12;(2)3PPPP解:满足 的拉格朗日插值多项式为:222(1)2;(2)4;(3)12LLL22222(2)(3)(1)(3)(1)(2)( )(1)(2)(3)(1 2)(1 3)(2 1)(23)(3 1)(32)376xxxxxxL xLLLxx 设4.4 牛顿插值公式32( )( )(1)(2)(3)P xL xA xxx 由 得3(2)3P2A 所以323( )29156P xxxx例4-6:给定数据表4.4 牛顿插值公式由求4次牛顿插值多项式及余项。解

38、:由所给的5个数据点做差商表4.4 牛顿插值公式457( )43(1)(1)(2)(1)(2)(4)6601(1)(2)(4)(6)180Nxxxxxxxxxxx4.4 牛顿插值公式(5)4( )( )( )( )(1)(2)(4)(6)(7)5!(1,7)fR xf xNxxxxxx插值余项为4.4 牛顿插值公式21( )1f xx!1 设函数写出它在插值节点1, 0, 1上的插值多项式。2 设 且 互不相等,证明1( )f xax01,.,na x xx012011,.,()().()1,2,.kkf x x xxaxaxaxkn，4.4 牛顿插值公式3 设 为 n+1个互异的节点, li

39、(x) (i=0,1,n) 为拉格朗日插值基函数,令li(x)=ci ,证明:01,.,nx xx00 121,00,1,2,.,( 1).,1nkiiinkc xknx x xxkn4 插值方法4.5 分段插值法 通常为了获得好的逼近效果，插值节点的间距应当较小，节点数目应该较多。这时，如果采用整体(一个插值多项式)插值，则关于给定函数值的插值多项式的次数一般很高，称为高次插值。4.5 分段插值法当次数太高时，会出现龙格现象(C. Runge)，这个现象是龙格在1901年发现的:用高次插值多项式可能产生极大误差。4.5 分段插值法龙格用了实例来说明这个现象：设f(x)是定义在-5,5上的函数

40、 21( )1f xx对于n个节点(n=1,2,)，由等距节点集105,0,1,.,niiSxinn 决定一个拉格朗日插值多项式 Ln(x)201( )( )1nniiiL xl xx4.5 分段插值法在 附近，Ln(x)离开f(x)很远。 5x 4.5 分段插值法用相对较少的数据点作插值节点，可以避免大的误差。但是我们既然有了很多数据点，就当然希望在插值时能够全部用上这些数据点，用得越多越好。 4.5 分段插值法 problem 解决这一矛盾的办法是分段插值，即，用分段多项式来代替单一多项式进行插值。4.5 分段插值法 solution 4.5.1 分段线性插值 4.5 分段插值法v 定义：

41、设a=x0 x1xn=b节点上的函数值为y0,y1,yn，若插值函数S1(x)满足 4.5.1 分段线性插值(1) 即在区间上连续 01( ) , S xC a b(2)1( ),0,1,2,.,iiS xyin(3) S1(x)在每个子区间xi,xi+1 , i=0,1,2n-1都是线性函数 那么，S1(x)叫a,b上的分段线性插值函数。 S1(x)在区间xi,xi+1上的拉格朗日形式是 4.5.1 分段线性插值11111111( ),iiiiiiiiiiiiiixxxxS xyyxxxxl ylyxxx S1(x)在区间xi,xi+1上的牛顿形式是 111( ) ,(),iiiiiiS x

42、yf x xxxxxx4.5.1 分段线性插值 S1(x)在区间a,b上可用插值基函数表示为 10( )( )niiiS xl x y其中li(x)叫分段线性插值基函数11111111,( ),0, , iiiiiiiiiiiiixxxxxxxxxl xxxxxxxxxxa b且1,2,.1in 分段线性插值基函数li(x)在xi附近不为零，在其它地方都为零。这种性质叫局部非零性质，当插值点函数值有误差时，这种性质可以把误差控制在一个局部区域内。 4.5.1 分段线性插值4.5.2 分段三次插值(Hermite)4.5 分段插值法 有些实际问题中不但要求插值函数P(x)在节点处的函数值与f(x

43、)在节点处的值相等，而且要求P(x)与f(x)在节点处的导数值也相等。4.5.2 分段三次插值4.5.2 分段三次插值v 定义：设函数f(x)在节点a=x0 x1 xn=b上的函数值为y0, y1, , yn其导数值为 ，如果S3(x)满足 01,.,nyyy(1) S3(x)在a,b上一阶导数连续(2) S3(xi)=yi,3( ),0,1,.,iiSxyin(3) S3(x)在每个子区间xi, xi+1上是次数小于等于3的多项式 则称S3(x)为插值区间a,b上的分段三次插值函数或Hermite插值函数。 S3(x)在区间xi, xi+1上的表达式为 4.5.2 分段三次插值31111(

44、)( )( )( )( )iiiiiiiiSxyxyxyxyx满足 Si(xi)=yi, Si(xi+1)=yi+1, 3( )iiSxy311()iiSxy4.5.2 分段三次插值由 Si(xi)=yi 得31111( )( )( )( )( )iiiiiiiiiiiiiiSxxyxyxyxyyai(x)ai+1(x)bi(x)bi+1(x)f(xi)f(xi+1)f(1)(xi)f(1)(xi+1)4.5.2 分段三次插值由 Si(xi)=yi 得31111( )( )( )( )( )iiiiiiiiiiiiiiSxxyxyxyxyyai(x)ai+1(x)bi(x)bi+1(x)f(x

45、i)1000f(xi+1)f(1)(xi)f(1)(xi+1)4.5.2 分段三次插值由 Si(xi+1)=yi+1 得ai(x)ai+1(x)bi(x)bi+1(x)f(xi)1000f(xi+1)f(1)(xi)f(1)(xi+1)31111111111()()()()()iiiiiiiiiiiiiiSxyxxyxyxyy4.5.2 分段三次插值由 Si(xi+1)=yi+1 得ai(x)ai+1(x)bi(x)bi+1(x)f(xi)1000f(xi+1)0100f(1)(xi)f(1)(xi+1)31111111111()()()()()iiiiiiiiiiiiiiSxyxxyxyxy

46、y4.5.2 分段三次插值ai(x)ai+1(x)bi(x)bi+1(x)f(xi)1000f(xi+1)0100f(1)(xi)f(1)(xi+1)由 得3( )iiSxy31111( )( )( )( )( )iiiiiiiiiiiiiiSxyxyxyyxyx4.5.2 分段三次插值ai(x)ai+1(x)bi(x)bi+1(x)f(xi)1000f(xi+1)0100f(1)(xi)0010f(1)(xi+1)由 得3( )iiSxy31111( )( )( )( )( )iiiiiiiiiiiiiiSxyxyxyyxyx4.5.2 分段三次插值ai(x)ai+1(x)bi(x)bi+1

47、(x)f(xi)1000f(xi+1)0100f(1)(xi)0010f(1)(xi+1)由 得311()iiSx)()()()()iiiiiiiiiiiiiiSxyxyxyxyyx 4.5.2 分段三次插值ai(x)ai+1(x)bi(x)bi+1(x)f(xi)1000f(xi+1)0100f(1)(xi)0010f(1)(xi+1)0001由 得311()iiSx)()()()()iiiiiiiiiiiiiiSxyxyxyxyyx 4.5.2 分段三次插值4.5.2 分段三次插值由此可以求出 11( ),( ),( ),( )iiiix

48、xxx例如求 ( )ix由于 11()()0iiiixx可知xi+1是 的两重零点，又 最高三次，可设其形式为 ( )ix( )ix21( )()()iixaxb xx利用 可以确定系数 ( )1iix( )0iix4.5.2 分段三次插值得到 2111( )(12)()iiiiiiixxxxxxxxx于是 211111(12)() , ,( )0, , , iiiiiiiiiiixxxxxx xxxxxxxx xxa b且4.5.2 分段三次插值同样可得21111()() , ,( )0, , , iiiiiiiiixxxxxx xxxxxx xxa b且4.5.2 分段三次插值211111

49、1(12)() , ,( )0, , , iiiiiiiiiiixxxxxx xxxxxxxx xxa b且211111()() , ,( )0, , , iiiiiiiiixxxxxx xxxxxx xxa b且4.5.2 分段三次插值4.5.2 分段三次插值于是 时，由1,iixxx2111111(12)() ,( )0, , kkkkkkkkkkkxxxxxxxxxxxxxxxxa b且1ki 211111(12)() ,( )0, , iiiiiiiiiiixxxxxxxxxxxxxxxxa b且4.5.2 分段三次插值由211111()() ,( )0, , kkkkkkkkkxxx

50、xxxxxxxxxxxa b且1ki 21111()() ,( )0, , iiiiiiiiixxxxxxxxxxxxxxa b且4.5.2 分段三次插值30( )( )( ), , niiiiiSxyxyxxa b 例:设 ，在1,4中构造 三次Hermite插值多项式.4.5.2 分段三次插值( )f xx解:01011,4,11,42xxyy1( )2fxx(1)0.5,(4)0.25,ff4.5.2 分段三次插值201( )(12 )(4)27xx x201( )(1)(4)9xxx211( )(112 )(1)27xx x211( )(4)(1)9xxx2232212( )(12 )

51、(4)(11 2 )(1)272711(1)(4)(4)(1)1836Hxx xx xxxxx4 插值方法4.6 三次样条插值4.6.1 问题的提出4.6 三次样条插值 在分段多项式插值中，分段线性插值函数在节点处连续，但不可导，分段三次Hermite插值多项式在节点处有连续一阶导数，但是这种连续一阶导数的光滑程度有时并不能满足实际问题要求，例如，有时我们需要插值函数的曲率连续，这就要求二阶导数连续。 4.6.1 问题的提出 飞机外形的理论模线，船体放样型值线通常要求二阶光滑，即具有连续二阶导数，最初工程师在绘制这类线型构件的外形轮廓时，使用一种叫“样条”(spline)的绘图工具，这个工具是

52、具有弹性的细木条或有机玻璃条，使它逐个通过所绘的数据点，在这些数据点处分别用压铁压住，在其它地方让其自然弯曲，沿这样的样条压出来的曲线叫样条曲线。 4.6.1 问题的提出 如果把样条看作弹性细梁，压铁看作作用在梁上的集中载荷，则样条曲线在力学上可当作细弹性梁在集中载荷作用下的弯曲变形曲线。设曲线方程为y=y(x),则由材料力学知y=y(x)在整体上具有二阶连续导数，在每一个小段(即相邻两压铁之间)上是三次多项式。这就是样条插值的一个工程背景。 4.6.1 问题的提出4.6.2 三次样条插值的定义4.6 三次样条插值v 定义：给定区间a,b的一个划分a=x0 x1xn=b,如果函数S(x)满足条

53、件：(1)在整个区间a,b上具有二阶连续导数；(2)在每个子区间xi-1, xi (i=1, 2, , n) 上是x的三次多项式。则称S(x)是以 x0, x1,xn,为节点的三次样条函数。4.6.2 三次样条插值定义 如果给定函数y=f(x)在xi点的值为yi, (i= 0, 1, n),而S(x)满足S(xi)=yi, (i=0,1,n),则称S(x)为f(x)的三次样条插值函数。 要确定S(x)在每个区间上的三次多项式，S(x)=a0+a1x+a2x2+a3x3共需要确定4n个待定系数，由S(xi)=yi,(i=0,1,n)可有n+1个条件，由S(x)在整个区间上具有连续二阶导数知在内部

54、节点xi (i=1,n-1)处，S(x),S(x),S(x)连续, 这样又有3(n-1)个条件，所以共有n+1+3(n-1)=4n-2个条件。 4.6.2 三次样条插值定义还差2个条件。 为了唯一确定4n个待定系数，需要在a,b端点补充两个边界条件，即端点条件。常见的边界条件有：4.6.2 三次样条插值定义 第一种边界条件：在端点x0,xn,处给定一阶导数的值，即给定端点的转角，S(x0)=m0, S(xn)=mn 第二种边界条件：给定端点x0,xn处的二阶导数值, 即给出了端点处的曲率或弯矩, S(x0)=M0, S(xn)=Mn 特别地，当S(x0)= S(xn)=0时为简支情况，称为自然

55、边界条件；否则，称为固支边界。 4.6.2 三次样条插值定义4.6.3 三次样条插值函数的构造 三转角方程4.6 三次样条插值 如何在子区间xi, xi+1, (i=1,n)上写出三次样条插值函数的表达式S(x)？4.6.3 三转角方程第一种边界条件，转角边界。假设已经知道节点xi (i=0,1,n)处的一阶导数值，即S(xi)=mi, (i=0,1,n)。可以发现，S(x)就是分段三次Hermite插值多项式,即 0( )( )( )niiiiiS xyxmx其中 是插值基函数：( ),( )iixx2111121111() (12),0( )() (12),0,iiiiiiiiiiiiii

56、iiixxxxxxxixxxxxxxxxxxxinxxxx其它4.6.3 三转角方程 显然，S(x)以及S(x)在整个区间a,b上是连续的.21112111() (),0( )() (),0,iiiiiiiiiiiiixxxxxxxixxxxxxxxxxinxx其它4.6.3 三转角方程 S(x)在xi,xi+1上的表达式是 1111( )( )( )( )( )iiiiiiiiS xyxyxmxmx 于是 1111( )( )( )( )( )iiiiiiiiS xyxyxmxmx 验证 11( ),()iiiiS xmS xm4.6.3 三转角方程进一步有111111122113( )(

57、)( )( )( )6246426(2 )()iiiiiiiiiiiiiiiiiiiiiSxyxyxmxmxxxxxxxmmhhxxxyyh 其中 hi=xi+1-xi4.6.3 三转角方程于是得112426( )()iiiiiiiiSxmmyyhhh 同理可得S(x)在区间xi-1,xi上的表达式111111122111121( )( )( )( )( )6246426(2 )()iiiiiiiiiiiiiiiiiiiiiSxyxyxmxmxxxxxxxmmhhxxxyyh其中 hi-1=xi-xi-1 4.6.3 三转角方程所以有112111246( )()iiiiiiiiSxmmyyhh

58、h由 得( )( )iiSxSx11112211111112()3(),(1,2,.,1)iiiiiiiiiiiiiyyyymmmhhhhhhin11, ,iiiiiiiffyff x xh用 除两边，并利用111iihh4.6.3 三转角方程上式整理为112,1,2,.,1iiiiiimmmgin其中11111,3(, ,),(1,2,.,1)iiiiiiiiiiiiiihhhhhhgf xxf x xin4.6.3 三转角方程这是一组有n+1个未知数mi, i=0,1,n的n-1个方程。补充上边界条件S(x0)=m0, S(xn)=mn, 则得到关于mi, i=1,2,n-1的一个方程组

59、1111022221111(1) (1)20020.002nnnnnnnmgmmgmgm 4.6.3 三转角方程在上面方程组中，由于01012hhh11112,1,2,.,2iiiiiiiihhinhhhh 11212iniihhh所以方程组对角占优，可以通过追赶法求解。4.6.3 三转角方程4.6.4 三次样条插值函数的构造 三弯矩方程4.6 三次样条插值假设二阶导数值S(xi)=Mi, i=0,1,2,n来表示S(x)。 4.6.4 三弯矩方程由于S(x)在区间xi,xi+1上是三次多项式，所以S(x)在xi,xi+1上是线性函数，对Mi,Mi+1进行拉格朗日插值 11( )iiiiiix

60、xxxSxMMhh这样得到了二阶导数在xi,xi+1上的表达式，并且满足S(xi)=Mi, S(xi1) =Mi1, 4.6.4 三弯矩方程4.6.4 三弯矩方程对S(x)积分两次得到S(x) 331112()()( )66iiiiiixxxxS xMMc xchh11( )iiiiiixxxxSxMMhh4.6.4 三弯矩方程由S(xi)=yi, S(xi+1)=yi+1,定出积分常数，得332111211()()( )()666(),0,1,.,16iiiiiiiiiiiiiiiixxxxM hxxS xMMyhhhMhxxyinh对S(x)求导得 4.6.4 三弯矩方程221111()(