第八章 直接法

线性方程组是科学计算中最基本的问题之一。给定 $n$ 阶线性方程组： $$Ax = b$$

其中 $A \in \mathbb{R}^{n \times n}$ 是非奇异矩阵，$b \in \mathbb{R}^n$ 是已知向量，$x \in \mathbb{R}^n$ 是未知向量。

Cramer法则：$x_i = \frac{\det(A_i)}{\det(A)}$，计算量约 $(n+1)!$ 次乘法，当 $n=20$ 时需要约 $10^{21}$ 次运算，不可行。

本章介绍实用的直接法，经过有限步算术运算求得精确解（不考虑舍入误差）。主要包括Gauss消去法及其变形。

通过初等行变换将系数矩阵化为上三角矩阵，然后回代求解。

初等行变换： 1. 交换两行 2. 某行乘以非零常数 3. 某行加上另一行的倍数

记 $A^{(1)} = A$，$b^{(1)} = b$。

第 $k$ 步（$k = 1, 2, \ldots, n-1$）：

假设 $a_{kk}^{(k)} \neq 0$（主元），计算乘数： $$m_{ik} = \frac{a_{ik}^{(k)}}{a_{kk}^{(k)}}, \quad i = k+1, \ldots, n$$

对 $i = k+1, \ldots, n$，$j = k, \ldots, n$： $$a_{ij}^{(k+1)} = a_{ij}^{(k)} - m_{ik} a_{kj}^{(k)}$$

对 $i = k+1, \ldots, n$： $$b_i^{(k+1)} = b_i^{(k)} - m_{ik} b_k^{(k)}$$

经过 $n-1$ 步后，得到上三角方程组 $A^{(n)}x = b^{(n)}$。

$$x_n = \frac{b_n^{(n)}}{a_{nn}^{(n)}}$$

$$x_i = \frac{b_i^{(n)} - \sum_{j=i+1}^{n} a_{ij}^{(n)} x_j}{a_{ii}^{(n)}}, \quad i = n-1, n-2, \ldots, 1$$

消去过程：

1. 乘除法次数：$\sum_{k=1}^{n-1} (n-k)(n-k+2) = \frac{n^3}{3} + \frac{n^2}{2} - \frac{5n}{6}$

回代过程：

1. 乘除法次数：$\sum_{i=1}^{n} (n-i+1) = \frac{n(n+1)}{2}$

总计：$\frac{n^3}{3} + n^2 - \frac{n}{3} \approx \frac{n^3}{3}$（当 $n$ 较大时）

若某步 $a_{kk}^{(k)} = 0$，消去过程无法继续。

若 $|a_{kk}^{(k)}|$ 很小，会导致舍入误差放大。

在第 $k$ 步，在第 $k$ 列中选取绝对值最大的元素作为主元： $$|a_{p_k, k}^{(k)}| = \max_{k \leq i \leq n} |a_{ik}^{(k)}|$$

交换第 $k$ 行和第 $p_k$ 行，然后消去。

定理 8.1 若 $A$ 非奇异，则列主元Gauss消去法可完成。

定理 8.2 若 $A$ 的各阶顺序主子式都不为零，则 $A$ 可唯一分解为： $$A = LU$$

其中 $L$ 是单位下三角矩阵，$U$ 是上三角矩阵。

Doolittle分解：$L$ 单位下三角，$U$ 上三角 Crout分解：$L$ 下三角，$U$ 单位上三角

设 $A = LU$，即： $$\begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n}
a_{21} & a_{22} & \cdots & a_{2n}
\vdots & \vdots & \ddots & \vdots
a_{n1} & a_{n2} & \cdots & a_{nn} \end{bmatrix} = \begin{bmatrix} 1 & & &
l_{21} & 1 & &
\vdots & \vdots & \ddots &
l_{n1} & l_{n2} & \cdots & 1 \end{bmatrix} \begin{bmatrix} u_{11} & u_{12} & \cdots & u_{1n}
& u_{22} & \cdots & u_{2n}
& & \ddots & \vdots
& & & u_{nn} \end{bmatrix}$$

