逆行列の計算量

逆行列の計算量#

逆行列の計算量まとめ

A^{- 1} = \frac{1}{| A |} \tilde{A}

から計算する場合、おそらく $O (n^{5})$ かかる（行列式の計算に $O (n^{3})$ + 余因子行列に $O (n^{5})$ ）

行列式の計算量

(1) 愚直に計算した場合 → $O (n \times n!)$

| A | = \sum_{σ \in S_{n}} sgn (σ) a_{1 σ (1)} a_{2 σ (2)} \dots a_{n σ (n)}

という行列式の定義から、置換の集合 $S_{n}$ の要素数が $n!$ 個あり、各項で $n$ 回 $a_{n σ (n)}$ を掛けるので $O (n \times n!)$

(2) 効率化した場合 → $O (n^{3})$

「行列Aのi行から、j行の定数倍を引いても、行列式の値は変わらない。」という性質を使って上三角行列に変形してから行列式を計算する。三角行列への変換は $O (n^{3})$ 、上三角行列の行列式は対角成分の積なので $O (n)$ なので、全体で $O (n^{3})$ になる

余因子行列の計算量

$(i, j)$ 余因子は「『 $i$ 行目と $j$ 列目を除いた行列』の行列式に $(- 1)^{i + j}$ をかけたもの」なので、 $n - 1$ 次行列の行列式を求める計算になり、 $O ((n - 1)^{3})$

余因子行列は「 $(i, j)$ 余因子を $i, j$ 成分に持つ行列を転置したもの」なので、 $(i, j)$ 余因子を $n \times n$ 個計算する必要がある→ $O ((n - 1)^{3} \times n^{2})$ か？

$O (n^{3})$ かかるとされる

教科書的な方法でありながら、行列分解による方法と計算量が大差ない（=結構効率的）

$A = L U$ に分解し、 $L y = b$ 、 $U x = y$ を順に解く（直接解法）

LU分解におよそ $n^{3} / 3$ 回の計算が発生し、 $A^{- 1}$ の計算におよそ $2 n^{3} / 3$ 回の計算が発生する（伊理・藤野 1985）

\frac{n^{3}}{3} + \frac{2 n^{3}}{3} = \frac{3}{3} n^{3} = n^{3}

よって $O (n^{3})$

正規方程式の $X^{T} X$ のような行列のみ使える。統計や機械学習では身近

LU分解の代わりにコレスキー分解 $A = L L^{T}$ を用いることで計算量をLUの約半分にできる（分解について $O (n^{3} / 6)$ ）

連立一次方程式

A x = b

の $x$ を求めることは、二次形式

f (x) = \frac{1}{2} x^{T} A x - b^{T} x

の最小化と一致するので、 $f (x)$ の最小値を探索する方法で解を求める方法を 共役勾配（conjugate gradient: CG）法 という

$A$ が対称正定値行列の場合、共役勾配法が利用可能（行列計算における高速アルゴリズム）

ただし、共役勾配法などの反復解法全般の特徴として以下がある

伊理正夫 & 藤野和建 (1985) 『数値計算の常識』