第2章 插值法

上页下页第2章插值法插值法的一种古老的数学方法，它来自生产实践.早在一千多年前的隋唐时期制定历法时就应用了二次插值，隋朝刘焯(公元6世纪)将等距节点二次插值应用于天文计算.但插值理论都是在17世纪微积分产生以后才逐步发展的，牛顿的等距节点插值公式及均差插值公式都是当时的重要成果.近半世纪由于计算机的广泛使用和造船、航空、精密机械加工等实际问题的需要，使插值法在理论上得到进一步发展，尤其是20世纪40年代后期发展起来的样条(spline)插值，更获得广泛应用，称为计算机图形学的基础.上页下页2.1.1插值问题的提出2.1引言许多实际问题都用函数y=f(x)来表示某种内在规律的关系，其中相当一部分函数是通过实验或观测得到的.虽然f(x)在某个区间[a,b]上是存在的，有的还是连续的，但却只能给出[a,b]上一系列点的xi函数值yi=f(xi)(i=0,1,...,n)，这只是一张函数表.有的函数虽有解析表达式，但由于计算复杂，使用不方便，通常也造一个函数表，如大家熟悉的三角函数表、对数表、平方根和立方根表等.上页下页为了研究函数的变化规律，往往需要求出不在表上的函数值，因此，我们希望根据给定的函数表做一个既能反映函数y=f(x)的特性，又便于计算的简单函数P(x)，用P(x)近似f(x).通常选一类较简单的函数(如代数多项式或分段代数多项式)作为P(x),并使P(xi)=f(xi)对i=0,1,...,n成立.这样确定的P(x)就是我们希望得到的插值函数.例如，在现代机械工业中用计算机程序控制加工机械零件，根据设计可给出零件外形曲线的某些型值点(xi,yi)(i=0,1,...,n)，加工时为控制每步走刀方向及步数，就要算出零件外形曲线其它点的函数值，才能加工出外表光滑的零件，这就是求插值函数的问题.下面我们给出有关插值法的定义.上页下页定义设y=f(x)在区间[a,b]上有定义，且已知在点a≤x0x1…xn≤b上的值y0,y1,…,yn，若存在一简单函数P(x)，使P(xi)=yi(i=0,1,...,n)(1.1)其中ai为实数，就称P(x)为插值多项式，相应的插值法称为多项式插值.若P(x)为分段的多项式，就称为分段插值.若P(x)为三角多项式，就称为三角插值.本章只讨论多项式插值与分段插值.成立，就称P(x)为f(x)的插值函数，点x0,x1,…,xn称为插值节点，包含插值节点的区间[a,b]称为插值区间，求插值函数P(x)的方法称为插值法.若P(x)是次数不超过n的代数多项式，即P(x)=a0+a1x+a2x2+...+anxn(1.2)上页下页从几何上看，插值法就是求曲线y=P(x)，使其通过给定的n+1个点(xi,yi),i=0,1,…,n，并用它近似已知曲线y=f(x)，见下图.上页下页2.1.2多项式插值设在区间[a,b]上给定n+1个点a≤x0x1…xn≤b上的函数值yi=f(xi),(i=0,1,…,n)，求次数不超过n的多项式(1.2)，使P(xi)=yi，i=0,1,…,n.(1.3)由此可得到关于系数a0,a1,…,an的n+1元线性方程组010000111101(1.4)nnnnnnnnnaaxaxyaaxaxyaaxaxy上页下页此方程组有n+1个方程,n+1个未知数,其系数行列式是范德蒙(Vandermonde)行列式：200021110211()01nnjinjinnnnxxxxxxxxxxx因此，线性方程组(1.4)的解a0,a1,…,an存在且唯一，于是有下面结论.定理1满足插值条件(1.3)的插值多项式P(x)是存在唯一的.虽然直接求解方程组(1.4)就可得到插值多项式P(x)，但这是求插值多项式最复杂的方法，一般是不用的.下面两节将给出构造插值多项式更简单的方法.上页下页约瑟夫·拉格朗日，全名约瑟夫·路易斯·拉格朗日（Joseph-LouisLagrange1735~1813）法国数学家、物理学家。Lagrange法1736-18132.2拉格朗日插值1736年1月25日生于意大利都灵，1813年4月10日卒于巴黎。他在数学、力学和天文学三个学科领域中都有历史性的贡献，其中尤以数学方面的成就最为突出。上页下页2.2.1线性插值与抛物线插值对给定的插值点为求得形如(1.2)式的插值多项式可以有不同方法，下面先讨论n=1的简单情形，假定给定一个区间[xk,xk+1]及端点函数值yk=f(xk),yk+1=f(xk+1)，要求线性插值多项式L1(x)，使它满足L1(xk)=yk,L1(xk+1)=yk+1.y=L1(x)的几何意义就是通过两点(xk,yk)与(xk+1,yk+1)的直线，如图所示，L1(x)的表达式可由几何意义直接给出()yfx1()yLxyxkx1kx1kyky上页下页由两点式看出，L1(x)是由两个线性函数1111(),()kkkkkkkkxxxxlxlxxxxx111()()kkkkkkyyLxyxxxx11111()kkkkkkkkxxxxLxyyxxxx(点斜式)(两点式)(2.1)(2.2)线性组合得到的，其系数分别为yk及yk+1，即显然，lk(x)及lk+1(x)也是线性插值多项式，在节点xk及xk+1上分别满足条件111()()().kkkkLxylxylx(2.3)1111()1,()0;()0,()1.kkkkkkkklxlxlxlx上页下页我们称函数lk(x)及lk+1(x)为线性插值基函数，它们的图形为插值基函数的特点：xkxk+1lk10lk+1011xkxk+1lklk+1kxy1Ox()klxy11()klxOx1kxkx1kx上页下页我们知道y=L2(x)在几何上就是通过三点(xk-1,yk-1),(xk,yk),(xk+1,yk+1)的抛物线，为了求出L2(x)的表达式，可采用基函数方法，此时基函数lk-1(x),lk(x),lk+1(x)是二次函数，且在节点上分别满足条件下面讨论n=2的情况，假定插值节点为xk-1,xk,xk+1，要求二次插值多项式L2(x)，使它满足L2(xk-1)=yk-1,L2(xk)=yk,L2(xk+1)=yk+1.111111()1,()0,,1;()1,()0,1,1;()1,()0,1,;kkkjkkkjkkkjlxlxjkklxlxjkklxlxjkk(2.4)上页下页满足条件(2.4)的插值基函数是很容易求出的，例如求lk-1(x)，因它有两个零点xk及xk+1，故可表示为11()()(),kkklxAxxxx其中A为待定系数，可由条件lk-1(xk-1)=1定出1111,()()kkkkAxxxx于是11111()()(),()()kkkkkkkxxxxlxxxxx同理可得1111()()(),()()kkkkkkkxxxxlxxxxx11111()()(),()()kkkkkkkxxxxlxxxxx上页下页1kx1()klx1kxxOykx()klx1kxxOykx1()klx1kxxOykx1kx1kx二次插值基函数lk-1(x),lk(x),lk+1(x)在区间[xk-1,xk+1]上的图形见下图.利用二次插值基函数lk-1(x),lk(x),lk+1(x)，立即得到二次插值多项式21111()()()().kkkkkkLxylxylxylx(2.5)上页下页21111()()()().kkkkkkLxylxylxylx(2.5)显然，它满足条件L2(xj)=yj(j=k-1,k,k+1).将上面求得的基函数lk-1(x),lk(x),lk+1(x)代入(2.5)式，得1211111111111111()()()()()()()()()()()()()kkkkkkkkkkkkkkkkkkkkkxxxxLxyxxxxxxxxyxxxxxxxxyxxxx上页下页2.2.2拉格朗日插值多项式上面我们对n=1及n=2的情况，得到了一次与二次插值多项式L1(x)及L2(x),它们分别由(2.3)式与(2.5)式表示，这种用插值基函数表示的方法容易推广到一般情形.下面讨论如何构造通过n+1个节点x0x1…xn的n次插值多项式Ln(x)，假设它满足条件Ln(xj)=yj,j=0,1,…,n.(2.6)为了构造Ln(x)，我们先定义n次插值基函数.上页下页定义1若n次多项式lj(x)(j=0,1,…,n)在n+1个节点x0x1…xn上满足条件1,()(,0,1,,)0,jkkjlxjknkj(2.7)就称这n+1个n次多项式l0(x),l1(x),…,ln(x)在为节点x0,x1,…,xn上的n次插值基函数.对n=1及n=2时的情况前面已经讨论.用类似的推导方法，可得到n次插值基函数为00()()()()()(0,1,,)nkkknxxxxlxxxxxkn11()()kkxxxx11()()kkkkxxxx(2.8)上页下页显然它满足条件(2.7).于是，满足条件(2.6)的插值多项式Ln(x)可表示为00110()()()()().(2.9)nnnnkkkLxylxylxylxylx由lk(x)的定义，知0()(),0,1,,.nnjkkjjkLxylxyjn形如(2.9)式的插值多项式Ln(x)称为拉格朗日(Lagrange)插值多项式，而(2.3)式与(2.5)式是当n=1和n=2时的特殊情况.上页下页若引入记号1010()()()()(),(2.10)nnnkkxxxxxxxxx容易求得1011()()()()().nkkkkkkknxxxxxxxxx于是公式(2.9)可改写成101()().(2.11)()()nnnkkknkxLxyxxx注意，n次插值多项式Ln(x)通常是次数为n的多项式，特殊情况下次数可能小于n.例如通过三点(x0,y0),(x1,y1),(x2,y2)的二次插值多项式L2(x)，如果三点共线，则y=L2(x)就是一直线，而不是抛物线，这时L2(x)是一次多项式.上页下页注意:(1)对于插值节点,只要求它们互异,与大小次序无关;(2)插值基函数lk(x)仅由插值节点xk(k=0,1,…,n)确定,与被插函数f(x)无关;(3)插值基函数lk(x)的顺序与插值节点xk(k=0,1,…,n)的顺序一致.上页下页所以019141()(9),()(4)495945xxlxxlxx1001111()()()2(9)3(4)55Lxylxylxxx1137(7)2.65L01,4,9,yxxx7例1已知用线性插值(即一次插值多项式)求的近似值。012,3,yy基函数分别为:解插值多项式为23(9)(4)55xx1(6)5x()上页下页4,3,1,13210xxxx)4)(3)(1(401)41)(31)(11()4)(3)(1()(0xxxxxxxl)4)(3)(1(121)41)(31)(11()4)(3)(1()(1xxxxxxxl)4)(1)(1(81)43)(13)(13()4)(1)(1()(2xxxxxxxl)3)(1)(1(151)34)(14)(14()3)(1)(1()(3xxxxxxxl例2求过点(-1,-2),(1,0),(3,-6),(4,3)的抛物线插值(即三次插值多项