Gram-Schmidt 正交化与QR 分解

Posted on 04/22/2010 by ccjou

本文的阅读等级：初级

令 \mathcal{X} 为几何向量空间 \mathbb{R}^{m} 的一个子空间，\dim\mathcal{X}=n，n\le m。假设 \{\mathbf{x}_1,\ldots,\mathbf{x}_n\} 为子空间 \mathcal{X} 的一组已知基底。在一些应用时机，例如最小平方法，我们希望从 \{\mathbf{x}_1,\ldots,\mathbf{x}_n\} 建构出另一组单范正交基底(orthonormal basis) \{\mathbf{q}_1,\ldots,\mathbf{q}_n\}，亦即每一 \Vert\mathbf{q}_i\Vert^2=\mathbf{q}_i^{T}\mathbf{q}_i=1 且\mathbf{q}_i^{T}\mathbf{q}_j=0，i\neq j。底下先考虑实几何向量空间，随后再推广至一般内积空间(见“内积的定义”，“从几何向量空间到函数空间”)。

Jørgen Pedersen Gram (1850-1916) From http://upload.wikimedia.org/wikipedia/commons/a/ab/Jorgen_Gram.jpg

 
Gram-Schmidt 正交化(orthogonalization) 是基础线性代数最常采用的方法，包含两个部分：

  1. 正交化：对于i=1,2,\ldots,n，由 \mathbf{x}_1,\ldots,\mathbf{x}_i 的线性组合产生\mathbf{y}_i，使得 \{\mathbf{y}_1,\ldots,\mathbf{y}_n\} 为一个正交向量集，即\mathbf{y}_i^T\mathbf{y}_j=0，i\neq j。
  2. 单位化：伸缩 \{\mathbf{y}_1,\ldots,\mathbf{y}_n\} 的长度，将每一 \mathbf{y}_i 替换为单位向量\mathbf{q}_i=\mathbf{y}_i/\Vert\mathbf{y}_i\Vert，最后得到单范正交基底\{\mathbf{q}_1,\ldots,\mathbf{q}_n\}。

Erhard Schmidt (1876-1959) From http://www-history.mcs.st-andrews.ac.uk/BigPictures/Schmidt_2.jpeg

 
下面我采用归纳法推导从给定的一组基底 \{\mathbf{x}_1,\ldots,\mathbf{x}_n\} 产生一组正交基底 \{\mathbf{y}_1,\ldots,\mathbf{y}_n\} 的Gram-Schmidt 正交化过程。为便于说明，考虑简单情况n=3。因为 \{\mathbf{x}_1,\mathbf{x}_2,\mathbf{x}_3\} 包含线性独立的基底向量，\mathbf{x}_1\neq\mathbf{0}，首先令

\mathbf{y}_1=\mathbf{x}_1。

见图一，将 \mathbf{x}_2 正交投影至 \mathbf{y}_1 所指的直线的分量扣除就得到\mathbf{y}_2(参阅“正交投影──威力强大的线代工具”)，算式如下：

\mathbf{y}_2=\mathbf{x}_2-\displaystyle\frac{\mathbf{y}_1^T\mathbf{x}_2}{\mathbf{y}_1^T\mathbf{y}_1}\mathbf{y}_1，

图一中绿色虚线投影向量为\frac{\mathbf{y}_1^T\mathbf{x}_2}{\mathbf{y}_1^T\mathbf{y}_1}\mathbf{y}_1。明显地，\mathbf{y}_1\perp\mathbf{y}_2。上式的扣除量(投影量) 还有另一种表达方式，因为 \frac{\mathbf{y}_1^T\mathbf{x}_2}{\mathbf{y}_1^T\mathbf{y}_1} 是一个纯量，利用矩阵乘法结合律可得

\begin{aligned} \displaystyle\frac{\mathbf{y}_1^T\mathbf{x}_2}{\mathbf{y}_1^T\mathbf{y}_1}\mathbf{y}_1&=\mathbf{y}_1\frac{\mathbf{y}_1^T\mathbf{x}_2}{\mathbf{y}_1^T\mathbf{y}_1}=\frac{1}{\mathbf{y}_1^T\mathbf{y}_1}\mathbf{y}_1\mathbf{y}_1^T\mathbf{x}_2=\frac{\mathbf{y}_1\mathbf{y}_1^T}{\mathbf{y}_1^T\mathbf{y}_1}\mathbf{x}_2\end{aligned}，

