用牛顿插值计算hermite插值

牛顿插值可以用来计算Hermite插值，具体步骤如下：

1. 将给定的数据点 $(x_0, f(x_0), f'(x_0)), (x_1, f(x_1), f'(x_1)), \ldots, (x_n, f(x_n), f'(x_n))$ 按照 $x$ 的大小进行排序。

2. 计算差商表：

$$
\begin{array}{ccccccc}
x_0 & f(x_0) & & & & & \\
& & f[x_0,x_1] & & & & \\
x_1 & f(x_1) & f[x_1,x_0,x_2] & & & & \\
& & f[x_1,x_2] & f[x_0,x_1,x_2,x_3] & & & \\
x_2 & f(x_2) & f[x_2,x_1,x_3] & f[x_1,x_2,x_3,x_4] & & & \\
& & f[x_2,x_3] & f[x_1,x_2,x_3,x_4,x_5] & f[x_0,x_1,x_2,x_3,x_4,x_5] & & \\
x_3 & f(x_3) & f[x_3,x_2,x_4] & f[x_2,x_3,x_4,x_5] & f[x_1,x_2,x_3,x_4,x_5,x_6] & & \\
& & f[x_3,x_4] & f[x_2,x_3,x_4,x_5,x_6] & f[x_1,x_2,x_3,x_4,x_5,x_6,x_7] & f[x_0,x_1,x_2,x_3,x_4,x_5,x_6,x_7] \\
x_4 & f(x_4) & f[x_4,x_3,x_5] & f[x_3,x_4,x_5,x_6] & f[x_2,x_3,x_4,x_5,x_6,x_7] & f[x_1,x_2,x_3,x_4,x_5,x_6,x_7,x_8] & \\
& & f[x_4,x_5] & f[x_3,x_4,x_5,x_6,x_7] & f[x_2,x_3,x_4,x_5,x_6,x_7,x_8] & f[x_1,x_2,x_3,x_4,x_5,x_6,x_7,x_8,x_9] & f[x_0,x_1,x_2,x_3,x_4,x_5,x_6,x_7,x_8,x_9] \\
\vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\
x_n & f(x_n) & f[x_n,x_{n-1},x_{n-2},\ldots,x_{n-k}] & f[x_{n-1},x_{n-2},\ldots,x_{n-k},x_{n-k-1}] & \cdots & f[x_2,x_1,x_0,x_{n-k-1},x_{n-k-2},\ldots,x_{n-1}] & f[x_1,x_0,x_{n-k-1},x_{n-k-2},\ldots,x_{n-2},x_{n-1}] \\
\end{array}
$$

其中 $f[x_{i_1},x_{i_2},\ldots,x_{i_k}]$ 表示差商，定义为

$$
f[x_{i_1},x_{i_2},\ldots,x_{i_k}] = \frac{f[x_{i_2},x_{i_3},\ldots,x_{i_k}] - f[x_{i_1},x_{i_2},\ldots,x_{i_{k-1}}]}{x_{i_k}-x_{i_1}}
$$

3. Hermite插值多项式为

$$
\begin{aligned}
p(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) \\
&+ \cdots + f[x_0,x_1,\ldots,x_n](x-x_0)(x-x_1)\cdots(x-x_{n-1}) \\
&+ f[x_0,x_1,\ldots,x_n,x](x-x_0)(x-x_1)\cdots(x-x_n) \\
\end{aligned}
$$

其中

$$
f[x_0,x_1,\ldots,x_n,x] = \sum_{i=0}^n \frac{f(x_i)}{(x-x_i)\prod_{j\neq i}(x_i-x_j)} - \sum_{i=0}^n \frac{f'(x_i)}{\prod_{j\neq i}(x_i-x_j)}
$$

4. 使用牛顿插值公式计算 $p(x)$ 的值，即

$$
p(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) + \cdots + f[x_0,x_1,\ldots,x_n](x-x_0)(x-x_1)\cdots(x-x_{n-1})
$$

其中

$$
f[x_{i_1},x_{i_2},\ldots,x_{i_k}] = \frac{f[x_{i_2},x_{i_3},\ldots,x_{i_k}] - f[x_{i_1},x_{i_2},\ldots,x_{i_{k-1}}]}{x_{i_k}-x_{i_1}}
$$

注意，当 $x$ 与给定的数据点中某个 $x_i$ 相等时，上述计算方法不适用，需要进行特殊处理。