参考章节目录

Iteriative Methods for Sparse Linear Systems P12

MATH 5330: Computational Methods of Linear Algebra—Lecture Note 10: Householder Transformation—Xianyi Zeng—Department of Mathematical Sciences, UTEP

Abstract

关于A=QR的分解，有三种方法：Gram、Givens、Householder，Givens我不熟悉、但好像和旋转有关、可以保留A’s columns的长度。HouseHolder也有这个优点。

大致了解

Gram-Schmidt的方法是通过一步一步地将新的列A_j，减去其在已正交化的q₁，q₂，q_(j-1)的投影从而得到新的正交项以此构成Q，HouseHolder采取了另外一种完全的方法，其一步一步地将待分解矩阵A，分解成Echelon matrix，当然这个分解过程不是简单的Gaussian Decomposition，而是用了HouseHolder算子，下面翻译一下参考书目1中的分解步骤

什么是Householder算子（Householder矩阵的几何表示）

Householder算子是一个矩阵，其形式是P = I - 2ww^T，这里我一般记作P_w，因为P是由w决定的，后续我们也是针对待分解矩阵的每一列来构造对应的w，从而得出针对每一列的P。

易证，P是Ortogonal矩阵、且是Symmetric矩阵：P^T=P，P^TP=I。

注意，我们后续在选择w的时候，要让其是2-norm unity的向量。

从几何上来看，Px表示的就是x,关于空间{w}^⊥的镜像。画图表示就是

v就是上文中的w、H_v就是上文中的P_w。

如何为每一列X_j构造每一个HouseHolder矩阵P_j

针对向量x、构造其P_w

一直在强调，HouseHolder矩阵P_j的作用就相当于Gaussian Elimination的消除矩阵（应该这么叫吧）。下面以第一列为例，假设第一列是x，那么目的肯定是

α是一个张量，后面我们会知道其实就是x的长度。现在将P的表达式代入:

至此、我们就用通过x、求得了一个w，使得x在P_w的作用下可以变换至||x||e₁，w的表达式如下

针对矩阵的每一列，进行构造P

先看矩阵的第一列x₁，我们直接用x₁替换掉1.17中的x，即得出w₁，从而得出P₁。记X₁是第一次HouseHolder变换后的矩阵（形如已经完成一次Gaussian Elimination的矩阵）

X₁的第一个元素为α，其余元素为0。

现在我们看一下第k次HouseHolder变换的情况，操作对象当然是已经完成k-1次的矩阵了鸭。表达式如下：

矩阵在列k-1前是一个上三角矩阵。进行下一步时，前k-1列保持不变，根据第k列的向量x_k，确定一个w，然后生成P。w的形状是1至k-1个元素都是0，这样才保证了前k-1列不变。P_k的推导如下

当k=0时，即第一次变换的P，此时的β=αe₁，符合上文的描述。

构造A=QR

到这里，我们就描述完了整个X的分解过程，使得x可以分解成

这里仅需要一小步、就可以将上式变成A=QR的美丽式子了鸭。(下面这个过程，即将R那部分中的0，转移到P中去，形成Q).我们将1.22表示成下面的式子1.23，R是mxm的矩阵。

我们在前面给出了P_i是对称、且正交的，所以我们把P放到右边:

我们用E_m表示I的前m列，shape=(n,m)。可表示如下

令Q=P^TE_m，这表示取P^T的前m列。我们可以验证：

所以，Q是我们想要的Q(Orthonomal)。分解成功！