====== 第一章 插值法 ======

===== 1.1 引言 =====

在实际问题中，函数 $y = f(x)$ 往往是通过实验或观测得到的，只知道其在某些离散点上的函数值。插值法就是根据这些已知数据点，构造一个简单函数 $P(x)$ 来近似代替 $f(x)$，并要求 $P(x)$ 在给定点处与 $f(x)$ 有相同的函数值。

**定义 1.1（插值问题）** 设函数 $y = f(x)$ 在区间 $[a, b]$ 上有定义，且已知在点 $a \leq x_0 < x_1 < \cdots < x_n \leq b$ 上的函数值 $y_0, y_1, \ldots, y_n$。若存在一个简单函数 $P(x)$ 满足：
$$P(x_i) = y_i, \quad i = 0, 1, 2, \ldots, n$$
则称 $P(x)$ 为 $f(x)$ 的**插值函数**，$x_0, x_1, \ldots, x_n$ 称为**插值节点**，$[a, b]$ 称为**插值区间**，求 $P(x)$ 的方法称为**插值法**。

如果 $P(x)$ 是次数不超过 $n$ 的多项式，即：
$$P(x) = a_0 + a_1 x + a_2 x^2 + \cdots + a_n x^n$$
则称 $P(x)$ 为**插值多项式**，相应的插值法称为**多项式插值**。

===== 1.2 插值多项式的存在唯一性 =====

**定理 1.1（存在唯一性定理）** 满足插值条件 $P(x_i) = y_i$（$i = 0, 1, \ldots, n$）的次数不超过 $n$ 的插值多项式 $P(x)$ 存在且唯一。

**证明**：设 $P(x) = a_0 + a_1 x + \cdots + a_n x^n$，由插值条件得线性方程组：
$$\begin{cases}
a_0 + a_1 x_0 + a_2 x_0^2 + \cdots + a_n x_0^n = y_0 \\
a_0 + a_1 x_1 + a_2 x_1^2 + \cdots + a_n x_1^n = y_1 \\
\vdots \\
a_0 + a_1 x_n + a_2 x_n^2 + \cdots + a_n x_n^n = y_n
\end{cases}$$

该方程组的系数行列式为**Vandermonde行列式**：
$$V_n = \begin{vmatrix} 
1 & x_0 & x_0^2 & \cdots & x_0^n \\
1 & x_1 & x_1^2 & \cdots & x_1^n \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
1 & x_n & x_n^2 & \cdots & x_n^n
\end{vmatrix} = \prod_{0 \leq j < i \leq n} (x_i - x_j)$$

由于 $x_0, x_1, \ldots, x_n$ 互不相同，故 $V_n \neq 0$，方程组有唯一解，即插值多项式存在且唯一。

===== 1.3 Lagrange插值 =====

==== 1.3.1 Lagrange插值多项式 ====

为避开求解线性方程组，Lagrange构造了一种显式表达方法。

**定义 1.2（Lagrange基函数）** 设 $l_k(x)$（$k = 0, 1, \ldots, n$）是 $n$ 次多项式，在节点 $x_0, x_1, \ldots, x_n$ 上满足：
$$l_k(x_i) = \delta_{ki} = \begin{cases} 1, & i = k \\ 0, & i \neq k \end{cases}$$
则称 $l_k(x)$ 为 **$n$ 次Lagrange基函数**。

Lagrange基函数的显式表达式为：
$$l_k(x) = \prod_{j=0, j \neq k}^{n} \frac{x - x_j}{x_k - x_j} = \frac{(x-x_0)(x-x_1)\cdots(x-x_{k-1})(x-x_{k+1})\cdots(x-x_n)}{(x_k-x_0)(x_k-x_1)\cdots(x_k-x_{k-1})(x_k-x_{k+1})\cdots(x_k-x_n)}$$

**定义 1.3（Lagrange插值多项式）** 称
$$L_n(x) = \sum_{k=0}^{n} y_k l_k(x) = \sum_{k=0}^{n} y_k \prod_{j=0, j \neq k}^{n} \frac{x - x_j}{x_k - x_j}$$
为 **$n$ 次Lagrange插值多项式**。

==== 1.3.2 线性插值与抛物线插值 ====

当 $n = 1$ 时，得到**线性插值**：
$$L_1(x) = y_0 \frac{x - x_1}{x_0 - x_1} + y_1 \frac{x - x_0}{x_1 - x_0}$$
也可写成：
$$L_1(x) = y_0 + \frac{y_1 - y_0}{x_1 - x_0}(x - x_0)$$

当 $n = 2$ 时，得到**抛物线插值（二次插值）**：
$$L_2(x) = y_0 \frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)} + y_1 \frac{(x-x_0)(x-x_2)}{(x_1-x_0)(x_1-x_2)} + y_2 \frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)}$$

