Subsections

4 ガウス・ジョルダン法

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

4.1 基本的な考え方

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

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

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

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

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

解くべき、方程式

$\displaystyle \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行

$\displaystyle \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行

$\displaystyle \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行

$\displaystyle \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行

$\displaystyle \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行

$\displaystyle \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行

$\displaystyle \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行

$\displaystyle \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)$ と分かる。 これがガウス・ジョルダン法である。もっともらしい名前が付けられているが、大したこ となはい。諸君が中学生以来,連立方程式を解いてきた方法である.

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

$\displaystyle \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$ は列拡大、つまりこの両側の括弧を取り去って行列をくっつ けて幅を広くすること意味する。この式から、容易に

$\displaystyle \boldsymbol{A}\boldsymbol{x}$ $\displaystyle =\boldsymbol{b}$ (12)
$\displaystyle \boldsymbol{A}\boldsymbol{Y}$ $\displaystyle =\boldsymbol{E}$ (13)

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

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

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

4.2 ピボット選択

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

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

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

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

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

4.3 フローチャート

ガウス・ジョルダン法のフローチャートを図1に示す。
図 1: ガウス・ジョルダン法のフローチャート
\includegraphics[keepaspectratio, scale=1.0]{figure/flow_gj.eps}

ホームページ: Yamamoto's laboratory
著者: 山本昌志
Yamamoto Masashi
2005-11-18


no counter