SOR法

SOR法（SORほう、、逐次加速緩和法）とは
元連立一次方程式を
反復法で解く手法の一つであり、
ガウス＝ザイデル法に加速パラメータを導入してその修正量を拡大することで、
更なる加速を図った手法である。

反復のスキーム
次正方行列は、上三角行列、
下三角行列、対角行列の和に分離すると、

と書ける。

非対角成分に相当する項をすべて右辺に移項し、すべての量に
各段階で得られている最新のデータを代入するようにする(ガウス＝ザイデル法)。こうして計算された値を
とすると、は次の形となる。

この値を次段でそのまま採用せずに、ガウス＝ザイデル法で本来修正される量に1より大きい
加速パラメータ（では緩和因子、緩和係数と呼ばれている）を乗じてこの修正量を拡大し、これを前段の近似値に加えることで、新たな値は

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

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

この漸化式を、上のを用いて行列で表現すると、

となり、この2式からを消去することで、次式が得られる。

上式におけるの係数
を反復行列という。

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

収束性
反復行列の固有値をとすると、

が成立することから、少なくともでなければSOR法の収束性は保証されない
。

さらに、正定値対称行列を係数にもつ方程式に対するSOR法は、
加速パラメータがのとき必ず収束する（Ostrowskiの定理）。

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

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

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

という形の行列に相似変換することができ、さらにヤコビ法の反復行列の
スペクトル半径が既知であるときである。
なお、上の行列内のは対角行列である。

このとき、SOR法の反復行列のスペクトル半径が最小となるの最適値は、
次の形で得られるVarga, R. S. (2009). Matrix iterative analysis (Vol. 27). Springer Science & Business Media.。

近年の研究
共役勾配法をはじめとしたクリロフ部分空間法の普及が進んだことでSOR法の使用が減ってしまったこともあったが、離散勾配法 (構造保存型数値解法の一つ) との関係が明らかになったことで再び注目されている 宮武勇登, 曽我部知広, & 張紹良. (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.。

 脚注 

 参考文献 

 杉原正顯, 室田一雄, 線形計算の数理, 岩波書店, 2009年.
 線形方程式の反復解法、 一般社団法人 日本計算工学会 編、藤野清次 著、阿部邦美 著、杉原正顯 著、丸善出版、2013年09月。
 数値線形代数の数理とHPC, 櫻井鉄也, 松尾宇泰, 片桐孝洋編（シリーズ応用数理 / 日本応用数理学会監修, 第6巻）共立出版, 2018.8

 関連項目 
 数値解析
 数値線形代数
 ヤコビ法
 ガウス＝ザイデル法

Category:緩和法 (反復法)
Category:応用力学
Category:数値線形代数
SORえすおうああるほう
Category:数値解析