SOR法

SOR法（SORほう、英: Successive Over-Relaxation、逐次加速緩和法）とは ${\displaystyle n}$元連立一次方程式${\displaystyle A{\boldsymbol {x}}={\boldsymbol {b}}}$を 反復法で解く手法の一つであり、 ガウス＝ザイデル法に加速パラメータ${\displaystyle \omega }$を導入してその修正量を拡大することで、 更なる加速を図った手法である^[1]。

反復のスキーム

${\displaystyle n}$次正方行列${\displaystyle A}$は、上三角行列${\displaystyle U}$、 下三角行列${\displaystyle L}$、対角行列${\displaystyle D}$の和に分離すると、

${\displaystyle A=L+D+U}$

と書ける。

非対角成分に相当する項をすべて右辺に移項し、すべての量${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$に 各段階で得られている最新のデータを代入するようにする(ガウス＝ザイデル法)。こうして計算された値を${\displaystyle {\boldsymbol {\tilde {x}}}^{(k+1)}}$ とすると、${\displaystyle {\tilde {x}}_{i}^{(k+1)}}$は次の形となる^[1]。

${\displaystyle {\tilde {x}}_{i}^{(k+1)}={\frac {1}{a_{ii}}}\left(b_{i}-\sum _{j=1}^{i-1}a_{ij}x_{j}^{(k+1)}-\sum _{j=i+1}^{n}a_{ij}x_{j}^{(k)}\right)}$

この値を次段でそのまま採用せずに、ガウス＝ザイデル法で本来修正される量${\displaystyle {\tilde {x}}_{i}^{(k+1)}-x_{i}^{(k)}}$に1より大きい 加速パラメータ（^[1]では緩和因子、緩和係数と呼ばれている）${\displaystyle \omega }$を乗じてこの修正量を拡大し、これを前段の近似値${\displaystyle x_{i}^{(k)}}$に加えることで、新たな値は

${\displaystyle x_{i}^{(k+1)}=x_{i}^{(k)}+\omega \left({\tilde {x}}_{i}^{(k+1)}-x_{i}^{(k)}\right)}$

とできる^[1]。ただし、桁落ちを防ぐ観点からこの式の通り計算するのではなく、

${\displaystyle x_{i}^{(k+1)}=(1-\omega )x_{i}^{(k)}+\omega {\tilde {x}}_{i}^{(k+1)}}$

として計算するか、または本節の最後に書かれた式を用いるのがよい。

この漸化式を、上の${\displaystyle A=L+D+U}$を用いて行列で表現すると、

${\displaystyle {\Biggl \{}{\begin{matrix}{\boldsymbol {\tilde {x}}}^{(k+1)}&=&D^{-1}\left({\boldsymbol {b}}-L{\boldsymbol {x}}^{(k+1)}-U{\boldsymbol {x}}^{(k)}\right)\\{\boldsymbol {x}}^{(k+1)}&=&{\boldsymbol {x}}^{(k)}+\omega \left({\boldsymbol {\tilde {x}}}^{(k+1)}-{\boldsymbol {x}}^{(k)}\right)\end{matrix}}}$

となり、この2式から${\displaystyle {\boldsymbol {\tilde {x}}}^{(k+1)}}$を消去することで、次式が得られる。

${\displaystyle {\boldsymbol {x}}^{(k+1)}=\left(I+\omega D^{-1}L\right)^{-1}\left\{\left(1-\omega \right)I-\omega D^{-1}U\right\}{\boldsymbol {x}}^{(k)}+\omega \left(D+\omega L\right)^{-1}{\boldsymbol {b}}}$

上式における${\displaystyle {\boldsymbol {x}}^{(k)}}$の係数 ${\displaystyle M_{\omega }=\left(I+\omega D^{-1}L\right)^{-1}\left\{\left(1-\omega \right)I-\omega D^{-1}U\right\}}$を反復行列という。

実際の数値計算においては、これを各成分について表した下の式が用いられる。

${\displaystyle x_{i}^{(k+1)}=(1-\omega )x_{i}^{(k)}+\omega {\frac {1}{a_{ii}}}\left(b_{i}-\sum _{j=1}^{i-1}a_{ij}x_{j}^{(k+1)}-\sum _{j=i}^{n}a_{ij}x_{j}^{(k)}\right)}$

収束性

反復行列の固有値を${\displaystyle \lambda }$とすると、

${\displaystyle \max |\lambda |\geq |\omega -1|\quad \forall \omega }$

が成立することから、少なくとも${\displaystyle 0<\omega <2}$でなければSOR法の収束性は保証されない ^[2]。

さらに、正定値対称行列${\displaystyle A}$を係数にもつ方程式${\displaystyle A{\boldsymbol {x}}={\boldsymbol {b}}}$に対するSOR法は、 加速パラメータ${\displaystyle \omega }$が${\displaystyle 0<\omega <2}$のとき必ず収束する（Ostrowskiの定理）^[1]。

また、${\displaystyle \omega =1}$のときガウス＝ザイデル法と同じになり^[1]、${\displaystyle \omega }$が1より小さいとき ガウス＝ザイデル法より収束が遅くなる。ただし、ガウス＝ザイデル法で収束しないような問題には使える ^[3]。

加速パラメータ ω {\displaystyle \omega } の選択

一般に加速パラメータ${\displaystyle \omega }$の値をあらかじめ最適に定めることはできない。そのため、問題ごとに適当な値を選択する必要がある。

しかし、${\displaystyle \omega }$の最適な値を決定することができる例も存在する。それは、係数行列${\displaystyle A}$が、ある基本行列${\displaystyle P}$に 対して

${\displaystyle PAP^{-1}=\left[{\begin{matrix}D_{1}&M_{1}\\M_{2}&D_{2}\end{matrix}}\right]}$

という形の行列に相似変換することができ、さらにヤコビ法の反復行列${\displaystyle M_{J}=-D^{-1}\left(L+U\right)}$の スペクトル半径${\displaystyle \rho \left(M_{J}\right)}$が既知であるときである。 なお、上の行列内の${\displaystyle D_{1},D_{2}}$は対角行列である。

このとき、SOR法の反復行列のスペクトル半径${\displaystyle \rho \left(M_{\omega }\right)}$が最小となる${\displaystyle \omega }$の最適値は、 次の形で得られる^[4]。

${\displaystyle \omega ={\frac {2}{1+{\sqrt {1-\rho \left(M_{J}\right)^{2}}}}}}$

近年の研究

共役勾配法をはじめとしたクリロフ部分空間法の普及が進んだことでSOR法の使用が減ってしまったこともあったが^[1]、離散勾配法 (構造保存型数値解法の一つ) との関係が明らかになったことで再び注目されている^[5][6]。