4.4. 正交三角分解

4.4.1. 什么是正交三角分解

正交三角分解 ( Orthogonal Triangular Decomposition ), 是指将一矩阵分解正 (酉) 交矩阵 ${\bm Q}$ 与非奇异上三角矩阵 ${\bm R}$ 两个矩阵的乘积的分解.

Definition 4.3 (正交三角分解)

设 ${\bm A} \in {\mathbb C}_{m\times n}$ , 若存在矩阵 ${\bm Q} \in {\mathbb C}$ 和 ${\bm R} \in {\mathbb C}$ 使得

${\bm A}_{m\times n} = {\bm Q}_{m\times n} {\bm R}_{n\times n}$

则称上述分解为 正交三角分解 , 简称 QR 分解 .

4.4.2. 求解方法

Schmidt 正交化方法

对矩阵 ${\bm A} \in {\mathbb C}_{m\times n}$ 进行QR分解的步骤如下:

1. 记矩阵 ${\bm A} = ({\bm a}_1, {\bm a}_2, \cdots, {\bm a}_n)$ , 其中 ${\bm a}_j$ 为矩阵 ${\bm A}$ 的第 $j$ 列;

2. 正交化向量组 ${\bm a}_1, {\bm a}_2, \cdots, {\bm a}_n$ , 得正交化后的向量组 ${\bm b}_1, {\bm b}_2, \cdots, {\bm b}_n$ ;

3. 单位化向量组 ${\bm b}_1, {\bm b}_2, \cdots, {\bm b}_n$ , 得单位化后的向量组 ${\bm q}_1, {\bm q}_2, \cdots, {\bm q}_n$ , 其中 ${\bm q}_j = \frac{1}{|{\bm b}_j|}{\bm b}_j$ , $j = 1, 2, \cdots, n$ ;

4. 将正交化的向量组按顺序组成矩阵 ${\bm Q} = ({\bm q}_1, {\bm q}_2, \cdots, {\bm q}_n)$ ;

5. 计算上三角矩阵 ${\bm R} = {\rm diag}(|{\bm b}_1|, |{\bm b}_2|, \cdots, |{\bm b}_n|) \cdot {\bm C}$ ;

其中,

${\bm C} = \left[ {\begin{array}{cccc} {\rm{1}}&{{k_{21}}}& \cdots &{{k_{n1}}}\\ {}&1& \cdots &{{k_{n2}}}\\ {}&{}& \ddots &{}\\ {}&{}&{}&1 \end{array}} \right]$

且 $k_{ij} = \frac{\left\langle {\bm a}_i{\bm b}_j \right\rangle}{\left\langle {\bm b}_j{\bm b}_j \right\rangle}$ , $j < i$ .

注解

举个例子, 求如下矩阵的QR分解,

${\bm A} = \left[ {\begin{array}{ccc} 0&2&2\\ 2&1&2\\ 0&2&1 \end{array}} \right]$

解: 由题意有,

令 ${\bm a}_1 = (0, 2, 0)^T$ , ${\bm a}_2 = (2, 1, 2)^T$ , ${\bm a}_3 = (2, 2, 1)^T$

正交化得

${\bm b}_1 = {\bm a}_1 = (0, 2, 0)^T$ , $k_{21} = \frac{\left\langle{\bm a_2}, {\bm b}_1\right\rangle }{\left\langle{\bm b}_1, {\bm b}_1\right\rangle } = \frac{1}{2}$

${\bm b}_2 = {\bm a}_2 - k_{21}{\bm b}_1$ $= (2, 1, 2)^T - \frac{1}{2}(0, 2, 0)^T = (2, 0, 2)^T$ , $k_{32} = \frac{\left\langle{\bm a_3}, {\bm b}_2\right\rangle }{\left\langle{\bm b}_2, {\bm b}_2\right\rangle } = \frac{3}{4}$ , $k_{31} = \frac{\left\langle{\bm a_3}, {\bm b}_1\right\rangle }{\left\langle{\bm b}_1, {\bm b}_1\right\rangle } = 1$

${\bm b}_3 = {\bm a}_3 - k_{32}{\bm b}_2 - k_{31}{\bm b}_1$ $= (2, 2, 1)^T - \frac{3}{4}(2, 0, 2)^T - 1(0, 2, 0)^T = (\frac{1}{2}, 0, \frac{-1}{2})^T$

