LU、QR 与 Cholesky 分解

层级：C｜深入

1. 为什么要分解矩阵

矩阵分解像把复杂服务拆成职责清晰的组件。求解方程、最小二乘、行列式、采样和数值稳定性都可利用特殊矩阵结构。公式里出现逆矩阵时，实际实现几乎总应选择合适分解。

2. LU 分解

许多方阵可写成

A=LU,

其中 $L$ 是下三角矩阵， $U$ 是上三角矩阵。高斯消元把 $A$ 变为 $U$ ，消元倍数记录在 $L$ 中。

实际为稳定性需要行交换：

PA=LU,

$P$ 是置换矩阵，表示部分主元选择。

3. 用 LU 解方程

要解 $Ax=b$ ，若 $PA=LU$ ：

计算 $Pb$ ；
解下三角系统 $Ly=Pb$ （前代）；
解上三角系统 $Ux=y$ （回代）。

分解成本约 $O(n^3)$ ，每个新右端项的两次三角求解约 $O(n^2)$ 。同一 $A$ 对多个 $b$ 时复用分解非常划算。

行列式也可由

\det(A)=\det(P)\prod_iL_{ii}\prod_iU_{ii}

得到；常见约定把 $L$ 对角设为 1。

4. QR 分解

对 $A\in\mathbb R^{m\times n}$ （常见 $m\ge n$ 、满列秩）：

A=QR,

$Q\in\mathbb R^{m\times n}$ 列标准正交， $R\in\mathbb R^{n\times n}$ 上三角。这是精简 QR；完整 QR 会把 $Q$ 扩为 $m\times m$ 正交矩阵。

Gram–Schmidt 可构造 QR，但实际常用 Householder 反射或 Givens 旋转，稳定性更好。

5. QR 解最小二乘

求

\min_x\|Ax-b\|_2.

若 $A=QR$ ：

\|Ax-b\|_2 =\|QRx-b\|_2.

利用正交变换保持长度，正规条件简化为

Rx=Q^Tb.

再回代求解。相比正规方程 $A^TAx=A^Tb$ ，QR 不会把条件数平方，通常更稳定。

6. Cholesky 分解

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

A=LL^T.

也可写成 $A=R^TR$ 。Cholesky 是针对正定矩阵的高效“平方根”，计算量约为一般 LU 的一半，且无需主元交换（理论精确算术下）。

7. Cholesky 的用途

解正定系统

先解 $Ly=b$ ，再解 $L^Tx=y$ 。

计算 log-determinant

\log\det(A)=2\sum_i\log L_{ii}.

生成多元高斯样本

若 $z\sim\mathcal N(0,I)$ 且 $\Sigma=LL^T$ ：

x=\mu+Lz\sim\mathcal N(\mu,\Sigma).

因为 $\operatorname{Cov}(Lz)=LL^T=\Sigma$ 。

高斯过程

训练和采样需要对核矩阵加噪声后做 Cholesky；数值失败常提示矩阵不够正定或条件很差。

8. 三种分解怎样选择

问题	首选思路
一般方阵线性系统	带主元 LU
矩形最小二乘	QR；秩亏时 SVD
对称正定系统	Cholesky
需要秩、零空间、稳健伪逆	SVD
稀疏大型系统	使用稀疏专用直接法或迭代法

库的高层 solve/lstsq 常会根据结构选择算法。若知道矩阵对称正定，应告诉库或调用对应接口。

9. “加抖动”与正定性

核矩阵或协方差矩阵理论上 PSD，但浮点误差、重复点和近相关会让 Cholesky 失败。常加

A_\epsilon=A+\epsilon I

其中 $\epsilon$ 是很小正数（jitter）。它提高最小特征值并改善条件。大小要相对数据尺度选择；过大将明显改变模型。

10. 分解不等于显式构造所有因子

高性能求解器可能原地存储因子，或只使用隐式 Householder 向量。工程上关注接口和性质，不要依赖内部矩阵恰好如何布局。

易错点

并非所有矩阵都能在无置换下做普通 LU。
Cholesky 要求对称正定，不只是对称或半正定。
QR 中 $Q$ 可能是精简形状，不一定方阵。
用正规方程解最小二乘会平方条件数。
chol 失败不能简单用很大 jitter 掩盖，应检查数据和建模原因。

常见问答

Q1：为什么三角系统容易解？

每个方程只依赖已知或后续少量变量，可按顺序前代/回代，复杂度 $O(n^2)$ 。

Q2：SVD 更稳健，是否所有问题都用 SVD？

SVD 信息最全但通常更慢。矩阵结构明确且满秩时，LU/QR/Cholesky 更高效。

Q3：协方差矩阵 PSD 为什么不能总做 Cholesky？

Cholesky 标准形式要求严格正定。PSD 若有零特征值，某个对角主元会为零，分解可能失败或需带主元变体。

练习

若 $A=LU$ ，写出解 $Ax=b$ 的两步方程。
为什么 QR 解最小二乘不必求 $A^TA$ ？
$A$ 特征值为 $(2,1,0)$ ，能否做标准 Cholesky？
若 $\Sigma=LL^T$ 且 $z$ 协方差为 $I$ ，证明 $Lz$ 协方差为 $\Sigma$ 。
同一矩阵要解一千个不同 $b$ ，为什么应缓存分解？

答案与提示

$Ly=b$ ，再 $Ux=y$ ；有置换时右侧为 $Pb$ 。
用 $A=QR$ 后直接解 $Rx=Q^Tb$ 。
不能，它只半正定非正定。
$\operatorname{Cov}(Lz)=LIL^T=LL^T$ 。
昂贵的 $O(n^3)$ 分解只做一次，每个右端只做 $O(n^2)$ 三角求解。