スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

連立1次方程式の求解(直接法)

連立1次方程式 Ax=b を解くアルゴリズムとして
・Gauss-Jordan法
・Gaussの消去法
・LU分解法
の3解法をC言語で実装した。
(A:係数行列,x:未知ベクトル,b:定数ベクトル)

2010/02/17

Tags : 数学 数値解析 プログラミング 線形代数
行列の各種演算をする関数を一から組んだので、思ったより時間がかかった。
行列のデータ構造をどうするかは、悩んだ末、2次元配列を動的確保する方向で落ち着いた。
実装が多少手間だったけど、各種関数が任意サイズの行列に対応しているのは大きなメリットだと思う。

上の3手法について、行列のサイズを100から2000まで100刻みで変化させたときの計算時間が↓のグラフ。

もちろん、アルゴリズムや実行環境によって計算時間は大きく変わるので、手法の比較としては余り参考にならないかも。
計算時間比較

nを次数として、どの方法も計算オーダーは、O(n3)。 (多分)
LU分解が思ったより遅い。
Google先生いわく
「LU分解は、一度L,Uを計算しておくとあとは右辺のベクトルが変わってもO(n2)の手間で計算できるので使える!!」
らしいが、右辺だけ変えるような場面が思いつかない……
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。