(){}
2
1
()(11),5,10,20:
1252
1()1,(0,1,2,,)()2,(0,1,2,,)()
()2
35,20:1100
(i i i
i n n k k k Newton f x x n x f x x i i n f x n
x
y i n Newton N x S x n x k y f x =
-≤≤=+=-+====-+
= 题目：插值多项式和三次样条插值多项式。

已知对作、计算函数在点处的值；、求插值数据点
的插值多项式和三次样条插值多项式；、对计算和相应的函数值),()() (1,2,,99)4:()max ()()max
()n k n k n k n k n k n k k
k
N x S x k E N y N x E S y S x ==-=- 和；
、计算，；
解释你所得到的结果。

算法组织:
本题在算法上需要解决的问题主要是：求出第二问中的Newton 插值多项式
)(x N n 和三次样条插值多项式()n S x 。

如此，则第三、四问则迎刃而解。

计算两
种插值多项式的算法如下：
一、求Newton 插值多项式)(x N n ，算法组织如下：
Newton 插值多项式的表达式如下：
)())(()()(110010--⋅⋅⋅--+⋅⋅⋅+-+=n n n x x x x x x c x x c c x N
其中每一项的系数c i 的表达式如下：
1102110)
,,,(),,,(),,,(x x x x x f x x x f x x x f c i i i i i -⋅⋅⋅-⋅⋅⋅=
⋅⋅⋅=-
根据i c 以上公式，计算的步骤如下：
⎪⎪
⎪⎩⎪
⎪⎪
⎨⎧⋅⋅⋅+⋅⋅⋅⋅⋅⋅⋅
⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅----)
,,,,(1)
,,,(),,,,(),(,),,(2)(,),(),(11101111011010n n n n n n n n x x x x f n x x x f x x x f n x x f x x f x f x f x f 、计算、计算、计算、计算 二、求三次样条插值多项式)(x S n ，算法组织如下：
所谓三次样条插值多项式)(x S n 是一种分段函数，它在节点i x 011()n n a x x x x b -=<<⋅⋅⋅<<=分成的每个小区间1[,]i i x x -上是3次多项式，其在此区间上的表达式如下：
2233
1111111()[()()]()()666[,]1,2,,.
i i i i i i i i i i i i i i i i i h x x h x x S x x x M x x M y M y M h h h x x x i n --------=-+-+-+-∈=⋅⋅⋅，
，
因此，只要确定了i M 的值，就确定了整个表达式，i M 的计算方法如下： 令：
11
111111116()6(,,)i i i i i i i i i i i i i i
i i i i i i i h h h h h h y y y y d f x x x h h h h μλμ++++--+++⎧
===-⎪++⎪⎨
--⎪=-=⎪+⎩
， 则i M 满足如下n-1个方程：
1121,2,,1i i i i i i M M M d i n μλ-+++==⋅⋅⋅-，
方程中有n+1个未知量，则令0M 和n M 分别为零，则由上面的方程组可得到
(11)i M i n ≤≤-的值，可得到整个区间上的三次样条插值多项式)(x S n 。

计算结果与结果分析
本题中各问的相应计算结果如下：
1、在n 取不同值时,x i 和对应的f(x i )(亦即下图中的y1)的值如下：
n ＝5时
:
n ＝10时:
n ＝20时:
2、Newton 插值多项式的表达式如下：
)())(()()(110010--⋅⋅⋅--+⋅⋅⋅+-+=n n n x x x x x x c x x c c x N
n ＝5时，其各项系数43210,,,,c c c c c 分别为:
n ＝10时，其各项系数10910,,,,c c c c ⋅⋅⋅⋅⋅⋅分别为:
n ＝20时，其各项系数20,1910,,,c c c c ⋅⋅⋅⋅⋅⋅分别为:
对于三次样条插值多项式)(x S n ，最重要的是求出其M 矩阵的值，其中M 0和
M n 都为0,M 1～M n-1则存储在矩阵M 中： n ＝5时的M 矩阵(M 1～M 4)的值为：
n ＝10时的M 矩阵(M 1～M 9)的值为：
n ＝20时的M 矩阵(M 1～M 19)的值为：
3、不论n 为多少，)(k x f 是不会改变的，其值存储在矩阵yy 中；当n 取不同值的时候，Newton 插值多项式()n k N x 和三次样条插值多项式()n k S x 的值是不同的，为了使整个结果直观，实验的最终结果还用图形进行的重现（本问中所得函数值
)(k x f 、牛顿插值()n k N x 和三次样条插值()n k S x 的结果分别存在数组变量yy 、Nn
和Sn 中）。

当n ＝5时，整个区间中的()n k N x 、()n k S x 以及)(k x f 的值如图所示：
图5-1 5n 时()n k N x 、()n k S x 与原始值)(k x f 的对比图
n ＝20时，整个区间中的()n k N x 和)(k x f 以及()n k S x 和)(k x f 的对比如下面两图所示：
图5-2 20n =时()n k N x 与原始值)(k x f 的对比图
图5-3 20n =时()n k S x 与原始值)(k x f 的对比图
通过对比以上三个图可得到如下结论：
1、随着n 的增大，使用Newton 插值多项式会出现龙格现象（对比图5-1和图5-2中的()n k N x ）。

2、随着n 的增大，三次样条插值多项式)(x S n 将越来越接近被插值的函数（对比图5-1和图5-3中的()n k S x ）。

4、根据第3问中得到的数据可以很容易的得到()n E N 和()n E S ，它们的值如下表所示：
当n ＝20时，使用Newton 插值多项式出现龙格现象，其最大误差达到58.2781，而相应的三次样条插值多项式)(x S n 的最大误差仅为0.00309。

可见，n 越大，Newton 插值越可能偏离被插值函数，而相应的三次样条插值则能更接近于被插值函数。

x=a:(b-a)/n:b; %插值节点 y=f(x);
plot(x,y,'b') %用蓝色线作被插函数图象 hold on
z=a:(b-a)/(2*n):b; n=length(x); for j=2:n for i=n:-1:j
y(i)=(y(i)-y(i-1))/(x(i)-x(i-j+1));%计算差商 end end u=y(n); m=length(z); for j=1:m for i=n-1:-1:1
u=y(i)+u*(z(j)-x(i)); %计算牛顿插值多项式的值 v(j)=u; end u=y(n); end
plot(z,v,'r') %用红色线作牛顿插值多项式图象
hold off
x=a:(b-a)/n:b; %插值节点
y=f(x);
plot(x,y,'b') %用蓝色线作被插函数图象
hold on
z=a:(b-a)/(2*n):b;
n=length(x);
for j=2:n
for i=n:-1:j
y(i)=(y(i)-y(i-1))/(x(i)-x(i-j+1));%计算差商
end
end
u=y(n);
m=length(z);
for j=1:m
for i=n-1:-1:1
u=y(i)+u*(z(j)-x(i)); %计算牛顿插值多项式的值
v(j)=u;
end
u=y(n);
end
plot(z,v,'r') %用红色线作牛顿插值多项式图象
hold off。