c++实现牛顿插值法实验报告

1、数值实验用Newton商差公式进行插值姓名：陈辉学号：13349006院系：数据科学与计算机学院专业：计算机科学与技术班级：计科一班日期：2015-10-11指导老师：纪庆革- 2 -目录一、实验目的3二、实验题目3三、实验原理与基础理论3四、实验内容6五、实验结果10六、心得体会14七、参考资料14八、附录（源代码）14- 19 -一、 实验目的编写一个程序，用牛顿差商公式进行插值。二、 实验题目编写一个程序，用牛顿差商公式进行插值。三、 实验原理与基础理论牛顿插值公式为：Nnx=fx0+fx0,x1x-x0+fx0,xnx-x0(x-xn-1)其中，fx0,x1=fx1-f(x0)x1-x

2、0fx0,xk=fx1,xk-fx0,xkxk-x0我们将从键盘读入n阶牛顿插值的n+1个节点xi, fi,i=0,1,n，以此得出牛顿插值多项式。有了节点，我们只需要求fx0,xk即可。我们记fxm,xm-1,xm-k为tmk，则tmk在差商表表的位置为(m, k)：m k012n0f(x0)2f(x1)fx1,x03f(x2)fx2,x1fx2,x1,x0nf(xn)fxn,xn-1fxn,xn-1,xn-2fxn,x0由fx0,xk的公式可得tmk = (tmk-1 - tm-1k-1) / (xi xi-j)，直观上来看，表中的某格的差商值可由其左边和左上边的值求得，从而牛顿插值多项式

3、变为N(x) = t00 + t11(x-x0) + + tnn(x-x0)(x-xn-1)做到这一步，我们已经可以通过上面的数据计算对于给出的x，f(x)的近似值。为了更规范地表示，下面我把N(x)变换成标准的降幂多项式N(x) = anxn + an-1x(n-1) + + a2x2 + a1x + a0。为了便于运算，不妨先把x-xi中的减号换成加号（在最后令yi=-xi，在令xi=yi，仍可以得到原本的结果），那么有：x+x0x+x1x+xm-1=xm+xm-1i=0m-1xi+xm-20i0i1m-1xi0xi1+x00i0im-1m-1xi0xi1xim-1为了便于表示，把0i0i

4、km-1xi0xi1xik-1记为mxk那么x+x0x+x1x+xm-1=xm+xm-1mx1+x0mxm只要把N(x)中的每一项展开然后x次数相同的系数相加就可以得到数组a。于是可以列出下表：x0x1xkxn-1xnt010000t11x11000t22x12x1000tkn-kxn-kn-kxn-k-110tn-1n-1xn-1n-1xn-2n-1xn-k-110tnnxnnxn-1nxn-knx11表中xi列的和就是N(x)中ai的值，下面就来求这个和，记cgh=0i0ihg-1xi0xih-1=gxhcgh的意义为g个数中所有h个数乘积之和，可以由g-1个数中所有h-1个数乘积之和，和

5、g-1个数中所有h个数乘积之和求得，递推公式为cgh=cg-1h-1xih+cg-1h。由cgh的意义可以得到递推的边界状态为ci0=x0+xi，cii=x0xi。于是我们又可以得到一张数组c的表（初始状态）：i j01kn0x01x0+x1x0x1kt=1kxtt=1kxtnt=1nxtt=1nxt表的左下角每个空格都可以由其上面的和左上边的格中的值求出。这样，所需要求的所有值都已经得到，只需要通过简单的循环结构就可以算出数组a，从而得到一个降幂的多项式。四、 实验内容实验环境：Mac OS X Yosemite，Sublime Text 2，Xcode，CMD实验步骤：我用一个类封装牛顿插

6、值算法：NewtonInterpolation()为类的初始化：Interpolation()类似于类中的主函数，依此调用下面其他的函数：Input()从键盘读入插值多项式的次数和节点，xi和fi为节点，yi和ti将会在后面解释，这里对其进行初始化：MakeTable()用差商表中tmk的递推式求出数组t所有的元素，这里的t已经在Input()中进行过初始化：DivideDifference()为求值公式：PrintTable()输出fx0,x1到fx0,xn的值：Calculate()计算第二部分中最后一张表c数组的值，其中y中的元素等于x中对应元素的相反数，这步操作已在Input()中完成