单位化得

${\bm q}_1 = \frac{(0, 2, 0)^T}{2} = (0, 1, 0)^T$ , ${\bm q}_2 = \frac{(2, 0, 2)^T}{2\sqrt 2} = (\frac{1}{\sqrt 2}, 0, \frac{1}{\sqrt 2})^T$ , ${\bm q}_3 = \frac{(\frac{1}{2}, 0, \frac{-1}{2})^T}{\frac{1}{\sqrt 2}} = (\frac{\sqrt 2}{2}, 0, \frac{-\sqrt 2}{2})^T$

从而有

${\bm{C}} = \left[ {\begin{array}{ccc} 1&{{k_{21}}}&{{k_{31}}}\\ 0&1&{{k_{32}}}\\ 0&0&1 \end{array}} \right] = \left[ {\begin{array}{ccc} 1&{\frac{1}{2}}&{1}\\ 0&1&{\frac{3}{4}}\\ 0&0&1 \end{array}} \right]$

由 ${\bm R} = {\rm diag}(|{\bm b}_1|, |{\bm b}_2|, |{\bm b}_3|) \cdot {\bm C}$ 知

${\bm R} = \left[ {\begin{array}{ccc} {2 }&0&0\\ 0&{2\sqrt 2 }&0\\ 0&0&{\frac{1}{\sqrt 2}} \end{array}} \right]\left[ {\begin{array}{ccc} 1&{\frac{1}{2}}&{1}\\ 0&1&{\frac{3}{4}}\\ 0&0&1 \end{array}} \right] = \left[ {\begin{array}{ccc} {2}&{1}&{2}\\ 0&{2\sqrt 2}&{\frac{3}{\sqrt 2}}\\ 0&0&{\frac{1}{\sqrt 2}} \end{array}} \right]$

${\bm{Q}} = \left[ {\begin{array}{ccc} {0}&{\frac{1}{{\sqrt 2}}}&{\frac{\sqrt 2}{2}}\\ {1}&{0}&0\\ {0}&{\frac{1}{{\sqrt 2}}}&{\frac{-\sqrt 2}{2}} \end{array}} \right] = \left[ {\begin{array}{ccc} 0&{\frac{1}{{\sqrt 2 }}}&{\frac{1}{{\sqrt 2 }}}\\ 1&0&0\\ 0&{\frac{1}{{\sqrt 2 }}}&{\frac{{ - 1}}{{\sqrt 2 }}} \end{array}} \right]$

Givens 变换方法

注解

举个例子, 求如下矩阵的QR分解,

${\bm A} = \left[ {\begin{array}{ccc} 0&2&2\\ 2&1&2\\ 0&2&1 \end{array}} \right]$

解: 由题意有,

记 ${\bm A}^{(1)} = {\bm A}$ , 取 ${\bm A}^{(1)}$ 的第一列 ${\bm a}_1^{(1)} = (0, 2, 0)^T$ , 构造Givens矩阵, 使得 ${\bm G}^{(1)}{\bm a}_1^{(1)} = |{\bm a}_1^{(1)}| {\bm e}_1$ :

取 ${\bm G}^{(1)}_{1,2} = \left[ {\begin{array}{ccc} 0&1&0\\ {{-}1}&0&0\\ 0&0&1 \end{array}} \right]$ , 其中, $c = \frac{\xi_1}{\sqrt{\xi_1^2 + \xi_2^2}} = \frac{0}{\sqrt{0^2 + 2^2}} = 0$ , $s = \frac{\xi_2}{\sqrt{\xi_1^2 + \xi_2^2}} = \frac{2}{\sqrt{0^2 + 2^2}} = 1$ .

从而 ${\bm G}^{(1)}_{1,2}{\bm a}_1^{(1)} = (2, 0, 0)^T = 2 {\bm e}_1$ 的第二坐标分量变为 $0$ , 又第三坐标分量为 $0$ , 所以无需再构造 ${\bm G}^{(1)}_{1,3}$ 使第三坐标分量为 $0$ , 当然也可以对 $(2, 0, 0)^T$ 继续构造

