线代-- 矩阵的QR分解

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

线代-- 矩阵的QR分解
矩阵分解
推荐系统中矩阵分解算法-funkSVD和ALS
矩阵分析学习笔记（五）-矩阵的分解
数学基础
numpy -- 实现线性代数
[转]QR分解和酉矩阵
线代--矩阵的分解-LU分解n阶方阵
QR分解
线代-矩阵的SVD分解-矩阵压缩降噪降维

对于一个矩阵，如果它的列向量之间线性无关，那么它就可以分解成 $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$

所以QR分解一个矩阵 $A$ ，其实只需要进行一边正向Gram-Schmidt过程求出矩阵 $A$ 的列向量的标准正交向量组；

QR分解的应用

主要还是用于加速线性系统的求解

对于 $Ax=b$ , $A=QR$ ,
$(QR)x = b$
$Q^{-1}(QR)x = Q^{-1}b$
$Rx = Q^{T}b$

求解过程中，只需要求解出矩阵A的Q矩阵，同时R矩阵又是一个上三角矩阵，从而降低了求解的时间复杂度。

线代-- 矩阵的QR分解
对于一个矩阵，如果它的列向量之间线性无关，那么它就可以分解成。是一个标准正交矩阵是一个上三角形式的矩阵矩阵的这种形...
矩阵分解
浅理解1.定义将矩阵拆解为数个矩阵的乘积2.常用方法三角分解，QR分解，SVD（奇异值）分解，还有满秩分解、QR分...
推荐系统中矩阵分解算法-funkSVD和ALS
矩阵分解funkSVD:该矩阵分解不像是线代中的，他属于伪分解。其主要思想是，用两个m＊k和k＊n的矩阵代替m＊n...
矩阵分析学习笔记（五）-矩阵的分解
QR分解设是阶可逆方阵，则存在阶正交矩阵和可逆上三角阵，使得，称为矩阵的分解。证明：将矩阵按列分块为由可...
数学基础
数学基础代数比如矩阵的SVD、QR分解，矩阵逆的求解，正定矩阵、稀疏矩阵等特殊矩阵的一些处理方法和性质等等。大学的...
numpy -- 实现线性代数
Python 实现线性代数 m_n 与 n_k 这样的矩阵才能相乘矩阵求逆矩阵和矩阵的逆相乘结果为单位矩阵 qr分解
[转]QR分解和酉矩阵
来源：https://www.cnblogs.com/zhoukui/p/7746371.html 预备知识平面...
线代--矩阵的分解-LU分解n阶方阵
矩阵分解的概念：初中我们接触过数的分解,如:;推广到矩阵，一个矩阵也可以分解为几个矩阵乘积的形式，矩阵分解具有不同...
QR分解
但是可能迭代还是太多次了，可以用householder明天再说吧！ https://blog.csdn.net/u...
线代-矩阵的SVD分解-矩阵压缩降噪降维
矩阵的SVD分解- Singular Value Decomposition【矩阵的奇异值分解】优点：适用于任意形...