掃き出し法

連立方程式の解き方

掃き出し法

掃き出し法は、連立方程式を解くための効率の良いアルゴリズムです。解が存在するかどうか、そして解が存在する場合、解空間がどのような集合かが簡単な操作を繰り返すことによって分かってしまいます。

まず、簡単な例を用いて掃き出し法を解説します。

3元一次連立方程式
$\left\{\begin{array}{c}x_1+2x_2&=&3\\3x_1-x_2+x_3&=&0\\2x_1+x_2+x_3&=&1\end{array}\right$
を掃き出し法によって解きます。

まず、連立方程式の係数を抜き取って以下のような行列を作ります。
$\left(\begin{array}{ccccc} 1& 2 & 0 & : & 3\\ 3& -1 & 1 & : & 0\\ 2& 1 & 1 & : & 1 \end{array}\right)$
これを拡大係数行列といいます。

この拡大係数行列に行基本変形と呼ばれる変形を繰り返し施すことによって点線の左側の正方行列を単位行列にします。
$\left(\begin{array}{ccccc} 1& 2 & 0 & : & 3\\ 3& -1 & 1 & : & 0\\ 2& 1 & 1 & : & 1 \end{array}\right)$ →行基本変形→ $\left(\begin{array}{ccccc} 1& 0 & 0 & : & 1\\ 0& 1 & 0 & : & 1\\ 0& 0 & 1 & : & -2 \end{array}\right)$
変形後に得られた行列の点線の右側に現れたベクトルがずばり求める連立方程式の解です！

すなわち、今回の場合は
$\left(\begin{array}{c}x_1\\x_2\\x_3\end{array}\right)=\left(\begin{array}{c}1\\1\\-2\end{array}\right)$
が解です。

行基本変形

掃き出し法の概要は分かっていただけたと思いますので、ここで肝心の行基本変形について解説します。行基本変形とは以下の3つの変形のことをいいます。

２つの行を入れ替える
１つの行をa倍する(a≠0)
１つの行をa倍して他の行に足す

これらの変形を繰り返すことで連立方程式の解が求まってしまうのです。

それでは先ほどの例で実際に行基本変形を行ってみましょう。
左側の行列を単位行列にするコツは一番左の列から順番に単位ベクトルを作っていくことです。

$\left(\begin{array}{ccccc} 1& 2 & 0 & : & 3\\ 3& -1 & 1 & : & 0\\ 2& 1 & 1 & : & 1 \end{array}\right)$

まず、一番左の列を単位ベクトル $\left(\begin{array}{c}1\\0\\0\end{array}\right)$ にします。
$\left(\begin{array}{ccccc} 1& 2 & 0 & : & 3\\ 3& -1 & 1 & : & 0\\ 2& 1 & 1 & : & 1 \end{array}\right)$ →1行目を-3倍して2行目に足す→ $\left(\begin{array}{ccccc} 1& 2 & 0 & : & 3\\ 0& -7 & 1 & : & -9\\ 2& 1 & 1 & : & 1 \end{array}\right)$ →1行目を-2倍して3行目に足す→ $\left(\begin{array}{ccccc} 1& 2 & 0 & : & 3\\ 0& -7 & 1 & : & -9\\ 0& -3 & 1 & : & -5 \end{array}\right)$

次に2列目を単位ベクトル $\left(\begin{array}{c}0\\1\\0\end{array}\right)$ にします。しかし、2列目には1がないので2行目と3行目を使ってまず1を作ります。(1行目を使うと1列目の単位ベクトルが崩れてしまいます)
$\left(\begin{array}{ccccc} 1& 2 & 0 & : & 3\\ 0& -7 & 1 & : & -9\\ 0& -3 & 1 & : & -5 \end{array}\right)$ →3行目を-2倍して2行目に足す→ $\left(\begin{array}{ccccc} 1& 2 & 0 & : & 3\\ 0& -1 & -1 & : & 1\\ 0& -3 & 1 & : & -5 \end{array}\right)$ →2行目を-1倍する→ $\left(\begin{array}{ccccc} 1& 2 & 0 & : & 3\\ 0& 1 & 1 & : & -1\\ 0& -3 & 1 & : & -5 \end{array}\right)$
これで1が作れました。あとは先ほどと同様に変形すれば単位ベクトルが作れます。
$\left(\begin{array}{ccccc} 1& 2 & 0 & : & 3\\ 0& 1 & 1 & : & -1\\ 0& -3 & 1 & : & -5 \end{array}\right)$ →2行目を-2倍して1行目に足す→ $\left(\begin{array}{ccccc} 1& 0 & -2 & : & 5\\ 0& 1 & 1 & : & -1\\ 0& -3 & 1 & : & -5 \end{array}\right)$ →2行目を3倍して3行目に足す→ $\left(\begin{array}{ccccc} 1& 0 & -2 & : & 5\\ 0& 1 & 1 & : & -1\\ 0& 0 & 4 & : & -8 \end{array}\right)$
これで2列目が単位ベクトルになりました。

後は3列目を単位ベクトルにするだけです。
3行目を1/4倍して1を作ります。(2行目にすでに1がありますが2行目を使うと2列目が崩れてしまいます) $\left(\begin{array}{ccccc} 1& 0 & -2 & : & 5\\ 0& 1 & 1 & : & -1\\ 0& 0 & 4 & : & -8 \end{array}\right)$ →3行目を1/4倍する→ $\left(\begin{array}{ccccc} 1& 0 & -2 & : & 5\\ 0& 1 & 1 & : & -1\\ 0& 0 & 1 & : & -2 \end{array}\right)$
あとは先ほどと同様に単位ベクトルを作ります。
$\left(\begin{array}{ccccc} 1& 0 & -2 & : & 5\\ 0& 1 & 1 & : & -1\\ 0& 0 & 1 & : & -2 \end{array}\right)$ →3行目を2倍して1行目に足す→ $\left(\begin{array}{ccccc} 1& 0 & 0 & : & 1\\ 0& 1 & 1 & : & -1\\ 0& 0 & 1 & : & -2 \end{array}\right)$ →3行目を-1倍して2行目に足す→ $\left(\begin{array}{ccccc} 1& 0 & 0 & : & 1\\ 0& 1 & 0 & : & 1\\ 0& 0 & 1 & : & -2 \end{array}\right)$
これでついに連立方程式の解 $\left(\begin{array}{c}x_1\\x_2\\x_3\end{array}\right)=\left(\begin{array}{c}1\\1\\-2\end{array}\right)$
が得られました。

単位行列に出来ない場合

この例ではめでたく単位行列を作ることが出来ましたが、実は単位行列を作ることができない場合もあります。次回は単位行列を作ることができないときにはどうすればよいかを解説します。また連立方程式の解の構造は(解の一つを $\mathbf{x}_0$ としたとき) $\mathbf{x}_0+\rm{Ker}f$ となっているということでしたが、今回の例では $\rm{Ker}f$ はどうなってしまったのでしょうか。次回、その謎に迫ります。

Next : 続掃き出し法