7、：MakeFormula()运用第二部分中的第二张表，每列累加计算出标准降幂多项式中的系数数组a，并输出到屏幕上：Formula()显示提示并从键盘读入x，然后用整理后的插值多项式计算对应的近似值f(x)：程序主函数很简单，创建类并调用函数：由于我是在苹果系统下完成这个实验，生成的可执行文件只能在Mac系统下打开，所以最后我在win虚拟机中编译了一个win下的可执行文件。五、 实验结果第一组：我用练习第一题中的主句进行检验。提示输入多项式次数：提示输入节点：计算出fx0,x1到fx0,xn的值，和将此多项式的系数并显示，这个结果和我手算得结果一致，然后提示输入x：输入x之后计算出f(x)的近似

8、值，然后程序结束：第二组：第一组是二阶的牛顿插值多项式，第二组我用练习题中第五题来测试，这题有五个节点，是四阶牛顿插值多项式。运行结果如下，和我手算得结果一致：六、 心得体会在完成这个程序之前，我进行了大量的计算，特别是把插值形式的式子整理成降幂的多项式那几个步骤。最后编写完成的时候发现结果怎么也不正确，然后我调试后发现是一个列表的行和列弄反了，改正这个错误之后就正确了。在做这个实验的过程中，我对很多数学的方法有了新的领会和心得，对word中插入公式的操作也熟悉了很多。完成程序后我在百度和谷歌上搜索了一下，还没有一个搜索结果是可以把多项式整理为降幂排列的。七、 参考资料数值方法（C+描述），P

9、ALLAB GHOSH 著，徐士良 译，清华大学出版社八、 附录（源代码）/ main.cpp/ NewtonInterpolation/ Created by 陈辉 on 2015/10/11./ Copyright (c) 2015年 CHANFai. All rights reserved./#include <iostream>#include <cmath>using namespace std;class NewtonInterpolationprivate: int n; double x20, f20, a20, c2020, y20; double t

10、2020; / Divided Difference Tablepublic: NewtonInterpolation(); void Interpolation(); void Input(); void MakeTable(); double DividedDifference(double f1, double f0, double x1, double x0); void PrintTable(); void Calculate(); void MakeFormula(); void Formula();NewtonInterpolation:NewtonInterpolation()

11、 memset(x, 0, sizeof x); memset(f, 0, sizeof f); memset(a, 0, sizeof a); memset(c, 0, sizeof c); memset(t, 0, sizeof t);void NewtonInterpolation:Interpolation() Input(); MakeTable(); PrintTable(); Calculate(); MakeFormula(); Formula();void NewtonInterpolation:Input() cout << "Input the de

12、gree of Newton Interpolation: " << endl; cin >> n; cout << "Input " << n+1 << " points: x f(x)" << endl; for (int i = 0; i <= n; i +) cin >> xi >> fi; yi = -xi; ti0 = fi; cout << endl;void NewtonInterpolation:MakeTable

13、() for (int i = 1; i <= n; i +) for (int j = 1; j <= n; j +) if (j > i) continue; tij = DividedDifference(tij-1, ti-1j-1, xi, xi-j); double NewtonInterpolation:DividedDifference(double f1, double f0, double x1, double x0) double ans = (f1-f0) / (x1-x0); return ans;void NewtonInterpolation:P

14、rintTable() for (int i = 1; i <= n; i +) cout << "fx0" for (int j = 1; j <= i; j +) cout << ",x" << j; cout << " = " << tii << endl; cout << "N(x) = f(x0) + fx0,x1(x-x0) + . + fx0,.,xn(x-x0).(x-x.n-1)" << e

15、ndl;void NewtonInterpolation:Calculate() c00 = y0; for (int i = 1; i <= n; i +) ci0 = ci-10 + yi; for (int i = 1; i <= n; i +) cii = ci-1i-1 * yi; for (int j = 1; j <= n-1; j +) for (int i = j+1; i <= n; i +) cij = ci-1j-1*yi + ci-1j;void NewtonInterpolation:MakeFormula() for (int j = 0;

16、 j <= n; j +) for (int i = j; i <= n; i +) if (i = j) aj = aj + tii; else aj = aj + tii*ci-1i-j-1; cout << "N(x) = " for (int i = n; i >= 0; i -) cout << ai; if (i != 0) cout << "x" << i << " + " cout << endl; cout << endl;void NewtonInterpolation:Formula() double X, ans = 0; cout << "Input x = "