按行计算（$k = 1, 2, \ldots, n$）：

计算 $U$ 的第 $k$ 行： $$u_{kj} = a_{kj} - \sum_{m=1}^{k-1} l_{km} u_{mj}, \quad j = k, k+1, \ldots, n$$

计算 $L$ 的第 $k$ 列： $$l_{ik} = \frac{a_{ik} - \sum_{m=1}^{k-1} l_{im} u_{mk}}{u_{kk}}, \quad i = k+1, \ldots, n$$

$Ax = b \Leftrightarrow LUx = b$

分两步求解： 1. 前代：$Ly = b$，求 $y$ 2. 回代：$Ux = y$，求 $x$

定义 8.1 若 $A^T = A$ 且对任意非零向量 $x$，$x^T A x > 0$，则称 $A$ 为对称正定矩阵。

定理 8.3 若 $A$ 对称正定，则： 1. $A$ 非奇异 2. $A$ 的顺序主子式全大于零 3. $A$ 的特征值全为正

定理 8.4 若 $A$ 对称正定，则存在唯一的对角元为正的下三角矩阵 $L$，使得： $$A = LL^T$$

这就是Cholesky分解或平方根法。

按列计算（$j = 1, 2, \ldots, n$）：

对角元： $$l_{jj} = \sqrt{a_{jj} - \sum_{k=1}^{j-1} l_{jk}^2}$$

非对角元（$i = j+1, \ldots, n$）： $$l_{ij} = \frac{a_{ij} - \sum_{k=1}^{j-1} l_{ik} l_{jk}}{l_{jj}}$$

为避免开方运算，可将 $A$ 分解为 $A = LDL^T$，其中 $L$ 单位下三角，$D$ 对角矩阵。

三对角方程组形如： $$\begin{bmatrix} b_1 & c_1 & & &
a_2 & b_2 & c_2 & &
& a_3 & b_3 & c_3 &
& & \ddots & \ddots & \ddots
& & & a_n & b_n \end{bmatrix} \begin{bmatrix} x_1
x_2
x_3
\vdots
x_n \end{bmatrix} = \begin{bmatrix} d_1
d_2
d_3
\vdots
d_n \end{bmatrix}$$

在样条插值、微分方程数值解等问题中常见。

设 $A = LU$，其中： $$L = \begin{bmatrix} 1 & & &
l_2 & 1 & &
& l_3 & 1 &
& & \ddots & \ddots
& & & l_n & 1 \end{bmatrix}, \quad U = \begin{bmatrix} u_1 & c_1 & &
& u_2 & c_2 &
& & \ddots & \ddots
& & & u_n \end{bmatrix}$$

分解公式： $$u_1 = b_1$$ $$l_i = \frac{a_i}{u_{i-1}}, \quad i = 2, \ldots, n$$ $$u_i = b_i - l_i c_{i-1}, \quad i = 2, \ldots, n$$

追过程（前代）：$Ly = d$ $$y_1 = d_1$$ $$y_i = d_i - l_i y_{i-1}, \quad i = 2, \ldots, n$$

赶过程（回代）：$Ux = y$ $$x_n = \frac{y_n}{u_n}$$ $$x_i = \frac{y_i - c_i x_{i+1}}{u_i}, \quad i = n-1, \ldots, 1$$

计算量：约 $5n$ 次乘除法，是 $O(n)$ 算法。

定义 8.2 向量 $x \in \mathbb{R}^n$ 的范数 $\|x\|$ 满足： 1. $\|x\| \geq 0$，$\|x\| = 0 \Leftrightarrow x = 0$ 2. $\|\alpha x\| = |\alpha| \|x\|$ 3. $\|x + y\| \leq \|x\| + \|y\|$

