ガウスの消去法
Gaussian Elimination
初級
公開日: 2026-03-20
1. 概要
ガウスの消去法（Gaussian Elimination）は、連立一次方程式 $A\mathbf{x} = \mathbf{b}$ を解く最も基本的な直接法である。拡大係数行列 $[A|\mathbf{b}]$ に行基本変形を施して上三角行列に変換し（前進消去）、その後、後退代入により解を求める。
C. F. Gauss (1777--1855) にちなんで名付けられたが、同様の手法は紀元前の中国の『九章算術』にも見られる。
2. 前進消去
$n \times n$ の係数行列 $A$ と右辺ベクトル $\mathbf{b}$ から拡大係数行列を構成し、第 $k$ 列（$k = 1, 2, \ldots, n-1$）について、$k$ 行目より下の全ての行から $k$ 行目の定数倍を引いて $a_{ik}$ を消去する。
消去の乗数
第 $k$ ステップにおいて、$i > k$ に対し乗数 $m_{ik}$ を
$$m_{ik} = \frac{a_{ik}^{(k)}}{a_{kk}^{(k)}}$$
と定め、第 $i$ 行から第 $k$ 行の $m_{ik}$ 倍を引く：$a_{ij}^{(k+1)} = a_{ij}^{(k)} - m_{ik}\, a_{kj}^{(k)}$。
図1. 前進消去の過程。各ステップで対角より下の要素を 0 にし、最終的に上三角行列を得る。
3. 後退代入
前進消去により上三角形 $U\mathbf{x} = \mathbf{c}$ が得られたら、最後の行から順に解を求める：
$$x_n = \frac{c_n}{u_{nn}}, \qquad x_k = \frac{1}{u_{kk}}\!\left(c_k - \sum_{j=k+1}^{n} u_{kj}\, x_j\right), \quad k = n{-}1, \ldots, 1$$
4. 計算過程のアニメーション例
具体的な3変数の連立方程式で、前進消去と後退代入の全過程をステップごとに確認する。
$$\left\{\begin{array}{rrrrcr}
\vphantom{\frac{1}{2}}\phantom{-3x_1}\llap{2x_1} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_2}\llap{+x_2} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_3}\llap{-x_3} & = & \vphantom{\frac{1}{2}}\phantom{-11}\llap{8} \\[6pt]
\vphantom{\frac{1}{2}}\phantom{-3x_1}\llap{-3x_1} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_2}\llap{-x_2} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_3}\llap{+2x_3} & = & \vphantom{\frac{1}{2}}\phantom{-11}\llap{-11} \\[6pt]
\vphantom{\frac{1}{2}}\phantom{-3x_1}\llap{-2x_1} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_2}\llap{+x_2} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_3}\llap{+2x_3} & = & \vphantom{\frac{1}{2}}\phantom{-11}\llap{-3}
\end{array}\right.$$
この連立方程式を解く
$$\left\{\begin{array}{rrrrcr}
\vphantom{\frac{1}{2}}\phantom{-3x_1}\llap{2x_1} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_2}\llap{+x_2} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_3}\llap{-x_3} & = & \vphantom{\frac{1}{2}}\phantom{-11}\llap{8} \\[6pt]
\vphantom{\frac{1}{2}}\phantom{-3x_1}\llap{} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_2}\llap{\color{blue}{\frac{1}{2}x_2}} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_3}\llap{\color{blue}{+\frac{1}{2}x_3}} & \color{blue}{=} & \vphantom{\frac{1}{2}}\phantom{-11}\llap{\color{blue}{1}} \\[6pt]
\vphantom{\frac{1}{2}}\phantom{-3x_1}\llap{-2x_1} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_2}\llap{+x_2} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_3}\llap{+2x_3} & = & \vphantom{\frac{1}{2}}\phantom{-11}\llap{-3}
\end{array}\right.$$
1行目の 3/2 倍を2行目に加えて、2行目の1列目を 0 にする
$$\left\{\begin{array}{rrrrcr}
\vphantom{\frac{1}{2}}\phantom{-3x_1}\llap{2x_1} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_2}\llap{+x_2} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_3}\llap{-x_3} & = & \vphantom{\frac{1}{2}}\phantom{-11}\llap{8} \\[6pt]
\vphantom{\frac{1}{2}}\phantom{-3x_1}\llap{} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_2}\llap{\frac{1}{2}x_2} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_3}\llap{+\frac{1}{2}x_3} & = & \vphantom{\frac{1}{2}}\phantom{-11}\llap{1} \\[6pt]
\vphantom{\frac{1}{2}}\phantom{-3x_1}\llap{} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_2}\llap{\color{blue}{2x_2}} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_3}\llap{\color{blue}{+x_3}} & \color{blue}{=} & \vphantom{\frac{1}{2}}\phantom{-11}\llap{\color{blue}{5}}
\end{array}\right.$$
1行目を3行目に加えて、3行目の1列目を 0 にする
$$\left\{\begin{array}{rrrrcr}
\vphantom{\frac{1}{2}}\phantom{-3x_1}\llap{2x_1} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_2}\llap{+x_2} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_3}\llap{-x_3} & = & \vphantom{\frac{1}{2}}\phantom{-11}\llap{8} \\[6pt]
\vphantom{\frac{1}{2}}\phantom{-3x_1}\llap{} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_2}\llap{\frac{1}{2}x_2} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_3}\llap{+\frac{1}{2}x_3} & = & \vphantom{\frac{1}{2}}\phantom{-11}\llap{1} \\[6pt]
\vphantom{\frac{1}{2}}\phantom{-3x_1}\llap{} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_2}\llap{} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_3}\llap{\color{blue}{-x_3}} & \color{blue}{=} & \vphantom{\frac{1}{2}}\phantom{-11}\llap{\color{blue}{1}}
\end{array}\right.$$
2行目の4倍を3行目から引いて、3行目の2列目を 0 にする
$$\left\{\begin{array}{rrrrcr}
\vphantom{\frac{1}{2}}\phantom{-3x_1}\llap{2x_1} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_2}\llap{+x_2} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_3}\llap{-x_3} & = & \vphantom{\frac{1}{2}}\phantom{-11}\llap{8} \\[6pt]
\vphantom{\frac{1}{2}}\phantom{-3x_1}\llap{} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_2}\llap{\frac{1}{2}x_2} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_3}\llap{+\frac{1}{2}x_3} & = & \vphantom{\frac{1}{2}}\phantom{-11}\llap{1} \\[6pt]
\vphantom{\frac{1}{2}}\phantom{-3x_1}\llap{} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_2}\llap{} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_3}\llap{-x_3} & = & \vphantom{\frac{1}{2}}\phantom{-11}\llap{1}
\end{array}\right.$$
前進消去が完了。対角線の下がすべて 0 になった
$$\left\{\begin{array}{rrrrcr}
\vphantom{\frac{1}{2}}\phantom{-3x_1}\llap{2x_1} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_2}\llap{+x_2} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_3}\llap{-x_3} & = & \vphantom{\frac{1}{2}}\phantom{-11}\llap{8} \\[6pt]
\vphantom{\frac{1}{2}}\phantom{-3x_1}\llap{} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_2}\llap{\frac{1}{2}x_2} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_3}\llap{+\frac{1}{2}x_3} & = & \vphantom{\frac{1}{2}}\phantom{-11}\llap{1} \\[6pt]
\vphantom{\frac{1}{2}}\phantom{-3x_1}\llap{} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_2}\llap{} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_3}\llap{\color{green}{-x_3}} & \color{green}{=} & \vphantom{\frac{1}{2}}\phantom{-11}\llap{\color{green}{1}}
\end{array}\right.$$
3行目の式から直接 3番目の未知数が求まる
$-x_3 = 1 \;\Rightarrow\; x_3 = -1$
$$\left\{\begin{array}{rrrrcr}
\vphantom{\frac{1}{2}}\phantom{-3x_1}\llap{2x_1} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_2}\llap{+x_2} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_3}\llap{\color{orange}{+1}} & = & \vphantom{\frac{1}{2}}\phantom{-11}\llap{8} \\[6pt]
\vphantom{\frac{1}{2}}\phantom{-3x_1}\llap{} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_2}\llap{\color{green}{\frac{1}{2}x_2}} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_3}\llap{\color{orange}{-\frac{1}{2}}} & \color{green}{=} & \vphantom{\frac{1}{2}}\phantom{-11}\llap{\color{green}{1}} \\[6pt]
\vphantom{\frac{1}{2}}\phantom{-3x_1}\llap{} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_2}\llap{} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_3}\llap{\color{orange}{1}} & = & \vphantom{\frac{1}{2}}\phantom{-11}\llap{1}
\end{array}\right.$$
求めた値を2行目に代入して 2番目の未知数を求める
$\dfrac{1}{2}x_2 \color{orange}{- \dfrac{1}{2}} = 1 \;\Rightarrow\; x_2 = 3$
$$\left\{\begin{array}{rrrrcr}
\vphantom{\frac{1}{2}}\phantom{-3x_1}\llap{\color{green}{2x_1}} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_2}\llap{\color{orange}{+3}} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_3}\llap{\color{orange}{+1}} & \color{green}{=} & \vphantom{\frac{1}{2}}\phantom{-11}\llap{\color{green}{8}} \\[6pt]
\vphantom{\frac{1}{2}}\phantom{-3x_1}\llap{} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_2}\llap{\color{orange}{\frac{3}{2}}} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_3}\llap{\color{orange}{-\frac{1}{2}}} & = & \vphantom{\frac{1}{2}}\phantom{-11}\llap{1} \\[6pt]
\vphantom{\frac{1}{2}}\phantom{-3x_1}\llap{} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_2}\llap{} & \vphantom{\frac{1}{2}}\phantom{+\frac{1}{2}x_3}\llap{\color{orange}{1}} & = & \vphantom{\frac{1}{2}}\phantom{-11}\llap{1}
\end{array}\right.$$
求めた値を1行目に代入して 1番目の未知数を求める
$2x_1 + \color{orange}{3} + \color{orange}{1} = 8 \;\Rightarrow\; x_1 = 2$
$x_1 = 2, \quad x_2 = 3, \quad x_3 = -1$
1 / 9
拡大係数行列による計算例
上記のアニメーションと同じ連立方程式を、拡大係数行列の行操作として表記する。
前進消去:
$$\left[\begin{array}{ccc|c} 2 & 1 & -1 & 8 \\ -3 & -1 & 2 & -11 \\ -2 & 1 & 2 & -3 \end{array}\right]$$
$R_2 \leftarrow R_2 + \frac{3}{2}R_1$, $R_3 \leftarrow R_3 + R_1$:
$$\left[\begin{array}{ccc|c} 2 & 1 & -1 & 8 \\ 0 & \frac{1}{2} & \frac{1}{2} & 1 \\ 0 & 2 & 1 & 5 \end{array}\right]$$
$R_3 \leftarrow R_3 - 4R_2$:
$$\left[\begin{array}{ccc|c} 2 & 1 & -1 & 8 \\ 0 & \frac{1}{2} & \frac{1}{2} & 1 \\ 0 & 0 & -1 & 1 \end{array}\right]$$
後退代入: 3行目から $x_3 = -1$、2行目に代入して $x_2 = 3$、1行目に代入して $x_1 = 2$。
5. ピボット選択
前進消去の第 $k$ ステップにおいて、ピボット $a_{kk}^{(k)}$ がゼロまたはゼロに近い場合、ゼロ除算や大きな丸め誤差が生じる。これを避けるためにピボット選択を行う。
5.1 部分ピボット選択（Partial Pivoting）
第 $k$ 列の $k$ 行目以下で絶対値が最大の要素を選び、行の交換を行う。行の交換は連立方程式の式の順番を入れ替えるだけなので、変数の対応関係は変わらない。実用上はほとんどの場合これで十分であり、LAPACKなどの標準的な数値計算ライブラリでも採用されている。
図2. 部分ピボット選択の概念図。第 $k$ 列で絶対値最大の要素がある行とピボット行を交換する。
5.2 完全ピボット選択（Complete Pivoting）
完全ピボット選択では、第 $k$ ステップにおいて $k$ 行目以下かつ $k$ 列目から右の全要素から絶対値最大のものを探し、行と列の両方を交換する。
図3. 完全ピボット選択の概念図。探索範囲（黄色）の全要素から絶対値最大を選び、行交換（赤）と列交換（青）の両方を行う。
列の交換は変数の順序の入れ替えに相当する。例えば第2列と第3列を交換すると、$x_2$ と $x_3$ の役割が入れ替わる。したがって、全ての消去が終わった後に列の交換履歴を逆順にたどって、変数の順序を元に戻す必要がある。
部分 vs 完全：完全ピボット選択は数値的安定性がわずかに優れるが、最大要素の探索に $O(n^2)$ の追加コストがかかる。部分ピボット選択の探索コストは $O(n)$ であり、実用上は部分ピボット選択で十分な場合がほとんどである。
5.3 有理数演算でのピボット選択
上記のピボット選択戦略は浮動小数点演算を前提としている。有理数（多倍長整数による分数）で厳密にガウスの消去法を実行する場合、丸め誤差は発生しないが、代わりに中間値の膨張（coefficient swell）が問題となる。消去の過程で分子・分母の桁数が爆発的に増大し、計算が極端に遅くなることがある。
この問題を軽減するために、浮動小数点とは逆に、絶対値が最小の（ゼロでない）要素をピボットに選ぶ戦略が有効である。より正確には、有理数 $p/q$（既約分数）の高さ $H(p/q) = \max(|p|, |q|)$ が最小の要素をピボットに選ぶことで、消去の乗数の分子・分母が小さくなり、中間値の膨張を抑えられる。
補足：有理数のガウスの消去法では、ピボット選択以外にも、各ステップで中間値を既約分数に約分する、あるいはBareissのアルゴリズム（分数を使わず整数のまま消去する手法）を用いるなど、中間値膨張を避ける工夫がある。
6. 計算量
$n$ 元連立一次方程式に対するガウスの消去法の計算量は次の通りである。
- 前進消去: $\frac{2}{3}n^3 + O(n^2)$ 回の浮動小数点演算
- 後退代入: $n^2 + O(n)$ 回の浮動小数点演算
- 全体: $O(n^3)$
7. LU分解との関係
ガウスの消去法の前進消去は、行列 $A$ を下三角行列 $L$ と上三角行列 $U$ の積に分解する操作と等価である：
$$A = LU$$
消去の乗数 $m_{ik}$ が $L$ の対角より下の要素となり、消去後の上三角行列が $U$ である。一度 $LU$ 分解を行えば、異なる右辺 $\mathbf{b}$ に対して $O(n^2)$ で解が求まるため、同じ係数行列で複数の右辺を解く場合に効率的である。
8. よくある質問
Q1. ガウスの消去法とは何ですか？
連立一次方程式を前進消去と後退代入の2段階で解く直接法である。計算量は $O(n^3)$ であり、数値線形代数の最も基本的なアルゴリズムである。
Q2. ピボット選択はなぜ必要ですか？
ピボット要素が 0 またはゼロに近いとゼロ除算や大きな丸め誤差が発生する。部分ピボット選択により列内の絶対値最大の要素をピボットに選ぶことで数値的安定性が向上する。
Q3. ガウスの消去法とLU分解の関係は？
前進消去の過程は行列 $A$ を $L$（下三角）と $U$（上三角）に分解する操作と等価である。消去の乗数が $L$ の要素、消去後の行列が $U$ となる。
9. 参考資料
- Wikipedia「ガウスの消去法」（日本語版）
- Wikipedia「Gaussian elimination」（英語版）
- G. H. Golub & C. F. Van Loan, Matrix Computations, 4th ed., Johns Hopkins, 2013.
- L. N. Trefethen & D. Bau III, Numerical Linear Algebra, SIAM, 1997.