==== 1.3.3 插值余项与误差估计 ====

**定理 1.2（插值余项定理）** 设 $f(x)$ 在 $[a, b]$ 上具有 $n+1$ 阶导数，$L_n(x)$ 是 $f(x)$ 的 $n$ 次Lagrange插值多项式，则对任意 $x \in [a, b]$，插值余项为：
$$R_n(x) = f(x) - L_n(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!} \omega_{n+1}(x)$$
其中 $\xi \in (a, b)$ 且依赖于 $x$，$\omega_{n+1}(x) = \prod_{i=0}^{n}(x - x_i) = (x-x_0)(x-x_1)\cdots(x-x_n)$。

**证明**：当 $x = x_i$ 时，$R_n(x_i) = 0$，定理显然成立。

当 $x \neq x_i$ 时，设 $R_n(x) = k(x) \omega_{n+1}(x)$，构造辅助函数：
$$\varphi(t) = f(t) - L_n(t) - k(x) \omega_{n+1}(t)$$

则 $\varphi(t)$ 在 $[a, b]$ 上有 $n+2$ 个零点 $x, x_0, x_1, \ldots, x_n$。反复应用Rolle定理，存在 $\xi \in (a, b)$ 使得：
$$\varphi^{(n+1)}(\xi) = f^{(n+1)}(\xi) - k(x) \cdot (n+1)! = 0$$

因此 $k(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!}$，定理得证。

**推论 1.1** 若 $|f^{(n+1)}(x)| \leq M_{n+1}$，则误差估计为：
$$|R_n(x)| \leq \frac{M_{n+1}}{(n+1)!} |\omega_{n+1}(x)|$$

===== 1.4 Newton插值 =====

==== 1.4.1 差商的定义与性质 ====

**定义 1.4（差商）** 设 $f(x)$ 在互异节点 $x_0, x_1, \ldots, x_n$ 上有定义。

**一阶差商**：$f[x_i, x_j] = \frac{f(x_j) - f(x_i)}{x_j - x_i}$

**二阶差商**：$f[x_i, x_j, x_k] = \frac{f[x_j, x_k] - f[x_i, x_j]}{x_k - x_i}$

**$k$ 阶差商**：$f[x_0, x_1, \ldots, x_k] = \frac{f[x_1, \ldots, x_k] - f[x_0, \ldots, x_{k-1}]}{x_k - x_0}$

**差商的性质**：

1. **对称性**：差商与节点的排列次序无关
   $$f[x_0, x_1, \ldots, x_k] = f[x_{i_0}, x_{i_1}, \ldots, x_{i_k}]$$
   其中 $(i_0, i_1, \ldots, i_k)$ 是 $(0, 1, \ldots, k)$ 的任一排列。

2. **与导数的关系**：若 $f(x)$ 在 $[a, b]$ 上有 $k$ 阶导数，则存在 $\xi \in (a, b)$ 使得：
   $$f[x_0, x_1, \ldots, x_k] = \frac{f^{(k)}(\xi)}{k!}$$

==== 1.4.2 Newton插值公式 ====

**定理 1.3（Newton插值公式）** 
$$N_n(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})$$
或写成：
$$N_n(x) = \sum_{k=0}^{n} f[x_0, x_1, \ldots, x_k] \omega_k(x)$$
其中 $\omega_0(x) = 1$，$\omega_k(x) = \prod_{i=0}^{k-1}(x-x_i)$（$k \geq 1$）。

Newton插值的**优点**：增加节点时只需在后面添加一项，前面的计算结果仍然可用。

==== 1.4.3 差分与等距节点插值 ====

当节点等距分布时，设步长为 $h$，$x_k = x_0 + kh$，引入**差分**概念。

**定义 1.5（差分）**
  - **向前差分**：$\Delta f_k = f_{k+1} - f_k$
  - **向后差分**：$\nabla f_k = f_k - f_{k-1}$
  - **中心差分**：$\delta f_k = f_{k+\frac{1}{2}} - f_{k-\frac{1}{2}}$

**$m$ 阶向前差分**：$\Delta^m f_k = \Delta^{m-1} f_{k+1} - \Delta^{m-1} f_k$

**差分表**：
| $x_k$ | $f_k$ | $\Delta f_k$ | $\Delta^2 f_k$ | $\Delta^3 f_k$ | ... |
|-------|-------|--------------|----------------|----------------|-----|
| $x_0$ | $f_0$ | $\Delta f_0$ | $\Delta^2 f_0$ | $\Delta^3 f_0$ | ... |
| $x_1$ | $f_1$ | $\Delta f_1$ | $\Delta^2 f_1$ | ... | |
| $x_2$ | $f_2$ | $\Delta f_2$ | ... | | |
| ... | ... | ... | | | |

