张叶安的小站

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
====== 第八章 直接法 ======

===== 8.1 引言 =====

线性方程组是科学计算中最基本的问题之一。给定 $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消去法及其变形。

===== 8.2 Gauss消去法 =====

==== 8.2.1 基本思想 ====

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

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

==== 8.2.2 消去过程 ====

记 $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)}$。

==== 8.2.3 回代过程 ====

$$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$$

==== 8.2.4 计算量分析 ====

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

**回代过程**：
  - 乘除法次数：$\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$ 较大时）

===== 8.3 列主元Gauss消去法 =====

==== 8.3.1 主元为零的问题 ====

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

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

==== 8.3.2 列主元消去法 ====

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

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

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

===== 8.4 LU分解 =====

==== 8.4.1 矩阵的LU分解 ====

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

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

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

==== 8.4.2 Doolittle分解的计算 ====

设 $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$$

==== 8.4.3 用LU分解解方程组 ====

$Ax = b \Leftrightarrow LUx = b$

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

===== 8.5 Cholesky分解 =====

==== 8.5.1 对称正定矩阵 ====

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

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

==== 8.5.2 Cholesky分解 ====

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

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

==== 8.5.3 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}}$$

==== 8.5.4 改进的Cholesky分解 ====

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

===== 8.6 追赶法 =====

==== 8.6.1 三对角方程组 ====

三对角方程组形如：
$$\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}$$

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

==== 8.6.2 追赶法 ====

设 $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.7 向量与矩阵范数 =====

==== 8.7.1 向量范数 ====

**定义 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-范数**：$\|x\|_1 = \sum_{i=1}^{n} |x_i|$
  - **2-范数**：$\|x\|_2 = \sqrt{\sum_{i=1}^{n} x_i^2}$
  - **$\infty$-范数**：$\|x\|_\infty = \max_{1 \leq i \leq n} |x_i|$

==== 8.7.2 矩阵范数 ====

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

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

===== 8.8 典型例题 =====

**例题 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}$$

**解**：

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

$m_{32} = 0.5$
  - 第三行：$(0, 0, 8.5, 8.5)$

回代：
  - $x_3 = 1$
  - $x_2 = \frac{3-1}{-2} = -1$
  - $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}$$

===== 8.9 习题 =====

**基础练习**

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.