連立線形方程式の代表的な計算方法についてまとめておく。

各種アルゴリズム

様々な手法があるが、大きく分けると以下の二種類。

直接法

連立線形方程式を構成する各式に代数的操作を繰り返し、係数行列を単位行列へと整形していく解法 (係数行列が単位行列ベクトルのはずのは解ベクトルに一致)。

代表的な手法。

反復法

適当な初期解を与え、そこから真の解へと近づく操作を何度も繰り返し、誤差を縮小していく解法 (縮小幅が小さくなった時点などで操作を打ち切る)。

代表的な手法。

Gauss-Jordan 法

直接法の一種。他と比べると実装が簡単。

行列の左側の列から順に、単位行列の各要素になるよう変形していく。

つまり、ちょうど k 回目のループでの等式は以下のようになる。

[ δ1,1 ⋯ δ1,k−1 v1,k⋯ v1,n ⋮ ⋮ ⋮ ⋮ δn,1 ⋯ δn,k−1 vn,k⋯ vn,n ] 𝒙 = [ w1 ⋮ wn ]

k 回目のループにおける各行の操作は以下のように行う。

※ ここで vk,k はピボットと呼ばれる。

ピボットの絶対値が 0 または小さ過ぎる場合、計算できないか誤差が大きくなる。

そのため、操作前に行または列を入れ替える。行のみを入れ替える場合、部分ピボット選択、両方を入れ替える場合、完全ピボット選択と言う。行を入れ替えても解の位置は変わらないため、前者は比較的簡単に実装できる。