Householder 變換於 QR 分解的應用

本文的閱讀等級：中級

目前已知三種主要的 QR 分解計算方法包括 Gram-Schmidt 正交化 (見“Gram-Schmidt 正交化與 QR 分解”)、Givens 旋轉 (見“Givens 旋轉於 QR 分解的應用”)，和 Householder 變換。本文介紹最後一種方法：利用特殊設計的 Householder 變換於矩陣的正交化簡 (orthogonal reduction)，從而得到 QR 分解。

令 $\mathbf{v}$ 為一 $n$ 維實向量， $\Vert\mathbf{v}\Vert=1$ ，Householder 變換矩陣具有以下形式 (見“特殊矩陣(4)：Householder 矩陣”)：

$H=I-2\mathbf{v}\mathbf{v}^T$

Householder 矩陣 $H$ 的幾何意義為基本鏡射 (反射) 變換，單位向量 $\mathbf{v}$ 是鏡射超平面 (hyperplane) 的法向量。直接計算可確認 $H$ 是對稱矩陣， $H^T=(I-2\mathbf{v}\mathbf{v}^T)^T=I^T-2\mathbf{v}\mathbf{v}^T=H$ ，並且是正交矩陣 (orthogonal matrix)，

$\begin{aligned} H^TH&=(I-2\mathbf{v}\mathbf{v}^T)(I-2\mathbf{v}\mathbf{v}^T)\\ &=I-4\mathbf{v}\mathbf{v}^T+4\mathbf{v}\mathbf{v}^T\mathbf{v}\mathbf{v}^T\\ &=I-4\mathbf{v}\mathbf{v}^T+4\mathbf{v}\mathbf{v}^T=I\end{aligned}$

所以 $H^2=H^TH=I$ ，也稱作對合 (involutory) 矩陣。

下面我們設計一特殊 Householder 矩陣。設 $\mathbf{x}$ 為一 $n$ 維非零實向量，為簡化符號，以下我們令 $\sigma$ 代表 $\mathbf{x}$ 的向量長度， $\sigma=\Vert\mathbf{x}\Vert$ 。考慮法向量

$\mathbf{v}=\displaystyle\frac{\mathbf{x}\pm\sigma\mathbf{e}_1}{\Vert\mathbf{x}\pm\sigma\mathbf{e}_1\Vert}$

其中 $\mathbf{e}_1=[1,0,\ldots,0]^T$ ， $\mathbf{x}$ 經鏡射變換 $H$ 的像為

$\begin{aligned} H\mathbf{x}&=(I-2\mathbf{v}\mathbf{v}^T)\mathbf{x}=\mathbf{x}-2(\mathbf{v}^T\mathbf{x})\mathbf{v}\\ &=\displaystyle\mathbf{x}-2\frac{(\mathbf{x}\pm\sigma\mathbf{e}_1)^T\mathbf{x}}{\Vert\mathbf{x}\pm\sigma\mathbf{e}_1\Vert^2}(\mathbf{x}\pm\sigma\mathbf{e}_1)\end{aligned}$

因為 $\mathbf{x}^T\mathbf{x}=\Vert\mathbf{x}\Vert^2=\sigma^2$ ，就有

$\begin{aligned} (\mathbf{x}\pm\sigma\mathbf{e}_1)^T(\mathbf{x}\pm\sigma\mathbf{e}_1)&=\mathbf{x}^T\mathbf{x}+\sigma^2\pm 2\sigma\mathbf{e}_1^T\mathbf{x}\\ &=2\mathbf{x}^T\mathbf{x}\pm 2\sigma\mathbf{e}_1^T\mathbf{x}\\ &=2(\mathbf{x}\pm\sigma\mathbf{e}_1)^T\mathbf{x}\end{aligned}$

合併以上結果即得

$\begin{aligned} H\mathbf{x}&=\mathbf{x}-(\mathbf{x}\pm\sigma\mathbf{e}_1)=\mp\sigma\mathbf{e}_1=\mp\Vert\mathbf{x}\Vert\mathbf{e}_1=\begin{bmatrix} \mp\Vert\mathbf{x}\Vert\\ 0\\ \vdots\\ 0 \end{bmatrix}\end{aligned}$

