逆行列の計算量 - データサイエンス関連+αのメモ

計算量¶

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

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

行列式の計算量

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

|A| = \sum_{\sigma \in S_n} \operatorname{sgn}(\sigma) a_{1 \sigma(1)} a_{2 \sigma(2)} \cdots a_{n \sigma(n)}

という行列式の定義から、置換の集合 $S_n$ の要素数が $n!$ 個あり、各項で $n$ 回 $a_{n \sigma(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=LU$ に分解し、 $Ly=b$ 、 $Ux=y$ を順に解く（直接解法）

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

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

よって $O(n^3)$

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

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

連立一次方程式

Ax = b

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

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

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

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

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

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