13、线性系统直接法：高斯消元与 LU 分解的深入剖析

线性系统直接法：高斯消元与 LU 分解的深入剖析

1. 运算次数分析

高斯消元法和 LU 分解法都需要 $O(n^3)$ 次运算，具体分析如下：
-第一步：有 $n - 1$ 行需要化简，每行需要一次除法和 $n - 1$ 次乘法与减法，总共进行 $n - 1$ 次除法和 $(n - 1)^2$ 次乘法或减法。
-第二步：行数和列数各减少 1，此时有 $n - 2$ 次除法和 $(n - 2)^2$ 次乘法与减法。
-以此类推：最终得到 $\frac{(n - 1)n}{2}$ 次除法和 $\frac{(n - 1)n(2n - 1)}{6}$ 次乘法与减法，因此运算次数为 $O(n^3)$。

这个过程可以用以下表格总结：
| 步骤 | 除法次数 | 乘法与减法次数 |
| ---- | ---- | ---- |
| 1 | $n - 1$ | $(n - 1)^2$ |
| 2 | $n - 2$ | $(n - 2)^2$ |
| $\cdots$ | $\cdots$ | $\cdots$ |
| $n - 1$ | 1 | $1^2$ |

2. 行交换

并非所有非奇异矩阵都能进行 LU 分解，例如矩阵 $\begin{bmatrix}0 & -1 \ 1 & 1\end{bmatrix}$，其行列式为 1，但如果 $LU = A$，则 $\ell_{11}u_{11} = a_{11} = 0$，由于 $\ell_{1