牛顿插值法的C语言学习知识实现.doc

.*牛顿插值法的C语言实现摘要：拉格朗日插值法具有明显的对称性，公式中的每一项与所有的插值节点有关。因此，如果需要增加一个插值节点，则拉格朗日插值公式中的每一项都要改变，在有的应用中就显得不太方便。因此，可以利用另外一种差值方法来弥补这种缺陷，就牛顿插值法。本文通过对牛顿插值法的数学分析，主要给出其C语言实现方法。关键字：差商 差分 C语言算法1差商及其牛顿插值公式1.1 差商及其主要性质定义 若已知函数在点处的函数值。则称：为函数在点的阶差商；为函数过点的阶差商；为函数过点的阶差商；以此类推，一般地称为函数过点的阶差商。性质1 阶差商表示为函数值的线性组合。即 性质2 若函数在包含节点的区间上存在阶导数，则阶差商与导数的关系为 1.2 牛顿插值公式通过个互异点上的次数不超过的插值多项式可以表示如下形式： 这种形式的插值多项式称为牛顿插值多项式，一般记为 由牛顿插值多项式可以看出，当增加一个插值点时，当前已有的各项不变，只需要在后面增加一项即可。并且，在牛顿插值公式中，每一项的系数就是各阶差商，比拉格朗日插值公式计算量小，且便于程序设计。根据差商性质2，即就可以将拉格朗日插值公式的余项转化成牛顿插值公式的余项，即 牛顿插值公式余项更具有一般性，它对于列表函数或者导数不存在的情形都适用。2 差分与等距结点插值公式2.1 差分及其主要性质 定义 设函数在等距结点上的函数值为其中，为常熟，称为步长。则 称为函数在处以为步长的一阶向前差分，并简记为；称为函数在处以为步长的一阶向后差分，并简记为称为函数在处以为步长的一阶向中心差分，并简记为性质1 各阶差分可以表示成函数值的线性组合。即 性质2 差商与差分具有如下关系： 2.2 等距结点插值公式2.2.1 牛顿前插公式 其余项公式为 2.2.2 牛顿后插公式 其余项公式为 在用牛顿前插和后插公式计算时候，要涉及到各阶前插和后插计算，下面是各阶向前和向后差分 的计算格式，如下图所示。表1 各阶向前差分和向前差分的计算公式1阶差分2阶差分3阶差分4阶差分用于前插公式用于后插公式3 牛顿差值公式的C程序设计和应用实例3.1 牛顿差值法的应用步骤步骤 首先我们按照表1，求得各点的差商.然后利用牛顿前差或后差公式，把数值带入.即可以求得n次多项式。 它在计算机上的应用步骤如下： 步骤1 输入所要求的牛顿多项式的次数，并依次输入个节点. for : i=0 to n+1scanf("%f",&xi) scanf("%f",&y0i);步骤2 计算各阶差商 for : i=1 to n+1 for : j=i to n+1 if(i>1) yij=(yi-1j-yi-1j-1)/(xj-xj-i); else yij=(yi-1j-yi-1j-1)/(xj-xj-1); 步骤3 代入牛顿插值公式,可计算得出结果。 for：i=1 to n+1 temp=temp*(xx-xi-1); 牛顿=牛顿+yii*temp;3.2 利用牛顿插值法程序的实例为了更方便的应用牛顿插值法，我们进行了与计算机的结合，下面我们将展示几个例子。例2.1 已知的一组数据为xsinx（1） 构造牛顿插值函数并作图分析。（2） 并分别利用程序估计，的估计值。 分析 首先我们可以通过程序求出差商表：一阶差商二阶差商三阶差商四阶差商带入定义1.5中可求得如下牛顿插值多项式如下 (2.1) (2.2) 第二步 利用C+程序计算和的值。步骤如下：利用C程序：首先输入所要求的牛顿多项式的次数n，然后输入n+1个节点的值.即可以得出和的值为0.2586和0.0804；例2.2 设的函数表如下：0.250.300.360.390.450.2231440.2623640.3074850.3293040.371564试计算，分析：同上题步骤我们先求差商表，进而代入公式可得 利用C程序我们可以得到计算结果 ： ，从上述两个例子我们可以看出,多项式在区间周围与原函数逼近的较好。离这个区间越远与原函数的误差越大在处时，该图像就已经开始背离图像了.所以该多项式只能在一个小的区间里可以逼近原函数,不适合作为原函数的逼近函数.也可以看出多项式在区间的周围逼近的较好，但是处时，该图像就离原图像误差较大.多项式在区间0,2.5都逼近的挺好，从图中我们看出在远离这个区间的图像误差相对较大，但是在这三个多项式中是逼近最好的。于是可以得出节点越多，函数逼近的相对较好.在节点附近逼近的越好，越远离节点误差越大，所以公式适用于计算节点附近的值于是为了减小误差，在下一节的等距节点下的插值公式根据所求的点的函数值的不同分别采取了前插和后插公式。3.4等距节点下的牛顿插值算法与程序设计前面我们讲述了一般节点下的牛顿插值公式，为了计算方便于是有了对等距节点下的牛顿多项式的研究，本节将对等距节点下的插值多项式进行总结讨论.3.4.1 等距节点下的牛顿插值法的程序算法步骤步骤先求差分.然后利用牛顿前插公式或牛顿后插公式并把数值带入.即可以求得n次多项式。 它在计算机上的应用步骤如下： 步骤1 输入所要求的牛顿多项式的次数，步长，并依次输入个节点。 for : i=0 to n+1 scanf("%f",&xi) scanf("%f",&y0i);步骤2 求得各界差分for : i=1 to n+1 for : j=i to n+1 yij=(yi-1j+1-yi-1j-1)/(xj-xj); /求向前差分 for : i=1 to n+1 for : j=i to n+1 yij=(yi-1j-yi-1j-1)/(xj-xj-i); /求向后差分步骤3 代入牛顿插值公式,可计算得出结果 for(i=1;i<n+1;i+) temp=temp*(t-i+1)/i); 牛顿=牛顿+yii*temp; printf("求得的结果为:N(%.4f)=%9fn",xx,牛顿); /求得运用前插公式的值for(i=n;i<0;i-) temp=temp*(t-i+1)/i); 牛顿=牛顿+yn-in-i*temp; printf("求得的结果为:N(%.4f)=%9fn",xx,牛顿); /求得运用后插公式的值3.4.2 等距节点下牛顿插值的实例例 已知的值列表如下： 1. 3 1.31 1.32 1.33 3.6021 3.7471 3.9033 4.0723近似计算,。采用牛顿向后插公式.为此，做差分表 1.3 3.6021 0.1450 0.0112 0.0016 1.31 3.7471 0.1562 0.0128 1.32 3.9033 0.1690 1.33 4.0723从而，有将代入上式，得。将带入后插多项式中可以得到现在我们利用C程序 首先输入所求插值的次数3和步长0.01.然后输入各个节点，并输入所要求的点1.325既可以求出该点的函数值。即 。 例 设函数在各节点的取值如下00.20.40.60.81.01.00.8187310.6703200.5488120.4493290.367879试利用插值公式求的值。采用牛顿向前插公式，同上题我们先做差分表，然后相应带入到差分公式.中求得后插公式。利用C语言程序步骤如下:首先输入所求插值的次数5和步长0.2。然后输入各个节点，并输入所要求的点0.3既可以求出该点的函数值。即。由以上例子我们看到例1用了牛顿后插公式，例2用了牛顿前插公式，我们该怎样选取。这个经过验证得出，如果所要求的点较靠近节点，则采用前插公式；如果靠近，则采用牛顿后插公式。4 结束语 用牛顿差值方法处理测量数据，具有使差值多项式通过选定测量值的特点，所以在数据处理中有一定的应用场合。当测量值较多、较密时，为了减轻计算工作量及提高准确性，应选取合适的测量值作为差商计算的依据求得。参考文献1 李庆扬等编.数值分析.华中科技大学出版社,1989 2 储钟武等编译.数值分析.黑龙江科学技术出版社,1987 3 徐士良编.数值分析与算法.机械工业出版社,2007附录A：牛顿插值法的程序#include<stdio.h>Newtonvoid main() float x11,y1111,xx,temp,牛顿; int i,j,n; printf("牛顿插值:n请输入要运算的值:x="); scanf("%f",&xx); printf("请输入插值的次数(n<11):n="); scanf("%d",&n); printf("请输入%d组值:n",n+1); for(i=0;i<n+1;i+) printf("x%d=",i); scanf("%f",&xi); printf("y%d=",i); scanf("%f",&y0i); for(i=1;i<n+1;i+) for(j=i;j<n+1;j+) if(i>1) yij=(yi-1j-yi-1j-1)/(xj-xj-i); else yij=(yi-1j-yi-1j-1)/(xj-xj-1); printf("%fn",yii); temp=1;牛顿=y00; for(i=1;i<n+1;i+) temp=temp*(xx-xi-1); 牛顿=牛顿+yii*temp; printf("求得的结果为:N(%.4f)=%9fn",xx,牛顿); 附录B：等距节点下的前插公式的C语言程序#include<stdio.h>void main() float x11,y1111,xx,temp,牛顿,t,h; int i,j,n; printf("牛顿插值:n请输入要运算的值:x="); scanf("%f",&xx); printf("请输入插值的次数(n<11):n="); scanf("%d",&n);printf("步长:n请输入要运算的值:h="); scanf("%f",&h); printf("请输入%d组值:n",n+1); for(i=0;i<n+1;i+) printf("x%d=",i); scanf("%f",&xi); printf("y%d=",i); scanf("%f",&y0i); t=(xx-x0)/h; for(i=1;i<n+1;i+) for(j=i;j<n+1;j+) yij=(yi-1j+1-yi-1j); printf("%fn",yii); temp=1;牛顿=y00; for(i=1;i<n+1;i+) temp=temp*(t-i+1)/i); 牛顿=牛顿+yii*temp; printf("求得的结果为:N(%.4f)=%9fn",xx,牛顿);附录C：等距节点下的后插公式的C语言程序#include<stdio.h>void main() float x11,y1111,xx,temp,牛顿,t,h; int i,j,n; printf("牛顿插值:n请输入要运算的值:x="); scanf("%f",&xx); printf("请输入插值的次数(n<11):n="); scanf("%d",&n);printf("步长:n请输入要运算的值:h="); scanf("%f",&h); printf("请输入%d组值:n",n+1); for(i=0;i<n+1;i+) printf("x%d=",i); scanf("%f",&xi); printf("y%d=",i); scanf("%f",&y0i); t=(xx-xn-1)/h; for(i=1;i<n+1;i+) for(j=i;j<n+1;j+) yij=(yi-1j-yi-1j-1); printf("%fn",yii); temp=1;牛顿=yn-1n-1; for(i=n;i<0;i-) temp=temp*(t-i+1)/i); 牛顿=牛顿+yn-in-i*temp; printf("求得的结果为:N(%.4f)=%9fn",xx,牛顿);附录D：牛顿插值法的流程图开始输入n分别输入n+1个节点YNYNYi=i+1i=i+1输出n值i>1i<n+1j<n?i=ji<1ni=0NNY