逆行列を求めるアルゴリズムとコード化

質問

正則な正方行列Aの逆行列A^(-1)を求めるための数値計算のアルゴリズムを考えています。
AX＝Bの場合、Xを求めるプログラムはガウスの消去法等でコード化することはできます。理論的にはA^(-1)があるとそれを左からかけるとXが求まりますが、そうなるとXとA^(-1)は同じ立ち位置なのかなと思ったのですが。XがわかってもA^(-1)はすぐには求まらないのでしょうか。未知数の数が違う（A^(-1)は3x3で、Xは３）のでそういうことになるのかと思いますが。逆行列は小行列で展開して求めていくという方向もあります。コンピュータで逆行列を求める計算アルゴリズムについてよろしくお願いします。行列のサイズとしては100x100程度まではいきたいのですが。

回答No.2

f272

> この場合、連立1次方程式を列の数だけ解くということになります（力技）

ガウスの消去法だと前進消去の部分で
(プログラム片A)
for (k = 1; k < n; k++)
for (i = k + 1; i <= n; i++) {
q = a[i][k] / a[k][k];
for (j = k + 1; j <= n; j++) a[i][j] -= q * a[k][j];
b[i] -= q * b[k];
}
こんな感じに進めていくわけですが，右辺ベクトルbを使う部分を分離して，かつ後から右辺ベクトルbの計算ができるように必要な値を保存しておくことにすれば
(プログラム片B)
for (k = 1; k < n; k++)
for (i = k + 1; i <= n; i++) {
q = a[i][k] / a[k][k];
for (j = k + 1; j <= n; j++) a[i][j] -= q * a[k][j];
a[i][k] = q;
}
のようになります。その後
(プログラム片C)
/* 前進消去 */
for (i = 1; i <= n; i++)
for (j = 1; j < i; j++)
b[i] -= a[i][j] * b[j];
/* 後退代入 */
for (i = n; i >= 1; i--) {
for (j = i + 1; j <= n; j++) b[i] -= a[i][j] * b[j];
b[i] /= a[i][i];
}
のように右辺ベクトルbの計算をまとめてやれば解が求まることになります。このようにすることで，「連立1次方程式を列の数だけ解く」ことは同じですが，計算量がだいぶ減りますね。

逆行列A^(－1)が得られている場合にA^(－1)*bを計算するのに n^2 回の乗算が必要なわけですが，(プログラム片C)の部分の計算量(乗除算)はn^2 回です。つまり作業量的には(プログラム片B)の部分がおおむね逆行列A^(－1)を計算することに対応し，(プログラム片C)の部分がA^(－1)*bを計算することに対応すると考えて差し支えありません。実際には(プログラム片B)の部分というのはLU分解という作業です。

> 逆行列を求める理由が解を得るためだとすると

明示的に逆行列を求めるわけではありませんが，LU分解することが解を得るという目的のためには実質的に同等と言えます。(明示的に逆行列を求めるためにはLU分解後にさらにn^2回の乗除算が必要ですが...)
解を求めるためにLU分解するのは1回だけです。右辺ベクトルが異なっても同じLU分解後の値を使うことができます。

お礼

懇篤な回答ありがとうございます。
解を得るために逆行列を事前に得たはずなのに、解を得たあと、改めて逆行列をあれこれ調べることへの疑問が質問の発端でしたが、求解の途中に黒子のように出てきてはいる、しかし解が求まった時点で消えてしまうという風に思いました。そこで求解の途中でこの方法で表に出てきてもらった、と理解しました。初等線形代数の本にもこのような説明が見られましたが、プログラム化というところで迷っていました。

回答No.1

f272

> AX＝Bの場合、Xを求めるプログラムはガウスの消去法等でコード化することはできます。

というのなら，全く同じ方法でA^(-1)も計算できます。
Xを求める計算に必要なのはAとBの各要素ですよね。A^(-1)を求めるときにはBの代わりにE(単位行列)を使います。
BとEでは列数が異なりますが，その部分を修正するのは容易でしょう。

お礼

回答ありがとうございます。ご指示頂いた方法をストレートにやると、AX=Bの右辺のベクトルBに単位行列を構成する列ベクトルを１つづつ（例えばj列）取り出してXを求めると、それが逆行列のj行となっているというわけですね。この場合、連立1次方程式を列の数だけ解くということになります（力技）。どうしてもそういうことになってしまう（一見そうでないようなスマートにみえる解法があったとしてもよくよくみると結局はそれに帰着する）のでしょうか。
元の質問に戻ってしまいますが、逆行列を求める理由が解を得るためだとすると、すでに解がある（ゴールインしている）、という状態から出発すると逆行列（ゴールする途上にあるという位置づけ）を求めるために何度も解かなければならないというところが不思議なのです。逆行列の方が解よりも豊富な情報を含んでいるので解がわかったとしても逆行列はすぐには手に入らないということになるのでしょうか。