插值matlab计算方法

1、计计算算方方法法第五章第五章 插值法插值法本部分课件主要参考哈工大刘克安老师的课件本部分课件主要参考哈工大刘克安老师的课件史晓非史晓非大连海事大学信息工程学院大连海事大学信息工程学院信号与图像处理研究所信号与图像处理研究所 计计算算方方法法-4计算方法KeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKean

2、LKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanL1-11-1问题问题天气预报天气预报早早 中中晚晚夜间夜间8 27 10 2 0C15时出门怎样穿衣服？时出门怎样穿衣服？?7 =xi4 9 16 yi2 3 4 4 7 9 164320数学模型外延广阔数学模型外延广阔潜在巨大

3、意义潜在巨大意义计计算算方方法法计计算算方方法法 实际中，f(x)多样，复杂，通常只能观测到一些离散数据；或者f(x)过于复杂而难以运算。这时我们要用近似函数g(x)来逼近f(x)。 自然地，希望g(x)通过所有的离散点。x0 x1x2x3x4xg(x) f(x)f(x)计计算算方方法法1-2 1-2 数学模型数学模型已知： ,1,2,iix yin=是函数是函数 的离散点的离散点( )f x求：( )( ),nxf x且满足：( ),1,2,niixy in=曲线插值曲线插值问题问题插值插值节点节点插值插值函数函数插值插值条件条件计计算算方方法法InterpolateFitting21( )

4、,1,2,min|( )|nniiniiixy inxy=计计算算方方法法KeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKea

5、nLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanLKeanL数学模型：已知数学模型：已知xi，yi ，求一条光滑曲线满足求一条光滑曲线满足n(xi)= y i 。理论问题：理论问题：1 数学描述；数学描述；2 误差估计；误差估计；3 收敛性。收敛性。计计算算方方法法目的：通过已知点目的：通过已知点求未知点。求未知点。x0 x1x2x3x4xg(x) f(x)f(x)内插内插x外插外插计计算算方方法法1-3 1-3 求解求解1 1）已知曲线方程）已知曲线方程直线、

6、抛物线等直线、抛物线等2 2）未知曲线方程，）未知曲线方程，允许一定的误差，构造多项式方程允许一定的误差，构造多项式方程拉格朗日、牛顿均差法等拉格朗日、牛顿均差法等计计算算方方法法2已知曲线方程已知曲线方程x0 x1y0y1xy1)1)直线直线令：令：01yaa x=将插值条件代入上式，得将插值条件代入上式，得00101011yaa xyaa x=00011111xayxay=计计算算方方法法2)2)抛物线抛物线令：令：2012yaa xax=将插值条件代入上式，得将插值条件代入上式，得200102021011212201222yaa xaxyaa xaxyaa xax=20000211112

7、2222111ayxxxxayxxay=0 xy1y2x0 x1xx2yy计计算算方方法法3)N3)N阶多项式阶多项式2012nnyaa xa xa x=只需确定只需确定,0,1,jajn=即可即可000011111111nnnnnnnayxxayxxayxx = 计计算算方方法法这是这是范德蒙行列式范德蒙行列式，其插值节点互异时，它，其插值节点互异时，它不等于零，方程组的不等于零，方程组的解存在唯一解存在唯一。可以用。可以用高高斯消去法斯消去法求解，其工作量：求解，其工作量：3/ 3n00111111nnnnnxxxxxx是关于是关于的线性代数方程组。的线性代数方程组。其系其系数行列式是数行

8、列式是ja存在唯一性存在唯一性计计算算方方法法3 3未知曲线方程，未知曲线方程，允许一定的误差，构造多项式方程允许一定的误差，构造多项式方程用用N N阶多项式近似：阶多项式近似：2012( )( )nnnxaa xa xa xf x=21,nxxx多项式的基多项式的基01,naaa多项式的坐标多项式的坐标( )( )( )nnR xf xx=余项（余项（p144p144）计计算算方方法法问题：问题：当当n很大时，待定系数法的工作很大时，待定系数法的工作量太大，是否存在简单的构造插值量太大，是否存在简单的构造插值项式项式的方法？的方法？计计算算方方法法0 01 12 20( )( )( )( )

9、( )( )nn nnk kkpxy lxy l xy lxy lxy lx=0( ),1,2,( )niink kiikpxy iny lxy=4 Lagrange插值方法插值方法1,( )0ikxx k =ilxelse=计计算算方方法法40 01 12 23 34 4( )( )( )( )( )( )pxy lxy l xy lxy l xy lx=400 001 102 203 304 400( )( )( )( )( )( )p xy l xyl xy l xyl xy l xy=410 011 112 213 314 411()()()()()()pxy lxy l xy lxy

