数值分析常用的插值方法

数值分析报告班级：专业：流水号：学号：姓名：常用的插值方法序言在离散数据的基础上补插连续函数，使得这条连续曲线通过全部给定的离散数据点。插值是离散函数逼近的重要方法，利用它可通过函数在有限个点处的取值状况，估算出函数在其他点处的近似值。早在6世纪，中国的刘焯已将等距二次插值用于天文计算。17世纪之后，牛顿、拉格朗日分别讨论了等距和非等距的一般插值公式。在近代，插值法仍然是数据处理和编制函数表的常用工具，又是数值积分、数值微分、非线性方程求根和微分方程数值解法的重要基础，许多求解计算公式都是以插值为基础导出的。插值问题的提法是：假定区间[a，b〕上的实值函数f（x）在该区间上n＋1个互不相同点x0，x1……xn处的值是f（x0），……f（xn），要求估算f（x）在[a，b〕中某点的值。其做法是：在事先选定的一个由简单函数构成的有n＋1个参数C0，C1，……Cn的函数类Φ(C0，C1，……Cn)中求出满足条件P（xi）＝f（xi）（i＝0，1，……n）的函数P(x)，并以P(x)作为f(x)的估值。此处f（x）称为被插值函数，x0，x1，……xn称为插值结(节)点，Φ(C0，C1，……Cn)称为插值函数类，上面等式称为插值条件，Φ（C0，……Cn）中满足上式的函数称为插值函数，R（x）＝f（x）－P（x）称为插值余项。求解这类问题，它有很多种插值法，其中以拉格朗日(Lagrange)插值和牛顿(Newton)插值为代表的多项式插值最有特点，常用的插值还有Hermit插值，分段插值和样条插值。一．拉格朗日插值1.问题提出：已知函数yfx在n+1个点01,,,nxxx上的函数值01,,,nyyy，求任意一点x的函数值fx。说明：函数yfx可能是未知的；也可能是已知的，但它比较复杂，很难计算其函数值fx。2.解决方法：构造一个n次代数多项式函数nPx来替代未知（或复杂）函数yfx，则用nPx作为函数值fx的近似值。设2012nnnPxaaxaxax，构造nPx即是确定n+1个多项式的系数012,,,,naaaa。3.构造nPx的依据：当多项式函数nPx也同时过已知的n+1个点时，我们可以认为多项式函数nPx逼近于原来的函数fx。根据这个条件，可以写出非齐次线性方程组：20102000201121112012nnnnnnnnnnaaxaxaxyaaxaxaxyaaxaxaxy其系数矩阵的行列式D为范德萌行列式：2000211102111nnijnijnnnnxxxxxxDxxxxx故当n+1个点的横坐标01,,,nxxx各不相同时，方程组系数矩阵的行列式D不等于零，故方程组有唯一解。即有以下结论。结论：当已知的n+1个点的横坐标01,,,nxxx各不相同时，则总能够构造唯一的n次多项式函数nPx，使nPx也过这n+1个点。4.几何意义f(x)P5(x)5．举例：已知函数fxx，求115f。分析：本题理解为，已知“复杂”函数fxx，当x=81,100,121,144时，其对应的函数值为：y=9,10,11,12，当x=115时，求函数值115f。解：（1）线性插值：过已知的（100,10）和（121,11）两个点，构造1次多项式函数1Px，于是有11211001011100121121100xxPx则111511510.71428571428572fP。（2）抛物插值：构造2次多项式函数2Px，使得它过已知的（100,10）、（121,11）和（144,12）三个点。于是有2次拉格朗日插值多项式：2121144100144100121101112100121100144121100121144144100144121xxxxxxPx则有2115115fP10.722755505364206.拉格朗日n次插值多项式公式：1200102002110121011011nnnnnnnnnnnxxxxxxPxyxxxxxxxxxxxxyxxxxxxxxxxxxyxxxxxx00110nnnnkkkPxlxylxylxylxy其中klx称为基函数（k=0,1,….,n），每一个基函数都是关于x的n次多项式，其表达式为：0njkjkjjkxxlxxx拉格朗日公式特点：1．把每一点的纵坐标ky单独组成一项；2.每一项中的分子是关于x的n次多项式，分母是一个常数；3.每一项的分子和分母的形式非常相似，不同的是：分子是x，而分母是kx7.误差分析（拉格朗日余项定理）101!nnnkkfPxfxxxn，其中在01,,,,nxxxx所界定的范围内。针对以上例题的线性插值，有11151151151001151212!fPf函数fx在[100,115]区间绝对值的极大值为41002.510f，则有：11151150.011250.05Pf于是近似值111511510.71428571428572fP有三位有效数字。针对以上例题的抛物线插值，有21151151151001151211151443!fPf函数fx在[100,115]区间绝对值的极大值为61003.7510f，则有21151150.001631250.005Pf于是近似值2115115fP10.72275550536420有四位有效数字。8.拉格朗日插值公式的优点公式有较强的规律性，容易编写程序利用计算机进行数值计算。9.拉格朗日插值通用程序程序流程图如下：开始输入nx[i],y[i],（i=0,1,n）t（即插值点x）p＝0，k＝0k=nl＝1，j＝0jkl＝l*(t-x[j])/(x[k]-x[j])j=j+1j＝nl＝l*(t-x[j])/(x[k]-x[j])j=j+1j=k+1p=p+l*y[k]k=k+1输出p结束yyyynnn开始输入nx[i],y[i],（i=0,1,n）t（即插值点x）p＝0，k＝0k=n计算l(k)p=p+l*y[k]k=k+1输出p结束yynl＝1，j＝0jkl＝l*(t-x[j])/(x[k]-x[j])j=j+1j＝nl＝l*(t-x[j])/(x[k]-x[j])j=j+1j=k+1yynn文件lagrange.m如下：%拉格朗日插值closealln=input('已知的坐标点数n=?');x=input('x1,x2,...,xn=?');y=input('y1,y2,...,yn=?');xx=input('插值点=？');symst%定义t为符号量p=0;fork=1:nl=1;forj=1:k-1l=l*(t-x(j))/(x(k)-x(j));endforj=k+1:nl=l*(t-x(j))/(x(k)-x(j));endp=p+l*y(k);endp=inline(p);%把符号算式p变为函数形式fplot(p,[min(min(x),xx)-1,max(max(x),xx)+1]);%画多项式函数holdonp(xx)%显示插值点plot(x,y,'o',xx,p(xx),'*');%画已知点和插值点在MATLAB命令窗口输入：lagrange然后有以下对话过程和结果，已知的坐标点数n=?6x1,x2,...,xn=?[1,3,5,7,9,11]y1,y2,...,yn=?[-1,20,0,-1,12,3]插值点=？8ans=5.67187500000000有以下图形：二．牛顿插值拉格朗日插值的缺点：无承袭性（继承性）若算出3点的抛物插值精度不够，再进行4点的3次多项式插值时，必须从头算起，前面算出的3点抛物插值的计算结果不能利用。而泰勒插值却是具有承袭性的，如线性插值的结果不精确，那么再加上一项，就变成了泰勒抛物插值，如：泰勒1次插值：1000Pxfxfxxx泰勒2次插值：20200002!fxPxfxfxxxxx。而牛顿插值就是具有承袭性的插值公式1.差商的概念设n+1个点01,,,nxxx互不相等，则定义：ix和jxij两点的一阶差商为：,ijijijfxfxfxxxxix,,jkxx三点的二阶差商为：,,,,ijjkijkikfxxfxxfxxxxxix,,,jklxxx四点的三阶差商为：,,,,,,,ijkjklijklilfxxxfxxxfxxxxxx……n+1个点01,,,nxxx的n阶差商为：01112010,,,,,,,,,nnnnfxxxfxxxfxxxxx差商具有对称性：,,ijjifxxfxx；,,,,ijkjikfxxxfxxx2.牛顿插值解决的问题与拉格朗日插值解决的问题相同只是表述n次多项式nPx的公式不同。3.牛顿插公式的推导根据差商的概念，有：000,fxfxfxxxx…………………0,fxx是0,xx两点的一阶差商；001011,,,,fxxfxxfxxxxx……01,,fxxx是01,,xxx三点的二阶差商；……010101,,,,,,,,,,nnnnfxxxfxxxfxxxxxx把以上各式从后向前逐次代入，可以得到：001001201010110101,,,,,,,,,,nnnnfxfxfxxxxfxxxxxxxfxxxxxxxxxfxxxxxxxxxxnnfxPxRx其中00100120101011,,,,,,nnnPxfxfxxxxfxxxxxxxfxxxxxxxxx0101,,,,nnnRxfxxxxxxxxxx以上nPx的表达式称为牛顿插值公式，可以证明，n次牛顿插值多项式与n次拉格朗日插值多项式完全相同，只是表达形式不同。故，拉格朗日余项定理与牛顿余项定理相同：10100,,,,1!nnnnnnkkkkfRxPxfxfxxxxxxxxn，其中在01,,,,nxxxx所界定的范围内。则有公式：101,,,,1!nnffxxxxn4.牛顿插值差商表xiyi一阶差商二阶差商n阶差商*x0y01x1y1f[x0,x1](x-x0)x2y2f[x1,x2]f[x0,x1,x2](x-x0)(x-x1)x3y3f[x2,x3]f[x1,x2,x3](x-x0)…(x-x2)……xn-1yn-1xnynf[xn-1,xn]f[xn-2,xn-1,xn]…f[x0,…,xn](x-x0)…(x-xn-1)5.举例已知函数f(x)当x=-2,-1,0,1,2时，其对应函数值为f(x)=13,-8,-1,4,1。求f(0.5)的值。解：该题目与例1相比，就是多了一个点，所以和例1的差商表相比，只需多一列，多一行：xiyi一阶差商二阶差商三阶差商四阶差商*-2131-1-8-21(x+2)0-1714(x+2)