這個精心設計的特殊 Householder 矩陣 $H$ 將向量 $\mathbf{x}$ 「鏡射」至 $\mathbb{R}^n$ 的第一軸上，亦即 $H\mathbf{x}$ 除了第一元外，其他各元皆為零，此性質使得 Householder 矩陣得以應用於一般矩陣的正交化簡 ( $H$ 為正交矩陣，故得此名)。讀者或許納悶上述 Householder 矩陣的法向量 $\mathbf{v}$ 究竟如何導出？過程其實很簡單，假設 $H=I-2\mathbf{v}\mathbf{v}^T$ 滿足 $H\mathbf{x}=\mp\sigma\mathbf{e}_1$ ，合併兩式，即有

$\begin{aligned} H\mathbf{x}&=(I-2\mathbf{v}\mathbf{v}^T)\mathbf{x}=\mathbf{x}-2(\mathbf{v}^T\mathbf{x})\mathbf{v}=\mp\sigma\mathbf{e}_1\end{aligned}$

整理得到

$2(\mathbf{v}^T\mathbf{x})\mathbf{v}=\mathbf{x}\pm\sigma\mathbf{e}_1$

這指出 $\mathbf{v}$ 和 $\mathbf{x}\pm\sigma\mathbf{e}_1$ 同向，故令 $\mathbf{v}$ 為 $\mathbf{x}\pm\sigma\mathbf{e}_1$ 正規化後的單位向量。

設 $A$ 是一個 $m\times n$ 階實矩陣，以行向量 (column vector) 表示為 $A=\begin{bmatrix} \mathbf{a}_1&\mathbf{a}_2&\cdots&\mathbf{a}_n \end{bmatrix}$ ， $\mathbf{a}_j\in\mathbb{R}^m$ 。令 $\mathbf{x}=\mathbf{a}_1$ ，且

$\mathbf{v}_1=\displaystyle\frac{\mathbf{x}-\sigma\mathbf{e}_1}{\Vert\mathbf{x}-\sigma\mathbf{e}_1\Vert}$

由此建構 $m\times m$ 階 Householder 矩陣 $H_1=I_m-2\mathbf{v}_1\mathbf{v}_1^T$ ，就有

$H_1\mathbf{a}_1=\Vert\mathbf{a}_1\Vert\mathbf{e}_1$

故左乘 $H_1$ 即可完全消滅 $A$ 中 $(1,1)$ 以下所有元：

$\begin{aligned} H_1A&=H_1\begin{bmatrix} \mathbf{a}_1&\mathbf{a}_2&\cdots&\mathbf{a}_n \end{bmatrix}=\begin{bmatrix} H_1\mathbf{a}_1&H_1\mathbf{a}_2&\cdots&H_1\mathbf{a}_n \end{bmatrix}\\ &=\begin{bmatrix} r_{11}&r_{12}&\cdots&r_{1n}\\ 0&\ast&\cdots&\ast\\ \vdots&\vdots&\ddots&\vdots\\ 0&\ast&\cdots&\ast \end{bmatrix}=\begin{bmatrix} r_{11}&\mathbf{r}_1^T\\ \mathbf{0}&A_2 \end{bmatrix}\end{aligned}$

其中 $r_{11}=\Vert\mathbf{a}_1\Vert$ ， $A_2$ 為右下 $(m-1)\times(n-1)$ 階分塊。繼續對分塊 $A_2$ 按同樣方式執行正交化簡，設計一 $(m-1)\times(m-1)$ 階 Householder 矩陣 $\hat{H}_2$ 以消滅 $A_2$ 分塊 $(1,1)$ 以下各元。令

$H_2=\begin{bmatrix} 1&\mathbf{0}^T\\ \mathbf{0}&\hat{H}_2 \end{bmatrix}$

設 $\hat{H}_2=I_{m-1}-2\mathbf{v}_2\mathbf{v}_2^T$ ，代入上式可確認 $H_2$ 是 Householder 矩陣。左乘 $H_2$ 可消滅 $H_1A$ 中 $(2,2)$ 以下各個元：

$\begin{aligned} H_2H_1A&=\begin{bmatrix} r_{11}&\mathbf{r}_1^T\\ \mathbf{0}&\hat{H}_2A_2 \end{bmatrix}=\begin{bmatrix} r_{11}&r_{12}&r_{13}&\cdots&r_{1n}\\ 0&r_{22}&r_{23}&\cdots&r_{2n}\\ 0&0&\ast&\cdots&\ast\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 0&0&\ast&\cdots&\ast \end{bmatrix}\end{aligned}$

