ガウスの消去法

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

ガウスの消去法(ガウスのしょうきょほう、: Gaussian elimination)あるいは掃き出し法(はきだしほう、: row reduction)とは、連立一次方程式を解くための多項式時間アルゴリズムであり、通常は問題となる連立一次方程式の係数からなる拡大係数行列に対して行われる一連の変形操作を意味する。 同様のアルゴリズムは歴史的には前漢九章算術で初めて記述された[1]。連立一次方程式の解法以外にも行列階数を求めること、行列式の計算あるいは、正則行列の逆行列の計算などに使われる[2][3]。このアルゴリズムは、大きな方程式系を系統的な方法で小さな系へ分解する方法を与えるものと理解することができ[4]、基本的には、前進消去と後退代入という2つのステップから成る。

行列に対して掃き出し法を行う為には、行に関する基本変形を行列に可能な限り繰り返し行って行列の左下部分の成分を全て 0 にする。行に関する基本変形には、1) 二つの行を入れ替えるもの、2) ある行を0でない定数倍するもの、3) ある行に、他のある行の定数倍を加えるもの、の三種類の操作あるいは変形があり、これらの変形を行うことで、常に行列は上三角型に変形することができ、実際には、ゼロでない成分を持つ行が、ゼロしか成分に持たない行よりも上に位置し、主成分(行の最も左にある 0 でない成分)が、その行の上にある行の主成分よりも、真に右側に位置する行階段形に変形される。 さらにすべての主成分が 1 になり、主成分を含む列にある主成分以外の成分が 0 であるとき、この行列は行簡約階段形であると呼ばれる。この最終形は一意的であり、別の言葉で言えば、いかなる行基本変形が施されたかには依存しない。例えば、次の様な行基本変形の繰り返し(各ステップで複数の基本変形を行っている)で、三番目と四番目は共に行階段形であるが、最後の四番目が一意に定まる行簡約階段形である。

\left[\begin{array}{rrr|r}
1 & 3 & 1 & 9 \\
1 & 1 & -1 & 1 \\
3 & 11 & 5 & 35
\end{array}\right]\to
\left[\begin{array}{rrr|r}
1 & 3 & 1 & 9 \\
0 & -2 & -2 & -8 \\
0 & 2 & 2 & 8
\end{array}\right]\to
\left[\begin{array}{rrr|r}
1 & 3 & 1 & 9 \\
0 & -2 & -2 & -8 \\
0 & 0 & 0 & 0
\end{array}\right]\to
\left[\begin{array}{rrr|r}
1 & 0 & -2 & -3 \\
0 & 1 & 1 & 4 \\
0 & 0 & 0 & 0
\end{array}\right]

行基本変形を用いて行列を行階段形に変形することをガウス・ジョルダンの消去法(ガウス・ジョルダンのしょうきょほう、: Gauss–Jordan elimination)と呼ぶことがある。教科書によっては、ガウスの消去法という用語を上三角形または(簡約とは限らない)行階段形へ変換する手法を指すこともある。実のところ、連立一次方程式の解を求める際に行基本変形を完全に簡約化する前に止めてしまう方が、計算上の理由から良いとされる場合もある。

基本的な考え方[編集]

nm連立一次方程式の解が x_1 = a_1+b_{11}c_1+\cdots+b_{1s}c_s, x_2=a_2+b_{21}c_1+\cdots+b_{2s}c_s, \cdots, x_r=a_r+b_{r1}c_1+\cdots+b_{rs}c_s, x_{r+1}=c_1,\ldots, x_n=c_sn=r+s かつ c_1,..., c_s は任意の定数)だとすると、これは次の連立一次方程式を略記したものである。ただし、下段に並んでいる、全ての係数が 0 でかつ右辺も 0 である式は m-r 本ある。

\begin{align}
&1x_1 + 0x_2 + \cdots + 0x_r - b_{11}x_{r+1} -\cdots- b_{1s}x_{n} = a_1\\
&0x_1 + 1x_2 + \cdots + 0x_r - b_{21}x_{r+1} -\cdots- b_{2s}x_{n} = a_2\\
&\qquad\vdots \\
&0x_1 + 0x_2 + \cdots + 1x_r - b_{r1}x_{r+1} -\cdots- b_{rs}x_{n}= a_r \\
&0x_1 + 0x_2 + \cdots + 0x_r + 0x_{r+1} +\cdots+ 0x_{n} = 0 \\
&\qquad\vdots \\
&0x_1 + 0x_2 + \cdots + 0x_r + 0x_{r+1} +\cdots+ 0x_{n} = 0
\end{align}