${\bm G}^{(1)}_{1,3} = \left[ {\begin{array}{ccc} 1&0&0\\ 0&1&0\\ 0&0&1 \end{array}} \right]$ , 其中, $c = \frac{\sqrt{\xi_1^2+\xi_2^2}}{\sqrt{\xi_1^2 + \xi_2^2 +\xi_3^2}} = \frac{\sqrt{2^2+0^2}}{\sqrt{2^2 + 0^2 + 0^2}} = 1$ , $s = \frac{\xi_3}{\sqrt{\xi_1^2 + \xi_2^2 +\xi_3^2}} = \frac{0}{\sqrt{2^2 + 0^2 + 0^2}} = 0$ , 可见 ${\bm G}^{(1)}_{1,3}$ 为单位阵.

从而有

${\bm G}^{(1)}{\bm A}^{(1)} = {\bm G}^{(1)}_{1,3}{\bm G}^{(1)}_{1,2}{\bm A}^{(1)} = \left[ {\begin{array}{ccc} 1&0&0\\ 0&1&0\\ 0&0&1 \end{array}} \right]\left[ {\begin{array}{ccc} 0&1&0\\ {{\rm{ - }}1}&0&0\\ 0&0&1 \end{array}} \right]\left[ {\begin{array}{ccc} 0&2&2\\ 2&1&2\\ 0&2&1 \end{array}} \right] \\ = \left[ {\begin{array}{ccc} 2&1&2\\ 0&{{-}2}&{{-}2}\\ 0&2&1 \end{array}} \right]$

对 ${\bm A}^{(2)} = \left[ {\begin{array}{cc}{-2}&{-2}\\2&1\end{array}} \right]$ , 取其第一列 ${\bm a}_1^{(2)} = (-2, 2)^T$ , 构造Givens矩阵, 使得 ${\bm G}^{(2)}{\bm a}_1^{(2)} = |{\bm a}_1^{(2)}| {\bm e}_1$ :

取 ${\bm G}^{(2)}_{1,2} = \left[ {\begin{array}{cc}{\frac{{{\rm{ - }}1}}{{\sqrt 2 }}}&{\frac{1}{{\sqrt 2 }}}\\{\frac{{{\rm{ - }}1}}{{\sqrt 2 }}}&{\frac{{{\rm{ - }}1}}{{\sqrt 2 }}}\end{array}} \right]$ , 其中, $c = \frac{\xi_1}{\sqrt{\xi_1^2 + \xi_2^2}} = \frac{-2}{\sqrt{{-2}^2 + 2^2}} = \frac{-1}{\sqrt 2}$ , $s = \frac{\xi_2}{\sqrt{\xi_1^2 + \xi_2^2}} = \frac{2}{\sqrt{{-2}^2 + 2^2}} = \frac{1}{\sqrt 2}$ .

从而有

${\bm G}^{(2)}{\bm A}^{(2)} = {\bm G}^{(2)}_{1,2}{\bm A}^{(2)} = \left[ {\begin{array}{cc} {\frac{{{\rm{ - }}1}}{{\sqrt 2 }}}&{\frac{1}{{\sqrt 2 }}}\\ {\frac{{{\rm{ - }}1}}{{\sqrt 2 }}}&{\frac{{{\rm{ - }}1}}{{\sqrt 2 }}} \end{array}} \right]\left[ {\begin{array}{cc} {{\rm{ - }}2}&{{\rm{ - }}2}\\ 2&1 \end{array}} \right]{\rm{ = }}\left[ {\begin{array}{cc} {2\sqrt 2 }&{\frac{3}{{\sqrt 2 }}}\\ 0&{\frac{1}{{\sqrt 2 }}} \end{array}} \right]$

最后, 令

${\bm G} = \left[ {\begin{array}{cc} 1&{}\\ {}&{{{\bm{G}}^{(2)}}} \end{array}} \right]{{\bm{G}}^{(1)}} = \left[ {\begin{array}{ccc} 1&0&0\\ 0&{\frac{{ - 1}}{{\sqrt 2 }}}&{\frac{1}{{\sqrt 2 }}}\\ 0&{\frac{{ - 1}}{{\sqrt 2 }}}&{\frac{{ - 1}}{{\sqrt 2 }}} \end{array}} \right]\left[ {\begin{array}{ccc} 0&1&0\\ {{\rm{ - }}1}&0&0\\ 0&0&1 \end{array}} \right] = \left[ {\begin{array}{ccc} 0&1&0\\ {\frac{1}{{\sqrt 2 }}}&0&{\frac{1}{{\sqrt 2 }}}\\ {\frac{1}{{\sqrt 2 }}}&0&{\frac{{ - 1}}{{\sqrt 2 }}} \end{array}} \right]$

