ガウスの消去法

各列でどの行をピボットにするか選び、消去が進む様子を見てみましょう。二つ目のプリセットでは、この選択によって答えが変わります。非常に小さな数をピボットに選ぶと、x は 1 ではなく 0 になってしまうのです。

三つの行基本変形	$\begin{gathered}R_i\leftrightarrow R_j,\qquad R_i\to kR_i\ (k\neq0)\\R_i\to R_i+kR_j\end{gathered}$
解がただ一つに定まる条件	$\operatorname{rank}A=\operatorname{rank}[A\,\|\,b]=n$

計算例 — ガウスの消去法

行列式	−1
残差	8.8818 × 10⁻¹⁶

ページを開いたときに計算機が表示する値です。上の入力を変えると再計算されます。

インタラクティブシミュレーションを読み込んでいます...

レッスン

理論 — ガウスの消去法849語

消去法は、連立方程式を同値な三角方程式系に変換する手法です。こうしてしまえば、あとは下から順に解を読み取っていくだけで済みます。この手法の要点は、「解を求められる」こと自体にはありません。解を出すだけなら他にもやり方はあります。最大の焦点はその計算コストなのです。コンピュータに実際にどの計算を走らせるかを最終的に決めるのは、他でもないこのコストだからです。

各記号の意味

n: 未知数の個数。計算コストを左右する唯一の変数でもあります。
pivot: 行を割るために使われる係数。アルゴリズムがその処理順序をあらかじめ固定してしまうことで、途中の分岐判断が一切不要になります。しかし、その場所にどの数値を配置するかが、浮動小数点演算による計算の崩壊を防ぐ生命線となります。

前提: 利用できるような規則的な構造を持たない、密な連立方程式です。もし対象が疎行列や帯行列、対称行列であれば、計算の負担はずっと軽くなります。個々の問題にいかに適した特化型の解法を選ぶか。それこそが数値線形代数という分野の大部分を占めています。
成り立たない場合: 計算コストは3乗のオーダーです。この3乗という性質こそが、巨大な壁として立ちはだかります。n 個の未知数を消去するには、およそ n³/3 回の掛け算と、同数の足し算をこなさなければなりません。実際に n = 100 の系で消去法を走らせて数えてみると、概算値 333,333 に対して、現実の掛け算は 333,300 回になります。この指数が意味するのは、規模拡大に対する容赦のないペナルティです。未知数が2倍になれば、必要な作業はきっちり8倍に膨れ上がります。100個の未知数で 333,300 回の掛け算が必要なら、200個では 2,666,600 回になるということです。千個の未知数を一秒で片付けるコンピュータがあったとしましょう。そのマシンでも二千個には八秒かかり、二万個ともなればおよそ二時間十五分も待たされることになります。これが壁の正体です。だからこそ、数値線形代数の世界における真の関心事は、密な連立方程式を「どう解くか」ではなく、「いかにして密な系を避けるか」に尽きるのです。

全プロセスの詳細解説

2x + y − z = 8の解法と精度のコスト 7 ステップ
2x + y − z = 8, −3x − y + 2z = −11, −2x + y + 2z = −3 を解き、消去法によって精度がどの程度失われたかを確認してください。

この問題をツールで開く
1. これを拡大係数行列として書き出します。文字は何も役割を果たさないため取り除き、列だけを残します。
  
  $\begin{bmatrix} 2 & 1 & -1 & 8 \\ -3 & -1 & 2 & -11 \\ -2 & 1 & 2 & -3 \end{bmatrix}$
2. 第一列の中で最も絶対値が大きい二行目の −3 をピボットに選び、上の行と入れ替えます。行を入れ替えるたびに行列式の符号が反転するため、その回数を数えておいてください。
  
  $R_1 \leftrightarrow R_2 \quad (|-3| > |2|)$
3. ピボットのある行を定数倍して引くことで、第一列の残りの要素を消去します。
  
  $R_2 \to R_2 - \tfrac{2}{-3}R_1, \qquad R_3 \to R_3 - \tfrac{-2}{-3}R_1$
4. 第二列でも同じ操作を繰り返し、一番下の行を確認します。そこには一つの未知数とその値が示されています。
  
  $R_2 \leftrightarrow R_3 \quad (\tfrac{5}{3} > \tfrac{1}{3}) \;\Rightarrow\; \tfrac{1}{5}z = -\tfrac{1}{5}$
