線形代数　掃き出し法

ここでは、大学で習う線形代数についての基本を説明していきます。また、対象は特に問いません。数学が苦手な方でも理解しやすいような例を利用しているので安心して読み進めてください。なお、当サイトの線形代数の進め方について知りたい方は以下をクリック。

線形代数の進め方

この回では、連立一次方程式を行列を利用して解く際の掃き出し法について説明していきます。

キーワード：連立一次方程式、未知数、係数行列、拡大係数行列、行基本変形、掃き出し法

連立一次方程式とは

掃き出し法に入る前に，連立一次方程式がどんなものだったのか簡単に説明します．なお，連立一次方程式が分かっている方は読み飛ばしましょう．

以下のような形の式を連立一次方程式と呼びました．

\[ \left \{\begin{array}{} x + y + z&= 3・・・① \\ 2x + y + 2z&= 5・・・② \\ 4x + 2y + 6z&= 12・・・③ \end{array} \right . \]

つまり，一次方程式(各項の最高次数が1であるもの，2乗や3乗の項がない)が連なったものでした．

これを普通の方法で解いてみましょう．

①×2-②より，

\[ \left \{\begin{array}{} 2x + 2y + 2z&= 6・・・①×2 \\ 2x + y + 2z&= 5・・・② \end{array} \right . \]

よって，y = 1．③-②×2より，

\[ \left \{\begin{array}{} 4x + 2y + 4z&= 10・・・② \\ 4x + 2y + 6z&= 12・・・③ \end{array} \right . \]

よって，z = 1．最後に①にy = 1，z = 1を代入すると

\[ x + 1 + 1 = 3 \]

よって，x = 1．以上で解が求まりました．

では，これを行列を利用して解くにはどうしたら良いのでしょうか？

用語の定義

行列を利用して連立一次方程式を解く際に少し用語について知っておきましょう．以下の例を使って説明します．

\[ \left \{\begin{array}{} x_{1} + x_{2}+ x_{3}&= 3 \\ 2x_{1} + x_{2} + 2x_{3}&= 5 \\ 4x_{1} + 2x_{2} + 6x_{3}&= 12\end{array} \right . \]

まず，\(x_{1}, x_{2}, x_{3}\)のことを未知数と呼びます．これは解となる変数のことを指します．

そしてこれらを列ベクトルxとしてまとめてみましょう．すると，

\[ x = \begin{pmatrix} x_{1} \\ x_{2} \\ x_{3} \end{pmatrix} \]

また同様に各方程式の右辺のみを列ベクトルbとしてまとめます．

\[ b = \begin{pmatrix} 3 \\ 5 \\ 12 \end{pmatrix} \]

最後に，残った係数を行列Aとしてまとめると，

\[ A = \begin{pmatrix} 1 & 1 & 1 \\ 2 & 1 & 2 \\ 4 & 2 & 6 \end{pmatrix} \]

このAを連立一次方程式の係数行列と呼びます．以上より，一般にある連立一次方程式は行列を使って以下のように表すことができます．

また，Aの最後の列にbを連結させた行列を拡大係数行列と呼びます．上の例では，以下が拡大係数行列です．

\begin{pmatrix} 1 & 1 & 1 & 3 \\ 2 & 1 & 2 & 5 \\ 4 & 2 & 6 & 12\end{pmatrix}

連立一次方程式を行列を利用して解く際には，この拡大係数行列を使うのでよく理解しておきましょう．

掃き出し法の解説

いよいよ行列を使って連立一次方程式を解いていきます．

ですがその前に，行基本変形について少し説明します．行基本変形とはある行列に対し以下の変形を行うことを指します．

実は，上の行基本変形を任意に繰り返すことで(1, 2, 3の順番である必要はない)連立一次方程式の解が必ず求まることが分かっています．

さまざまな線形代数の教科書には行基本変形の証明が書かれていますが，正直抽象的すぎる表現が多く，それらを理解するより，計算の過程で理解する方が早いので，ここでは計算しながら具体的に一つ一つ説明します．

初めて掃き出し法を行う人は何だかよく分からないと思いますが，後にアルゴリズムをまとめたものを説明するので，今は流れを理解するように頑張りましょう．

では，再び以下の例を使ってやってみます．

\[ \left \{\begin{array}{} x_{1} + x_{2}+ x_{3}&= 3 \\ 2x_{1} + x_{2} + 2x_{3}&= 5 \\ 4x_{1} + 2x_{2} + 6x_{3}&= 12\end{array} \right . \]

まず，拡大係数行列を用意します．

\begin{pmatrix} 1 & 1 & 1 & 3 \\ 2 & 1 & 2 & 5 \\ 4 & 2 & 6 & 12\end{pmatrix}

初めに，(1, 1)成分を見ましょう．つまり，1ですね．この事実を覚えておきましょう．

次に，(1, 1)成分以外の第一列の要素を0にするにはどうすれば良いでしょうか？

ここで行基本変形の2番目を利用できます．つまり，第一行を仮定的に-2倍して第二行との和を取ることと， 第一行を仮定的に-4倍して第三行との和を取ることで(1,1)成分以外の第一列の要素を0にできます．

実際に計算してみます．

まず，仮定的に(実際に値が変化するわけではない)，第一行を-2倍します．

\[ \textbf{第一行(仮定)}　\begin{pmatrix} -2 & -2 & -2 & -6 \end{pmatrix} \]

これと第二行との和を取り，それを新たな第二行とします．

\[ \textbf{第一行(仮定)}　\begin{pmatrix} -2 & -2 & -2 & -6 \end{pmatrix}　+　\textbf{第二行}　\begin{pmatrix} 2 & 1 & 2 & 5 \end{pmatrix} \]

\[ \textbf{新たな第二行}　\begin{pmatrix} 0 & -1 & 0 & -1 \end{pmatrix} \]

以上の計算を全体の拡大係数行列に反映すると以下になります．

\begin{pmatrix} 1 & 1 & 1 & 3 \\ 0 & -1 & 0 & -1 \\ 4 & 2 & 6 & 12\end{pmatrix}

次に，第一行を仮定的に-4倍して第三行との和を取るため，仮定的に(実際に値が変化するわけではない)，第一行を-4倍します．

\[ \textbf{第一行(仮定)}　\begin{pmatrix} -4 & -4 & -4 & -12 \end{pmatrix} \]

これと第三行との和を取り，それを新たな第三行とします．

\[ \textbf{第一行(仮定)}　\begin{pmatrix} -4 & -4 & -4 & -12 \end{pmatrix}　+　\textbf{第三行}　\begin{pmatrix} 4 & 2 & 6 & 12 \end{pmatrix} \]

\[ \textbf{新たな第三行} \begin{pmatrix} 0 & -2 & 2 & 0 \end{pmatrix} \]

全体の拡大係数行列を更新すると以下になります．

\begin{pmatrix} 1 & 1 & 1 & 3 \\ 0 & -1 & 0 & -1 \\ 0 & -2 & 2 & 0 \end{pmatrix}

以上で(1,1)成分以外の第一列が0になりました．

次に，(2,2)成分が1であるかどうか注目します．見ると-1であるので，これを1にするために，行基本変形の1番目を利用できます．つまり，第二行を-1倍すると良いと分かります．よって拡大係数行列を更新すると

\begin{pmatrix} 1 & 1 & 1 & 3 \\ 0 & 1 & 0 & 1 \\ 0 & -2 & 2 & 0 \end{pmatrix}

そして，(2,2)成分より下の要素つまり，(3,2)成分を0にします．これには行基本変形の2番目を利用して，第二行を仮定的に2倍して第三行との和をとればOKですね．よって行うと，

第二行を仮定的に2倍する

\begin{pmatrix} 0 & 2 & 0 & 2 \end{pmatrix}

これと第三行との和をとると

\[ \textbf{新たな第三行}　\begin{pmatrix} 0 & 0 & 2 & 2 \end{pmatrix} \]

そして拡大係数行列を更新します．

\begin{pmatrix} 1 & 1 & 1 & 3 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 2 & 2 \end{pmatrix}

少しずつ0の数が増えてきました．次に，(3,3)成分が1であるかどうかを見ます．今は2であるので，行基本変形の1番目より，第三行を1/2倍するとよさそうです．それを行うと，

\begin{pmatrix} 1 & 1 & 1 & 3 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \end{pmatrix}

ここまでで掃き出し法の前半部分が終了しました．拡大係数行列を見ると，係数行列部分(第四列以外)の対角成分(斜めの部分)の左下側が全て0になっているのに気が付きます．このような形になっていることが重要な点です．

逆に言えば，0になっていない場合，どこかで計算ミスをしている可能性があるので注意しましょう．では後半部分です．

係数行列の対角成分が全て1ですが，その各上を見ます．ただし(1,1)成分の上には何もないので，(2,2)成分を見ます．すると(2,2)成分の上つまり(1,2)成分は1となっています．これを0にしたいです．

つまり，第二行を仮定的に-1倍し，第一行との和をとるとよさそうです．よって行うと，拡大係数行列は

\begin{pmatrix} 1 & 0 & 1 & 2 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \end{pmatrix}

最後に，(3,3)成分の上の要素が全て0であるか見ます．今，(2,3)成分は0ですでにOKですが，(1,3)成分は1なのでこれを0にしたいです．よって，第三行を仮定的に-1倍し，第一行との和をとるとよさそうです．拡大係数行列は

\begin{pmatrix} 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \end{pmatrix}

となりました．ここまで長かったものです．以上で掃き出し法は終了です．

拡大係数行列を見ると，係数行列が対角成分を境に階段のようになっています(今回は単位行列になってる)．このように，拡大係数行列に行基本変形を繰り返すことによってできた係数行列を階段行列と呼びます．

連立一次方程式は Ax = bで表されたので，この拡大係数行列をAとbに崩して式に当てはめると，解\(x_{1} = 1, x_{2} = 1, x_{3} = 1\)が求まります(ここは自分でやってみよう)．

掃き出し法は連立一次方程式を解く上で非常に重要です．同じ問題で良いので，一度自分で解いてみましょう．

掃き出し法のアルゴリズム

先ほどは具体例を使って掃き出し法を行いましたが，ここでは，そのアルゴリズムをより分かりやすく説明します．

アルゴリズムの流れは以下になります．

このアルゴリズムをもとに，もう一つ以下の連立一次方程式を解いてみましょう．

\[ \left \{\begin{array}{} x_{1} + 2x_{2}+ 3x_{3}&= 4 \\ 2x_{1} + 5x_{2} + 3x_{3}&= 13 \\ x_{1} + 8x_{3}&= -5\end{array} \right . \]

１．連立一次方程式から拡大係数行列を作る．

\begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 5 & 3 & 13 \\ 1 & 0 & 8 & -5\end{pmatrix}

三つ目の式の\(x_{2}\)の項がないので，このような場合は，0で補完しましょう．

２．拡大係数行列のうち，係数行列部分の第一列から順に見て，零ベクトル(ある列の要素が全て0)でない列jを見つける．

このときの列jは第一列ですね．

３．次に，列jを上から順に見たとき，0でない値αを見つける．ただし，αは第一行にあるものとする．もしαが他の第i行にある場合，3番目の行基本変形により，第一行とその第i行を入れ替える．また，αが1の場合は4へ進む．そうでない場合，1番目の行基本変形より，αを1にして(αを含む行を1/α倍して)4へ進む．

0でない値は(1, 1)成分の1です．そしてこれは第一行にありかつ値も1なので自動でアルゴリズム4に進めます．

４．2番目の行基本変形より，αより下の要素を全て0にする．

つまり，第一行を仮定的に-2倍し第二行との和を取ることと， 第一行を仮定的に-1倍し第三行との和を取ることで実現できます．よって拡大係数行列は以下になります．

\begin{pmatrix} 1 & 2 & 3 & 4 \\ 0 & 1 & -3 & 5 \\ 0 & -2 & 5 & -9\end{pmatrix}

５．列j+1以降で，アルゴリズム3，4の順で再び行う．ただし，アルゴリズム3において，αの存在位置は第二行以下，第三行以下と増えていきその行にあるものとする．そしてこのアルゴリズムを係数行列の最後の列まで繰り返す．

第一列はOKなのでその次の第二列にアルゴリズム3を適用します．このとき，第二行以下で0でない値が初めてあるのは，(2, 2)成分の1です．また，その位置が第二行でかつ値が1なので自動で4に進めます．

アルゴリズム4すなわち(2, 2)成分より下の要素を全て0にしたいので，(3, 2)成分の-2を0にするために，第二行を仮定的に2倍し，第三行との和をとると拡大係数行列は

\begin{pmatrix} 1 & 2 & 3 & 4 \\ 0 & 1 & -3 & 5 \\ 0 & 0 & -1 & 1\end{pmatrix}

これで第二列はOKです．次に第三列にアルゴリズム3を適用します． このとき，第三行以下で0でない値が初めてあるのは，(3, 3)成分の-1です．その位置は第三行ですが，値が-1なので，第三行を-1倍することで(3, 3)成分を1にする必要があります．よって拡大係数行列は

\begin{pmatrix} 1 & 2 & 3 & 4 \\ 0 & 1 & -3 & 5 \\ 0 & 0 & 1 & -1\end{pmatrix}

これでアルゴリズム4に進めます．しかし，(3, 3)成分より下の要素はないです．また，第四列からは拡大係数行列であるのでこれ以上アルゴリズム5は出来ません．

６．最後に各αより上の要素を2番目の行基本変形より，全て0にする．

ここは自分で計算してみましょう．すなわち，(1, 1)成分，(2, 2)成分，(3, 3)成分より上の要素を全て0にするということです．これを行うと最終的に拡大係数行列は以下になります．

\begin{pmatrix} 1 & 0 & 0 & 3 \\ 0 & 1 & 0 & 2 \\ 0 & 0 & 1 & -1\end{pmatrix}

よって解は，\(x_{1} = 3，x_{2} = 2，x_{3} = -1\)となります．

あと数問自分で連立一次方程式を掃き出し法で解いてみましょう．よりアルゴリズムに慣れるはずです．

まとめ

１．連立一次方程式を以下のように行列で表せる．

Ax = b (A:係数行列, x:未知数の列ベクトル, b:各方程式の右辺の列ベクトル)

２．掃き出し法のアルゴリズムは以下である．

(１)．連立一次方程式から拡大係数行列を作る．

(２)．拡大係数行列のうち，係数行列部分の第一列から順に見て，零ベクトル(ある列の要素が全て0)でない列jを見つける．

(３)．次に，列jを上から順に見たとき，0でない値αを見つける．ただし，αは第一行にあるものとする．もしαが他の第i行にある場合，3番目の行基本変形により，第一行とその第i行を入れ替える．また，αが1の場合は4へ進む．そうでない場合，1番目の行基本変形より，αを1にして(αを含む行を1/α倍して)4へ進む．

(４)．2番目の行基本変形より，αより下の要素を全て0にする．

(５)．列j+1以降で，アルゴリズム3，4の順で再び行う．ただし，アルゴリズム3において，αの存在位置は第2行以下，第3行以下と増えていきその行にあるものとする．そしてこのアルゴリズムを係数行列の最後の列まで繰り返す．

(６)．最後に各αより上の要素を2番目の行基本変形より，全て0にする．

３．慣れるまで問題を解きましょう．

練習問題

１．以下の連立一次方程式を掃き出し法によって解きなさい．((2)のヒント：3番目の行基本変形を使うと良い)

\[ (1) \left \{\begin{array}{} x_{1} -2x_{2}+ 2x_{3}&= 1 \\ -2x_{1} + 2x_{2} + x_{3}&= -2 \\ 2x_{1} + x_{2} -2x_{3}&= 2\end{array} \right . \]

\[ (2) \left \{\begin{array}{} x_{1} + 2x_{2} -5x_{3} -x_{4}&= 0 \\ 2x_{1} + 3x_{2} -7x_{3} -4x_{4}&= 0 \\ x_{1} + x_{2} -2x_{3} + 3x_{4}&= 0 \\ -x_{1} -3x_{2} + 2x_{3} + 5x_{4}&= 0 \end{array} \right . \]

解答はこちら → 練習問題解答