**差商与差分的关系**：
$$f[x_0, x_1, \ldots, x_k] = \frac{\Delta^k f_0}{k! h^k} = \frac{\nabla^k f_k}{k! h^k}$$

**Newton向前插值公式**（插值点靠近 $x_0$）：
令 $x = x_0 + th$，则：
$$N_n(x_0 + th) = \sum_{k=0}^{n} \binom{t}{k} \Delta^k f_0$$
其中 $\binom{t}{k} = \frac{t(t-1)\cdots(t-k+1)}{k!}$。

**Newton向后插值公式**（插值点靠近 $x_n$）：
$$N_n(x_n + th) = \sum_{k=0}^{n} (-1)^k \binom{-t}{k} \nabla^k f_n$$

===== 1.5 Hermite插值 =====

==== 1.5.1 Hermite插值问题 ====

在某些应用中，不仅要求插值函数与被插函数在节点处函数值相等，还要求导数值相等。

**定义 1.6（Hermite插值）** 已知 $f(x)$ 在节点 $x_0, x_1, \ldots, x_n$ 处的函数值 $y_i = f(x_i)$ 和导数值 $y'_i = f'(x_i)$（$i = 0, 1, \ldots, n$），求次数不超过 $2n+1$ 的多项式 $H_{2n+1}(x)$ 满足：
$$H_{2n+1}(x_i) = y_i, \quad H'_{2n+1}(x_i) = y'_i, \quad i = 0, 1, \ldots, n$$

==== 1.5.2 三次Hermite插值 ====

**两点三次Hermite插值**：已知 $f(x_0) = y_0$，$f(x_1) = y_1$，$f'(x_0) = y'_0$，$f'(x_1) = y'_1$。

$$H_3(x) = y_0 h_0(x) + y_1 h_1(x) + y'_0 \bar{h}_0(x) + y'_1 \bar{h}_1(x)$$

其中基函数为：
$$h_0(x) = \left(1 + 2\frac{x-x_0}{x_1-x_0}\right)\left(\frac{x-x_1}{x_0-x_1}\right)^2$$
$$h_1(x) = \left(1 + 2\frac{x-x_1}{x_0-x_1}\right)\left(\frac{x-x_0}{x_1-x_0}\right)^2$$
$$\bar{h}_0(x) = (x-x_0)\left(\frac{x-x_1}{x_0-x_1}\right)^2$$
$$\bar{h}_1(x) = (x-x_1)\left(\frac{x-x_0}{x_1-x_0}\right)^2$$

==== 1.5.3 余项公式 ====

**定理 1.4（Hermite插值余项）**
$$R_{2n+1}(x) = f(x) - H_{2n+1}(x) = \frac{f^{(2n+2)}(\xi)}{(2n+2)!} \omega_{n+1}^2(x)$$
其中 $\xi \in (a, b)$，$\omega_{n+1}(x) = \prod_{i=0}^{n}(x-x_i)$。

===== 1.6 分段插值 =====

==== 1.6.1 高次插值的Runge现象 ====

**Runge现象**：对于 $f(x) = \frac{1}{1+x^2}$，$x \in [-5, 5]$，当用等距节点构造高次Lagrange插值时，在区间端点附近出现剧烈振荡，插值效果反而变差。

这表明：**高次插值并不总是优于低次插值**。

==== 1.6.2 分段线性插值 ====

**定义 1.7（分段线性插值）** 设节点 $a = x_0 < x_1 < \cdots < x_n = b$，在每一小区间 $[x_i, x_{i+1}]$ 上用线性函数：
$$S_1(x) = y_i \frac{x_{i+1} - x}{x_{i+1} - x_i} + y_{i+1} \frac{x - x_i}{x_{i+1} - x_i}, \quad x \in [x_i, x_{i+1}]$$

整体函数 $S_1(x)$ 在 $[a, b]$ 上连续，称为**分段线性插值函数**。

**误差估计**：若 $f(x) \in C^2[a, b]$，则
$$|f(x) - S_1(x)| \leq \frac{h^2}{8} \max_{a \leq x \leq b} |f''(x)|$$
其中 $h = \max_{0 \leq i \leq n-1} (x_{i+1} - x_i)$。

==== 1.6.3 分段三次Hermite插值 ====

**定义 1.8（分段三次Hermite插值）** 已知 $f(x_i) = y_i$，$f'(x_i) = y'_i$（$i = 0, 1, \ldots, n$），在每个小区间 $[x_i, x_{i+1}]$ 上构造三次Hermite插值。

整体函数 $S_3(x)$ 满足：
  - $S_3(x) \in C^1[a, b]$（一阶导数连续）
  - $S_3(x_i) = y_i$，$S'_3(x_i) = y'_i$

**误差估计**：
$$|f(x) - S_3(x)| \leq \frac{h^4}{384} \max_{a \leq x \leq b} |f^{(4)}(x)|$$