5. 下から上へと後退代入を行います。一番下の行から z が求まり、次に真ん中の行から y が、そして一番上の行から x が求まります。
  
  $z = -1, \qquad y = 3, \qquad x = 2$
6. ピボットをすべて掛け合わせ、二回の行の入れ替えに応じた符号を適用して行列式を求めます。そして、簡約化された方程式ではなく、元の方程式に代入して答えを確認してください。
  
  $\det = (-3)\left(\tfrac{5}{3}\right)\left(\tfrac{1}{5}\right)(-1)^2 = -1$
7. 残差はおよそ 10⁻¹⁶ となり、ゼロではありません。これは計算機がどうしても避けられない丸め誤差の大きさであり、それをそのまま報告するのが誠実な姿勢というものです。完全な正確さを主張する答えは、整数演算によるものか、あるいは単に誤差から目を背けているかのどちらかです。ピボット選択をオフにして先頭の係数を 10⁻¹⁷ に変更すると、同じ残差が 1 になります。これは先ほどと同じ警告が、今度は叫び声を上げている状態なのです。
  
  $\max_i |A_i x - b_i| \approx 9 \times 10^{-16}$
解答

x = 2, y = 3, z = −1, 行列式 −1。 約 10⁻¹⁶ という残差は、浮動小数点演算の限界まで計算が正確に行われたことを示しています。スケールの悪い連立方程式でピボット選択をオフにした場合、答えが間違っていることを教えてくれるのは、まさにこの数字なのです。
行列式 0 が二度現れ、それぞれ別のことを意味する 7 ステップ
このプリセットには解がなく、次のプリセットには解が無数にありますが、どちらも行列式は 0 と表示されます。実際に両者を分けているものは何かを求め、右辺を変えることで何が買えるのかを判断してください。

この問題をツールで開く
解答を表示
1. 部分ピボット選択は、第一列で絶対値が最大の係数を探します。最下行の 3 が見つかるため、最初の操作は行の入れ替えになります。
  
  $\begin{bmatrix} 1 & 1 & 1 & 3 \\ 2 & 2 & 2 & 7 \\ 3 & 1 & 2 & 5 \end{bmatrix} \xrightarrow{\;R_1 \leftrightarrow R_3\;} \begin{bmatrix} 3 & 1 & 2 & 5 \\ 2 & 2 & 2 & 7 \\ 1 & 1 & 1 & 3 \end{bmatrix} \qquad (|3| > |2| > |1|)$
2. 列を消去します。新しい第一行の ⅔ を第二行から、⅓ を第三行から引きます。
  
  $R_2 \to R_2 - \tfrac{2}{3}R_1, \quad R_3 \to R_3 - \tfrac{1}{3}R_1: \qquad \begin{bmatrix} 3 & 1 & 2 & 5 \\ 0 & \tfrac{4}{3} & \tfrac{2}{3} & \tfrac{11}{3} \\ 0 & \tfrac{2}{3} & \tfrac{1}{3} & \tfrac{4}{3} \end{bmatrix}$
3. 第二列では 4/3 がすでに 2/3 の上にあるので、入れ替えは不要です。第三行から第二行の半分を引きます。
  
  $R_3 \to R_3 - \tfrac{1}{2}R_2: \qquad \begin{bmatrix} 3 & 1 & 2 & 5 \\ 0 & \tfrac{4}{3} & \tfrac{2}{3} & \tfrac{11}{3} \\ 0 & 0 & 0 & -\tfrac{1}{2} \end{bmatrix}$
4. 第三行は左辺が空になり、右辺に −½ が残りました。これは 0 = −½ と読めます。置かれたピボットは 3 と 4/3 の二つだけで、三つの未知数には三つ必要です。ピボットが欠けると積は 0 になります。
  
  $\text{pivots } 3,\ \tfrac{4}{3} \ \text{— two, not three} \;\Longrightarrow\; \det A = 0, \qquad \text{last row: } 0 = -\tfrac{1}{2}$
5. 行列式が隠しているのは階数です。係数行列の独立な行は 2 本。拡大係数行列は 3 本です。残った −½ は、何をもってしても消せない行だからです。階数 2 と階数 3 の食い違いこそが「解なし」の意味です。
  
  $\operatorname{rank} A = 2 \;<\; \operatorname{rank}[A\,|\,b] = 3 \;\Longrightarrow\; \text{no solution}$