与えられた方程式からこの形式を導くためには、対角成分に注目して左上から式を加減していけばよいが、未知数がk 個定まった時点で残りk + 1 個の未知数を含む式が解けるため、x_1 から x_r までの全ての変数を孤立させる必要はない。つまり、

\begin{align}
&1x_1 + m_{12}x_2 +\cdots+ m_{1r}x_r - b'_{11}x_{r+1} -\cdots- b'_{1s}x_{n} = a'_1 \\
&0x_1 + 1x_2 + \cdots + m_{2r}x_r - b'_{21}x_{r+1} -\cdots- b'_{2s}x_{n} = a'_2 \\
&\qquad\vdots \\
&0x_1 + 0x_2 + \cdots + 1x_r - b'_{r1}x_{r+1} -\cdots- b'_{rs}x_{n} = a'_r \\
&0x_1 + 0x_2 + \cdots + 0x_r + 0x_{r+1} +\cdots+ 0x_{n} = 0 \\
&\qquad\vdots \\
&0x_1 + 0x_2 + \cdots + 0x_r + 0x_{r+1} +\cdots+ 0x_{n} = 0
\end{align}

と三角形になった時点で、r+1 番目以後の変数を任意定数 c_1,..., c_s を用いて x_{r+1}=c_1, x_{r+2}=c_2,..., x_{n}=c_s と置き、右辺に移項して下から順に値を代入していくことで全ての解を確定できる。

[編集]

次のような連立一次方程式の解を求める。

\begin{align}
&2x_1 &+&  4x_2 &+& 2x_3 &+& 2x_4 &&= 8 \\
&4x_1 &+& 10x_2 &+& 3x_3 &+& 3x_4 &&= 17 \\
&2x_1 &+& 6x_2 &+& x_3 &+& x_4 &&= 9 \\
&3x_1 &+&  7x_2 &+& x_3 &+& 4x_4 &&= 11
\end{align}
  1. まず前進消去をする。
    1. 1 番目の方程式を 1/2 倍する。
      \begin{align}
& x_1 &+&  2x_2 &+&  x_3 &+& x_4 &&= 4 \\
&4x_1 &+& 10x_2 &+& 3x_3 &+& 3x_4 &&= 17 \\
&2x_1 &+& 6x_2 &+& x_3 &+& x_4 &&= 9 \\
&3x_1 &+&  7x_2 &+& x_3 &+& 4x_4 &&= 11
\end{align}
    2. 2 番目の方程式に 1 番目の方程式の -4 倍を足す。3 番目の方程式に 1 番目の方程式の -2 倍を足す。4 番目の方程式に 1 番目の方程式の -3 倍を足す。
      \begin{align}
&x_1 &+& 2x_2 &+&  x_3 &+& x_4 &&= 4 \\
&   &&  2x_2 &-&  x_3 &-& x_4 &&= 1 \\
&   &&  2x_2 &-&  x_3 &-& x_4 &&= 1 \\
&    &&   x_2 &-& 2x_3 &+& x_4 &&= -1
\end{align}
    3. 2 番目の方程式を 1/2 倍する。
      \begin{align}
&x_1 &+& 2x_2 &+&            x_3 &+& x_4 &&= 4 \\
&    &&   x_2 &-& \frac{1}{2}x_3 &-& \frac{1}{2}x_4 &&= \frac{1}{2} \\
&    &&  2x_2 &-&  x_3 &-& x_4 &&= 1 \\
&    &&   x_2 &-& 2x_3 &+& x_4 &&= -1
\end{align}
    4. 3 番目の方程式に 2 番目の方程式の -2 倍を足す。4 番目の方程式に 2 番目の方程式の -1 倍を足す。
      \begin{align}
