この記事にはや(外部リンク)の一覧が含まれていますが、(脚注)による参照が不十分であるため、情報源が依然不明確です。適切な位置に脚注を追加して、記事の(信頼性向上)にご協力ください。(2022年7月) |
ガウスの消去法(ガウスのしょうきょほう、英: Gaussian elimination)あるいは掃き出し法(はきだしほう、英: row reduction)とは、連立一次方程式を解くための多項式時間アルゴリズムであり、通常は問題となる連立一次方程式の係数からなる拡大係数行列に対して行われる一連の変形操作を意味する。 同様のアルゴリズムは歴史的には前漢に九章算術で初めて記述された。連立一次方程式の解法以外にも
などに使われる。このアルゴリズムは、大きな方程式系を系統的な方法で小さな系へ分解する方法を与えるものと理解することができ[4]、基本的には、前進消去 (forward elimination) と後退代入 (backward substitution) という2つのステップから成る。
行列に対して掃き出し法を行う為には、行に関する基本変形を行列に可能な限り繰り返し行って行列の左下部分の成分を全て 0 にする。行に関する基本変形には、
- 二つの行を入れ替えるもの
- ある行を0でない定数倍するもの
- ある行に他のある行の定数倍を加えるもの
の3種類の操作があり、必ず行列を上三角型に変形することができる。実際には、ゼロでない成分を持つ行が、ゼロしか成分に持たない行よりも上に位置し、主成分(行内の 0 でない成分のうち最も左にあるもの)が、その行の上にある行の主成分よりも、真に右側に位置する行階段形に変形される。 特に全ての主成分が 1 になり、主成分を含む列にある主成分以外の成分が 0 であるとき、この行列は行簡約階段形であると呼ばれる。この最終形は一意的であり、どのような行基本変形が行われたかには依存しない。例えば、次の様な行基本変形の繰り返し(各ステップで複数の基本変形を行っている)で、3番目と4番目は共に行階段形であるが、最後の4番目が一意に定まる行簡約階段形である。
行基本変形を用いて行列を行階段形に変形することをガウス・ジョルダンの消去法(ガウス・ジョルダンのしょうきょほう、英: Gauss–Jordan elimination)という。ガウスの消去法という用語を上三角形または(簡約とは限らない)行階段形へ変換する手法を指すこともある。連立一次方程式の解を求める際に行基本変形を完全に簡約化する前に止めてしまう方が、計算上の理由から良いとされる場合もある。
次の n 元m連立一次方程式を考察する。右側にある行列がその拡大係数行列である。
-
この方程式が ( かつ は任意の定数)という解を持つとすると、これらの式は次の連立一次方程式を略記したものであると見なせる。ただし、下段に並んでいる、左辺の全ての係数が 0 である式は 本ある。 同様に右側にある行列がその拡大係数行列である。
-
始めの拡大係数行列から上の拡大係数行列の形に変形する為には、対角成分に注目して行基本変形を行って行簡約階段形に変形する。ただし簡単のため、変数の番号を付け替えることなしに主成分がすべて対角線にあるものと仮定する。しかし一般的には、このような仮定の下で作業を行っても次の形の行簡約階段形にしか変形できない。(最も右の列の r + 2 番目の成分以下はすべて '0')
-
この時点で、与えられた連立一次方程式が解を持つ必要条件が であることが分かり、これは十分条件でもある。実際、 とすると、上記の形の解が逆に得られていることは明らかである。より現実的な解法としては、未知数が k 個定まった時点で残り k + 1 個の未知数を含む式が解けるため、 から までの全ての変数を孤立させる必要はない。 これを行列の言葉で言えば、拡大係数行列を行簡約階段形にまで変形せずに途中で止めてしまう方がより現実的であるということになる。つまり、拡大係数行列が次の形の行階段形に変形された時点で、それ以上の簡約化を止めるのである。このとき、対応する連立一次方程式がその右の形に表せる:
-
従って、任意定数 を用いて {{math2|>r+1</math> 番目以後の s 個の変数を と置き、右辺に移項して下から順に値を代入していくことで全ての解を確定できる。