计算方法期末复习笔记

考试信息¶

• 考试时间：2026 年 6 月 23 日（周二）下午场，二教 407
• 题型：计算/证明题 10 分 × 10
• 不考察：伪代码、时间复杂度
• 附公式（风格与期中一致）
• 必须携带：科学计算器

1 插值法¶

考察重点：Lagrange 插值（构造原理、一般形式、误差）、Newton 插值（构造原理、与 Lagrange 的差异、≤4 点的均差）、分段线性插值（基函数、误差）、两节点与分段三次 Hermite 插值、样条插值（构造思路、三种边界条件）

不考察：一般形式 Hermite、样条误差分析、二维插值、快速 Fourier 变换

1.1 插值基本概念¶

给定 \(n+1\) 个互异节点 \((x_i, y_i)\)，构造次数不超过 \(n\) 的多项式 \(\varphi_n(x)\)，使 \(\varphi_n(x_i)=y_i\)。

插值余项（通用公式）：

其中 \(\omega_{n+1}(x) = \prod_{i=0}^{n} (x - x_i)\)。

1.2 Lagrange 插值¶

构造原理¶

构造 \(n\) 次插值基函数 \(l_i(x)\)，满足 \(l_i(x_j) = \delta_{ij}\)：

Lagrange 插值公式：

基函数性质：\(l_i(x_j) = \delta_{ij}\)，\(\sum_{i=0}^{n} l_i(x) \equiv 1\)

插值余项¶

1.3 Newton 插值¶

差商（均差）定义¶

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

\(k\) 阶差商：

差商性质：对称性（点的顺序对值无影响）、线性性。

Newton 插值公式¶

递推形式：\(\varphi_n(x) = \varphi_{n-1}(x) + f[x_0, \cdots, x_n] \prod_{j=0}^{n-1} (x - x_j)\)

1.4 分段线性插值¶

基函数构造¶

误差估计¶

1.5 Hermite 插值（两节点）¶

给定两点 \(x_0, x_1\) 及其函数值 \(y_0, y_1\) 和导数值 \(y_0', y_1'\)，构造不超过三次的多项式 \(H(x)\)。

基函数：

Hermite 插值函数：\(H(x) = y_0 h_0(x) + y_1 h_1(x) + y_0' H_0(x) + y_1' H_1(x)\)

余项：

分段三次 Hermite 插值¶

在每个小区间 \([x_i, x_{i+1}]\) 上构造三次 Hermite 插值，全局具有 \(C^1\) 连续性。

误差：\(|R(x)| \leqslant \dfrac{h^4 M_4}{384}\)

1.6 三次样条插值¶

构造思路¶

在 \([a,b]\) 上给定节点 \(a=x_0<\cdots<x_n=b\) 及函数值 \(y_i\)，构造 \(s(x)\) 满足：

1. \(s(x_i) = y_i\)
2. 每个小区间上是不超过三次的多项式
3. \(s(x) \in C^2[a,b]\)（二阶导数连续）

