ガウスの消去法（掃き出し法）による連立一次方程式の解き方

ガウスの消去法の基本的なアイデアは，中学数学で学ぶ「消去法」です。

ガウスの消去法は

• 前進消去（文字を1つずつ消していく操作）
• 後退代入（1成分ずつ答えを求めていく操作）

からなります。順々に説明していきます。

注：以下では方程式の数と変数の数が同じで，解が1つしかない（係数行列が正則）場合を考えます。解が存在しない場合や無数にある場合も少し状況が変わりますが使えます。

まず，方程式の定数倍を他の方程式に加えることで文字を順番に消していきます。

前進消去における目標の形は $k$ 番目の方程式には $k$ 個目以降の変数のみがあるような連立一次方程式です。

注：前進消去のステップ $i$ で $i$ 番目の式の $x_i$ の係数が $0$ のときはそれを使って $x_i$ を消去することができません。その場合は適当に方程式の順番を交換すればOKです（係数行列が正則という仮定のもとでは $x_i$ の係数が $0$ でない方程式が必ず存在するのでそれを $i$ 番目に持っていく）。

後退代入は簡単です。後ろの式から順番にたどっていき，1つずつ変数の値を求めていくだけです。

• アイデアが簡単
  ガウスの消去法の基本的なアイデアは中学数学で学ぶレベルです！　中学，高校数学で登場する連立一次方程式は3変数くらいまでで，代入法または消去法で解くのが一般的でしたが，同じアイデアが一般の $n$ 変数の場合にも通用します。今回は消去法に注目しました。

• 計算時間が短い
  連立一次方程式の解を明示的に表す公式としてクラメルの公式があります。→クラメルの公式の具体例と証明
  しかし，クラメルの公式をそのまま使おうとすると大規模な問題では計算量が爆発します。 一方，ガウスの消去法は計算時間がそれなりに短い（乗算がだいたい $\dfrac{n^3}{3}$ 回）ので大規模な連立一次方程式にも太刀打ちできます。