出典: フリー百科事典『ウィキペディア(Wikipedia)』
SOR法︵SORほう、英: Successive Over-Relaxation、逐次加速緩和法︶とは
元連立一次方程式を
反復法で解く手法の一つであり、
ガウス=ザイデル法に加速パラメータを導入してその修正量を拡大することで、
更なる加速を図った手法である[1]。
次正方行列は、上三角行列、
下三角行列、対角行列の和に分離すると、
と書ける。
非対角成分に相当する項をすべて右辺に移項し、すべての量に
各段階で得られている最新のデータを代入するようにする(ガウス=ザイデル法)。こうして計算された値を
とすると、は次の形となる[1]。
この値を次段でそのまま採用せずに、ガウス=ザイデル法で本来修正される量に1より大きい
加速パラメータ︵[1]では緩和因子、緩和係数と呼ばれている︶を乗じてこの修正量を拡大し、これを前段の近似値に加えることで、新たな値は
とできる[1]。ただし、桁落ちを防ぐ観点からこの式の通り計算するのではなく、
として計算するか、または本節の最後に書かれた式を用いるのがよい。
この漸化式を、上のを用いて行列で表現すると、
となり、この2式からを消去することで、次式が得られる。
上式におけるの係数
を反復行列という。
実際の数値計算においては、これを各成分について表した下の式が用いられる。
反復行列の固有値をとすると、
が成立することから、少なくともでなければSOR法の収束性は保証されない
[2]。
さらに、正定値対称行列を係数にもつ方程式に対するSOR法は、
加速パラメータがのとき必ず収束する︵Ostrowskiの定理︶[1]。
また、のときガウス=ザイデル法と同じになり[1]、が1より小さいとき
ガウス=ザイデル法より収束が遅くなる。ただし、ガウス=ザイデル法で収束しないような問題には使える
[3]。
加速パラメータの選択
[編集]
一般に加速パラメータの値をあらかじめ最適に定めることはできない。そのため、問題ごとに適当な値を選択する必要がある。
しかし、の最適な値を決定することができる例も存在する。それは、係数行列が、ある基本行列に
対して
という形の行列に相似変換することができ、さらにヤコビ法の反復行列の
スペクトル半径が既知であるときである。
なお、上の行列内のは対角行列である。
このとき、SOR法の反復行列のスペクトル半径が最小となるの最適値は、
次の形で得られる[4]。
共役勾配法をはじめとしたクリロフ部分空間法の普及が進んだことでSOR法の使用が減ってしまったこともあったが[1]、離散勾配法 (構造保存型数値解法の一つ) との関係が明らかになったことで再び注目されている[5][6]。
(一)^ abcdefg山本哲朗﹃数値解析入門﹄︵増訂版︶サイエンス社︿サイエンスライブラリ 現代数学への入門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.