5.1插值法

拉格朗日(Lagrange)插值牛顿(Newton)插值分段线性插值第5章插值法样条插值埃尔米特(Hermite)插值快速傅里叶变换(FFT)应用实例1生产实践中常常出现这样的问题：给出一批离散样点,要求作出一条通过这些点的光滑曲线,以便满足设计要求或进行加工.反映在数学上,既已知函数在一些点上的值,寻求它的分析表达式.因为由函数的表格形式不能直接得出表中未列点处的函数值，也不便于研究函数的的性质.此外,有些函数虽然有表达式,但因式子复杂，不易计算其值和进行理论分析，也需要构造一个简单函数来近似它.解决这种问题的方法有两种：插值法2一类是给出函数fx的一些样点值,选定一个便于计算的函数形式，如多项式，分式线性函数和三角多项式等，要求它通过已知样点，由此确定函数x作为fx的近似.这就是插值法。另一类方法在选定近似函数形式后,不要求近似函数过已知样点,只要求在某种意义下它在这些点上的总偏差最小.拟合法.本章主要讨论构造插值多项式的几种常用方法及其误差.这类方法称为曲线(数据)插值法3设函数在区间yfx,ab上有定义,它在该区间上n+1个互异点nxxx,,,10处的函数值为已知,记为(),0,1,,iiyfxin若存在一个简单函数Px使得,0,1,,iiPxyin成立,就称Px为fx的插值函数,点nxxx,,,10称为插值节点,区间,ab称为插值区间,求插值函数Px的方法称为插值法.4若PxPxPx是次数不超过n的代数多项式,就称为插值多项式,相应的插值法称为多项式插值;若Px为分段多项式,就是分段插值;若为三角多项式,就称为三角插值.5§5.1拉格朗日(Lagrange)插值5.1.1多项式插值用插值法求函数的近似表达式时,首选要选定近似函可供选择的函数很多,常用的是多项式函数.因为多项式函数计算简便,只需用加,减,乘等运算,而且其导数与积分仍为多项式.用多项式作为研究插值的工具,称为代数插值.插值法数的形式.6求一个至多n次的多项式nnnxaxaax10)((5—1)使其在给定点处与fx同值，即满足插值条件iiinyxfx)()((0,1,,)in(5—2))(xn称为插值多项式,(0,1,,)inix称为插值节点,简称节点，,ab称为插值区间.插值法7p9其基本问题是:已知函数fx在区间,ab上1n个不同点nxxx,,,10处的函数值)(iixfy(0,1,,)inO插值法xy2x1x0xnx0y1y2y)(xfy)(xyn图5-1从几何上看（如图5-1所示），n次多项式插值就是过n+1个点))(,(iixfx(0,1,,)in作一条多项式曲线)(xyn近似曲线yfx8n次多项式(5-1)有n+1个待定系数，由插值条件式(5-3)记此方程组之系数矩阵为A，则20102000nnaaxaxaxy20112111nnaaxaxaxy2012nnnnnnaaxaxaxy插值法(5-2)恰好给出n+1个方程9p7200021112111nnnnnnxxxxxxxxx是范德蒙特（Vandermonde）行列式.当01,,,nxxx互不相同时，此行列式不为零.因此,方程组（5-3）有唯一解.只要n+1个节点互不相同，满足插值要求式的插值多项式（5-1）detA插值法10iiinyxfx)()((0,1,,)in(5-2)nnnxaxaax10)((5-1)这表明，（5-2）是存在唯一的.5.1.2插值多项式的误差估计插值多项式与被插函数之间的差)()()(xxfxRnn称为截断误差，又称为插值余项.假定fx在区间,ab上n+1次连续可导，对,ab上任意点x,且ixx(0,1,,),in构造辅助函数11()()()()()nnnnRxftttx(5—4)其中10()().nnjjttx显然()t插值法11p14()x又由插值条件式（5-2),0)(inxR(0,1,,)in故函数)(t在区间ba,内至少有n+2个零点01,,,,.nxxxx由罗尔（Rolle）定理，函数()t在(a,b)内至少有n+1个零点.(1)()nt11()()()()0,()nnnnRxfxxxx11()()()()()nnnnRxftttx(1)(1)(1)11()()()()()nnnnnnnRxftttx插值法()0ix12反复使用Rolle定理,可以得出在(a,b)内至少有一个零点,设为,即(1)()0n因为)(tn为至多n次多项式,)(1tn为最高次项系数为1的n+1次多项式,因而(1)()0,nnt(1)1()(1)!nntn于是有)()1(n0)!1()()()(1)1(nxxRfnnn插值法1310()().nnjjttx(1)()nt(1)(1)(1)11()()()()()nnnnnnnRxftttx所以)(xRn()()()()!nnfxn111()()()()()!nnfxxxxxxn1011当(0,1,,)ixxin时,上式自然成立,因此,上式对ba,上的任意点对成立.这就是插值多项式的误差估计.定理5.1设01,,,nxxx是区间ba,上的互异节点,nx是过这组节点的n次插值多项式.如果fx在ba,上n+1次连续可导,则对ba,内任意点x,插值余项为()nRx(1)1()(),(1)!nnfxn),(ba(5-5)插值法14通过解方程组(5-3)来确定插值多项式,计算量较大.下面介绍几种常用的确定插值多项式的方法.5.1.3Lagrange插值多项式先讨论只有两个节点)1(,10nxx由前所述,插值多项式设为101(),xaax且满足插值条件)(01x010aax)(11x011aax插值法的插值多项式.1500()yfx11()yfx解此方程组得,1010010xxxyxya10101xxyya所以,两个节点的一次插值多项式为1()x1001010101yxyxyyxxxxx(56)如图５-２所示，这是用过两点),(),,(1100yxyx的直线)(1xy近似曲线,yfx故这种插值又称为线性插值．插值法16如果将式(5-6)改写成以下形式)(1x01011010xxxxyxxxxy式（5-7）中，)(1x被表示成两个线性函数的线性组合．记,)(1010xxxxxl0101)(xxxxxl插值法Oxy1x0x)(xfy)(1xy),(00yx),(11yx图5-2(5-7)17显然，它们满足,1)(00xl0)(10xl,0)(01xl1)(11xl于是(5-7)可写为不难想像,以对应点处的函数值为系数对它们作插值条件.由此得到启发,当节点增多到n+1个时,可以先构造n次多项式()(0,1,,)ilxin它们满足插值法0()1kiiklxik即10011()()()xylxylx18,)(1010xxxxxl0101)(xxxxxl线性组合所得的函数,不仅仍是线性的,且必定满足)(jixl01jiji(5-8)然后作线性组合,)(xli有n个根(0,1,,,)jxjnji又1)(iixl011()()()()iiinAxxxxxxxx)(xli插值法0011()()()()nnnxylxylxylx显然有()()njjjjxylx即()nx为所求插值多项式.由于所以代入上式得19,jy0,1,,jn0111()()()()iiiiiiinAxxxxxxxx011011()()()()()()()()()iiniiiiiiinxxxxxxxxlxxxxxxxxx0njjijjixxxx故称(),0,1,,ilxin为Lagrange插值基函数,(5-9)插值多项式为20)(xn0()niiiylx(5-10a)00()nnjiijijjixxyxx式(5-10a)称为n次Lagrange插值多项式.为了以后便于区别,常用)(xLn代替)(xnLagrange插值所得到的插值多项式,即niiinxlyxL0)()((5-10b)由前面讨论的结果,n+1个节点的n次Lagrange插值多项式插值法()nx0()niiiylx(5-10a)存在唯一,式(5-5)为插值余项.式(5-10b)形式对称,以突出表示这是由2100()nnjiijijjixxyxx容易编制程序.算法5.1用于计算非节点处的函数近似值.算法5.1(1)输入).,,1,0(,,niyxxii(2)对ni,,1,0nijjjijixxxxl0.(3)niiilyL0.(4)输出),(xfL停机.因为()(),nnjjxxx10求导可得10()(),nniijjjixxx插值法22于是式(5-10)可改写成101()()()nniiinixyxxxxLn(5-11)特别的,当n=1时,两点一次Lagrange插值多项式为01010110xxxxyyxxxx10011()()()Lxylxylx当n=2时,即给定三个节点210,,xxx处的函数值012,,,yyy三个插值基函数为插值法23()nLxninijjjijiniiixxxxyxly000)()((5-10a)xl0120102,xxxxxxxxxl1xl2210120xxxxxxxx120210xxxxxxxx二次Lagrange插值多项式为)()()(221100xlyxlyxly)(2xL插值法1200102xxxxyxxxx0211012xxxxyxxxx0122021xxxxyxxxx24如图5—3所示,这是一条过点)2,1,0)(,(iyxii的抛物线.这说明用二次插值多项式近似函数,其几何意义是用过曲线上三点的抛物线近似曲线,故三点二次插值又称为抛物线插值.插值法Oxy2x1x0x0y1y2y)(xfy)(2xLy图5-325分别用Lagrange线性插值和抛物线插值求ln11.5的近似值,并估计截断误差.[解]线性插值.取两个节点,12,1110xx插值基函数为1001()xxlxxx0110()xxlxxx插值法xlnyx10111312142.30262.48492.56492.63912.397926例1已知函数xyln的函数表如下:(12),x11xp28p29由式(5-7):)(1xL)11(4849.2)12(3979.2xx将x=11.5代入,即得1ln11.511.5L4414.25.04849.25.03979.2按式(5-5)(ln)11122!xxx)(1xR插值法101()()2!fRxxxxx于是有2710011()()()Lxylxylx因为21(ln),xx在11与12之间,故21(ln)x于是...10008264505052)5.11(1R抛