若 $m>n$ ，連續左乘 $n$ 個 $m\times m$ 階 Householder 矩陣可使 $m\times n$ 階矩陣 $A$ 化簡為

$H_n\cdots H_2H_1A=\begin{bmatrix} R\\ 0 \end{bmatrix}$

其中 $R$ 是 $n\times n$ 階上三角矩陣。因為 $H_i^{-1}=H_i^T=H_i$ ， $A$ 的 QR 分解式就是

$\begin{aligned} A&=H_1H_2\cdots H_n\begin{bmatrix} R\\ 0 \end{bmatrix}=Q\begin{bmatrix} R\\ 0 \end{bmatrix}\end{aligned}$

不難證明 $Q=H_1H_2\cdots H_n$ 是正交矩陣。若 $m\le n$ ，執行 $m-1$ 次 Householder 矩陣乘法可將 $A$ 化簡成梯形矩陣：

$H_{m-1}\cdots H_2H_1A=\begin{bmatrix} R&S \end{bmatrix}$

上式中 $R$ 是 $m\times m$ 階上三角矩陣，QR 分解則為

$\begin{aligned} A&=H_1H_2\cdots H_{m-1}\begin{bmatrix} R&S \end{bmatrix}=Q\begin{bmatrix} R&S \end{bmatrix}\end{aligned}$

下面我們用一個例子展示 Householder 正交化簡於 QR 分解的應用。考慮

$A=\left[\!\!\begin{array}{crr} 0&-15&14\\ 4&32&2\\ 3&-1&4 \end{array}\!\!\right]$

為消滅矩陣 $A$ 中 $(1,1)$ 以下各元，令 $\mathbf{x}=\begin{bmatrix} 0\\ 4\\ 3 \end{bmatrix}$ ，就有

$\begin{aligned} \mathbf{v}_1&=\displaystyle\frac{\mathbf{x}-\sigma\mathbf{e}_1}{\Vert\mathbf{x}-\sigma\mathbf{e}_1\Vert}=\frac{1}{\sqrt{50}}\left[\!\!\begin{array}{r} -5\\ 4\\ 3 \end{array}\!\!\right]\end{aligned}$

令 $H_1=I_3-2\mathbf{v}_1\mathbf{v}_1^T$ 。由前述討論可知 $H_1\mathbf{a}_1=\Vert\mathbf{a}_1\Vert\mathbf{e}_1$ ，再利用下式

$H_1\mathbf{a}_j=\mathbf{a}_j-2(\mathbf{v}_1^T\mathbf{a}_j)\mathbf{v}_1,~~j=2,3$

即得

$\begin{aligned} H_1A&=\begin{bmatrix} H_1\mathbf{a}_1&H_1\mathbf{a}_2&H_1\mathbf{a}_3 \end{bmatrix}=\left[\!\!\begin{array}{crr} 5&25&4\\ 0&0&10\\ 0&-25&10 \end{array}\!\!\right]\end{aligned}$

為消滅 $H_1A$ 中 $(2,2)$ 以下各元，考慮 $A_2=\left[\!\!\begin{array}{rc} 0&10\\ -25&10 \end{array}\!\!\right]$ 。令 $\mathbf{x}=\left[\!\!\begin{array}{r} 0\\ -25 \end{array}\!\!\right]$ ，則

$\begin{aligned} \mathbf{v}_2&=\displaystyle\frac{\mathbf{x}-\sigma\mathbf{e}_1}{\Vert\mathbf{x}-\sigma\mathbf{e}_1\Vert}=\frac{1}{\sqrt{2}}\begin{bmatrix} 1\\ 1 \end{bmatrix}\end{aligned}$

又令 $H_2=\begin{bmatrix} 1&\mathbf{0}^T\\ \mathbf{0}&\hat{H}_2 \end{bmatrix}$ ，其中 $2\times 2$ 階矩陣 $\hat{H}_2=I-2\mathbf{v}_2\mathbf{v}_2^T$ ，依照前述計算方式，可得

$\hat{H}_2A_2=\begin{bmatrix} 25&-10\\ 0&-10 \end{bmatrix}$

也就有

$\begin{aligned} R&=H_2H_1A=\left[\!\!\begin{array}{crr} 5&25&4\\ 0&25&-10\\ 0&0&-10 \end{array}\!\!\right]\end{aligned}$