10、 l xy lxy=420 021 122 223 324 422()()()()()()pxy lxy l xy lxy l xy lxy=430 031 132 233 334 433()()()()()()pxy lxy l xy lxy l xy lxy=440 041 142 243 344 444()()()()()()pxy lxy l xy lxy l xy lxy=计计算算方方法法( )0?klx =0111( )()()()()()kiinlxxxxxxxxxxx=01110111()()()()()( )()()()()()iinkiiiiiiinxxxxxxxxxxlx

11、xxxxxxxxxx=( )1?,kilxxx k =i=1,( )0ikxx k =ilxelse=计计算算方方法法0100012100101( )n01()()()(),1()c1()nnnjjnjjnjjl xxxxllc xxxxxxcxxxxcxxcxx=是个 次多项式，在点 ， ， 处的值是 ，而在点 处是显然 具有如下形式令由于可得到 的值1001()( )()njjnjjxxlxxx=计计算算方方法法011101()( )()njjjnjjjxxlxxx=00()( )()njjj kknkjjj kxxlxxx=称为称为Lagerange插值基插值基计计算算方方法法例：已知函

12、数y=f(x)的观测数据为 x1234y0-5-63试求拉格朗日插值多项式。 00()( )()njjj kknkjjj kxxlxxx=计计算算方方法法解 332(2)(3)(4)( )0(12)(13)(14)(1)(3)(4)( 5)(21)(23)(24)(1)(2)(4)( 6)(3 1)(32)(34)(1)(2)(3)3(41)(42)(43)43xxxp xxxxxxxxxxxx= =00()( )()njjj kknkjjj kxxlxxx=x1234y0-5-63计计算算方方法法解 x0123y230-1试求拉格朗日插值多项式。并求出x=1.5时的值计计算算方方法法已知函数

13、y=f(x)的观测数据为 x012y123试求拉格朗日插值多项式。 解 2(1)(2)(0)(2)( )12(01)(02)(10)(12)(0)(1)3(20)(21)1xxxxpxxxx= =计计算算方方法法1 493 6yx=利用在， ， 处的值建立拉格朗日多项式并近似求 ，012(4 )(9 )(1)(9 )(),()(14 )(19 )( 41)( 49 )(1)(4 )()(94 )(91)xxxxlxlxxxlx=012( )1* ( )2 ( )3 ( )nP xlxl xlx=计计算算方方法法程序：0 01 12 20( )( )( )( )( )( )nn nnk kkpx

