Gaussian Elimination on Matrices / 行列を使ったガウスの消去法

Preliminaries / 前置き

ガウスの消去法はとってもシンプルなので、使えないという人は殆どいないと思う。ただ、特に、勉強を始めたばかりの人から、ガウスの消去法を行列式で解く場合、やり方は覚えたけれど良く分からないという声を聞くことがある。そこで、ここでは、まず、連立方程式とマトリクスの基本を振り返ってから、ガウスの消去法に結び付けたいと思う。

連立方程式から基本のマトリクスへ

連立方程式はマトリクスを使うと簡単に解けるというのは高校数学でも散々やってきたと思う。（コンピュータもmatricesを使った方が演算速度が速いので、実際よく使われている。また、PythonやMATLABの演習でloop処理を使い過ぎている人をたまに見かける。もちろん、loopが必要なケースもあるけれど、場合によってはmatricesでの処理にすることで高速化できるので、こういう点からも、マトリクスには慣れましょう。）

例えば、

$ \left\{\begin{array}{l}2x + y -3z = -2\\x -4y +2z = 14\\-x +3y +4z = 5\end{array}\right. $　　　　　　　　・・・ (eq. 1)

これを連立方程式で解けって言われたら、2番目の式を入れ替えて、 $x = 15 + 5y -2z$。これを定数倍して、その他の式に足す（代入）。なんでこんな簡単な例を持ち出したかというと、この 3 step を行列に適応したものが、マトリクスの基本形そのものだから。

行の入れ替え

$n$次正方行列について、$i$行目と$j$行目を入れ替えるための基本マトリクス $M$ は以下の通り。

e.g.　　 $ M_{3}(2,3) A = \left( \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \\ \end{array} \right) \left( \begin{array}{ccc} a & b & c \\ d & e & f \\ g & h & i \\ \end{array} \right) = \left( \begin{array}{ccc} a & b & c \\ g & h & i \\ d & e & f \\ \end{array} \right) $

行の定数倍

$n$次正方行列について、$i$行目の全ての成分を$k$倍するための基本マトリクス$M$は以下の通り。ただし、$k \neq 0$。

e.g.　　 $ M_{3}(3;4) A = \left( \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 4 \\ \end{array} \right) \left( \begin{array}{ccc} a & b & c \\ d & e & f \\ g & h & i \\ \end{array} \right) = \left( \begin{array}{ccc} a & b & c \\ d & e & f \\ 4g & 4h & 4i \\ \end{array} \right) $

行の足し算

以上から、$n$次正方行列について、$i$行に$j$行の$k$倍を足す基本マトリクス$M$は以下の通り。ただし、$ i \neq j \land k \neq 0$。

e.g.　　 $ M_{3}(3,2;-1) A = \left( \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -1 & 1 \\ \end{array} \right) \left( \begin{array}{ccc} a & b & c \\ d & e & f \\ g & h & i \\ \end{array} \right) = \left( \begin{array}{ccc} a & b & c \\ d & e & f \\ g-d & h-e & i-f \\ \end{array} \right) $

Gaussian Elimination / ガウスの消去法

ガウスの消去法は、”前進消去法”と”後退代入”の手順で構成されている。前進消去のマトリクス上の操作は、拡大行列の係数行列部分を上三角行列（upper triangular matrix）に変換することになる。これについて、上三角行列に変換する意味が分からない、という人がいるけれど（こんな時、イギリスの先生はよく、Don’t panic;) と言う。）やることは、入れ替えて、定数倍して、足す。これまで何度もやってきたことと同じ。

念のために、拡大行列（augmented matrix）と係数行列（coefficient matrix）についても触れておく。

$ \left\{\begin{array}{l}a_{11}x + a_{12}y +a_{13}z = b_{1}\\a_{21}x +a_{22}y +a_{23}z = b_{2}\\a_{31}x +a_{32}y +a_{33}z = b_{3}\end{array}\right. $

ただし、$a_{ij}, b_{i}$ は定数。$x, y, z$ は変数とする。この連立方程式に対応する、拡大行列 $A$ は以下の通り。また、構成要素として係数行列を含む。

eq. 1 を使って、実際に、ガウスの消去法をマトリクスで解いてみる。ここでの拡大行列は以下の通り。

$ A = \left( \begin{array}{rrr} 2 & 1 & -3 & -2 \\ 1 & -4 & 2 & 14 \\ -1 & 3 & 4 & 5 \\ \end{array} \right) $

まず、$A$ の(2,1)成分を0にするために、2行目に3行目の1倍を足す。最初にやった基本マトリクスを使って

$ M_{3}(2,3; +1) A = \left( \begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \\ \end{array} \right) \left( \begin{array}{rrr} 2 & 1 & -3 & -2 \\ 1 & -4 & 2 & 14 \\ -1 & 3 & 4 & 5\\ \end{array} \right) = \left( \begin{array}{rrr} 2 & 1 & -3 & -2 \\ 0 & -1 & 6 & 19 \\ -1 & 3 & 4 & 5\\ \end{array} \right) $

次に、(3,2)成分も0にする。3行目に1行目の1/2倍を足す。

$ M_{3}(3,1; 1/2) A = \left( \begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1/2 & 0 & 1 \\ \end{array} \right) \left( \begin{array}{rrr} 2 & 1 & -3 & -2 \\ 0 & -1 & 6 & 19 \\ -1 & 3 & 4 & 5\\ \end{array} \right) = \left( \begin{array}{rrr} 2 & 1 & -3 & -2 \\ 0 & -1 & 6 & 19 \\ 0 & 3.5 & 2.5 & 4\\ \end{array} \right) $

(3,2)成分も0にする。ただし、A(3,1) = 0をキープしたままにしたいので、3行目に2行目の3.5倍を足す。

$ M_{3}(3,2; 3.5) A = \left( \begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 3.5 & 1 \\ \end{array} \right) \left( \begin{array}{rrr} 2 & 1 & -3 & -2 \\ 0 & -1 & 6 & 19 \\ 0 & 3.5 & 2.5 & 4\\ \end{array} \right) = \left( \begin{array}{rrr} 2 & 1 & -3 & -2 \\ 0 & -1 & 6 & 19 \\ 0 & 0 & 23.5 & 70.5\\ \end{array} \right) $

これで、”前進消去法”の手続きは終了。あとは、もうイメージの通り。$A$ の3行目から、$23.5z = 60.5$ つまり、$ z = 3$ 。これを代入して、$x = 4, y = -1 $ と簡単に求まる。この代入仮定が（難しく聞こえるのかもしれないけど）後退代入と呼ばれているだけ。