QR分解

维基百科，自由的百科全书

QR分解法是三種将矩阵分解的方式之一。這種方式，把矩阵分解成一个正交矩阵与一个上三角矩阵的积。

[编辑] QR分解的求法

QR分解的实际计算有很多方法，例如en:Givens rotation、Householder变换，以及Gram-Schmidt正交化等等。每一种方法都有其优点和不足。

[编辑] Gram-Schmidt正交化

参见Gram-Schmidt正交化

Recall the Gram-Schmidt method, with the vectors to be considered in the process as columns of the matrix $A=(\mathbf{a}_1| \cdots|\mathbf{a}_n)$ . Then

$\mathbf{u}_1 = \mathbf{a}_1, \qquad\mathbf{e}_1 = {\mathbf{u}_1 \over \|\mathbf{u}_1\|}$

$\mathbf{u}_2 = \mathbf{a}_2-\mathrm{proj}_{\mathbf{e}_1}\,\mathbf{a}_2, \qquad\mathbf{e}_2 = {\mathbf{u}_2 \over \|\mathbf{u}_2\|}$

$\mathbf{u}_3 = \mathbf{a}_3-\mathrm{proj}_{\mathbf{e}_1}\,\mathbf{a}_3-\mathrm{proj}_{\mathbf{e}_2}\,\mathbf{a}_3, \qquad\mathbf{e}_3 = {\mathbf{u}_3 \over \|\mathbf{u}_3\|}$

$\vdots$

$\mathbf{u}_k = \mathbf{a}_k-\sum_{j=1}^{k-1}\mathrm{proj}_{\mathbf{e}_j}\,\mathbf{a}_k,\qquad\mathbf{e}_k = {\mathbf{u}_k\over\|\mathbf{u}_k\|}$

Naturally then, we rearrange the equations so the a_is are the subject, to get the following

$\mathbf{a}_1 = \mathbf{e}_1\|\mathbf{u}_1\|$

$\mathbf{a}_2 = \mathrm{proj}_{\mathbf{e}_1}\,\mathbf{a}_2+\mathbf{e}_2\|\mathbf{u}_2\|$

$\mathbf{a}_3 = \mathrm{proj}_{\mathbf{e}_1}\,\mathbf{a}_3+\mathrm{proj}_{\mathbf{e}_2}\,\mathbf{a}_3+\mathbf{e}_3\|\mathbf{u}_3\|$

$\vdots$

$\mathbf{a}_k = \sum_{j=1}^{k-1}\mathrm{proj}_{\mathbf{e}_j}\,\mathbf{a}_k+\mathbf{e}_k\|\mathbf{u}_k\|$

Each of these projections of the vectors $\mathbf{a}_i$ onto one of these $e j$ are merely the inner product of the two, since the vectors are normed.

Now these equations can be written in matrix form, viz.,

$\left(\mathbf{e}_1\left|\ldots\right|\mathbf{e}_n\right) \begin{pmatrix} \|\mathbf{u}_1\| & \langle\mathbf{e}_1,\mathbf{a}_2\rangle & \langle\mathbf{e}_1,\mathbf{a}_3\rangle & \ldots \\ 0 & \|\mathbf{u}_2\| & \langle\mathbf{e}_2,\mathbf{a}_3\rangle & \ldots \\ 0 & 0 & \|\mathbf{u}_3\| & \ldots \\ \vdots & \vdots & \vdots & \ddots \end{pmatrix}$

But the product of each row and column of the matrices above give us a respective column of A that we started with, and together, they give us the matrix A, so we have factorized A into an orthogonal matrix Q (the matrix of e_ks), via Gram Schmidt, and the obvious upper triangular matrix as a remainder R.

Alternatively, $\begin{matrix} R \end{matrix}$ can be calculated as follows:

Recall that $\begin{matrix}Q\end{matrix} = \left(\mathbf{e}_1\left|\ldots\right|\mathbf{e}_n\right).$ Then, we have

$\begin{matrix} R = Q^{T}A = \end{matrix} \begin{pmatrix} \langle\mathbf{e}_1,\mathbf{a}_1\rangle & \langle\mathbf{e}_1,\mathbf{a}_2\rangle & \langle\mathbf{e}_1,\mathbf{a}_3\rangle & \ldots \\ 0 & \langle\mathbf{e}_2,\mathbf{a}_2\rangle & \langle\mathbf{e}_2,\mathbf{a}_3\rangle & \ldots \\ 0 & 0 & \langle\mathbf{e}_3,\mathbf{a}_3\rangle & \ldots \\ \vdots & \vdots & \vdots & \ddots \end{pmatrix}.$

Note that $\langle\mathbf{e}_j,\mathbf{a}_j\rangle = \|\mathbf{u}_j\|,$ $\langle\mathbf{e}_j,\mathbf{a}_k\rangle = 0 \mathrm{~~for~~} j > k,$ and $Q Q T = I$ , so $Q T = Q - 1$ .