插值法

插值算法

原理

设有 n+1 个互不相同的节点 $ (x_i,y_i)  (i = 0,1,2,...n) $

则存在唯一的多项式 \[ L_n(x)=a_0+a_1x+a_2x^2+...+a_nx^n\\\text{使得 } L_n(x_j)=y_j \ \ (j = 0,1,2,...n) \] 注意：

• 只要 n+1 个节点互异，满足上述插值条件的多项式是唯一存在的
• 如果不限制多项式的次数，插值多项式并不唯一

拉格朗日插值法

\[ L_n(x) = \sum_{k=0}^ny_k\frac{\omega_{n+1}(x)}{(x-x_k)\omega^{'}_{n+1}(x_k)} \\\text{其中}\\ \omega_{n+1}(x) = \prod_{i=0}^n(x-x_i)\\ \omega^{'}_{n+1}(x_k) = \prod_{i=0}^n(x_k-x_i) \]

Runge Phenomenon

高次插值在两端波动极大，产生明显的震荡。

不熟悉曲线运动趋势的前提下，不要轻易使用高次插值。

分段二次插值

选取跟节点 \(x\) 最近的三个节点 \(x_{i-1},x_i, x_{i+1}\) 进行二次插值。即再每一个区间 \([x_{i-1},x_{i+1}]\) 上，取： \[ f(x) \approx L_2(x) = \sum^{i+1}_{k=i-1}(y_k\prod_{j=i-1\atop j \neq k}\frac{x_i-x_j}{x_k-x_i}) \]

牛顿插值法

与拉格朗日法相比，具有继承性。

存在龙格现象。

差商

一阶差商

\[ \text{称 }f[x_0,x_k] = \frac{f(x_k)-f(x_0)}{x_k-x_0}\text{ 为函数}f(x)\text{关于点}x_0,x_k\text{的一阶差商} \]

k阶差商

\[ f[x_0,x_1,...,x_k]=\frac{f[x_1,...,x_{k-1},x_k]-f[x_0,x_1,...,x_{k-1}]}{x_k-x_0} \]

牛顿插值法

\[ f(x) = f(x_0)+f[x_0, x_1](x-x_0) + f[x_0, x_1,x_2](x-x_0)(x-x_1)+... +f[x_0, x_1,...,x_{n}](x-x_0)(x-x_1)...(x-x_{n}) \]

Hermite 插值

设函数 \(f(x)\) 在区间 \([a,b]\) 上有 \(n+1\) 个互异节点 \(a = x_0<x_1<x_2<...<x_n = b\)，定义在 \([a, b]\) 上的函数 \(f(x)\) 在节点上满足： \[ f(x_i) = y_i, f'(x_i) = y_i'\ (i=0,1,2,...n)\ (2n+2\text{ 个条件}) \] 可唯一确定一个次数不超过 \(2n-1\) 的多项式 \(H_{2n+1}(x) = H(x)\) 满足： \[ H(x_j) = y_j,\ H'(x_j) = m_j \ (j=0,1,...n) \] 其余项为： \[ R(x) = f(x)-H(x)=\frac{f^{2n+2}(\xi)}{(2n+2)!}\omega_{2n+2}(x) \]

分段三次 Hermite 插值 (PCHIP)

直接使用 Hermite 插值也存在龙格现象。