计算方法-插值方法.ppt

《计算方法-插值方法.ppt》由会员分享，可在线阅读，更多相关《计算方法-插值方法.ppt（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计计 算算 方方 法法光信息光信息插值方法插值方法插值多项式定义插值多项式定义插值多项式的存在唯一性插值多项式的存在唯一性插值余项插值余项基函数构造拉氏插值多项式基函数构造拉氏插值多项式计算机实现计算机实现分段线性插值分段线性插值其它插值方法介绍其它插值方法介绍引例及问题综述引例及问题综述引例引例1 1 血药浓度问题血药浓度问题为试验某种新药的疗效，医生对某人用快速静脉注射方为试验某种新药的疗效，医生对某人用快速静脉注射方式一次注入该药式一次注入该药300300mgmg后，在一定时间后，在一定时间t(h)t(h)采取血样，测采取血样，测得血药浓度得血药浓度C C数据如下数据如下试确定血药浓度试

2、确定血药浓度C C与时间与时间t t的函数关系。的函数关系。引例及问题综述引例及问题综述引例引例2 2：标准正态分布函数：标准正态分布函数引例及问题综述引例及问题综述 在生产实际及科学研究中，经常要研究变量之间的函数在生产实际及科学研究中，经常要研究变量之间的函数关系关系y=f(x)y=f(x)。若若f(x)f(x)的表达式很复杂，或的表达式很复杂，或f(x)f(x)只能用一张只能用一张数据表来表示，即只知道数据表来表示，即只知道f(x)f(x)在一系列点在一系列点x x0 0、x x1 1、x xn n处的函数值：处的函数值：这都会给研究带来困难。如何解决这类问题？当函数这都会给研究带来困难

3、。如何解决这类问题？当函数f(x)f(x)比较复杂或根本无法写出解析式时，往往寻求用一个熟悉的比较复杂或根本无法写出解析式时，往往寻求用一个熟悉的简单函数简单函数P(x)P(x)的去近似表示的去近似表示f(x),f(x),将研究将研究f(x)f(x)的问题转化为的问题转化为研究函数研究函数P(x)P(x)的问题。的问题。X X0X1XnF(x)F(x0)F(x1)F(xn)插值插值 /*Interpolation*/当精确函数当精确函数 y=f(x)非常复杂或未知时，在一非常复杂或未知时，在一系列节点系列节点 x0 xn 处测得函数值处测得函数值 y0=f(x0),yn=f(xn)，由此构造一

4、个简单易算的近似函数由此构造一个简单易算的近似函数 g(x)f(x)，满足条件满足条件g(xi)=f(xi)(i=0,n)。这里的这里的 g(x)称为称为f(x)的的插值函数插值函数。最常用的。最常用的插值函数是插值函数是?多项式多项式x0 x1x2x3x4xg(x)f(x)定理定理 (唯一性唯一性)满足满足 的的 n 阶插值多项式阶插值多项式是唯一存在的。是唯一存在的。证明：证明：(p.105-106 利用利用Vandermonde 行列式行列式论证论证)反证：若不唯一，则除了反证：若不唯一，则除了Ln(x)外还有另一外还有另一 n 阶多项阶多项式式 Pn(x)满足满足 Pn(xi)=yi。

5、考察考察 则则 Qn 的阶数的阶数 n而而 Qn 有有 个不同的根个不同的根n+1x0 xn注：注：若不将多项式次数限制为若不将多项式次数限制为 n，则插值多项式则插值多项式不唯一不唯一。例如例如 也是一个插值多项式，也是一个插值多项式，其中其中 可以是任意多项式。可以是任意多项式。这样的插值多项式是否存在并且唯一呢？对此，有如下结论这样的插值多项式是否存在并且唯一呢？对此，有如下结论：拉格朗日多项式拉格朗日多项式 /*Lagrange Polynomial*/niyxPiin,.,0,)(=求求 n 次多项式次多项式 使得使得条件：条件：无重合节点，即无重合节点，即n=1已知已知 x0,x1

6、;y0,y1，求求使得使得111001)(,)(yxPyxP=可见可见 P1(x)是过是过(x0,y0)和和(x1,y1)两点的直线。两点的直线。)()(0010101xxxxyyyxP +=101xxxx 010 xxxx =y0+y1l0(x)l1(x)=10)(iiiyxl称为称为拉氏基函数拉氏基函数 /*Lagrange Basis*/，满足条件满足条件 li(xj)=ij /*Kronecker Delta*/n 1希望找到希望找到li(x)，i=0,n 使得使得 li(xj)=ij；然后令然后令=niiinyxlxP0)()(，则显然有，则显然有Pn(xi)=yi。li(x)每个每

7、个 li 有有 n 个根个根 x0 xi xn=njj i jiniiixxCxxxxxxCxl00)().().()(=j i jiiiixxCxl)(11)(Lagrange Polynomial与与 有关，而与有关，而与 无关无关节点节点f插值余项插值余项 作为作为 的近似一定存在误差，用的近似一定存在误差，用 来表示它的截断误差，来表示它的截断误差，也称之为余项。下面，我们也称之为余项。下面，我们导出其具体表达形式。导出其具体表达形式。【定定理理2 2】设设 在在 a,ba,b上上连连续续，在在(a,b)a,b)内内存存在在，节节点点 ，是是满满足足插插值值条条件件(2.1)(2.1)