则有

${\bm Q} = {\bm G}^T = \left[ {\begin{array}{ccc} 0&{\frac{1}{{\sqrt 2 }}}&{\frac{1}{{\sqrt 2 }}}\\ 1&0&0\\ 0&{\frac{1}{{\sqrt 2 }}}&{\frac{{ - 1}}{{\sqrt 2 }}} \end{array}} \right]$

${\bm{R}}{\rm{ = }}\left[ {\begin{array}{ccc} 2&1&2\\ 0&{2\sqrt 2 }&{\frac{{3\sqrt 2 }}{2}}\\ 0&0&{\frac{{\sqrt 2 }}{2}} \end{array}} \right] = \left[ {\begin{array}{ccc} 2&1&2\\ 0&{2\sqrt 2 }&{\frac{3}{{\sqrt 2 }}}\\ 0&0&{\frac{1}{{\sqrt 2 }}} \end{array}} \right]$

Householder 变换方法

注解

举个例子, 求如下矩阵的QR分解,

${\bm A} = \left[ {\begin{array}{ccc} 0&2&2\\ 2&1&2\\ 0&2&1 \end{array}} \right]$

解: 由题意有,

记 ${\bm A}^{(1)} = {\bm A}$ , 取 ${\bm A}^{(1)}$ 的第一列 ${\bm a}_1^{(1)} = (0, 2, 0)^T$ , 构造Householder矩阵, 使得 ${\bm H}^{(1)}{\bm a}_1^{(1)} = |{\bm a}_1^{(1)}| {\bm e}_1$ :

${\bm b}_1^{(1)} = {\bm a}_1^{(1)} - |{\bm a}_1^{(1)}|{\bm e}_1 = (0, 2, 0)^T - 2(1, 0, 0)^T = (-2, 2, 0)^T$ , ${\bm u}_1^{(1)} = \frac{{\bm b}_1^{(1)}}{|{\bm b}_1^{(1)}|} = \frac{(-2, 2, 0)^T}{2\sqrt{2}} = (\frac{-1}{\sqrt 2}, \frac{1}{\sqrt 2}, 0)^T$

${\bm u}_1^{(1)}{{\bm u}_1^{(1)}}^T = \left[ {\begin{array}{ccc}{\frac{1}{2}}&{\frac{{ - 1}}{2}}&0\\{\frac{{ - 1}}{2}}&{\frac{1}{2}}&0\\0&0&0\end{array}} \right]$

${{\bm{H}}^{(1)}} = {\bm{I}} - 2{\bm u}_1^{(1)}{{\bm u}_1^{(1)}}^T = \left[ {\begin{array}{ccc} 1&0&0\\ 0&1&0\\ 0&0&1 \end{array}} \right] - \left[ {\begin{array}{ccc} 1&{ - 1}&0\\ { - 1}&1&0\\ 0&0&0 \end{array}} \right] = \left[ {\begin{array}{ccc} 0&1&0\\ 1&0&0\\ 0&0&1 \end{array}} \right]$

${{\bm{H}}^{(1)}}{{\bm{A}}^{(1)}} = \left[ {\begin{array}{ccc} 0&1&0\\ 1&0&0\\ 0&0&1 \end{array}} \right]\left[ {\begin{array}{ccc} 0&2&2\\ 2&1&2\\ 0&2&1 \end{array}} \right] = \left[ {\begin{array}{ccc} 2&1&2\\ 0&2&2\\ 0&2&1 \end{array}} \right]$

对 ${\bm A}^{(2)} = \left[ {\begin{array}{cc}2&2\\2&1\end{array}} \right]$ , 取其第一列 ${\bm a}_1^{(2)} = (2, 2)^T$ , 构造Householder矩阵, 使得 ${\bm H}^{(2)}{\bm a}_1^{(2)} = |{\bm a}_1^{(2)}| {\bm e}_1$ :

