ガウス・ジョルダン消去法

Basis
最終更新: タグ: Linear Algebra

前提知識

五つの方程式と五つの未知数があるとしよう。当てずっぽうを試みることもできるが、唯一解を見つけるか、無数の解をすべて記述するか、解なしと判定するかを確実に行う系統的な手順を使うこともできる。ガウス・ジョルダン消去法（Gauss-Jordan elimination）がその手順であり、方程式と未知数がどれだけあっても機能する。

基本行変換

鍵となる洞察は、行列の行に対するある種の操作が対応する線型方程式系の解集合を変えないということだ。それが次の三つの基本行変換（elementary row operations）だ：

  1. 行交換（row swap）：二つの行を入れ替える、Ri↔RjR_i \leftrightarrow R_j と書く。
  2. 行のスケーリング（row scaling）：ある行のすべての成分をゼロでないスカラー c≠0c \ne 0 で掛ける、Ri←c⋅RiR_i \leftarrow c \cdot R_i と書く。
  3. 行の置換（row replacement）：ある行に別の行のスカラー倍を加える、Ri←Ri+c⋅RjR_i \leftarrow R_i + c \cdot R_j と書く。

各操作は可逆（その逆操作も同じ種類の基本行変換）なので、これらの操作の任意の列を適用しても等価な系——全く同じ解を持つ系——が得られる。

行階段形

基本行変換を適用した後、特定の形を目指す。次の条件を満たす行列が行階段形（row echelon form、REF）だ：

  • ゼロ行（すべての成分がゼロの行）はすべて下に置かれる。
  • 各非ゼロ行で、最初の非ゼロ成分——ピボット（pivot）または先頭成分（leading entry）と呼ぶ——は一つ上の行のピボットより厳密に右にある。

ピボットを左上から右下にたどると、行列は階段状の形になる。

行簡約階段形

行列が行簡約階段形（reduced row echelon form、RREF）にあるとは、REF の条件をすべて満たし、さらに次の条件を満たすことだ：

  • すべてのピボットがちょうど 11 に等しい。
  • ピボットの列の他のすべての成分が 00 だ（ピボットの下だけでなく上も）。

RREF は「最もクリーンな」形だ：これ以上算術をしなくても線型方程式系の解を直接読み取れる。

基本定理として、すべての行列は一意な RREF を持つ。どの行変換の列を選んでも（アルゴリズムに従う限り）、常に同じ行簡約階段形に到達する。

消去アルゴリズム

アルゴリズムは二つの掃引で進む。

前向き掃引（各ピボットの下を消去）：

  1. まだ処理していない行に非ゼロ成分を持つ最も左の列を見つける。
  2. 必要であれば行を交換して、その列の上に（未処理の行の中で）非ゼロ成分を持ってくる。
  3. 現在の行をスケーリングして先頭成分を 11 にする。
  4. このピボット行の適切なスカラー倍を、下のすべての行に加えてピボットの下の成分をすべて 00 にする。
  5. 次の行に移り、ステップ 1 から繰り返す。

後ろ向き掃引（各ピボットの上を消去）： 6. 最下のピボットから上向きに作業し、各ピボット行のスカラー倍を、上のすべての行に加えてピボットの上の成分をすべて 00 にする。

両方の掃引が終わると、すべてのピボットが 11 で、各ピボット列のピボット以外のすべての成分が 00 になる——RREF に到達した。

計算例

次の方程式系を解く：

{x1+2x2−x3=12x1+3x2+x3=4−x1+x2+2x3=3\begin{cases} x_1 + 2x_2 - x_3 = 1 \\ 2x_1 + 3x_2 + x_3 = 4 \\ -x_1 + x_2 + 2x_3 = 3 \end{cases}

拡大行列 [A∣b][A \mid b] を書き、簡約する：

(12−112314−1123)\begin{pmatrix} 1 & 2 & -1 & 1 \\ 2 & 3 & 1 & 4 \\ -1 & 1 & 2 & 3 \end{pmatrix}

R2←R2−2R1R_2 \leftarrow R_2 - 2R_1、次に R3←R3+R1R_3 \leftarrow R_3 + R_1：

(12−110−1320314)\begin{pmatrix} 1 & 2 & -1 & 1 \\ 0 & -1 & 3 & 2 \\ 0 & 3 & 1 & 4 \end{pmatrix}

R2←−1⋅R2R_2 \leftarrow -1 \cdot R_2（ピボットを 11 にするためスケーリング）：

(12−1101−3−20314)\begin{pmatrix} 1 & 2 & -1 & 1 \\ 0 & 1 & -3 & -2 \\ 0 & 3 & 1 & 4 \end{pmatrix}

R3←R3−3R2R_3 \leftarrow R_3 - 3R_2：

(12−1101−3−2001010)\begin{pmatrix} 1 & 2 & -1 & 1 \\ 0 & 1 & -3 & -2 \\ 0 & 0 & 10 & 10 \end{pmatrix}

R3←110R3R_3 \leftarrow \tfrac{1}{10} R_3：

(12−1101−3−20011)\begin{pmatrix} 1 & 2 & -1 & 1 \\ 0 & 1 & -3 & -2 \\ 0 & 0 & 1 & 1 \end{pmatrix}

後ろ向き掃引へ。R2←R2+3R3R_2 \leftarrow R_2 + 3R_3、次に R1←R1+R3R_1 \leftarrow R_1 + R_3：

(120201010011)\begin{pmatrix} 1 & 2 & 0 & 2 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \end{pmatrix}

R1←R1−2R2R_1 \leftarrow R_1 - 2R_2：

(100001010011)\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \end{pmatrix}

これが RREF だ。読み取ると：x1=0x_1 = 0、x2=1x_2 = 1、x3=1x_3 = 1。方程式系は唯一解を持つ。

ピボット列と自由変数

行列 AA の RREF において、ピボットを含む列をピボット列（pivot column）、それ以外のすべての列を自由列（free column）という。自由列に対応する変数を自由変数（free variables）と呼ぶ——それらは FF の任意の値を取れ、それぞれの選択が有効な解を与える。ピボット列に対応する変数はそれらによって後退代入で決まる。

自由変数がない場合、解（存在すれば）は一意だ。自由変数が少なくとも一つある場合、解は無数に存在する。この分類は線型方程式系でさらに探る。

まとめ

  • 基本行変換（交換、スケーリング、置換）は線型方程式系の解集合を保存する。
  • 行階段形（REF）はピボットの階段を持つ；行簡約階段形（RREF）はさらにすべてのピボットを 11 に正規化し、ピボット列の他のすべての成分を消去する。
  • すべての行列は一意な RREF を持ち、使う行変換の列に依存しない。
  • アルゴリズムは前向き掃引（ピボットの下を消去）と後ろ向き掃引（ピボットの上を消去）からなる。
  • ピボット列は確定した変数に対応し；自由列は解集合をパラメータ化する自由変数に対応する。