行列分解の導入

$A \vec{x} = \vec{b}$ のような連立方程式の解法は、特に大規模なシステムでは計算コストが高くなる場合があります。

行列分解は、このプロセスを行列 $A$ をより単純な部分に分解することで簡略化し、段階的に解くことを可能にします。

LU と QR

行列 $A$ を他の構造化された行列に分解します。

LU分解

$A$ を下三角行列と上三角行列に分解：

• ガウス消去法を用いて構築；
• 正方行列に最適。

$$A = LU$$

QR分解

$A$ を直交行列と上三角行列に分解：

• 非正方行列によく使用；
• 最小二乗問題やLU分解が適用できない場合に最適。

$$A = QR$$

LU分解

正方行列から始めます：

$$A = \begin{bmatrix} 4 & 3 \\ 6 & 3 \end{bmatrix}$$

この行列を次のように表現することを目指します：

$$A = LU$$

ここで：

$$L = \begin{bmatrix} 1 & 0 \\ l_{21} & 1 \end{bmatrix},\ \ U = \begin{bmatrix} u_{11} & u_{12} \\ 0 & u_{22} \end{bmatrix}$$

この分解はAが正方かつ可逆の場合に可能です。

重要なポイント：

• 下三角行列は対角線より上の成分がすべてゼロであり、前進代入を簡単にする；
• 上三角行列は対角線より下の成分がゼロであり、後退代入が容易；
• 直交行列は列ベクトルが直交かつ正規化（長さ1）されている；
• この性質によりベクトルの長さや角度が保たれ、最小二乗法の解法や数値安定性の向上に役立つ。

ガウス消去法

ガウス消去法を適用して、左上のピボットの下の要素を消去：

$$R_2 \rarr R_2 - \frac{6}{4}R_1$$

これにより、次のようになります：

$$R'_2 = [0, -1.5]$$

したがって、更新後の行列は次の通り：

$$U = \begin{bmatrix} 4 & 3 \\ 0 & -1.5 \end{bmatrix}$$

また、行基本変形から次が分かります：

$$L = \begin{bmatrix} 1 & 0 \\ 1.5 & 1 \end{bmatrix}$$

重要なポイント：

• ガウス消去法は、各列のピボット要素の下の要素を、ピボット行の定数倍を下の行から引くことで系統的に消去；
• この処理により、Aは上三角行列Uに変換；
• 消去に使われた乗数はLに格納され、AをLUの積として表現可能。

LU分解の結果

検算：

$$A = LU = \begin{bmatrix} 1 & 0 \\ 1.5 & 1 \end{bmatrix} \begin{bmatrix} 4 & 3 \\ 0 & -1.5 \end{bmatrix} = \begin{bmatrix} 4 & 3 \\ 6 & 3 \end{bmatrix}$$

このとき、連立方程式 $A \vec{x} = \vec{b}$ は2段階で解ける：

1. 前進代入で $L \vec{y} = \vec{b}$ を解く；
2. 後退代入で $U \vec{x} = \vec{y}$ を解く。

QR分解

行列 $A$ を2つの行列の積として表現：

$$A = QR$$

ここで：

• $A$ は入力行列（例：データ、係数など）；
• $Q$ は直交行列（列ベクトルが正規直交）；
• $R$ は上三角行列。

形状の例：

$$A = \begin{bmatrix} a_1 & a_2 \\ a_3 & a_4 \end{bmatrix} = \begin{bmatrix} q_1 & q_2 \\ q_3 & q_4 \end{bmatrix} \begin{bmatrix} r_{11} & r_{12} \\ 0 & r_{22} \end{bmatrix}$$

この分解は以下の場合によく使われる：

• 行列Aが正方行列でない場合；
• 最小二乗問題の解法；
• LU分解が安定しない場合。

直交規格直交ベクトルとは？

直交ベクトル

2つのベクトル $u, v$ が直交するとは、内積がゼロであることを意味します：

$$u \cdot v = 0$$

正規化ベクトル