其中 \frac{\mathbf{y}_1\mathbf{y}_1^{T}}{\mathbf{y}_1^{T}\mathbf{y}_1} 是将 \mathbb{R}^n 向量投影至子空间(直线)\mathrm{span}\{\mathbf{y}_1\}的 n\times n 阶正交投影矩阵。

图一Gram-Schmidt 正交化的第一步骤

 
继续下一个步骤，将 \mathbf{x}_3 投影至 \mathbf{y}_1 和 \mathbf{y}_2 所扩张的子空间(平面) 的分量扣除可得\mathbf{y}_3。因为 \mathbf{y}_1 正交于\mathbf{y}_2(见图二)，

\mathbf{y}_3=\displaystyle\mathbf{x}_3-\frac{\mathbf{y}_1^T\mathbf{x}_3}{\mathbf{y}_1^T\mathbf{y}_1}\mathbf{y}_1-\frac{\mathbf{y}_2^T\mathbf{x}_3}{\mathbf{y}_2^T\mathbf{y}_2}\mathbf{y}_2。

上式也有对应于正交投影矩阵的推导。设Y=\begin{bmatrix} \mathbf{y}_1&\mathbf{y}_2 \end{bmatrix}，将 \mathbf{x}_3 至 Y 的行空间 \mathrm{span}\{\mathbf{y}_1,\mathbf{y}_2\} 的投影量从 \mathbf{x}_3 扣除即得\mathbf{y}_3，计算式如下：

\begin{aligned} \mathbf{y}_3&=\mathbf{x}_3-Y(Y^TY)^{-1}Y^{T}\mathbf{x}_3\\ &=\mathbf{x}_3-\begin{bmatrix} \mathbf{y}_1&\mathbf{y}_2 \end{bmatrix}\begin{bmatrix} \mathbf{y}_1^T\mathbf{y}_1&0\\ 0&\mathbf{y}_2^T\mathbf{y}_2 \end{bmatrix}^{-1}\begin{bmatrix} \mathbf{y}_1^T\\ \mathbf{y}_2^T \end{bmatrix}\mathbf{x}_3\\ &=\mathbf{x}_3-\displaystyle\left(\frac{\mathbf{y}_1\mathbf{y}_1^T}{\mathbf{y}_1^T\mathbf{y}_1}+\frac{\mathbf{y}_2\mathbf{y}_2^T}{\mathbf{y}_2^T\mathbf{y}_2}\right)\mathbf{x}_3.\end{aligned}

最后再单位化正交向量集\{\mathbf{y}_1,\mathbf{y}_2,\mathbf{y}_3\}，令\mathbf{q}_i=\mathbf{y}_i/\Vert\mathbf{y}_i\Vert，i=1,2,3。

图二Gram-Schmidt 正交化的第二步骤

 
请注意，Gram-Schmidt 单位化过程显示新基底向量 \mathbf{y}_i 可以表示为旧基底向量 \mathbf{x}_1,\ldots,\mathbf{x}_i 的线性组合。反过来说也成立，即 \mathbf{x}_i 可写为 \mathbf{y}_1,\ldots,\mathbf{y}_i 的线性组合，如下：

\begin{aligned} \mathbf{x}_1&=\mathbf{y}_1\\ \mathbf{x}_2&=\displaystyle\frac{\mathbf{y}_1^T\mathbf{x}_2}{\mathbf{y}_1^T\mathbf{y}_1}\mathbf{y}_1+\mathbf{y}_2\\ \mathbf{x}_3&=\frac{\mathbf{y}_1^T\mathbf{x}_3}{\mathbf{y}_1^T\mathbf{y}_1}\mathbf{y}_1+\frac{\mathbf{y}_2^T\mathbf{x}_3}{\mathbf{y}_2^T\mathbf{y}_2}\mathbf{y}_2+\mathbf{y}_3.\end{aligned}

如果进一步将单位化结果纳入上式，直接替换 \mathbf{y}_i 为\mathbf{q}_i，就有下列形式：

\begin{aligned} \mathbf{x}_1&=r_{11}\mathbf{q}_1\\ \mathbf{x}_2&=r_{12}\mathbf{q}_1+r_{22}\mathbf{q}_2\\ \mathbf{x}_3&=r_{13}\mathbf{q}_1+r_{23}\mathbf{q}_2+r_{33}\mathbf{q}_3.\end{aligned}

