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



n元連立1次方程式

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

ls_matrix.eq3.gif

ここで,ls_matrix.eq4.gifは係数項,ls_matrix.eq5.gifは定数項である. ベクトル表記で表すと,

ls_matrix.eq6.gif

となる.

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

ls_matrix.eq8.gif

と解くことができる. 逆行列ls_matrix.eq9.gifは余因子行列ls_matrix.eq10.gifを用いると,

ls_matrix.eq11.gif

ここでls_matrix.eq12.gifls_matrix.eq7.gifの行列式(determinant)であり,ls_matrix.eq13.gifでなければならない. また,余因子行列ls_matrix.eq10.gifは,

ls_matrix.eq14.gif

の要素で構成される.ここで,ls_matrix.eq15.gifls_matrix.eq7.gifls_matrix.eq16.gifls_matrix.eq17.gif列を除いたls_matrix.eq18.gif の行列の行列式である.

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

ls_matrix.eq19.gif

よって,

ls_matrix.eq20.gif

により各未知数ls_matrix.eq21.gifを求めることができる. さらに,右辺のls_matrix.eq22.gifの項はls_matrix.eq7.gifls_matrix.eq17.gif列目を\V{b}で置き換えた行列の行列式に等しいことから,

ls_matrix.eq23.gif

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

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

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

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

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

ソースコード

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

含まれる方法は,

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

参考文献

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

添付ファイル: filelinearsystem_v1.1.zip 1781件 [詳細]

トップ   編集 凍結 差分 履歴 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2022-11-30 (水) 13:48:13