情報処理演習 第5回 行列の反復解法 「反復解法による連立 1 次方程式の解法」 (講義ノート)

消去法は、直接解法であり、元の数により演算回数が決まる。 ただし除算を含むため、相対誤差が積み重なることがある。 部分 pivot を用いて防ぐことが可能であった。

この一方、 反復解法iternative method を使う場合は、演算を繰り返しつつ、数値解に近づける方法である。

近似解のデータが固定されている場合は定常反復解法、と呼ばれ、 Jacobi 法、Gauss -- Seidel 法、 SORSuccessive Over Relaxation などがある。 反復回数により変化するデータを用いる場合は非定常反復解法に分けられる。 BiCGSTAB などがある。偏微分方程式の境界値問題などに利用できる。

方程式を数値的に解く場合、数値解がある値へと収束しない場合は、 計算を続けても求まらない場合がある。 ある方程式において、k 回目に得られる数値解を v_k とする。 十分大きな数 N 回目までに収束する場合は、 十分小さな数 ε (>0) を用いて、

|vk+1 - vk| < ε

が成立することを意味する。

対角優位行列

n 元連立 1 次方程式から作られる n × n 行列 A の各要素について、

|ai,i| > &Sigmanj = 1, j ≠ i |ai,j| 
                                (1 ≤ i ≤ n)

が成り立つとき、A は対角優位行列strictly diagonally dominant matrix であるという。

0 の要素が多い 疎sparse行列のとき、 少ない計算量で解を求めることができる。 ただし、A の対角要素はゼロではないと仮定する。 もし対角要素がゼロになっている場合は、適宜行を交換したものを使用する。