SOR法

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索

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

反復のスキーム[編集]

正方行列は、上三角行列、 下三角行列対角行列の和に分離すると、

と書ける。

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

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

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

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

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

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

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

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


収束性[編集]

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

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

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

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

加速パラメータの選択[編集]

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

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

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

このとき、SOR法の反復行列のスペクトル半径が最小となるの最適値は、 次の形で得られる。


脚注[編集]

参考文献[編集]


関連項目[編集]