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}3x+6y+9z&=6\\ 2x+2y+3z&=1\\ 2x+2y+z&=-1 \end{aligned} \right.$$

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

解くべき，方程式

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

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

$$\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
著者: 山本昌志