[数学建模算法] (25) 插值和拟合：分段线性插值

最编程 2024-06-22 16:25:34

...

1.插值多项式的震荡

用 Lagrange 插值多项式 $L_{n}(x)$ 近似 $f(x)(a \leq x \leq b)$ ，虽然随着节点个数的增加， $L_{n}(x)$ 的次数 $n$ 变大，多数情况下误差 $\left|R_{n}(x)\right|$ 会变小。但是 $n$ 增大时， $L_{n}(x)$ 的光滑性变坏，有时会出现很大的振荡。理论上，当 $n \rightarrow \infty$ ，在 $[a, b]$ 内并不能保证 $L_{n}(x)$ 处处收敛于 $f(x)$ 。Runge给出了一个有名的例子：

$f(x)=\frac{1}{1+x^{2}}, \quad x \in[-5,5]$

对于较大的 $|x|$ ，随着 $n$ 的增大， $L_{n}(x)$ 震荡越来越大，事实上可以证明，仅当 $x \leq 3.63$ 时，才有 $\lim _{n \rightarrow \infty} L_{n}(x)=f(x)$ ，而在此区间外， $L_{n}(x)$ 是发散的。

高次插值多项式的这些缺陷，促使人们转而寻求简单的低次多项式插值。

2.分段线性插值

简单地说，将每两个相邻的节点用直线连起来，如此形成的一条折线就是分段线性插值函数，记做 $I_{n}(x)$ ,它满足 $I_{n}\left(x_{i}\right)=y_{i}$ ，且 $I_{n}(x)$ 在每个小区间 $\left[x_{i}, x_{i+1}\right]$ 是线性函数 $(i=0,1, \cdots, n)$ 。

$I_{n}(x)$ 可表示为
$I_{n}(x)=\sum_{i=0}^{n} y_{i} l_{i}(x)$
$l_{i}(x)=\left\{\begin{array}{l}{\frac{x-x_{i-1}}{x_{i}-x_{i-1}}}，x \in\left[x_{i-1}, x_{i}\right]（i=0时舍去） \\ {\frac{x-x_{i+1}}{x_{i}-x_{i+1}}} ，x \in\left[x_{i}, x_{i+1}\right]（i=n时舍去）\\ {0}，其他\end{array}\right.$

I_{n}(x)有良好的收敛性，即对于x \in[a, b]有，
$\lim _{n \rightarrow \infty} I_{n}(x)=f(x)$
有 $I_{n}(x)$ 计算 $x$ 点的插值时，只用到 $x$ 左右的两个节点，计算量与节点个数 $n$ 无关。但 $n$ 越大，分段越多，插值误差越小。实际上用函数表作插值计算时，分段线性插值就足够了，如数学、物理中用的特殊函数表，数理统计中用的概率分布表等。