《计算方法》总复习

《计算方法》课程需要记忆的知识点较多，临近期末考试，我觉得有必要对这门课的各种知识点进行整理。

总结

矩阵算法
- Gauss 消元（列主元法），LU 分解（Doolittle 分解，Crout 分解，Cholesky 分解）
- 线性方程组的直接法和迭代法
- 矩阵特征值特征向量的幂法和反幂法（及规范幂法）
- 实对称矩阵的 Jacobi 方法和 QR 方法
方程解法
二分法、迭代法、牛顿

基础知识

范数

向量范数 $\|x\|$：满足非负性，齐次性（$\|\alpha x\| = |a|\cdot \|x\|$ ）和三角不等式的映射 $x \mapsto \|x\|$；
我们所常说的 $L_1$ 范数、$L_2$ 范数、$L_\infty$ 范数都是 Hölder 范数；

矩阵范数的定义和向量范数很接近，基本要求是非负性、齐次性和三角不等式；

但是，一般我们讨论的矩阵范数是相容矩阵范数，它需要额外满足两个特性：

$\|AB\| \leq \|A\|\cdot \|B\|$；
$\|Ax\| \leq \|A\|\cdot \|x\|$；（相容性）

矩阵范数可以由向量范数定义，用这种方式定义的范数称为诱导矩阵范数，我们也可以得到常见向量范数诱导范数的形式：

\[ \begin{gathered} \|A\| = \max_{\|x\| = 1} \|Ax\| \\ \|A\|_1 = \max_{1 \leq j \leq n} \sum_{i=1}^m |a_{ij}| & \textsf{列绝对值和的最大值} \\ \|A\|_\infty = \max_{1 \leq i \leq m} \sum_{j=1}^n |a_{ij}| & \textsf{行绝对值和的最大值} \\ \|A\|_2 = \sqrt{\lambda_1} & \textsf{$\lambda_1$ 是 $A^TA$ 的最大特征值绝对值} \end{gathered} \]

此外还有 Frobenius 范数，它也是相容的：

\[ \|A\|_F = \sqrt{\sum_{i=1}^m \sum_{j=1}^n |a_{ij}|^2} \]

对于任何相容范数，矩阵的特征值满足性质 $|\lambda| \leq \|A\|$
$\lim_{k \to \infty} A^k = 0$ 当且仅当 $\rho(A) < 1$，其中 $\rho(A)$ 是矩阵 $A$ 的谱半径；

条件数

矩阵 $A$ 的条件数定义为 $\kappa(A) = \|A\|\cdot \|A^{-1}\|$（相容范数），它反映了线性系统 $Ax = b$ 的敏感程度；

\[ \begin{gathered} A(x + \delta x) = b + \delta b \\ \implies \delta x = A^{-1} \delta b \implies \|\delta x\| \le \| A^{-1} \| \|\delta b\| \\ Ax = b \implies \|x\| \le \|A^{-1}\| \|b\| \\ \implies \frac{\|\delta x\|}{\|x\|} \le \|A\| \|A^{-1}\| \frac{\|\delta b\|}{\|b\|} = \kappa(A) \frac{\|\delta b\|}{\|b\|} \end{gathered} \]

矩阵算法

Gauss 消元

顺序消元法和列主元法

$LU$ 分解：Doolittle 分解（$L$ 单位下三角矩阵），Crout 分解（$U$ 单位上三角矩阵），Cholesky 分解（适用于对称正定矩阵，$A = LL^T$）

Doolittle 和 Crout 分解的核心方法就是「交错计算」

Cholsky 分解

迭代法解线性方程组

迭代法的思想是将线性方程组 $Ax = b$ 转化为 $x^{(k+1)} = Gx^{(k)} + c$ 的形式。

\[ \begin{cases} \text{Jacobi:} & D x^{(k+1)} = -(L + U)x^{(k)} + b \\ \text{Gauss-Seidel:} & (D + L)x^{(k+1)} = -Ux^{(k)} + b \\ \text{SOR:} & (D + \omega L)x^{(k+1)} = [-\omega U + (1 - \omega)D]x^{(k)} + \omega b \end{cases} \]

对于一般的迭代格式 $x^{(k+1)} = Gx^{(k)} + c$：

