Gauss の消去法

よく知られているように, $n\times n$ 行列は行列式が 0 でないとき 逆行列を持ちます. 逆行列は Cramer の公式によって与える事ができます. 線形代数学の授業でも学んだと思いますが, Cramer の公式は数学の理論を 作るには重要ですが(数学だけではなく電気工学などでも, 理論上は重要), 与えられた逆行列の計算には向きません. 多量の行列式の計算が大変だからです.

その事情はプログラミングでも同じで, 逆行列の計算をプログラム する際にも, Cramer の公式は使いません. プログラム されるのは Gauss の消去法(掃き出し法)です. 即ち, 中学で学ぶ連立 方程式の解法です.

掃き出し法は, 次のアルゴリズムです. $A = (a_{ij})$ を $n$ 次正方行列とします. $E_n$ を $n$ 次の単位 行列とする時, $A$ と $E_n$ を横に並べてできる $n \times 2n$ 行列 $(A~ E_n)$ を考えます. これに対して行の 基本変形, 即ち

1. ある行を(0 でない)定数倍する.
2. ふたつの行を入れ換える.
3. ある行に, 別の行の定数倍を加える.

を実行して, 左半分の $A$ の部分を単位行列に変形し, $(E_n~ B)$ の形にできたとします. このとき, $B$ は $A$ の逆行列です. もし, $A$ を単位行列に変形できなければ, $A$ は逆行列を持ちません.

より具体的なアルゴリズムは, 次の形になります.

1. $a_{11} \neq 0$ かどうかを調べる. もし $a_{11} \neq 0$ なら3に進む.
2. $a_{11} = 0$ なら列を下に見て, すなわち $a_{21}, a_{31},\cdots$ で 0 でないのものを捜し出して, その行と1行を入れ換える.
3. 第 1 行を $a_{11}$ でわる.
4. 第 $i$ 行 $i=2,\ldots,n$ から 3 でできた 第1行の $a_{i1}$ 倍を引く.
   この操作で $a_{21}= \cdots = a_{n1} = 0$ となる.
5. $a_{22} \neq 0$ かどうかを調べる. もし $a_{22} \neq 0$ なら7に進む.
6. $a_{22} = 0$ なら列を下に見て, すなわち $a_{32}, a_{42},\cdots$ で 0 でないのものを捜し出して, その行と2行を入れ換える.
7. 第 2 行を $a_{22}$ でわる.
8. 第 $i$ 行 $i=1,\ldots,n, (i\neq 2)$ から 7 でできた 第2行の $a_{i2}$ 倍を引く.
   この操作で $a_{i2} = 0~ (i\neq 2)$ となる.
9. 以下同様の操作を第 $n$ 列まで繰り返す.

すなわち, 各列毎に対角成分に 0 でない値を選んで来て, それを利用して, その列の他の成分を消去して行くわけです. この 0 でない値の事を, pivot(軸)といいます. pivot を選べなくなった時点 でこのアルゴリズムは止まってしまい, その場合には $A$ が逆行列を持ちません.