常用向量范数：

1. 1-范数：$\|x\|_1 = \sum_{i=1}^{n} |x_i|$
2. 2-范数：$\|x\|_2 = \sqrt{\sum_{i=1}^{n} x_i^2}$
3. $\infty$-范数：$\|x\|_\infty = \max_{1 \leq i \leq n} |x_i|$

定义 8.3 矩阵范数是从属范数（算子范数）： $$\|A\| = \max_{x \neq 0} \frac{\|Ax\|}{\|x\|} = \max_{\|x\|=1} \|Ax\|$$

常用矩阵范数：

1. 1-范数（列和范数）：$\|A\|_1 = \max_{j} \sum_{i=1}^{n} |a_{ij}|$
2. $\infty$-范数（行和范数）：$\|A\|_\infty = \max_{i} \sum_{j=1}^{n} |a_{ij}|$
3. 2-范数（谱范数）：$\|A\|_2 = \sqrt{\lambda_{\max}(A^T A)}$
4. F-范数：$\|A\|_F = \sqrt{\sum_{i,j} a_{ij}^2}$

例题 8.1 用Gauss消去法解： $$\begin{cases} x_1 + 2x_2 + x_3 = 0
2x_1 + 2x_2 + 3x_3 = 3
-x_1 - 3x_2 + 8x_3 = 10 \end{cases}$$

解：

消去：

1. $m_{21} = 2$，$m_{31} = -1$
2. 第二行：$(0, -2, 1, 3)$
3. 第三行：$(0, -1, 9, 10)$

$m_{32} = 0.5$

1. 第三行：$(0, 0, 8.5, 8.5)$

回代：

1. $x_3 = 1$
2. $x_2 = \frac{3-1}{-2} = -1$
3. $x_1 = \frac{0 - 2(-1) - 1}{1} = 1$

解：$x = (1, -1, 1)^T$

例题 8.2 用Cholesky分解求 $A = \begin{bmatrix} 4 & 2 & -2
2 & 10 & 2
-2 & 2 & 5 \end{bmatrix}$ 的分解。

解：

$l_{11} = \sqrt{4} = 2$ $l_{21} = \frac{2}{2} = 1$，$l_{31} = \frac{-2}{2} = -1$ $l_{22} = \sqrt{10 - 1} = 3$ $l_{32} = \frac{2 - (-1)(1)}{3} = 1$ $l_{33} = \sqrt{5 - 1 - 1} = \sqrt{3}$

$$L = \begin{bmatrix} 2 & 0 & 0
1 & 3 & 0
-1 & 1 & \sqrt{3} \end{bmatrix}$$

基础练习

1. 用Gauss消去法解：$\begin{cases} 2x_1 + x_2 + x_3 = 4
x_1 + 3x_2 + 2x_3 = 6
x_1 + 2x_2 + 2x_3 = 5 \end{cases}$

2. 求矩阵 $A = \begin{bmatrix} 2 & 1 & 1
1 & 3 & 2
1 & 2 & 2 \end{bmatrix}$ 的Doolittle分解。

3. 用追赶法解三对角方程组（$n=4$）：$a_i = 1$，$b_i = 4$，$c_i = 1$，$d = (5, 6, 6, 5)^T$。

进阶练习

4. 证明：若 $A$ 严格对角占优，则Gauss消去法中所有主元非零。

5. 证明Cholesky分解的存在唯一性。

6. 设 $A = LU$，证明 $\det(A) = \prod_{i=1}^{n} u_{ii}$。

编程实践

7. 编写列主元Gauss消去法程序。

8. 实现Cholesky分解算法，并与numpy.linalg.cholesky比较。

1. 李庆扬等. 数值分析（第5版）. 清华大学出版社, 2008. 2. Golub G H, Van Loan C F. Matrix Computations (4th ed.). Johns Hopkins University Press, 2013.