ガウスの消去法

ガウスの消去法（ガウスのしょうきょほう、英: Gaussian elimination）あるいは掃き出し法（はきだしほう、英: row reduction）とは、連立一次方程式を解くための多項式時間アルゴリズムであり、通常は問題となる連立一次方程式の係数からなる拡大係数行列に対して行われる一連の変形操作を意味する。 同様のアルゴリズムは歴史的には前漢に九章算術で初めて記述された[1]。連立一次方程式の解法以外にも

などに使われる[2][3]。このアルゴリズムは、大きな方程式系を系統的な方法で小さな系へ分解する方法を与えるものと理解することができ[4]、基本的には、前進消去 (forward elimination) と後退代入 (backward substitution) という2つのステップから成る。

行列に対して掃き出し法を行う為には、行に関する基本変形を行列に可能な限り繰り返し行って行列の左下部分の成分を全て 0 にする。行に関する基本変形には、

  • 二つの行を入れ替えるもの
  • ある行を0でない定数倍するもの
  • ある行に他のある行の定数倍を加えるもの

の3種類の操作があり、必ず行列を上三角型に変形することができる。実際には、ゼロでない成分を持つ行が、ゼロしか成分に持たない行よりも上に位置し、主成分（行内の 0 でない成分のうち最も左にあるもの）が、その行の上にある行の主成分よりも、真に右側に位置する行階段形に変形される。 特に全ての主成分が 1 になり、主成分を含む列にある主成分以外の成分が 0 であるとき、この行列は行簡約階段形であると呼ばれる。この最終形は一意的であり、どのような行基本変形が行われたかには依存しない。例えば、次の様な行基本変形の繰り返し（各ステップで複数の基本変形を行っている）で、3番目と4番目は共に行階段形であるが、最後の4番目が一意に定まる行簡約階段形である。