6. 同じ式が3つ のプリセットは同じ計算をして、別のことを言います。どの行も第一行の定数倍なので、両方の階数が 1 になり、行列式はまた 0 です。解集合には 3 − 1 = 2 本の自由な方向があり、それは平面 x + y + z = 3 の全体です。ツールは「無数にある」とは言いますが、何方向に無数なのかは言いません。
  
  $\text{Infinitely many: } \operatorname{rank} A = \operatorname{rank}[A\,|\,b] = 1, \quad \det A = 0, \quad \dim = 3 - 1 = 2 \quad (x+y+z=3)$
7. 数を一つ変えて、どの量が動くかを見ましょう。第二行の右辺の 7 を 6 にします。係数行列は手つかずなので行列式は微動だにしませんが、拡大係数行列の階数は 2 に落ち、答えは「解なし」から解の直線へと変わります。
  
  $b_2 = 7 \to 6: \quad \operatorname{rank}[A\,|\,b] = 2 = \operatorname{rank} A \;\Longrightarrow\; \dim = 3 - 2 = 1$
解答

行列式が報告しているのは、係数行列にピボットが揃っているかどうかだけです。右辺を見ることは一度もありません。だから二つのプリセットを区別できないのであり、二つの階数にはそれができます。食い違えば解なし、一致すれば解集合の次元は 3 − 階数です。行列式がいったん 0 になれば、どんな右辺を持ってきても一つの答えは買えません。得られるのは解なしか、解の一族かのどちらかで、b が決めるのはその二択だけです。残差のカードが消えるのは、それが存在する理由と同じ理由によります。残差には、方程式に戻して確かめる解が要るからです。

$\dim = n - \operatorname{rank} A \ \text{ when } \operatorname{rank}[A|b] = \operatorname{rank} A; \qquad \det A = 0 \;\Longrightarrow\; \text{no } b \ \text{gives exactly one}$
三つの方程式を手計算で解く 5 ステップ
連立方程式 x + y + z = 6, 2x − y + z = 3, x + 2y − z = 2 を解きましょう。

この問題をツールで開く
解答を表示
1. 第二行から第一行の2倍を引き、x を消去します。
  
  $R_2\to R_2-2R_1:\quad-3y-z=-9$
2. 第三行から第一行を引き、x を消去します。
  
  $R_3\to R_3-R_1:\quad y-2z=-4$
3. 第三行に、新しい第二行の1/3を加えて y を消去します。残る未知数は z だけです。
  
  $\begin{gathered}R_3\to R_3+\tfrac13R_2\\-\tfrac73z=-7\ \Rightarrow\ z=3\end{gathered}$
4. 後退代入で求めましょう。z の値を第二行に代入すると y が求まり、y と z の値を第一行に代入すると x が求まります。
  
  $y=2,\qquad x=6-2-3=1$
5. 最後に使った式以外の二つの式に代入して、確かめましょう。
  
  $2-2+3=3,\qquad1+4-3=2\ \checkmark$
解答

x = 1, y = 2, z = 3。行列式の値が7なので、解はこれだけです。

$x=1,\quad y=2,\quad z=3$
無数の解を文字で表す 4 ステップ
連立方程式 x + y + z = 3, x − y + z = 1, 2x + 2z = 4 を解きましょう。
解答を表示
1. 第二行から第一行を引くと、y = 1 が得られます。
  
  $R_2\to R_2-R_1:\quad-2y=-2\ \Rightarrow\ y=1$
2. 第三行から第一行の2倍を引くと、また同じ式が得られます。第三行から新たな条件は得られません。
  
  $R_3\to R_3-2R_1:\quad-2y=-2$
3. 未知数は三つ、独立な式は二つで、矛盾もありません。未知数の一つは自由に値を選べます。
  
  $\operatorname{rank}A=\operatorname{rank}[A\,|\,b]=2<3$
4. 任意の数 t を使って z = t とおきましょう。第一行から x が求まります。
  
  $z=t:\quad x=3-1-t=2-t$
解答

任意の t に対して、(x, y, z) = (2 − t, 1, t)。t = 0 なら (2, 1, 0)、t = 2 なら (0, 1, 2) となり、どちらも三つの式をすべて満たします。