利用 \{\mathbf{q}_1, \mathbf{q}_2, \mathbf{q}_3\} 的单范正交性质，组合权重 r_{ij} 即为 \mathbf{q}_i 与 \mathbf{x}_j 的内积，r_{ij}=\mathbf{q}_i^T\mathbf{x}_j，例如，

\begin{aligned} \mathbf{q}_2^T\mathbf{x}_3&=\mathbf{q}_2^T(r_{13}\mathbf{q}_1+r_{23}\mathbf{q}_2+r_{33}\mathbf{q}_3)=r_{23}\mathbf{q}_2^T\mathbf{q}_2=r_{23}\end{aligned}。

将前述方程组写成矩阵形式即得到著名的QR 分解式：

\begin{aligned} A&=\begin{bmatrix} \mathbf{x}_1&\mathbf{x}_2&\mathbf{x}_3 \end{bmatrix}\\ &=\begin{bmatrix} \mathbf{q}_1&\mathbf{q}_2&\mathbf{q}_3 \end{bmatrix}\begin{bmatrix} r_{11}&r_{12}&r_{13}\\ 0&r_{22}&r_{23}\\ 0&0&r_{33} \end{bmatrix}\\ &=\begin{bmatrix} \mathbf{q}_1&\mathbf{q}_2&\mathbf{q}_3 \end{bmatrix}\begin{bmatrix} \mathbf{q}_1^T\mathbf{x}_1&\mathbf{q}_1^T\mathbf{x}_2&\mathbf{q}_1^T\mathbf{x}_3\\ 0&\mathbf{q}_2^T\mathbf{x}_2&\mathbf{q}_2^T\mathbf{x}_3\\ 0&0&\mathbf{q}_3^T\mathbf{x}_3 \end{bmatrix}\\ &=QR.\end{aligned}

因为 \mathbf{y}_i=\Vert\mathbf{y}_i\Vert\mathbf{q}_i 且\mathbf{q}_i\perp\hbox{span}\{\mathbf{y}_1,\ldots,\mathbf{y}_{i-1}\}，主对角元 r_{ii} 亦可表示为

\begin{aligned} r_{ii}&=\mathbf{q}_i^T\mathbf{x}_i=\mathbf{q}_i^T\mathbf{y}_i=\mathbf{q}_i^T(\Vert\mathbf{y}_i\Vert\mathbf{q}_i)=\Vert\mathbf{y}_i\Vert\end{aligned}。

 
下面用一个例子来说明Gram-Schmidt 正交化演算程序，考虑

A=\left[\!\!\begin{array}{rrr} 1&2&-1\\ 1&-1&2\\ -1&1&1\\ 1&-1&2 \end{array}\!\!\right]。

矩阵 A 的行向量(column vector) 就是\mathbf{x}_1,\mathbf{x}_2,\mathbf{x}_3，下面用演算法形式记录计算步骤。

1. 正交化：

\begin{aligned} \mathbf{y}_1&\leftarrow\mathbf{x}_1=\left[\!\!\begin{array}{r} 1\\ 1\\ -1\\ 1 \end{array}\!\!\right],~~\Vert\mathbf{y}_1\Vert=2\\ \mathbf{y}_2&\leftarrow\mathbf{x}_2-\displaystyle\frac{\mathbf{y}_1^T\mathbf{x}_2}{\Vert\mathbf{y}_1\Vert^2}\mathbf{y}_1=\frac{3}{4}\left[\!\!\begin{array}{r} 3\\ -1\\ 1\\ -1 \end{array}\!\!\right],~~\Vert\mathbf{y}_2\Vert=\frac{3\sqrt{3}}{2}\\ \mathbf{y}_3&\leftarrow\mathbf{x}_3-\frac{\mathbf{y}_1^T\mathbf{x}_3}{\Vert\mathbf{y}_1\Vert^2}\mathbf{y}_1-\frac{\mathbf{y}_2^T\mathbf{x}_3}{\Vert\mathbf{y}_2\Vert^2}\mathbf{y}_2=\begin{bmatrix} 0\\ 1\\ 2\\ 1 \end{bmatrix},~~\Vert\mathbf{y}_3\Vert=\sqrt{6}.\end{aligned}

2. 单位化：

