插值法课堂.ppt

插值法课堂现在学习的是第1页，共93页2.一般概念一般概念现在学习的是第2页，共93页研究问题研究问题若满足条件的 存在，又如何构造？满足插值条件的多项式满足插值条件的多项式 是否存在，唯是否存在，唯一？一？用用 近似代替近似代替 的误差估计？的误差估计？现在学习的是第3页，共93页定理定理1 满足条件满足条件(1.1)(1.1)的的 n n 阶插值多项式阶插值多项式(1.2)(1.2)是唯一是唯一存在的。存在的。3.3.多项式插值多项式插值证明：由(1.1)可得 (1.3)现在学习的是第4页，共93页 (1.3)为一个n1未知量 的线性方程组，要证明插值多项式存在唯一，只要证明参数 存在且唯一，即只要证明其系数行列式不为零即可。其系数行列式为 此为范德蒙行列式。利用行列式性质可得系数行列式为 现在学习的是第5页，共93页 由于 时 ，故所有因子 ，于是 即插值多项式存在唯一。直接求解方程组可得到P(x)，但过程繁琐现在学习的是第6页，共93页插值方法插值方法拉格朗日插值拉格朗日插值牛顿插值牛顿插值埃尔米特插值埃尔米特插值分段低次插值分段低次插值三次样条插值三次样条插值现在学习的是第7页，共93页2 2 拉格朗日插值拉格朗日插值1.1.线性插值和抛物插值线性插值和抛物插值对给定插值点对给定插值点,求出形如求出形如的插值多项式的方法有多种的插值多项式的方法有多种.n=1已知区间 及端点函数值求线性插值多项式可见可见 L1(x)是过是过 和和 两点的直线。两点的直线。现在学习的是第8页，共93页现在学习的是第9页，共93页现在学习的是第10页，共93页n=2假设给定插值点 求二次插值多项式现在学习的是第11页，共93页为由(2.4)的第一式，知 的两个零点，则将条件带入到上式中可得现在学习的是第12页，共93页现在学习的是第13页，共93页现在学习的是第14页，共93页2.拉格朗日插值多项式拉格朗日插值多项式现在学习的是第15页，共93页现在学习的是第16页，共93页现在学习的是第17页，共93页现在学习的是第18页，共93页拉格朗日插值公式优缺点优点：结果清晰、紧凑，适用于作理论分析、应用；当节点个数有所变动，插值基函数都要重新算一遍，整个插值公式发生变化，在实际应用时不方便。现在学习的是第19页，共93页3 3 均差与牛顿插值均差与牛顿插值一、均差及其一、均差及其性质性质现在学习的是第20页，共93页定义定义1 1一阶差商一阶差商二阶差商二阶差商现在学习的是第21页，共93页均差的基本性质均差的基本性质:现在学习的是第22页，共93页现在学习的是第23页，共93页(4)若fx,x0,x1,xk 是 x 的 m 次多项式,则 fx,x0,x1,xk,xk+1是 x 的 m-1 次多项式证：由差商定义 右端分子为 m 次多项式,且当 x=xk+1 时,分子为0,故分子含有因子 xk+1 x，与分母相消后，右端为m-1 次多项式。现在学习的是第24页，共93页4.4.1 差商及其性质(5)若 f(x)是n次多项式,则f x,x0,x1,xn 恒为0 证：f(x)是n次多项式，则f x,x0 是 n-1次多项式,f x,x0,x1 是 n-2 次多项式,依次递推 ，f x,x0,x1,xn-1 是零次多项式，所以 fx,x0,x1,xn 0现在学习的是第25页，共93页均差表:kxkf(xk)一阶均差 二阶均差 三阶均差 01234x0 x1x2x3x4f(x0)f(x1)f(x2)f(x3)f(x4)fx0,x1fx1,x2 fx0,x1,x2fx2,x3 fx1,x2,x3 fx0,x1,x2,x3fx3,x4 fx2,x3,x4 fx1,x2,x3,x4 现在学习的是第26页，共93页把后一式依次带入前一式现在学习的是第27页，共93页增加一项即可现在学习的是第28页，共93页kxkf(xk)一阶差商 二阶差商 三阶差商 四阶差商012341234514786 3 3 0 1 -1 -1/3 -2 -3/2 -1/6 1/24现在学习的是第29页，共93页现在学习的是第30页，共93页差分与等距节点插值差分与等距节点插值上节讨论任意分布节点的插值公式，应用时常碰到等距节点的情形，此时插值公式可简化，为此先介绍差分一、差分及其一、差分及其性质性质现在学习的是第31页，共93页在处的m阶(向前)差分现在学习的是第32页，共93页N阶差商与导数的关系现在学习的是第33页，共93页差分表:2f0 2f1 2f2 f0f1f2f3f0f1f2f3f401234 2 3 fkk现在学习的是第34页，共93页二、等距节点插值公式二、等距节点插值公式现在学习的是第35页，共93页 如果要表示附近的函数值，也可使用牛顿插值公式（3.6），但为了降低误差，插值点应按的次序排列，作变换，并利用公式均差与向后差分关系公式这时得36现在学习的是第36页，共93页称其为牛顿后插公式牛顿后插公式，其中其余项37现在学习的是第37页，共93页 通常求开头部分插值点附近函数值时使用牛顿前插公式，求插值节点末尾附近函数值时使用牛顿后插公式.如果用相同节点进行插值，则向前向后两种公式只是形式上差别，其计算结果是相同的.38现在学习的是第38页，共93页为使用牛顿插值公式，先构造差分表（表2-4）.给出在处的函数值，试用4次等距节点插值公式计算及例例的近似值并估计误差.解解根据题意，插值条件为 由于接近，所以应用牛顿向前插值公式计算的近似值.39现在学习的是第39页，共93页(注意：表中带下划线的数据为 点的各阶向前差分，双下划线为 点的各阶向后差分.)40现在学习的是第40页，共93页取则用表2-4上半部的各阶向前差分，得41现在学习的是第41页，共93页由余项公式（4.11）得误差估计其中42现在学习的是第42页，共93页于是 计算应使用牛顿向后插值公式，用差分表2-4中下半部的各阶向后差分，得这里43现在学习的是第43页，共93页其中由余项公式（4.13）得误差估计44现在学习的是第44页，共93页解：现在学习的是第45页，共93页分段线性插值高次插值的龙格现象高次插值的龙格现象 插值多项式余项公式说明插值节点越多，一般说插值多项式余项公式说明插值节点越多，一般说来误差越小，函数逼近越好，但这也不是绝对的，来误差越小，函数逼近越好，但这也不是绝对的，因为余项的大小既与插值节点的个数有关，也与函因为余项的大小既与插值节点的个数有关，也与函数数f(x)的高阶导数有关的高阶导数有关。换句话说，适当地提高插。换句话说，适当地提高插值多项式的次数，有可能提高计算结果的准确程度值多项式的次数，有可能提高计算结果的准确程度，但并非插值多项式的次数越高越好。当插值节点，但并非插值多项式的次数越高越好。当插值节点增多时，不能保证非节点处的插值精度得到改善，增多时，不能保证非节点处的插值精度得到改善，有时反而误差更大。考察函数有时反而误差更大。考察函数 现在学习的是第46页，共93页考察函数考察函数 右图给出了右图给出了和和 的图像的图像,当当n增大时增大时,在两端在两端会发出激烈的振荡会发出激烈的振荡,这就是所谓龙格现这就是所谓龙格现象。该现象表明象。该现象表明,在在大范围内使用高次大范围内使用高次插值插值,逼近的效果往逼近的效果往往是不理想的往是不理想的 现在学习的是第47页，共93页 另外，从舍入误差来看，高次插值误差的传播另外，从舍入误差来看，高次插值误差的传播也较为严重，在一个节点上产生的舍入误差会在计也较为严重，在一个节点上产生的舍入误差会在计算中不断扩大，并传播到其它节点上。因此，次数算中不断扩大，并传播到其它节点上。因此，次数太高的高次插值多项式并不实用，因为节点数增加太高的高次插值多项式并不实用，因为节点数增加时，计算量增大了，但插值函数的精度并未提高。时，计算量增大了，但插值函数的精度并未提高。为克服在区间上进行高次插值所造成的龙格现象，为克服在区间上进行高次插值所造成的龙格现象，采用分段插值的方法，将插值区间分成若干个小的采用分段插值的方法，将插值区间分成若干个小的区间，在每个小区间进行线性插值，然后相互连接区间，在每个小区间进行线性插值，然后相互连接，用连接相邻节点的折线逼近被插函数，这种把插，用连接相邻节点的折线逼近被插函数，这种把插值区间分段的方法就是分段线性插值法。值区间分段的方法就是分段线性插值法。现在学习的是第48页，共93页2.4.2 2.4.2 分段线性插值分段线性插值 分段线性插值就是通过插值节点用折线段连接起分段线性插值就是通过插值节点用折线段连接起来逼近来逼近f(x)。设设f(x)f(x)在在n+1n+1个节点个节点 上的函数值为上的函数值为 ,在每个小区间在每个小区间 (k=0,1,k=0,1,，n n）上作线性插值，得上作线性插值，得 现在学习的是第49页，共93页在几何上就是用折线在几何上就是用折线替代曲线替代曲线,如右图所示如右图所示若用插值基函数表示若用插值基函数表示,则在则在 a,b 上上 其中其中现在学习的是第50页，共93页显然，显然，是分段线性连续函数，且是分段线性连续函数，且 称称S S(x x)为为f f(x x)的的分段线性插值函数。分段线性插值函数。由线性插值的余项估计式知由线性插值的余项估计式知,f f(x x)在每个子段在每个子段上有误差估计式上有误差估计式其中其中 现在学习的是第51页，共93页例例2.19 2.19 已知已知f(x)f(x)在四个节点上的函数值如下表所示在四个节点上的函数值如下表所示 30 45 60 901求求f(x)f(x)在区间在区间 30,9030,90 上的上的分段连续线性插值函数分段连续线性插值函数S(x)S(x)解解 将将插值区间插值区间 30,9030,90 分成连续的三个小区间分成连续的三个小区间 30,4530,45,45,6045,60,60,9060,90 则则S(x)在区间在区间 30,4530,45 上的上的线性插值为线性插值为 现在学习的是第52页，共93页S(x)在区间在区间 45,6045,60 上的线性插值为上的线性插值为 S(x)S(x)在区间在区间 60,9060,90 上的线性插值上的线性插值为为 现在学习的是第53页，共93页将各小区间的将各小区间的线性插值函数连接在一起，得线性插值函数连接在一起，得 现在学习的是第54页，共93页 许多实际问题不但要求插值函数许多实际问题不但要求插值函数p(x)在插值节点在插值节点处与被插函数处与被插函数f(x)有相同的函数值有相同的函数值p(xi)=f(xi)(i=0,1,2,n),而且要求在有些节点或全部节点上而且要求在有些节点或全部节点上与与f(x)的导数值也相等，甚至要求高阶导数值也相的导数值也相等，甚至要求高阶导数值也相等，能满足这种要求的插值问题就称为等，能满足这种要求的插值问题就称为埃尔米特插埃尔米特插值值(Hermite)埃尔米特埃尔米特(Hermite)插值插值现在学习的是第55页，共93页 定义定义定义定义 已知已知已知已知 n n+1+1个互异点上个互异点上 的函数值的函数值 和导数值和导数值 ,若存在若存在 一个次数不超过一个次数不超过一个次数不超过一个次数不超过2 2 2 2n n n n+1+1的多项式的多项式的多项式的多项式H H H H(x x)，满足满足 则称则称则称则称HH(x x)为为为为f(x)的的的的2 2 2 2n n+1+1次埃尔米特次埃尔米特次埃尔米特次埃尔米特(HermiteHermite)插插值值 2.4 埃尔米特插值埃尔米特插值上式给出了上式给出了2 2n+2+2个条件，可惟一确定一个次数不超过个条件，可惟一确定一个次数不超过2 2n+1+1的多项式的多项式H2n+1(x)，采用类似于求采用类似于求Lagrange插值多插值多项式的基函数方法求埃尔米特项式的基函数方法求埃尔米特(Hermite)插值多项式插值多项式H2n+1(x)现在学习的是第56页，共93页次数不超过次数不超过2n+1次的多项式的次的多项式的形式为：形式为：，H2n+1(x)=H(x),H2n+1(x)=a0+a1x+a2x2+a2n+1x2n+1由由2n+2个条件来确定个条件来确定2n+2个系数个系数a0,a1,a2,a2n+1显然非常显然非常复杂复杂,所以要用求所以要用求Lagrange插值多项式的基函数的方法插值多项式的基函数的方法,求求插值基函数插值基函数 i(x)及及 i(x)(i=0,1,2,n)共有共有2n+2个个,设每一个设每一个基函数为次数不超过基函数为次数不超过2n+1次的多项式，且满足条件次的多项式，且满足条件(i,j=0,1,2,n)现在学习的是第57页，共93页HermiteHermite插值多项式可写成插值基函数表示的形式插值多项式可写成插值基函数表示的形式验证：验证：现在学习的是第58页，共93页根据插值条件可求出根据插值条件可求出 和和H2n+1(x)为满足条件为满足条件的的2 2n+1+1次次Hermite插值多项式。插值多项式。现在学习的是第59页，共93页定理定理5.3 5.3 满足插值条件满足插值条件 的的HermiteHermite插值多项式是惟一的。插值多项式是惟一的。证证:设设 和和 都满足上述插值条件都满足上述插值条件,令令则每个节点则每个节点 均为均为 的二重根的二重根,即即有有2 2n+2+2个根，但个根，但 是不高于是不高于2 2n+1+1次的多项式次的多项式，所以，所以 ，即，即 惟一性得证。惟一性得证。现在学习的是第60页，共93页定理定理5.4 5.4 若若f(x)在在 a,b 上存在上存在2 2n+2+2阶导数，则阶导数，则 2 2n+1+1次次Hermite插值多项式的余项为插值多项式的余项为 其中其中定理的证明可仿照定理的证明可仿照LagrangeLagrange插值余项的证明插值余项的证明方法请同学们自行证明方法请同学们自行证明 现在学习的是第61页，共93页实际中使用最广泛的是三次实际中使用最广泛的是三次Hermite插值多项式插值多项式,即即n=1的情况的情况余项余项现在学习的是第62页，共93页例例5.18 已知函数已知函数 y=f(x)的数据如下表所示的数据如下表所示,求次数求次数 不超过三次的不超过三次的Hermite的插值多项式的插值多项式H3(x)使使 H3(xi)=yi (i=0,1,2)H3(xi)=yi 解解 所求三次所求三次Hermite的插值多项式为的插值多项式为现在学习的是第63页，共93页解解 所求三次所求三次Hermite的插值多项式为的插值多项式为由插值条件得到以下方程组由插值条件得到以下方程组解上述方程组解上述方程组故得故得现在学习的是第64页，共93页另解另解 由题意知：由题意知：x=0是是H3(x)的二重零点，故可令的二重零点，故可令 H3(x)=x2(ax+b)由由H3(-1)=-1 H3(-1)=1 知知 b-a=-1 a+b=1 解之得解之得 a=1 b=0 故有故有 H3(x)=x3 微分和积分、差分、差商与求微分和积分、差分、差商与求和这几种矛盾相互转化的运算和这几种矛盾相互转化的运算规律如有图所示，规律如有图所示，表示近似表示近似 表示互为逆运算表示互为逆运算。至于如何实现这些基本运算之至于如何实现这些基本运算之间的联系和转化，途径是多种间的联系和转化，途径是多种多样的，结果是丰富多彩多样的，结果是丰富多彩 的，魅力是无群无尽的的，魅力是无群无尽的现在学习的是第65页，共93页4 4 埃尔米特插值埃尔米特插值注：注：N 个条件可以确定个条件可以确定 阶多项式。阶多项式。N 1要求在要求在1个节点个节点 x0 处直到处直到m0 阶导数都相等的插值阶导数都相等的插值多项式即为多项式即为Taylor多项式多项式其余项为其余项为一般只考虑一般只考虑 f 与与f 的值。的值。现在学习的是第66页，共93页两个典型的埃尔米特多项式两个典型的埃尔米特多项式解：由条件，可确定次数不超过3的插值多项式设现在学习的是第67页，共93页为得余项的表达式，设待定由及罗尔定理现在学习的是第68页，共93页现在学习的是第69页，共93页2.两点三次埃尔米特插值两点三次埃尔米特插值 现在学习的是第70页，共93页现在学习的是第71页，共93页现在学习的是第72页，共93页现在学习的是第73页，共93页其余项现在学习的是第74页，共93页现在学习的是第75页，共93页现在学习的是第76页，共93页现在学习的是第77页，共93页5 5 分段低次插值分段低次插值一、高次插值的病态性质一、高次插值的病态性质龙格(Runge)现象.二、分段线性插值二、分段线性插值所谓分段线性插值就是用通过插值点的折线段逼近f(x).现在学习的是第78页，共93页现在学习的是第79页，共93页二、分段三次埃尔米特插值二、分段三次埃尔米特插值分段线性插值函数导数间断，若已知节点上函数值和导数，可构造一个导数连续的插值函数Ih(x)，满足现在学习的是第80页，共93页现在学习的是第81页，共93页现在学习的是第82页，共93页6 6 三次样条插值三次样条插值一、样条插值的概念一、样条插值的概念现在学习的是第83页，共93页3n-3个条件现在学习的是第84页，共93页现在学习的是第85页，共93页二、三次样条插值函数的建立二、三次样条插值函数的建立线性插值基函数法现在学习的是第86页，共93页现在学习的是第87页，共93页现在学习的是第88页，共93页现在学习的是第89页，共93页现在学习的是第90页，共93页现在学习的是第91页，共93页现在学习的是第92页，共93页现在学习的是第93页，共93页