SOR法 （SORほう、英 : Successive Over-Relaxation 、逐次加速緩和法 ）とは n {\displaystyle n} 連立一次方程式 A x = b {\displaystyle A{\boldsymbol {x}}={\boldsymbol {b}}} 反復法 で解く手法の一つであり、 ガウス＝ザイデル法 に加速パラメータ ω {\displaystyle \omega } [ 1]
n {\displaystyle n} 正方行列 A {\displaystyle A} 三角行列 U {\displaystyle U} 三角行列 L {\displaystyle L} 対角行列 D {\displaystyle D}
A = L + D + U {\displaystyle A=L+D+U} と書ける。
非対角成分に相当する項をすべて右辺に移項し、すべての量 x 1 , x 2 , … , x n {\displaystyle x_{1},x_{2},\ldots ,x_{n}} ガウス＝ザイデル法 )。こうして計算された値を x ~ ( k + 1 ) {\displaystyle {\boldsymbol {\tilde {x}}}^{(k+1)}} x ~ i ( k + 1 ) {\displaystyle {\tilde {x}}_{i}^{(k+1)}} [ 1]
x ~ i ( k + 1 ) = 1 a i i ( b i − ∑ j = 1 i − 1 a i j x j ( k + 1 ) − ∑ j = i + 1 n a i j x j ( k ) ) {\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)} この値を次段でそのまま採用せずに、ガウス＝ザイデル法 で本来修正される量 x ~ i ( k + 1 ) − x i ( k ) {\displaystyle {\tilde {x}}_{i}^{(k+1)}-x_{i}^{(k)}} 加速パラメータ （[ 1] 緩和因子 、緩和係数 と呼ばれている） ω {\displaystyle \omega } x i ( k ) {\displaystyle x_{i}^{(k)}}
x i ( k + 1 ) = x i ( k ) + ω ( x ~ i ( k + 1 ) − x i ( k ) ) {\displaystyle x_{i}^{(k+1)}=x_{i}^{(k)}+\omega \left({\tilde {x}}_{i}^{(k+1)}-x_{i}^{(k)}\right)} とできる[ 1]
x i ( k + 1 ) = ( 1 − ω ) x i ( k ) + ω x ~ i ( k + 1 ) {\displaystyle x_{i}^{(k+1)}=(1-\omega )x_{i}^{(k)}+\omega {\tilde {x}}_{i}^{(k+1)}} として計算するか、または本節の最後に書かれた式を用いるのがよい。
この漸化式を、上の A = L + D + U {\displaystyle A=L+D+U}
{ x ~ ( k + 1 ) = D − 1 ( b − L x ( k + 1 ) − U x ( k ) ) x ( k + 1 ) = x ( k ) + ω ( x ~ ( k + 1 ) − x ( k ) ) {\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式から x ~ ( k + 1 ) {\displaystyle {\boldsymbol {\tilde {x}}}^{(k+1)}}
x ( k + 1 ) = ( I + ω D − 1 L ) − 1 { ( 1 − ω ) I − ω D − 1 U } x ( k ) + ω ( D + ω L ) − 1 b {\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}}} 上式における x ( k ) {\displaystyle {\boldsymbol {x}}^{(k)}} M ω = ( I + ω D − 1 L ) − 1 { ( 1 − ω ) I − ω D − 1 U } {\displaystyle 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 ) = ( 1 − ω ) x i ( k ) + ω 1 a i i ( b i − ∑ j = 1 i − 1 a i j x j ( k + 1 ) − ∑ j = i n a i j x j ( k ) ) {\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 }
max | λ | ≥ | ω − 1 | ∀ ω {\displaystyle \max |\lambda |\geq |\omega -1|\quad \forall \omega } が成立することから、少なくとも 0 < ω < 2 {\displaystyle 0<\omega <2} [ 2]
さらに、正定値対称行列 A {\displaystyle A} A x = b {\displaystyle A{\boldsymbol {x}}={\boldsymbol {b}}} ω {\displaystyle \omega } 0 < ω < 2 {\displaystyle 0<\omega <2} [ 1]
また、 ω = 1 {\displaystyle \omega =1} ガウス＝ザイデル法 と同じになり[ 1] ω {\displaystyle \omega } 1 より小さいとき ガウス＝ザイデル法 より収束が遅くなる。ただし、ガウス＝ザイデル法 で収束しないような問題には使える [ 3]
ω {\displaystyle \omega } [ 編集 ] 一般に加速パラメータ ω {\displaystyle \omega }
しかし、 ω {\displaystyle \omega } A {\displaystyle A} P {\displaystyle P}
P A P − 1 = [ D 1 M 1 M 2 D 2 ] {\displaystyle PAP^{-1}=\left[{\begin{matrix}D_{1}&M_{1}\\M_{2}&D_{2}\end{matrix}}\right]} という形の行列に相似変換することができ、さらにヤコビ法 の反復行列 M J = − D − 1 ( L + U ) {\displaystyle M_{J}=-D^{-1}\left(L+U\right)} スペクトル半径 ρ ( M J ) {\displaystyle \rho \left(M_{J}\right)} D 1 , D 2 {\displaystyle D_{1},D_{2}} 対角行列 である。
このとき、SOR法の反復行列のスペクトル半径 ρ ( M ω ) {\displaystyle \rho \left(M_{\omega }\right)} ω {\displaystyle \omega } [ 4]
ω = 2 1 + 1 − ρ ( M J ) 2 {\displaystyle \omega ={\frac {2}{1+{\sqrt {1-\rho \left(M_{J}\right)^{2}}}}}} 共役勾配法 をはじめとしたクリロフ部分空間法 の普及が進んだことでSOR法の使用が減ってしまったこともあったが[ 1] [ 5] [ 6]
^ a b c d e f g 山本哲朗『数値解析入門』（増訂版）サイエンス社 〈サイエンスライブラリ 現代数学への入門 14〉、2003年6月。ISBN 4-7819-1038-6 。 ^ 幸谷智紀 (13 October 2007). 連立一次方程式の解法2 -- 反復法 (PDF) (Report). 2018年3月30日閲覧 。 ^ “SOR法 ” (2004年12月16日). 2018年3月30日 閲覧。 ^ Varga, R. S. (2009). Matrix iterative analysis (Vol. 27). Springer Science & Business Media. ^ 宮武勇登, 曽我部知広, & 張紹良. (2017). 微分方程式に対する離散勾配法に基づく線形方程式の数値解法の生成. 日本応用数理学会 論文誌, 27(3), 239-249. ^ Miyatake, Y., Sogabe, T., & Zhang, S. L. (2018). On the equivalence between SOR-type methods for linear systems and the discrete gradient methods for gradient systems. en:Journal of Computational and Applied Mathematics , 342, 58-69. 
French
Deutsch
![{\displaystyle PAP^{-1}=\left[{\begin{matrix}D_{1}&M_{1}\\M_{2}&D_{2}\end{matrix}}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ec6822fbfce8c13ab9463d4a295c35bc1d1b3c02)
