计算方法多项式插值方法上机习题报告
（一）问题：
对Runge函数R(x)=1
1+x
，x∈[-5,5]，利用下列条件做插值逼近，并与R(x)的图像进行比较.
（1）用等距节点x i= -5 + i, i=0, 1, 2,…,10，绘出它的10次Newton插值多项式的图像；
（2）用节点x i= 5cos(2i+1
42
π), i=0, 1, 2,…,20，绘出它的20次Lagrange插值多项式的图像；
（3）用等距节点x i= -5 + i, i=0, 1, 2,…,10，绘出它的分段线性插值函数图像；
（4）用等距节点x i= -5 + i, i=0, 1, 2,…,10，绘出它的分段三次Hermite插值函数的图像；
（5）用等距节点x i= -5 + i, i=0, 1, 2,…,10，绘出它的三次自然样条插值函数的图像。
（二）解决问题的算法
由于问题中已经明确了被插函数（Runge函数）及所用的插值方法，所以下面简单介绍一下各插值方法。
（1）Newton插值方法
对于被插函数，选取插值点(x1,f x1),…,(x n,f(x n)).
定义k阶插商(k≥1)为：
f x i,x i+1,…,x i+k=f x i+1,x i+2,…,x i+k−f x i,x i+1,…,x i+k−1
i+k i
.
此外，规定f(x)在节点x j上的0阶插商为f[x j]=f(x j).
定义函数：
ωn (x)=(x-x0)(x-x1)…(x-x n).
则牛顿插值多项式为：
N n(x)=f[x0]+f[x0,x1]ω0 (x)+…+f[x0,x1,…,x n]ωn-1 (x).
在具体的计算机实现过程中，可以使用一个二维数组，使得角标为（i, j）(i≤j+1)的位置存储f[x i-1,…,x j]，从而得到牛顿插值多项式.
（2）Lagrange插值方法
对于被插函数，选取n+1个插值节点并求出其函数值：(x0,f x0),…,(x n,f(x n)).
定义：
l i x=
x−x0…x−x i−1x−x i+1……(x−x n) x i−x0…x i−x i−1x i−x i+1……(x i−x n)
.
则拉格朗日插值多项式为：
p(x)=f x i∗l i(x)
n
i=1
（3）分段线性插值方法
过被插函数上若干点（即插值点）做一条折线以近似一条曲线，就可以得到使用分段线性插值方法得到的插值曲线。
其实现方式最为简单，不做过多介绍（即具体的函数形式不在此列出）.
（4）分段三次Hermite插值方法
设选取n+1个插值节点：x0,x1,…,x n，记被插函数f(x)在这些点的函数值与导数值
分别为y i,m i. 定义：
α0x=αL x;x0,x1,xϵx0,x1, 0, xϵx1,x n,
β0x=βL x;x0,x1,xϵx0,x1, 0, xϵx1,x n,
αi x αR x;x i−1,x i,xϵx i−1,x i,
αL x;x i,x i+1,xϵx i,x i+1,
0, x∉x i−1,x i+1,
1≤i≤n−1
βi x
βR x;x i−1,x i,xϵx i−1,x i,
βL x;x i,x i+1,xϵx i,x i+1,
0, x∉x i−1,x i+1,
1≤i≤n−1αn x=
0, xϵ[x0,x n−1]
αR x;x n−1,x n,xϵ[x n−1,x n]
βn x=
0, xϵ[x0,x n−1]
βR x;x n−1,x n,xϵ[x n−1,x n]
其中：
αL x;a,b=1+2x−a
b−a
x−b
a−b
2
,
αR x;a,b=1+2x−a
a−b
x−a
b−a
2
,
βL x;a,b=x−a x−b2
,
βR x;a,b=x−b x−a2
.
则分段三次多项式可写为：
Hℎx= y iαi x+m iβi x.
n
i=0
使用三次Hermite插值方法，可以克服线性插值函数不光滑的缺点。
（5）三次自然样条插值方法
设选取n+1个插值节点：x0,x1,…,x n，记被插函数f(x)在这些点的函数值与导数值分别为y i,m i.（注：此时m i为未知量）设ℎi=x i+1−x i.
设:
λ0=1,λi=
ℎi−1
i−1i
,λn=0
μ0=3(y1−y0)
ℎ0
,μi=3
1−λi
ℎi−1
y i−y i−1+
λi
ℎi
y i+1−y i,μn=
3(y n−y n−1)
ℎn−1
在自然边界条件下，可以得到关于m i的封闭的线性代数方程组：
2λ00 1−λ12λ1⋯00
00
⋮⋱⋮
00 00⋯
1−λn−12λn−1
01−λn2
m0
m1
m2
⋮
m n−1
m n
=
μ0
μ1
μ2
⋮
μn−1
μn
这个方程组可以用追赶法快速求解，从而求出m i.
利用分段三次Hermite函数插值的基函数αi x和βi x，可以得到样条插值法得到
的插值多项式：
n
Sℎx= y iαi x+m iβi x.
i=0
三次样条插值也是一种分段三次多项式插值，它在每个插值节点处比分段三次
Hermite插值函数更光滑，具有二阶连续导数，而且不需要被插函数f(x)在节点的
导数的信息。
（三）使用的软件
IDL
（四）数值结果
（1）10次Newton插值多项式的图像（等距节点x i= -5 + i, i=0, 1, 2,…,10）与R(x)函数图像的比较
π), i=0, 1, 2,…,20）与R(x)（2）20次Lagrange插值多项式的图像（节点x i= 5cos(2i+1
42
函数图像的比较
（3）分段线性插值函数图像（等距节点x i= -5 + i, i=0, 1, 2,…,10）与R(x)函数图像的比较
（4）分段三次Hermite插值函数的图像（等距节点x i= -5 + i, i=0, 1, 2,…,10）与R(x)函数图像的比较
（5）三次自然样条插值函数（等距节点x i= -5 + i, i=0, 1, 2,…,10）与R(x)函数图像的比较
（五）数值结果分析
1、使用等距节点对Runge函数进行Newton插值，随着插值节点的增多，生成的插值函数L n(x)在[-5, 5]区间的两端点附近偏差迅速增大；而且因为多项式次数较高（10次），函数的稳定性也很差。
2、与使用等距节点对Runge函数进行Newton插值生成的插值函数L n(x)（下图左）与被插函数的最大偏差相比，使用非等距节点对Runge函数进行Lagrange插值生成的插值函数R n(x)（下图右）与被插函数的最大偏差要小很多！考虑到在插值节点相同时，L n(x)≈R n(x)；而在本例中R n(x)是20次多项式，L n(x)只是10次多项式。
由此可见：插值点的选取是否得当对插值多项式的逼近效果好坏有很大的影响。
等距插值节点的newton 插值与非等距插值节点的Lagrange 插值比较图
3、为了避免Runge 现象，使用分段低阶多项式确实是一项很有利的手段。
随着插值节点的增多，分段线性插值函数和相对误差将会越来越小，不过分段线性插值函数的缺点之一是函数不够连续。
4、使用两点三次Hermite 插值方法得到的曲线、三次自然样条插值函数得到的曲线与原函数曲线几乎重合，可见其插值效果的优良性。
图中三次自然样条插值函数的误差较两点三次Hermite 插值方法稍稍大一些的可能原因有：三次自然样条插值时解矩阵方程会引入更大的误差；选取的插值节点比较少。