QR 分解可以不显式形成 就求解最小二乘问题。要把这个想法变成算法,需要一种既能经济地消去许多分量、又能保持欧氏(Euclidean)长度的方法。Householder 反射只用一个向量就能做到这一点。
将向量反射到坐标轴
定义 4.2.1
(Householder 反射)
对非零 ,Householder 反射定义为
它关于垂直于 的超平面反射。
定理 4.2.2
(反射的性质与到第一坐标轴的反射)
设 , 如 (1)。则 且 ,所以 ,并且对每个 都有 。此外,给定非零 ,令 ;当 时取 ,否则取 。令
则 除第一项外的所有分量均为零。
证明
(由两个内积算出 )
记 ,则 , 对称,且 。因此 ,。对 (2),由 得 ,。 的第一分量绝对值为 ,故 ,且 。因此 。对 的约定消除了符号歧义;若 ,则不需要反射。
证明透视
为什么这样选择符号?
证明对两种符号都成立;在精确算术中, 同样给出一个反射。符号改变的是 的大小:由于 ,两个内积都是 的倍数,而它从不很小,所以 中的除法是安全的。 第一分量的绝对值是 ,所以形成它时不会相减两个几乎相等的正数。对小 ,若 ,所选向量的第一分量为 ,接近 。另一种选择 的第一分量为 ,只有 的阶,容易发生消去误差。
这个符号选择保护了一处关键计算,但它本身并没有证明完整的浮点后向误差定理。当分量极大或极小时,稳健的范数计算和缩放仍然重要。
构造并应用 QR
对 ()的第 列,只对第 行作用一个反射,将当前列的尾部变成 的倍数。由此得到下面的分解。
定理 4.2.3
(Householder QR 分解)
设 ,。存在反射 (其中某些可以等于 ),使
其中 为上三角矩阵。若 列满秩,则 非奇异,最小二乘解就是 的解,残差范数为 。
证明
(对列数归纳)
设 步之后,矩阵 的前 列在对角线以下为零。令 为第 列中第 行的部分。若 ,按 (2) 由 构造 ,并取 ;它仍是反射(向量 前面补 个零),而且只作用于第 行。前 列在这些行上为零,所以不变;第 列则在对角线以下变为零。若 ,取 。第 步之后,矩阵形如 , 为上三角。每个 都是对称正交的,所以 正交,且 。正交变换保持秩,故 ,列满秩即使 非奇异。最后,,当且仅当 时最小。
若某列尾部为零,可以跳过该反射;此时取 ,恒等式仍成立。将反射作用于矩阵块 时,计算 。只需存储向量 ,不必存储稠密的 。按构造顺序将相同反射作用于 ,就得到 ,无须显式形成 。当 时,更新尾随矩阵块的算术运算量为 ;为完成这个求解,不必构造稠密的完整 。
例题
例题 4.2.4
(首项为正的向量的反射)
取 ,则 、、。由 (1) 得
前导分量为负是有意的。如果后续约定要求对角线为正,可以另行调整符号;正交性和最小二乘解并不要求对角线为正。
例题 4.2.5
(用两个反射解最小二乘问题)
设 ,。第一列 有 、、、,所以 。对第二列 ,,故 。因此
尾部 的 ,且第一分量为负,所以 ,作用于第 行的向量为 ,。它把尾部映为 ,于是 。
对 :,所以 。对其尾部,,且 。故 。在 中回代得 ,再由 得 ,残差范数为 。
检验:正规方程 对 成立,而 的范数为 。 的对角线符号不一致,这并不要紧。
例题 4.2.6
(首项为负时的符号分支)
取 。此时 ,所以 、、,。于是
另一种选择 在精确算术中同样给出反射,,但它的第一分量是差 。对 ,同样的形式就是上面证明透视所述的消去误差。
反例模式
零主元不能完整诊断秩
对 ,第一列尾部为零,但 的秩为一。跳过这一反射不会使整个矩阵变为零。在浮点计算中,仅凭一个小对角项也不能普遍确定数值秩;可能需要主元选取或奇异值,并明确容差。
常见错误
常见错误
(按错误次序把反射作用于 b)
要得到 ,必须先作用 。在上面的两反射例子中,若先作用 再作用 ,得到 而不是 ,回代便会得出 ,而不是 。
常见错误
(形成稠密的反射矩阵)
把 建成 矩阵再相乘,对 列的矩阵块需要 次运算。公式 只需 次,而且只需要向量 。
练习与解答
快速检查
(按上述符号约定,对 计算一个反射矩阵。)
先决定 ;留意 时的约定。
解答 · 答案
、、,所以 ,且 。
快速检查
(为什么 作用后保持 ?)
计算 。
解答 · 答案
因为 :。
快速检查
(在 (3) 中,为得到 ,应按什么顺序将反射作用于 ?)
把 从右往左读。
解答 · 答案
先作用 ,再作用 ,依次到 。
快速检查
(Householder QR 的 对角线必须为正吗?)
看上面的第一个例子。
解答 · 答案
不必; 的对角元可以为负,若约定需要,可另行调整符号。