线代-- 矩阵的QR分解

作者: 倪桦 | 来源:发表于2022-07-26 00:52 被阅读0次

对于一个矩阵，如果它的列向量之间线性无关，那么它就可以分解成 $A = Q \cdot R$ 。
$Q$ 是一个标准正交矩阵
$R$ 是一个上三角形式的矩阵
矩阵 $A$ 的 $A = Q \cdot R$ 这种形式的分解称为 $QR分解$ 。

获取一个列向量之间线性无关的矩阵 $A$ 的标准正交矩阵 $Q$ ，实际上就是对矩阵 $A$ 的列向量执行Gram-Schmidt过程，因为矩阵 $A$ 的列向量之间线性无关，所以可以把它们当成空间的一组基来处理。

QR分解实际上是Gram-Schmidt过程的逆过程:

Gram-Schmidt过程是给定空间的一组基求取空间的正交基的过程:
如果已知一组基: $\vec v_1 , \vec v_2 , \cdots , \vec v_n$ ，相应的求出这组基所代表的 $n$ 维空间的一组正交基的过程就是:
$\vec p_1 = \vec v_1$
$\vec p_2 = \vec v_2 - \frac {\vec p_1 \cdot \vec v_2}{\|{\vec p_1}\|} \cdot {\vec p_1}$
$\vec p_3 = \vec v_3 - \frac {\vec p_1 \cdot \vec v_3}{\|{\vec p_1}\|} \cdot {\vec p_1} - \frac {\vec p_2 \cdot \vec v_3}{\|{\vec p_2}\|} \cdot {\vec p_2}$
$\vec p_4 = \vec v_4 - \frac {\vec p_1 \cdot \vec v_4}{\|{\vec p_1}\|} \cdot {\vec p_1} - \frac {\vec p_2 \cdot \vec v_4}{\|{\vec p_2}\|} \cdot {\vec p_2} - \frac {\vec p_3 \cdot \vec v_4}{\|{\vec p_3}\|} \cdot {\vec p_3}$
...
$\vec p_n = \vec v_n - \frac {\vec p_1 \cdot \vec v_n}{\|{\vec p_1}\|} \cdot {\vec p_1} - \frac {\vec p_2 \cdot \vec v_n}{\|{\vec p_2}\|} \cdot {\vec p_2} - \frac {\vec p_3 \cdot \vec v_n}{\|{\vec p_3}\|} \cdot {\vec p_3} - \cdots - \frac {\vec p_{n-1} \cdot \vec v_n}{\|{\vec p_{n-1}}\|} \cdot {\vec p_{n-1}}$

对于矩阵 $A$ 通过Gram-Schmidt过程，就可以将列向量 $\vec v_1 , \vec v_2 , \cdots , \vec v_n$ 处理成一组正交向量组 $\vec p_1 , \vec p_2 , \cdots , \vec p_n$ ;
继续将正交向量组的向量进行规范化 $\hat u = \frac {\vec u}{\|\vec u\|}$ 处理，最后就得到了矩阵的列向量的标准正交向量组 $\vec q_1 , \vec q_2 , \cdots , \vec q_n$
将这组标准正交向量组按列向量的方式排列就得到了标准正交矩阵 $Q= \left (\begin{array} , \ | \ \ \ \ |\ \ \ \ |\ \ \ \ \cdots \ \ \ | \\ \vec q_1,\vec q_2,\vec q_3,\cdots ,\vec q_n \\ \ | \ \ \ \ |\ \ \ \ |\ \ \ \ \cdots \ \ \ |\end{array} \right )$

从Gram-Schmidt的逆过程推导矩阵的QR分解