14、y lxy l xy lxy lxy lx=00()( )()njjj kknkjjj kxxlxxx=function yTest=GetLagrange(x,y,xTest)nSampNum=length(x);nTestNum=length(xTest);yTest=zeros(nTestNum,1);for nTIndex=1:nTestNum z=xTest(nTIndex); s=0; for k=1:nSampNum p=1; for j=1:nSampNum if j=k p=p*(z-x(j)/(x(k)-x(j); end end s=p*y(k)+s; end yTest

15、(nTIndex)=s; end 计计算算方方法法5 Newton插值插值拉格朗日法增加一个节点，所有的系数拉格朗日法增加一个节点，所有的系数必须重新计算能否有一种方法，增加节点时，必须重新计算能否有一种方法，增加节点时，先前的计算仍然可以利用，只增加很少的工作先前的计算仍然可以利用，只增加很少的工作量就能得到新的高次插值多项式。量就能得到新的高次插值多项式。计计算算方方法法10121( )( )()()()()nnnnP xPxaxxxxxxxx=00( )P xa=做法：做法：1010010( )( )()()P xP xa xxaa xx=21201010201( )( )()()()(

16、)()P xP xa x xx xaa x xa x xx x=0102010121( )()()()()()()()nnnPxaaxxaxxxxaxxxxxxxx=001 11111( )( )( )( )( )( )()( )nnnnnnnnP xaxaxaxaxxxxx=其中计计算算方方法法求解：求解：,0,1,ia in=(),0,1,niiP xyin=依据：依据：00( )P xa=1010010( )( )()()P xP xa xxaa xx=21201010201( )( )()()()()()P xP xa x xx xaa x xa x xx x=0102010121(

17、)()()()()()()()nnnPxaaxxaxxxxaxxxxxxxx=00ay=101110()ypxaxx=21222021()()()ypxaxxxx=1011()()()()kkkkkkkkypxaxxxxxx=计计算算方方法法01010010110,)()(,xxxxfxxfxxfxxxfxfxxfkkkk=称为k阶差商称为1阶差商定义：差商差商计计算算方方法法0101.()().()nnxxxfxfxfx定义定义 给定一个函数表给定一个函数表时时当当其其中中jixxji , .,.,1 ,0),(nixfxfii= = =( )iif xf xx称称为为关关于于 的的零零阶阶

18、差差商商。计计算算方方法法一般的一般的, f(x)关于关于xi,xi+1,xi+k的的k 阶差商记做阶差商记做 fxi,xi+1,xi+k ，即即ikik-iiikiiikiiixx,x.,xxf,x.,xxf,x.,xxf = = 11211的的一一阶阶差差商商定定义义为为关关于于jixxxf,)(ijijjixxxfxf,xxf = =计计算算方方法法2002201055422f xf xf x ,xxx = = = = 例例：32233241062743f xf xf x ,xxx= 230202330,25/ 29,7210f xxf xxf xx ,xxx = = = = 计计算算方

19、方法法差商示意一阶二阶n阶)(,00 xfx)(,11xfx)(,22xfx)(,nnxfx,10 xxf12 ,f x x,1nnxxf012,f x x x21,nnnf xxx0,nf xx计计算算方方法法差商表差商表计计算算方方法法 001001201010110101, , , ,nnnnf xf xf x xxxf x x xxxxxf x xxxxxxxxf x x xxxxxxxx=牛顿插值公牛顿插值公式式()nPx=插插值值余余项项( )nR x= .的各阶差商系数为函数其中xfxpn牛顿插值公式（推导方法选讲）牛顿插值公式（推导方法选讲）计计算算方方法法00100011(

20、)( ) , () , , ()() ()nnnnNewtonN xf xf x x x xf xx x x x xx x= 次插 值 多 项 式 (推 导 方 法 选 讲 )：计计算算方方法法 例3 构造例1中f(x)的牛顿均差插值多项式。作均差表。 P3(x)=0+(-5)(x-1)+2(x-1)(x-2) +(x-1)(x-2)(x-3) =x3-4x2+300100011( )(),(),()()()nnnNxf xf x xxxf xxxxxxxx=计计算算方方法法例 已知数据表： x 1 2 3 5 6F(x) 0 2 6 20 90试求牛顿均差插值多项式。解作均差表： 计计算算方

21、方法法 首先根据给定函数表造出均差表. 给出 的函数表（见），求4次牛顿插值多项式，并由此计算 的近似值.)596.0(f)(xfkkxf(x )阶阶阶阶阶一均差二均差三均差四均差五均差0.400.410750.550.578151.116000.650.696751.186000.280000.800.888111.275730.358930.197330.901.026521.384100.433480.213000.031341.051.253821.515330.524930.228630.031260.00012计计算算方方法法 从均差表看到4阶均差近似常数，5阶均差近似为0. 故取

22、4次插值多项式 做近似即可. )(4xN)55. 0)(4 . 0(28. 0)4 . 0(116. 141075. 0)(4=xxxxN)65. 0)(55. 0)(4 . 0(19733. 0 xxx于是 ,63192.0)596.0()596.0(4= Nf),8 . 0)(65. 0)(55. 0)(4 . 0(03134. 0 xxxx 按牛顿插值公式，将数据代入计计算算方方法法 function D=matdivdif(x,y) % 计算数据的均差表 % x,y为已知数据，D返回各阶均差 n=length(x);D=zeros(n); D(:,1)=y; for j=2:n for

23、 k=j:n D(k,j)=(D(k,j-1)-D(k-1,j-1)/(x(k)-x(k-j+1); end end计计算算方方法法习题P155:1,2,7,8,9选作选作:数值实验数值实验计计算算方方法法计计算算方方法法)()()()(11001 = =nnonxxxxxxcxxccxN由插值条件由插值条件 Nn(xi)=f(xi) i=0,1,n101101()()()()nNxf xc xxf x=由 Newton 插值公式的一种解法插值公式的一种解法导出导出 Nn(x0) =c0=f(x0)1010110()(),f xf xcf x xxx=计计算算方方法法00120220212()

24、,()()()()f xf xxxxcxxxxf x=020110011120222,(),()()()()f xcxxxf xxxxff xxxxxx = 01211220212,()()()()()f xcxxxf xxxxf xx= ,)()()(,21121202210 xxfxxxfxfxxcxxf= = = = 010011( ),()()()()nonnN xcf x xxxc xxxxxx=1201201220,f xxf xxcf xxxxx = 0212202110120102( )( )( )()() ()() ()()f xf xf xcxxxxxxxxxxxx= = 计计算算方方法法依次类推，得：依次类推，得： cn=fx0,x1,xn1201100001( ) ,., , ,.,() , ,.,ninnnninijjj inf xf x xxf x xxcxxxxf x xx = = = = = = = = 计计算算方方法法00010101(),nncfxf xcf xxcf xxx= = = = =10010012010011,( ),( )(),(),()(),()()()onnnnnc ccxnNewtonNxf xf x xxxf x x x