4 ガウス・ジョルダン法

逆行列が不要であれば、ガウス・ジョルダン法よりも、後で述べるLU分解の法が計算速度 は速い。しかし、教育的効果を考えると、両方の方法を知っておくのは良いことである。

4.1 基本的な考え方

ガウス・ジョルダン(Gauss-Jordan)法というのは、連立方程式 (4)を次にように変形させて、解く方法である。

$$\begin{aligned}\begin{bmatrix}1 & 0 & 0 & \cdots & 0 0 & 1 &... ... b_3^\prime \vdots b_N^\prime \end{bmatrix} \end{aligned}$$

この式から明らかに、求める解 $x_{i}=b_{i}^\prime$ となる。これをどうやって求めるか?。 コンピューターで実際に計算する前に、人力でガウス・ジョルダン法で計算してみる。例 として、

$$\left\{ \begin{aligned}1x+2y+3&=2 2x+2y+3z&=1 2x+2y+1z&=-1 \end{aligned} \right.$$

をガウス・ジョルダン法で解を求める。

解くべき、方程式

$$\begin{bmatrix}1 & 2 & 3 2 & 2 & 3 2 & 2 & 1 \end{bmatrix} ... ...rix}x_1 x_2 x_3 \end{bmatrix} = \begin{bmatrix}2 1 -1 \end{bmatrix}$$

2行$-2\times$ 1行

$$\begin{bmatrix}1 & 2 & 3 0 & -2 & -3 2 & 2 & 1 \end{bmatrix... ...ix}x_1 x_2 x_3 \end{bmatrix} = \begin{bmatrix}2 -3 -1 \end{bmatrix}$$

3行$-2\times$ 1行

$$\begin{bmatrix}1 & 2 & 3 0 & -2 & -3 0 & -2 & -5 \end{bmatr... ...ix}x_1 x_2 x_3 \end{bmatrix} = \begin{bmatrix}2 -3 -5 \end{bmatrix}$$

$-\frac{1}{2}\times$ 2行

$$\begin{bmatrix}1 & 2 & 3 0 & 1 & \frac{3}{2} 0 & -2 & -5 \e... ... x_2 x_3 \end{bmatrix} = \begin{bmatrix}2 \frac{3}{2} -5 \end{bmatrix}$$

1行$-2\times$ 2行

$$\begin{bmatrix}1 & 0 & 0 0 & 1 & \frac{3}{2} 0 & -2 & -5 \e... ...x_2 x_3 \end{bmatrix} = \begin{bmatrix}-1 \frac{3}{2} -5 \end{bmatrix}$$

3行$+2\times$ 2行

$$\begin{bmatrix}1 & 0 & 0 0 & 1 & \frac{3}{2} 0 & 0 & -2 \en... ...x_2 x_3 \end{bmatrix} = \begin{bmatrix}-1 \frac{3}{2} -2 \end{bmatrix}$$

$-\frac{1}{2}\times$ 3行

$$\begin{bmatrix}1 & 0 & 0 0 & 1 & \frac{3}{2} 0 & 0 & 1 \end... ... x_2 x_3 \end{bmatrix} = \begin{bmatrix}-1 \frac{3}{2} 1 \end{bmatrix}$$

$2行-\frac{3}{2}\times$ 3行

$$\begin{bmatrix}1 & 0 & 0 0 & 1 & 0 0 & 0 & 1 \end{bmatrix} ... ...rix}x_1 x_2 x_3 \end{bmatrix} = \begin{bmatrix}-1 0 1 \end{bmatrix}$$

これで、ガウス・ジョルダン法による対角化の作業は完了である。これか ら、 $(x_1,x_2,x_3)=(-1,0,1)$ と分かる。 これがガウス・ジョルダン法である。もっともらしい名前が付けられているが、大したこ となはい。諸君が中学生以来，連立方程式を解いてきた方法である．

これで、ガウス・ジョルダン法が理解できたと思う。もう少し数学的にその内容を説明す る²。そのために、次の線形行列方程式を考える。 ここでは、紙面の関係で係数行列が $4 \times 4$ について述べるが、一般的に$N$ への拡 張は容易である。

