第1节课-第一章-插值法--拉格朗日插值-分段插课件

第一章 插值方法李书杰合肥工业大学 计算机学院 第一章 插值方法李书杰提纲插值的基本概念拉格朗日插值逐步插值插值余项分段插值提纲插值的基本概念插值的基本概念插值的基本概念例例.某地区某年夏季时节间隔某地区某年夏季时节间隔 30 天的日出日落时天的日出日落时间为间为 5月月1日日 5月月31日日 6月月30日日日出日出 5：51 5：17 5：10日落日落 19：04 19：38 19：50任意一天的日照时间？任意一天的日照时间？插值的基本概念例.某地区某年夏季时节间隔 30 天的日出日日照时间的变化设为日照时间的变化设为 y(x)=a0+a1x+a2x2,求出求出a0，a1，a2，即可得到，即可得到5、6月份的日照时月份的日照时间的变化规律。间的变化规律。根据三组数据根据三组数据:(1,13.21)，(31,14.35)，(61,14.66)导出关于导出关于a0，a1，a2的线性方程组的线性方程组日照时间的变化设为 y(x)=a0+a1x+a2x2,什么是插值什么是插值?插值法是函数逼近的一种简单但又十分重要的方法，实际中，f(x)是复杂多样的，通常只能观测到一些离散数据；或者f(x)过于复杂而难以运算。这时我们要用近似函数(x)来逼近f(x)。自然地，希望(x)通过所有的离散点x3x4x(x)f(x)x0 x1x2什么是插值?插值法是函数逼近的一种简单但又十分重要定义定义1:函数函数y=f(x)给出一组函数值给出一组函数值 x:x0 x1 x2 xny:y0 y1 y2 yn其中其中x0,x1,x2,xn是区间是区间a,b上的互异点上的互异点,要在函数类要在函数类中中求一个简单的函数求一个简单的函数(x)作为作为f(x)的近似表达式。的近似表达式。使满足使满足(插值原则、插值条件插值原则、插值条件)这类问题称为这类问题称为插值问题插值问题。-f(x)的的插值函数插值函数;f(x)-被插值函数被插值函数;x0,x1,x2,xn-插值节点插值节点;求插值函数的方法称为求插值函数的方法称为插值法插值法。若若xa,b,需要计算需要计算f(x)的近似值的近似值(x),则称则称x为为插值点插值点。函数类函数类-插值函数类插值函数类;一、定义：一、定义：定义1:函数y=f(x)给出一组函数值 x:x0 x当选择代数多项式作为插值函数类时，称为代数多项当选择代数多项式作为插值函数类时，称为代数多项式插值问题式插值问题:代数多项式插值问题代数多项式插值问题:设函数设函数y=f(x)在在a,ba,b有定义有定义,且已知在且已知在n+1n+1个点个点ax0 x1xnb上的函数值上的函数值y0,y1,yn.,要求一要求一个次数不高于个次数不高于n n的多项式的多项式 使满足插值原则使满足插值原则 称称Pn(x)为为f(x)的的n次插值多项式次插值多项式。这样的插值多项式是否存在、唯一？这样的插值多项式是否存在、唯一？当选择代数多项式作为插值函数类时，称为代数多项式插值问题:设设 Pn(x)=a0+a1x+a2x2+anxn是是y=f(x)在在a,b上的上的n+1个互异节点个互异节点x0,x1,xn的插值多的插值多项式，则求项式，则求Pn(x)问题归结为求系数问题归结为求系数a0,a1,an。定理定理 n次插值问题的解是存在而且唯一的。次插值问题的解是存在而且唯一的。证明：证明：由插值条件：由插值条件：由插值条件：由插值条件：P Pn n (x xk k)=)=y yk k (k k=0,1,=0,1,n n)得关于得关于得关于得关于a a0 0,a a1 1,a an n的的的的n n+1+1阶线性方程组阶线性方程组阶线性方程组阶线性方程组设 Pn(x)=a0+a1x+a2x2 故故Pn(x)存在且唯一。存在且唯一。因因故上式不为故上式不为0。据据Cramer法则，方程组解存在且唯一。法则，方程组解存在且唯一。是是Vandermonde行列式行列式.其系数行列式其系数行列式故Pn(x)存在且唯一。因故上式不为0。据Cramer法则提纲插值的基本概念拉格朗日插值逐步插值插值余项分段插值提纲插值的基本概念拉格朗日插值线性插值抛物插值一般情形拉格朗日插值线性插值给定插值节点给定插值节点 x0,x1，y0=f(x0)，y1=f(x1).求线性插值多项式求线性插值多项式L1(x)=a0+a1x，使满足，使满足:L1(x0)=y0,L1(x1)=y1.线性插值线性插值y=L1(x)的几何意义就是过点的几何意义就是过点(x0,y0)，(x1,y1)的的直线。直线。给定插值节点 x0,x1，y0=f(x0)，y1=f(xL1(x)的表达式：的表达式：点斜式点斜式:变换可得变换可得:可以看到，可以看到，L1(x)是由两个线性函数是由两个线性函数的线性组合得到，其系数分别为的线性组合得到，其系数分别为y0，y1。即。即L1(x)的表达式：点斜式:变换可得:可以看到，L1(l0(x)及及l1(x)在节点在节点x0,x1上满足条件：上满足条件：l0(x0)=1,l0(x1)=0.l1(x0)=0,l1(x1)=1.称称l0(x)及及l1(x)为线性插值为线性插值基函数基函数。(j,k=0,1)即即l0(x)及l1(x)在节点x0,x1上满足条件：称l n=1时的时的一次基函数一次基函数为为:y1 O x y 1O x n=1时的一次基函数为:y O 抛物插值抛物插值假定插值节点为假定插值节点为x0,x1,x2，求二次插值多项，求二次插值多项式式 L2(x)，使，使 L2(xj)=yj (j=0,1,2)y=L2(x)的的几何意义几何意义就是过就是过(x0,y0)，(x1,y1)，(x2,y2)三点的抛物线。三点的抛物线。采用采用基函数方法基函数方法，设，设L2(x)=l0(x)y0+l1(x)y1+l2(x)y2此时基函数此时基函数l0(x),l1(x),l2(x)是二次函数是二次函数.抛物插值假定插值节点为x0,x1,x2，求二次插值多项l0(x0)=1,l0(x1)=0,l0(x2)=0.l1(x0)=0,l1(x1)=1,l1(x2)=0.l2(x0)=0,l2(x1)=0,l2(x2)=1.基函数基函数l0(x),l1(x),l2(x)在节点上满足：在节点上满足：满足上式的插值基函数很容易求出。满足上式的插值基函数很容易求出。即即(j,k=0,1,2)l0(x0)=1,l0(x1)=0,l0(x2)=0故故其中其中C为待定系数，由为待定系数，由l0(x0)=1,得得如求如求l0(x):因因x1,x2 为其零点，故可表为为其零点，故可表为同理同理故其中C为待定系数，由l0(x0)=1,得如求l0(x)显然显然 L2(x)=l0(x)y0+l1(x)y1+l2(x)y2 满足条件满足条件L2(xj)=yj (j=0,1,2)将将l0(x),l1(x),l2(x)代入得代入得显然L2(x)=l0(x)y0+l1(x)y1+l2(x)n=2时的时的二次基函数二次基函数为为 :n=2时的二次基函数为 :设有设有n+1个互异节点个互异节点x0 x1xn，且，且yi=f(xi)(i=0,1,2,n)构造构造Ln(x)，使，使 Ln(xj)=yj (j=0,1,2,n)一般情形一般情形定义定义 若若n次多项式次多项式lj(x)(j=0,1,n)在在n+1个节个节点点x0 x1xn上满足条件上满足条件(j,k=0,1,n)则称这则称这n+1个个n次多项式次多项式l0(x),l1(x),ln(x)为为节点节点x0,x1,xn上的上的n次次插值基函数插值基函数。设有n+1个互异节点x0 x1xn，且一般情形定义若 由条件由条件lk(xj)=0(j k)知知x0,x1,xk-1,xk+1 ,xn都是都是 n次多项式次多项式lk(x)的的零点零点，故可设，故可设 lk(x)=Ak(x-x0)(x-x1)(x-xk-1)(x-xk+1)(x-xn)其中其中Ak为待定系数。为待定系数。再由再由lk(xk)=1有有 1=Ak(xk-x0)(xk-x1)(xk-xk-1)(xk-xk+1)(xk-xn)由由x0,x1,xk-1,xk+1 ,xn互异，解出互异，解出Ak 由条件lk(xj)=0(j k)知x0,x1,从而得从而得(k=0,1,2,n)或记为或记为(k=0,1,2,n)次数不高于次数不高于n的多项式的多项式在在x0,x1,xn上的值分别为上的值分别为y0,y1,yn 从而得(k=0,1,2,n)或记为(k=0,1,n次次插值基函数插值基函数(k=0,1,2,n)Lagrange插值多项式插值多项式n=1时时,线性插值线性插值n=2时时,二次插值二次插值或或抛物插值抛物插值n次插值基函数(k=0,1,2,n)Lagrang取取x0=4,y0=2，x1=9,y1=3，x2=16,y2=4.例例1已知已知求求解解（1）线性插值：线性插值：取取x0=4,x1=9取x0=4,y0=2，x1=9,y1=3，x2=16取取x0=4,x1=9,x2=16（2）抛物插值：抛物插值：取x0=4,x1=9,x2=16（2）抛物插值：例例2 求过点求过点(-1,-2),(1,0),(3,-6),(4,3)的三次插值多项式的三次插值多项式解解 以以以为节点的基函数以为节点的基函数分别为分别为:例2 求过点(-1,-2),(1,0),(3,-6),则拉格朗日则拉格朗日的三次插值多项式为的三次插值多项式为则拉格朗日的三次插值多项式为使其满足使其满足利用拉格朗日基函数利用拉格朗日基函数l i(x),构造次数构造次数不超过不超过n的多项式的多项式称为称为拉格朗日插值多项式拉格朗日插值多项式。由插值多项式的唯一性由插值多项式的唯一性,得得 特别地特别地,当当 n=1时又叫时又叫线性插值线性插值,其几何意义为其几何意义为过两点的直线过两点的直线.当当 n=2时又叫时又叫抛物（线）插值抛物（线）插值,其几其几何意义为过三点的抛物线何意义为过三点的抛物线.使其满足利用拉格朗日基函数l i(x),构造次数不超过n的注意注意:(1)对于插值节点对于插值节点,只要求它们互异只要求它们互异,与大小次序无关与大小次序无关;(2)插值基函数插值基函数l i(x)仅由插值节点仅由插值节点xi(i=0,1,n)确定确定,与被插函数与被插函数 f(x)无关无关;(3)插值基函数插值基函数l i(x)的顺序与的顺序与插值节点插值节点xi(i=0,1,n)的顺序一致的顺序一致.注意:(2)插值基函数l i(x)仅由插值节点xi(提纲插值的基本概念拉格朗日插值逐步插值插值余项分段插值提纲插值的基本概念逐步插值逐步插值拉格朗日插值公式拉格朗日插值公式 计算函数的近似值计算函数的近似值 若对原先选定的若对原先选定的n+1个节点所得结果精度不够，个节点所得结果精度不够，需要需要增加节点增加节点 怎么办怎么办？给定区间给定区间a,b上上一组插值节点一组插值节点x0,x1,xn,及及对应的函数值对应的函数值y0,y1,yn,把把k+1个节点个节点 ，所确定的不高于所确定的不高于k 次插值多项式记作次插值多项式记作 ，则，则 1）(r=0,1,k)2）逐步插值拉格朗日插值公式 计算函数的近似值 Neville算法算法算法步骤如下表算法步骤如下表例如例如 K=0 1 2 3 x0 y0=p0(x)x1y0=p1(x)p01(x)x2y0=p2(x)p12(x)p012(x)x3y0=p3(x)p23(x)p123(x)p0123(x)Neville算法算法步骤如下表 K=0 1 Aitken算法算法算法步骤如下表算法步骤如下表计算公式计算公式 x0 y0=p0(x)X1y0=p1(x)p01(x)X2y0=p2(x)p02(x)p012(x)x3y0=p3(x)p03(x)p013(x)p0123(x)x4y0=p4(x)p04(x)p014(x)p0124(x)p01234(x)Aitken算法算法步骤如下表x0 y0=p0(x)X1y0提纲插值的基本概念拉格朗日插值逐步插值插值余项分段插值提纲插值的基本概念定理定理 设设 f(x)在在a,b上具有上具有n阶连续导数阶连续导数,且且 f(n+1)(x)存在存在,节点节点a x0 x1xnb，Ln(x)是满足条件是满足条件Ln(xj)=yj (j=0,1,2,n)的插值的插值多项式，则对任何多项式，则对任何x a,b，插值余项，插值余项插值余项插值余项定义定义 若在若在若在若在 a a,b b 上用上用上用上用L Ln n(x x)近似近似近似近似f f(x x)，则其截断误差，则其截断误差，则其截断误差，则其截断误差R Rn n(x x)f f(x x)-)-L Ln n(x x)称称称称插值多项式的余项插值多项式的余项插值多项式的余项插值多项式的余项。其中其中定理 设 f(x)在a,b上具有n阶连续导数,且证明：证明：因为因为设设其中其中证明：因为设其中第1节课-第一章-插值法-拉格朗日插值-分段插课件根据Rolle定理,再由Rolle定理,依此类推，由于因此根据Rolle定理,再由Rolle定理,依此类推，由于因此所以注：余项表达式只有在注：余项表达式只有在注：余项表达式只有在注：余项表达式只有在f f(x x)的高阶导数存在时才能使用，的高阶导数存在时才能使用，的高阶导数存在时才能使用，的高阶导数存在时才能使用，通常不能具体通常不能具体通常不能具体通常不能具体给给出，可求出出，可求出出，可求出出，可求出故故故故L Ln n(x x)逼近逼近逼近逼近f f(x x)的截断误差限是的截断误差限是的截断误差限是的截断误差限是所以注：余项表达式只有在f(x)的高阶导数存在时才能使用，当当 f(x)是是n次的多项式时次的多项式时,Ln(x)=f(x)。即。即n次次多项式的多项式的n次插值函数即为该次插值函数即为该n次多项式本身。次多项式本身。说明：说明：n=1时，时，n=2时，时，当 f(x)是n次的多项式时,Ln(x)=f(x)。即例例:解解:例:解:第1节课-第一章-插值法-拉格朗日插值-分段插课件的抛物插值多项式的抛物插值多项式,且计算且计算f(3)的近似值并估计误差。的近似值并估计误差。例例2 设设解解 插值多项式为插值多项式为的抛物插值多项式,且计算f(3)的近似值并估计误差。例2 因为因为故故于是于是因为故于是用二次插值计算用二次插值计算ln11.25ln11.25的近似值的近似值,并估计误差并估计误差.例例3 给定函数表给定函数表x10111213lnx 2.302585 2.3978952.484907 2.564949解解 取节点取节点x x0 0=10,x=10,x1 1=11,x=11,x2 2=12,=12,作二次插值有作二次插值有ln11.25ln11.25 L L2 2(11.25)(11.25)用二次插值计算ln11.25的近似值,并估计误差.例3 在区间在区间10,1210,12上上lnx lnx 的三阶导数的上限的三阶导数的上限M M3 3=0.002,=0.002,可得误差估计式可得误差估计式实际上实际上,ln11.25=2.420368,ln11.25=2.420368,|R|R2 2(11.25)|=0.000058.(11.25)|=0.000058.在区间10,12上lnx 的三阶导数的上限M3=0.00事后误差估计一般直接应用余项公式来估计误差是困难的，常采用一种事后估计法。设x0 xx1x2,且f(xi)(i=0,1,2)已知，若将用x0,x1两点作线性插值所求得y的近似值记为y1，将用x0,x2两点作线性插值所求得y的近似值记为y2，则由余项公式知：事后误差估计一般直接应用余项公式来估计误差是困难的，常采用一得：假设 这表明可以通过两个结果的偏差y2-y1来估计插值误差y-y1。这种直接利用计算结果来估计误差的方法，称为事后估事后估计法。计法。得：假设 这表明可以通过两个结果的偏差y2-y1来事后估计法算例分析事后估计法算例分析为节点为节点,求得近似值为求得近似值为:用用 为节点为节点,求得近似值为求得近似值为:按照估计式有按照估计式有用用用用用用例：求例：求的近似值。的近似值。事后估计法算例分析为节点,求得近似值为:用 提纲插值的基本概念拉格朗日插值逐步插值插值余项分段插值提纲插值的基本概念分段插值分段插值高次插值的病态性质：高次插值的病态性质：对于一个确定的区间，如果插值节点之间的距对于一个确定的区间，如果插值节点之间的距离较小，自然插值节点就增多，如果用一个多离较小，自然插值节点就增多，如果用一个多项式插值，自然次数就会升高，也就是说要用项式插值，自然次数就会升高，也就是说要用高次多项式插值。高次多项式插值。但是否次数越高，插值多项式的逼近效果越但是否次数越高，插值多项式的逼近效果越好呢？好呢？20世纪初，世纪初，Runge就给出了一个等距节点插值就给出了一个等距节点插值多项式不收敛的例子。多项式不收敛的例子。分段插值高次插值的病态性质：对于一个确定的区间，如果插值节点Runge反例反例:(-5x5)它在它在-5,5上各阶导数均存在，在该区间上取上各阶导数均存在，在该区间上取n+1个等距节点：个等距节点：构造拉格朗日插值多项式为：构造拉格朗日插值多项式为：Runge反例:(-5x5)它在-5,5上各阶导数均n20.1379310.759615-0.6216844 0.066390-0.3568260.42321660.0544630.607879-0.55341680.049651-0.8310170.880668100.0470591.578721-1.531662120.045440-2.7550002.800440140.0443345.332743-5.288409160.043530-10.17386710.217397180.04292020.123671-20.080751200.042440-39.95244939.994889下表列出了下表列出了n=2,4,20的的Ln(xn-1/2)和和R(xn-1/2)的值：的值：n20.1379310.759615-0.6216844 0取取xk=-5+k 计算计算:f(xk)(k=0,1,10)构造构造L10(x).取取:tk=-5+0.05k (k=0,1,200),计算计算:L10(tk)L10(t)f(t)f(x)取xk=-5+k 计算:f(xk)(k=0,一、分段线性一、分段线性Lagrange插值插值构造构造Lagrange线性插值线性插值1.分段线性插值的构造分段线性插值的构造设插值节点为设插值节点为xi，函数值为，函数值为yi，i=0,1,2,nhi=xi+1-xi，i=0,1,2,n-1，任取两个相邻的节点任取两个相邻的节点xk，xk+1，形成一个插值区，形成一个插值区间间xk，xk+1,k=0,1,2,n-1一、分段线性Lagrange插值构造Lagrange线性插值显然显然我们称由上式构成的插值多项式我们称由上式构成的插值多项式L1(x)为为分段线分段线性性Lagrange插值多项式插值多项式。i=0,1,2,n显然我们称由上式构成的插值多项式L1(x)为分段线性Lagr内插外插外插内插外插外插故也称故也称故也称故也称折线插值折线插值折线插值折线插值，如右图：，如右图：，如右图：，如右图：但曲线的光滑性较差，但曲线的光滑性较差，但曲线的光滑性较差，但曲线的光滑性较差，且且且且在节点处有尖点。在节点处有尖点。如果增加节点的数量，减小如果增加节点的数量，减小如果增加节点的数量，减小如果增加节点的数量，减小步长，会改善插值效果。步长，会改善插值效果。步长，会改善插值效果。步长，会改善插值效果。因此因此因此因此则则则则故也称折线插值，如右图：但曲线的光滑性较差，且在节点处有尖点由前述余项定理可知，由前述余项定理可知，n次次Lagrange插值多项式插值多项式的余项为：的余项为：2.分段线性插值的误差估计分段线性插值的误差估计则分段线性插值则分段线性插值L1(x)的余项为的余项为由前述余项定理可知，n次Lagrange插值多项式的余项为：二、分段二次二、分段二次Lagrange插值插值1.分段二次插值的构造分段二次插值的构造设插值节点为设插值节点为xi，函数值为，函数值为yi，i=0,1,2,nhi=xi+1-xi，i=0,1,2,n-1，任取三个相邻的节点任取三个相邻的节点xk-1，xk，xk+1，以，以 xk-1，xk+1为插值区间构造二次为插值区间构造二次Langrange插值多项式：插值多项式：二、分段二次Lagrange插值1.分段二次插值的构造设插2.分段二次插值的误差估计分段二次插值的误差估计由于由于那么分段二次插值那么分段二次插值L2(x)的余项为：的余项为：2.分段二次插值的误差估计由于那么分段二次插值L2(x)的例例:解解:(1)分段线性分段线性Lagrange插值的公式为插值的公式为例:解:(1)分段线性Lagrange插值的公式为同理同理(2)分段二次分段二次Lagrange插值的公式为插值的公式为(2)分段二次Lagrange插值的公式为第1节课-第一章-插值法-拉格朗日插值-分段插课件Langrange插值优缺点：（1）优点：简单，对称 （2）不足：无继承性 为了提高精度有时需增加结点,但这时原来求的 全改变,即所有的基函数都要重新计算，原来的数据不能利用，浪费资源。Langrange插值优缺点：Thank you!第1节课-第一章-插值法-拉格朗日插值-分段插课件