如果你上过研究生的数值分析课程的话，对这个算法应该不会很陌生。从这节开始，我们将逐一回顾各种插值和拟合方法以及使用Matlab来实现这些算法：

1.拉格朗日插值

1.1插值多项式

用多项式作为研究插值的工具，称为代数插值。其基本问题是：已知函数 $f(x)$ 在区间 $[a, b]$ 上 $n+1$ 个不同点 $x_{0}, x_{1}, \cdots, x_{n}$ 处的函数值 $y_{i}=f\left(x_{i}\right)(i=0,1, \cdots, n)$ ，求一个至多 $n$ 次多项式：
$\varphi_{n}(x)=a_{0}+a_{1} x+\cdots+a_{n} x^{n}（1）$
使其在给定点处与 $f(x)$ 同值，即满足插值条件：
$\varphi_{n}\left(x_{i}\right)=f\left(x_{i}\right)=y_{i} \quad(i=0,1, \cdots, n)（2）$

$\varphi_{n}(x)$ 称为插值多项式， $x_{i}(i=0,1, \cdots, n)$ 称为插值节点，简称节点， $[a, b]$ 称为插值区间。从几何上看， $n$ 次多项式插值就是过 $n+1$ 个点 $\left(x_{i}, f\left(x_{i}\right)\right)(i=0,1, \cdots, n)$ ，作一条多项式曲线 $y=\varphi_{n}(x)$ 近似曲线 $y=f(x)$ 。

$n$ 次多项式（1）有 $n+1$ 个待定系数，由插值条件（2）恰好给出 $n+1$ 个方程：
$\left\{\begin{array}{l}{a_{0}+a_{1} x_{0}+a_{2} x_{0}^{2}+\cdots+a_{n} x_{0}^{n}=y_{0}} \\ {a_{0}+a_{1} x_{1}+a_{2} x_{1}^{2}+\cdots+a_{n} x_{1}^{n}=y_{1}} \\ {\ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots} \\ {a_{0}+a_{1} x_{n}+a_{2} x_{n}^{2}+\cdots+a_{n} x_{n}^{n}=y_{n}}\end{array}\right.（3）$

记此方程组的系数矩阵为 $A$ ，则：
$\operatorname{det}(A)=\left|\begin{array}{ccccc}{1} & {x_{0}} & {x_{0}^{2}} & {\cdots} & {x_{0}^{n}} \\ {1} & {x_{1}} & {x_{1}^{2}} & {\cdots} & {x_{1}^{n}} \\ {} & {\cdots} & {\cdots} & {\cdots} & {\cdots} \\ {1} & {x_{n}} & {x_{n}^{2}} & {\cdots} & {x_{n}^{n}}\end{array}\right|$

称为范德蒙特行列式。当 $x_{0}, x_{1}, \cdots, x_{n}$ 互不相同时，此行列式值不为零。因此方程组（3）有唯一解。这表明，只要 $n+1$ 个节点互不相同，满足插值要求（2）的
插值多项式（1）是唯一的。

插值多项式与被插函数之间的差：
$R_{n}(x)=f(x)-\varphi_{n}(x)$

称为截断误差，又称为插值余项。当 $f(x)$ 充分光滑时，
$R_{n}(x)=f(x)-L_{n}(x)=\frac{f^{(n+1)}(\xi)}{(n+1) !} \omega_{n+1}(x), \xi \in(a, b)$
其中，
$\omega_{n+1}(x)=\prod_{j=0}^{n}\left(x-x_{j}\right)$

1.2.拉格朗日插值多项式

实际上比较方便的作法不是解方程（3）求待定系数，而是先构造一组基函数：
$\begin{aligned} l_{i}(x) &=\frac{\left(x-x_{0}\right) \cdots\left(x-x_{i-1}\right)\left(x-x_{i+1}\right) \cdots\left(x-x_{n}\right)}{\left(x_{i}-x_{0}\right) \cdots\left(x_{i}-x_{i-1}\right)\left(x_{i}-x_{i+1}\right) \cdots\left(x_{i}-x_{n}\right)} \\ &=\prod_{j=0 \atop j \neq i}^{n} \frac{x-x_{j}}{x_{i}-x_{j}}, \quad(i=0,1, \cdots, n) \end{aligned}$
$l_{i}(x)$ 是 $n$ 次多项式，满足：
$l_{i}\left(x_{j}\right)=\left\{\begin{array}{ll}{0} & {j \neq i} \\ {1} & {j=i}\end{array}\right.$
令：
$L_{n}(x)=\sum_{i=0}^{n} y_{i} l_{i}(x)=\sum_{i=0}^{n} y_{i}\left(\prod_{j=0 \atop j \neq i}^{n} \frac{x-x_{j}}{x_{i}-x_{j}}\right)（4）$

上式称为 $n$ 次 $Lagrange$ 插值多项式，由方程（3）解的唯一性， $n+1$ 个节点的 $n$ 次 $Lagrange$ 插值多项式存在唯一。

1.3.用Matlab作Lagrange插值

Matlab中没有现成的 $Lagrange$ 插值函数，必须编写一个M文件实现 $Lagrange$ 插值。

设 $n$ 个节点数据以数组 $x 0, y 0$ 输入（注意 Matlab 的数组下标从 1 开始）， $m$ 个插值点以数组 $x$ 输入，输出数组 $y$ 为 $m$ 个插值。编写一个名为lagrange.m的M文件：

function y=lagrange(x0,y0,x);
n=length(x0);m=length(x);
for i=1:m
    z=x(i);
    s=0.0;
    for k=1:n
        p=1.0;
        for j=1:n
            if j~=k
                p=p*(z-x0(j))/(x0(k)-x0(j));
            end
        end
        s=p*y0(k)+s;
    end
y(i)=s;
end

【数学建模算法】(23)插值和拟合：拉格朗日插值

【数学建模算法】(23)插值和拟合：拉格朗日插值

1.拉格朗日插值

1.1插值多项式

1.2.拉格朗日插值多项式

1.3.用Matlab作Lagrange插值

推荐阅读更多精彩内容