[科普中国]-多项式插值-

定义

给定n+1个点（称为插值点），所谓多项式插值就是找到一个多项式（称为插值多项式）

使得它满足条件

其中，i=0,1,...,n。也就是说，多项式y=P(x)的图像要经过给定的n+1个点。

在实际应用中，这些插值点可能来自某次实验测量所得的数据，也可能来自某个复杂函数的值。通过计算插值多项式，我们可以找到这些实验数据间的规律，或者使用简单的多项式函数来近似复杂的函数。1

存在唯一性和误差

定理一：

给定n+1个点 ,若两两不同，则存在唯一一个次数不超过n的多项式，使得成立。

证明：利用范德蒙德矩阵和代数学基本定理即得。

当的值来自某个函数，且f(x)具有n+1阶连续导数时，下面的定理可以用来计算多项式插值的（截断）误差。

定理二：

给定n+1个点 ,其中，进一步假设函数f(x)具有n+1阶连续导数，则插值多项式P(x)的误差R(x)为

其中，

计算方法

给定n+1个点, 计算插值多项式的主要方法有：直接法、拉格朗日多项式插值和牛顿多项式插值。下面我们分别介绍这三种方法。

（注意，根据定理一，这三种方法得到的插值多项式在理论上说应该是一致的，而且误差也相同。）

直接法

根据定理一，假设插值多项式为

由插值条件，我们得到关于系数 , ,…, , 的线性方程组

通过求解这个线性方程组，即得到插值多项式。

优点：直接，性质一目了然。

缺点：待求解的线性方程组的系数矩阵为范德蒙德(Vandermonde)矩阵，它是一个病态矩阵，这使得在实际求解方程组时将产生很大的误差。

拉格朗日多项式插值

拉格朗日(Lagrange)多项式插值的原理是：先构造一组拉格朗日基函数，这些基函数为次数不超过n的多项式，且具有性质

然后将这些基函数做线性组合，得到拉格朗日插值多项式

容易验证，多项式L(x)满足插值条件

拉格朗日基函数的构造如下：

由基函数的性质，当时，，即为的零点，可以假设

其中，K为待定系数。再由，得到

从而得到

因此，基函数

令，则还可以表示为

下面的定理说明称为基函数的原因：

定理三：令为全体次数不超过n的多项式构成的集合，则是线性空间的一组基。

Matlab 实现

function [y,Lb] = LagrangeInterpolation(X,Y,x)% 拉格朗日多项式插值函数% 注意：插值点的个数为n，差值多项式的次数为n-1%% 输入参数% X,Y: 插值点坐标% x: 求值点%% 输出参数% y: 拉格朗日插值多项式在x点的值% Lb: 拉格朗日基函数在x点的值if length(X) ~= length(Y) error('X和Y的长度不相等'); endn = length(X); %获取插值点的个数 %初始化 y = 0; Lb = ones(1,n); for i = 1:n for j = 1:n %计算拉格朗日基函数在x点的值 if j ~= i Lb(i) = Lb(i) * (x-X(j))/(X(i)-X(j)); end end y = y + Lb(i)*Y(i); %计算拉格朗日插值多项式的值 endend均差与牛顿多项式插值

牛顿多项式插值是基于均差的计算。首先定义均差如下：

函数f(x)关于点的一阶均差（或差商）为

一阶均差反映了函数在区间的平均变化率

用递归的方式，我们定义二阶均差为

同理，k阶均差为

特别地，0阶均差定义为。

根据均差的定义，构造均差表如下：

如果将x也看作一个点，由均差的定义可以得到

其中，

称为牛顿插值多项式。

为插值余项。

由定理一和定理二得到均差和导数的关系如下：

其中，

Matlab实现

function [y,Nt]=NewtonInterpolation(X,Y,x)% 牛顿多项式插值函数% 注意：插值点的个数为n，差值多项式的次数为n-1%% 输入参数% X,Y: 插值点坐标% x: 求值点%% 输出参数% y：牛顿差值多项式在x点的值% Nt：均差表if length(X) ~= length(Y) error('X和Y的长度不相等'); endn = length(X); Nt = zeros(n); %初始化均差表，按列存放各阶均差 Nt(1,1) = Y(1); %0阶均差 for i = 2:n %按行计算均差表 Nt(i,1) = Y(i); %0阶均差 for j = 2:i Nt(i,j) = (Nt(i,j-1)-Nt(i-1,j-1))/(X(i)-X(i-j+1)); end end %计算牛顿插值多项式在x点上的值w = 1; y = Nt(1,1) * w; for i = 2 : n w = w * (x - X(i-1)); y = y + Nt(i,i) * w; end end比较

拉格朗日多项式插值的计算量大于牛顿多项式插值的计算量。

特别地，当新增一个插值点时，拉格朗日插值需要重新计算全部的基函数，而牛顿插值只需计算均差表中新的一行的值即可。