逆行列の計算量#
計算量#
逆行列の計算量 まとめ
行列式を使う場合：おそらく\(O(n^5)\)
Gauss-Jordanの掃き出し法：\(O(n^3)\)
LU分解してから逆行列を求める：\(O(n^3)\)
行列式を使う場合#
から計算する場合、おそらく\(O(n^5)\)かかる（行列式の計算に\(O(n^3)\) + 余因子行列に\(O(n^5)\)）
行列式の計算量
(1) 愚直に計算した場合 → \(O(n\times 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）
よって\(O(n^3)\)
行列が対称正定値行列のときのみ使える方法#
正規方程式の\(X^T X\)のような行列のみ使える。統計や機械学習では身近
コレスキー分解#
LU分解の代わりにコレスキー分解\(A=LL^T\)を用いることで計算量をLUの約半分にできる（分解について\(O(n^3/6)\)）
共役勾配法#
連立一次方程式
の\(x\)を求めることは、二次形式
の最小化と一致するので、\(f(x)\)の最小値を探索する方法で解を求める方法を 共役勾配（conjugate gradient: CG）法 という
連立1次方程式：共役勾配法 - PukiWiki for PBCG Lab
\(A\)が対称正定値行列の場合、共役勾配法が利用可能（行列計算における高速アルゴリズム）
ただし、共役勾配法などの反復解法全般の特徴として以下がある
解がうまく収束する場合、計算量が直接解法より大幅に削減できる
収束しない場合もある
事前に収束回数はわからない
参考文献#
伊理正夫 & 藤野和建 (1985) 『数値計算の常識』