ガウスの消去法

ガウスの消去法（ガウスのしょうきょほう、英: Gaussian elimination）あるいは掃き出し法（はきだしほう）とは、連立一次方程式を解くための多項式時間アルゴリズムである。歴史的には前漢に九章算術で初めて記述された^[1]。線型代数学における重要なアルゴリズムで、連立一次方程式の解法以外にも行列の階数・行列式・逆行列の計算に使われる^[2]^[3]。大きな方程式系を系統的な方法で小さな系へ分解するという考え方に基づいており^[4]、基本的には、前進消去と後退代入という2つのステップから成り立つ。

基本的な考え方

n 元連立方程式の解が $x_{1}=c_{1},x_{2}=c_{2},...,x_{n}=c_{n}$ だとすると、これは次の連立方程式を略記したものと同じである。

{\begin{aligned}&1x_{1}+0x_{2}+\cdots +0x_{n}=c_{1}\\&0x_{1}+1x_{2}+\cdots +0x_{n}=c_{2}\\&\vdots \\&0x_{1}+0x_{2}+\cdots +1x_{n}=c_{n}\end{aligned}}

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

{\begin{aligned}1x_{1}&+&m_{12}x_{2}&+\cdots +&m_{1n}x_{n}&=c_{1}'\\0x_{1}&+&1x_{2}&+\cdots +&m_{2n}x_{n}&=c_{2}'\\\vdots \\0x_{1}&+&0x_{2}&+\cdots +&1x_{n}&=c_{n}\end{aligned}}

となった時点で、下から順に値を代入することで全ての解を確定できる。

例

次のような線形方程式系の解を求める。

{\begin{aligned}2x_{1}&+&4x_{2}&+&2x_{3}&=&8\\4x_{1}&+&10x_{2}&+&3x_{3}&=&17\\3x_{1}&+&7x_{2}&+&x_{3}&=&11\end{aligned}}

まず前進消去をする。
1. 1 番目の方程式を 1/2 倍する。
  ${\begin{aligned}x_{1}&+&2x_{2}&+&x_{3}&=&4\\4x_{1}&+&10x_{2}&+&3x_{3}&=&17\\3x_{1}&+&7x_{2}&+&x_{3}&=&11\end{aligned}}$
2. 2 番目の方程式に 1 番目の方程式の -4 倍を足す。3 番目の方程式に 1 番目の方程式の -3 倍を足す。
  ${\begin{aligned}x_{1}&+&2x_{2}&+&x_{3}&=&4\\&&2x_{2}&-&x_{3}&=&1\\&&x_{2}&-&2x_{3}&=&-1\end{aligned}}$
3. 2 番目の方程式を 1/2 倍する。
  ${\begin{aligned}x_{1}&+&2x_{2}&+&x_{3}&=&4\\&&x_{2}&-&{\frac {1}{2}}x_{3}&=&{\frac {1}{2}}\\&&x_{2}&-&2x_{3}&=&-1\end{aligned}}$
4. 3 番目の方程式に 2 番目の方程式の -1 倍を足す。
  ${\begin{aligned}x_{1}&+&2x_{2}&+&x_{3}&=&4\\&&x_{2}&-&{\frac {1}{2}}x_{3}&=&{\frac {1}{2}}\\&&&-&{\frac {3}{2}}x_{3}&=&-{\frac {3}{2}}\end{aligned}}$
次に後退代入をする。
1. 3 番目の方程式を -2/3 倍する
  ${\begin{aligned}x_{1}&+&2x_{2}&+&x_{3}&=&4\\&&x_{2}&-&{\frac {1}{2}}x_{3}&=&{\frac {1}{2}}\\&&&&x_{3}&=&1\end{aligned}}$
2. $x_{3}=1$ を 2 番目の方程式に代入する。
  ${\begin{aligned}x_{1}&+&2x_{2}&+&x_{3}&=&4\\&&x_{2}&&&=&1\\&&&&x_{3}&=&1\end{aligned}}$
3. $x_{3}=1$ と $x_{2}=1$ を 1 番目の方程式に代入する。
  ${\begin{aligned}x_{1}=1\\x_{2}=1\\x_{3}=1\end{aligned}}$

これで解が求まった。

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

注意

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

脚注

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

ガウスの消去法

基本的な考え方

例

注意

脚注

参考文献

関連項目