在整个Gram-Schmidt过程中，每一步获取一个正交向量 $\vec p_i$ 的时候， $\vec p_i$ 可以和最后得到的 $\vec q_i$ 存在联系 $\vec p_i = \|\vec p_i\| \cdot \vec q_i$ ，进而矩阵 $A$ 中原先的每个列向量 $\vec v_i$ 就可以和 $\vec q_i$ 建立联系:
$A = Q R$
$\vec p_1 = \vec v_1 = \|\vec p_1\| \cdot \vec q_1 = r_{11} \cdot \vec q_1$ ,其中 $\|\vec p_1\|$ 本身是个标量，这里就用 $r_{11}$ 代替；
$\therefore \vec v_1 = r_{11} \cdot \vec q_1$ $\leftarrow$
$\vec p_2 = \vec v_2 - \frac {\vec p_1 \cdot \vec v_2}{\|{\vec p_1}\|} \cdot {\vec p_1}= \|\vec p_2\| \cdot \vec q_2$
$\therefore \vec v_2 = \|\vec p_2\| \cdot \vec q_2 + \frac {\vec p_1 \cdot \vec v_2}{\|{\vec p_1}\|} \cdot {\vec p_1}$ ，这里 $\vec p_1$ 用 $\|\vec p_1\| \cdot \vec q_1$ 代入得下式
$\therefore \vec v_2 = \|\vec p_2\| \cdot \vec q_2 + \frac {\vec p_1 \cdot \vec v_2}{\|{\vec p_1}\|} \cdot { \|\vec p_1\| \cdot \vec q_1}$
$\therefore \vec v_2 =r_{21} \vec q_1 + r_{22} \vec q_2$ ,上式的 $\|\vec p_2\|$ 和 $\frac {\vec p_1 \cdot \vec v_2}{\|{\vec p_1}\|} \cdot { \|\vec p_1\|}$ 都是标量，用 $r_{22},r_{21}$ 代替，简化表示出 $\vec v_2$ 与 $\vec q_1，\vec q_2$ 的关系； $\leftarrow$
$\vec p_3 = \vec v_3 - \frac {\vec p_1 \cdot \vec v_3}{\|{\vec p_1}\|} \cdot {\vec p_1} - \frac {\vec p_2 \cdot \vec v_3}{\|{\vec p_2}\|} \cdot {\vec p_2} = \|\vec p_3\| \cdot \vec q_3$
$\therefore \vec v_3 = \|\vec p_3\| \cdot \vec q_3 + \frac {\vec p_2 \cdot \vec v_3}{\|{\vec p_2}\|} \cdot {\vec p_2} + \frac {\vec p_1 \cdot \vec v_3}{\|{\vec p_1}\|} \cdot {\vec p_1}$
$\therefore \vec v_3 = r_{31}\cdot \vec q_1 + r_{32} \cdot \vec q_2 + r_{33} \cdot \vec q_3$ $\leftarrow$
$\cdots$
持续执行上过程，就能反推得到矩阵 $A$ 中原先的每个列向量 $\vec v_i$ 和 $\vec q_i$ 的关系:
$\vec v_1 = r_{11} \cdot \vec q_1$
$\vec v_2 = r_{21} \vec q_1 + r_{22} \vec q_2$
$\vec v_3 = r_{31}\cdot \vec q_1 + r_{32} \cdot \vec q_2 + r_{33} \cdot \vec q_3$
$\vec v_4 = r_{41}\cdot \vec q_1 + r_{42} \cdot \vec q_2 + r_{43} \cdot \vec q_3 + r_{44} \cdot \vec q_4$
$\cdots$
$\vec v_n = r_{n1}\cdot \vec q_1 + r_{n2} \cdot \vec q_2 + r_{n3} \cdot \vec q_3 +\cdots + r_{nn} \cdot \vec q_n$

从而，对于矩阵 $A$ 的一组列向量 $\vec v_1 , \vec v_2 , \cdots , \vec v_n$ ，就可以由 $r_{ij} , \vec q_i$ 进行表示，重新排列成矩阵：
$A= \left (\begin{array} ,\ \ r_{11} \cdot \vec q_1 ,\ \ r_{21} \vec q_1 + r_{22} \vec q_2 ,\ \cdots \ , r_{n1}\cdot \vec q_1 + r_{n2} \cdot \vec q_2 + r_{n3} \cdot \vec q_3 +\cdots + r_{nn} \cdot \vec q_n \end{array} \right )$

这个新组成的矩阵A，提出其中的 $\vec q_i$ 向量，进而就表示成矩阵的 $QR$ 分解形式:
$A= \left (\begin{array} ,\vec q_1 \ \ \ , \vec q_2\ \ \ ,\cdots , \vec q_n \end{array} \right ) \cdot \begin{bmatrix} r_{11}&r_{21}&r_{31}&\cdots&r_{n1} \\ 0&r_{22}&r_{32}&\cdots&r_{n2} \\ 0&0&r_{33}&\cdots&r_{n3} \\ 0&0&0&\cdots&r_{nn} \end{bmatrix} = Q \cdot R$
$Q = \left (\begin{array} ,\vec q_1 \ \ \ , \vec q_2\ \ \ ,\cdots , \vec q_n \end{array} \right )$

$R = \begin{bmatrix} r_{11}&r_{21}&r_{31}&\cdots&r_{n1} \\ 0&r_{22}&r_{32}&\cdots&r_{n2} \\ 0&0&r_{33}&\cdots&r_{n3} \\ 0&0&0&\cdots&r_{nn} \end{bmatrix}$

获取矩阵的 $Q$ 矩阵和 $R$ 矩阵

通过上面的推导过程可知Gram-Schmidt过程得到了矩阵 $A$ 的Q矩阵，再逆推导就能得到R矩阵。
但是对于一个列向量之间线性无关的矩阵 $A$ ，它能够进行QR分解，其实就有:
$A = QR = Q^{-1} \cdot A = Q^{-1} Q \cdot R = R$
又 $\because Q^T \cdot Q= I \to Q^{1} = Q^{T}$ ，Q是标准正交矩阵，所以根本不需要通过计算来求矩阵Q的逆
$R = Q^{-1} A = Q^{T} \cdot A$