c 实现牛顿插值法实验报告.docx

数值实验
用Newton商差公式进行插值
姓名:陈辉
学号:13349006
院系:数据科学与计算机学院
专业:计算机科学与技术
班级:计科一班
日期:2015-10-11
指导老师:纪庆革
目录
一、 实验目的 3
二、 实验题目 3
三、 实验原理与基础理论 3
四、 实验内容 6
五、 实验结果 10
六、 心得体会 14
七、 参考资料 14
八、 附录(源代码) 14
实验目的
编写一个程序,用牛顿差商公式进行插值。
实验题目
编写一个程序,用牛顿差商公式进行插值。
实验原理与基础理论
牛顿插值公式为:
Nnx=fx0+fx0,x1x-x0+…+fx0,…,xnx-x0…(x-xn-1)
其中,
fx0,x1=fx1-f(x0)x1-x0
fx0,…,xk=fx1,…xk-f[x0,…,xk]xk-x0
我们将从键盘读入n阶牛顿插值的n+1个节点xi, fi,i=0,1,…,n,以此得出牛顿插值多项式。
有了节点,我们只需要求fx0,…,xk即可。
我们记fxm,xm-1,…,xm-k为t[m][k],则t[m][k]在差商表表的位置为(m, k):
m \ k
0
1
2
…
n
0
f(x0)
2
f(x1)
fx1,x0
3
f(x2)
fx2,x1
fx2,x1,x0
…
…
…
…
…
n
f(xn)
fxn,xn-1
fxn,xn-1,xn-2
…
fxn,…,x0
由fx0,…,xk的公式可得t[m][k] = (t[m][k-1] - t[m-1][k-1]) / (x[i] – x[i-j]),直观上来看,表中的某格的差商值可由其左边和左上边的值求得,从而牛顿插值多项式变为N(x) = t[0][0] + t[1][1](x-x[0]) + …+ t[n][n](x-x[0])…(x-x[n-1])
做到这一步,我们已经可以通过上面的数据计算对于给出的x,f(x)的近似值。
为了更规范地表示,下面我把N(x)变换成标准的降幂多项式N(x) = a[n]x^n + a[n-1]x^(n-1) + …+ a[2]x^2 + a[1]x + a[0]。
为了便于运算,不妨先把x-x[i]中的减号换成加号(在最后令y[i]=-x[i],在令x[i]=y[i],仍可以得到原本的结果),那么有:
x+x0x+x1…x+xm-1=xm+xm-1i=0m-1xi+xm-20≤i0≠i1≤m-1xi0xi1+…+x00≤i0≠…≠im-1≤m-1xi0xi1…xim-1
为了便于表示,把
0≤i0≠…≠ik≤m-1xi0xi1…xik-1
记为
mx[k]
那么
x+x0x+x1…x+xm-1=xm+xm-1mx1+…+x0mx[m]
只要把N(x)中的每一项展开然后x次数相同的系数相加就可以得到数组a。于是可以列出下表:
x[0]
x[1]
…
x[k]
…
x[n-1]
x[n]
t[0]
1
0
0
0
0
t[1]
1x[1]
1
0
0
0
t[2]
2x[1]
2x[1]
0
0
0
…
t[k]
n-kx[n-k]
n-kx[n-k-1]
1
0
…
…
…
…
…
t[n-1]
n-1x[n-1]
n-1x[n-2]
…
n-1x[n-k-1]
…
1
0
t[n]
nx[n]
nx[n-1]
…
nx[n-k]
…
nx[1]
1
表中x[i]列的和就是N(x)中a[i]的值,下面就来求这个和,记
cgh=0≤i0≠…≠i[h]≤g-1xi0…xih-1=gx[h]
c[g][h]的意义为g个数中所有h个数乘积之和,可以由g-1个数中所有h-1个数乘积之和,和g-1个数中所有h个数乘积之和求得,递推公式为c[g][h]=c[g-1][h-1]x[i[h]]+c[g-1][h]。由c[g][h]的意义可以得到递推的边界状态为c[i][0]=x[0]+…+x[i],c[i][i]=x[0]…x[i]。
于是我们又可以得到一张数组c的表(初始状态):
i \ j
0
1
…
k
…
n
0
x[0]
1
x[0]+x[1]
x[0]x[1]
…
…
…
k
t=1kx[t]
t=1kx[t]
…
…
n
t=1nx[t]
t=1nx[t]
表的左下角每个空格都可以由其上面的和左上边的格中的值求出。
这样,所需要求的所有值都已经得到,只需要通过简单的循环结构就可以算出数组a,从而得到一个降幂的多项式。
实验内