8、的插值多项式，则对任何的插值多项式，则对任何 ，插值余项，插值余项 注：注：通常不能确定通常不能确定 x,而是估计而是估计 ,x(a,b)将将 作为误差估计上限。作为误差估计上限。当当 f(x)为任一个次数为任一个次数 n 的的多项式多项式时，时，,可知可知 ，即插值多项式对于次数，即插值多项式对于次数 n 的的多项式是多项式是精确精确的。的。Quiz:给定给定 xi=i+1,i=0,1,2,3,4,5.下面哪个是下面哪个是 l2(x)的图像？的图像？y 0-1 0.5 -0.5 1 2 3 4 5 6 x y 0-1 0.5 -0.5 1 2 3 4 5 6 x y 0-1 0.5 -0.5

9、 1 2 3 4 5 6 x ABC 例：例：已知已知分别利用分别利用 sin x 的的1次、次、2次次 Lagrange 插值计算插值计算 sin 50 并估计误差。并估计误差。解：解：n=1分别利用分别利用x0,x1 以及以及 x1,x2 计算计算利用利用这里这里而而sin 50 =0.7660444)185(50sin10 L0.77614外推外推/*extrapolation*/的实际误差的实际误差 利用利用sin 50 0.76008,内插内插/*interpolation*/的实际误差的实际误差 内插通常优于外推。选择内插通常优于外推。选择要计算的要计算的 x 所在的区间的所在的区

10、间的端点，插值效果较好。端点，插值效果较好。n=2)185(50sin20 L0.76543sin 50 =0.76604442次插值的实际误差次插值的实际误差 高次插值通常优于高次插值通常优于低次插值低次插值但绝对不是次数越但绝对不是次数越高就越好，嘿嘿高就越好，嘿嘿计算机实现 HermiteHermite插值简介插值简介前述插值问题前述插值问题:要求被插函数与插值多项式在节点取要求被插函数与插值多项式在节点取 相同值相同值,LagrangeLagrange型插值条件型插值条件 然而然而,实际许多问题还常常要求两曲线进一步实际许多问题还常常要求两曲线进一步有共同切线有共同切线插值条件为插值条

11、件为:求一次数求一次数求一次数求一次数的多项式的多项式 ，使之满足给定的，使之满足给定的HermiteHermite型插值条件：型插值条件：HermiteHermite插插值值也也叫叫带带指指定定微微商商值值的的插插值值,它它要要构构造造一一个个插插值值函函数数,不不但但在在给给定定节节点点上上取取函函数数值值,而而且且取取已已知知微微商商值值，使使插插值值函函数数和和被被插插函函数数的的密密和和程度更好程度更好。定义：定义：f(x)在区间在区间 a,b 上上 n+1个互异节点个互异节点a=x0 x1x2xn=b,定义在定义在a,b上函数上函数f(x)在节在节点上满足点上满足 f(xi)=yi

12、 f(xi)=y i i=0,1,2n求一个次数不高于求一个次数不高于2n+1次的插值多项式次的插值多项式H(x)满足满足2n+2个个条件条件 H(xi)=yi H(xi)=y i i=0,1,2n若若H(x)存在存在,则叫函数则叫函数f(x)的的Hermite插值多项式插值多项式.因为因为 H(x)是一个次数不高于是一个次数不高于2n+1次的多项式次的多项式,常记为常记为H2n+1(x).定理一定理一:满足插值条件满足插值条件H(xH(xi i)=y)=yi iH(xH(xi i)=y)=yi i i=0,1,2n i=0,1,2n且次数不大于且次数不大于2 2n+1n+1的多项式是唯一的。

13、的多项式是唯一的。定理二定理二:f(x)在区间在区间a,b存在存在2n+2阶导数阶导数,则其则其Hermite插值余项为插值余项为:(x)=(x-x0)(x-x1).(x-xn)函函 数数 构构 造造设设Hermite插值函数插值函数 n n H2n+1(x)=Li(x)yi+hi(x)yi i=0 i=0Li(x),hi(x)都是不高于都是不高于2n+1次的次的多项式多项式,类似类似Lagrange插值插值,利用利用Hermite插值条件可得插值条件可得 Li(xj)=ij hi(xj)=0 Li(xj)=0 hi(xj)=ij i,j=0,1,2n从而可设从而可设 Li(x)=(aix+b

14、i)li(x)2 hi(x)=(cix+di)li(x)2 a ai i,b,bi i,c,ci i,d,di i为待定系数为待定系数,分别由分别由L Li i(x(xi i)=1)=1 和和L Li i(x(xi i)=0)=0 及及h hi i(x(xi i)=1)=1 (i=0,1,2,n)(i=0,1,2,n)确定确定.2n个二重零点个二重零点xk 这里这里那么对应的2n+1次Hermite插值多项式为三次三次HermiteHermite插值函数的构造插值函数的构造(n=1,2n+1=3(n=1,2n+1=3)已知数表：已知数表：x x x x0 0 x x1 1 y y y y0 0

15、 y y1 1 y y y y0 0 y y1 1 求一个三次求一个三次HermiteHermite插值函数插值函数H H3 3(x)(x).解解:H H3 3(x)=y(x)=y0 0L L0 0(x)+y(x)+y1 1L L1 1(x)+(x)+y y0 0h h0 0(x)+(x)+y y1 1h h1 1(x)(x)对对 x=xx=x0 0,有有 L L0 0(x(x0 0)=1 L)=1 L1 1(x(x0 0)=0 h)=0 h0 0(x(x0 0)=0 h)=0 h1 1(x(x0 0)=0)=0 L L0 0(x(x0 0)=0 L)=0 L1 1(x(x0 0)=0 h)=

16、0 h0 0(x(x0 0)=1 h)=1 h1 1(x(x0 0)=0)=0 对对 x=xx=x1 1,有有 L L0 0(x(x1 1)=0 L)=0 L1 1(x(x1 1)=1 h)=1 h0 0(x(x1 1)=0 h)=0 h1 1(x(x1 1)=0)=0 L L0 0(x(x1 1)=0 L)=0 L1 1(x(x1 1)=0 h)=0 h0 0(x(x1 1)=0 h)=0 h1 1(x(x1 1)=1)=1 L Li i(x)=1-a*(x-x(x)=1-a*(x-x0 0)/(x)/(x1 1-x-x0 0)li 2 2(x)h hi i(x)=(x-x(x)=(x-xi

17、 i)li 2 2(x)解之得解之得L L0 0(x)=1+2*(x-x(x)=1+2*(x-x0 0)/(x)/(x1 1-x-x0 0)(x-x)(x-x1 1)/(x)/(x0 0-x-x1 1)2 2h h0 0(x)=(x-x(x)=(x-x0 0)(x-x)(x-x1 1)/(x)/(x0 0-x-x1 1)2 2同理有同理有L L1 1(x)=1+2*(x-x(x)=1+2*(x-x1 1)/(x)/(x0 0-x-x1 1)(x-x)(x-x0 0)/(x)/(x1 1-x-x0 0)2 2h h1 1(x)=(x-x(x)=(x-x1 1)(x-x)(x-x0 0)/(x)/

18、(x1 1-x-x0 0)2 2例例3 3 给定函数值表如下给定函数值表如下:实际问题中还会有其他的插值问题实际问题中还会有其他的插值问题,这类问题可用这类问题可用LagrangeLagrange：x 0 1x 0 1 y y y y0 0 y y1 1 y y y y0 0 求过求过0,10,1两点构造一个插值多项式两点构造一个插值多项式p(x)p(x),满足条件满足条件 p(0)=p(0)=y y0 0,p,p(0)=(0)=y y0 0,p(1)=,p(1)=y y1 1 解解:他有三个条件他有三个条件,故故p(x)p(x)可设为二次多项式可设为二次多项式 p p(x)=(x)=y y0

19、 0 L L0 0(x)+(x)+y y1 1 L L1 1(x)(x)+y y0 0 h h0 0(x)(x)这里这里L L0 0(x),L(x),L1 1(x),(x),h h0 0(x)(x)都是二次多项式都是二次多项式,由插值由插值条件得条件得对对 x=xx=x0 0=0=0有有 L L0 0(0)=1 L(0)=1 L1 1(0)=0 h(0)=0 h0 0(0)=0 (0)=0 L L0 0(0)=0 L(0)=0 L1 1(0)=0 h(0)=0 h0 0(0)=1 (0)=1 对对 x=xx=x1 1=1=1有有 L L0 0(1)=0 L(1)=0 L1 1(1)=1 h(1

20、)=1 h0 0(1)=0 (1)=0 由条件由条件 L0(0)=1,L0(0)=0,L0(1)=0,可设可设 L0(x)=(ax+b)(x-1)利用利用L0(0)=1,L0(0)=0,得得 b=a=-1.所以所以:L0(x)=(-x-1)(x-1)=1-x2 同理可得同理可得L1(x)=x2 h0(x)=x(1-x)所以所以 p(x)=y0(1-x2)+y1 x2+y0(1-x)x y(3)()其余项表达式为其余项表达式为 R(x)=-(1-x)x2 3!3!分段线性插值分段线性插值RungeRunge（龙格）现象龙格）现象 由插值多项式余项公式说明插值节点越多，一般来说误由插值多项式余项公

21、式说明插值节点越多，一般来说误差越小，但这并不是绝对的，因为余项的大小还和函数差越小，但这并不是绝对的，因为余项的大小还和函数f(x)f(x)的高阶导数有关。的高阶导数有关。经典例子：经典例子：取等距节点取等距节点 ，所构造的拉，所构造的拉格朗日插值多项式为格朗日插值多项式为 n 越大，端点附近抖动越大，称为越大，端点附近抖动越大，称为Runge 现象现象 所谓分段线性插值就是通过插值点用折线段连接所谓分段线性插值就是通过插值点用折线段连接起来逼近起来逼近f(x)f(x)。设设f(x)f(x)在在n+1n+1个节点个节点a=xa=x0 0 xx1 1xxn n=b=b上的函数上的函数值为值为在

22、每个小区间在每个小区间 x xk k,x,xk+1k+1 上作线性插值，得上作线性插值，得称称L(x)L(x)为为f(x)f(x)的分段线性插值函数的分段线性插值函数 快速傅立叶变换快速傅立叶变换 /*Fast Fourier Transform*/问题的背景问题的背景 /*background*/傅立叶变换傅立叶变换 函数展开为函数展开为三角级数三角级数设设 f(x)周期为周期为2，在，在 0,2 上展开为三角级数上展开为三角级数 ，其中其中Cj 为复系数，为复系数，则实际计算时要取级数，则实际计算时要取级数的前的前 N 项，并要求在区间的项，并要求在区间的N 个等分点上与个等分点上与f(x

23、)重合。重合。即：给定即：给定0,2 上上N 个等分点个等分点 上的函数值上的函数值 ，令，令 满足插值条件满足插值条件 。N 个未知数个未知数N 个方程个方程Discrete Fourier TransformInverse of DFT总之要进行形如总之要进行形如 的计算，其中的计算，其中 已知，已知，Fast Fourier Transform 快速计算快速计算 (j=0,1,N 1)，其中其中直接计算需直接计算需复数乘法复数乘法 次次N 2 降到降到 N logN由于由于W 的周期性的周期性W qN+s=W s,W k j 实际上只有实际上只有 这这 个不同的值。若个不同的值。若 N

24、为偶数，则为偶数，则W k j只有只有 个不同值。个不同值。10.NWWN N/2先先合并同类项合并同类项，再做乘法。，再做乘法。例：例：N=23=8,计算计算 ，j=0,1,2,3,4,5,6,7技巧：技巧：将将 k,j 先记为先记为二进制数二进制数/*binary numbers*/=+=+=)(222)(222012001122012001122jjjjjjjkkkkkkkkjW)222()222(001122001122+=kkkjjjW)()222()222(012010213212031422kkkjkkkjkkkjW+=)()0()00(012001102kkkjkkjkjW+=2 3次乘次乘法法全部计算需要全部计算需要2 3 8次乘法次乘法一般地：取一般地：取 N=2p，每个每个Cj 用用 2p 次乘法，共用次乘法，共用 2N log2N 次乘法。次乘法。利用利用 ，还可以进一，还可以进一步化简到步化简到 N(p 1)/2 次乘法。次乘法。