利用 Hermite 插值形式，由 \(s''(x_i^-) = s''(x_i^+)\) 得到关于 \(m_i = s'(x_i)\) 的方程组：

其中 \(\alpha_i = \dfrac{h_{i-1}}{h_{i-1} + h_i}\)，\(\beta_i = 3\left((1 - \alpha_i) \dfrac{y_i - y_{i-1}}{h_{i-1}} + \alpha_i \dfrac{y_{i+1} - y_i}{h_i}\right)\)

三种边界条件¶

2 函数逼近¶

考察重点：离散数据多项式最佳平方逼近（定义、求解）、指数拟合与分式线性拟合、连续函数最佳平方逼近（定义、求解）、正交函数系定义与性质

不考察：基于离散数据的一般形式（含离散正交函数族）

2.1 数据拟合与最小二乘¶

插值要求 \(\varphi(x_i)=y_i\)；拟合允许残差，关注整体趋势。

最小二乘准则：

多项式最小二乘拟合¶

设 \(\varphi(x) = a_0 + a_1 x + \cdots + a_m x^m\)（\(m < n-1\)），令偏导为零得 正规方程：

其中 \(A\) 为 Vandermonde 型矩阵。

一次最小二乘拟合公式¶

2.2 可线性化的非线性拟合¶

指数拟合¶

\(y = b e^{ax}\) → 取对数 \(\ln y = ax + \ln b\)，令 \(Y = \ln y,\; B = \ln b\)，化为 \(Y = ax + B\)。

分式线性拟合¶

• \(y = \dfrac{1}{ax+b}\) → 令 \(Y = 1/y\)，化为 \(Y = ax + b\)
• \(y = \dfrac{x}{ax+b}\) → 令 \(Y = x/y\)，化为 \(Y = ax + b\)

2.3 连续函数的最佳平方逼近¶

定义¶

设 \(f(x) \in C[a,b]\)，在 \(H = \operatorname{span}\{\varphi_0, \cdots, \varphi_m\}\) 中求 \(\phi(x)\)，使

定义内积 \((u, v) = \int_a^b \omega(x) u(x) v(x) dx\)，正规方程为：

2.4 正交函数系¶

正交基下的优势：系数可直接计算，无需解方程组：

常见正交多项式：

3 数值微分与数值积分¶

考察重点：三种差商公式及 Taylor 展开误差、代数精度、Newton-Cotes（梯形、Simpson 误差）、复化求积与误差、逐次分半法、Richardson 外推与 Romberg 积分、Gauss 积分适用范围与方法、矩形域多重积分

不考察：数值积分专题（振荡、奇异、无限区间、自适应）

3.1 数值微分¶

三种差商公式¶

Taylor 展开误差分析¶

以向前差商为例：

中心差商因对称消去 \(O(h)\) 项，精度提升为 \(O(h^2)\)。

3.2 代数精度¶

判定方法：依次检验 \(f(x) = 1, x, x^2, \cdots\) 是否精确成立。

3.3 Newton-Cotes 求积¶

基本思想：用 Lagrange 插值多项式代替被积函数 → \(A_i = \int_a^b l_i(x) dx\)

等距节点：\(x_i = a + ih,\; h = \frac{b-a}{n}\)

梯形公式（\(n=1\)）¶

误差：\(R_1 = -\dfrac{(b-a)^3}{12} f''(\eta)\)，代数精度 1

Simpson 公式（\(n=2\)）¶

误差：\(R_2 = -\dfrac{(b-a)^5}{2880} f^{(4)}(\eta)\)，代数精度 3

3.4 复化求积¶

复化梯形公式¶

将 \([a,b]\) 等分为 \(n\) 份，\(h = \frac{b-a}{n}\)：

误差：\(R = -\dfrac{b-a}{12} h^2 f''(\eta) = O(h^2)\)

复化 Simpson 公式¶

将 \([a,b]\) 进行 \(2n\) 等分：

误差：\(R = -\dfrac{b-a}{180} h_1^4 f^{(4)}(\eta) = O(h^4)\)，其中 \(h_1 = \frac{b-a}{n}\)

3.5 逐次分半法¶

基本思想：不断将区间对半细分，利用前后两次近似值进行 事后误差估计。

梯形递推（复用已有节点）：

事后误差估计：

停止准则：\(|T_{2n} - T_n| < 3\varepsilon\)（梯形），\(|S_{2n} - S_n| < 15\varepsilon\)（Simpson）

3.6 Richardson 外推与 Romberg 积分¶

Richardson 外推¶

若 \(F^* - F_1(h) = a_1 h^{p_1} + a_2 h^{p_2} + \cdots\)，则

消去 \(h^{p_1}\) 项，误差阶提升至 \(O(h^{p_2})\)。

Romberg 求积¶

复化梯形误差仅含偶次幂 → 取 \(q=1/2\)，\(p_m = 2m\)：

3.7 Gauss 型求积¶

核心思想¶

\(n\) 个节点的 Gauss 求积可达 \(2n-1\) 次代数精度（普通求积只有 \(n-1\) 次）。节点为相应正交多项式的零点。

充要条件：节点多项式 \(\omega_n(x)\) 与任意次数 \(< n\) 的多项式关于权函数正交。

四种常见 Gauss 求积¶

Gauss 求积误差：

3.8 矩形域上的多重积分¶

二重积分化为累次积分：

分别对内层和外层应用一维求积方法（如复合 Simpson 公式）。

4 非线性方程（组）的数值解法¶

考察重点：二分法、不动点迭代法（收敛性判定、误差分析）、松弛法与 Steffensen 加速、Newton-Raphson 法（构造过程、二阶收敛性）、非线性方程组 Newton-Raphson 迭代流程

不考察：重根改善方法、收敛域改善方法、弦位法、Müller 法、Aitken 法

4.1 二分法¶

条件：\(f \in C[a,b]\)，\(f(a)f(b) < 0\)

过程：每次取中点 \(p = \frac{a+b}{2}\)，根据 \(f(a)f(p)\) 符号缩小区间。

收敛性：\(k\) 次后区间长度 \(\frac{b-a}{2^k}\)，所需步数 \(k \geqslant \log_2\frac{b-a}{\varepsilon}\)

特点：稳定可靠、必收敛，但线性收敛（\(p=1\)），需初始异号区间。

4.2 不动点迭代法¶

迭代格式¶

将 \(f(x)=0\) 改写为 \(x = \phi(x)\)，迭代 \(x_{k+1} = \phi(x_k)\)。

局部收敛判据：\(|\phi'(x^*)| < 1\) 则局部收敛；越小越快。

收敛阶¶

若 \(\phi'(x^*) \neq 0\)：线性收敛（\(p=1\)），\(e_{k+1} \approx \phi'(x^*) e_k\)

若 \(\phi'(x^*) = 0,\; \phi''(x^*) \neq 0\)：二阶收敛（\(p=2\)），\(e_{k+1} \approx \frac{1}{2}\phi''(x^*) e_k^2\)

4.3 松弛法¶

迭代格式：\(x_{k+1} = x_k - \omega f(x_k)\)

对应 \(\phi(x) = x - \omega f(x)\)，\(\phi'(x^*) = 1 - \omega f'(x^*)\)

收敛条件：\(|1 - \omega f'(x^*)| < 1\)，即 \(0 < \omega < \frac{2}{f'(x^*)}\)（当 \(f'(x^*) > 0\) 时）

4.4 Steffensen 方法¶

不显式使用导数，却能达二阶收敛。

基于 Aitken 加速思想，定义：

迭代：\(x_{k+1} = \hat{\phi}(x_k)\)。每步需计算两次 \(\phi\)，但收敛阶提升至 \(p=2\)。

4.5 Newton-Raphson 法（单变量）¶

迭代格式¶

对 \(f(x)=0\)，在 \(x_k\) 处 Taylor 展开取线性部分：

几何意义：用切线与 \(x\) 轴交点作为下一次近似。

收敛性¶

4.6 非线性方程组的 Newton 法¶

对 \(\boldsymbol{f}(\boldsymbol{x}) = \boldsymbol{0}\)，在 \(\boldsymbol{x}^{(k)}\) 处 Taylor 展开取线性部分：

其中 \(\boldsymbol{J}\) 为 Jacobi 矩阵：\(J_{ij} = \dfrac{\partial f_i}{\partial x_j}\)

迭代格式：

计算流程：每步需 (1) 计算 Jacobi 矩阵，(2) 解线性方程组得 \(\Delta \boldsymbol{x}^{(k)}\)，(3) 更新 \(\boldsymbol{x}\)。具有局部二阶收敛性。

5 常微分方程初值问题的数值解法¶

考察重点：基础概念（局部/总体截断误差、显式/隐式、单步/多步、精度阶、稳定性）、Euler 法推导与误差/稳定性、向后 Euler 法推导、梯形公式推导、改进 Euler 法构造、Runge-Kutta 法属性与计算流程、Adams 外推/内插的构造理念与计算流程

不考察：预估-校正法、常微分方程组、高阶微分方程、边值问题

5.1 基本概念¶

考虑初值问题：

步长 \(h = x_{k+1} - x_k\)（等距）。

5.2 Euler 方法¶

推导方式一：Taylor 展开¶

取线性部分，得 Euler 公式：\(y_{n+1} = y_n + h f(x_n, y_n)\)

推导方式二：数值积分¶

用 左矩形公式 近似积分 → Euler 公式。

误差分析¶

• 局部截断误差：\(l_{n+1} = \dfrac{h^2}{2} y''(x_n) + O(h^3) = O(h^2)\) → 1 阶精度
• 总体截断误差：\(e_n = O(h)\)（比局部低一阶）

稳定性分析¶

解模型方程 \(y' = \lambda y\)：\(y_{n+1} = (1 + \lambda h) y_n\)

绝对稳定条件：\(|1 + \lambda h| \leqslant 1\)（复平面上以 \((-1,0)\) 为圆心、半径为 1 的圆盘）

若 \(\lambda < 0\)：需 \(h \leqslant -2/\lambda\)

5.3 向后 Euler 方法¶

推导方式一：Taylor 展开（向后）¶

\(y(x_n) = y(x_{n+1}) - h y'(x_{n+1}) + \cdots\)

得 向后 Euler 公式：\(y_{n+1} = y_n + h f(x_{n+1}, y_{n+1})\)

推导方式二：数值积分（右矩形）¶

用 右矩形公式 近似积分 → 向后 Euler 公式。

特点¶

• 单步隐式方法，需不动点迭代求解
• 局部截断误差 \(O(h^2)\)，1 阶精度
• A-稳定：\(\text{Re}(\lambda h) \leqslant 0\) 即稳定（整个左半平面），适合刚性问题

5.4 梯形公式¶

推导（数值积分）¶

用 梯形积分公式 近似 \(\int_{x_n}^{x_{n+1}} f(\xi, y(\xi)) d\xi\)：

特点¶

• 单步隐式方法
• 局部截断误差 \(O(h^3)\)，2 阶精度，全局误差 \(O(h^2)\)
• A-稳定
• 内迭代收敛条件更宽松：\(hL/2 < 1\)

5.5 改进 Euler 方法（Heun 方法）¶

构造思路¶

梯形公式需迭代求解。固定一次校正，得到显式方法：

即：\(y_{n+1} = y_n + \frac{h}{2} [f(x_n, y_n) + f(x_{n+1}, y_n + h f(x_n, y_n))]\)

特点¶

• 单步显式方法，不需迭代
• 局部截断误差 \(O(h^3)\)，2 阶精度
• PEC 结构（Predict-Evaluate-Correct）

5.6 Runge-Kutta 方法¶

方法属性与构造理念¶

核心思想：在 \([x_n, x_{n+1}]\) 内计算多个点的斜率，加权平均获得更高精度。

Butcher 表：将 RK 系数整理成表格形式。

二阶 RK 一般形式¶

参数满足：\(\omega_1 + \omega_2 = 1\)，\(\alpha\omega_2 = \beta\omega_2 = 1/2\)

• 改进 Euler 法：\(\omega_1=\omega_2=1/2,\; \alpha=\beta=1\)
• 中点方法：\(\omega_1=0,\; \omega_2=1,\; \alpha=\beta=1/2\)

经典四阶 RK 方法¶

• 局部截断误差 \(O(h^5)\)，全局误差 \(O(h^4)\)，4 阶精度
• 权重 \(\frac{1}{6}, \frac{2}{6}, \frac{2}{6}, \frac{1}{6}\) 与 Simpson 积分权重一致

5.7 Adams 方法¶

构造理念¶

线性多步法 的一般形式：

通过插值多项式近似 \(f(x, y(x))\)，再积分得到计算格式。

Adams-Bashforth（外推公式）¶

构造思想：用 \([x_{n-k}, x_n]\) 上的历史点插值 → 外推到 \([x_n, x_{n+1}]\) 积分 → 显式方法。

4 阶 Adams-Bashforth（4 步，使用 \(f_n, f_{n-1}, f_{n-2}, f_{n-3}\)）：

局部截断误差 \(O(h^5)\)，4 阶精度。

Adams-Moulton（内插公式）¶

构造思想：插值包含 \((x_{n+1}, f_{n+1})\) → 隐式方法，稳定性更好。

4 阶 Adams-Moulton（3 步，使用 \(f_{n+1}, f_n, f_{n-1}, f_{n-2}\)）：

局部截断误差 \(O(h^5)\)，4 阶精度。误差系数 \(|-19/720| < |251/720|\)（优于外推）。

出发值¶

多步法需要 \(y_0, y_1, \cdots, y_{k-1}\) 才能启动。通常用 同阶 RK 方法 以小步长计算出发值。

核心方法速查表¶

插值方法对比¶

ODE 方法对比¶

非线性方程求根方法对比¶

数值积分方法对比¶