SOR法

出典: フリー百科事典『ウィキペディア(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]

脚注[編集]

  1. ^ a b c d e f g 山本哲朗『数値解析入門』サイエンス社〈サイエンスライブラリ 現代数学への入門 14〉、2003年6月、増訂版。ISBN 4-7819-1038-6
  2. ^ 幸谷智紀 (2007-10-13). 連立一次方程式の解法2 -- 反復法 (Report). http://na-inet.jp/nasoft/chap09.pdf 2018年3月30日閲覧。. 
  3. ^ SOR法” (2004年12月16日). 2018年3月30日閲覧。
  4. ^ Varga, R. S. (2009). Matrix iterative analysis (Vol. 27). Springer Science & Business Media.
  5. ^ 宮武勇登, 曽我部知広, & 張紹良. (2017). 微分方程式に対する離散勾配法に基づく線形方程式の数値解法の生成. 日本応用数理学会論文誌, 27(3), 239-249.
  6. ^ 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.

参考文献[編集]

関連項目[編集]