ガウスの消去法

この記事には参考文献や外部リンクの一覧が含まれていますが、脚注による参照が不十分であるため、情報源が依然不明確です。 適切な位置に脚注を追加して、記事の信頼性向上にご協力ください。（2022年7月）

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

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

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

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

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

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

${\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）という。ガウスの消去法という用語を上三角形または（簡約とは限らない）行階段形へ変換する手法を指すこともある。連立一次方程式の解を求める際に行基本変形を完全に簡約化する前に止めてしまう方が、計算上の理由から良いとされる場合もある。

次の n 元m連立一次方程式を考察する。右側にある行列がその拡大係数行列である。

${\displaystyle {\begin{aligned}&a_{11}x_{1}+a_{12}x_{2}+\cdots +a_{1n}x_{n}=b_{1}\\&a_{21}x_{1}+a_{22}x_{2}+\cdots +a_{2n}x_{n}=b_{2}\\&\qquad \vdots \\&a_{m1}x_{1}+a_{m2}x_{2}+\cdots +a_{mn}x_{n}=b_{m}\end{aligned}}\qquad \left[{\begin{array}{cccc|c}a_{11}&a_{12}&\cdots &a_{1n}&b_{1}\\a_{21}&a_{22}&\cdots &a_{2n}&b_{2}\\\vdots &\vdots &\ddots &\vdots &\vdots \\a_{m1}&a_{m2}&\cdots &a_{mn}&b_{m}\end{array}}\right]}$

この方程式が ${\displaystyle x_{1}=c_{1}+d_{11}\lambda _{1}+\cdots +d_{1s}\lambda _{s},x_{2}=c_{2}+d_{21}\lambda _{1}+\cdots +d_{2s}\lambda _{s},\cdots ,x_{r}=c_{r}+d_{r1}\lambda _{1}+\cdots +d_{rs}\lambda _{s},x_{r+1}=\lambda _{1},\ldots ,x_{n}=\lambda _{s}}$（${\displaystyle n=r{+}s}$ かつ ${\displaystyle \lambda _{1},...,\lambda _{s}}$ は任意の定数）という解を持つとすると、これらの式は次の連立一次方程式を略記したものであると見なせる。ただし、下段に並んでいる、左辺の全ての係数が 0 である式は ${\displaystyle m{-}r}$ 本ある。 同様に右側にある行列がその拡大係数行列である。

${\displaystyle {\begin{aligned}&1x_{1}+0x_{2}+\cdots +0x_{r}-d_{11}x_{r+1}-\cdots -d_{1s}x_{n}=c_{1}\\&0x_{1}+1x_{2}+\cdots +0x_{r}-d_{21}x_{r+1}-\cdots -d_{2s}x_{n}=c_{2}\\&\qquad \vdots \\&0x_{1}+0x_{2}+\cdots +1x_{r}-d_{r1}x_{r+1}-\cdots -d_{rs}x_{n}=c_{r}\\&0x_{1}+0x_{2}+\cdots +0x_{r}+0x_{r+1}+\cdots +0x_{n}=0\\&\qquad \vdots \\&0x_{1}+0x_{2}+\cdots +0x_{r}+0x_{r+1}+\cdots +0x_{n}=0\end{aligned}}\qquad \left[{\begin{array}{ccccccc|c}1&0&\cdots &0&-d_{11}&\cdots &-d_{1s}&c_{1}\\0&1&\cdots &0&-d_{21}&\cdots &-d_{2s}&c_{2}\\\vdots &\vdots &\ddots &\vdots &\vdots &&\vdots &\vdots \\0&0&\cdots &1&-d_{r1}&\cdots &-d_{rs}&c_{r}\\0&0&\cdots &0&0&\cdots &0&0\\\vdots &\vdots &&\vdots &\vdots &\ddots &\vdots &\vdots \\0&0&\cdots &0&0&\cdots &0&0\end{array}}\right]}$

始めの拡大係数行列から上の拡大係数行列の形に変形する為には、対角成分に注目して行基本変形を行って行簡約階段形に変形する。ただし簡単のため、変数の番号を付け替えることなしに主成分がすべて対角線にあるものと仮定する。しかし一般的には、このような仮定の下で作業を行っても次の形の行簡約階段形にしか変形できない。（最も右の列の r + 2 番目の成分以下はすべて '0'）

${\displaystyle \left[{\begin{array}{ccccccc|c}1&0&\cdots &0&-d_{11}&\cdots &-d_{1s}&c_{1}\\0&1&\cdots &0&-d_{21}&\cdots &-d_{2s}&c_{2}\\\vdots &\vdots &\ddots &\vdots &\vdots &&\vdots &\vdots \\0&0&\cdots &1&-d_{r1}&\cdots &-d_{rs}&c_{r}\\0&0&\cdots &0&0&\cdots &0&c_{r+1}\\\vdots &\vdots &&\vdots &\vdots &\ddots &\vdots &\vdots \\0&0&\cdots &0&0&\cdots &0&0\end{array}}\right]}$

この時点で、与えられた連立一次方程式が解を持つ必要条件が ${\displaystyle c_{r+1}=0}$ であることが分かり、これは十分条件でもある。実際、${\displaystyle c_{r+1}=0}$ とすると、上記の形の解が逆に得られていることは明らかである。より現実的な解法としては、未知数が k 個定まった時点で残り k + 1 個の未知数を含む式が解けるため、${\displaystyle x_{1}}$ から ${\displaystyle x_{r}}$ までの全ての変数を孤立させる必要はない。 これを行列の言葉で言えば、拡大係数行列を行簡約階段形にまで変形せずに途中で止めてしまう方がより現実的であるということになる。つまり、拡大係数行列が次の形の行階段形に変形された時点で、それ以上の簡約化を止めるのである。このとき、対応する連立一次方程式がその右の形に表せる：

${\displaystyle \left[{\begin{array}{ccccccc|c}1&m_{12}&\cdots &m_{1r}&-d'_{11}&\cdots &-d'_{1s}&c'_{1}\\0&1&\cdots &m_{2r}&-d'_{21}&\cdots &-d'_{2s}&c'_{2}\\\vdots &\vdots &\ddots &\vdots &\vdots &&\vdots &\vdots \\0&0&\cdots &1&-d'_{r1}&\cdots &-d'_{rs}&c'_{r}\\0&0&\cdots &0&0&\cdots &0&0\\\vdots &\vdots &&\vdots &\vdots &\ddots &\vdots &\vdots \\0&0&\cdots &0&0&\cdots &0&0\end{array}}\right]\qquad {\begin{aligned}&1x_{1}+m_{12}x_{2}+\cdots +m_{1r}x_{r}-d'_{11}x_{r+1}-\cdots -d'_{1s}x_{n}=c'_{1}\\&0x_{1}+1x_{2}+\cdots +m_{2r}x_{r}-d'_{21}x_{r+1}-\cdots -d'_{2s}x_{n}=c'_{2}\\&\qquad \vdots \\&0x_{1}+0x_{2}+\cdots +1x_{r}-d'_{r1}x_{r+1}-\cdots -d'_{rs}x_{n}=c'_{r}\\&0x_{1}+0x_{2}+\cdots +0x_{r}+0x_{r+1}+\cdots +0x_{n}=0\\&\qquad \vdots \\&0x_{1}+0x_{2}+\cdots +0x_{r}+0x_{r+1}+\cdots +0x_{n}=0\end{aligned}}}$

従って、任意定数 ${\displaystyle \lambda _{1},\ldots ,\lambda _{s}}$ を用いて >r+1 番目以後の s 個の変数を${\displaystyle x_{r+1}=\lambda _{1},x_{r+2}=\lambda _{2},...,x_{n}=\lambda _{s}}$ と置き、右辺に移項して下から順に値を代入していくことで全ての解を確定できる。

次の連立一次方程式の解を拡大係数行列を用いずにガウスの消去法のアルゴリズムで求めてみる。 式の本数が固定されていること、式の入れ替えもまた一つの操作であることに注意すべきである。

${\displaystyle {\begin{aligned}&2x_{1}&+&4x_{2}&+&2x_{3}&+&2x_{4}&&=8\\&4x_{1}&+&10x_{2}&+&3x_{3}&+&3x_{4}&&=17\\&2x_{1}&+&6x_{2}&+&x_{3}&+&x_{4}&&=9\\&3x_{1}&+&7x_{2}&+&x_{3}&+&4x_{4}&&=11\end{aligned}}}$

1. まず前進消去をする。
   1. 1 番目の方程式を 1/2 倍する。

      ${\displaystyle {\begin{aligned}&x_{1}&+&2x_{2}&+&x_{3}&+&x_{4}&&=4\\&4x_{1}&+&10x_{2}&+&3x_{3}&+&3x_{4}&&=17\\&2x_{1}&+&6x_{2}&+&x_{3}&+&x_{4}&&=9\\&3x_{1}&+&7x_{2}&+&x_{3}&+&4x_{4}&&=11\end{aligned}}}$

   2. 2 番目の方程式に 1 番目の方程式の −4 倍を足す。3 番目の方程式に 1 番目の方程式の −2 倍を足す。4 番目の方程式に 1 番目の方程式の −3 倍を足す。

      ${\displaystyle {\begin{aligned}&x_{1}&+&2x_{2}&+&x_{3}&+&x_{4}&&=4\\&&&2x_{2}&-&x_{3}&-&x_{4}&&=1\\&&&2x_{2}&-&x_{3}&-&x_{4}&&=1\\&&&x_{2}&-&2x_{3}&+&x_{4}&&=-1\end{aligned}}}$

   3. 2 番目の方程式を 1/2 倍する。

      ${\displaystyle {\begin{aligned}&x_{1}&+&2x_{2}&+&x_{3}&+&x_{4}&&=4\\&&&x_{2}&-&{\frac {1}{2}}x_{3}&-&{\frac {1}{2}}x_{4}&&={\frac {1}{2}}\\&&&2x_{2}&-&x_{3}&-&x_{4}&&=1\\&&&x_{2}&-&2x_{3}&+&x_{4}&&=-1\end{aligned}}}$

   4. 3 番目の方程式に 2 番目の方程式の -2 倍を足す。4 番目の方程式に 2 番目の方程式の -1 倍を足す。

      ${\displaystyle {\begin{aligned}&x_{1}&+&2x_{2}&+&x_{3}&+&x_{4}&&=4\\&&&x_{2}&-&{\frac {1}{2}}x_{3}&-&{\frac {1}{2}}x_{4}&&={\frac {1}{2}}\\&&&&&&&0&&=0\\&&&&-&{\frac {3}{2}}x_{3}&+&{\frac {3}{2}}x_{4}&&=-{\frac {3}{2}}\end{aligned}}}$

   5. 3 番目の方程式と 4 番目の方程式を入れ替える。

      ${\displaystyle {\begin{aligned}&x_{1}&+&2x_{2}&+&x_{3}&+&x_{4}&&=4\\&&&x_{2}&-&{\frac {1}{2}}x_{3}&-&{\frac {1}{2}}x_{4}&&={\frac {1}{2}}\\&&&&-&{\frac {3}{2}}x_{3}&+&{\frac {3}{2}}x_{4}&&=-{\frac {3}{2}}\\&&&&&&&0&&=0\end{aligned}}}$

2. 次に後退代入をする。
   1. 3 番目の方程式を ${\displaystyle -{\frac {2}{3}}}$ 倍する

      ${\displaystyle {\begin{aligned}&x_{1}&+&2x_{2}&+&x_{3}&+&x_{4}&=4\\&&&x_{2}&-&{\frac {1}{2}}x_{3}&-&{\frac {1}{2}}x_{4}&={\frac {1}{2}}\\&&&&&x_{3}&-&x_{4}&=1\\&&&&&&&0&=0\end{aligned}}}$

   2. ${\displaystyle x_{3}=1+x_{4}}$ を 2 番目の方程式に代入する。

      ${\displaystyle {\begin{aligned}&x_{1}&+&2x_{2}&+&x_{3}&+&x_{4}&=4\\&&&x_{2}&&&-&x_{4}&=1\\&&&&&x_{3}&-&x_{4}&=1\\&&&&&&&0&=0\end{aligned}}}$

   3. ${\displaystyle x_{3}=1+x_{4}}$ と ${\displaystyle x_{2}=1+x_{4}}$ を 1 番目の方程式に代入する。

      ${\displaystyle {\begin{aligned}x_{1}+4x_{4}&=1\\x_{2}-x_{4}&=1\\x_{3}-x_{4}&=1\\0&=0\end{aligned}}}$

そこで、${\displaystyle x_{4}=c}$（"c" は任意定数）とおくと、

${\displaystyle {\begin{aligned}x_{1}&=-4c+1\\x_{2}&=c+1\\x_{3}&=c+1\\x_{4}&=c\end{aligned}}}$

これで解が全て求まった。

一般的なアルゴリズムについては、たとえば(コルテ & フィーゲン 2009, p. 96)を見よ。

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

• コルテ, B.、フィーゲン, J.『組合せ最適化：理論とアルゴリズム』（第2版）シュプリンガー・ジャパン、2009年。ISBN 978-4-431-10021-8。https://books.google.co.jp/books?id=7OfUJPqwyKwC&pg=PA95。 
• Schrijver, Alexander (1998). Theory of Linear and Integral Programming. Wiley-Interscience series in discrete mathematics and optimization. Wiley. ISBN 0-471-98232-6. https://books.google.co.jp/books?id=zEzW5mhppB8C&pg=PA31 
• [1]

• LU分解
• アルゴリズム
• 三角行列
• Bareiss algorithm

• 『ガウスの消去法による連立一次方程式の解き方』 - 高校数学の美しい物語
• Nicholas J. Higham:How Accurate is Gaussian Elimination?, (2023）

表 話 編 歴 線型代数学・行列解析
連立一次方程式	ガウスの消去法 クラメルの公式 ガウス＝ザイデル法 ヤコビ法
ベクトル	線型独立 線型結合 基底 双対基底
ベクトル空間	双対空間 核空間 固有空間 広義固有空間 線型包 行空間 列空間 次元
計量ベクトル空間	ドット積 コーシー＝シュワルツの不等式 直交 正規直交系 正規直交基底 グラム・シュミットの正規直交化法 直交補空間
行列・線型写像	演算・操作 乗法 転置 逆行列 サラスの方法 基本変形 対角化 分解 LU QR コレスキー シューア 特異値 固有値 不変量 行列式 跡 階数 固有値と固有ベクトル 固有多項式 最小多項式 単因子 階数標準形 スミス標準形 ジョルダン標準形 有理標準形 小行列式 クラス 正則 基本 対称 エルミート 正規 直交 回転 ユニタリ 冪零 射影 正定値 ユニモジュラー 置換 区分
行列式	余因子展開 余因子行列 ヴァンデルモンドの行列式 終結式 コーシー・ビネの公式
多重線型代数	外積 外積代数 対称代数 テンソル代数
数値線形代数	基本的な概念 浮動小数点 数値的安定性 疎行列 Z-行列 M行列 条件数 ゲルシュゴリンの定理 クリロフ部分空間 ソフトウェア MATLAB 数値解析ソフトの比較/一覧 ライブラリ Armadillo Basic Linear Algebra Subprograms (BLAS) INTLAB Intel oneAPI Math Kernel Library LAPACK NumPy OpenBLAS 線型代数学ライブラリの比較 反復法・技法 SOR法 共役勾配法 GMRES法 固有値問題の数値解法 ランチョス法 QR法 べき乗法 逆べき乗法 ヤコビ法 (固有値問題) シュトラッセンのアルゴリズム ハウスホルダー変換 ギブンス回転 人物 ジェームズ・H・ウィルキンソン クリーブ・モラー ニコラス・ハイアム ジーン・ゴラブ リチャード・バルガ
行列値関数	行列指数関数 行列の対数 行列の平方根
その他	スカラー ケイリー・ハミルトンの定理 ペロン＝フロベニウスの定理 シューア補行列 シルヴェスターの慣性法則
カテゴリ