1. QR分解(QR decomposition)

1.1 定义

设A∈Cm×rr$A\in C_r^{m\times r}$是一个列满秩矩阵，则，有如下分解

其中，Q∈Um×rr$Q\in U_r^{m\times r}$是一个次酉矩阵，R$R$是一个r×r$r\times r$的上三角矩阵。且当对角线上元素均为正时，分解唯一。
【注】：此定义为复数域含义下，实数域自然适用。
示意图：

1.2 计算QR分解的方法

1.2.1 Gram-Schmidt正交化

以一个例子说明过程：

将Gram-Schmidt正交化应用到矩阵A$A$的每一列，

• 正交化
  γ1=α1${\gamma }_1={\alpha }_1$
  γ2=α2−<α2,γ1><γ1,γ1>γ1${\gamma }_2={\alpha }_2-\frac{<{\alpha }_2,{\gamma }_1>}{<{\gamma }_1,{\gamma }_1>}{\gamma }_1$
  γ3=α3−<α3,γ1><γ1,γ1>γ1−<α3,γ2><γ2,γ2>γ2${\gamma }_3={\alpha }_3-\frac{<{\alpha }_3,{\gamma }_1>}{<{\gamma }_1,{\gamma }_1>}{\gamma }_1-\frac{<{\alpha }_3,{\gamma }_2>}{<{\gamma }_2,{\gamma }_2>}{\gamma }_2$

• 单位化
  γ1=γ1∥γ1∥,γ2=γ2∥γ2∥,γ3=γ3∥γ3∥${\gamma }_1=\frac{{\gamma }_1}{\Vert {\gamma }_1\Vert },{\gamma }_2=\frac{{\gamma }_2}{\Vert {\gamma }_2\Vert },{\gamma }_3=\frac{{\gamma }_3}{\Vert {\gamma }_3\Vert }$

【注】：内积的含义：
矢量α$\alpha$投影在矢量β$\beta$的长度 与 矢量β$\beta$的长度 的乘积。结果是个实数。
例如，<α,α>=∥α∥2$<\alpha ,\alpha >=\Vert \alpha {\Vert }^2$
<α2,γ1><γ1,γ1>γ1$\frac{<{\alpha }_2,{\gamma }_1>}{<{\gamma }_1,{\gamma }_1>}{\gamma }_1$就是α2${\alpha }_2$在γ1${\gamma }_1$上的投影（构成的矢量）。

得到：
γ1=[−312√112√112√112√]T${\gamma }_1=[-\frac{3}{\sqrt{12}}\frac{1}{\sqrt{12}}\frac{1}{\sqrt{12}}\frac{1}{\sqrt{12}}{]}^T$
γ2=[026√−16√−16√]T${\gamma }_2=[0\frac{2}{\sqrt{6}}-\frac{1}{\sqrt{6}}-\frac{1}{\sqrt{6}}{]}^T$
γ3=[−16√−16√−26√0]T${\gamma }_3=[-\frac{1}{\sqrt{6}}-\frac{1}{\sqrt{6}}-\frac{2}{\sqrt{6}}0{]}^T$
组成次酉矩阵U=[γ1γ2γ3]$U=[{\gamma }_1{\gamma }_2{\gamma }_3]$
那么，上三角矩阵R$R$

1.2.2 Householder reflection

1.2.3 Givens rotation

1.3 QR分解的应用

1.3.1 求 不相容方程 某种含义下的最优解

不相容方程(incompatible equation)：
若n$n$元一次线性方程组Ax=b$Ax=b$有解，则称该方程组相容；若无解，则称其不相容。
有解的充要条件是：rank(A|b)=rank(A)≤n$rank(A|b)=rank(A)\le n$

结合上面的例子，给出方程右侧的常数项 b=[1021]T$b=[1021{]}^T$
此时，验算有解的充要条件是不满足的。

也就是说，使4个方程同时成立的解是不存在的，即，使下式

的矢量x$x$（解）是不存在的。
但是，我们可以寻求某种意义下的一个解，比方说，
找到这样一个x$x$，使得即使右端不全为零，但是它的个元素的平方和最小。
物理意义：It minimizes the distance between the two vector Ax$Ax$ and b$b$.
数学语言：
min∥e∥2=min(Ax−b)∗(Ax−b)$min\Vert e{\Vert }^2=min(Ax-b{)}^{\ast }(Ax-b)$
使上式成立的那个x$x$，记为xopt$x_{opt}$.

问题转化：
已知

，
其中，Q是一个次酉矩阵，[QQ⊥]$Q是一个次酉矩阵，[Q{Q}_{\perp }]$组成一个酉矩阵。

则，

因此，

那么，使上式最小的x$x$为

两向量间的最小距离为

*搬运：https://en.wikipedia.org/wiki/QR_decomposition#cite_note-Trefethen-1