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