使い方:
- "lastset", "sample1", "sample2" の何れかのボタンを押すとテキストボックスが開き、行列を入力できます。
テキストボックス内の行の区切りは Enter で良く、行内の各要素は、コンマか空白の1個以上で区切ります。
編集の後、"set" によって、"matrix_U" の内容として設定できます。
- 今から求めるのは、"matrix_U" (に設定した内容)を行列の左から掛算することによる変換の逆変換です。逆行列自体も求められます。
- "matrix_U" に変換を加えて、その対角要素以下のものをゼロにします。これは左から順に行います。対角要素上でマウスを下げ、
その真下の各要素までドラッグして離すことで、各要素をゼロにできます。これは先の行の定数倍を別の行に加える操作です。
- まずは、"sample1" のそのままの内容でやってみて下さい。対角要素下の全ての要素がゼロになると、2つのボタンの色が変わります。
- 逆変換しようと狙うのは "matrix-B" の内容です。"from table" を押してから書き換えることもできます。
デフォルトで1列のみですが、複数列の行列にもできます。
Gauss の逆解法に対応する "→ U-1 * V * B" と、LU分解法に対応する "→ U-1 * L-1 * B" とが黄色になっている状態で、
これらのどちらかのボタンを押すと、"matrix-X" に逆変換の結果が設定されます。
- "lastset * X" を押すことによって、"matrix-X" の内容を("matrix_U" に先に設定した内容で)順変換し、結果を "matrix_B_again" に入れます。
これが上の "matrix_B" と同じになっていれば、先の逆変換は成功していたことになります。
- ここからは、Gauss-Jordan 法に進みます。"matrix-U" は、対角要素の下側のみがゼロの状態でしたが、対角要素から真上にもドラッグし、対角要素のみを残します。
- 最後(でなくても良いのですが)に、対角要素のそれぞれをダブルクリックすると、その値が1になります。これは個々の行に定数倍を掛ける操作であり、
同じ定数を "matrix_V" の同じ行にも掛け、"matrix_L" の同じ順番の列は割ります。
ここまで進むと、"Gauss-Jordan" 法に対応する "→ V * B" のボタンが黄色くなります。
この時、"matrix_V" の内容は、"matrix-U" に先に設定したものの逆行列になっています。
- 黄色くなっているボタンを押すと、"matrix_B" の内容が逆変換され、"matrix_X" に入ります。これは、"matrix_V" を掛算しているのです。
"matrix-X" の検証は先と同様に可能であり、以上のようにして、Gauss 法、LU分解法、Gauss-Jordan 法の3つがテストできます。
さて、"sample1" に即してご説明しましたが、同じことを "sample2" についてしようと思うと、困難に直面します。
これを乗り越えるため、変換機能は他にも用意しています。列挙すると、
- "matrix-U" の要素を真下、あるいは真上にドラッグして、目標の要素をゼロにする(すでに説明したものです)。
- "matrix-U" の要素をダブルクリックし、行を定数倍した結果、クリックした要素を1にする(すでに説明したものです)。
- "matrix-U" の要素を右クリックし、そのまま真下、あるいは真上にドラッグして、目標の要素の絶対値を増やす。
- "matrix-U" の右端の影の何れかをクリックし、上か下にドラッグして、行を相互に入れ替える。
- "matrix-U" の右端の影の何れかをダブルクリックし、ダイアログボックスを使用して、行を定数倍する。
- "matrix-V" の要素を真下、あるいは真上にドラッグして、目標の要素をゼロにする。
- "matrix-L" の要素を真左、あるいは真右にドラッグして、目標の要素をゼロにする。
上に挙げた中で、項目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分解 |
全体 | 内訳 |
全体 | 内訳 |
全体 | 内訳 |
U | B (V) |
U(前進) | V適用 | 後退(U適用) |
分解 | L適用 | U適用 |
単一ベクトル | 0.5 | 0.5 | 0 |
0.333 | 0.333 | 0 | 0 | 0.333 | 0.333 | 0 | 0 |
一般正方行列 | 1.5 | 0.5 | 1 |
1.333 | 0.333 | 0.5 | 0.5 | 1.333 | 0.333 | 0.5 | 0.5 |
単位行列(→ 逆行列) | 1 | 0.5 | 0.5 |
1 | 0.333 | 0.166 | 0.5 | 1 | 0.333 | 0.166 | 0.5 |
ガウス法やLU分解法を、ガウス・ジョルダン法に対する高速解法と捉えるのであれば、それは単一もしくは少ない数のベクトルの計算に
活用するのでなければ価値がない。それも、もとの行列の分解と同時、もしくは保存した上下の三角行列を通じて計算するので
なければならない。まずは逆行列を求めておいて、課題のベクトルが出てきたときに掛算するという考えであれば、
少なくともガウス・ジョルダン法に対する優位性は消失するのである。
しかもsample2のようなケースの「泥沼」に対する解決はこれからである。
「逆行列を求めるには」という文字通りの問に対しては、「ガウス・ジョルダン法」でほぼ間違いない。