$$\begin{bmatrix}a_{11} & a_{12} & a_{13} & a_{14} a_{21} & a_{22... ...& 0 0 & 1 & 0 & 0 0 & 0 & 1 & 0 0 & 0 & 0 & 1 \end{pmatrix} \end{bmatrix}$$ (11)

ここで、$\sqcup$ は列拡大、つまりこの両側の括弧を取り去って行列をくっつ けて幅を広くすること意味する。この式から、容易に

$$\boldsymbol{A}\boldsymbol{x} =\boldsymbol{b}$$ (12)

$$\boldsymbol{A}\boldsymbol{Y} =\boldsymbol{E}$$ (13)

が分かる。もちろん、 $\boldsymbol{E}$ は単位行列である。要するに行列方程式 (11)を解くということは、この2つの連立方程式を解く ことに他ならない。 $\boldsymbol{x}$ はもとの方程式(1)の解となり、 $\boldsymbol{Y}$ は $\boldsymbol{A}$ の逆行列である。

式(11)について、以下のことが容易に分かる。

• $\boldsymbol{A}$ の任意の2行を入れ替えて、それに対応する $\boldsymbol{b}$ と $\boldsymbol{E}$ を入れ替えた場合、 $\boldsymbol{x}$ や $\boldsymbol{Y}$ の値と順序は変わらない。た だし、 $\boldsymbol{E}$ はもはや単位行列ではない。これは連立方程式の順序を入れ替 えて書いていることに相当している。
• $\boldsymbol{A}$ の任意の行を、その行と別の行との線形結合に置き換え、同 時に対応する $\boldsymbol{b}$ と $\boldsymbol{E}$ も同様に置き換える。この場合、 $\boldsymbol{x}$ と $\boldsymbol{Y}$ の値と順序は変わらない。当然、この場合も $\boldsymbol{E}$ はもはや単 位行列ではない。
• $\boldsymbol{A}$ の任意の2列を入れ替えて、それに対応する $\boldsymbol{x}$ と $\boldsymbol{Y}$ の行を入れ替えれば、 $\boldsymbol{b}$ と $\boldsymbol{E}$ の順序は入れ替える必要 は無い。この場合、解の行の順序が変わるので、最後に元に戻す操作が必要 になる。

この3つの操作を組み合わせて、係数行列 $\boldsymbol{A}$ を単位行列に変換するのがガウス・ジョ ルダン法である。 $\boldsymbol{A}$ が単位行列に変換されれば、右辺に $\boldsymbol{x}$ と $\boldsymbol{Y}$ が表れ る。したがって、解と逆行列が求められたことになる。もし、逆行列が不要であれば $\boldsymbol{x}$ だけ計算し、逆行列のみ必要であれば $\boldsymbol{Y}$ のみ計算する。

4.2 ピボット選択

先に示した、ガウス・ジョルダン法の3つの基本操作のうち、2番目しか使わな い方法を「ピボット選択なしのガウス・ジョルダン法」と言う。最初、人 力で連立方程式を解いた方法である。この方法の明らかにまずい点は、もし1に したい対角要素がゼロの場合、計算ができなくなってしまうところにある。この割る要 素をピボット(pivot)と言う。ゼロでないにしても、そのピボットが非常 に小さい値の場合、丸め誤差が大きくなり問題である³。このようなことから、普通は ピボット選択なしのガウス・ジョルダン法というものは考えられない。

この問題を避けるためにどうするかというと、ピボット選択という方法を使う。方法は簡 単で、先に示した3つの基本操作のうち、1番目と3番目を使って、対角に素性の良い要素 をもってくる。1番目の操作のみを用いて行を入れ替える方法を、部分ピボット選択 (partial pivoting)と言う。1番目の操作と3番目の操作を使って、行と列を入れ替え るのを完全ピボット選択(full pivoting)と言う。すでにある程度出来上がっている 単位行列を壊したくないので、ピボットの選択は操作している行の下の行から選ばなく てはならない。

部分ピボット選択の方が明らかに簡単である。解の行列を入れ替える必要が無い からである。その場合、行の入れ替えしかしないので、ピボットはその列から選 ばなくてはならない。完全ピボット選択の方が選べる要素が多いが、 最終的な解の精度はあまり変わらないようである。したがって、ここではプログ ラムの簡単な部分ピボット選択で計算する事にする。

次に考えなくてはならないのは、ピボットを選択する基準である。簡単に言えば、 大きな要素選択すれば大体よい。しかし、ある行を100万倍して、それに 対応する右辺の行も100万倍することもできるので、ただ大きいというだけ では問題がありそうである。どうするかと言うと、各方程式の最大係数を1に規 格化して、最大のものをピボットに選ぶことが行われている。この方法を陰 的ピボット選択(implicit pivoting)と呼ぶ。

これで、ピボットの問題も片付いたので、フローチャートを書いてみる。

4.3 フローチャート

ガウス・ジョルダン法のフローチャートを図1に示す。

図 1: ガウス・ジョルダン法のフローチャート

ホームページ: Yamamoto's laboratory
著者: 山本昌志