[ 1 3 1 9 1 1 − 1 1 3 11 5 35 ] → [ 1 3 1 9 0 − 2 − 2 − 8 0 2 2 8 ] → [ 1 3 1 9 0 − 2 − 2 − 8 0 0 0 0 ] → [ 1 0 − 2 − 3 0 1 1 4 0 0 0 0 ] {\displaystyle \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）という。ガウスの消去法という用語を上三角形または（簡約とは限らない）行階段形へ変換する手法を指すこともある。連立一次方程式の解を求める際に行基本変形を完全に簡約化する前に止めてしまう方が、計算上の理由から良いとされる場合もある。

基本的な考え方

次の n 元m連立一次方程式を考察する。右側にある行列がその拡大係数行列である。

a 11 x 1 + a 12 x 2 + ⋯ + a 1 n x n = b 1 a 21 x 1 + a 22 x 2 + ⋯ + a 2 n x n = b 2 ⋮ a m 1 x 1 + a m 2 x 2 + ⋯ + a m n x n = b m [ a 11 a 12 ⋯ a 1 n b 1 a 21 a 22 ⋯ a 2 n b 2 ⋮ ⋮ ⋱ ⋮ ⋮ a m 1 a m 2 ⋯ a m n b m ] {\displaystyle {\begin{aligned}&a_{11}x_{1}+a_{12}x_{2}+\cdots +a_{1n}x_{n}=b_{1}\\&a_{21}x_{1}+a_{22}x_{2}+\cdots +a_{2n}x_{n}=b_{2}\\&\qquad \vdots \\&a_{m1}x_{1}+a_{m2}x_{2}+\cdots +a_{mn}x_{n}=b_{m}\end{aligned}}\qquad \left[{\begin{array}{cccc|c}a_{11}&a_{12}&\cdots &a_{1n}&b_{1}\\a_{21}&a_{22}&\cdots &a_{2n}&b_{2}\\\vdots &\vdots &\ddots &\vdots &\vdots \\a_{m1}&a_{m2}&\cdots &a_{mn}&b_{m}\end{array}}\right]}

この方程式が x 1 = c 1 + d 11 λ 1 + ⋯ + d 1 s λ s , x 2 = c 2 + d 21 λ 1 + ⋯ + d 2 s λ s , ⋯ , x r = c r + d r 1 λ 1 + ⋯ + d r s λ s , x r + 1 = λ 1 , … , x n = λ s {\displaystyle x_{1}=c_{1}+d_{11}\lambda _{1}+\cdots +d_{1s}\lambda _{s},x_{2}=c_{2}+d_{21}\lambda _{1}+\cdots +d_{2s}\lambda _{s},\cdots ,x_{r}=c_{r}+d_{r1}\lambda _{1}+\cdots +d_{rs}\lambda _{s},x_{r+1}=\lambda _{1},\ldots ,x_{n}=\lambda _{s}} （ n = r + s {\displaystyle n=r{+}s} かつ λ 1 , . . . , λ s {\displaystyle \lambda _{1},...,\lambda _{s}} は任意の定数）という解を持つとすると、これらの式は次の連立一次方程式を略記したものであると見なせる。ただし、下段に並んでいる、左辺の全ての係数が 0 である式は m − r {\displaystyle m{-}r} 本ある。 同様に右側にある行列がその拡大係数行列である。

1 x 1 + 0 x 2 + ⋯ + 0 x r − d 11 x r + 1 − ⋯ − d 1 s x n = c 1 0 x 1 + 1 x 2 + ⋯ + 0 x r − d 21 x r + 1 − ⋯ − d 2 s x n = c 2 ⋮ 0 x 1 + 0 x 2 + ⋯ + 1 x r − d r 1 x r + 1 − ⋯ − d r s x n = c r 0 x 1 + 0 x 2 + ⋯ + 0 x r + 0 x r + 1 + ⋯ + 0 x n = 0 ⋮ 0 x 1 + 0 x 2 + ⋯ + 0 x r + 0 x r + 1 + ⋯ + 0 x n = 0 [ 1 0 ⋯ 0 − d 11 ⋯ − d 1 s c 1 0 1 ⋯ 0 − d 21 ⋯ − d 2 s c 2 ⋮ ⋮ ⋱ ⋮ ⋮ ⋮ ⋮ 0 0 ⋯ 1 − d r 1 ⋯ − d r s c r 0 0 ⋯ 0 0 ⋯ 0 0 ⋮ ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ 0 0 ⋯ 0 0 ⋯ 0 0 ] {\displaystyle {\begin{aligned}&1x_{1}+0x_{2}+\cdots +0x_{r}-d_{11}x_{r+1}-\cdots -d_{1s}x_{n}=c_{1}\\&0x_{1}+1x_{2}+\cdots +0x_{r}-d_{21}x_{r+1}-\cdots -d_{2s}x_{n}=c_{2}\\&\qquad \vdots \\&0x_{1}+0x_{2}+\cdots +1x_{r}-d_{r1}x_{r+1}-\cdots -d_{rs}x_{n}=c_{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{aligned}}\qquad \left[{\begin{array}{ccccccc|c}1&0&\cdots &0&-d_{11}&\cdots &-d_{1s}&c_{1}\\0&1&\cdots &0&-d_{21}&\cdots &-d_{2s}&c_{2}\\\vdots &\vdots &\ddots &\vdots &\vdots &&\vdots &\vdots \\0&0&\cdots &1&-d_{r1}&\cdots &-d_{rs}&c_{r}\\0&0&\cdots &0&0&\cdots &0&0\\\vdots &\vdots &&\vdots &\vdots &\ddots &\vdots &\vdots \\0&0&\cdots &0&0&\cdots &0&0\end{array}}\right]}

始めの拡大係数行列から上の拡大係数行列の形に変形する為には、対角成分に注目して行基本変形を行って行簡約階段形に変形する。ただし簡単のため、変数の番号を付け替えることなしに主成分がすべて対角線にあるものと仮定する。しかし一般的には、このような仮定の下で作業を行っても次の形の行簡約階段形にしか変形できない。（最も右の列の r + 2 番目の成分以下はすべて '0'）

[ 1 0 ⋯ 0 − d 11 ⋯ − d 1 s c 1 0 1 ⋯ 0 − d 21 ⋯ − d 2 s c 2 ⋮ ⋮ ⋱ ⋮ ⋮ ⋮ ⋮ 0 0 ⋯ 1 − d r 1 ⋯ − d r s c r 0 0 ⋯ 0 0 ⋯ 0 c r + 1 ⋮ ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ 0 0 ⋯ 0 0 ⋯ 0 0 ] {\displaystyle \left[{\begin{array}{ccccccc|c}1&0&\cdots &0&-d_{11}&\cdots &-d_{1s}&c_{1}\\0&1&\cdots &0&-d_{21}&\cdots &-d_{2s}&c_{2}\\\vdots &\vdots &\ddots &\vdots &\vdots &&\vdots &\vdots \\0&0&\cdots &1&-d_{r1}&\cdots &-d_{rs}&c_{r}\\0&0&\cdots &0&0&\cdots &0&c_{r+1}\\\vdots &\vdots &&\vdots &\vdots &\ddots &\vdots &\vdots \\0&0&\cdots &0&0&\cdots &0&0\end{array}}\right]}

この時点で、与えられた連立一次方程式が解を持つ必要条件が c r + 1 = 0 {\displaystyle c_{r+1}=0} であることが分かり、これは十分条件でもある。実際、 c r + 1 = 0 {\displaystyle c_{r+1}=0} とすると、上記の形の解が逆に得られていることは明らかである。より現実的な解法としては、未知数が k 個定まった時点で残り k + 1 個の未知数を含む式が解けるため、 x 1 {\displaystyle x_{1}} から x r {\displaystyle x_{r}} までの全ての変数を孤立させる必要はない。 これを行列の言葉で言えば、拡大係数行列を行簡約階段形にまで変形せずに途中で止めてしまう方がより現実的であるということになる。つまり、拡大係数行列が次の形の行階段形に変形された時点で、それ以上の簡約化を止めるのである。このとき、対応する連立一次方程式がその右の形に表せる：

[ 1 m 12 ⋯ m 1 r − d 11 ′ ⋯ − d 1 s ′ c 1 ′ 0 1 ⋯ m 2 r − d 21 ′ ⋯ − d 2 s ′ c 2 ′ ⋮ ⋮ ⋱ ⋮ ⋮ ⋮ ⋮ 0 0 ⋯ 1 − d r 1 ′ ⋯ − d r s ′ c r ′ 0 0 ⋯ 0 0 ⋯ 0 0 ⋮ ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ 0 0 ⋯ 0 0 ⋯ 0 0 ] 1 x 1 + m 12 x 2 + ⋯ + m 1 r x r − d 11 ′ x r + 1 − ⋯ − d 1 s ′ x n = c 1 ′ 0 x 1 + 1 x 2 + ⋯ + m 2 r x r − d 21 ′ x r + 1 − ⋯ − d 2 s ′ x n = c 2 ′ ⋮ 0 x 1 + 0 x 2 + ⋯ + 1 x r − d r 1 ′ x r + 1 − ⋯ − d r s ′ x n = c r ′ 0 x 1 + 0 x 2 + ⋯ + 0 x r + 0 x r + 1 + ⋯ + 0 x n = 0 ⋮ 0 x 1 + 0 x 2 + ⋯ + 0 x r + 0 x r + 1 + ⋯ + 0 x n = 0 {\displaystyle \left[{\begin{array}{ccccccc|c}1&m_{12}&\cdots &m_{1r}&-d'_{11}&\cdots &-d'_{1s}&c'_{1}\\0&1&\cdots &m_{2r}&-d'_{21}&\cdots &-d'_{2s}&c'_{2}\\\vdots &\vdots &\ddots &\vdots &\vdots &&\vdots &\vdots \\0&0&\cdots &1&-d'_{r1}&\cdots &-d'_{rs}&c'_{r}\\0&0&\cdots &0&0&\cdots &0&0\\\vdots &\vdots &&\vdots &\vdots &\ddots &\vdots &\vdots \\0&0&\cdots &0&0&\cdots &0&0\end{array}}\right]\qquad {\begin{aligned}&1x_{1}+m_{12}x_{2}+\cdots +m_{1r}x_{r}-d'_{11}x_{r+1}-\cdots -d'_{1s}x_{n}=c'_{1}\\&0x_{1}+1x_{2}+\cdots +m_{2r}x_{r}-d'_{21}x_{r+1}-\cdots -d'_{2s}x_{n}=c'_{2}\\&\qquad \vdots \\&0x_{1}+0x_{2}+\cdots +1x_{r}-d'_{r1}x_{r+1}-\cdots -d'_{rs}x_{n}=c'_{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{aligned}}}

従って、任意定数 λ 1 , … , λ s {\displaystyle \lambda _{1},\ldots ,\lambda _{s}} を用いて >r+1 番目以後の s 個の変数を x r + 1 = λ 1 , x r + 2 = λ 2 , . . . , x n = λ s {\displaystyle x_{r+1}=\lambda _{1},x_{r+2}=\lambda _{2},...,x_{n}=\lambda _{s}} と置き、右辺に移項して下から順に値を代入していくことで全ての解を確定できる。

例

次の連立一次方程式の解を拡大係数行列を用いずにガウスの消去法のアルゴリズムで求めてみる。 式の本数が固定されていること、式の入れ替えもまた一つの操作であることに注意すべきである。

2 x 1 + 4 x 2 + 2 x 3 + 2 x 4 = 8 4 x 1 + 10 x 2 + 3 x 3 + 3 x 4 = 17 2 x 1 + 6 x 2 + x 3 + x 4 = 9 3 x 1 + 7 x 2 + x 3 + 4 x 4 = 11 {\displaystyle {\begin{aligned}&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{aligned}}}
  1. まず前進消去をする。
    1. 1 番目の方程式を 1/2 倍する。
      x 1 + 2 x 2 + x 3 + x 4 = 4 4 x 1 + 10 x 2 + 3 x 3 + 3 x 4 = 17 2 x 1 + 6 x 2 + x 3 + x 4 = 9 3 x 1 + 7 x 2 + x 3 + 4 x 4 = 11 {\displaystyle {\begin{aligned}&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{aligned}}}
    2. 2 番目の方程式に 1 番目の方程式の −4 倍を足す。3 番目の方程式に 1 番目の方程式の −2 倍を足す。4 番目の方程式に 1 番目の方程式の −3 倍を足す。
      x 1 + 2 x 2 + x 3 + x 4 = 4 2 x 2 − x 3 − x 4 = 1 2 x 2 − x 3 − x 4 = 1 x 2 − 2 x 3 + x 4 = − 1 {\displaystyle {\begin{aligned}&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{aligned}}}
    3. 2 番目の方程式を 1/2 倍する。
      x 1 + 2 x 2 + x 3 + x 4 = 4 x 2 − 1 2 x 3 − 1 2 x 4 = 1 2 2 x 2 − x 3 − x 4 = 1 x 2 − 2 x 3 + x 4 = − 1 {\displaystyle {\begin{aligned}&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{aligned}}}
    4. 3 番目の方程式に 2 番目の方程式の -2 倍を足す。4 番目の方程式に 2 番目の方程式の -1 倍を足す。
      x 1 + 2 x 2 + x 3 + x 4 = 4 x 2 − 1 2 x 3 − 1 2 x 4 = 1 2 0 = 0 − 3 2 x 3 + 3 2 x 4 = − 3 2 {\displaystyle {\begin{aligned}&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{aligned}}}
    5. 3 番目の方程式と 4 番目の方程式を入れ替える。
      x 1 + 2 x 2 + x 3 + x 4 = 4 x 2 − 1 2 x 3 − 1 2 x 4 = 1 2 − 3 2 x 3 + 3 2 x 4 = − 3 2 0 = 0 {\displaystyle {\begin{aligned}&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{aligned}}}
  2. 次に後退代入をする。
    1. 3 番目の方程式を − 2 3 {\displaystyle -{\frac {2}{3}}} 倍する
      x 1 + 2 x 2 + x 3 + x 4 = 4 x 2 − 1 2 x 3 − 1 2 x 4 = 1 2 x 3 − x 4 = 1 0 = 0 {\displaystyle {\begin{aligned}&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{aligned}}}
    2. x 3 = 1 + x 4 {\displaystyle x_{3}=1+x_{4}} を 2 番目の方程式に代入する。
      x 1 + 2 x 2 + x 3 + x 4 = 4 x 2 − x 4 = 1 x 3 − x 4 = 1 0 = 0 {\displaystyle {\begin{aligned}&x_{1}&+&2x_{2}&+&x_{3}&+&x_{4}&=4\\&&&x_{2}&&&-&x_{4}&=1\\&&&&&x_{3}&-&x_{4}&=1\\&&&&&&&0&=0\end{aligned}}}
    3. x 3 = 1 + x 4 {\displaystyle x_{3}=1+x_{4}} と x 2 = 1 + x 4 {\displaystyle x_{2}=1+x_{4}} を 1 番目の方程式に代入する。
      x 1 + 4 x 4 = 1 x 2 − x 4 = 1 x 3 − x 4 = 1 0 = 0 {\displaystyle {\begin{aligned}x_{1}+4x_{4}&=1\\x_{2}-x_{4}&=1\\x_{3}-x_{4}&=1\\0&=0\end{aligned}}}

そこで、 x 4 = c {\displaystyle x_{4}=c} （"c" は任意定数）とおくと、

x 1 = − 4 c + 1 x 2 = c + 1 x 3 = c + 1 x 4 = c {\displaystyle {\begin{aligned}x_{1}&=-4c+1\\x_{2}&=c+1\\x_{3}&=c+1\\x_{4}&=c\end{aligned}}}

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

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

注意

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

脚注

[脚注の使い方]
  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。 

参考文献

  • コルテ, B.、フィーゲン, J.『組合せ最適化：理論とアルゴリズム』（第2版）シュプリンガー・ジャパン、2009年。ISBN 978-4-431-10021-8。https://books.google.com/books?id=7OfUJPqwyKwC&pg=PA95。 
  • Schrijver, Alexander (1998). Theory of Linear and Integral Programming. Wiley-Interscience series in discrete mathematics and optimization. Wiley. ISBN 0-471-98232-6. https://books.google.com/books?id=zEzW5mhppB8C&pg=PA31 
  • [1]

関連項目

外部リンク

  • 表
  • 話
  • 編
  • 歴
連立一次方程式
ベクトル
ベクトル空間
計量ベクトル空間
行列・線型写像
演算・操作
不変量
クラス
行列式
多重線型代数
数値線形代数
基本的な概念
ソフトウェア
ライブラリ
反復法・技法
人物
行列値関数
その他
カテゴリ カテゴリ