ガウスの消去法

ガウスの消去法（ガウスのしょうきょほう、）あるいは掃き出し法（はきだしほう、）とは、連立一次方程式を解くための多項式時間アルゴリズムであり、通常は問題となる連立一次方程式の係数からなる拡大係数行列に対して行われる一連の変形操作を意味する。
同様のアルゴリズムは歴史的には前漢に九章算術で初めて記述された。連立一次方程式の解法以外にも
などに使われる。このアルゴリズムは、大きな方程式系を系統的な方法で小さな系へ分解する方法を与えるものと理解することができ、基本的には、前進消去 (forward elimination) と後退代入 (backward substitution) という2つのステップから成る。
行列に対して掃き出し法を行う為には、行に関する基本変形を行列に可能な限り繰り返し行って行列の左下部分の成分を全て 0 にする。行に関する基本変形には、
の3種類の操作があり、必ず行列を上三角型に変形することができる。実際には、ゼロでない成分を持つ行が、ゼロしか成分に持たない行よりも上に位置し、主成分（行内の 0 でない成分のうち最も左にあるもの）が、その行の上にある行の主成分よりも、真に右側に位置する行階段形に変形される。
特に全ての主成分が 1 になり、主成分を含む列にある主成分以外の成分が 0 であるとき、この行列は行簡約階段形であると呼ばれる。この最終形は一意的であり、どのような行基本変形が行われたかには依存しない。例えば、次の様な行基本変形の繰り返し（各ステップで複数の基本変形を行っている）で、3番目と4番目は共に行階段形であるが、最後の4番目が一意に定まる行簡約階段形である。
行基本変形を用いて行列を行階段形に変形することをガウス・ジョルダンの消去法（ガウス・ジョルダンのしょうきょほう、）という。ガウスの消去法という用語を上三角形または（簡約とは限らない）行階段形へ変換する手法を指すこともある。連立一次方程式の解を求める際に行基本変形を完全に簡約化する前に止めてしまう方が、計算上の理由から良いとされる場合もある。
基本的な考え方.
次の "n" 元"m"連立一次方程式を考察する。右側にある行列がその拡大係数行列である。
この方程式が formula_3（formula_4 かつ formula_5 は任意の定数）という解を持つとすると、これらの式は次の連立一次方程式を略記したものであると見なせる。ただし、下段に並んでいる、左辺の全ての係数が "0" である式は formula_6 本ある。
同様に右側にある行列がその拡大係数行列である。
始めの拡大係数行列から上の拡大係数行列の形に変形する為には、対角成分に注目して行基本変形を行って行簡約階段形に変形する。ただし簡単のため、変数の番号を付け替えることなしに主成分がすべて対角線にあるものと仮定する。しかし一般的には、このような仮定の下で作業を行っても次の形の行簡約階段形にしか変形できない。（最も右の列の 番目の成分以下はすべて '0'）
この時点で、与えられた連立一次方程式が解を持つ必要条件が formula_9 であることが分かり、これは十分条件でもある。実際、formula_9 とすると、上記の形の解が逆に得られていることは明らかである。より現実的な解法としては、未知数が "k" 個定まった時点で残り "k" + 1 個の未知数を含む式が解けるため、formula_11 から formula_12 までの全ての変数を孤立させる必要はない。
これを行列の言葉で言えば、拡大係数行列を行簡約階段形にまで変形せずに途中で止めてしまう方がより現実的であるということになる。つまり、拡大係数行列が次の形の行階段形に変形された時点で、それ以上の簡約化を止めるのである。このとき、対応する連立一次方程式がその右の形に表せる：
従って、任意定数 formula_14 を用いて 番目以後の "s" 個の変数をformula_15 と置き、右辺に移項して下から順に値を代入していくことで全ての解を確定できる。
例.
次の連立一次方程式の解を拡大係数行列を用いずにガウスの消去法のアルゴリズムで求めてみる。
式の本数が固定されていること、式の入れ替えもまた一つの操作であることに注意すべきである。
そこで、formula_29（"c" は任意定数）とおくと、
これで解が全て求まった。
一般的なアルゴリズムについては、たとえばを見よ。