SOR法

SOR法（逐次加速緩和法）詳解

SOR法（Successive Over-Relaxation method）とは、連立一次方程式を数値的に解くための反復解法の一種です。ガウス＝ザイデル法を基礎とし、収束を加速させるパラメータω（オメガ）を用いることで、より効率的に解を求めます。本稿では、SOR法の原理、アルゴリズム、収束性、そしてパラメータωの最適化について詳細に解説します。

SOR法の原理

連立一次方程式Ax = bを考えます。ここで、Aはn×nの正方行列、xはn次元ベクトル（未知数）、bはn次元ベクトル（既知数）です。SOR法では、行列Aを以下の様に分解します。

A = L + D + U

ここで、LはAの下三角行列、DはAの対角行列、UはAの上三角行列です。この分解を用いて、ガウス＝ザイデル法と同様の反復式を導出します。ガウス＝ザイデル法では、各未知数xᵢを順番に更新していきますが、SOR法では、この更新量に加速パラメータωを乗じて修正することで、収束速度の向上を目指します。

具体的には、k回目の反復における近似解x⁽ᵏ⁾から、k+1回目の近似解x⁽ᵏ⁺¹⁾への更新は次の式で表されます。

xᵢ⁽ᵏ⁺¹⁾ = (1 - ω)xᵢ⁽ᵏ⁾ + ω(1/aᵢᵢ)(bᵢ - Σⱼ<ᵢ aᵢⱼxⱼ⁽ᵏ⁺¹⁾ - Σⱼ>ᵢ aᵢⱼxⱼ⁽ᵏ⁾)

この式において、ω = 1とするとガウス＝ザイデル法と同一になります。ω > 1のとき、更新量が拡大され、収束が加速する可能性があります。しかし、ωの値が大きすぎると、発散する可能性があるため、適切なωを選択することが重要です。

SOR法の収束性

SOR法の収束性は、加速パラメータωと係数行列Aの性質に依存します。一般的に、0 < ω < 2の範囲でなければ、SOR法の収束は保証されません。特に、Aが正定値対称[[行列]]の場合、0 < ω < 2であれば必ず収束することが知られています（Ostrowskiの定理）。ω = 1、すなわちガウス＝ザイデル法の場合も、Aが対角優位行列であれば収束が保証されます。

加速パラメータωの最適化

SOR法の効率は、加速パラメータωの選択に大きく依存します。最適なωの値は問題ごとに異なり、事前に決定することは困難です。しかし、係数行列Aが特定の条件を満たす場合、最適なωを解析的に求めることができます。例えば、ヤコビ法の反復行列のスペクトル半径ρ(Mⱼ)が既知であれば、最適なωは次の式で計算できます。

ω = 2 / (1 + √(1 - ρ(Mⱼ)²))

近年の研究動向

近年、共役勾配法などのクリロフ部分空間法が普及したことで、SOR法の利用頻度は減少しました。しかし、離散勾配法との関連性が明らかになったことで、再び注目を集めています。特に、構造保存型数値解法が必要とされる分野で、その有効性が再認識されています。

まとめ

SOR法は、連立一次方程式を解くための強力な反復解法です。ガウス＝ザイデル法を改良し、加速パラメータωを用いることで収束速度を向上させます。適切なωの選択が重要であり、問題によっては最適なωを解析的に求めることも可能です。近年の研究では、離散勾配法との関連性から、その有効性が再評価されています。様々な数値計算手法が存在する中で、SOR法は依然として重要な位置を占めていると言えます。

もう一度検索