高斯消元法与 LU 分解

高斯消元法与 LU 分解

学习目标

完成本节后，你将能够： - 系统地进行高斯消元 - 理解主元、乘数、回代 - 理解 LU 分解的本质和意义 - 用 Python 实现消元法

1. 消元法：为什么是它？

问题：解 \(A\mathbf{x} = \mathbf{b}\) 的最可靠方法是什么？

高斯消元法的思想很简单——通过**行操作**将矩阵简化，使得解变得明显。

### 1.1 2×2 示例

\[\begin{cases} 2x + 4y = 10 \\ 3x + y = 5 \end{cases} \implies \begin{bmatrix} 2 & 4 \\ 3 & 1 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} 10 \\ 5 \end{bmatrix}\]

步骤 1：消去第二行的 x——第二行减去 \(\frac{3}{2}\) 倍第一行

\[\begin{bmatrix} 2 & 4 \\ 0 & -5 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} 10 \\ -10 \end{bmatrix}\]

步骤 2：回代——\(-5y = -10 \implies y = 2\)，\(2x + 8 = 10 \implies x = 1\)

主元 (Pivot)：对角线上的 2 和 -5 就是主元。它们是我们消元的"支点"。

### 1.2 主元的重要性

  • 如果某个主元为零，需要交换行
  • 如果即使交换行也无法得到非零主元，矩阵不可逆（奇异）
  • 主元的个数 = 矩阵的秩

2. 复杂示例：3×3

\[\begin{bmatrix} 2 & 1 & -1 \\ -4 & -1 & 3 \\ 2 & 3 & 1 \end{bmatrix} \mathbf{x} = \begin{bmatrix} 1 \\ -5 \\ 7 \end{bmatrix}\]

消元过程： 1. 主元 2：\(R_2 \leftarrow R_2 + 2R_1\)，\(R_3 \leftarrow R_3 - R_1\) 2. 主元 1：\(R_3 \leftarrow R_3 - R_2\) 3. 回代得到 \(x=1, y=2, z=3\)

3. 消元矩阵

每次行操作 = 左乘一个**初等矩阵**。

\[E_{21} = \begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}\]

\[E_{21}A = \begin{bmatrix} 2 & 1 & -1 \\ 0 & 1 & 1 \\ 2 & 3 & 1 \end{bmatrix}\]

意义：\(E_{21}\) 表示"第 2 行加 2 倍第 1 行"。

4. LU 分解

### 4.1 消元过程的矩阵表达

\[E_{32}E_{31}E_{21}A = U\]

其中 \(U\) 是上三角矩阵。将这些消元矩阵求逆移项：

\[A = (E_{21})^{-1}(E_{31})^{-1}(E_{32})^{-1} U = LU\]

L 的秘密：\(L\) 的对角线下方的元素恰好就是消元时的乘数！

\[L = \begin{bmatrix} 1 & 0 & 0 \\ l_{21} & 1 & 0 \\ l_{31} & l_{32} & 1 \end{bmatrix}\]

\(l_{21}\) 就是消元时加在第 2 行上的第一行倍数。

### 4.2 为什么 LU 重要？

主要优势：求解多个右侧向量。

假设你要解 \(A\mathbf{x} = \mathbf{b}_1, A\mathbf{x} = \mathbf{b}_2, \ldots, A\mathbf{x} = \mathbf{b}_k\)。

传统方法：每次从零开始消元 → \(O(kn^3)\) LU 方法：一次分解 \(A = LU\)（\(O(n^3)\)），然后每次求解只需前向/回代（\(O(n^2)\)）

当 \(k\) 很大时，差异巨大。

import numpy as np

def solve_with_lu(A, b): """使用 LU 求解 Ax = b""" P, L, U = lu(A) # PA = LU # 解 Ly = P^T b（前向替换） y = np.linalg.solve(L, P.T @ b) # 解 Ux = y（回代） x = np.linalg.solve(U, y) return x

# 测试 A = np.array([[2, 1, -1], [-4, -1, 3], [2, 3, 1]]) b = np.array([1, -5, 7])

x_lu = solve_with_lu(A, b) x_direct = np.linalg.solve(A, b) print("LU 解:", x_lu) print("直接求解:", x_direct) print("匹配?", np.allclose(x_lu, x_direct)) ```

5. 行交换与置换矩阵

### 5.1 置换矩阵

交换两行的矩阵称为置换矩阵。

\[P = \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}\]

\(P A\) 交换了 \(A\) 的第一行和第二行。

### 5.2 PA = LU

当消元需要行交换时，分解变为：\(PA = LU\)。

6. 计算复杂度

  • 消元需要约 \(\frac{2}{3}n^3\) 次浮点运算
  • 回代需要约 \(n^2\) 次运算
  • \(n=1000\) 时，消元约 6.7 亿次操作，现代 CPU 约需 0.2 秒

7. Python 实现：完整高斯消元

def gauss_elimination(A, b):
    """完整高斯消元（带行选主元）"""
    n = len(A)

# 前向消元 for col in range(n): # 部分选主元 max_row = np.argmax(abs(Ab[col:, col])) + col if abs(Ab[max_row, col]) < 1e-12: raise ValueError("矩阵奇异") Ab[[col, max_row]] = Ab[[max_row, col]]

for row in range(col+1, n): factor = Ab[row, col] / Ab[col, col] Ab[row, col:] -= factor * Ab[col, col:]

# 回代 x = np.zeros(n) for i in range(n-1, -1, -1): x[i] = (Ab[i, -1] - Ab[i, i+1:n] @ x[i+1:n]) / Ab[i, i] return x

A = np.array([[3, 1, 2], [6, 3, 4], [3, 1, 5]]) b = np.array([0, 1, 3]) print("解:", gauss_elimination(A, b)) ```

8. 本节习题

  1. 对 \(\begin{bmatrix} 2 & 3 \\ 4 & 7 \end{bmatrix}\) 做 LU 分解（手工）
  2. 证明 \(\det(L) = 1\)（LU 分解中的 L）
  3. 为什么部分选主元在数值上很重要？
  4. 用 Python 比较：n=100 时，\(A^{-1}\mathbf{b}\) 和 LU 求解的速度差异
  5. 解释：当 \(A\) 正定时，消元不需要行交换

总结

- 高斯消元通过行操作将 \(A\) 变为上三角 \(U\) - \(A = LU\) 中 \(L\) 包含消元乘数，\(U\) 是最终上三角矩阵 - LU 的优势：一次分解，多次求解 - 部分选主元保证数值稳定性