逆行列の計算量

逆行列の計算量#

計算量#

逆行列の計算量まとめ

行列式を使う場合：おそらく\(O(n^5)\)
Gauss-Jordanの掃き出し法：\(O(n^3)\)
LU分解してから逆行列を求める：\(O(n^3)\)

行列式を使う場合#

\[ 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)\)になる

（参考：Tech Tips: 行列式の計算）

余因子行列の計算量

\((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)\)かかるとされる

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

LU分解してから解く#

\(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）法 という

連立1次方程式：共役勾配法 - PukiWiki for PBCG Lab

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

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

解がうまく収束する場合、計算量が直接解法より大幅に削減できる
収束しない場合もある
事前に収束回数はわからない

参考文献#

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