数值分析-插值法

第四章插值法（interpolation）4.1问题提出niyxii,,2,1,0),,(对原函数，其本身表达式过于复杂，我们只知道有限个点的函数值,需要寻找一个简单的函数近似地表示原函数，且满足这些给定的数值点。4.1.1插值概念定义：设函数f(x)在区间[a,b]上有意义,且已知nxxx,,,10bxxxan10的值为,若存在一个简单nyyy,,,10)(xPnjjnyxP)(nj,,1,0(1)成立，则称为f(x)的插值函数。其中为插值节点，[a,b]为插值区间，f(x)为被插值函数，式(1)为插值条件.)(xPn函数,使得几何意义：用线性、抛物线等简单函数近似表示原函数。插值函数类的选取:代数多项式(多次式插值)，三角多项式，有理多项式等最简单的插值多项式:nnxaxaaxP10)(,)(iiyxPni,,1,0使得:有n+1个未知数，n+1个方程求解。4.1.2插值多项式的存在唯一性20102000201121112012nnnnnnnnnnaaxaxaxyaaxaxaxyaaxaxaxy求未知数：01,,naaa其系数行列式为200021111002111nnniijijnnnnxxxxxxVxxxxx范德蒙行列式(Vandermonde)200211102021222111xxVxxxxxxxxxx例如n=2时，0ijxxV有唯一解。利用特殊情况：00,,xy00ayn=0时，即过一点可知00Pxay0y插值函数为过的直线.n=1时,00010011100100011110111yxaaxyyxxyxyaxaaxyxxx10011001101010011010101000001010101010xyxyyyPxaaxxxxxxxyxyyyyyyyyyxxxyxxxxxxxxxxxx0011,,,xyxy即为过两点的直线。10110yyaxx4.2拉格朗日插值（Lagrange）使用线性方程组求系数构造插值公式相对复杂，可改用构造方法来插值。(0,1,,)ixin(0)kxkn对节点中任一点,作一n次多项式()klx，使它在该点上取值为1，(0,1,,1,1,,)ixikkn上为0，即1()0kiiklxik则插值多项式为:0()()nniiiLxylx而在其余点构造过程：0111,,,,kknxxxxx()klx上式表明：n个点都是0111()()()()()()kkkknlxAxxxxxxxxxxkA其中为待定系数。∵1)(ikxl(i=k时)∴)())(())((11110nkkkkkkkkxxxxxxxxxxA)())(()()())(()(110110nkkkkkknkkkxxxxxxxxxxxxxxxxl∴n次拉格朗日插值多项式为：niniiiiiiniiiniiinxxxxxxxxxxxxxxxxyxlyL01101100)())(()()())(()()(的零点。()klx常用的拉格朗日插值多项式：n=1时，称为线性插值，1001101010100011010()()()()Lxylxylxxxyxxxyyyxxxxxxxxn=2时，称为二次插值或抛物线插值，))(())(())(())(())(())(()(1202102210120120102102xxxxxxxxyxxxxxxxxyxxxxxxxxyxL10010,12111,14412,115例题：已知用线性插值的近似值。和抛物线插值计算解：首先是线性插值：节点为:001122100,10;121,11;144,12xyxyxy∴10011115(115)115121115100101110.714100121121100Lylyl抛物线插值：2001122115(115)(115121)(115144)(115100)(115144)1011(100121)(100144)(121100)(121144)(115100)(115121)12(144100)(144121)10.723Lylylyl精确值为7238.10115,抛物线精度相对高些.4.3插值余项)(xPnix区间[a,b]上使用插值多项式近似f(x),节点上没有误差，其它点上一般存在误差，记)()()(xPxfxRnn)(xRn)(xPn)(xf)(xPn称为近似代替的截断误差，也称为的插值余项.可由下面定理来估计)(xRnnxx,,0)(xPn)()(iinxfxPbax,定理：设f(x)在区间[a,b]上有直到n+1阶导数，为互不相同的节点，为满足的n次插值)()!1()()(1)1(xWnfxRnnn其中10()(),(,)nniiWxxxab，且与x有关。除了在多项式，则对任何有:证明：考虑插值节点上有),,1,0(0)(nixRin∴这些节点是的零点,)(xRn可设)()()(1xWxkxRnn①)(xk)(xk其中为待定函数（与x有关），需确定.)(xk对分析知：),,1,0(njxxj)(xk当时，①式左边=右边=0，此时可为任意函数。jxx)(xk1()()nnRxWx当为其他某点时，取∴为了计算，引入辅导函数)(xk也可使①式成立.)()()()(1tWxktRtnn②(变量用t表示,x表示某点))(txxxn,,,0可知=0至少有n+2个零点：.)('t)(t由罗尔定理知:在的两个相邻零点间至少有一个零点。∴)('t至少有n+1个零点，以此类推，)()1(tn(1)()0n至少有一个零点，即)()()()()1(1)1()1(tWxktRtnnnnn对②关于t求n+1阶导数：(1)()0nnLtnL(为n次多项式）(1)(1)(1)(1)()()()()nnnnnnRtftLtft又因为(n+1)n+1(t)=(n+1)!w所以(n+1)1(ξ)(ξ)()(1)!0nkxnφf其中()()nPxfx()0nxR注意：，即使得11()maxnnaxbxfM2.该定理中，当f(x)具有（n+1）阶导数才可使用且在求误差时，利用求得，即11()((1)nnnxxnMRw例：前面例子中，求线性插值和抛物线插值在处的误差限。1151.若f(x)本身为不超过n次多项式，则一定可构造出1(ξ)()(1)!nkxnf11(ξ)()()(1)!nnnxxnfwR即解：12()fxxx1–21f'()2,xx3–21f''()-4,xx5–23f'''()8xx121()΄˝(ξ)(2xfxRw3–2011–()()(ξ)8xxxx01ξ,xx0100,x1121,x115x11(115)(115100)(115121)8R3max2[100,121]·{}ξ3211560.011251008线性插值：抛物线插值：321()'''(ξ)(3xfxwR520121()()()(ξ)16xxxxxx01ξ,xx0100,x1121,x2144,x115x5221(115)(115100)(115121)(115144)0.001710016R4.4带导数插值条件的插值利用拉格朗日插值和待定系数法求导数插值条件的插值，一阶导数在几何图形中具有几何意义，（例如切线斜率,参数曲线切矢量，包括切线方向和模长）如何构造，通过下例说明：()(0,1,2)jjfjyx1x11΄΄()fxm3()xP3(),jjyxP(0,1,2)j113΄()xmP例：已知节点上函数值和处的导数值,构造一个次数不超过3的多项式,要求满足：且解：对012,,xxx三节点，可先构造二次拉格朗日插值2012012()()()()xxxxyyylllL令32()()()xQxxPL()Qx其中为不超过3次的多项式32()()()QxxxPL012,,xxx3()xP2()xL因为是和的零点,()()0()jjjjjjjyyQxxPLx(0,1,2)j012,,xxx()xQ即也是的3个零点,可设012()()()(),QAxxxxxxxA为待定系数13211'()'()'()QxxxPL1m（1）通过计算知，121021021012010210122021()()()2'()()()()()()()xxxxxxxyyyxLxxxxxxxxxxxx且102102'()()'()()()[()()]'QAxAxxxxxxxxxxxx11012'()()()QAxxxxx3()xP利用(1)式可求出A,从而得到所以3012()()()(),xAxxxxxxP113'()xmP3()xP3()xP注意:(1)也可直接设A为待定系数，利用导数条件，求出A，一般情况下也有可能为二次多项式，原来方法更加准确。（2）求余项:R(x)=f(x)－P3(x)易知:x0,x2是R(x)的一重零点，x1为R(x)的二重零点,∴R(x)可写为R(x)=K(x)(x－x0)(x－x1)2(x－x2)①其中K(x)待定函数可知：当x=x0,x1,x2时，K(x)可取任意数，式①都成立（此时左=右=0）但求出的通常为3次多项式或为0，当x≠x0,x1,x2为其他点时，∴引入辅助函数()()tRtK(x)(t－x0)(t－x1)2(t－x2)可知()t在插值区间内有5个零点：x0,x1(二重),x2,x反复应用罗尔定理知：4()t在区间内至少有一个零点，444()()()4!()4!()0RKxfKx(4)3()0,Px(4)(4)()()Rf(∵)∴41()()4!Kxf∴插值余项为R(x)=420121()()()()4!fxxxxxx在插值区间内与x有关.所以若K(x)为R(x)/(x－x0)(x－x1)2(x－x2)式①也成立。记为ξ,4.5埃尔米特插值（Hermite）有时插值函数不仅要求在节点上与原函数相同，还要求其导数的值与原函数的值相同，即要求H2n＋1(xi)=f(xi)，H’2n＋1(xi)=f’(xi)i=0、1、…、nH2n＋1(x)为次数不超过2n＋1的插值多项式该问题即为埃尔米特插值.这里只讨论如何构造三次Hermite插值.4.5.1Hermite插值问题：在[x0,x1]上寻找一个次数不多于3的多项式H(x)，满足H(x0)=f(x0);H’(x0)=f’(x0);H(x1)=f(x1);H’(x1)=f’(x1)(1)''00110011()()()()()()()()()Hxfxxfxxfxxfxx根据条件①可知(每个条件得到一行方程)：00100010()1,()0,()0,()0,xxxx具体构造：''''00100010()0,()0,()1,()0,xxxx01110111()0,()1,()0,()0,xxxx''''01110111()0,()0,()0,()1,xxxx可设由第