数值线性代数

凸优化算法需要反复求解线性方程组。实际计算中，矩阵的结构、条件数和分解方法会影响计算量、存储量与数值误差。本页介绍常见矩阵分解及其在线性方程求解中的作用。

矩阵结构与计算代价

对一般稠密的 $n\times n$ 矩阵，存储所有元素需要 $O(n^2)$ 空间，使用标准消元法求解线性方程组通常需要 $O(n^3)$ 运算。若矩阵是带状或稀疏的，利用其结构可以减少存储和计算；不过消元过程中可能出现新的非零元素（称为填充），因此稀疏矩阵的计算代价还取决于变量排序和分解产生的填充量。

矩阵的条件数衡量问题对输入扰动的敏感程度；算法的数值稳定性则描述计算过程如何传播舍入误差。条件数差的问题，即使使用稳定算法，结果也可能对数据误差敏感。两者是不同来源，分析求解误差时应分别考虑。

使用分解求解线性方程组

求解 $Ax=b$ 时，通常先分解矩阵，再通过三角方程组求解，而不显式计算 $A^{-1}$。例如若 $A=LU$，其中 $L$ 为下三角矩阵、$U$ 为上三角矩阵，则先解 $Ly=b$，再解 $Ux=y$。多个右端项共用同一个 $A$ 时，可以重复使用其分解结果。

LU 分解

带部分主元的 LU 分解通常写作

$$PA=LU,$$

其中 $P$ 是置换矩阵。对非奇异方阵，该分解把消元过程表示为一次行置换和两个三角矩阵。主元选取有助于控制舍入误差；矩阵若奇异或接近奇异，仍需结合秩和条件数判断问题是否适定。

Cholesky 分解

若 $A$ 对称正定，则存在唯一的下三角矩阵 $L$（对角线元素为正），使得

$$A=L{L}^{\mathrm{\top }}.$$

于是 $Ax=b$ 可通过解 $Ly=b$ 和 $L^{\mathrm{\top }}x=y$ 完成。Cholesky 分解利用对称性，通常比一般 LU 分解更省计算和存储。若 $A$ 仅半正定或不定，标准 Cholesky 分解不一定适用。

LDL${}^{\mathrm{\top }}$ 分解

实对称矩阵常可通过带主元的对称消元写成

$$PA{P}^{\mathrm{\top }}=LD{L}^{\mathrm{\top }},$$

其中 $L$ 为单位下三角矩阵，$D$ 为对角或小型分块对角矩阵。它避免对特征值进行开平方，适用于更广泛的对称矩阵，包括不定矩阵；求解时同样转化为置换和三角方程组。优化算法中的 KKT 系统常为对称不定系统，因此这一类分解很有用。

分块消元与 Schur 补

对分块线性方程组

$$\left[\begin{array}{cc}A& B\\ C& D\end{array}\right]\left[\begin{array}{c}x\\ y\end{array}\right]=\left[\begin{array}{c}u\\ v\end{array}\right],$$

若 $A$ 可逆，先由第一行消去 $x$，得到

$$(D-C{A}^{-1}B)y=v-C{A}^{-1}u.$$

矩阵 $D-C{A}^{-1}B$ 是相应的 Schur 补。若其中一个分块系统可以便宜地求解，就能用 Schur 补把较大的系统化简为较小的系统。计算实现时应通过分解和求解来应用 $A^{-1}$，避免显式形成逆矩阵。Schur 补的定义及分块逆公式见线性代数。

欠定线性方程组

当 $A\in {\mathbf{R}}^{m\times n}$ 且 $m<n$ 时，方程 $Ax=b$ 若相容，通常有多个解。全部解可表示为一个特解加上零空间中的向量：

$$x=x_p+z,z\in \mathcal{N}(A).$$

许多问题需要其中 Euclid 范数最小的解。若 $A$ 满行秩，将 $A^{\mathrm{\top }}$ 作薄 QR 分解 $A^{\mathrm{\top }}=QR$，其中 $Q^{\mathrm{\top }}Q=I$、$R$ 为可逆上三角矩阵，则最小范数解为

$$x_{\min }=Q{R}^{-\mathrm{\top }}b.$$

若矩阵秩不足，可用 SVD 或伪逆刻画最小范数解；伪逆的定义见线性代数中的 SVD 与伪逆。数值计算时，QR 或 SVD 通常比先构造正规方程 $A{A}^{\mathrm{\top }}y=b$ 更稳健，因为正规方程会平方非零奇异值，从而可能恶化条件数。

参考

本页对应 Boyd 与 Vandenberghe 的《Convex Optimization》附录 C：数值线性代数背景，重点整理矩阵结构、分解求解、分块消元和欠定方程组。