插值算法

插值法定理

[定理]设有n + 1个互不相同的节点(x_i, y_i) (i = 0, 1, 2, ..., n)则存在唯一的多项式： φ_n(x) = a₀ + a₁x + a₂x² + ... + a_nxⁿ,使得φ_n(x_j) = y_j (j = 0, 1, 2, ...n). $$\begin{aligned}&\text{证}\begin{cases}a_0+a_1x_0+a_2x_0^2+...+a_nx_0^n=y_0\\a_0+a_1x_1+a_2x_1^2+...+a_nx_1^n=y_1\\...\\a_0+a_1x_n+a_2x_n^2+...+a_nx_n^n=y_n&\end{cases}\text{,令:}A=\begin{bmatrix}1&x_0&\cdots&x_0^n\\1&x_1&\cdots&x_1^n\\\vdots&\vdots&\cdots&\vdots\\1&x_n&\cdots&x_n^n\end{bmatrix}\quad X=\begin{bmatrix}a_0\\a_1\\\vdots\\a_n\end{bmatrix}\quad Y=\begin{bmatrix}y_0\\y_1\\\vdots\\y_n\end{bmatrix}\\&\text{一}\end{aligned}$$ 又|A|为范德蒙行列式，很明显r(A) = n,即矩阵A可逆，则对于方程组AX = Y有且仅有一个解. 从而φ_n(x) = a₀ + a₁x + a₂x² + ... + a_nxⁿ唯一存在，证毕.

拉格朗日插值法

• 二维的，对于点 (x₁.y₁), (x₂, y₂) $$f(x)=\frac{x-x_2}{x_1-x_2}y_1+\frac{x-x_1}{x_2-x_1}y_2$$
• 三维的， $$f(x)=\frac{\left(x-x_2\right)\left(x-x_3\right)}{\left(x_1-x_2\right)\left(x_1-x_3\right)}y_1+\frac{\left(x-x_1\right)\left(x-x_3\right)}{\left(x_2-x_1\right)\left(x_2-x_3\right)}y_2+\frac{\left(x-x_1\right)\left(x-x_2\right)}{\left(x_3-x_1\right)\left(x_3-x_2\right)}y_3$$
• 任意的

拉格朗日插值的基函数为

$$ 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)} $$

插值函数为

$$L_n(x)=\sum_{i=0}^ny_il_i(x)=\sum_{i=0}^ny_i\left(\prod_{j=0,j\neq i}^n\frac{x-x_j}{x_i-x_j}\right).$$

牛顿插值法

观察基本思路 f₁(x) = f(x₀) + b₁(x − x₀) 可以解得：$f_1(x)=f(x_0)+\frac{f(x_1)-f(x_0)}{x_1-x_0}(x-x_0)$
再考虑后一个点进行修正， f₂(x) = f₁(x) + b₂(x − x₀)(x − x₁),令f₂(x₂) = f(x₂)

解得

$$f_2(x)=f(x_0)+\frac{f(x_1)-f(x_0)}{x_1-x_0}(x-x_0)+\frac{\left[\frac{f(x_2)-f(x_1)}{x_2-x_1}\right]-\left[\frac{f(x_1)-f(x_0)}{x_1-x_0}\right]}{x_2-x_0}(x-x_0)(x-x_1)$$

为便于书写，引入均差的概念，

其中，两个系数 $$b_1=\frac{f(x_1)-f(x_0)}{x_1-x_0}, b_2=\frac{\left[\frac{f(x_2)-f(x_1)}{x_2-x_1}\right]-\left[\frac{f(x_1)-f(x_0)}{x_1-x_0}\right]}{x_2-x_0}$$ 成为均差

b₁称为一阶均差，一般形式为 $$f[x_i,x_j]=\frac{f(x_i)-f(x_j)}{x_i-x_j},i\neq j$$ b₂称为二阶均差，一般形式为 $$ f[x_i,x_j,x_k]=\frac{f[i,j]\boldsymbol{-}f[j,k]}{x_i\boldsymbol{-}x_k},i\neq j\neq k $$

由此可以写出牛顿插值函数，

$$\begin{aligned} f(x)=& f(x_0)+f[x_0,x_1](x-x_0) \\ &+f[x_0,x_1,x_2]\left(x-x_0\right)\left(x-x_1\right)+\cdotp\cdotp\cdotp \\ &+f\begin{bmatrix}x_0,x_1,\cdotp\cdotp\cdotp,x_{n-2},x_{n-1}\end{bmatrix}(x-x_0)(x-x_1)\cdots(x-x_{n-2})(x-x_{n-1}) \\ &+f\left[x_{0},x_{1},\cdotp\cdotp\cdotp,x_{n-1},x_{n}\right]\left(x-x_{0}\right)\left(x-x_{1}\right)\cdotp\cdotp\cdotp\left(x-x_{n-1}\right)\left(x-x_{n}\right) \end{aligned}$$

埃米尔特插值法