数值计算方法插值法

1、插值法的概念n已知函数在n+1个点x0 ,x1 ,xn 上的函数值 yi=f(xi ), (i=0,1,n) ，求一个简单函数y=P(x),使其满足: P(xi )=yi ,(i=0,1,n) 。即要求该简单函数的曲线要经过y=f(x)上已知的这个n+1个点： (x0 ,y0 ),(x1 ,y1 ),(xn ,yn ),同时在其它xa,b上要估计误差: R(x) = f(x) - P(x)n其中P(x)为f(x)的插值函数，x0 ,x1 ,xn 称为插值节点，包含插值节点的区间a,b 称为插值区间，求插值函数P(x)的方法称为插值法。若P(x)是次数不超过n的代数多项式，就称P(x)为插值多项

2、式，相应的插值法称为多项式插值。若P(x)是分段的多项式，就是分段插值。若P(x)是三角多项式，就称三角插值。为什么要插值 n1.在工程技术和科学研究中，有时对一个函数f(x)只能通过实验或观测的手段得到它在某个区间a,b上的有限个不同点上的函数值，也就是只知道一张函数表，却没有明确的表达式。n2.虽然函数有明确的表达式，但由于形式复杂，不便于计算和使用，所以人们往往希望做出一个既能反映函数的特性，又便于计算的简单函数P(x)去近似替代f(x)。问题的提出 010011( )1,( ),(0,1, ),( )( ),(0,1, ).( )1,( )( )( )niiiinnyf xnxxxyf

3、 xinyP xP xyinyf xnxyx yxyxa bR xf xP x插值问题的数学提法：已知函数在个点上的函数值求一个多项式，使其满足即要求该多项式的函数曲线要经过上已知的个点同时在其他上要估计误差插值问题n 1 ,0011nnxyx yxy( )( )( )Rxf xP x n 1 个点个点同时在其它同时在其它上要估计误差上要估计误差。当当时时,求一次多项式求一次多项式插值法的分类n一，拉格朗日插值法n二，牛顿插值法n三，埃尔米特插值法n四，分段多项式插值法n五，样条插值法一，拉格朗日插值法流程：线性插值（一次插值）二次插值 n次拉格朗日插值法的方程组法证明用中国剩余定理证明拉格朗

4、日插值多项式。一次插值 100111( ),nP xxyx y当时，求一次多项式要求通过两点二次插值 20011222( ),nP xxyx yxy当时，求二次多项式要求通过三点拉格朗日插值公式n线性插值（一次插值） 1111111111 ( ),(),()( )(),(),kkkkkkkkkkkkkkf xxxyf xyf xyP xyP xyP xxyxy已知函数在区间的端点上的函数值，求一个一次函数使得。其几何意义是已知平面上两点，求一条直线过该已知两点。线性插值n插值函数和插值基函数1111111111111( )()( )( ),( )kkkkkkkkkkkkkkkkkkkkkkkk

5、yyPxyxxxxxxxxyyPxyyxxxxxxxxlxlxxxxx由直线的点斜式公式可知：，把此式按照和写成两项:，记，称它们为一次插值基函数。线性插值n基函数的特点：( )klxkx1kx( )klx1( )kxl1( )klxkx1kx11111( )( )( ),k kkkkkkkP xy lxylxyyxx拉格朗日型插从而，此形式称之为。其中，插值基函数与、无关，而由插值结点 、值多项式决定例子0101011lg101 , lg201.3010lg12( )lg( )lg(10)1(20)1.3010102011.3010201101( )(20)( )(10)10201020 1

6、010f xxf xxffxxyyxxlxxl xx 例：已知，利用插值一次多项式求的近似值。解：，设，则插值基本多项式为：，例子10 01 1111.3010( )( )( )(20)(10)101011.3010(12)(1220)(12 10)1.06021010lg12lg10 lg20 lg121.0792).P xy lxy l xxxP 于是，拉格朗日型一次插值多项式为：故即由和两个值的线性插值得到，且具有两位有效数字（精确解二次插值多项式 111111221122111111 ( ),() , ()()( )()()(),kkkkkkkkkkkkkkkkkkkkkyf xxxx

7、yf xyf xyf xP xP xyP xyP xyxyxyxy已知函数在点上的函数值，。求一个次数不超过二次的多项式，使其满足，。其几何意义为：已知平面上的三个点：，求一个二次抛物线，使得该抛物线经过这三点。二次插值基本多项式11 ,kkkxxx有三个插值结点，构造三个插值基本多项式，要求满足：（1）基本多项式为二次多项式；（2）它们的函数值满足下表：1kxkx1kxkx1kx 1( )klx( )klx1( )klx1kx1( )klx( )klx1( )klx拉格朗日型二次插值多项式拉格朗日型二次插值多项式 2111122 ( )( )( )( )( )( ) , 1, ,1kkk k

