实验名称插值法

探索实验5插值法一、实验目的了解插值问题及其适用的场合，理解并掌握常用的插值算法的构造和计算，了解差商概念、Runge现象及样条插值方法，学习用计算机求近似函数的一些科学计算方法和简单的编程技术。二、概念与结论1.插值问题与插值函数：由实验或测量的方法得到所求函数y=f(x)在互异点x0,x1,...,xn处的值y0,y1,…,yn,构造一个简单函数(x)作为函数y=f(x)的近似表达式y=f(x)(x)使(x0)=y0,(x1)=y1,,(xn)=yn,(1)这类问题称为插值问题。f(x)称为被插值函数，(x)称为插值函数，x0,x1,...,xn称为插值节点。(1)式称为插值条件。常用的插值函数是多项式函数。且当n=1时是称为线性插值，n=2时称为Simpson插值或抛物线插值。2．插值定理：假设x0,x1,…,xn是n+1个互异节点,函数f(x)在这组节点的值f(xk)(k=0,1,…,n)是给定的，那么存在唯一的n次次多项式pn(x)满足pn(xk)=f(xk),k=0,1,…,n3.插值的截断误差设n(x)是过点x0，x1，x2，…xn的n次插值多项式，f(n+1)(x)在（a，b）上存在，其中[a，b]是包含点x0，x1，x2，…,xn的任一区间，则对任意给定的x[a，b]，总存在一点（a，b）（依赖于x）使其中n+1(x)=(x–x0)(x-x1)…(x-xn)，f(n+1)()是f(x)的n+1阶微商在的值。4.差商：给定一个函数表x|x0x1…....xn-----------------------------------------------------------------y|y0,y1…….yn其中当ij时,xixj记f[xi]=f(xi),定义f(x)关于xi,xj的一阶差商一般的,f(x)关于xi,xi+1,…,xi+k的k阶差商定义为:)()!1()()()()(1)1(xnxxfxRnnnnfjijijixxxfxfxxf][][],[5.分段线性插值：在区间[a,b]上给定一组节点:a=x0x1x2xn=b且在节点上的函数值f(xi)=yi,i=0,1,2,,n,如果函数(x)满足：1)(x)在[a,b]上连续2)(xi)=yi,i=0,1,2,,n3)(x)在每个子区间[xi,xi+1](i=0,1,2,,n-1)上是次数为1的多项式则称(x)是定义在[a,b]上的分段线性插值函数。6.m次样条插值函数：设f(x)是区间[a,b]上的一个连续可微函数,在区间[a,b]上给定一组节点:a=x0x1x2xn=b且y=f(x)在点x0，x1，x2,xn的值为y0，y1，y2,yn，如果函数s(x)满足条件(1)s(x)在每个子区间[xi,xi+1](i=0,1,2,,n-1)上是次数不超过m的多项式;(2)s(x)在区间[a,b]上有m-1阶连续导数;(3)s(xi)=f(xi)=yi,i=0,1,2,,n则称s(x)为函数f(x)的在[a,b]上的m次样条插值函数。x0，x1，x2,称为样条结点,其中x1,,xn-1称为内结点,x0,xn称为边界结点。当m=3时,则称s(x)为函数f(x)的三次样条插值函数。三、程序中Mathematica语句解释：1.Product[f(i),{i，imin，imax，h}]计算乘积f(imin)f(imin+h)f(imin+2h)……f(imin+nh)}imax–himin+nhimax,h02．Simplify[expr]对expr进行化简3.Append[list,elem]在表list的后面加一个元素elem4.Prepend[list,elem]在表list的前面加一个元素elem四、方法与程序插值法是函数逼近的重要方法之一,它是求近似函数的一种方法，有着广泛的应用。插值法有很多种,其中以拉格朗日(Lagrange)插值和牛顿(Newton)插值为代表的多项式插值最有特点,常用的插值还有Hermit插值,分段插值和样条插值等。这里只给出Lagrange插值、Newton插值、分段线性插值和样条插值的构造过程及程序。kiikiiikiiikiiixxxxxfxxxfxxxf],,[],,[],,[,211,1,11．Lagrange插值Lagrange插值是将待求的n次多项式插值函数Pn(x)改写成另一种表示方式，再利用插值条件确定其中的待定插值基函数，从而求出插值多项式。Lagrange插值是多项式插值，它成功地用构造插值基函数的方法解决了求多项式插值函数出现的病态问题。1.1Lagrange插值的构造过程：令插值多项式为Ln(x)=l0n(x)y0+l1n(x)y1+l2n(x)y2+…+lnn(x)yn式中l0n(x),l1n(x),l2n(x),…,lnn(x)都是次数n的待定多项式，利用插值条件Pn(x0)=y0,Pn(x1)=y1,......,Pn(xn)=yn可以得到l0n(x0)=1,l1n(x0)=0,l2n(x0)=0,…,lnn(x0)=0l0n(x1)=0,l1n(x1)=1,l2n(x1)=0,…,lnn(x1)=0……...l0n(xn)=0,l1n(xn)=0,l2n(xn)=0,…,lnn(xn)=1考虑函数l0n(x),由其在x1,x2...xn的零值，可以知道它含有x-x1,x-x2,...,x-xnn个因子，于是可令l0n(x)=a(x-x1)(x-x2)...(x-xn)利用l0n(x0)=1确定其中的系数a，得(x-x1)(x-x2)…(x-xn)l0n(x)=-----------------------------(x0-x1)(x0-x2)…(x0-xn)类似的可以得出l1n(x),l2n(x),…,lnn(x)(x-x0)(x-x1)…(x-xi-1)(x-xi+1)…(x-xn)lin(x)=-----------------------------------------------------(xi-x0)(xi-x1)…(xi-xni-1)(xi-xi+1)…(xi-xn)l0n(x),l1n(x),…,lnn(x)称为以x0,x1,...,xn为节点的插值基函数。于是，将这些插值基函数代入前面的多项式Ln(x)即得到如下所求的n次Lagrange插值多项式：1.2求n次Lagrange插值多项式算法：ninijjijijnijniiiiiiiniiniiinnyxxxyxxxxxxxxxxxxxxxylPxLxxxxxxxxn000111011100)())...()()...()(())...()()...()(()()()(1．输入n+1个插值点：(xi,yi),i=0,1,…,n2．计算插值基函数l0n(x),l1n(x),…,lnn(x)3．给出n次Lagrange插值多项式：Ln(x)=y0l0n(x)+y1l1n(x)+…+ynlnn(x)1.3求Lagrange插值多项式程序：Clear[lag,xi,x,yi];xi=Input[xi=]yi=Input[yi=]n=Length[xi]-1;p=Sum[yi[[i]]*(Product[(x-xi[[j]])/(xi[[i]]-xi[[j]]),{j,1,i-1}]*Product[(x-xi[[j]])/(xi[[i]]-xi[[j]]),{j,i+1,n+1}]),{i,1,n+1}];lag[x_]=Simplify[p]说明：本程序用于求n次Lagrange插值多项式。程序执行后，按要求通过键盘输入插值基点xi:{x0,x1,...,xn}和对应函数值yi:{y0,y1,…,yn}后，程序即可给出对应的n次Lagrange插值多项式lag[x]。程序中变量说明：xi：存放插值基点{x0,x1,...,xn}yi:存放对应函数值{y0,y1,…,yn}lag[x]:存放求出的n次Lagrange插值多项式Ln(x)注：语句lag[x_]=Simplify[p]用简化形式给出对应的n次Lagrange插值多项式。1.4例题与实验例1.给定数据表x0123y=f(x)13512用Lagrange插值法求三次插值多项式,并给出函数f(x)在x=1.4的近似值。解：执行Lagrange插值程序后，在输入的两个窗口中按提示分别输入{0,1,2,3}、{1,3,5,12}，每次输入后用鼠标点击窗口的“OK”按扭，得如下插值函数：6+22x-15x2+5x3-----------------------6所以得到三次插值多项式L3(x)=1+11x/3-5x2/2+5x3/6接着键入：lag[1.4]得输出:3.52，因此f(x)在x=1.4的近似值为3.52，即f(1.4)3.52.2.Newton插值Newton插值是多项式插值的另一种表示形式，它在增加插值节点时具有灵活性，只要在原有的插值多项式中增加一项就得到新的插值函数。2.1Newton插值构造过程：为了使插值Newton多项式具有承袭性，令插值函数具有下列形式：式中称为Newton插值基函数。为求出Nn(x),利用插值条件和差商，得出如下n次Newton插值多项式：计算Newton插值多项式Nn(x)常用如下差商表：2.2求Newton插值多项式算法：1.输入n+1个插值点：(xi,yi),i=0,1,…,n2.计算差商表3.给出n次Newton插值多项式。2.3求Newton插值多项式程序：Clear[newt,s,x];)())(()()(110011100nnonnnxxxxxxcxxcccccxN)1()(1)()(,1)(10nixixxxxii)())(](,,[)](,[)()(11000100nnnxxxxxxxxfxxxxfxfxN差商表xyf[xi,xj]f[xi,xj,xk]...f[x0,x1,...,xn]x0y0f[x0,x1]f[x0,x1,x2]...f[x0,x1,...,xn]x1y1f[x1,x2]f[x1,x2,x3]...x2y2f[x2,x3]f[x2,x3,x6]..................xn-1yn-1f[xn-1,xn]xnynxi=Input[xi=]yi=Input[yi=]n=Length[xi];(*计算差商表*)f=Table[0,{n},{n}];Do[f[[i,1]]=yi[[i]],{i,1,n}]Do[f[[i,j+1]]=(f[[i,j]]-f[[i+1,j]])/(xi[[i]]-xi[[i+j]]),{j,1,n-1},{i,1,n-j}]Print[差商表]Do[Print[xi[[i]],,f[[i]]],{i,1,n}](*求Newton插值多项式*)fa=1;s=f[[1,1]];Do[fa=(x-xi[[k]])*fa;s=s+fa*f[[1,k+1]],{k,1,n-1}]newt[x_]=sSimplify[%]说明：本程序用于求n次Newton插值多项式。程序执行后，按要求通过键盘输入插值基点xi:{x0,x1,...,xn}和对应函数值yi:{y0,y1,…,yn}后，程序依次给出输入的数据表、计算出的差商表、Newton插值多项式、Newton插值多项式的简化形式。程序中变量说明：xi：存放插值基点{x0,x1,...,xn}yi:存放对应函数值{y0,y1,…,yn}f:存放函数值{y0,y1,…,yn}及所有差商newt[x]:存放求出的n次newton插值多项式Nn(x)注：1)语句f=Table[