\begin{aligned} \mathbf{q}_1&\leftarrow\frac{\mathbf{y}_1}{\Vert\mathbf{y}_1\Vert}=\frac{1}{2}\left[\!\!\begin{array}{r} 1\\ 1\\ -1\\ 1 \end{array}\!\!\right]\\ \mathbf{q}_2&\leftarrow\frac{\mathbf{y}_2}{\Vert\mathbf{y}_2\Vert}=\frac{1}{2\sqrt{3}}\left[\!\!\begin{array}{r} 3\\ -1\\ 1\\ -1 \end{array}\!\!\right]\\ \mathbf{q}_3&\leftarrow\frac{\mathbf{y}_3}{\Vert\mathbf{y}_3\Vert}=\frac{1}{\sqrt{6}}\begin{bmatrix} 0\\ 1\\ 2\\ 1 \end{bmatrix}.\end{aligned}

合并结果便得到 Q 矩阵：

\begin{aligned} Q&=\displaystyle\begin{bmatrix} \mathbf{q}_1&\mathbf{q}_2&\mathbf{q}_3 \end{bmatrix}=\left[\!\!\begin{array}{rrc} \frac{1}{2}&\frac{3}{2\sqrt{3}}&0\\[0.3em] \frac{1}{2}&-\frac{1}{2\sqrt{3}}&\frac{1}{\sqrt{6}}\\[0.3em] -\frac{1}{2}&\frac{1}{2\sqrt{3}}&\frac{2}{\sqrt{6}}\\[0.3em] \frac{1}{2}&-\frac{1}{2\sqrt{3}}&\frac{1}{\sqrt{6}} \end{array}\!\!\right]\end{aligned}，

但 R 矩阵的上三角元还需要耗费一些计算：

\begin{aligned} R&=\displaystyle\begin{bmatrix} \Vert\mathbf{y}_1\Vert&\mathbf{q}_1^T\mathbf{x}_2&\mathbf{q}_1^T\mathbf{x}_3\\ 0&\Vert\mathbf{y}_2\Vert&\mathbf{q}_2^T\mathbf{x}_3\\ 0&0&\Vert\mathbf{y}_3\Vert \end{bmatrix}=\left[\!\!\begin{array}{ccr} 2&-\frac{1}{2}&1\\[0.3em] 0&\frac{3\sqrt{3}}{2}&-\sqrt{3}\\ 0&0&\sqrt{6} \end{array}\!\!\right]\end{aligned}。

 
上述实矩阵的QR 分解可以推广至广义内积空间\mathcal{V}，作法是把几何内积算式 \mathbf{x}^T\mathbf{y} 取代为广义内积\left\langle\mathbf{x},\mathbf{y}\right\rangle，将数字 3 代回n，再加上一些「\cdots」即可。设 m\times n 阶矩阵 A 包含 m 维线性独立行向量\mathbf{x}_1,\ldots,\mathbf{x}_n，其QR 分解式为

\begin{aligned} A&=QR=\begin{bmatrix} \mathbf{q}_1&\mathbf{q}_2&\cdots&\mathbf{q}_n \end{bmatrix}\begin{bmatrix} \Vert\mathbf{y}_1\Vert&\left\langle\mathbf{q}_1,\mathbf{x}_2\right\rangle&\cdots&\left\langle\mathbf{q}_1,\mathbf{x}_n\right\rangle\\ 0&\Vert\mathbf{y}_2\Vert&\cdots&\left\langle\mathbf{q}_2,\mathbf{x}_n\right\rangle\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\cdots&\Vert\mathbf{y}_n\Vert \end{bmatrix}\end{aligned}，

其中 m\times n 阶矩阵 Q 包含单范正交的行向量，R则为 n\times n 阶上三角矩阵，主对角元的计算如下：\Vert\mathbf{y}_1\Vert=\Vert\mathbf{x}_1\Vert，当i>1，

\Vert\mathbf{y}_i\Vert=\Vert\mathbf{x}_i-\left\langle\mathbf{q}_1,\mathbf{x}_i\right\rangle\mathbf{q}_1-\cdots\left\langle\mathbf{q}_{i-1},\mathbf{x}_i\right\rangle\mathbf{q}_{i-1}\Vert。