8、kkiiP xylxy lxylxP xP xyikk k由前述，拉格朗日型二次插值多项式：，是三个二次插值多项式的线性组合，因为它是次数不超过二次的多项式，且满足：二次插值基本多项式1kxkx1kx 1( )klx( )klx1( )klx111111111111111111()0,()0( )()()( )()()()1()()1()()1( )()()()kkkkkkkkkkkkkkkkkkkkkkkkklxlxlxxxxxlxa xxxxlxa xxxxxxxxalxxxxxxx因为，故有因子，而其已经是一个二次多项式，仅相差一个常数倍，可设，又因为，故，得：，从而1111111111

9、1()()()()()( )( )()()()()kkkkkkkkkkkkkkkkxxxxxxxxxxlxlxxxxxxxxx，例子2例 ：已知ixlgiiyxixlgiiyxlg12利用此三值的二次插值多项式求的近似值012012101520(15)(20)1( )1520(10 15)(1020)50(10)(20)1( )1020(15 10)(1520)25(10)(15)1( )1015(20 10)(20 15)50 xxxxxlxxxxxl xxxxxlxxx 解：设，则例2（续）ixlgiiyx20 01 12 221( )( )( )( )2015501.17611.3010

10、10201015255011.1761(12)1220 12 1512 10 122050251.301012 10 12 151.076650lg12lg121.07923P xy lxy l xy lxxxxxxxP故所以：利用三个点进行抛物线插值得到的的值，与精确值相比，具有 位有效数字。插值基函数01101101101 ()0,( )()()()()( )()()()()( )1()()()()( )()()(ikiiiniiiniiiiniiiiil xkil xxxxxxxxxnl xa xxxxxxxxl xaxxxxxxxxl xxxxxx由于，故有因子：，因其已经是次多项式，

11、故而仅相差一个常数因子。令：由，可以定出 ，进而得到：1)()iinxxx插值基函数01 11( ), ( ), ( )( )1( )2( )1,()0,niiiiiknnnlx l xlxl xl xnl xnl xki过个不同的点分别决定个 次插值函数。每个插值基本多项式满足：（）是 次多项式；（ ）而在其它 个。n次拉格朗日型插值多项式Pn(x)01010 01 10( )1( ), ( ), ( ),( )( )( )( )( )( )( )0,1,nnnnnn nk kknniiP xnnlx l xlxyyyP xy lxy l xy lxy lxP xnP xyin是个 次插值基

