为什么利用对称性?
高斯(Gauss)消元法适用于许多矩阵,但即使系数矩阵对称,仍须存储两个三角因子。对于实对称正定矩阵,一个三角因子便决定另一个。所得的 Cholesky 分解在精确算术下也无需选主元。相同矩阵要配合多个右端项时,这个特性尤其有用;但正定或分解成功并不意味着原系统的条件良好。
本节设 对称、,除非另有说明,计算均为精确算术。
定义 3.2.1
(正定矩阵与 Cholesky 因子)
若对每个非零 都有 ,则实对称矩阵 称为正定。 的 Cholesky 因子是对角元严格为正、满足 的下三角矩阵 。
逐列构造
由 可确定计算次序。已知第 列后,令
空和为零,平方根取正值。下面的定理说明正定输入保证这些运算有意义;仅仅写出平方根并不能证明被开方数为正。
定理 3.2.2
(存在性与唯一性)
实对称矩阵 正定,当且仅当存在对角元严格为正的下三角矩阵 满足 。此 唯一,上面的逐列公式可将它算出。
证明
(经 Schur 补作归纳)
先证正定性推出分解,对维数归纳。 时 ,结论成立。若 ,分块写为
这里 。对任意非零 ,取 ,则 且 ,所以 正定。归纳假设给出 ,其中 为对角元为正的下三角矩阵。因此
满足 。反复进行同样的分块步骤,得到逐列公式及正的被开方数。反过来,若 且 为对角元为正的三角矩阵,则 可逆,所以非零 满足 。
唯一性来自逐项比较: 先强制 ,再确定第一列其余元素。假设之前各列已确定,对角方程强制正值 ,非对角方程再确定每个 。归纳便确定全部元素。正对角约定不可省略:否则可以改变列的符号。
归纳中藏着一个不明显的测试向量选择,而唯一性部分依赖一个符号约定。下面的剖析把两者分开。
证明透视
Schur 补为何保证下一主元为正
关键一步是测试向量 。展开 ,取 ,交叉项便抵消,只剩 。这一个恒等式把正定性由 传给较小的 ,归纳才得以继续。它也解释逐列公式:第 步的被开方数是第 个 Schur 补的首元,而正定矩阵的对角元为正(),所以每个平方根都取自正数。
对称性用在分块本身:同一个向量 同时出现在 的下方及右方,所以一个因子 连同其转置已足够。反方向只用到对角元为正的三角矩阵可逆,因此 时 。唯一性在每条对角方程 处使用符号约定:若不要求 ,每一列都可乘以 。
求解并复用因子
算出 后,先用前代解 ,再用回代解 ,无需构造逆矩阵。对于稠密矩阵,按乘法和加法各计一次运算的惯例,分解约需 次运算;每对三角求解需 次。这是稠密情形的主导运算量,并非稀疏实现的保证:消元可能产生填充,排序也会影响存储量。
例题 3.2.3
(一次分解,多次求解)
取
第一列为 。第二个对角元为 ,而 。最后 ,故
对角元为正且 ,也证明了 正定。前代得 ,回代得 ;直接相乘可检验 。若第二个右端项为 ,可复用同一个 ,解为 。分解只需做一次,但计算机中的每次求解都有各自的算术误差。
哪些情况会失败?
反例模式
对称且对角元为正仍不足够
对称矩阵 的对角元为正,但 。第一个 Cholesky 主元为 ,第二个被开方数却是 。矩阵虽可逆,却不存在实分解 。对角元为正不能代替正定性。
正定与半正定之间的界线,在公式中清楚可见。
例题 3.2.4
(半正定矩阵遇到零主元)
取 。它对称,且 ,在 时取等号,所以 半正定而非正定。逐列公式给出 、,然后
乘积 确实等于 ,但对角元并非严格为正,所以这不是定理意义下的 Cholesky 因子。在更大的矩阵中,零主元也会使下一列的公式除以零。定理中的严格不等式正好排除这种情况。
例题 3.2.5
(正定但条件差)
即使 正定,较小的特征值也会使解敏感。例如 ,,其因子是 ,但二范数条件数为 。若 变为 ,解从 变为 :数据的相对变化 造成解的相对变化 。稳定的分解无法消除问题固有的敏感性。
常见错误
(以为分解成功就代表问题条件良好)
在精确算术下,完成的 Cholesky 分解证明了正定性,但对条件数的大小毫无说明,正如对角例子所示。溢出、输入不确定性和条件数须另行考虑。
常见错误
(判断计算所得的非正主元)
浮点计算出现非正主元,可能由于不定性,也可能由于接近奇异时的舍入;仅凭这一现象不能证明是哪一种。要断定 不定,需要更多证据,例如一个满足 的明确向量。
练习与解答
快速检查
(分解 ,并解 。)
解答 · 答案
第一列是 ,第二个对角元为 ,所以 。前代得 ,回代得 。相乘可验证。
快速检查
(对 ,确定何时存在实的正对角 Cholesky 因子。)
解答 · 答案
第一主元为 ,第二个被开方数为 ,所以恰在 时存在。 时矩阵奇异; 时二次型可取负值。由正定性定理也可得到同一结论。
快速检查
(如果 中 是对角元符号不受限制的可逆下三角矩阵, 是否必为正定?此时 是否唯一?)
解答 · 答案
正定:非零 有 ,所以 。但不唯一,例如 。要求对角元为正才能选出唯一因子。
证明针对规定的矩阵类别及精确算术;它本身不提供有限精度误差界、条件数、稀疏填充估计或不定矩阵的适用性。