ガウスの消去法
カテゴリ：線形代数
一次方程式系を解くアルゴリズムの一つにガウスの消去法というものがあります。一次方程式をプログラムで解く際によく使います。ここではこのガウスの消去法について解説します。
ガウスの消去法
さっそくですが、例を使いながらガウスの消去法について解説します。
を実際にガウスの消去法で解いていきます。まず、行列表示させます。すると
![\left[\begin{array}{cc}1&1\\1&-1\end{array}\right|\left. \begin{array}{c}3\\-1\end{array}\right]](https://s0.wp.com/latex.php?latex=%5Cleft%5B%5Cbegin%7Barray%7D%7Bcc%7D1%261%5C%5C1%26-1%5Cend%7Barray%7D%5Cright%7C%5Cleft.+%5Cbegin%7Barray%7D%7Bc%7D3%5C%5C-1%5Cend%7Barray%7D%5Cright%5D&bg=ffffff&fg=000000&s=0 "\left[\begin{array}{cc}1&1\\1&-1\end{array}\right|\left. \begin{array}{c}3\\-1\end{array}\right]")
となります。次に、
- 行の入れ替え：
- ある行に別の行を何倍かして代入する：
という操作をして、対角線を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}](https://s0.wp.com/latex.php?latex=%5Cleft%5B%5Cbegin%7Barray%7D%7Bcc%7D1%261%5C%5C1%26-1%5Cend%7Barray%7D%5Cright%7C%5Cleft.+%5Cbegin%7Barray%7D%7Bc%7D3%5C%5C-1%5Cend%7Barray%7D%5Cright%5D%5Crightarrow%5Cleft%5B%5Cbegin%7Barray%7D%7Bcc%7D1%261%5C%5C0%26-2%5Cend%7Barray%7D%5Cright%7C%5Cleft.+%5Cbegin%7Barray%7D%7Bc%7D3%5C%5C-4%5Cend%7Barray%7D%5Cright%5D%2CR_%7B2%7D-R_%7B1%7D%5Crightarrow+R_%7B1%7D&bg=ffffff&fg=000000&s=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}](https://s0.wp.com/latex.php?latex=%5Cleft%5B%5Cbegin%7Barray%7D%7Bcc%7D1%261%5C%5C0%26-2%5Cend%7Barray%7D%5Cright%7C%5Cleft.+%5Cbegin%7Barray%7D%7Bc%7D3%5C%5C-4%5Cend%7Barray%7D%5Cright%5D%5Crightarrow%5Cleft%5B%5Cbegin%7Barray%7D%7Bcc%7D1%261%5C%5C0%261%5Cend%7Barray%7D%5Cright%7C%5Cleft.+%5Cbegin%7Barray%7D%7Bc%7D3%5C%5C2%5Cend%7Barray%7D%5Cright%5D%2C%5Cfrac%7B1%7D%7B2%7D%5Ctimes+R_%7B2%7D%5Crightarrow+R_%7B2%7D&bg=ffffff&fg=000000&s=0 "\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}](https://s0.wp.com/latex.php?latex=%5Cleft%5B%5Cbegin%7Barray%7D%7Bcc%7D1%261%5C%5C0%261%5Cend%7Barray%7D%5Cright%7C%5Cleft.+%5Cbegin%7Barray%7D%7Bc%7D3%5C%5C2%5Cend%7Barray%7D%5Cright%5D%5Crightarrow%5Cleft%5B%5Cbegin%7Barray%7D%7Bcc%7D1%260%5C%5C0%261%5Cend%7Barray%7D%5Cright%7C%5Cleft.+%5Cbegin%7Barray%7D%7Bc%7D1%5C%5C2%5Cend%7Barray%7D%5Cright%5D+%2CR_%7B1%7D-R_%7B2%7D%5Crightarrow+R_%7B1%7D&bg=ffffff&fg=000000&s=0 "\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}{ccc}0&2&-1\\-1&2&-1\\1&-4&1\end{array}\right|\left.\begin{array}{c}1\\0\\2\end{array}\right]](https://s0.wp.com/latex.php?latex=%5Cleft%5B%5Cbegin%7Barray%7D%7Bccc%7D0%262%26-1%5C%5C-1%262%26-1%5C%5C1%26-4%261%5Cend%7Barray%7D%5Cright%7C%5Cleft.%5Cbegin%7Barray%7D%7Bc%7D1%5C%5C0%5C%5C2%5Cend%7Barray%7D%5Cright%5D&bg=ffffff&fg=000000&s=0 "\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}](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle%5Cleft%5B%5Cbegin%7Barray%7D%7Bccc%7D0%262%26-1%5C%5C-1%262%26-1%5C%5C1%26-4%261%5Cend%7Barray%7D%5Cright%7C%5Cleft.%5Cbegin%7Barray%7D%7Bc%7D1%5C%5C0%5C%5C2%5Cend%7Barray%7D%5Cright%5D%5C%5C%5Crightarrow%5Cleft%5B%5Cbegin%7Barray%7D%7Bccc%7D1%26-4%261%5C%5C-1%262%26-1%5C%5C0%262%26-1%5Cend%7Barray%7D%5Cright%7C%5Cleft.%5Cbegin%7Barray%7D%7Bc%7D2%5C%5C0%5C%5C1%5Cend%7Barray%7D%5Cright%5D%2CR_%7B1%7D%5Cleftrightarrow+R_%7B3%7D%5C%5C%5Crightarrow%5Cleft%5B%5Cbegin%7Barray%7D%7Bccc%7D1%26-4%261%5C%5C0%26-2%260%5C%5C0%262%26-1%5Cend%7Barray%7D%5Cright%7C%5Cleft.%5Cbegin%7Barray%7D%7Bc%7D2%5C%5C2%5C%5C1%5Cend%7Barray%7D%5Cright%5D%2CR_%7B2%7D%2BR_%7B1%7D%5Crightarrow+R_%7B2%7D%5C%5C%5Crightarrow%5Cleft%5B%5Cbegin%7Barray%7D%7Bccc%7D1%26-4%261%5C%5C0%261%260%5C%5C0%262%26-1%5Cend%7Barray%7D%5Cright%7C%5Cleft.%5Cbegin%7Barray%7D%7Bc%7D2%5C%5C-1%5C%5C1%5Cend%7Barray%7D%5Cright%5D%2CR_%7B2%7D%5Ctimes%5Cleft%28-%5Cfrac%7B1%7D%7B2%7D%5Cright%29%5Crightarrow+R_%7B2%7D%5C%5C%5Crightarrow%5Cleft%5B%5Cbegin%7Barray%7D%7Bccc%7D1%26-4%261%5C%5C0%261%260%5C%5C0%260%26-1%5Cend%7Barray%7D%5Cright%7C%5Cleft.%5Cbegin%7Barray%7D%7Bc%7D2%5C%5C-1%5C%5C3%5Cend%7Barray%7D%5Cright%5D%2CR_%7B3%7D-2R_%7B2%7D%5Crightarrow+R_%7B3%7D%5C%5C%5Crightarrow%5Cleft%5B%5Cbegin%7Barray%7D%7Bccc%7D1%26-4%261%5C%5C0%261%260%5C%5C0%260%261%5Cend%7Barray%7D%5Cright%7C%5Cleft.%5Cbegin%7Barray%7D%7Bc%7D2%5C%5C-1%5C%5C-3%5Cend%7Barray%7D%5Cright%5D%2CR_%7B3%7D%5Ctimes%28-1%29%5Crightarrow+R_%7B3%7D&bg=ffffff&fg=000000&s=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}](https://s0.wp.com/latex.php?latex=%5Cleft%5B%5Cbegin%7Barray%7D%7Bccc%7D1%26-4%261%5C%5C0%261%260%5C%5C0%260%261%5Cend%7Barray%7D%5Cright%7C%5Cleft.%5Cbegin%7Barray%7D%7Bc%7D2%5C%5C-1%5C%5C-3%5Cend%7Barray%7D%5Cright%5D%5C%5C%5Crightarrow%5Cleft%5B%5Cbegin%7Barray%7D%7Bccc%7D1%26-4%260%5C%5C0%261%260%5C%5C0%260%261%5Cend%7Barray%7D%5Cright%7C%5Cleft.%5Cbegin%7Barray%7D%7Bc%7D5%5C%5C-1%5C%5C-3%5Cend%7Barray%7D%5Cright%5D%2CR_%7B1%7D-R_%7B3%7D%5Crightarrow+R_%7B1%7D%5C%5C%5Crightarrow%5Cleft%5B%5Cbegin%7Barray%7D%7Bccc%7D1%260%260%5C%5C0%261%260%5C%5C0%260%261%5Cend%7Barray%7D%5Cright%7C%5Cleft.%5Cbegin%7Barray%7D%7Bc%7D1%5C%5C-1%5C%5C-3%5Cend%7Barray%7D%5Cright%5D%2CR_%7B1%7D%2B4R_%7B2%7D%5Crightarrow+R_%7B1%7D&bg=ffffff&fg=000000&s=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}")
これで答えが
と求まります。
著者：安井 真人(やすい まさと)
@yasui_masatoさんをフォロー