プログラムな日常>ウェブプログラム作品集>
逆行列の解法
(How to get matrices' inverse?)
matrix_U
matrix_V
matrix_L
matrix_B
Gauss-Jordan
Gauss
LU-Decomp.
matrix_X
matrix_B_again
使い方:
さて、"sample1" に即してご説明しましたが、同じことを "sample2" についてしようと思うと、困難に直面します。 これを乗り越えるため、変換機能は他にも用意しています。列挙すると、
  1. "matrix-U" の要素を真下、あるいは真上にドラッグして、目標の要素をゼロにする(すでに説明したものです)。
  2. "matrix-U" の要素をダブルクリックし、行を定数倍した結果、クリックした要素を1にする(すでに説明したものです)。
  3. "matrix-U" の要素を右クリックし、そのまま真下、あるいは真上にドラッグして、目標の要素の絶対値を増やす。
  4. "matrix-U" の右端の影の何れかをクリックし、上か下にドラッグして、行を相互に入れ替える。
  5. "matrix-U" の右端の影の何れかをダブルクリックし、ダイアログボックスを使用して、行を定数倍する。
  6. "matrix-V" の要素を真下、あるいは真上にドラッグして、目標の要素をゼロにする。
  7. "matrix-L" の要素を真左、あるいは真右にドラッグして、目標の要素をゼロにする。
  8.  
上に挙げた中で、項目3は、Gauss-Jordan 法で sample2 のような例を解くには効果的である(ゼロ値の対角要素を非ゼロにできる)が、Gauss、LU分解の両法には、 今回用意した残りの変換機能を駆使しても無力である。 これは両法で前半を終了する(ボタンが黄色くなる)には、matrix-U の下側がクリアされると共に、matrix-V や matrix-L の上側も全てゼロであることが必要だからである。 実は、Gauss および LU分解の方法でも、さらに工夫を加えれば sample2 を解くことはできるようなのであるが、泥沼は深く、解決は別の機会に完結する予定である。

解説:

本ページの狙いは行列の直接的逆解法とされる三法の比較である。

内、ガウス法とLU分解法とは、どちらも上下の三角行列に分解する点では共通するが、前者で利用した下三角行列Vは、逆計算を途中まで行ったものであるのに対し、 LU分解法は、文字通り、Uの初期状態を、LとUの積に分解している点で違う。しかし、ガウス法のVとLU分解法のLとは、実は逆行列の関係にあり、 途中までの分解をどういう形式で記憶しているかだけの違いだったとも解釈できる。また、このページに乗せたソフトでは、Uの変形とBへの適用は 前後して行ったが、通常のガウス法では並行して、つまりUの変換一行とBへの適用一行とを続けて行う。 つまり、UとBとに常に同一の行列を左側から掛けて、等号関係(B = U・X)を保つように実装するわけである。 同じことはガウス・ジョルダン法についても言える。

下でも上でも良いが、三角行列は、同次元である任意のベクトルに対して、順変換でも逆変換でも、速やかに適用できる。 具体的には、LU分解の適用で、ソフトのボタンを見ると、BにLの逆行列を掛け、その結果にさらにUの逆行列を掛けると解釈できるかも知れないが、 実はそれぞれの逆行列を作ってから行っているのではなく、逆行列は作らなくとも、逆行列を掛けたと同じ効果の計算をしているのである。 同じことは、ガウス法適用の後半についても言える。ベクトルもしくはマトリクスに対する三角行列適用のルーチンは  「次」 (クリックすると開閉する)のように簡素なものである。

そういうわけで、ガウス法とLU分解法とはほぼ一つのものとして捉えられる。 単一ベクトルの逆計算を行う場合、これらの解法に対して、ガウス・ジョルダン法は、ほぼ 1.5倍のステップ数がかかってしまうと言われる。 この倍率は、一般の正方行列の逆計算になると、「高々12.5%増し」と修正され、さらに、単位行列の逆計算、即ち、逆行列を求める計算だと、 3つの方法の速度上の差は、なくなってしまうのである。この事情を表にまとめると次のようになる(n は正方行列の一辺; ガウス・ジョルダン法では、上側の消去を左からすることで、もとよりゼロである V の右側の計算を省略できるぶんが、有利になる)。

Bの種類(=Xの種類) 必要ステップ数/(n^3)
ガウス・ジョルダン ガウス(前進消去と後退消去) LU分解
全体内訳 全体内訳 全体内訳
UB (V) U(前進)V適用後退(U適用) 分解L適用U適用
単一ベクトル0.50.50 0.3330.333000.3330.33300
一般正方行列1.50.51 1.3330.3330.50.51.3330.3330.50.5
単位行列(→ 逆行列)10.50.5 10.3330.1660.510.3330.1660.5


ガウス法やLU分解法を、ガウス・ジョルダン法に対する高速解法と捉えるのであれば、それは単一もしくは少ない数のベクトルの計算に 活用するのでなければ価値がない。それも、もとの行列の分解と同時、もしくは保存した上下の三角行列を通じて計算するので なければならない。まずは逆行列を求めておいて、課題のベクトルが出てきたときに掛算するという考えであれば、 少なくともガウス・ジョルダン法に対する優位性は消失するのである。 しかもsample2のようなケースの「泥沼」に対する解決はこれからである。

「逆行列を求めるには」という文字通りの問に対しては、「ガウス・ジョルダン法」でほぼ間違いない。