2.2.2 色々な解き方の比較

逆行列なんか、誰も使わない。。。

1. 普通の掃き出し法 (Jordan の消去法)。
   
   $$A b \longto \cdots \longto \begin{array}{cccc} 1 & & & \ast \\ & \ddots & & \vdots \\ & & 1 & \ast \end{array}$$
   
   
   これは乗除算約 $N^3/2$ 回が必要。
2. Cramer の公式。$N+1$ 個の行列式が現れる。普通に計算すると $O(N^4)$ 回の乗除算。丸め誤差の観点からも損。
3. $A^{-1}$ を掃き出し法で求めてから、$A^{-1} b$ を計算する。 $N^3$ 回の乗除算が必要になり、損。他の理由もあってダメ。
4. Gauss の消去法。$N^3/3$ 回の乗除算で OK.

Gauss の消去法には、上に述べた以外にも、大きな長所がある。それは、係 数行列 $A$ が疎そである場合は、その性質を保ったまま計算しや すく、従って問題がさらに効率的に解ける、ということである。例えば、$A$ が三重対角行列である場合、逆行列を計算するのはやはり $O(N^3)$ であるが、 Gauss の消去法を用いると、$O(N)$ で済む。

もしかすると、逆行列のファンである人（特に学生）は多いかもしれない。 大昔は、学生でなくても、連立一次方程式を解くには、まず逆行列を求めよう とする人が多かった -- 現在、こんなことをしたら、研究者・技術者として、 化石扱いにされるのがオチである。

Gauss の消去法による、連立一次方程式の解法は、実際には LU 分解の形で 扱われることが多い。まず、前進消去の段階では、$A x=b$ を表す

$$[A \vert b]$$

から始めて、行に関する基本変形を繰り返すことによって、対角線よりも下の 部分に $0$ が並ぶ形を導く。これはある方程式を表現しているが、それを $U x=c$ と書くと、$U$ は上三角行列である。Gauss の消去法の後半部分である、 後退代入の原理は、「上三角行列を係数行列にもつ連立一次方程式は、簡単な 代入操作で解ける」ということである。

実は、基本変形は、左から基本行列と呼ばれる行列を掛けることに他ならな いが、今の場合は、ある下三角行列 $L$ が存在して、

$$U = L A, \quad c = L b$$

となる。

$L$, $U$ を記憶しておくと、別の $b'$ が与えられた時に、$A x=b'$ の解 を

$$U^{-1} L b'$$

として計算できる。