动机
矩阵分解之所以有用,是因为因子比原矩阵容易处理。可靠性还要求回答另一个问题:计算所得因子及三角求解,究竟精确解决了哪个邻近问题?这与邻近问题的解是否接近原解是两回事。后向误差描述数据改变多少,条件则描述这些改变可能怎样影响答案。
本节在前面消元入门的基础上研究增长与分解残差,再发展矩形最小二乘的正交 QR。证明将精确代数与明确假设的浮点误差模型分开,使“稳定”成为有条件的数学陈述,而非算法名称附带的承诺。
定义
定义 14.1.1
(部分选主元与增长因子)
对非奇异方阵,部分行选主元消元在精确算术中给出 。 记录每次交换, 是单位下三角, 是上三角。后续交换也必须移动 已存储的相应乘子。部分选主元保证精确乘子的绝对值不超过一。增长因子定义为消元过程中所有活动矩阵的最大元素绝对值,除以初始矩阵的最大元素绝对值。
定义 14.1.2
(分解残差)
计算因子的精确分解残差为
这是数学上的差,在计算机上求它还会引入误差;它不同于解残差 。以下绝对值矩阵逐项取值,例如 是分量不等式。若 ,记 。
定义 14.1.3
(最小二乘、完整 QR 与 Householder 反射)
对于 、 且列线性无关,最小二乘求 的极小值。完整正交 QR 为
其中 是非奇异上三角。非零向量 定义 Householder 反射矩阵 ,它对称且正交。作用时用 ,不必存储稠密矩阵。
概念视角结构
三种残差,三个问题
分解残差检查因子是否代表原矩阵,系统残差检查候选解是否满足方程,最小二乘残差则包含不可避免的模型失配,在最优点应与模型空间正交。同一个词不能替代它们不同的数学职责。
定理/命题
定理 14.1.4
(从因子及求解误差得到邻近系统)
设计算中的三角求解满足
其中 、。则存在矩阵 ,使 且
对任意 ,使它成为精确解、并且只改变矩阵的最小 Frobenius 范数扰动为
定理 14.1.5
(正交约化解决满列秩最小二乘)
写 ,其中 。唯一最小二乘解满足 ,最小残差范数为 ,等价条件为 。对奇异值为 的矩形满列秩矩阵,定义 。于是
因此法方程矩阵的条件数是原矩阵条件数的平方。正交约化避免形成这个矩阵,却不能把所有最小二乘问题变得条件良好。
证明思路或证明
分解误差只是求解误差的一部分
证明
(组合出邻近系统)
代入两次三角关系,得 。因为 ,可取
逐项取绝对值即得上界。若绝对值因子的乘积很大,仅有小 并不足够。反过来,经过适当归一化、可靠计算的小解残差,可认证该次求解的后向误差小,即使最坏因子界保守。它本身不认证前向误差小;下面的残差求值预算也必须计入。
对第二部分,,所以 。外积的 Frobenius 范数等于两个向量范数之积。任何其他满足 的矩阵都满足 ,因此该扰动最小。这里允许任意矩阵扰动;要求保留稀疏结构或逐项相对误差时,是另一个问题。只改变右端则写成 。
当 ,前向误差恒等式又给出
残差与矩阵扰动使用不同的归一化;两者都不能从前向保证中去掉条件数。
部分选主元究竟控制什么
命题 14.1.6
(部分选主元的增长界)
在精确算术中,对非奇异 矩阵作部分选主元消元,增长因子至多为 。
证明
(每次更新至多使活动最大值翻倍)
活动更新为 。因为 ,有 ,不超过当前活动最大值的两倍;所以在 个消元步骤中,每步活动最大值至多翻倍。行交换只重排元素,不改变最大值。
这是指数界,不是普遍的小常数;例题给出在明确平局规则下达到该界的矩阵族。
常见错误
(把乘子有界当作增长小)
部分选主元保证 ,这只控制局部除法。增长因子追踪反复更新;即使乘子有界,它仍可达到 ,例题中的矩阵 正是如此。把两者混为一谈,是许多错误稳定性断言的来源。
普通回代使用模型 、。假设主元非零、,没有溢出,也没有超出这个相对误差模型的运算。展开一行的乘积、累加及除法,可把舍入因子分配给三角系数;每个系数涉及至多 个因子,得到 中的 。这说明上面三角求解假设的来源。要进一步用输入及舍入约束 ,仍需针对分解算法的分析;本节保留实际分解残差,而不虚构其大小。
残差计算本身也需预算。对于直接舍入的矩阵向量乘积及相减,一个保守分量界为 ,要求相同正常运算模型及 。把一行所有可能的乘法、加法、减法因子计入即可得到此较松常数。因此显示为零的残差未必是精确零。
用正确符号构造 QR
证明
(反射与正交不变性)
对非零活动列 ,令 、,约定 ,再令 。直接计算
所以 。 第一分量的绝对值为 ,避免两个接近的正数相减。若活动向量为零,则不需反射。逐列把反射作用于剩余行列,乘积得到 ;列满秩保证 非奇异。
正交不改变二范数,故
第一项的唯一最小值为零。在任意候选点对位移 展开目标函数,其一次项为 。它消失正是残差正交条件,而非零 的 保证唯一性。 的特征值是奇异值的平方,遂得条件数关系。
固定设计矩阵,只扰动右端 ,解变化为 ,其中 是 前 列;其范数至多 。与列空间正交的变化只改变残差,不改变拟合系数。扰动设计矩阵则是不同的敏感性问题,尤其当最优残差很大时。因此,三角求解的残差小或避免法方程,本身都不能认证不确定或近相关数据的系数准确性。
明确的浮点 QR 误差约定
存储的浮点矩阵不必严格正交。以下条件模型给出完整传播证明。假设每步计算可用某个精确正交 表示为
并且最终存储矩阵为 。
证明
(经精确反射传回局部误差)
经过 步,令 。正交不变性给出 。将每个局部误差通过先前正交因子搬回原坐标,再相加,得到精确关系
对右端使用同一组反射及类似局部界,得到 。若三角求解另有 且 ,将其吸收到 ,总矩阵界变成 。只要扰动后三角因子仍非奇异,返回向量就精确极小化一个邻近最小二乘问题。
证明透视
局部误差为何相加而非相乘
假设是各步的局部约定:每一步都是对稍受扰动的数据作用一个精确正交的 。正交性用了两次。第一,,所以每步至多把范数放大 倍。第二,也是关键一步,每个局部误差 都经 传回原始数据,而这不改变它的范数。于是误差相加,,几何级数收束为 。最后三角求解的扰动也以同样方式吸收。若约定中的反射只是近似正交,传回一步便不再保持范数,界中需要额外一项; 的符号选择之所以重要,是因为它帮助实现达到局部约定,而不是因为它出现在此论证中。
仔细实现的 Householder 程序,在适当舍入假设及小 下可取得 量级的局部界,其中 是与内核有关的适度常数。因此该界依赖维数,并非只有单位舍入误差。上面证明从明确约定开始,并未推导每种实现的全部常数。范数求值应缩放以避免可避免的溢出或下溢,反射构造与作用也必须遵守所分析的操作顺序。LAPACK 最小二乘误差分析给出其满秩程序的相应范数后向解释;这不是普遍小前向误差的承诺。
例题详解
例题 14.1.7
(反射符号是有意选择的)
取 ,、、。于是
若选相反目标符号,第一分量要形成 ;当 更接近范数时,这种相减会产生严重抵消。精确代数中两种符号都可以,算术性质却不同。
例题 14.1.8
(部分选主元仍可能指数增长)
考虑
若平局保留当前第一行,部分选主元不交换,每个乘子为 。 前三个对角元素为一,除末列以外的严格上三角元素全部为零,末列为 。初始最大值为一,所以增长为八。相同的 维矩阵族得到末列 。这证明可能增长,并非宣称这个可精确表示的小例子必然算错。
例题 14.1.9
(不形成法方程的直线拟合)
在 对数据 拟合 。设计列为 、。可核验的正交单位基为
得到 ,。回代给出斜率 、截距 。残差为 ,范数为 ,与两个设计列都正交。这里列出完整 是为了检查结果,Householder 实现无需显式存储它。
常见错误
反例模式
最小二乘残差大未必是求解失败
令 、,。唯一最小二乘解为零,残差范数为 ,因为未知标量无法改变第二个方程。任意大的残差都可能是精确最优结果。残差正交及后向误差回答的是残差大小本身无法回答的问题。
常见错误
(因为法方程精确就直接形成它)
法方程在精确数学中成立,但形成 会平方条件数,并给矩阵本身引入舍入。Householder 避免该步骤,却不会恢复近相关列中已缺少的信息。秩亏及欠定问题需要额外的秩与最小范数决策,不在本节满列秩定理内。
总结
选主元控制乘子,却允许指数最坏增长。分解及三角求解误差共同解释一个邻近系统,条件决定其解可能改变多少。Householder 将满秩最小二乘化为三角求解,不必形成法方程;明确的局部后向约定解释这个精确构造如何成为范数稳定方法。
练习
快速检查
(对 作部分选主元分解,解 。同时检查排列及解。)
第一个主元是第一列中较大的元素 。
解答 · 答案
交换两行,,,乘积为 。解 得 ,再回代得 。代回原矩阵得到 。
快速检查
(候选解为 、残差为 。求使其成为精确解的最小 Frobenius 范数矩阵扰动,并证明该范数为 。)
使用 。
解答 · 答案
,乘候选向量得到残差,其 Frobenius 范数为 。任何可行 都满足 ,所以最小,包括零的情况。
快速检查
(对 构造上述符号规则的反射,直接核验正交及作用,并解释第一分量为零时的约定。)
由 得 。
解答 · 答案
约定给出 、,故 。直接乘得 、。约定 只是为了使公式有确定意义:当 ,两种目标符号都给出 ,都不涉及抵消。
快速检查
(用常数最小二乘拟合 ,求残差向量及范数,核验正交条件。最优残差非零是否证明数值不稳定?)
设计矩阵是列向量 。
解答 · 答案
设计列为 ,拟合常数是平均数三。残差 的范数为 ,分量和为零,因此满足 。这是精确唯一最优解;非零残差表示模型失配,并非求解器造成的误差。