SOR法

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

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

反復のスキーム[編集]

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


A=L+D+U

と書ける。

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


\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)

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


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

とできる。

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


\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式から\boldsymbol{\tilde{x}}^{(k+1)}を消去することで、次式が得られる。


\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}

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

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


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)


収束性[編集]

反復行列の固有値を\lambdaとすると、


\max\|\lambda\| \geq \|\omega-1\|  \mbox{for}  \forall\omega

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

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

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

加速パラメータ\omegaの選択[編集]

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

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


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

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

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


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


脚注[編集]

参考文献[編集]


関連項目[編集]