ベクトル $u$ が正規化されているとは、$|u| = 1$ であることを指します。

直交規格直交集合

ベクトルの集合 $\{q_1, q_2, ..., q_k\}$ が直交規格直交であるとは、それぞれが単位長であり、互いに直交していることを意味します：

$$q_i \cdot q_j = \begin{cases} 1,\ \text{if}\ \ i = j,\\ 0,\ \text{if}\ \ i \neq j. \end{cases}$$

重要性：$Q$ の列が直交規格直交であることで、幾何学的性質が保たれ、射影計算が簡単になり、数値的安定性が向上します。

行列Aの定義

次の例から始めます：

$$A = \begin{bmatrix} 4 & 3 \\ 6 & 3 \end{bmatrix}$$

グラム・シュミットの方法を用いて、$A=QR$ となるような行列 $Q$ と $R$ を求めます。 グラム・シュミットの方法は、$A$ の列ベクトルから直交規格直交なベクトル集合を作成します。

つまり、$Q$ のベクトルはすべて互いに直交し（直交）、かつ単位長（正規化）です。この性質により、多くの計算が簡単になり、連立方程式を解く際の数値的安定性が向上します。

ここでの目標は：

• $Q$ の列を直交規格直交にすること；
• 射影を表現する行列 $R$ を作成すること。

最初の基底ベクトルの計算

まず、$A$ の第1列を取り出します：

$$a_1 = \begin{bmatrix} 4 \\ 6 \end{bmatrix}$$

これを正規化するためにノルムを計算します：

$$|a_1| = \sqrt{4^2 + 6^2} = \sqrt{16 + 36} = \sqrt{52}$$

次に：

$$q_1 = \frac{1}{\sqrt{52}} \begin{bmatrix} 4 \\ 6 \end{bmatrix} = \begin{bmatrix} \frac{4}{\sqrt{52}} \\ \frac{6}{\sqrt{52}} \end{bmatrix}$$

これが $Q$ の最初の直交規格直交ベクトルです。

ベクトルの正規化方法

ベクトルが与えられたとき：

$$v = \begin{bmatrix} v_1 \\ v_2 \\ \vdots \\ v_n \end{bmatrix}$$

そのノルムを計算します：

$$|v| = \sqrt{v_1^2 + v_2^2 + ... + v^2_n}$$

次に正規化します：

$$\hat{v} = \frac{1}{|v|}v$$

例：

$$v = \begin{bmatrix} 3 \\ 4 \end{bmatrix},\ \ |v| = \sqrt{3^2 + 4^2} = 5$$

したがって、正規化ベクトルは：

$$\hat{v} = \frac{1}{5}\begin{bmatrix} 3 \\ 4 \end{bmatrix} = \begin{bmatrix} 0.6 \\ 0.8 \end{bmatrix}$$

ベクトルの正規化と直交化の方法が分かれば、グラム・シュミットの方法を用いて $Q$ 行列を作成し、QR分解で $R$ を計算できます。

グラム・シュミット法による $q_2$ の計算

$q_2$ を計算するために、まず $A$ の第2列から始めます：

$$a_2 = \begin{bmatrix} 3 \\ 3 \end{bmatrix}$$

次に、$a_2$ を $q_1$ に射影します：

$$r_{12} = q_1^Ta_2 = \frac{1}{\sqrt{52}}(4 \cdot 3 + 6 \cdot 3) = \frac{1}{\sqrt{52}} \cdot 30$$

$a_2$ から射影成分を取り除きます：

$$u_2 = a_2 - r_{12}q_1$$

その後、（上記と同様に）正規化します：

$$q_2 = \frac{u_2}{|u_2|}$$

これで $q_1$ と $q_2$ の両方が $Q$ の直交正規基底となります。 最終結果を組み立てます：

$$Q = \begin{bmatrix} q_1 & q_2 \end{bmatrix},\ \ R = \begin{bmatrix} r_{11} & r_{12} \\ 0 & r_{22} \end{bmatrix}$$

これらは次を満たします：

$$A = QR$$