SOR法のソースを表示

'''SOR法'''（SORほう、{{lang-en-short|Successive Over-Relaxation}}、'''逐次加速緩和法'''）とは
<math>n</math>元[[連立一次方程式]]<math>A\boldsymbol{x}=\boldsymbol{b}</math>を
[[反復法_(数値計算)|反復法]]で解く手法の一つであり、
[[ガウス＝ザイデル法]]に加速パラメータ<math>\omega</math>を導入してその修正量を拡大することで、
更なる加速を図った手法である<ref name="Yamamoto1">{{Cite book |和書 |author=山本哲朗 |title=数値解析入門 |edition=増訂版 |date=2003-06 |publisher=[[サイエンス社]] |series=サイエンスライブラリ 現代数学への入門 14 |ISBN=4-7819-1038-6}}</ref>。

==反復のスキーム==
<math>n</math>次[[正方行列]]<math>A</math>は、上[[三角行列]]<math>U</math>、
下[[三角行列]]<math>L</math>、[[対角行列]]<math>D</math>の和に分離すると、
<center><math>
A=L+D+U
</math></center>
と書ける。

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

この値を次段でそのまま採用せずに、[[ガウス＝ザイデル法]]で本来修正される量<math>\tilde{x}_i^{(k+1)}-x_i^{(k)}</math>に1より大きい
'''加速パラメータ'''（<ref name="Yamamoto1"/>では'''緩和因子'''、'''緩和係数'''と呼ばれている）<math>\omega</math>を乗じてこの修正量を拡大し、これを前段の近似値<math>x_i^{(k)}</math>に加えることで、新たな値は
<center><math>
x_i^{(k+1)} = x_i^{(k)} + \omega \left( \tilde{x}_i^{(k+1)}-x_i^{(k)} \right)
</math></center>
とできる<ref name="Yamamoto1"/>。ただし、桁落ちを防ぐ観点からこの式の通り計算するのではなく、
<center><math>
x_i^{(k+1)} = (1-\omega)x_i^{(k)} + \omega\tilde{x}_i^{(k+1)}
</math></center>
として計算するか、または本節の最後に書かれた式を用いるのがよい。

この漸化式を、上の<math>A=L+D+U</math>を用いて行列で表現すると、
<center><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></center>
となり、この2式から<math>\boldsymbol{\tilde{x}}^{(k+1)}</math>を消去することで、次式が得られる。
<center><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></center>
上式における<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>を反復行列という。

実際の数値計算においては、これを各成分について表した下の式が用いられる。
<center><math>
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)
</math></center>

==収束性==
反復行列の固有値を<math>\lambda</math>とすると、

:<math>
\max|\lambda| \geq |\omega-1| \quad \forall\omega
</math>

が成立することから、少なくとも<math>0<\omega<2</math>でなければSOR法の収束性は保証されない
<ref>{{Cite report |author = 幸谷智紀 |title = 連立一次方程式の解法2 -- 反復法 |date = 2007-10-13 |accessdate = 2018-03-30 |url = http://na-inet.jp/nasoft/chap09.pdf }}</ref>。

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

また、<math>\omega=1</math>のとき[[ガウス＝ザイデル法]]と同じになり<ref name="Yamamoto1"/>、<math>\omega</math>が''1''より小さいとき
[[ガウス＝ザイデル法]]より収束が遅くなる。ただし、[[ガウス＝ザイデル法]]で収束しないような問題には使える
<ref>{{Cite web|和書|url = http://www.yamamo10.jp/yamamoto/lecture/2004/5E/linear_equations/relaxation/html/node6.html |title = SOR法 
|accessdate = 2018-03-30 |date = 2004-12-16}}</ref>。

==加速パラメータ<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>の最適値は、
次の形で得られる<ref>Varga, R. S. (2009). Matrix iterative analysis (Vol. 27). Springer Science & Business Media.</ref>。

:<math>
\omega = \frac{2}{1+\sqrt{1-\rho\left(M_J\right)^2}}
</math>
==近年の研究==
[[共役勾配法]]をはじめとした[[クリロフ部分空間|クリロフ部分空間法]]の普及が進んだことでSOR法の使用が減ってしまったこともあったが<ref name="Yamamoto1"/>、離散勾配法 (構造保存型数値解法の一つ) との関係が明らかになったことで再び注目されている<ref> 宮武勇登, 曽我部知広, & 張紹良. (2017). 微分方程式に対する離散勾配法に基づく線形方程式の数値解法の生成. [[日本応用数理学会]]論文誌, 27(3), 239-249.</ref><ref> 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.</ref>。

== 脚注 ==
<div class="references-small"><references/></div>

== 参考文献 ==
* {{Cite book|和書|author=森正武|authorlink=森正武|year=2002|month=2|title=数値解析|publisher=共立出版|isbn=4-320-01701-3|}}
* [[杉原正顯]], 室田一雄, 線形計算の数理, [[岩波書店]], 2009年.
* 線形方程式の反復解法、 一般社団法人 日本計算工学会 編、藤野清次 著、阿部邦美 著、[[杉原正顯]] 著、[[丸善出版]]、2013年09月。
* 数値線形代数の数理とHPC, 櫻井鉄也, 松尾宇泰, 片桐孝洋編（シリーズ応用数理 / [[日本応用数理学会]]監修, 第6巻）[[共立出版]], 2018.8

== 関連項目 ==
* [[数値解析]]
* [[数値線形代数]]
* [[ヤコビ法]]
* [[ガウス＝ザイデル法]]
{{linear algebra}}

{{デフォルトソート:えすおうああるほう}}
[[Category:緩和法 (反復法)]]
[[Category:応用力学]]
[[Category:数値線形代数]]
[[Category:数学に関する記事|SORえすおうああるほう]]
[[Category:数値解析]]