連立方程式(4) - 講義ノート

SOR法（Succesive Over-Relaxation Method）

$\left\{\begin{matrix} x_1^{(k+1)} = \omega f_1 \left(x_2^{(k)} \right)+ (1-\omega) x_1^{(k)} \\ x_2^{(k+1)} = \omega f_2 \left(x_1^{(k)} \right)+ (1-\omega) x_2^{(k)} \end{matrix}\right.$

ω：加速係数（ω=1：ガウズ・ザイデル法）：一般に1〜2の値
ガウス・ザイデル法の数倍の速さで収束する

SORの意味

ガウス・ザイデル法では下のようであった。
$\left\{\begin{matrix} x_1^{(k+1)} = f_1 \left(x_2^{(k)} \right) \\ x_2^{(k+1)} = f_2 \left(x_1^{(k)} \right) \end{matrix}\right.$
上の方の式より、
$x_1^{(k+1)} - x_1^{(k)} = f_1 \left(x_2^{(k)} \right) - x_1^{(k)}$
上式の左辺はx1のk+1回目とk回目の差。この差分をω加速させると、
$x_1^{(k+1)} - x_1^{(k)} = \omega \left( f_1 \left(x_2^{(k)} \right) - x_1^{(k)} \right)$
したがって
$x_1^{(k+1)} = \omega f_1 \left(x_2^{(k)}\right)+ (1-\omega) x_1^{(k)}$

2以下であれば、振動したとしても発散することはないので、1.9近くの値を用いることが多い。2より大きくなると発散してしまう恐れがある。

(補足)ガウス・ジョルダンの消去法

ガウスの消去法
1. 前進消去
2. 後退代入

ガウスの消去法では、前進消去の段階では現在位置よりも下の行の要素を消去していたが、全ての行の要素を消去することにより、前進消去のステップのみで行列を対角化することができる→ガウス・ジョルダンの消去法

直接法vs反復法

以下の要素を検討して決める

行列の形
行列の規模（nの値）
精度（反復法では近似値が求まる）
メモリ量（反復法が有利）

各種行列演算

行列式の演算

サラスの方法（3x3まで）
余因子展開：O(n!)→演算量が多い

特定の行列式は単純に演算できる
例：三角行列の行列式は対角要素の積
LU分解によって行列Aが三角行列に変換できれば、|A|=|LU|=|L||U|=|U|*1と計算できる：O(n^3)

逆行列

AX=I（Iは単位行列）ならばXはAの逆行列
並べた行列に対し、左半分をガウス・ジョルダンの方法を用いて対角化する。
例
$\begin{bmatrix} 3 & 1 & 2 & | & 1 & 0 & 0 \\ 5 & 1 & 3 & | & 0 & 1 & 0 \\ 4 & 2 & 1 & | & 0 & 0 & 1 \end{bmatrix}$
(中略)
$\begin{bmatrix} 1 & 0 & 0 & | & -1.25 & 0.75 & 0.25 \\ 0 & 1 & 0 & | & 1.75 & -1.25 & 0.25 \\ 0 & 0 & 1 & | & 1.5 & -0.5 & -0.5 \end{bmatrix}$
というわけで右側に逆行列を求めることができる。

*1:Lの対角要素はすべて1だから