這個結果與 Givens 旋轉導出的 QR 分解式相同。請讀者注意，對於 $m\times n$ 階矩陣 $A$ ，Householder 變換和 Givens 旋轉得到的 QR 分解與 Gram-Schmidt 正交化得到的 QR 分解具有不同形式，詳細討論請參閱“Givens 旋轉於 QR 分解的應用”。

12 Responses to Householder 變換於 QR 分解的應用

Liang Dai says:

05/27/2011 at 2:42 pm

周老师，Gram/Schmitt方法，Givens旋转，Householder翻转三种方法对一个矩阵做QR分解从计算量和数值稳定性上讲那种方法最值得推荐呢？

ccjou says:

05/27/2011 at 10:29 pm

說來話長，下回就來討論這個問題。

Vahi Chen says:

09/18/2015 at 7:41 am

对于矩阵 $A$ ，针对非奇异（ $m=n$ ）和column满秩（ $A\in\mathbb{R}^{m\times n}$ ）两种情况，Householder变换和Givens变换实现的QR分解都是唯一的吗？

- ccjou says:
  
  09/18/2015 at 7:56 am
  
  如果限定 $R$ 的主對角元為正值，則非奇異方陣與full col rank矩陣有唯一的QR分解，不過後者的形式為 $A=QR=\begin{bmatrix} Q_1&Q_2 \end{bmatrix}\begin{bmatrix} R_1\\ 0 \end{bmatrix}=Q_1R_1$ ， $Q_1$ 和 $R_1$ 是唯一的，但 $Q_2$ 則否。
  
Allen says:

09/19/2016 at 1:31 pm

周老師你好:

H1A 可以消滅 A中(1,1)以下所有元
要消滅H1A中(2,2)以下各元要考慮A2(即A矩陣右下角的分塊)去做H2計算

我想請教的
當H2H1A 時，要怎麼去推導證明 H2乘上去第一行不會改變 ?
每次要消滅(2,2)以下的元，都要取A矩陣右下角的分塊來計算
(可以以整個矩陣來看不要做分塊的計算來證明第一行不會變嗎 )
假如例題都不一樣，每次不是都要在證明一次
還是householder就是這樣子計算的

謝謝

- ccjou says:
  
  09/19/2016 at 3:35 pm
  
  根據分塊矩陣乘法，
  $\begin{bmatrix} 1&0^T\\ 0&\hat{H}_2 \end{bmatrix}\begin{bmatrix} a&\mathbf{b}^T\\ 0&A_2 \end{bmatrix}=\begin{bmatrix} a&\mathbf{b}^T\\ 0&\hat{H}_2A_2 \end{bmatrix}$
  
  - Allen says:
    
    09/19/2016 at 4:22 pm
    
    所以上面例子是將 H1A 分塊成4塊
    分別為 r11，0， r1^T，和(m-1)*(n-1) 四塊嗎 ?
    
    r1^T(這邊是指 r12 到 r1n 嗎) ?
    
    - Allen says:
      
      09/19/2016 at 4:40 pm
      
      老師你回應的b^T 是指 ?
      
      謝謝
      
    - ccjou says:
      
      09/19/2016 at 4:42 pm
      
      我將上例稍作補充，請再看一次。
      
      - Allen says:
        
        09/19/2016 at 5:21 pm
        
        我在看了一次
        還是不太懂也不敢確定我想的是不是正確的
        所以麻煩老師解惑
        
        上面的描述 r1^T(是指 r12 到 r1n 嗎) ?
        還有H2 的0^T 所代表是甚麼意思為什麼不寫0就好
        謝謝
        
        
        ccjou says:
        
        09/19/2016 at 5:55 pm
        
        本文 $\mathbf{a}$ 是column vector， $\mathbf{a}^T$ 是row vector。
Charlie Li says:

10/28/2020 at 4:33 pm

老師好

雖然結果沒差，不過例子那段
v_2=…=\frac{1}{ \sqrt{2}} [1 1]^T
是不是要加個負號？

	陳倍恩 on 線性代數的第一堂課──矩陣乘法的定義
	輕鬆談如何教學二項式定理？… on 牛頓的二項式定理 (上)
	madhouse on 高斯消去法
	WishMobile on 翻轉 LU 分解
	周子傑 on Karush-Kuhn-Tucker (KKT) 條件
	Cloud Huang on 線性泛函與伴隨