共役勾配法

共役勾配法詳解

共役勾配法 (Conjugate Gradient method, CG法) は、対称正定値行列を係数とする連立一次方程式を解くための強力なアルゴリズムです。特に、直接法では計算コストが大きすぎるような大規模な疎行列を扱う際に威力を発揮します。このような問題は、偏微分方程式の数値解法など、様々な科学技術計算分野で頻繁に現れます。

共役勾配法の基礎

n元連立一次方程式 Ax = b を考えます。ここで、A は対称正定値行列です。共役勾配法は、この方程式の解 x を反復的に求める方法です。

共役ベクトル

2つの非零ベクトル u, v が、以下の条件を満たすとき、A に関して共役であるといいます。

`uᵀAv = 0`

ここで、ᵀ は転置を表します。A が対称正定値であるため、この条件は、A を用いて定義された内積 `(u, v)A = uᵀAv` に関して u と v が直交することと同値です。

直接法としての共役勾配法

n 個の互いに A に関して共役なベクトル p₁, p₂, ..., pₙ を考えます。これらのベクトルは Rⁿ の基底を形成するため、解 x はこれらのベクトルの線形結合で表せます。

`x = α₁p₁ + α₂p₂ + ... + αₙpₙ`

係数 αₖ は、共役性を利用して以下の式で効率的に計算できます。

`αₖ = (pₖᵀb) / (pₖᵀApₖ)`

この方法では、事前に n 個の共役ベクトルを求める必要があります。大規模問題に対しては計算コストが大きいため、通常は反復法として利用されます。

反復法としての共役勾配法

反復法では、n 個の共役ベクトルを全て計算する代わりに、解 x の良い近似を効率的に得られるように共役ベクトル列を生成します。

初期値 x₀ = 0 から出発し、残差 rₖ = b - Axₖ を用いて、各ステップで共役な探索方向 pₖ を決定します。最急降下法では、残差の方向に進んでいきますが、共役勾配法では、残差と共役な方向へ進むことで、より効率的に解に近づきます。

各ステップでの更新は、以下の式で行われます。

`αₖ = (rₖᵀrₖ) / (pₖᵀApₖ)`

`xₖ₊₁ = xₖ + αₖpₖ`

`rₖ₊₁ = rₖ - αₖApₖ`

`βₖ = (rₖ₊₁ᵀrₖ₊₁) / (rₖᵀrₖ)`

`pₖ₊₁ = rₖ₊₁ + βₖpₖ`

残差のノルムが十分小さくなったら、反復を終了します。

アルゴリズム

上記の反復手順をまとめたアルゴリズムは以下のようになります。

1. 初期値 x₀ を設定 (例: x₀ = 0)
2. r₀ = b - Ax₀ を計算
3. p₀ = r₀ を設定
4. k = 0, 1, 2, ... に対して以下の計算を繰り返す
- αₖ = (rₖᵀpₖ) / (pₖᵀApₖ) を計算
- xₖ₊₁ = xₖ + αₖpₖ を計算
- rₖ₊₁ = rₖ - αₖApₖ を計算
- ‖rₖ₊₁‖ が十分小さければ終了
- βₖ = (rₖ₊₁ᵀrₖ₊₁) / (rₖᵀrₖ) を計算
- pₖ₊₁ = rₖ₊₁ + βₖpₖ を計算
5. xₖ₊₁ を解の近似値とする

前処理

前処理は、係数行列 A の条件数を改善することで、共役勾配法の収束を加速させるテクニックです。前処理行列 P を用いて、変換された方程式 P⁻¹AP⁻ᵀx' = P⁻¹b を解くことで、収束速度を向上させます。

正規方程式

任意の実行列 A に対して、ATA は対称半正定値行列となるため、正規方程式 ATAx = ATb を解くことで、共役勾配法を一般の行列に適用できます (CGNR 法)。しかし、条件数の悪化により収束が遅くなる傾向があるため、CGLS や LSQR などの改良された手法が提案されています。

まとめ

共役勾配法は、大規模な連立一次方程式を効率的に解くための強力な反復解法です。そのアルゴリズムは比較的シンプルでありながら、様々な改良手法と組み合わせることで、様々な問題に適用可能です。前処理や正規方程式への適用など、更なる高度な手法を理解することで、より複雑な問題への対処が可能になります。

もう一度検索