EUREKA --ILPFの定理--

ブログ主のILPF(イルフ)と申します.本ブログでは数学やプログラミング等の知識を書き込み,私自身の備忘録として残すことを目的に開設しました.

ガウス・ジョルダン法

今回は「ガウスジョルダン法」についてのお話.

皆さんは「ガウスジョルダン法」って知っていますか?

理系大学生であれば一度は耳にしたことがあるかもしれませんが,数学を専門としていない人にはあまり馴染みがないかもしれませんね^^;

でも,言葉は知らなくても,実は中学を卒業している人なら誰もが一度は触れたことがある方法なんですよ!!


皆さんは中学の時の数学で連立方程式を学んだことを覚えているでしょうか?

おそらく,連立方程式の解き方には「代入法」と「加減法」の2通りがあるって先生から教わっていると思います.
実は,「加減法」こそが「ガウスジョルダン法」の正体なのです!!

もし中学生の読者がいたら,是非ともクラスの友人にこの話題を話してみましょう!!
きっと「xxさんって物知りなんだね!!」って注目を浴びることが出来るかもしれませんよ(確証はないけどww)

中学校で学んだ「加減法」並びに「ガウスジョルダン法」はそのシンプルさが故に,あまり記憶に残っていない人も多いかもしれません.
ですが,この方法は線形代数学的にも非常に理にかなっており,今日の連立方程式を解くプログラムの基礎となる,非常に重要なアルゴリズムなんです!!


ガウスジョルダン法は次の基本ルールから成り立っているといえます.

  1. ある方程式の両辺に定数を掛ける
  2. ある方程式の両辺に定数を掛け,別の方程式に加える

言葉だけだと伝わり辛いと思うので,次の三元連立方程式を例に
挙げて説明します(中学校は二元連立方程式が主流ですが,方程式の数が増えてもやり方は変わらないので,こっちで説明させていただきます).

f:id:ILPF:20170503153323j:plain

それでは,1,2のルールを用いて,変数をどんどん消していきます.

{\displaystyle(4)=(2)-(1),(5)=(3)-2\times(1)}

f:id:ILPF:20170503153436j:plain

{\displaystyle(6)=(1)+\frac{1}{2}\times(4),(7)=-\frac{1}{2}\times(4),(8)=(5)+(4)}

f:id:ILPF:20170503153615j:plain

{\displaystyle(9)=(6)-2\times(8),(10)=(7)+(8),(11)=-(8)}

f:id:ILPF:20170503153746j:plain

これで連立方程式を解くことができました.

特別なことをしていないので,中学生の読者でも解くことができたのではないでしょうか?
この単純な解法のことこそ「ガウスジョルダン法」なんです.

ここから線形代数の知識を織り交ぜて「ガウスジョルダン法」を見ていくことにします.

先程の連立方程式は,行列の形で表すと次のように表すことができます.

f:id:ILPF:20170503153907j:plain

ここで,係数をまとめた行列{\displaystyle\boldsymbol{A}}のことを「係数行列」,変数をまとめた行列
(ベクトル){\displaystyle\boldsymbol{x}}を「変数ベクトル」,定数項をまとめたベクトル{\displaystyle\boldsymbol{b}}
「定数ベクトル」と呼びます.まんまですね.

線形代数学的にいえば,この連立方程式を解くということは即ち,

f:id:ILPF:20170503154043j:plain

となるような{\displaystyle\boldsymbol{A}}逆行列{\displaystyle\boldsymbol{A}^{-1}}を求め,

f:id:ILPF:20170503154216j:plain

を計算することに相当します.ここで{\displaystyle\boldsymbol{E}}単位行列といい,いわゆる数字の{\displaystyle1}に相当する行列です.

{\displaystyle\boldsymbol{A}^{-1}}を求める」のは,{\displaystyle3\times3}の行列までならサラスの公式を使って手計算で行えますが,それ以上の大きさになるとより複雑になってしまいます.

そこで,より簡潔に連立方程式を解く方法の一つが「ガウスジョルダン法」です.そしてこの方法が線形代数学的に見て理にかなっていることをこれから実証しようと思います.

先程の例で,{\displaystyle(1)(4)(5)}の形に変形したのを行列で表してみると,

f:id:ILPF:20170503154420j:plain

となります.行列の計算を嗜んでいる読者の方は実際に計算してみて確認してみてくださいね.
ここで,{\displaystyle\boldsymbol{P}_1}のことを変換行列って呼んだりします.変換行列の見方についてはいつかの機会で話すことにして,注目してほしいのは両辺左側から{\displaystyle\boldsymbol{P}_1}を掛けていることです.当たり前のことですが,変換後の式全体は変換前の関係をちゃんと維持していることが分かります.

同様にその後の式変形についても見ていきましょう.

{\displaystyle(6)(7)(8)}

f:id:ILPF:20170503154824j:plain

{\displaystyle(9)(10)(11)}

f:id:ILPF:20170503155012j:plain

以上から,ガウスジョルダン法の変換のすべては変換行列で表すことができ,新たに変換が行われたら,両辺左側から新しい変換行列が掛け合わされることが分かります.

そして,この変形を何回か繰り返していくと,左辺は最終的に

f:id:ILPF:20170503155143j:plain

となり,右辺は

f:id:ILPF:20170503155243j:plain

となります.

気が付いた方もいるかもしれませんが,変換行列をすべて掛け合わせたものは逆行列になる,すなわち,

f:id:ILPF:20170503155519j:plain

となることが分かります.

長々と計算ばかりしてきましたが,つまり結論をいうと,ガウスジョルダン法を行えば自ずと逆行列を求めることができ,さらには方程式の解まで分かっちゃうんです!!
ちょっと面白さを感じますよね~(私だけかな^^;)

今回はガウスジョルダン法についてお話をしてきました.まとめると以下のようになります.

次回はガウスジョルダン法によるプログラミングと,計算量についてお話できたらと思います.