SOR法

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

反復のスキーム

[math]n[/math]次正方行列[math]A[/math]は、上三角行列[math]U[/math]、 下三角行列[math]L[/math]、対角行列[math]D[/math]の和に分離すると、

[math] A=L+D+U [/math]

と書ける。

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

[math] \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) [/math]

この値を次段でそのまま採用せずに、ガウス＝ザイデル法で本来修正される量[math]\tilde{x}_i^{(k+1)}-x_i^{(k)}[/math]に1より大きい 加速パラメータ[math]\omega[/math]を乗じてこの修正量を拡大し、これを前段の近似値[math]x_i^{(k)}[/math]に加えることで、新たな値は

[math] x_i^{(k+1)} = x_i^{(k)} + \omega \left( \tilde{x}_i^{(k+1)}-x_i^{(k)} \right) [/math]

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

[math] x_i^{(k+1)} = (1-\omega)x_i^{(k)} + \omega\tilde{x}_i^{(k+1)} [/math]

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

この漸化式を、上の[math]A=L+D+U[/math]を用いて行列で表現すると、

[math] \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} [/math]

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

[math] \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} [/math]

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

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

[math] x_i^{(k+1)} = 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) [/math]

収束性

反復行列の固有値を[math]\lambda[/math]とすると、

[math] \max|\lambda| \geq |\omega-1| \quad \forall\omega [/math]

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

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

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

加速パラメータ[math]\omega[/math]の選択

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

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

[math] PAP^{-1}=\left[\begin{matrix} D_1 & M_1 \\ M_2 & D_2 \end{matrix}\right] [/math]

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

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

[math] \omega = \frac{2}{1+\sqrt{1-\rho\left(M_J\right)^2}} [/math]

参考文献

• 森正武 『数値解析』 共立出版、2002年2月。ISBN 4-320-01701-3。

関連項目

• 数値解析
• ヤコビ法
• ガウス＝ザイデル法