&x_1 &+& 2x_2 &+&            x_3 &+& x_4 &&= 4 \\
&    &&   x_2 &-& \frac{1}{2}x_3 &-& \frac{1}{2}x_4 &&= \frac{1}{2} \\
&    &&   &&  && 0 &&= 0 \\
&    &&       &-& \frac{3}{2}x_3 &+& \frac{3}{2}x_4 &&= -\frac{3}{2}
\end{align}
    5. 3 番目の方程式と 4 番目の方程式を入れ替える。
      \begin{align}
&x_1 &+& 2x_2 &+&            x_3 &+& x_4 &&= 4 \\
&    &&   x_2 &-& \frac{1}{2}x_3 &-& \frac{1}{2}x_4 &&= \frac{1}{2} \\
&    &&       &-& \frac{3}{2}x_3 &+& \frac{3}{2}x_4 &&= -\frac{3}{2} \\
&    &&   &&  &&  0 &&= 0 
\end{align}
  2. 次に後退代入をする。
    1. 3 番目の方程式を -\frac{2}{3} 倍する
      \begin{align}
&x_1 &+& 2x_2 &+&            x_3 &+& x_4 &= 4 \\
&    &&   x_2 &-& \frac{1}{2}x_3 &-& \frac{1}{2}x_4 &= \frac{1}{2} \\
&    &&       &&             x_3 &-& x_4 &= 1 \\
&    &&   &&  && 0 &= 0 
\end{align}
    2. x_3 = 1 + x_4 を 2 番目の方程式に代入する。
      \begin{align}
&x_1 &+& 2x_2 &+& x_3  &+& x_4 &= 4 \\
&    &&   x_2 &&  &-& x_4  &= 1 \\
&    &&       &&  x_3 &-& x_4 &= 1 \\
&    &&   &&  &&  0 &= 0 
\end{align}
    3. x_3 = 1 + x_4x_2 = 1 + x_4 を 1 番目の方程式に代入する。
      \begin{align}
x_1 + 4x_4 &= 1 \\
x_2 - x_4 &= 1 \\
x_3 - x_4 &= 1 \\
0 &= 0 
\end{align}

そこで、x_4=c("c" は任意定数)とおくと、

\begin{align}
x_1 &=-4c + 1 \\
x_2 &= c + 1 \\
x_3 &= c + 1 \\
x_4 &= c 
\end{align}

これで解が全て求まった。

一般的なアルゴリズムについては、たとえば(コルテ & フィーゲン 2009, p. 96)を見よ。

注意[編集]

  • 対角成分が 0 になる場合には、枢軸選択(ピボット選択)という式の交換を行う必要がある。
    • 対角成分が 0 になる場合以外でも、対角成分が絶対値が最大の係数になるように枢軸選択を行ったほうが、解の丸め誤差が少なくなる。ただし、これは行列要素の絶対値が同程度の大きさの場合のみ成り立ち、スケーリングを行わずに枢軸選択を行うとむしろ精度が悪化する場合もあるため、注意が必要である
    • 枢軸選択には部分選択法と完全選択法がある。絶対値が最大の係数を探索する範囲が、部分選択法は掃出し列(下方向)のみであるのに対し、完全選択法ではすべての項目(右および下方向)である。完全選択の方が計算精度は高いが計算速度およびアルゴリズムの複雑化の面で不利であるため、完全選択法の採用は現実には少ない。
  • 疎行列に対してガウスの消去法のステップを行うと疎性を損なう。
  • 前進消去の段階において対角化を目指して、後退代入を行わずに x を直接計算する方法はガウス・ジョルダンの消去法Gauss-Jordan elimination)と呼ぶ。アルゴリズムは単純になるが、計算量は多くなる(変数が多い場合、ほぼ 1.5 倍になる)。
  • 計算量(乗算の回数)は、変数の個数を n とすると、ほぼ n3/3 になる。大部分は前進消去にかかっており、後退代入にはそれより少ないn2/2 程度である[4]

脚注[編集]

  1. ^ Schrijver 1998, p. 38.
  2. ^ コルテ & フィーゲン 2009, p. 95.
  3. ^ Schrijver 1998, p. 33.
  4. ^ a b Joel H. Ferziger; Milovan Perić; 小林敏雄、谷口伸行、坪倉誠訳 『コンピュータによる流体力学』 シュプリンガー・フェアラーク東京、2003年、88頁。ISBN 4-431-70842-1 

参考文献[編集]

関連項目[編集]