SOR法

SOR法(、逐次加速緩和法)とは
formula_1元連立一次方程式formula_2を
反復法で解く手法の一つであり、
ガウス＝ザイデル法に加速パラメータformula_3を導入してその修正量を拡大することで、
更なる加速を図った手法である。
反復のスキーム.
formula_1次正方行列formula_5は、上三角行列formula_6、
下三角行列formula_7、対角行列formula_8の和に分離すると、
formula_9
と書ける。
非対角成分に相当する項をすべて右辺に移項し、すべての量formula_10に
各段階で得られている最新のデータを代入するようにする(ガウス＝ザイデル法)。こうして計算された値をformula_11
とすると、formula_12は次の形となる。
formula_13
この値を次段でそのまま採用せずに、ガウス＝ザイデル法で本来修正される量formula_14に1より大きい
加速パラメータ（では緩和因子、緩和係数と呼ばれている）formula_3を乗じてこの修正量を拡大し、これを前段の近似値formula_16に加えることで、新たな値は
formula_17
とできる。ただし、桁落ちを防ぐ観点からこの式の通り計算するのではなく、
formula_18
として計算するか、または本節の最後に書かれた式を用いるのがよい。
この漸化式を、上のformula_19を用いて行列で表現すると、
formula_20
となり、この2式からformula_11を消去することで、次式が得られる。
formula_22
上式におけるformula_23の係数
formula_24を反復行列という。
実際の数値計算においては、これを各成分について表した下の式が用いられる。
formula_25
収束性.
反復行列の固有値をformula_26とすると、
が成立することから、少なくともformula_28でなければSOR法の収束性は保証されない
さらに、正定値対称行列formula_5を係数にもつ方程式formula_2に対するSOR法は、
加速パラメータformula_3がformula_28のとき必ず収束する（Ostrowskiの定理）。
また、formula_33のときガウス＝ザイデル法と同じになり、formula_3が"1"より小さいとき
ガウス＝ザイデル法より収束が遅くなる。ただし、ガウス＝ザイデル法で収束しないような問題には使える
加速パラメータformula_3の選択.
一般に加速パラメータformula_3の値をあらかじめ最適に定めることはできない。そのため、問題ごとに適当な値を選択する必要がある。
しかし、formula_3の最適な値を決定することができる例も存在する。それは、係数行列formula_5が、ある基本行列formula_39に
対して
という形の行列に相似変換することができ、さらにヤコビ法の反復行列formula_41の
スペクトル半径formula_42が既知であるときである。
なお、上の行列内のformula_43は対角行列である。
このとき、SOR法の反復行列のスペクトル半径formula_44が最小となるformula_3の最適値は、
次の形で得られる。
近年の研究.
共役勾配法をはじめとしたクリロフ部分空間法の普及が進んだことでSOR法の使用が減ってしまったこともあったが、離散勾配法 (構造保存型数値解法の一つ) との関係が明らかになったことで再び注目されている。