${\bm b}_1^{(2)} = {\bm a}_1^{(2)} - |{\bm a}_1^{(2)}|{\bm e}_1 = (2, 2)^T - 2{\sqrt 2}(1, 0)^T = (2-2{\sqrt 2}, 2)^T$ , ${\bm u}_1^{(2)} = \frac{{\bm b}_1^{(2)}}{|{\bm b}_1^{(2)}|} = \frac{(2-2{\sqrt 2}, 2)^T}{2{\sqrt{4-2\sqrt 2}}} = \frac{(1-{\sqrt 2}, 1)^T}{{\sqrt{4-2\sqrt 2}}}$

${\bm u}_1^{(2)}{{\bm u}_1^{(2)}}^T = \frac{1}{{4{-}2\sqrt 2 }}\left[ {\begin{array}{cc} {1{-}\sqrt 2 }\\ 1 \end{array}} \right]\left[ {\begin{array}{ccc} {1{-}\sqrt 2 }&1 \end{array}} \right]{\rm{ = }}\frac{1}{{4{-}2\sqrt 2 }}\left[ {\begin{array}{ccc} {3{-}2\sqrt 2 }&{1{-}\sqrt 2 }\\ {1{-}\sqrt 2 }&1 \end{array}} \right]$

${{\bm{H}}^{(2)}} = {\bm{I}} - 2{\bm u}_1^{(2)}{{\bm u}_1^{(2)}}^T = \left[ {\begin{array}{ccc} 1&0\\ 0&1 \end{array}} \right] - \frac{1}{{{\rm{2 - }}\sqrt 2 }}\left[ {\begin{array}{ccc} {3{-}2\sqrt 2 }&{1{-}\sqrt 2 }\\ {1{-}\sqrt 2 }&1 \end{array}} \right]{\rm{ = }}\left[ {\begin{array}{ccc} {\frac{{\sqrt 2 }}{2}}&{\frac{{\sqrt 2 }}{2}}\\ {\frac{{\sqrt 2 }}{2}}&{\frac{{{-}\sqrt 2 }}{2}} \end{array}} \right]$

${{\bm{H}}^{{\rm{(2)}}}}{{\bm{A}}^{{\rm{(2)}}}} = \left[ {\begin{array}{ccc} {\frac{{\sqrt 2 }}{2}}&{\frac{{\sqrt 2 }}{2}}\\ {\frac{{\sqrt 2 }}{2}}&{\frac{{{-}\sqrt 2 }}{2}} \end{array}} \right]\left[ {\begin{array}{ccc} 2&2\\ 2&1 \end{array}} \right]{\rm{ = }}\left[ {\begin{array}{ccc} {2\sqrt 2 }&{\frac{{3\sqrt 2 }}{2}}\\ 0&{\frac{{\sqrt 2 }}{2}} \end{array}} \right]$

再令

${\bm{S}} = \left[ {\begin{array}{ccc} 1&0\\ 0&{{{\bm{H}}^{{\rm{(2)}}}}} \end{array}} \right]{{\bm{H}}^{{\rm{(1)}}}}{\rm{ = }}\left[ {\begin{array}{ccc} 1&0&0\\ 0&{\frac{{\sqrt 2 }}{2}}&{\frac{{\sqrt 2 }}{2}}\\ 0&{\frac{{\sqrt 2 }}{2}}&{\frac{{{-}\sqrt 2 }}{2}} \end{array}} \right]\left[ {\begin{array}{ccc} 0&1&0\\ 1&0&0\\ 0&0&1 \end{array}} \right]$

从而

${\bm Q} = {\bm S}^T = \left[ {\begin{array}{ccc} 0&{\frac{1}{{\sqrt 2 }}}&{\frac{1}{{\sqrt 2 }}}\\ 1&0&0\\ 0&{\frac{1}{{\sqrt 2 }}}&{\frac{{ - 1}}{{\sqrt 2 }}} \end{array}} \right]$

且

${\bm{R}} = \left[ {\begin{array}{ccc} 2&1&2\\ 0&{2\sqrt 2 }&{\frac{3}{{\sqrt 2 }}}\\ 0&0&{\frac{1}{{\sqrt 2 }}} \end{array}} \right]$

代码实现

matlab代码

>> A = [0 2 2;2 1 2;0 2 1]

A =

     0     2     2
     2     1     2
     0     2     1

>> [Q, R] = qr(A)

Q =

         0    0.7071   -0.7071
   -1.0000         0         0
         0    0.7071    0.7071

R =

   -2.0000   -1.0000   -2.0000
         0    2.8284    2.1213
         0         0   -0.7071