ガウスの消去法
出典: フリー百科事典『ウィキペディア（Wikipedia）』
ガウスの消去法（ガウスのしょうきょほう）あるいは掃き出し法（はきだしほう）とは、変数の数と方程式の本数が一致した連立一次方程式（線形方程式系）を解く為の解法である。基本的には、前進消去と後退代入という2つのステップから成り立つ。
[編集] 例
- 次のような線形方程式系の解を求める。
- 2x1 + 4x2 + 2x3 = 8
- 4x1 + 10x2 + 3x3 = 17
- 3x1 + 7x2 + x3 = 11
- まず前進消去をする。
- 1 番目の方程式を 1/2 倍する。
- x1 + 2x2 + x3 = 4
- 4x1 + 10x2 + 3x3 = 17
- 3x1 + 7x2 + x3 = 11
-
- 2 番目の方程式に 1 番目の方程式の -4 倍を足す。3 番目の方程式に 1 番目の方程式の -3 倍を足す。
- x1 + 2x2 + x3 = 4
- 2x2 − x3 = 1
- x2 − 2x3 = − 1
-
- 2 番目の方程式を 1/2 倍する。
- x1 + 2x2 + x3 = 4
- x2 − 2x3 = − 1
-
- 3 番目の方程式に 2 番目の方程式の -1 倍を足す。
- x1 + 2x2 + x3 = 4
- 次に後退代入をする。
- 3 番目の方程式を -2/3 倍する
- x1 + 2x2 + x3 = 4
- x3 = 1
-
- x3 = 1 を 2 番目の方程式に代入する。
- x1 + 2x2 + x3 = 4
- x2 = 1
- x3 = 1
-
- x3 = 1 と x2 = 1 を 1 番目の方程式に代入する。
- x1 = 1
- x2 = 1
- x3 = 1
- これで解が求まった。
[編集] 注意
- 対角成分が 0 になる場合には、枢軸選択（式の交換）を行う必要がある。
- 対角成分が 0 にはならなくても、常に対角成分の下を見て、絶対値が最大の係数をもつ式と入れ替えたほうが、解に混入する丸め誤差が少なくなる。
- 疎行列に対してガウスの消去法のステップを行うと疎性を損なう。
- 前進消去の段階において対角化を目指して、後退代入を行わずに x を直接計算する方法はガウスジョルダンの消去法と呼ぶ。アルゴリズムは単純になるが、計算量は多くなる（変数が多い場合、ほぼ 1.5 倍になる）。
- 計算量（乗算の回数）は、変数の個数を n とすると、ほぼ
になる。
