2015/07/05

ガウスの消去法による連立一次方程式の解き方

分野: 線形代数  レベル: 大学数学

連立一次方程式の解法としてガウスの消去法(掃き出し法)を解説します。ガウスの消去法はアイデアが簡単で,計算時間が短いので広く利用されています。

ガウスの消去法のメリット

・アイデアが簡単
ガウスの消去法の基本的なアイデアは中学数学で学ぶレベルです!中学,高校数学で登場する連立一次方程式は三変数くらいまでで,代入法または消去法で解くのが一般的でした(今回は消去法に注目)が,同じアイデアが一般の $n$ 変数の場合にも通用します。

・計算時間が短い
連立一次方程式の解を(一応)明示的に表す公式としてクラメルの公式があります。→クラメルの公式の具体例と証明
しかし,クラメルの公式をそのまま使おうとすると大規模な問題では計算量が爆発します。

一方,ガウスの消去法は計算時間がそれなりに短い(乗算がだいたい $\dfrac{n^3}{3}$ 回)ので大規模な連立一次方程式にも太刀打ちできます。

ガウスの消去法の概要

ガウスの消去法は前進消去(文字を1つずつ消していく操作)と後退代入(1成分ずつ答えを求めていく操作)からなります。順々に説明していきます。

注:以下では方程式の数と変数の数が同じで,解が一つしかない(係数行列が正則)場合を考えます。解が存在しない場合や無数にある場合も少し状況が変わりますが使えます。

前進消去

方程式の定数倍を他の方程式に加えることで文字を順番に消していきます。

前進消去における目標の形は $k$ 番目の方程式には $k$ 個目以降の変数のみがあるような連立一次方程式です。

例題

以下の連立一次方程式を解け。
$x_1+2x_2-2x_3=3$
$x_1-x_2+3x_3=4$
$2x_1+3x_2-5x_3=1$

解答(前進消去部分):
STEP1.二番目以降の式から $x_1$ を消すのが目標。
一番目の式の$-1$ 倍を二番目の式に加える,一番目の式の$-2$ 倍を三番目の式に加える:
$x_1+2x_2-2x_3=3$
$-3x_2+5x_3=1$
$-x_2-x_3=-5$

STEP2.三番目(以降)の式から $x_2$ を消すのが目標。
二番目の式の$-\dfrac{1}{3}$ 倍を三番目に加える:
$x_1+2x_2-2x_3=3$
$-3x_2+5x_3=1$
$-\frac{8}{3}x_3=-\frac{16}{3}$

これで「目標の形」になった!
なお,$n$ 変数の場合はSTEP$ (n-1)$ まで続きます。


注:前進消去のステップ $i$ で $i$ 番目の式の $x_i$ の係数が $0$ のときはそれを使って $x_i$ を消去することができません。その場合は適当に方程式の順番を交換すればOKです(係数行列が正則という仮定のもとでは $x_i$ の係数が $0$ でない方程式が必ず存在するのでそれを $i$ 番目に持っていく)。

後退代入

後退代入は簡単です。後ろの式から順番にたどっていき,一つずつ変数の値を求めていくだけです。

解答(後退代入部分):
$x_1+2x_2-2x_3=3$
$-3x_2+5x_3=1$
$-\frac{8}{3}x_3=-\frac{16}{3}$
の三番目の式から $x_3=2$ が分かる。

次に,これを二番目の式に代入すると$-3x_2+10=1$ となり $x_2=3$ が分かる。

さらに,今まで得た部分($x_2,x_3$ の値)を一番目の式に代入すると $x_1+6-4=3$ となり $x_1=1$ となる。

答えは$(x_1,x_2,x_3)=(1,3,2)$

実際計算するときは $x_1$ とか $x_2$ とか書かずに係数だけを並べた行列を用いるのが普通です。
分野: 線形代数  レベル: 大学数学