グラム・シュミットの直交化法とQR分解

この記事では、グラム・シュミットの直交化法とQR分解について解説します。

グラム・シュミットの直交化法

ベクトル $a_1, a_2, \ldots, a_n\in {\bf R}^n$ は一次独立だとします。このとき、 $\{a_1,a_2,\ldots,a_n\}$ は ${\bf R}^n$ の基底となります。しかし、 $\{a_1,a_2,\ldots,a_n\}$ は ${\bf R}^n$ の正規直交基底ではないかもしれません。グラム・シュミットの直交化法は ${\bf R}^n$ の任意の基底 $\{a_1,a_2,\ldots,a_n\}$ から以下のように正規直交基底を構成する方法です。\begin{align} q_1 &:=\frac{a_1}{||a_1||}\\ q_k &:= \frac{a_k-P_{q_1,\ldots,q_{k-1}}(a_k)}{||a_k-P_{q_1,\ldots,q_{k-1}}(a_k)||}\quad (k=2,\ldots,n) \end{align}

ただし、 $P_{q_1,\ldots,q_{k-1}}$ は ${\rm Im}\, Q_{k-1}$ 上への直交射影で、\begin{align}Q_{k-1}:= \begin{pmatrix} q_1 & q_2 & \cdots & q_{k-1} \end{pmatrix}\in {\bf R}^{n\times (k-1)}\end{align}

です。ベクトル $q_i$ の作り方から $Q_{k-1}^TQ_{k-1}=I$ となるので、直交射影 $P_{q_1,\ldots,q_{k-1}}$ は

で説明したように、\begin{align}P_{q_1,\ldots,q_{k-1}} = Q_{k-1}Q_{k-1}^T=q_1q_1^T+q_2q_2^T+\cdots+ q_{k-1}q_{k-1}^T \end{align} となります。

${\bf R}^2$ の場合のグラム・シュミットの直交化法は次のような感じでイメージできます。

f:id:ogyahogya:20191228102436p:plain

${\bf R}^3$ の場合は次のような感じです。

f:id:ogyahogya:20191228102519p:plain

QR分解

ベクトル $a_1, a_2, \ldots, a_n\in {\bf R}^n$ は一次独立だとして、\begin{align} A:= \begin{pmatrix} a_1 & a_2 & \cdots & a_n \end{pmatrix}\in {\bf R}^{n\times n} \end{align} だとします。グラム・シュミットの直交化法により、 $c_k:=||a_k-P_{q_1,\ldots,q_{k-1}}(a_k)||$ とすると、以下のように行列 $A$ を分解できます。

f:id:ogyahogya:20191228114946p:plain

f:id:ogyahogya:20191228115047p:plain

このように、行列 $A$ を直交行列 $Q$ と上三角行列 $R$ へ分解することを $A$ のQR分解と言います。QR分解の構成から、QR分解することはグラム・シュミットの直交化をすることと同値ですので、 $A$ の各列ベクトルが一次独立なら常に $A$ のQR分解を実行することができます。

注意1

$m\geq n$ でベクトル $a_1, a_2, \ldots, a_n\in {\bf R}^m$ は一次独立だとします ( $m＜n$ の場合は一次独立にならないので考えません）。 $m=n$ の場合は上と同じなので、 $m＞n$ の場合の注意を書いときます。

$m＞n$ の場合も上のグラム・シュミットの直交化法はまったく同じように実行できて、 $a_1, a_2, \ldots, a_n\in {\bf R}^m$ から正規直交ベクトル $q_1, q_2, \ldots, q_n\in {\bf R}^m$ を得ることができます。このとき\begin{align} A:= \begin{pmatrix} a_1 & a_2 & \cdots & a_n \end{pmatrix}\in {\bf R}^{m\times n} \end{align} は\begin{align} A=QR \end{align} というようにQR分解できます。ただし、 $R$ は $m=n$ の場合と同じ $n\times n$ の上三角行列ですが、\begin{align} Q:= \begin{pmatrix} q_1 & q_2 & \cdots & q_n \end{pmatrix}\in {\bf R}^{m\times n} \end{align}は各列が正規直交しているものの、 $m＞n$ なので直交行列とは言えません。このような各列が正規直交している行列全体の集合をシュティーフェル多様体と言い、色々な応用で出てきます。

注意2

$m\geq n$ でベクトル $a_1, a_2, \ldots, a_n\in {\bf C}^m$ は一次独立だとします。注意1との違いはベクトルの成分が実数ではなく、複素数だということです。この場合もグラム・シュミットの直交化法が適用できます。ただし、ノルムの定義や直交射影に若干の変更が必要です。すなわち、 $x\in {\bf R}^m$ の場合のノルムは（陽に書いていませんでしたが）\begin{align} ||x||^2 = x_1^2+x_2^2+\cdots +x_m^2 \end{align} だとしていましたが、 $x\in {\bf C}^m$ のノルムは\begin{align} ||x||^2 = |x_1|^2+|x_2|^2+\cdots +|x_m|^2 \end{align} に変更する必要があります。また、直交射影は\begin{align} P_{q_1,\ldots,q_{k-1}} =Q_{k-1}Q_{k-1}^{\dagger} \end{align} と変更されます。ただし、 $\dagger$ は複素共役転置を表しています。この変更のもとで、\begin{align} A:= \begin{pmatrix} a_1 & a_2 & \cdots & a_n \end{pmatrix}\in {\bf C}^{m\times n} \end{align} は\begin{align} A=QR \end{align} というようにQR分解できます。ただし、 $Q\in {\bf C}^{m\times n}$ は各列が正規直交しており、 $R\in {\bf C}^{n\times n}$ は上三角行列です。さらに、 $m=n$ の場合には $Q\in {\bf C}^{n\times n}$ はユニタリ行列となります。