連立1次方程式

n元連立1次方程式の解を数値的に求める方法について

n元連立1次方程式†

元連立1次方程式はの行列を使って以下のように表される．

ここで，は係数項，は定数項である． ベクトル表記で表すと，

となる．

連立1次方程式はクラメルの公式(Cramer's fomula)で理論的に解くことができる． に逆行列が存在するならば，上記の式は，

と解くことができる． 逆行列は余因子行列を用いると，

ここではの行列式(determinant)であり，でなければならない． また，余因子行列は，

の要素で構成される．ここで，はの行列を除いた の行列の行列式である．

この余因子行列を使った逆行列の式を代入する．

よって，

により各未知数を求めることができる． さらに，右辺のの項はの列目を\V{b}で置き換えた行列の行列式に等しいことから，

となる．これがクラメルの公式である．

クラメルの公式を用いた際の演算回数はとなり，非常に大きい． 行列のサイズが小さい時やこれから述べる数値解法で得られた解をチェックする際には有用であるが， 行列のサイズが非常に大きくなりがちな実際の問題に当てはめるのは難しい． そこで数値解法により近似的に解く方法を説明する．

連立方程式の数値解法は大きく分けると，

• 直接解法(direct method)
• 反復解法(iterative method)

の2つに分類される． ここでは，直接解法としてガウス消去とガウス・ジョルダン法，反復解法としてヤコビ法，ガウス・ザイデル法，共役勾配法について述べる．また，主に前処理として用いられる三角分解法として，LU分解，コレスキー分解法についても説明する．

• 連立1次方程式：直接解法
• 連立1次方程式：反復法
• 連立1次方程式：三角分解
• 連立1次方程式：共役勾配法
• 連立1次方程式：双共役勾配法

ソースコード†

上記の方法の実装を含むVisual Studio 2010用のソースコードを以下に置く．

linearsystem_v1.1.zip

含まれる方法は，

• ガウス消去,ガウス・ジョルダン法
• ヤコビ法，ガウス・ザイデル法
• 共役勾配法，前処理付き共役勾配法

参考文献†

• 佐藤次男, 中村理一郎, ``よくわかる数値計算 アルゴリズムと誤差解析の実際'', 日刊工業新聞社, 2001.
• 川上一郎, ``数値計算の基礎'', http://www7.ocn.ne.jp/~kawa1/
• Yousef Saad, Iterative methods for sparse linear systems 2nd ed., SIAM, 2003.