$(x,y,z)=(2-t,\ 1,\ t),\quad t\in\mathbb{R}$

補充問題（答えのみ）

連立方程式 x + y + z = 2, y + z = 1, z = −1 を解きましょう。

答えを表示

z = −1, y = 2, x = 1。すでに三角形の形に整理されているので、後退代入だけで解けます。

$z=-1,\quad y=2,\quad x=1$
連立方程式 x + 2y + z = 4, 2x + y − z = −1, x − y + 2z = 7 を解きましょう。

答えを表示

x = 1, y = 0, z = 3。

$x=1,\quad y=0,\quad z=3$
連立方程式 x + y + z = 1, x + 2y + 3z = 2, 2x + 3y + 4z = 5 に解がないことを示しましょう。

答えを表示

R₃ − R₁ − R₂ を計算すると、左辺は0、右辺は2になります。0 = 2 は成り立たないので、解はありません。

$R_3-R_1-R_2:\quad0=2$

迷いを排除する、同じ2つの操作の順序

方程式が二つの場合、必要な操作は一つだけでした。ある行の定数倍を別の行から引くという操作です。方程式が三つになると、これにもう一つの操作が加わります。ステップのリストにはその両方が記されています。ピボットに使える数を配置するための「入れ替え」と、「消去」です。順序は決まっています。一列目を消去し、次に二列目を消去します。あとは一番下の行から答えを読み取り、上に向かって解を求めていくだけです。この通りに進めれば、どの方程式から処理すべきか知恵を絞る必要はありません。それがパズルと定まった手順の違いであり、規模が大きくなっても通用する理由です。未知数が千個になっても同じやり方が通用します。名前が付けられてから六十年が経過した現在でも、世界中のあらゆる工学系ソフトウェアがこのルーチンを実行し続けているのです。

行列式はピボットの積

消去法を進めながらピボットに注目し、それらをすべて掛け合わせてください。そして、行の入れ替えを行った回数だけ符号を反転させます。それが行列式であり、方程式を解く作業の中から自然に導き出されます。行列式といえば余因子展開から学ぶ人が多いですが、実際には誰もその方法で計算しない理由を知っておく価値はあります。消去法の計算量が n³ であるのに対し、余因子展開にはおよそ n! もの操作が必要です。20 × 20 の行列であれば、8,000 に対しておよそ 2 × 10¹⁸ になります。この 10¹⁴ 倍という差が、計算機にどちらを実行させるべきかを決定づけています。誰もが最初に教わる公式は、機械が決して使わない公式なのです。

手順の中にある一つの選択が、答えを変える

ピボット選択オフを押してみてください。先頭の係数は10⁻¹⁷です。アルゴリズムは忠実にこの値で割り算を行いますが、本当の答えが1であるにもかかわらず、xは0として返ってきます。どこかが壊れているわけでも、ルールに違反したわけでもありません。小さな数で割るという操作は、すでに存在している丸め誤差を何倍にも増幅させます。後退代入で一番上までさかのぼる頃には、その誤差が本来の答えを完全に飲み込んでしまっているのです。これはなだらかな坂ではなく、切り立った崖です。係数を徐々に小さくしていくと、10⁻¹²ではまだ正しい数字が四桁得られ、10⁻¹⁵では三桁になります。しかし、10⁻¹⁶は2.22を返し、10⁻¹⁷は0を返します。この崖の縁は「機械イプシロン」、すなわち倍精度浮動小数点数において1とその次に表現できる数との間隔に位置しています。チェックボックスをオンにすると、アルゴリズムは代わりに利用可能な最も大きな数で割るようになり、これらのケースはすべて正確に解けるようになります。だからこそ、このページには残差カードが用意されています。残差カードは答えを元の方程式に再び代入してくれます。そしてこれこそが、本当に正しい答えと、ただ自信満々なだけの答えを見分ける唯一の方法なのです。

学習の道すじ

xについて解く：マイナス記号からの積み上げ

参考文献 (1)

Two centuries of the method being reinvented and misattributed, including how Gauss's name came to be on it: J. F. Grcar, "How ordinary elimination became Gaussian elimination." Historia Mathematica 38:2 (2011), 163–218.

7 Raven Room チーム · 公表された資料と照合しています。訂正のご指摘を歓迎します。