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\VertA_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,連續左乘 nm\times m 階 Householder 矩陣可使 m\times n 階矩陣 A 化簡為

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

其中 Rn\times n 階上三角矩陣。因為 H_i^{-1}=H_i^T=H_iA 的 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}

上式中 Rm\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 分解的應用”。

Advertisements
本篇發表於 線性代數專欄, 內積空間 並標籤為 , , , , 。將永久鏈結加入書籤。

11 則回應給 Householder 變換於 QR 分解的應用

  1. Liang Dai 說道:

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

  2. ccjou 說道:

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

  3. Vahi Chen 說道:

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

    • ccjou 說道:

      如果限定 R 的主對角元為正值,則非奇異方陣與full col rank矩陣有唯一的QR分解,不過後者的形式為A=QR=\begin{bmatrix} Q_1&Q_2 \end{bmatrix}\begin{bmatrix} R_1\\ 0 \end{bmatrix}=Q_1R_1Q_1R_1 是唯一的,但 Q_2 則否。

  4. Allen 說道:

    周老師你好:

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

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

    謝謝

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s