数值分析报告.doc

实验报告

一、对列表函数的计算
【开发语言及实现平台或实验环境】
C++/C#

1.实验目的
（1）掌握拉格郎日插值多项式的用法，适用范围及精确度。
（2）掌握牛顿插值多项式的用法，适用范围及精确度。
（3）掌握埃特金插值多项式的用法，适用范围及精确度。
2.算法思想
(1)拉格朗日插值算法
已知函数y=f(x)在n+1个不同的点x0,x1,…,x2上的函数值分别为y0,y1,…,yn,求一个次数不超过n的多项式Pn(x),使其满足:
Pn(xi)=yi,(i=0,1,…,n),
即n+1个不同的点可以唯一决定一个n次多项式。
①插值基函数
过n+1个不同的点分别决定n+1个n次插值基函数
l0(x),l1(x),…,ln(X)
每个插值基本多项式li(x)满足：
a.li(x)是n次多项式;
b.li(xi)=1,而在其它n个li(xk)=0,(k≠i)。
由于li(xk)=0,(k≠i),故有因子:
(x-x0)…(x-xi-1)(x-xi+1)…(x-xn)
因其已经是n次多项式，故而仅相差一个常数因子。令:
li(x)=a(x-x0)…(x-xi-1)(x-xi+1)…(x-xn)
由li(xi)=1,可以定出a,进而得到：

②n次拉格朗日型插值多项式Pn(x)
Pn(x)是n+1个n次插值基本多项式l0(x),l1(x),…,ln(X)的线性组合,相应的组合系数是y0,y1,…,yn。即:
Pn(x)=y0l0(x)+y1l1(x)+…+ynln(x),
从而Pn(x)是一个次数不超过n的多项式,且满足
Pn(xi)=yi,(i=0,1,2,…,n).
(2)牛顿插值算法
牛顿插值是基于下面这些的公式：
f[x0,x1,...xk]=(f[x1,...xk]-f[x0,...xk-1])/(xk-x0)
f[x]=f(x)
f(x)=f[x0]+f[x0,x1](x-x0)+f[x0,x1,x2](x-x0)(x-x1)+...f[x0,...xn](x-x0)...(x-xn-1)+Rn(x)
前两个是均差的递推关系式，而后一个就是牛顿插值公式，其中N(x)=f(x)-Rn(x)，即目标多项式，Rn(x)是n阶插值余项，我们就是用N(x)去近似f(x)。
可以构造这样一个均方差表：

xkf(xk)一阶均差二阶均差...
x0f(x0)
x1f(x1)f[x0,x1]
x2f(x2)f[x1,x2]f[x0,x1,x2]
...
如果有n个点插值，表会有(n*n)/2+n个表项，如果直接编程会有O(n*n)的空间复杂度，编程时做个简单的改进，不难发现在这个表中只有部分数据有用，对角线（斜行）它们是目标值，用来表示多项式的，左边的两纵行（实际上只需要x一行）以及最底下的一行，表示当前插值的状态。经过改进后只需要O(n)的空间复杂度。
两个过程：
①新增加一个点时的更新。只须更新最底下一行数据，其递推关系由均差公式给出，最后算出高一队的均差值，需时O(n)
②插入点完成后如何计算多项式在另外给定点的值N(x)。
由牛顿插值公式，最终的表达式为：
N(x)=f[x0]+f[x0,x1](x-x0)+f[x0,x1,x2](x-x0)(x-x1)+...f[x0,...xn](x-x0)...(x-xn-1)
如果直接将它展开，再算实在麻烦，实际上大可不必这样做，还记得多项式求值的秦九韶算法吗？将多项式‘叠’起来，从内层括号往外一层层拨开，n次多项多的计算，只需要做n次乘法，同样的思想，将上式改写成：
N(x)=f[x0]+(x-x0){f[x0,x1]+(x-x1){f[x0,x1,x2]+(x-x2){...{f[x0,...xn-1]+(x-xn-1)f[x0,...xn]}...}
就可以同样简单的计算了，时间复杂度O(n)综合起来的性能：对于n个点的插值，产生多项式的时间复杂度是O(n*n)，最终进行一个点的计算的时间复杂度是O(n)。
(3)埃特金插值算法
埃特金插值又称分段插值。分段插值是将被插值函数逐步多项式化。分段插值的处理过程分两步，将区间分成几个子段，并在每个子段上构造插值多项式装配在一起，作为整个区间的插值函数。在分化的每个节点给出数据，连接相邻节点得一折线，该折线函数可以视作插值问题的解。
举例说明：
例已知列表函数
12340－5－63用Aitken算法求的近似值。
解，用列表方法求解。

故

3.插值算法流程图
（1）拉格朗日插值法

（2）牛顿插值法

（3）埃特金插值法

4.实验内容
X01234F（x）121782257求任意结点x对应的函数值。
5.插值算法代码
#include<stdio.h>
#include