===== 1.7 典型例题 =====

**例题 1.1** 已知 $\sin 30° = 0.5$，$\sin 45° = \frac{\sqrt{2}}{2} \approx 0.7071$，$\sin 60° = \frac{\sqrt{3}}{2} \approx 0.8660$。用抛物线插值求 $\sin 50°$ 的近似值。

**解**：取 $x_0 = 30°$，$x_1 = 45°$，$x_2 = 60°$，$y_0 = 0.5$，$y_1 = 0.7071$，$y_2 = 0.8660$。

Lagrange插值：
$$L_2(50) = 0.5 \cdot \frac{(50-45)(50-60)}{(30-45)(30-60)} + 0.7071 \cdot \frac{(50-30)(50-60)}{(45-30)(45-60)} + 0.8660 \cdot \frac{(50-30)(50-45)}{(60-30)(60-45)}$$

计算：
  - 第一项：$0.5 \cdot \frac{5 \times (-10)}{(-15) \times (-30)} = 0.5 \cdot \frac{-50}{450} = -0.0556$
  - 第二项：$0.7071 \cdot \frac{20 \times (-10)}{15 \times (-15)} = 0.7071 \cdot \frac{-200}{-225} = 0.7071 \cdot 0.8889 = 0.6285$
  - 第三项：$0.8660 \cdot \frac{20 \times 5}{30 \times 15} = 0.8660 \cdot \frac{100}{450} = 0.8660 \cdot 0.2222 = 0.1924$

$$L_2(50) = -0.0556 + 0.6285 + 0.1924 = 0.7653$$

（精确值：$\sin 50° = 0.7660$，误差约 $0.0007$）

**例题 1.2** 已知函数表：
| $x$ | 1 | 2 | 4 | 6 |
|-----|---|---|---|---|
| $f(x)$ | 0 | 1 | 2 | 3 |

求Newton插值多项式并计算 $f(3)$ 的近似值。

**解**：构造差商表：
| $x_i$ | $f(x_i)$ | 一阶差商 | 二阶差商 | 三阶差商 |
|-------|----------|----------|----------|----------|
| 1 | 0 | 1 | -1/3 | 1/15 |
| 2 | 1 | 1/2 | 1/12 | |
| 4 | 2 | 1/2 | | |
| 6 | 3 | | | |

Newton插值多项式：
$$N_3(x) = 0 + 1 \cdot (x-1) - \frac{1}{3}(x-1)(x-2) + \frac{1}{15}(x-1)(x-2)(x-4)$$

计算 $N_3(3)$：
$$N_3(3) = 2 - \frac{1}{3} \cdot 2 \cdot 1 + \frac{1}{15} \cdot 2 \cdot 1 \cdot (-1) = 2 - \frac{2}{3} - \frac{2}{15} = 2 - 0.6667 - 0.1333 = 1.2$$

===== 1.8 习题 =====

**基础练习**

1. 已知 $f(1) = 2$，$f(2) = 3$，$f(3) = 5$，求Lagrange插值多项式 $L_2(x)$。

2. 设 $f(x) = x^3 + 2x^2 + x + 1$，取节点 $x = 0, 1, 2, 3$。
   (1) 构造差商表；
   (2) 写出Newton插值多项式。

3. 已知数据：
   | $x$ | 0 | 1 | 2 |
   |-----|---|---|---|
   | $f(x)$ | 1 | 2 | 3 |
   | $f'(x)$ | 0 | 1 | |
   
   求三次Hermite插值多项式 $H_3(x)$。

**进阶练习**

4. 设 $f(x) \in C^2[a, b]$，$f(a) = f(b) = 0$，证明：
   $$\max_{a \leq x \leq b} |f(x)| \leq \frac{(b-a)^2}{8} \max_{a \leq x \leq b} |f''(x)|$$

5. 证明 $n$ 次Lagrange基函数满足 $\sum_{k=0}^{n} l_k(x) = 1$。

6. 设 $L_n(x)$ 是 $f(x)$ 的 $n$ 次Lagrange插值多项式，证明：
   $$f[x_0, x_1, \ldots, x_n, x] = \frac{f^{(n+1)}(\xi)}{(n+1)!}$$
   其中 $\xi$ 位于 $x_0, x_1, \ldots, x_n, x$ 所界定的区间内。

**编程实践**

7. 用Python编写Lagrange插值程序，对 $f(x) = \frac{1}{1+x^2}$，$x \in [-5, 5]$，分别用5个、10个、20个等距节点进行插值，观察Runge现象。

8. 编写Newton插值程序，实现动态增加节点的功能。

===== 参考文献 =====

1. 李庆扬等. 数值分析（第5版）. 清华大学出版社, 2008.
2. Atkinson K E. An Introduction to Numerical Analysis. Wiley, 1989.