ガウスの消去法

ガウスの消去法（ガウスのしょうきょほう）あるいは掃き出し法（はきだしほう）とは、変数の数と方程式の本数が一致した連立一次方程式（線形方程式系）を解くための解法である。大きな方程式系を系統的な方法で小さな系へ分解するという考え方に基づいており。、基本的には、前進消去と後退代入という2つのステップから成り立つ。

基本的な考え方

n 元連立方程式の解が$x_1 = c_1,x_2=c_2, ... ,x_n=c_n$だとすると、これは次の連立方程式を略記したものと同じである。

$\begin{align} &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{align}$

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

$\begin{align} 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{align}$

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

例

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

$\begin{align} 2x_1 &+& 4x_2 &+& 2x_3 &=& 8 \\ 4x_1 &+& 10x_2 &+& 3x_3 &=& 17 \\ 3x_1 &+& 7x_2 &+& x_3 &=& 11 \end{align}$

1. まず前進消去をする。
   1. 1 番目の方程式を 1/2 倍する。

      $\begin{align} x_1 &+& 2x_2 &+& x_3 &=& 4 \\ 4x_1 &+& 10x_2 &+& 3x_3 &=& 17 \\ 3x_1 &+& 7x_2 &+& x_3 &=& 11 \end{align}$

   2. 2 番目の方程式に 1 番目の方程式の -4 倍を足す。3 番目の方程式に 1 番目の方程式の -3 倍を足す。

      $\begin{align} x_1 &+& 2x_2 &+& x_3 &=& 4 \\ && 2x_2 &-& x_3 &=& 1 \\ && x_2 &-& 2x_3 &=& -1 \end{align}$

   3. 2 番目の方程式を 1/2 倍する。

      $\begin{align} x_1 &+& 2x_2 &+& x_3 &=& 4 \\ && x_2 &-& \frac{1}{2}x_3 &=& \frac{1}{2} \\ && x_2 &-& 2x_3 &=& -1 \end{align}$

   4. 3 番目の方程式に 2 番目の方程式の -1 倍を足す。

      $\begin{align} 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{align}$

2. 次に後退代入をする。
   1. 3 番目の方程式を -2/3 倍する

      $\begin{align} x_1 &+& 2x_2 &+& x_3 &=& 4 \\ && x_2 &-& \frac{1}{2}x_3 &=& \frac{1}{2} \\ && && x_3 &=& 1 \end{align}$

   2. $x_3 = 1$ を 2 番目の方程式に代入する。

      $\begin{align} x_1 &+& 2x_2 &+& x_3 &=& 4 \\ && x_2 && &=& 1 \\ && && x_3 &=& 1 \end{align}$

   3. $x_3 = 1$ と $x_2 = 1$ を 1 番目の方程式に代入する。

      $\begin{align} x_1 = 1 \\ x_2 = 1 \\ x_3 = 1 \end{align}$

これで解が求まった。

注意

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

関連項目

• アルゴリズム
• 三角行列