nopu@wiki
nopu@wiki

行列の分解

連立方程式との関係

連立方程式をとく方法3つ
1. 掃き出し法 → LU分解
2. QR分解
3. SVD

三角化・対角化という観点

LU分解 : 三角行列による三角化
QR分解 : 直交行列による三角化
SVD    : 直交行列による対角化

LU分解の系譜

LU分解の系譜は掃き出し法でよく使われる。
また不完全Choleskyは共役勾配法の前処理として使われる。

LU分解

任意の横長行列A \in \mathbb{R}^{m \times n} \ (m \leq n)に対して存在する。
P_1 A P_2 = LU
ただしL \in \mathbb{R}^{m\times m}, U \in \mathbb{R}^{m \times n}

u_{ii} \neq 0のときは，P_1, P_2不要
A = LU

LDU分解

LU分解を同値変形して得られる。
(u_{ij}) = \left( \frac{u_{ij}}{u_ii}\right) = V, D = \mathrm{diag}\{ u_{11}, \cdots, u_{rr}, 1, \cdots, 1 \}

P_1 A P_2 = LDV
A = LDV
ただし, さきのLU分解のUに対して，U=DVが成り立つ。

(もう少し厳密に条件を与えて)LDU分解は一意である。

Cholesky分解

Aが正定値対称の場合は，LU分解から
A=L L^\mathrm{T}
の形を導くことができる。これをCholesky分解という。

修正Cholesky分解

正定値を仮定しなくても，対称行列Aに対して
A=L D L^\mathrm{T}
とできる。

QR分解

QR分解は，連立方程式の解法以外にも，
もとの行列Aのランクを求める方法として使われる。
\mathrm{rank}A = \mathrm{rank}R
QR分解によるランク計算の方が，反復法を用いるSVDよりも早い。

QR分解

任意の行列A \in \mathbb{R}^{m \times n}に対して存在する。
A = QR
ただしQ \in O(m), R \in \mathbb{R}^{m \times n}上三角行列

QR分解の計算法

1. Gram-Schmidtの直交化法
2. Householder変換を使う
3. Givens変換を使う

Gram-Schmidtは素朴で分かりやすいが，計算には使わない。
Householder法を使うのが普通。

特異値分解

Aが特異(つまり正則でない)の場合に，数値的に最も安定な解を与える。
とくに正規方程式を解く場合(つまり最小二乗法)は，最小ノルム解を与える。
このようにSVDはMoore-Penroseの一般化逆行列と深い関係を持つ。

特異値分解

一般の行列A \in \mathbb{R}^{m \times n}に対し，
A = U \Sigma V^\mathrm{T}
ただし U \in O(m), V \in O(n), \Sigma \in \mathbb{R}^{m \times n}
\Sigma = \mathrm{diag}\{\sigma_1, \cdots, \sigma_r, 0, \cdots, 0\}

次の一般化された固有値問題を解いていることになる。
\mathcal{U} \cong \mathbb{R}^n
\mathcal{V} \cong \mathbb{R}^m
A : \mathcal{U} \to \mathcal{V} \mbox{ linear}
として，
A \mathbf{u}_i = \sigma_i \mathbf{v}_i
ただし
\mathbf{u}_i \cdot \mathbf{u}_j = \delta_{ij}, \mathbf{v}_i \cdot \mathbf{v}_j = \delta_{ij}
「行列の分解」をウィキ内検索
最終更新：2011年11月10日 18:29
ツールボックス

下から選んでください:

新しいページを作成する
ヘルプ / FAQ もご覧ください。