数值计算方法插值与拟合实验报告
摘要：通过实验介绍插值方法中常见的拉格朗日插值，线性分段插值和牛顿前插公式，分析计算各种方法的插值余项。在曲线拟合方面使用两种不同类型的曲线来拟合同一组数据，并计算残差向量范数，比较不同曲线拟合的效果，在此例上给出优劣的判断。
关键词：拉格朗日插值；线性分段插值；牛顿前插公式；曲线拟合
引言
在工程和科学计算中经常碰到只知道离散的数据测量点而需要匹配其变量之间的数学函数表达式的情况，这就需要插值和拟合的数值方法来解决这些问题。插值法是在离散数据的基础上补插连续函数，使得这条连续曲线通过全部给定的离散数据点，也是离散函数逼近的重要方法，利用它可通过函数在有限点处的取值状况，估算出函数在其他点处的近似值。曲线拟合则是用连续曲线近似地刻画或比拟平面上离散点所表示的坐标之间的函数关系，在各个方面也有着愈加广泛的应用。
1 算法介绍
1.1 拉格朗日插值法 1.1.1 算法理论
对某个多项式函数，已知有给定的k +1个取值点：
00(,),...,(,)k k x y x y
其中i x 对应着自变量的位置，而i y 对应着函数在这个位置的取值。假设任意两个不同的x j 都互不相同，那么应用拉格朗日插值公式所得到的拉格朗日插值多项式为：
():()k
i i j L x y l x ==∑
其中每个()j l x 为拉格朗日基本多项式（或称插值基函数），其表达式为：
1100,011()()()()
():......
()()()()k
j j i k j i i j j i
j j j j j j k x x x x x x x x x x l x x x x x x x x x x x -+=≠-+-----==-----∏
拉格朗日基本多项式 ()j l x 的特点是在 j x 上取值为1，在其它的点 ,i x i
j ≠上取值为0。对
于给定的 1k +个点：00(,),...,(,)k k x y x y ，拉格朗日插值法的思路是找到一个在一点j x 取值为1，而在其他点取值都是0的多项式()j l x 。这样，多项式()i i y l x 在点j x 取值为j y ，而在其
他点取值都是0。而多项式
():()k
i i j L x y l x ==∑
就可以满足
():()00...0k
i i i i j L x y l x y y ===++...+++=∑
在其它点取值为0的多项式容易找到，例如：
011()...()()...()j j k x x x x x x x x -+----
它在点j x 取值为：011()...()()...()j
j j j j j k x x x x x x x x -+----。由于已经假定i
x 两两互不相同，因此上面的取值不等于0。于是，将多项式除以这个取值，就得到一个满足“在
j x 取值为1，而在其他点取值都是0的多项式”：
1100,011()()()()
():......
()()()()k
j j i k j i i j j i
j j j j j j k x x x x x x x x x x l x x x x x x x x x x x -+=≠-+-----==-----∏ 这就
是拉格朗日基本多项式。
拉格朗日插值法的公式结构整齐紧凑，在理论分析中十分方便，然而在计算中，当插值点增加或减少一个时，所对应的基本多项式就需要全部重新计算，于是整个公式都会变化，非常繁琐。此外，当插值点比较多的时候，拉格朗日插值多项式的次数可能会很高，因此具有数值不稳定的特点，也就是说尽管在已知的几个点取到给定的数值，但在附近却会和“实际上”的值之间有很大的偏差。这类现象也被称为龙格现象，解决的办法是分段用较低次数的插值多项式。 1.2.2 算法描述
对于已给定的点 00(,),...,(,)k k x y x y 和待估计的点的横坐标x ，如上述理论，将其值代入
1100,011()()()()
():......()()()()k
j j i k j i i j j i j j j j j j k
x x x x x x x x x x l x x x x x x x x x x x -+=≠-+-----==-----∏
计算出插值基函数的值，然后根据公式：
():()k
i i j L x y l x ==∑
计算出纵坐标的估计值，由此完成对该点的插值过程，其中k 为该点插值的阶数。
1.2 线性分段插值 1.
2.1 算法理论
首先介绍线型插值，假设我们已知坐标 00(,)x y 与 11(,)x y 要得到 01(,)x y 区间内某一位置 x 在直线上的值。根据图中所示，我们得到
由于 x 值已知，所以可以从公式得到 y 的值
已知y 求x 的过程与以上过程相同，只是x 与y 要进行交换。
线性插值经常用于已知函数 f 在两点的值要近似获得其它点数值的方法，这种近似方法的误差定义为：
()()T R f x p x =-
其中 p 表示上面定义的线性插值多项式
100010
()()
()()()f x f x p x f x x x x x -=+--
根据罗尔定理，我们可以证明：如果 f 有二阶连续导数，那么误差范围是
2
"10()||max |()|8
T x x R f x -≤ 01x x x ≤≤
正如所看到的，函数上两点之间的近似随着所近似的函数的二阶导数的增大而逐渐变差。从直观上来看也是这样：函数的曲率越大，简单线性插值近似的误差也越大。
而分段线型插值就是把需要插值的区间依已给定的点 00(,),...,(,)k k x y x y 分为k-1段，每段利用其端点进行线型插值。