12、本多项式的线性组合，相应的组合系数是。即从而是一个次数不超过 的多项式，且满足，以下就是拉格朗日基本多项式：拉格朗日型拉格朗日型n次插值多项式次插值多项式 0101 ( ),( )( )0,1,1nnnniiyf xx xxyyyP xP xyinnn已知函数在n+1个不同的点上的函数值分别为，求一个次数不超过n次的多项式，使其满足，即个不同的点可以唯一决定一个 次多项式。存在性 唯一性n给定平面上n+1个互不相同的插值点 n ，互不相同是指 互不相等，是否有且仅有一条不高于n次的插值多项式曲线，如果曲线存在，那么如何简单地作出这条n次插值多项式曲线？），（n210(),(,ixfxiiix

13、将 依次代入 中，得到线性方程组)(,(iixfxnnoxaxaxaa221n)(xPn方程组的系数行列式是范德蒙（Vandermonde）行列式：n当 互异时， ，所以线性方程组的解存在且惟一。即这样的插值多项式 存在而且惟一。（这同时也说明了不同形式的插值多项式本质上是同一个）ixnnoxaxaxaa221n)(xPn当 互异时， ，即行列试不为0，由克莱默法则得知，线性方程组的解存在且惟一。即f(x)关于 的n次插值多项式 存 存在而且惟一。n注：（这同时也说明了不同形式的插值多项式本质上是同一个，即 与 是同一个多项式，前者是插值型式，后者是Lagrange型式）niix0niix0n

14、noxaxaxaa221n)(xPnnoxaxaxaa221n)(xP)()()(0iininxfxlxp二，牛顿插值流程：均差牛顿插值公式例子求解拉格朗日插值与牛顿插值的比较均差010101010101010112011202012( )1,(),( ),(),()( )1.( ), ,2., ,( ),nnnf xnx xxf xf xf xyyyf xf xf xx xf x xxxf x xf x xf x xf x xxxf xx x x设函数在个相异的点上的函数值分别为，或者记为一阶均差：称为关于结点的一阶均差，记为。二阶均差：一阶均差，的均差称为关于结点的二阶均差，0120111

15、201001,3.1, ,( )1,nnnnnf x x xnnnf x xxf x xxf x xxxxf xnx xx记为。阶均差：递归地用阶均差来定义 阶均差，称为关于个结点的均差。均差的性质010100110101010101100112012020102011001.11,()()()()()(), ,11()nnknkkkkkkknnnyyyyf x xxxxxxxxxxf xf xyyf x xxxxxxxf x xf x xf x x xxxyyxxxxxxx性质 ： 阶均差可以表示成个函数值的线性组合，即例：1221221012010202101220210120102101

16、22021()11()()()()()()()()()()()yyxxxxxyyyxxxxxxxxxxxxxxyyyxxxxxxxxxxxx均差的性质0110012102021001012., , ,3.( ),1,2( )2,3,()kf x xf x xf x x xf x x xf x x xf xxnf x xxnf x x xxnf xkf x xxxnkknknk：均差与结点的顺序无关，即：若是 的 次多项式，则一阶均差是 的次多项式，二阶均差是 的次多项式；一般地，函数性的 阶均差是质（对称性）的次多项式，而时性，质阶均差为零。利用均差表计算均差 n利用均差的递推定义利用均差的递

17、推定义,可以用递推来计算均差。可以用递推来计算均差。n如下表：如下表：n如要计算四阶均差如要计算四阶均差,应再增加一个节点应再增加一个节点,表中还要增加表中还要增加一行。一行。例1n例1：已知ixix ( )if x( )if x计算三阶均差f1,3,4,7例1（解）解：列表计算ixix ( )if x( )if x牛顿插值公式0000000010110010110101201220101.( )() ,( )() ,(), (0) , , , ,() (1) , , ,f xf xf x xxxf xf xf x xxxf x xf x xf x x xxxf x xf x xf x x x

18、xxf x x xf x x xf x x x xxxf x x xf x x牛顿插值公式的构造因为，所以式因，有， 式因120122, ,() (2)xf x x x xxx， 式牛顿插值公式01010010100010012010 , , , ,() ()1),( )(),(),()(),2)nnnnnnnnf x xxf x xxf x xxxxf x xxf x xxf x xxxxnf xf xf x xxxnnf x x xxxxxf x一般地， 式将( 式)代入(式式 代入(1式)，(1式)代入(0式)，得：10110101,()()() ,()(),()11( )( )( )(

19、 )nnnnnnnnxxxxxxxxf x x xxxxxxxxR xnxnxnNxf xNxR xx最后一项中，均差部分含有 是余项部分，记作。前面项中，均差部分不含有 ，因而前面项是关于 的 次多项式，记作，这就是牛顿公式。于是上式成为：00100101011001000010010012010121( )(),() ,()()( )(),()()2( )(),(),()() ,(nf xf xf x xxxf x x xxxxxyyN xf xf x xxxyxxxxnf xf xf x xxxf x x xxxxxf x x x x例如：当时，其中，这就是牛顿一次插值多项式，也就是点斜

20、式直线方程。当时，0122001001201)()()( )(),(),()()xxxxxxNxf xf x xxxf x x xxxxx这就是牛顿二次插值多项式。20001210101010122020010112202102011222()()()()()()()()()()()()()()()()()1()()()( )Nxf xf xf xNxf xxxf xxxf xf xNxf xxxxxf xf xf xf xxxxxxxxxxxf xNx显然，即满足二次插值条件。例2例2：已知ixix ( )if x( )if x求满足以上插值条件的牛顿型插值多项式。例2（解）00101201

21、2331()0,1,4,1.25( )0(1)4 (1)(3)1.25 (1)(3)(4)f xf xxf xx xf xx x xNxxxxxxx 解：在例中，我们已经计算出，；则牛顿三次插值多项式为拉格朗日插值与牛顿插值的比较(1)01( )( )()()(), 0,1,( )( )( ) ,( )( )(1)!1nnnknkknnnnnnP xNxnP xNxf xknP xNxff x x xxxxnnn（1）和均是 次多项式，且均满足插值条件：由多项式的唯一性，因而，两个公式的余项是相等的，即：（2）当插值多项式从次增加到 次时，拉格朗日型插值必须重新计算所有的基本插值多项式；而对于牛顿插值，只需要表格再计算一个n阶均差，然后加上一项即可。三，埃尔米特插值n定义：基本思想n基函数的思想（langrange插值的思想）：n将待求的n次多项式插值函数pn(x)改写成另一种表示方式，再利用有关的插值条件确定其中的待定函数，从而求出插值多项式。四，分段多项式插值n定义：n a=x0 x1xn=