掃き出し法・ガウスの消去法（連立1次方程式の解法）

掃き出し法

変数\(x_{1},x_{2},\cdots ,x_{n}\)に関する\(\mathbb{R} \)上の連立1次方程式\begin{equation*}\left\{
\begin{array}{c}
a_{11}x_{1}+a_{12}x_{2}+\cdots +a_{1n}x_{n}=b_{1} \\
a_{21}x_{1}+a_{22}x_{2}+\cdots +a_{2n}x_{n}=b_{2} \\
\vdots \\
a_{m1}x_{1}+a_{m2}x_{2}+\cdots +a_{mn}x_{n}=b_{m}\end{array}\right.
\end{equation*}が与えられているものとします。ただし、\(a_{ij}\in \mathbb{R} \)は係数、\(b_{i}\in \mathbb{R} \)は定数項、\(x_{j}\in \mathbb{R} \)は変数です。変数の個数\(n\)と方程式の個数\(m \)はともに自然数であり、それぞれ任意に選ぶことができます。

連立1次方程式に解が存在することを判定する方法や、解の個数を特定する方法を明らかにしました。結果を簡単に復習します。

行列の階数はその行列の行標準形の階数と一致します。したがって、連立1次方程式\begin{equation*}
\left\{
\begin{array}{c}
a_{11}x_{1}+a_{12}x_{2}+\cdots +a_{1n}x_{n}=b_{1} \\
a_{21}x_{1}+a_{22}x_{2}+\cdots +a_{2n}x_{n}=b_{2} \\
\vdots \\
a_{m1}x_{1}+a_{m2}x_{2}+\cdots +a_{mn}x_{n}=b_{m}\end{array}\right.
\end{equation*}の拡大係数行列\begin{equation*}
\widetilde{A}=\left( A,\boldsymbol{b}\right)
\end{equation*}にガウス・ジョルダンの消去法を適用した上で、得られた行標準形\begin{equation*}
\widetilde{B}=\left( B,\boldsymbol{c}\right)
\end{equation*}について、\begin{equation*}
\mathrm{rank}\left( B\right) =\mathrm{rank}\left( \widetilde{B}\right)
\end{equation*}が成り立つことを確認すれば、連立1次方程式が解を持つことを示したことになります。特に、\begin{equation*}
\mathrm{rank}\left( B\right) =\mathrm{rank}\left( \widetilde{B}\right) =n
\end{equation*}の場合には解が1つだけ存在し、\begin{equation*}
\mathrm{rank}\left( B\right) =\mathrm{rank}\left( \widetilde{B}\right) <n
\end{equation*}の場合には複数の解が存在します。

連立1次方程式の解を具体的に特定するためにはどうすればよいでしょうか。以前に示した以下の命題がヒントになります。

上の命題はどのような意味において有用なのでしょうか。連立1次方程式\begin{equation}
\left\{
\begin{array}{c}
a_{11}x_{1}+a_{12}x_{2}+\cdots +a_{1n}x_{n}=b_{1} \\
a_{21}x_{1}+a_{22}x_{2}+\cdots +a_{2n}x_{n}=b_{2} \\
\vdots \\
a_{m1}x_{1}+a_{m2}x_{2}+\cdots +a_{mn}x_{n}=b_{m}\end{array}\right. \quad \cdots (1)
\end{equation}が解を持つものとします。連立1次方程式\(\left( 1\right) \)は行列方程式\begin{equation}A\boldsymbol{x}=\boldsymbol{b} \quad \cdots (2)
\end{equation}と同値であるため、\(\left( 1\right) \)と\(\left( 2\right) \)の解集合は一致します。\(\left( 1\right) \)の拡大係数行列\begin{equation*}\widetilde{A}=\left( A,\boldsymbol{b}\right)
\end{equation*}にガウス・ジョルダンの消去法を適用した上で、得られた行標準形\begin{equation*}
\widetilde{B}=\left( B,\boldsymbol{c}\right)
\end{equation*}から行列方程式\begin{equation}
B\boldsymbol{x}=\boldsymbol{c} \quad \cdots (3)
\end{equation}を定義します。ガウス・ジョルダンの消去法は有限回の行基本操作であるため\(\widetilde{A}\)と\(\widetilde{B}\)は行同値であり、したがって先の命題より\(\left( 2\right) \)と\(\left( 3\right) \)の解集合は一致します。ゆえに\(\left( 1\right) \)と\(\left(3\right) \)の解集合もまた一致するため、\(\left( 1\right) \)を解く代わりに\(\left( 3\right) \)を解くことができます。\(B\)は行標準形であるため、\(\left( 3\right) \)の解集合は容易に特定できます。このような解法を吐き出し法（row reduction）やガウスの消去法（Gaussian elimination）などと呼びます。

掃き出し法の利用例：解が1つだけ存在する場合

連立1次方程式\begin{equation}
\left\{
\begin{array}{c}
a_{11}x_{1}+a_{12}x_{2}+\cdots +a_{1n}x_{n}=b_{1} \\
a_{21}x_{1}+a_{22}x_{2}+\cdots +a_{2n}x_{n}=b_{2} \\
\vdots \\
a_{m1}x_{1}+a_{m2}x_{2}+\cdots +a_{mn}x_{n}=b_{m}\end{array}\right. \quad \cdots (1)
\end{equation}の拡大係数行列\(\widetilde{A}=\left( A,\boldsymbol{b}\right) \)にガウス・ジョルダンの消去法を適用することにより得られる行標準形\(\widetilde{B}=\left( B,\boldsymbol{c}\right) \)が以下の条件\begin{equation*}\mathrm{rank}\left( B\right) =\mathrm{rank}\left( \widetilde{B}\right) =n
\end{equation*}を満たす場合、\(\left( 1\right) \)は解を1つだけ持ちます。先の議論より、\(\left( 1\right) \)の解は、以下の行列方程式\begin{equation*}B\boldsymbol{x}=\boldsymbol{c}
\end{equation*}の解と一致します。

掃き出し法の利用例：複数の解が存在する場合

連立1次方程式\begin{equation}
\left\{
\begin{array}{c}
a_{11}x_{1}+a_{12}x_{2}+\cdots +a_{1n}x_{n}=b_{1} \\
a_{21}x_{1}+a_{22}x_{2}+\cdots +a_{2n}x_{n}=b_{2} \\
\vdots \\
a_{m1}x_{1}+a_{m2}x_{2}+\cdots +a_{mn}x_{n}=b_{m}\end{array}\right. \quad \cdots (1)
\end{equation}の拡大係数行列\(\widetilde{A}=\left( A,\boldsymbol{b}\right) \)にガウス・ジョルダンの消去法を適用することにより得られる行標準形\(\widetilde{B}=\left( B,\boldsymbol{c}\right) \)が以下の条件\begin{equation*}\mathrm{rank}\left( B\right) =\mathrm{rank}\left( \widetilde{B}\right) <n
\end{equation*}を満たす場合、\(\left( 1\right) \)は複数の解を持ちます。先の議論より、\(\left( 1\right) \)の解集合は、以下の行列方程式\begin{equation*}B\boldsymbol{x}=\boldsymbol{c}
\end{equation*}の解集合と一致します。

掃き出し法の利用例：解が存在しない場合

連立1次方程式\begin{equation}
\left\{
\begin{array}{c}
a_{11}x_{1}+a_{12}x_{2}+\cdots +a_{1n}x_{n}=b_{1} \\
a_{21}x_{1}+a_{22}x_{2}+\cdots +a_{2n}x_{n}=b_{2} \\
\vdots \\
a_{m1}x_{1}+a_{m2}x_{2}+\cdots +a_{mn}x_{n}=b_{m}\end{array}\right. \quad \cdots (1)
\end{equation}の拡大係数行列\(\widetilde{A}=\left( A,\boldsymbol{b}\right) \)にガウス・ジョルダンの消去法を適用することにより得られる行標準形\(\widetilde{B}=\left( B,\boldsymbol{c}\right) \)が以下の条件\begin{equation*}\mathrm{rank}\left( B\right) \not=\mathrm{rank}\left( \widetilde{B}\right)
\end{equation*}を満たす場合、\(\left( 1\right) \)は解を持ちません。

演習問題