第2章-插值法.

数值分析第1页第二章插值法太原理工大学数学学院第2章插值法(Interpolation)一、问题的提出第一类问题函数y=f(x)表达式未知,通过观察、实验或测量得到上n+1个互异点xi的值yi=f(xi)(i=0,1,...,n).第二类问题函数y=f(x)表达式已知,但太复杂,计算得到其(容易计算)在n+1个互异点xi的值yi=f(xi)(i=0,1,...,n).2.1引言如三角函数表、对数表、平方根和立方根表等.数值分析第2页第二章插值法太原理工大学数学学院.......Oxyx0x1xn-1xn两类问题可归结为：已知一个表格函数xx0x1x2…xnyy0y1y2…yn1.问题:如何确定函数f(x)在任意点处的函数值?y=f(x)x---------------数值分析第3页第二章插值法太原理工大学数学学院.......Oxyx0x1xn-1xny=p(x)y=f(x)2.方法简单函数y=p(x)满足条件p(xi)=yi(i=0,1,...,n)插值和数据拟合用一个简单函数y=p(x)近似代替函数y=f(x),即f(x)p(x)3.插值法的思想插值条件数值分析第4页第二章插值法太原理工大学数学学院例如,用计算机程序控制加工机械零件。根据设计可给出零件外形曲线的某些型值点(xi,yi)(i=0,1,...,n),加工时为控制每步走刀方向及步数,就要算出零件外形曲线其它点的函数值,才能加工出外表光滑的零件,这就是求插值函数的问题.数值分析第5页第二章插值法太原理工大学数学学院定义已知函数y=f(x)在区间[a,b]上互异个点x0,x1,…,xn上的值y0,y1,…,yn,若存在一简单函数P(x)满足P(xi)=yi(i=0,1,...,n)(2.1)就称P(x)为f(x)的插值函数,点x0,x1,…,xn称为插值节点,(xi,yi)称为插值点,[a,b]称为插值区间,求插值函数P(x)的方法称为插值法,式(1.1)称为插值条件.多项式插值、分段插值、三角插值等.本章只讨论多项式插值与分段插值.数值分析第6页第二章插值法太原理工大学数学学院从几何上看，插值法就是求曲线y=P(x)，使其通过给定的n+1个点(xi,yi),i=0,1,…,n，并用它近似已知曲线y=f(x)，见下图.数值分析第7页第二章插值法太原理工大学数学学院已知函数y=f(x)在n+1个互异点xi的值yi=f(xi)(i=0,1,...,n),求一个多项式p(x),使其满足(1)p(x)是一个次数不超过n的多项式;(2)p(xi)=yi(i=0,1,...,n)定义则p(x)称为f(x)的n次插值多项式,用Pn(x)表示,即2.1.2多项式插值(polynomialinterpolation)Pn(x)=a0+a1x+a2x2+...+anxn(2.2)a=min{xi},b=max{xi}.数值分析第8页第二章插值法太原理工大学数学学院(1)插值多项式是否存在?若存在,是否唯一?所须讨论的问题：(2)如何求插值多项式?(3)插值多项式近似代替f(x)的误差?数值分析第9页第二章插值法太原理工大学数学学院定理1设节点xi(i=0,1,…,n)互异,则满足插值条件Pn(xi)=yi(i=0,1,...,n)证设所求的插值多项式为Pn(x)=a0+a1x+a2x2+...+anxn的次数不超过n的多项式存在且唯一.由Pn(xi)=yi(i=0,1,...,n),得插值多项式的存在性与唯一性数值分析第10页第二章插值法太原理工大学数学学院010000111101(2.3)nnnnnnnnnaaxaxyaaxaxyaaxaxy其系数行列式为Vandermonde行列式：200021110211()1nnjinjinnnnxxxxxxxxxxx0由克莱姆法则，方程组(1.3)有唯一解.证毕数值分析第11页第二章插值法太原理工大学数学学院先讨论n=1的情形.假定给定一个区间[x0,x1]及端点函数值y0=f(x0),y1=f(x1),要求线性插值多项式L1(x)，使它满足L1(x0)=y0,L1(x1)=y1.y=L1(x)的几何意义就是通过两点(x0,y0)与(x1,y1)的直线，如右图.()yfx1()yLxyx0x1x1y0y对给定的插值点(xi,yi),i=0,1,…,n，求插值多项式可以有不同方法。数值分析第12页第二章插值法太原理工大学数学学院()yfx1()yLxyx0x1x1y0y1010010()()yyLxyxxxx(点斜式方程)可写为011010110()xxxxLxyyxxxx(对称式方程)数值分析第13页第二章插值法太原理工大学数学学院约瑟夫·拉格朗日,全名约瑟夫·路易斯·拉格朗日(Joseph-LouisLagrange)法国数学家、物理学家。Lagrange法1736-18132.2拉格朗日插值1736年1月25日生于意大利都灵,1813年4月10日卒于巴黎.他在数学、力学和天文学三个学科领域中都有历史性的贡献,其中尤以数学方面的成就最为突出.数值分析第14页第二章插值法太原理工大学数学学院n=1时,由对称式方程01010110(),()xxxxlxlxxxxx011010110()xxxxLxyyxxxx线性组合得到的,其系数分别为y0及y1,即l0(x)及l1(x)是一次多项式,在节点x0及x1上分别满足10011()()().Lxylxylx00011111()1,()0;()0,()1.lxlxlxlx2.2.1线性插值与抛物线插值看出,L1(x)是由两个线性函数数值分析第15页第二章插值法太原理工大学数学学院称l0(x)及l1(x)为线性插值基函数，它们的图形为插值基函数的特点：x0x1l010l1010xy1Ox0()lxy11()lxOx1x0x1x1x0x1l0l1数值分析第16页第二章插值法太原理工大学数学学院y=L2(x)在几何上就是通过三点(x0,y0),(x1,y1),(x2,y2)的抛物线.n=2时,假定插值节点为x0,x1,x2，要求二次插值多项式L2(x)，使它满足L2(x0)=y0,L2(x1)=y1,L2(x2)=y2.1,,(),0,1,2.0,,ikiklxikik用基函数方法,此时基函数l0(x),l1(x),l2(x)是二次函数,且在节点上分别满足条件数值分析第17页第二章插值法太原理工大学数学学院满足条件的插值基函数很容易求出.例如求l0(x),因它有两个零点x1及x2,故可表示为012()()(),lxAxxxx其中A为待定系数，可由条件l0(x0)=1定出01021,()()Axxxx于是1200102()()(),()()xxxxlxxxxx同理可得0211012()()(),()()xxxxlxxxxx0122021()()().()()xxxxlxxxxx数值分析第18页第二章插值法太原理工大学数学学院n=2时的二次基函数图形为:利用二次插值基函数l0(x),l1(x),l2(x)，立即得到二次多项式2001122()()()().Lxylxylxylx显然满足L2(x0)=y0,L2(x1)=y1,L2(x2)=y2.数值分析第19页第二章插值法太原理工大学数学学院2001122()()()().Lxylxylxylx将上面求得的基函数l0(x),l1(x),l2(x)代入得1220010202110120122021()()()()()()()()()()()()()xxxxLxyxxxxxxxxyxxxxxxxxyxxxx数值分析第20页第二章插值法太原理工大学数学学院2.2.2拉格朗日插值多项式对n=1和n=2的情形,得到了一次与二次插值多项式L1(x)及L2(x),它们分别是基函数的线性组合,下面将用基函数表示插值多项式的方法推广到一般情形.Ln(xj)=yj,j=0,1,…,n.为了构造Ln(x)，我们先定义n次插值基函数.构造通过n+1个节点x0x1…xn的n次插值多项式Ln(x)，假设它满足条件数值分析第21页第二章插值法太原理工大学数学学院定义1若n次多项式lj(x)(j=0,1,…,n)在n+1个节点x0x1…xn上满足条件1,()(,0,1,,)0,jkkjlxjknkj就称这n+1个n次多项式l0(x),l1(x),…,ln(x)在为节点x0,x1,…,xn上的n次插值基函数.0101()()()nnxxxlxlxlx节函点数函数值100010001数值分析第22页第二章插值法太原理工大学数学学院用类似的推导方法，可得到n次插值基函数为00()()()()()(0,1,,)nkkknxxxxlxxxxxkn11()()kkxxxx11()()kkkkxxxx0101()()()nnxxxlxlxlx节函点数函数值100010001数值分析第23页第二章插值法太原理工大学数学学院构造次数不超过n的多项式称为拉格朗日插值多项式。则Ln(x)满足Ln(xj)=yj,i=0,1,…,n,)()()()(1100xlyxlyxlyxLnnn由唯一性得：Ln(x)≡Pn(x)数值分析第24页第二章插值法太原理工大学数学学院记1010()()()()(),nnnkkxxxxxxxxx则于是1001()()().()()nnnnkkkkkknkxLxylxyxxxNote:n次插值多项式是次数≤n的多项式,特殊情况下次数可能小于n.如过三点(x0,y0),(x1,y1),(x2,y2)的二次插值多项式L2(x),如果三点共线,则y=L2(x)就是一直线,而不是抛物线,这时L2(x)是一次多项式.10()()().nkkknxxxxx11()()kkkkxxxx数值分析第25页第二章插值法太原理工大学数学学院Remark:(1)对于插值节点,只要求它们互异,与大小次序无关;(2)插值基函数lk(x)仅由插值节点xk(k=0,1,…,n)确定,与被插函数f(x)无关;(3)插值基函数lk(x)的顺序与插值节点xk(k=0,1,…,n)的顺序一致.数值分析第26页第二章插值法太原理工大学数学学院所以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()数值分析第27页第二章插值法太原理工大学数学学院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)的抛物线插值(即三次插值多项式).解以以为节点的基函数分别为:数值分析第28页第二章插值法太原理工大学数学学院)()()()()(332211003xlyxlyxlyxlyxL)3)(1)(1(1513)4)(1)(1(81)6()4)(3)(1(1210)4)(3)(