ガウスの消去法

ガウスの消去法

一次方程式系を解くアルゴリズムの一つにガウスの消去法というものがあります。一次方程式をプログラムで解く際によく使います。ここではこのガウスの消去法について解説します。

ガウスの消去法

さっそくですが、例を使いながらガウスの消去法について解説します。

 \left\{\begin{array}{c}x+y=3\\x-y=-1\end{array}\right.

を実際にガウスの消去法で解いていきます。まず、行列表示させます。すると

 \left[\begin{array}{cc}1&1\\1&-1\end{array}\right|\left. \begin{array}{c}3\\-1\end{array}\right]

となります。次に、

  1. 行の入れ替え:R_{i}\rightarrow R_{j}
  2. ある行に別の行を何倍かして代入する:\alpha R_{i}+\beta R_{j}\rightarrow R_{i}

という操作をして、対角線を1にして、それより下を0にすることをはじめにやります。では、1行1列目の要素を1にして、1列目の他の部分を0にします。行列の操作は以前に書いた記事を参照してください「一次方程式系の行列表示」。

では、一列目を1,0というように変形させていきます。すると

 \left[\begin{array}{cc}1&1\\1&-1\end{array}\right|\left. \begin{array}{c}3\\-1\end{array}\right]\rightarrow\left[\begin{array}{cc}1&1\\0&-2\end{array}\right|\left. \begin{array}{c}3\\-4\end{array}\right],R_{2}-R_{1}\rightarrow R_{1}

となります。次に、2行2列の要素を1にします。

 \left[\begin{array}{cc}1&1\\0&-2\end{array}\right|\left. \begin{array}{c}3\\-4\end{array}\right]\rightarrow\left[\begin{array}{cc}1&1\\0&1\end{array}\right|\left. \begin{array}{c}3\\2\end{array}\right],\frac{1}{2}\times R_{2}\rightarrow R_{2}

これで対角成分が1になって、それより下は0になりました。

あとは、右下から徐々に対角成分以外を0にしていきます。そして、最終的には対角成分だけを1にします。ではいきます。

 \left[\begin{array}{cc}1&1\\0&1\end{array}\right|\left. \begin{array}{c}3\\2\end{array}\right]\rightarrow\left[\begin{array}{cc}1&0\\0&1\end{array}\right|\left. \begin{array}{c}1\\2\end{array}\right] ,R_{1}-R_{2}\rightarrow R_{1}

これで対角成分だけが1になりました。あとは、行列表示を一次方程式系表示にします。すると

 \left\{\begin{array}{c}x=1\\y=2\end{array}\right.

となります。これが一次方程式系の答えになります。

 \left\{\begin{array}{c}2y-z=1\\-x+2y-z=0\\x-4y+z=2\end{array}\right.

を解け。

まず、行列表示すると

 \left[\begin{array}{ccc}0&2&-1\\-1&2&-1\\1&-4&1\end{array}\right|\left.\begin{array}{c}1\\0\\2\end{array}\right]

となりまう。そして、対角成分を1にしてそれより下を0にします。

 \displaystyle\left[\begin{array}{ccc}0&2&-1\\-1&2&-1\\1&-4&1\end{array}\right|\left.\begin{array}{c}1\\0\\2\end{array}\right]\\\rightarrow\left[\begin{array}{ccc}1&-4&1\\-1&2&-1\\0&2&-1\end{array}\right|\left.\begin{array}{c}2\\0\\1\end{array}\right],R_{1}\leftrightarrow R_{3}\\\rightarrow\left[\begin{array}{ccc}1&-4&1\\0&-2&0\\0&2&-1\end{array}\right|\left.\begin{array}{c}2\\2\\1\end{array}\right],R_{2}+R_{1}\rightarrow R_{2}\\\rightarrow\left[\begin{array}{ccc}1&-4&1\\0&1&0\\0&2&-1\end{array}\right|\left.\begin{array}{c}2\\-1\\1\end{array}\right],R_{2}\times\left(-\frac{1}{2}\right)\rightarrow R_{2}\\\rightarrow\left[\begin{array}{ccc}1&-4&1\\0&1&0\\0&0&-1\end{array}\right|\left.\begin{array}{c}2\\-1\\3\end{array}\right],R_{3}-2R_{2}\rightarrow R_{3}\\\rightarrow\left[\begin{array}{ccc}1&-4&1\\0&1&0\\0&0&1\end{array}\right|\left.\begin{array}{c}2\\-1\\-3\end{array}\right],R_{3}\times(-1)\rightarrow R_{3}

次に、対角成分より上の部分を0にします。

 \left[\begin{array}{ccc}1&-4&1\\0&1&0\\0&0&1\end{array}\right|\left.\begin{array}{c}2\\-1\\-3\end{array}\right]\\\rightarrow\left[\begin{array}{ccc}1&-4&0\\0&1&0\\0&0&1\end{array}\right|\left.\begin{array}{c}5\\-1\\-3\end{array}\right],R_{1}-R_{3}\rightarrow R_{1}\\\rightarrow\left[\begin{array}{ccc}1&0&0\\0&1&0\\0&0&1\end{array}\right|\left.\begin{array}{c}1\\-1\\-3\end{array}\right],R_{1}+4R_{2}\rightarrow R_{1}

これで答えが

 x=1,y=-1,z=-3

と求まります。

著者:安井 真人(やすい まさと)