QR分解とグラムシュミットの直交化法・定義・例題・計算方法について
1. QR分解とは
ここで、
- \(Q\) は \(m \times n\) 行列で、列ベクトルが直交する（つまり、\(Q^T Q = I\) となる）行列です。ただし、n×n行列になる場合は直交行列となる。
- \(R\) は \(n \times n\) の上三角行列で、上三角行列とは対角成分より下の部分がすべてゼロである行列を指します。
QR分解を求める方法として、グラム・シュミットの直交化法や、ハウスホルダー変換、ギヴンズ回転といった手法がよく用いられます。
2. QR分解を求める方法
まず、行列 \( X \) を \( n \times n \) の正則行列としますここで、行列 \( X \) を次のように列ベクトル \( \mathbf{x}_1, \mathbf{x}_2, \dots, \mathbf{x}_n \) で表します。
\[ X = \begin{bmatrix} \mathbf{x}_1 \mathbf{x}_2 \dots \mathbf{x}_n\end{bmatrix} \]
このとき、各列ベクトル \( \mathbf{x}_i \) は \( \mathbb{R}^n \) に属し、互いに線形独立です。
次に、グラムシュミットの直交化法を用いて、これらの線形独立なベクトル \( \mathbf{x}_1, \mathbf{x}_2, \dots, \mathbf{x}_n \) を用いて、直交ベクトル \( \mathbf{y}_1, \mathbf{y}_2, \dots, \mathbf{y}_n \) を構成します。
最初のベクトル \( \mathbf{y}_1 \) は次のようになります。
\[ \mathbf{y}_1 = \frac{\mathbf{x}_1}{\|\mathbf{x}_1\|} \]
このとき、\( \mathbf{x}_1 \) は次のように \( \mathbf{y}_1 \) を用いて表されます。
\[ \mathbf{x}_1 = \|\mathbf{x}_1\| \mathbf{y}_1 \]
2番目のベクトル \( \mathbf{y}_2 \) は次のようになります。
\[ \mathbf{y}_2 = \frac{\mathbf{x}_2 – (\mathbf{y}_1, \mathbf{x}_2)\mathbf{y}_1}{\|\mathbf{x}_2 – (\mathbf{y}_1, \mathbf{x}_2)\mathbf{y}_1\|} \]
このとき、\( \mathbf{x}_2 \) は次のように \( \mathbf{y}_1 \) と \( \mathbf{y}_2 \) を用いて表されます。
\[ \mathbf{x}_2 = (\mathbf{y}_1, \mathbf{x}_2) \mathbf{y}_1 + \|\mathbf{x}_2 – (\mathbf{y}_1, \mathbf{x}_2)\mathbf{y}_1\| \mathbf{y}_2 \]
同様に、3番目のベクトル \( \mathbf{y}_3 \) は次のようになります。
\[ \mathbf{y}_3 = \frac{\mathbf{x}_3 – (\mathbf{y}_1, \mathbf{x}_3)\mathbf{y}_1 – (\mathbf{y}_2, \mathbf{x}_3)\mathbf{y}_2}{\|\mathbf{x}_3 – (\mathbf{y}_1, \mathbf{x}_3)\mathbf{y}_1 – (\mathbf{y}_2, \mathbf{x}_3)\mathbf{y}_2\|} \]
このとき、\( \mathbf{x}_3 \) は次のように \( \mathbf{y}_1 \), \( \mathbf{y}_2 \), \( \mathbf{y}_3 \) を用いて表されます。
\[ \mathbf{x}_3 = (\mathbf{y}_1, \mathbf{x}_3) \mathbf{y}_1 + (\mathbf{y}_2, \mathbf{x}_3) \mathbf{y}_2 + \|\mathbf{x}_3 – (\mathbf{y}_1, \mathbf{x}_3)\mathbf{y}_1 – (\mathbf{y}_2, \mathbf{x}_3)\mathbf{y}_2\| \mathbf{y}_3 \]
\( i \) 番目のベクトル \( \mathbf{y}_i \) は次のようになります。
\[ \mathbf{y}_i = \frac{\mathbf{x}_i – \sum_{k=1}^{i-1} (\mathbf{y}_k, \mathbf{x}_i)\mathbf{y}_k}{\|\mathbf{x}_i – \sum_{k=1}^{i-1} (\mathbf{y}_k, \mathbf{x}_i)\mathbf{y}_k\|} \]
このとき、\( \mathbf{x}_i \) は次のように \( \mathbf{y}_1, \mathbf{y}_2, \dots, \mathbf{y}_i \) を用いて表されます。
\[ \mathbf{x}_i = \sum_{j=1}^{i-1} (\mathbf{y}_j, \mathbf{x}_i) \mathbf{y}_j + \|\mathbf{x}_i – \sum_{k=1}^{i-1} (\mathbf{y}_k, \mathbf{x}_i)\mathbf{y}_k\| \mathbf{y}_i \]
次に、行列 \( Q \) と \( R \) を以下のように定義します。
行列 \( Q \) は、生成した直交ベクトル \( \mathbf{y}_1, \mathbf{y}_2, \dots, \mathbf{y}_n \) を列に持つ行列として定義します。
\[ Q = [\mathbf{y}_1 \ \mathbf{y}_2 \ \dots \ \mathbf{y}_n] \]
行列 \( R \) は、各ベクトル \( \mathbf{x}_i \) が \( \mathbf{y}_j \) の線形結合として表されることを利用して、以下のように定義されます。
\[ R = \begin{bmatrix} \|\mathbf{x}_1\| & (\mathbf{y}_1, \mathbf{x}_2) & \dots & (\mathbf{y}_1, \mathbf{x}_n) \\ 0 & \|\mathbf{x}_2 – (\mathbf{y}_1, \mathbf{x}_2) \mathbf{y}_1\| & \dots & (\mathbf{y}_2, \mathbf{x}_n) \\ 0 & 0 & \ddots & \vdots \\ 0 & 0 & \dots & \|\mathbf{x}_n – \sum_{k=1}^{n-1} (\mathbf{y}_k, \mathbf{x}_n) \mathbf{y}_k\| \end{bmatrix} \]
これを行列形式にまとめると、行列 \( X \) は次のように表されます。
\[ X = QR \]
3. QR分解を求める例題
3.1. 例題1（2×2行列のQR分解）
\[ A = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix} \]
まず、行列 \(A\) の各列を直交化します。
最初の列ベクトル \( \mathbf{a}_1 = \begin{pmatrix} 2 \\ 1 \end{pmatrix} \)
2つ目の列ベクトル \( \mathbf{a}_2 = \begin{pmatrix} 1 \\ 2 \end{pmatrix} \) とします。
最初のベクトル \( \mathbf{u}_1 \) は \( \mathbf{a}_1 \) そのものになります。
\[ \mathbf{u}_1 = \mathbf{a}_1 = \begin{pmatrix} 2 \\ 1 \end{pmatrix} \]
次に、2つ目のベクトル \( \mathbf{u}_2 \) を \( \mathbf{a}_2 \) と \( \mathbf{u}_1 \) の線形結合を用いて直交化します。
\[ \mathbf{u}_2 = \mathbf{a}_2 – \frac{\mathbf{u}_1 \cdot \mathbf{a}_2}{\mathbf{u}_1 \cdot \mathbf{u}_1} \mathbf{u}_1 \]
\( \mathbf{u}_1 \) と \( \mathbf{a}_2 \) の内積を計算し、それを \( \mathbf{u}_1 \) の内積で割ります：
\[ \mathbf{u}_1 \cdot \mathbf{a}_2 = 2 \times 1 + 1 \times 2 = 4 \]
\[ \mathbf{u}_1 \cdot \mathbf{u}_1 = 2^2 + 1^2 = 5 \]
したがって、係数は \( \frac{4}{5} \) になります。これに基づき \( \mathbf{u}_2 \) を計算します：
\[ \mathbf{u}_2 = \begin{pmatrix} 1 \\ 2 \end{pmatrix} – \frac{4}{5} \begin{pmatrix} 2 \\ 1 \end{pmatrix} = \begin{pmatrix} \frac{-3}{5} \\ \frac{6}{5} \end{pmatrix} \]
直交ベクトル \( \mathbf{u}_1 \) と \( \mathbf{u}_2 \) を正規化します。
\[ \mathbf{q}_1 = \frac{\mathbf{u}_1}{\|\mathbf{u}_1\|} = \frac{1}{\sqrt{5}} \begin{pmatrix} 2 \\ 1 \end{pmatrix}\]
\[ \mathbf{q}_2 = \frac{\mathbf{u}_2}{\|\mathbf{u}_2\|} = \frac{1}{\sqrt{5}} \begin{pmatrix} -1 \\ 2 \end{pmatrix} \]
これにより、行列\( Q \) は次のようになります。
\[ Q = \begin{pmatrix} \frac{2}{\sqrt{5}} & -\frac{1}{\sqrt{5}} \\ \frac{1}{\sqrt{5}} & \frac{2}{\sqrt{5}} \end{pmatrix} = \begin{pmatrix} \frac{2\sqrt{5}}{5} & -\frac{\sqrt{5}}{5} \\ \frac{\sqrt{5}}{5} & \frac{2\sqrt{5}}{5} \end{pmatrix} \]
次に、直交行列Qの性質を用いて、行列 \( R \) は次のように求められます。
\[ R = Q^T A = \begin{pmatrix} \frac{2\sqrt{5}}{5} & \frac{\sqrt{5}}{5} \\ -\frac{\sqrt{5}}{5} & \frac{2\sqrt{5}}{5} \end{pmatrix} \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix} = \begin{pmatrix} \sqrt{5} & \frac{4\sqrt{5}}{5} \\ 0 & \frac{3\sqrt{5}}{5} \end{pmatrix} \]
ここで、$QQ^T=E$となることを利用した。
したがって、QR分解の結果は次のようになります。
\[ A = QR = \begin{pmatrix} \frac{2\sqrt{5}}{5} & -\frac{\sqrt{5}}{5} \\ \frac{\sqrt{5}}{5} & \frac{2\sqrt{5}}{5} \end{pmatrix} \begin{pmatrix} \sqrt{5} & \frac{4\sqrt{5}}{5} \\ 0 & \frac{3\sqrt{5}}{5} \end{pmatrix} \]
3.2. 例題2（3×2行列のQR分解）
\[ A = \begin{pmatrix} 1 & 1 \\ 1 & 0 \\ 0 & 1 \end{pmatrix} \]
まず、行列 \(A\) の各列を直交化します。
最初の列ベクトル \( \mathbf{a}_1 = \begin{pmatrix} 1 \\ 1 \\ 0 \end{pmatrix} \)
2つ目の列ベクトル \( \mathbf{a}_2 = \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix} \)
とする。
最初のベクトル \( \mathbf{u}_1 \) は \( \mathbf{a}_1 \) そのものになります。
\[ \mathbf{u}_1 = \mathbf{a}_1 = \begin{pmatrix} 1 \\ 1 \\ 0 \end{pmatrix} \]
次に、2つ目のベクトル \( \mathbf{u}_2 \) を \( \mathbf{a}_2 \) と \( \mathbf{u}_1 \) の線形結合を用いて直交化します。
\[ \mathbf{u}_2 = \mathbf{a}_2 – \frac{\mathbf{u}_1 \cdot \mathbf{a}_2}{\mathbf{u}_1 \cdot \mathbf{u}_1} \mathbf{u}_1 \]
\( \mathbf{u}_1 \) と \( \mathbf{a}_2 \) の内積を計算し、それを \( \mathbf{u}_1 \) の内積で割ります：
\[ \mathbf{u}_1 \cdot \mathbf{a}_2 = 1 \times 1 + 1 \times 0 + 0 \times 1 = 1 \]
\[ \mathbf{u}_1 \cdot \mathbf{u}_1 = 1^2 + 1^2 + 0^2 = 2 \]
したがって、係数は \( \frac{1}{2} \) になります。これに基づき \( \mathbf{u}_2 \) を計算します：
\[ \mathbf{u}_2 = \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix} – \frac{1}{2} \begin{pmatrix} 1 \\ 1 \\ 0 \end{pmatrix} = \begin{pmatrix} \frac{1}{2} \\ -\frac{1}{2} \\ 1 \end{pmatrix} \]
直交ベクトル \( \mathbf{u}_1 \) と \( \mathbf{u}_2 \) を正規化します。
\[ \mathbf{q}_1 = \frac{\mathbf{u}_1}{\|\mathbf{u}_1\|} = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 \\ 1 \\ 0 \end{pmatrix} \]\[ \mathbf{q}_2 = \frac{\mathbf{u}_2}{\|\mathbf{u}_2\|} = \frac{1}{\sqrt{6}}\begin{pmatrix} 1 \\ -1 \\ 2 \end{pmatrix}\]
これにより、行列\( Q \) は次のようになります。
\[ Q = \begin{pmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{6}} \\ \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{6}} \\ 0 & \frac{2}{\sqrt{6}} \end{pmatrix} \]
次に、行列Qの性質を用いて、行列 \( R \) は次のように求められます。
\[ R = Q^T A = \begin{pmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} & 0 \\ \frac{1}{\sqrt{6}} & -\frac{1}{\sqrt{6}} & \frac{2}{\sqrt{6}} \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 1 & 0 \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} \sqrt{2} & \frac{1}{\sqrt{2}} \\ 0 & \frac{3}{\sqrt{6}} \end{pmatrix} \]
ここで、$QQ^T=E$となることを利用した。
したがって、QR分解の結果は次のようになります。
\[ A = QR = \begin{pmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{6}} \\ \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{6}} \\ 0 & \frac{2}{\sqrt{6}} \end{pmatrix} \begin{pmatrix} \sqrt{2} & \frac{1}{\sqrt{2}} \\ 0 & \frac{3}{\sqrt{6}} \end{pmatrix} \]
