数学建模插值方法.ppt

《数学建模插值方法.ppt》由会员分享，可在线阅读，更多相关《数学建模插值方法.ppt（75页珍藏版）》请在优知文库上搜索。

1、插值与拟合插值与拟合前言前言 函数是多种多样的，在科研与工程实际中有的函数表达式过于复杂而不便于计算，但又需要计算多点的函数值；有的函数甚至给不出数学式子，只能通过实验和测量得到一些离散数据（如某些点的函数值和导数值）。面对这种情况，很自然的一个想法就是构造某个简单的函数作为要考察的函数的近似 。 如果要求近似函数满足给定的离散数据，则称之为插值函数。实用上，我们常取结构相对比较简单的代数多项式作为插值函数,这就是所谓的代数插值。 设设 为给定的节点，为给定的节点， ，为相应的函数值，求一个次数不超过为相应的函数值，求一个次数不超过 的多项式的多项式 ，使其满足使其满足 ， .这类问题称为这类

2、问题称为插值问题插值问题。 称为称为被插值函数被插值函数， 称称为为插值函数插值函数， 称为称为插值节点插值节点01,nx xx)(iixfy ni, 1 , 0n)(xPnni, 1 , 0( )niiP xy一、问题提出一、问题提出01,nx xx( )f x( )nP x插值部分插值部分 定理定理1 设设 为给定的彼此互异的为给定的彼此互异的 个插值个插值节点，则存在唯一的次数不超过节点，则存在唯一的次数不超过 的多项式的多项式 ，满足，满足条件条件 , .nxxx10,1nn)(xPn( )niiP xyni, 1 , 0二、存在性与唯一性二、存在性与唯一性证明证明: 设设 , 其中其

3、中 为待定系数为待定系数.利用插值条件利用插值条件 , ,我们得到一个线性代数方程我们得到一个线性代数方程组组 , ,其中其中 观察发现矩阵观察发现矩阵A A是范德蒙矩阵是范德蒙矩阵, ,那么那么, ,由几代知识知道矩阵由几代知识知道矩阵A A 的行列式的行列式 为为 , ,由定理中条件由定理中条件, ,插值结点为彼此互异的插值结点为彼此互异的, , 那么行那么行列式不为零列式不为零. .故由故由CramerCramer法则知线性代数方程组法则知线性代数方程组 存在唯一解存在唯一解. . 2012nnnPaa xa xa x012,na a aa( )niiP xyAab0011111nnnn

4、nxxxxAxx0011,nnayayabay0( )()ijj i nDet Axx Aab三、三、Lagrange插值法插值法 011011()()()()( ),0,1,()()()()iiniiiiiiinxxxxxxxxl xinxxxxxxxx0( )( )nni iiPxy lx（1）Lagrange插值插值多项式可以表示为多项式可以表示为 引入记号引入记号 , , 易证易证 , , 从而从而LagrangeLagrange插值多项式可表示为插值多项式可表示为 )()()()(1101niiiiiiinxxxxxxxxx)()()(101ninxxxxxxxniinininxxx

5、xyxP011)()()()(（2）插值误差估计）插值误差估计 定理定理2 设设 在在 上连续，上连续， 在在 内存在内存在,节点节点 ， 是拉格朗日插值多项是拉格朗日插值多项式，则对任意式，则对任意 , 插值余项插值余项 其中其中 且依赖于且依赖于 .)()(xfn,ba)()1(xfn),(babxxxan10)(xPn,bax)()!1()()()()(1)1(xnfxPxfxRnnnn),(bax例2.求过点(2,0)(4,3)(6,5)(8,4)(10,1)的拉格朗日型插值多项式。解：用4次插值多项式对5个点插值 00112233442 04 36 58 410 1,xyx yxyx

6、 yxy0(4)(6)(8)(10)1( )(4)(6)(8)(10)(2 4)(2 6)(2 8)(2 10)384xxxxl xxxxx 1(2)(6)(8)(10)1( )(2)(6)(8)(10)(4 2)(4 6)(4 8)(4 10)96xxxxl xxxxx2(2)(4)(8)(10)1( )(2)(4)(8)(10)(6 2)(6 4)(6 8)(6 10)64xxxxl xxxxx3(2)(4)(6)(10)1( )(2)(4)(6)(10)(8 2)(8 4)(8 6)(8 10)96xxxxl xxxxx4(2)(4)(6)(8)1( )(2)(4)(6)(8)(10 2

7、)(10 4)(10 6)(10 8)384xxxxl xxxxx40 01 12 23 34 4( )( )( )( )( )( )P xy l xy l xy l xy l xy l x13(4)(6)(8)(10)(2)(6)(8)(10)3849654(2)(4)(8)(10)(2)(4)(6)(10)64961(2)(4)(6)(8)384xxxxxxxxxxxxxxxxxxxx于是有于是有function yi=lagrcz(x,y,xi)n=length(x);m=length(xi);for s=1:m yi(s)=0; for i=1:n w(i)=1; dw(i)=1; f

8、or j=1:n if (j=i) w(i)=(xi(s)-x(j)*w(i); dw(i)=(x(i)-x(j)*dw(i); end end yi(s)=y(i)*w(i)/dw(i)+yi(s); endend23456789100123456缺点缺点: 当增加或减少插值节点时当增加或减少插值节点时,基函数需要重新基函数需要重新 构造构造,不便于实际的计算使用不便于实际的计算使用 定义定义称称 为为 在在 两点处的两点处的一阶差商一阶差商. （1）差商定义差商定义011201202, ,f x xf x xf x x xxx( )() ,ijijijf xf xf x xijxx( )f

9、 x四、四、 Newton插值法插值法,ijx x01112010, ,nnnnf x xxf x xxf x xxxx二阶差商二阶差商n 阶差商阶差商(2) Newton插值公式插值公式 由差商定义由差商定义把以上各式由后向前代入把以上各式由后向前代入,可得可得 , xa b 000( )() ,()f xf xf x xxx001011 , ,()f x xf x xf x x xxx010101 , , , , , , ,()nnnnf x xxf x xxf x x xxx x00100101( )( ) , () , ,()()nnnN xf xf x x x xf x xxx xx

10、 x010( )( )( ) , , ,()()nnnnR xf xN xf x x xxx xx x差商表差商表 一阶一阶差商差商二阶差商二阶差商三阶差商三阶差商四阶差商四阶差商kx0 x1x2x3x4x()kf x0()f x2()f x1()f x3()f x4()f x01,f xx12,f x x23,f xx34,f x x012,f xx x123,f x xx234,f xx x0123,f xx xx1234,f x xx x01234,f x x xx x例2:已知求满足以上插值条件的牛顿型插值多项式。解: 1 2 3 4 0 -5 -6 3一阶差商二阶差商三阶差商 1 2

11、 3 4 0 -5 -6 3 -5 -1 9 2 5 1xy( )if xix由上述差商表对角线上取得的值则牛顿三次插值多项式为 00101201230, ,5, , ,2, , , 1,f xf x xf x x xf x x x x)2)(1(2) 1(50)(xxxxNn) 3)(2)(1(xxx3423xxfunction yi=newtcz(x,y,xi)n=length(x); m=length(xi); nt=zeros(n,n);nt(:,1)=y;for i=2:n for j=i:n nt(j,i)=(nt(j,i-1)-nt(j-1,i-1)/(x(j)-x(j-(i-1

12、); endEndfor i=1:n nt(i,i)Endfor i=1:m yi(i)=nt(1,1); for j=2:n t=1; for s=1:j-1 t=t*(xi(i)-x(s); end yi(i)=yi(i)+t*nt(j,j); endend五、五、 Hermite插值多项式插值多项式给定的是节点上的函数值和导数值给定的是节点上的函数值和导数值问题问题：已知：已知iiyxf)(iiyxf)(1 , 0i求求3次多项式次多项式 ，使得，使得)(3xHiiyxH)(iiyxH)(1 , 0i120101010210101032121)(yxxxxxxxxyxxxxxxxxxH1

13、20101021010)()(yxxxxxxyxxxxxx *多项式插值的问题 前面介绍了构造插值公式的方法，并分析了它前面介绍了构造插值公式的方法，并分析了它们的余项。在实际应用插值函数作近似计算时，总们的余项。在实际应用插值函数作近似计算时，总希望插值公式余项希望插值公式余项 的绝对值小一些，即使得的绝对值小一些，即使得 逼近的精度好。从表达式看，似乎提高插值多项式逼近的精度好。从表达式看，似乎提高插值多项式的次数便可达到目的，但实际上并非如此。的次数便可达到目的，但实际上并非如此。)(xR例如 给定函数 取其等距节点 ， 构造的Lagrange插值多项式为 当 时， 只能在 内收敛，而在

14、这个区间以外是发散的。这种畸形现象 通常叫做Runge现象。如下图所示。3.63x 21,55,1f xxx 201( )1nnijjpxlxxn( )npx), 1 , 0( ,/105ninixi六、六、 分段插值分段插值 所谓分段插值，就是将被插值函数逐段多项式化。在每所谓分段插值，就是将被插值函数逐段多项式化。在每个个 子段上构造插值多项式，然后把它们装配在一，子段上构造插值多项式，然后把它们装配在一，作为整个区间作为整个区间 上的插值函数，即称为分段多项式。如果上的插值函数，即称为分段多项式。如果函数函数 在每个子段上都是在每个子段上都是 次式，则称为次式，则称为 次式。次式。1,i

15、ix x, a b kSxkk一般（低次：一般（低次：k=1,2,3）（1）分段线性插值的构造（）分段线性插值的构造（k=1) 易知易知 在每个子区间在每个子区间 上是一上是一次插值多项式次插值多项式分段线性插值的余项分段线性插值的余项其中其中1 , (0,1,)iix xin2( )( )( )8Mhf xxR x( )xmax( )a x bMfx 11111 iiiiiiiiiixxxxxxxyxxxxyx,)(（2） 分段抛物线插值（分段抛物线插值（K=2）（3） 分段三次分段三次 Hermite 插值插值(K=3)（4） 三次样条插值三次样条插值 在分段插值中，分段线性插值在节点上仅

16、连续而不可在分段插值中，分段线性插值在节点上仅连续而不可导，分段三次埃尔米特插值有连续的一阶导数，如此光滑导，分段三次埃尔米特插值有连续的一阶导数，如此光滑程度常不能满足物理问题的需要，而引入的样条函数则可程度常不能满足物理问题的需要，而引入的样条函数则可以同时解决这两个问题以同时解决这两个问题,使插值函数既是低阶分段函数使插值函数既是低阶分段函数,又又是光滑的函数。是光滑的函数。 三次样条函数定义三次样条函数定义 给定区间给定区间 的一个划分的一个划分 ，如果函数如果函数 满足：满足： ba,bxxxxann110)(xS（1）在每一小区间上是三次多项式；）在每一小区间上是三次多项式；（2）在每个内节点上具有二阶连续导数；）在每个内节点上具有二阶连续导数；（3）iiyxS)( 则称则称 是是 在该区间上关于该划分的一个三次在该区间上关于该划分的一个三次样条函数。样条函数。)(xs)(xf其中四个待定系数为其中四个待定系数为 , ,子区间共有子区间共有n n个所以要个所以要确定确定S(x)S(x)需要需要4n4n个待定系数。个待定系数。 另一方面另一方面, ,要求分段三次多项式要求分段