$\rho(G) < 1$ 是迭代收敛的充分必要条件；
某个相容范数 $\|G\| < 1$ 是迭代收敛的充分条件；

对于 Jacobi 和 Gauss-Seidel 方法，有一些特定的方法：

A 为严格对角优（行或列）矩阵时，Jacobi 和 Gauss-Seidel 方法收敛；
A 正定时，Gauss-Seidel 方法收敛；
A 对称正定时，SOR 方法在 $0 < \omega < 2$ 时收敛；

特征值和特征向量的幂法

略

Jacobi 方法和 QR 方法

Jacobi 方法用于构造 $Q^TAQ$ 使其为对角阵，思想——用 Givens 变换逐渐减小非对角元的比重：

\[ \begin{gathered} Q(p, q, \theta)=I + (\cos \theta - 1)(E_{pp} + E_{qq}) + \sin\theta(E_{pq} - E_{qp}) \\ A = (a_{ij}), \quad B = Q^T(p, q, \theta) A Q(p, q, \theta) \\ \end{gathered} \]

我们要寻找这样的 $\theta$ 使得 $b_{pq} = b_{qp} = 0$，这个 $\theta$ 的求法如下：

\[ \begin{gathered} \cot 2\theta = -\frac{a_{pp} - a_{qq}}{2a_{pq}} \\ \implies s \triangleq \frac{a_{qq} - a_{pp}}{2a_{pq}},\quad t = \tan\theta \\ t = \begin{cases} \arg \min |t|,\quad t^2 + 2st - 1 = 0, & s \ne 0 \\ 1 & s = 0 \end{cases} \\ \cos\theta = \frac{1}{\sqrt{1+t^2}}, \quad \sin\theta = \frac{t}{\sqrt{1+t^2}} \end{gathered} \]

则 Jacobi 算法的流程是：每次寻找 $|a_{pq}| = \max_{i \ne j} |a_{ij}|$，用 Givens 变换把它消掉，直到误差范围（一般阶数大于 $2$ 时无法用 Jacobi 方法得到纯对角阵）

QR 分解：$A = QR$，其中 $Q$ 是正交阵，$R$ 是上三角阵

QR 分解是 QR 方法的基石（如下），这样若 $A$ 满足一定条件，矩阵序列 $\{A_k\}$ 基本收敛于对角阵，可以用于求特征向量和特征值：

\[ \begin{gathered} A_1 \gets A \\ A_1 = Q_1R_1, \quad A_2\gets R_1Q_1 \\ A_2 = Q_2R_2, \quad A_3\gets R_2Q_2 \\ \cdots \\ \end{gathered} \]

用 Householder 反射变换做 QR 分解：

\[ \begin{gathered} H = I - 2vv^T \\ \|x\| = \|y\|,~v \triangleq \frac{y-x}{\| y - x\|} \implies Hx = y \end{gathered} \]

最小二乘拟合

矛盾方程组 $A\alpha = Y$ 的法方程 $A^TA\alpha = A^TY$

单纯形法

重点：

化成标准形式（等号，极大值）
单纯形表

其他算法

Newton 迭代

插值

Lagrange 插值：

\[ \begin{gathered} L_n(x) = \sum_{i} f(x_i)\prod_{j\ne i}\frac{x - x_j}{x_i - x_j} \\ R_n(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!}\prod_{i}(x-x_i),\quad \xi\in[a,b]\quad (R_n=f-L_n) \end{gathered} \]

Newton 插值多项式即是一种具有承袭性的 Lagrange 插值的变种，它们是同一插值多项式 $L(x)$ 在不同基下的不同表达形式，计算 Newton 插值常用差商表：

\[ \begin{gathered} N_n(x) = \sum_{i=0}^nf[x_0,\cdots,x_i]\prod_{k=0}^{i-1}(x-x_k) \\ R_n(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!}\prod_i(x-x_i) = f[x,x_0,\cdots,x_n]\prod_i(x-x_i) \end{gathered} \]

如果提供更多的信息（比如某点的更高阶导数值），Newton 插值就变成了 Hermite 插值，此时 Lagrange 插值换了新基，Newton 插值形式不变，误差仍然遵守 Newton 插值误差形式：