矩阵 A 的行空间与 Q 的行空间相等，可知 R 为可逆矩阵，也就是说 R 的主对角元皆不为零。

 
利用QR 分解可化简线性方程 A\mathbf{x}=\mathbf{b}。将 A=QR 代入前式，QR\mathbf{x}=\mathbf{b}。等号两边左乘Q^{T}，利用Q^TQ=I_n，就有

R\mathbf{x}=Q^{T}\mathbf{b}。

先算出\mathbf{c}=Q^T\mathbf{b}，再使用反向迭代即能解出R\mathbf{x}=\mathbf{c}。读者或许纳闷：以高斯消去法解线性方程比QR 分解简单容易，何须如此费事呢？从表面上看，似乎如此。然而，在一些特定的问题中，QR 分解的精确度比高斯消去法高；另外，QR 分解有它自己的典型应用──解最小平方法。当方程式 A\mathbf{x}=\mathbf{b} 无解时，我们可以考虑它的最小平方近似解：

\displaystyle \min_{\mathbf{x}}\Vert A\mathbf{x}-\mathbf{b}\Vert^2。

问题转而求正规方程 A^{T}A\hat{\mathbf{x}}=A^T\mathbf{b} 的解(见“从线性变换解释最小平方近似”)。若\hbox{rank}A=n，即 m\times n 阶矩阵 A 有线性独立的行向量，将 A=QR 代入正规方程式，等号左边是A^TA\hat{\mathbf{x}}=(QR)^{T}QR\hat{\mathbf{x}}=R^TQ^TQR\hat{\mathbf{x}}=R^TR\hat{\mathbf{x}}，等号右边是A^T\mathbf{b}=R^{T}Q^{T}\mathbf{b}。因为 R 是可逆的，R^TR\hat{\mathbf{x}}=R^TQ^T\mathbf{b}左乘(R^T)^{-1}，即得等价的正规方程

R\hat{\mathbf{x}}=Q^T\mathbf{b}。

这与之前化简线性方程得到的式子相同。

继续阅读：
This entry was posted in线性代数专栏,内积空间and tagged , ,,,. Bookmark the permalink .

6 Responses to Gram-Schmidt 正交化与QR 分解

  1. d897203 says:
    05/17/2015 at 11:45 pm

    在将x_3 写成y_1, y_2 和y_3 的线性组合那一段，
    y_3 的系数好像有打错字。

    Reply
  2. 计组小粉丝 says:
    01/03/2017 at 10:35 am

    明显地，\mathbf{y}_1\perp\mathbf{y}_2。上式的扣除量(投影量) 还有另一种表达方式，因为\frac{\mathbf{y}_1^T\mathbf{x}_2}{\mathbf{y}_1^T\mathbf{y}_1} 是一个纯量，利用矩阵乘法结合律可得

    \begin{aligned} \displaystyle\frac{\mathbf{y}_1^T\mathbf{x}_2}{\mathbf{y}_1^T\mathbf{y}_1}\mathbf{y}_1&=\mathbf{y}_1\frac{\mathbf{y}_1^T\mathbf{x}_2}{\mathbf{y}_1^T\mathbf{y}_1}=\frac{1}{\mathbf{y}_1^T\mathbf{y}_1}\mathbf{y}_1\mathbf{y}_1^T\mathbf{x}_2=\frac{\mathbf{y}_1\mathbf{y}_1^T}{\mathbf{y}_1^T\mathbf{y}_1}\mathbf{x}_2\end{aligned}

    第三个式子的分母y^T 和y 忘了加上下标“1”

    Reply
  3. 计组小粉丝 says:
    01/03/2017 at 10:41 am

    抱歉
    是
    \begin{aligned} \displaystyle\frac{\mathbf{y}_1^T\mathbf{x}_2}{\mathbf{y}_1^T\mathbf{y}_1}\mathbf{y}_1&=\mathbf{y}_1\frac{\mathbf{y}_1^T\mathbf{x}_2}{\mathbf{y}_1^T\mathbf{y}_1}=\frac{1}{\mathbf{y}_1^T\mathbf{y}_1}\mathbf{y}_1\mathbf{y}_1^T\mathbf{x}_2=\frac{\mathbf{y}_1\mathbf{y}_1^T}{\mathbf{y}_1^T\mathbf{y}_1}\mathbf{x}_2\end{aligned}

    Reply
  4. bao says:
    11/25/2017 at 5:42 pm

    老师好，r(i,i) 推导的第二等号没懂？

    Reply

Leave a Reply