贡献者： ditto; addis
1. 什么是插值
插值法，就是在函数表达式未知的情况下，通过已知点处的函数值来估计未知点处函数值的方法。
定义 1 插值函数
已知函数 $f(x)$ 在 $\left[a,b\right] $ 上有定义，且已经测得在 $x_0,x_1,\dots, x_n$ 处的函数值为
\begin{equation}
y_i = f(x_i) \qquad (i = 1,2, \dots, n)~.
\end{equation}
如果存在一个简单易算的函数 $p(x)$，使得
\begin{equation}
p(x_i) = f(x_i)\qquad (i = 1,2, \dots, n)~,
\end{equation}
则称 $p(x)$ 是 $f(x)$ 的插值函数。
插值法是数值计算中一种常用且基础的方法，在数据挖掘、数学建模等诸多领域都有广泛的应用。
2. 多项式插值
当式 2 中的简单函数 $p(x)$ 是多项式函数时，该插值方法就叫多项式插值，$p(x)$ 被称为插值多项式。当有 $n$ 个插值点时，插值多项式的次数一定小于等于 $n$ 次。
定理 1 插值多项式的唯一性定理
满足上述条件的多项式 $p(x)$ 存在唯一。
证明： 由 Vandermonde 矩阵为非奇异矩阵易证。
由 定理 1 可知，对一组给定的插值点以及对应的函数值，由插值法得到的多项式存在且唯一。因此，下面介绍的两种插值方法只是推导不同，但其最终得到的插值多项式是一致的。
Lagrange 插值
定义 2 Lagrange 基函数
设 $l_k(x)$ 是 $n$ 次多项式，在节点 $x_0, x_1,\cdots,x_n$ 上满足：
\begin{equation}
l_k(x_i) =
\begin{cases}
1\ &(i = k)\\
0 \ &(i \neq k)~,
\end{cases}
\end{equation}
则称 $l_k(x)$ 为节点 $x_0,x_1,\cdots,x_n$ 上的 $n$ 次 Lagrange 插值基函数。
根据定义，由构造法易得：
\begin{equation}
l_k(x) = \frac{(x-x_0)\cdots(x-x_{k-1})(x-x_{k+1})\cdots (x-x_n)}{(x_k-x_0)\cdots(x_k-x_{k-1})(x_k-x_{k+1})\cdots(x_k-x_n)}~.
\end{equation}
已知 Lagrange 基函数，构造插值函数的过程就十分简单了。由于我们已知函数在 $x_0,x_1,\cdots,x_n$ 处的函数值，只要让每一个 $x_i$ 对应的基函数乘上相应的 $f(x_i)$ 再相加，就可以得到最终的插值多项式函数:
\begin{equation}
p(x) = \sum_{i = 0}^n f(x_i)l_i(x) ~.
\end{equation}
Lagrange 插值的 MATLAB 实现
这里以 $y = \frac{1}{1+x^2}$ 在 $[-5,5]$ 的 n 次 Lagrange 插值函数为例展示 Lagrange 插值的具体实现。
function f = LagrangeIP(n)
% [-5,5]内的Lagrange等距点插值，多项式次数为n,插值函数为y = 1./(1+x.*x);
x = -5:0.1:5;
y = 1./(1+x.*x);
x1 = linspace(-5,5,n+1);%插值节点
y1 = 1./(1+x1.*x1);
f = 0;%f为插值形成的函数
for i = 1:n+1
L = 1;%L为插值基函数
for j = 1:n+1
if j~=i
L = L.*(x-x1(j))./(x1(i)-x1(j));
end
end
L = y1(i).*L;
f = f+L;
end
plot(x,f,x,y);
Newton 插值
龙格现象
致读者： 小时百科一直以来坚持所有内容免费，这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。 因此，我们请求广大读者
热心打赏 ，使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 10 元，我们一个星期内就能脱离亏损， 并保证在接下来的一整年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款， 他们的付出帮助了 99% 的读者免费获取知识， 我们在此表示感谢。