LU 与 QR 分解

为什么要分解矩阵？

解一次 A*x = b 很容易。但实际中你常常要用同一个 A、每次换一个新的 b 来反复求解——多个右端项，一个矩阵。每次都从头重做消元纯属浪费。而分解把最费力的部分只做一次，并把结果存成若干更简单矩阵的乘积。

更简单的矩阵——三角矩阵或正交矩阵——用起来很容易求解。所以这一级的核心玩法就是：把一个难对付的矩阵变成若干容易矩阵的乘积。

高斯消元通过行相减把 A 变成上三角矩阵 U。LU 分解不过是把你用过的那些乘数记在一个下三角矩阵 L 里。结果就是 A = L*U：U 是消元得到的，L 记录了你是怎么走到那一步的。

A = L*U
Solve A*x = b  ->  L*y = b   (forward)
                    U*x = y   (backward)

存好 L 和 U 之后，每个新的 b 只需两次便宜的三角求解，而不必整套消元重做一遍。

QR 分解把 A 写成 A = Q*R，其中 Q 的各列是标准正交的，R 是上三角的。这正是对 A 的各列做格拉姆-施密特，而 R 负责记账，记下长度与重叠量。由于 Q 的各列标准正交，乘以 Q 不会拉伸或扭曲——这正是 QR 在数值上稳定的原因。