ガウスの消去法

ウィキペディア

ガウスの消去法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/10/04 09:50 UTC 版)

ガウスの消去法（ガウスのしょうきょほう、英: Gaussian elimination）あるいは掃き出し法（はきだしほう、英: row reduction）とは、連立一次方程式を解くための多項式時間アルゴリズムであり、通常は問題となる連立一次方程式の係数からなる拡大係数行列に対して行われる一連の変形操作を意味する。 同様のアルゴリズムは歴史的には前漢に九章算術で初めて記述された。連立一次方程式の解法以外にも

• 行列の階数の計算
• 行列式の計算
• 正則行列の逆行列の計算

などに使われる。このアルゴリズムは、大きな方程式系を系統的な方法で小さな系へ分解する方法を与えるものと理解することができ、基本的には、前進消去 (forward elimination) と後退代入 (backward substitution) という2つのステップから成る。

行列に対して掃き出し法を行う為には、行に関する基本変形を行列に可能な限り繰り返し行って行列の左下部分の成分を全て 0 にする。行に関する基本変形には、

• 二つの行を入れ替えるもの
• ある行を0でない定数倍するもの
• ある行に他のある行の定数倍を加えるもの

の3種類の操作があり、必ず行列を上三角型に変形することができる。実際には、ゼロでない成分を持つ行が、ゼロしか成分に持たない行よりも上に位置し、主成分（行内の 0 でない成分のうち最も左にあるもの）が、その行の上にある行の主成分よりも、真に右側に位置する行階段形に変形される。 特に全ての主成分が 1 になり、主成分を含む列にある主成分以外の成分が 0 であるとき、この行列は行簡約階段形であると呼ばれる。この最終形は一意的であり、どのような行基本変形が行われたかには依存しない。例えば、次の様な行基本変形の繰り返し（各ステップで複数の基本変形を行っている）で、3番目と4番目は共に行階段形であるが、最後の4番目が一意に定まる行簡約階段形である。

$\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]$ カテゴリ