|TOP Page|
CG法(Conjugate Gradient Methods)はM.R.HestenesとE.Stiefelによって1952年に提案された方法である[1]。
CG法は正定値対称行列に対して使われる連立一次方程式を反復法で解くための手法である。
ベクトルの内積を
のように書く。
実行列が正定値対称とは、
ということであり、が対称であるということは、
が成り立つということである。
今、次のような線形同次方程式を解くとする。
CG法は回目の反復において、次のようにこの方程式の解
や誤差
を用いて定義される誤差の
ノルム
(等号成立は
のとき)
を最小化するような近似解を部分空間
の中から見つける方法である。但し、
はクリロフ部分空間(Krylov Subspace)
である。
つまりCG法は次のような連立一次方程式の近似解を探すための方法である。
![]() |
このように部分空間の中で
との
ノルムで表される距離が極値をとるとき、明らかに次のような直交性の関係が成り立つ。
但し、行列によって定義される内積とした。これを用いるとCG法は次のように表すことができる。
![]() |
但しとは次の関係を表している。
つまりCG法は解を部分空間
に行列により定義される内積において正射影する方法であるともいえる。クリロフ部分空間
は有限次元部分空間であるから、完備な線形空間である。よってLax-Milgramの定理より、このような射影は常に存在する。
(ユークリッド空間で表した)CG法の反復解の様子 |
---|
![]() |
また、回反復時における残差
は
であるから、CG法は次のように解を探すともいえる。
これは残差が部分空間
に直交するように、
の中から解を探すということを意味している。
CG法はクリロフ部分空間の正規直交基底を作る方法である、Lanczos法と深い関係にある。
回目の反復解
から
回目の反復解
への解の増分を係数
とベクトル
を用いて次のように書くとする。
は解の増分の方向を決めることから探索方向ベクトルと呼ぶ。
回目の反復解
への解の更新ベクトル
は次のように解
の残差
、係数
、1つ前の解の更新ベクトル
を用いて次のように決定する
係数、
をどのように決定するのかを以下で説明する。
前の議論からCG法では厳密解と反復解
の差がクリロフ部分空間
に
ノルムにおいて直交していた。つまり、
よって厳密解との差がクリロフ部分空間
と
ノルムにおいて直交する空間の中にあるのだから、この
に
ノルムで直交する空間の中から次の反復解
への解の更新ベクトル
を決めたほうが
が厳密解に近くなるはずである。
後に示すようにの1つ前の探索方向ベクトル
は直交させようとする部分空間
に入っている。つまり、
よって、探索方向ベクトルが
に
ノルムで直交するためには最低
に
ノルムで直交することが必要条件である。つまり、
![]() |
後に示すように、上のように選んだ探索方向はだけでなく、
空間に
ノルムで直交する。
上の残差と1つ前の探索方向ベクトルから探索方向ベクトルを定める式、
から、残差をクリロフ部分空間
と
ノルムで直交する空間に射影することで新しい探索方向ベクトル
が得られることを意味している。
またこの式から、を決定することができる。
この式と2つ探索方向が直交する式に代入すると、パラメータ
は次のようになる。
さらに、後に示す残差の直交性の関係式を用いると、
これにより、さらに係数は次の様に表すことができる。
係数は次のステップでのポテンシャル
を最小化するように決められる。次のステップにおけるポテンシャル
は
行列は対称であったので、
となる。よって
ポテンシャルが最小値をとるとき, ポテンシャル
は極値をとるので
よってこれを計算すると
となるので係数は次のようになる。
さらに、後に示す残差の直交性の関係式を用いると、
これにより、さらに係数は次の様に表すことができる。
これらを用いるとCG法のアルゴリズムは次のようになる
  1.  
,
  2.  
  3.     
  4.     
  5.     
  6.     
  7.     
  8.  
問題の離散化は有限要素法を用いている。
DOWNLOAD | CG.zip |
---|
OS:WindowsXP, Windows2000 開発環境:VC++ 2005 言語:C++
プログラムを走らせると、プログラムを動かしたフォルダにconv_history.datというファイルができるはずである。これは収束の様子を記録したファイルでgnuplotで次のようなコマンドを打つとグラフとして見ることができる。
set style data line set logscale y plot 'conv_history.dat'
次のようなグラフが表示されるはずである。
この収束のグラフについては共役勾配法の収束の中に詳しく書いてある。
CG法はクリロフ部分空間法の一種である。クリロフ部分空間法とは、クリロフ部分空間の中でもっとも解に近い近似解を求める方法である。
以下ではCG法がクリロフ部分空間法であることを証明する
ただし部分空間については
とする。
数学的帰納方を使って証明する
以上から数学的帰納法により命題は証明される。
ところでk回目の反復時における解とすると、
であるから
であることがわかる。
よってCG法はクリロフ部分空間の中で解を探索するクリロフ部分空間法であるということがわかる。
以下では残差rが直交するという条件からCG法が必ずn解の反復で収束するということを示す。
数学的帰納法を使って証明する
以上から数学帰納法を用いれば命題は証明される
数学的帰納法で証明する
以上から数学帰納法を用いれば命題は証明される
ここで残差ベクトルの列は互いに直交する線形独立なベクトルであることがわかった。線形独立なベクトルの数の最大値はベクトルの次元数
であるので、残差ベクトルの列の数はベクトルの次元数
より大きくならないことがわかる。このことから、理論上では
CG法は必ずベクトルの次元数n回以下の反復数で収束する
ということがいえる。但し、これはあくまでこれは理論上の話でCG法は丸め誤差の影響を強くうけるので、計算機上ではCG法はn回の反復で完全に収束することはない。
実用的な収束については共役勾配法の収束の中に詳しく書いてある。
係数が複素数の場合は係数行列は対称行列ではなく、エルミート行列(Hermetian Matrix)でなくてはならない。つまり
この場合にかぎり、内積は実数となる。また、固有値も全て実数となる。
係数行列がエルミート行列でなく、対称行列である場合はCOCG法(Conjugate Orhogonal Conjugate Gradient Method)などを使って解くことができる。
またそうでない場合はCGNR法(Conjugate Non-Linear Method)、などを用いて解く。
共役勾配法 (シリーズ新しい応用の数学 (17)) |
戸川隼人 著 |
[1]Hestenes, Magnus R.; Stiefel, Eduard (December, 1952). "Methods of Conjugate Gradients for Solving Linear Systems". Journal of Research of the National Bureau of Standards 49 (6).