$$ \begin{gathered} H_{2n+1}(x) = \left[f(x_i)\left(1-2(x-x_i)\sum_{j\ne i}\frac{1}{x_i-x_j}\right)+f^\prime(x_i)(x-x_i)\right]l_i^2(x) \end{gathered}

$$

三次样条插值的基本思想是保持分段的导数和二阶导数不变，根据设未知数的不同可以分为 $M$ 关系式和 $m$ 关系式。

给定 $\{(x_i,f(x_i)), i=0,1,\cdots,n\}$，$S(x)$ 是分段三次多项式，$S^{\prime\prime}(x)$ 是线性函数：

\[ \begin{gathered} S^{\prime\prime}_i(x) = \frac{x-x_{i+1}}{x_i-x_{i+1}}M_i + \frac{x-x_i}{x_{i+1}-x_i}M_{i+1} \\ S_i(x) = \frac{(x_{i+1}-x)^3}{6h_i} M_i + \frac{(x-x_i)^3}{6h_i}M_{i+1}+C(x_{i+1}-x) + D(x - x_i) \\ \text{where.}~C=\frac{y_i}{h_i} - \frac{h_iM_i}{6},\quad D= \frac{y_{i+1}}{h_i} - \frac{h_iM_{i+1}}{6} \end{gathered} \]

化简后可以得到：

\[ \begin{gathered} \mu_iM_{i-1}+2M_i+\lambda_i M_{i+1} = d_i,\quad i=1,2,\cdots,n-1 \\ \lambda_i = \frac{h_i}{h_i+h_{i-1}},\quad \mu_i - 1 - \lambda_i\\ d_i = \frac{6}{h_i+h_{i-1}}\left(\frac{y_{i+1}-y_i}{h_i} - \frac{y_i - y_{i-1}}{h_{i-1}}\right) = 6y[x_{i-1},x_i,x_{i+1}] \end{gathered} \]

类似，$m$ 关系式有：

\[ \begin{gathered} \lambda_im_{i-1} + 2m_i+\mu_im_{i+1} = c_i,\quad i=1,2,\cdots,n-1 \\ \lambda_i = \frac{h_i}{h_i+h_{i-1}},\quad \mu_i = 1 - \lambda_i,\quad c_i=3[\lambda_i y[x_{i-1},x_i]+\mu_iy[x_i,x_{i+1}]] \end{gathered} \]

数值微积分

数值积分的代数精度：若对任意不超过 $n$ 阶的公式准确成立，则称该积分公式有 $n$ 阶的代数精度

所有数值积分在本质上进行的都是多项式插值，数值积分误差：

\[ E_n(f)=\int_{-1}^1f[x_1^{(n)},x_2^{(n)},\cdots,x_n^{(n)},x]\prod_{i=1}^n(x-x_i^{(n)})\,\mathrm d x \]

Newton-Cotes 积分公式，等距采样（可以复化），代数精度为 $n$（奇数时）或 $n+1$（偶数时）

Gauss-Legendre 积分：达到 $2n-1$ 阶的理论最优的积分公式，积分节点为 Legendre 积分多项式的节点

数值微分同样也是基于插值

微分方程数值解

用差商近似导数或者用数值积分公式近似积分的方法
近似多阶导数的方法——Taylor 法和 Runge-Kutta 法

线性多步法：有两个控制量 $p$ 和 $q$，分别控制积分区间（$[x_{n-p},x_{n+1}]$）和插值节点（共 $q+1$ 个），具体来说：

显式公式：用积分节点 $\{x_n, x_{n-1}, \cdots, x_{n-q}\}$ 近似计算 $\int_{x_{n-p}}^{x_{n+1}} f(x, y)\,\mathrm d x$；
隐式公式：用积分节点 $\{x_{n+1}, x_{n}, \cdots, x_{n+1-q}\}$ 近似计算 $\int_{x_{n-p}}^{x_{n+1}} f(x, y)\,\mathrm d x$；

绝对稳定性指在以下特定方程上的稳定性：

\[ \begin{cases} \frac{\mathrm d y}{\mathrm d x} = \lambda y, \\ y(a) = y_0, \end{cases}\quad a\le x\le b,\quad \lambda\in\mathbb C,\quad \Re\lambda<0 \]