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のとき必ず収束する。また、formula_33のときガウス＝ザイデル法と同じになり、formula_3が"1"より小さいときガウス＝ザイデル法より収束が遅くなる。ただし、ガウス＝ザイデル法で収束しないような問題には使える。一般に加速パラメータformula_3の値をあらかじめ最適に定めることはできない。そのため、問題ごとに適当な値を選択する必要がある。しかし、formula_3の最適な値を決定することができる例も存在する。それは、係数行列formula_5が、ある基本行列formula_39に対してという形の行列に相似変換することができ、さらにヤコビ法の反復行列formula_41のスペクトル半径formula_42が既知であるときである。なお、上の行列内のformula_43は対角行列である。このとき、SOR法の反復行列のスペクトル半径formula_44が最小となるformula_3の最適値は、次の形で得られる。

出典:wikipedia