ガウスの消去法とガウス・ジョルダン法
行階段形、既約行階段形、枢軸、そして 3 つの行基本変形を、具体的な行列で追いかけます。
消去法は線形代数でもっとも役に立つアルゴリズムです。階数、行列式、逆行列、連立一次方程式の解——どれもここから出てきます。土台になるのは 3 つの行基本変形で、いずれも元の方程式系の解集合を変えません。
- 2 行を入れ替える：
R(i) ↔ R(j) - ある行を 0 でないスカラー倍する：
R(i) → k·R(i) - ある行の定数倍を別の行に加える：
R(i) → R(i) + k·R(j)
行階段形
次を満たすとき、行列は行階段形です。
- すべてが 0 の行は下に集まっている；
- 各行の最初の非零成分（枢軸）が、ひとつ上の行の枢軸より厳密に右にある；
- 枢軸より下はすべて 0 である。
| 2 | 1 | −1 |
| 0 | 3 | 2 |
| 0 | 0 | 5 |
既約行階段形
既約形はさらに進んで、すべての枢軸が 1 で、その列で唯一の非零成分になります。重要なのは、どんな行列にも既約行階段形はただ 1 つしかないという点です。変形の順序によって答えが変わることはありません。
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 1 |
アルゴリズムの手順
- 左上から始めます。いまの列で絶対値が最大の成分を探します——これが部分枢軸選択で、丸め誤差を小さく保ちます。
- 列全体が 0 なら、1 列右へ移ってやり直します。
- その行を枢軸の位置へ入れ替えます。
- 枢軸の行を枢軸で割り、枢軸を 1 にします。
- 枢軸の行の定数倍を他のすべての行から引き、その列の残りを 0 にします。
- 1 行下、1 列右へ移り、繰り返します。
手順 5 で枢軸より下の行だけを 0 にすればガウスの消去法（行階段形）、上の行も片づければガウス・ジョルダン法（既約形）になります。
解の読み取り方
- 解がただ 1 つ：係数行列のすべての列に枢軸がある。
- 解が無数にある：枢軸のない列がある——その変数は自由変数です。
- 解なし：
0 0 0 | c（c ≠ 0）という行が現れ、0 = c を主張します。