線形連立方程式を解くメモ

どうも,ぽるぽるです.

大学の研究室に配属されゼミで[アルゴリズム設計マニュアル]という本を読んでいます.

その中で　線形連立方程式を解く　という分野の担当になったので、軽く調べたことをまとめることにしました。

入力：サイズm×nの行列Aとm×1のベクトルb

問題：Ax = b を満たすベクトルxは何か

ようは連立方程式を解けってことですね.

これを解くためにいい方法が複数あって、、、

①ガウスの消去法（掃き出し法）

　１：前進消去

　　　行列の掃き出し法を使って変数をどんどん減らしていき x = a の形をつくる

　２：後退代入

　　　１で作った形からどんどん逆に戻していき、変数をすべて求める

O(n^3)でできるが、途中割り算があったりで数値がバグったりするかもだからちゃんとしたサイトでうまく操作されているプログラムを使うのがいいみたい。

自分で実装するのは大変っぽい

②LU分解

　Aｘ = b という行列においてAに前処理をすることで効率よく計算できる

　Aを下三角行列Lと上三角行列Uに分解することをLU分解という

　Ax = b = (L U)x = L (U x) = b

　三角化された連立方程式はn^2時間で解けるので効率がいいみたい

　y = Uxと置くとAx = bは次の連立方程式となる

　 Ly = b

Ux = y

　これについてまず上の式からyを求め、次に下の式を解きxが求まる

　LU分解にO(n^3)、y,xを求めるのO(n^2)が２つで連立方程式を解くことができる

これについてはどの部分がいいのか調べてみると、Ax = bのbが複数ある場合に役に立つみたい

解きたい連立方程式が複数個あって、係数行列の部分が毎回同じならガウスの消去法を複数回つかうとn*O(n^3)で計算がいっぱいだけどLU分解を使うとLU分解にO(n^3)でその後各bに対してO(n^2)で解が求まるので計算量を減らすことができるみたい

LU分解は初耳だったので調べてみて結構面白かった

他にもいろいろな解き方があるみたいなので、興味があれば調べてみると面白いかも

勉強のメモ程度でしか書かないので詳しいことは調べてみてください.