1 講義の内容の復習

代表的な反復法として、きょうやくこうばいほう共役勾配 法 (conjugate gradient method, 略して CG 法) を取 り上げる¹。これは $A$ が 正定値対称行列である場合に利用可能な方法である²。

$\underline{\hbox{\textbf{CG 法のアルゴリズム:}}}$

  初期ベクトル ${\bf x_{0}}$ をとる$;\;$  目標とする相対残差 $\varepsilon$ を決める$;$ 

${\bf r_{0}} := {\bf b} - A{\bf x_{0}}; \; {\bf p_{0}}:={\bf r_{0}};$ 

for $k:=0,1,\cdots$    until $\Vert{\bf r_{k}}\Vert\le \varepsilon\Vert{\bf b}\Vert \;$ do 

    begin 

    $\alpha_k := \dsp\frac{({\bf r_{k}},{\bf p_{k}})}{({\bf p_{k}},A{\bf p_{k}})};$ 

${\bf x_{k+1}}:={\bf x_{k}}+\alpha_k {\bf p_{k}};$ 

${\bf r_{k+1}}:={\bf r_{k}}-\alpha_k A{\bf p_{k}};$ 

    $\beta_k:=-\dsp\frac{({\bf r_{k+1}},A{\bf p_{k}})}{({\bf p_{k}},A{\bf p_{k}})};$ 

${\bf p_{k+1}}:={\bf r_{k+1}}+\beta_k {\bf p_{k}};$ 

end

ここに掲げた「古典的な」CG 法では、実際に解ける問題がかなり限定され る。近年は前処理 (preconditioning) と呼ばれるテクニックを併 用した前処理つき共役勾配法 (preconditioned CG method, 略し てPCG 法) が広く使われている。前処理でやっていることは、与え られた問題を、固有値が密集している係数行列を持つ問題に変換することであ ると言えるが、具体的にどのような前処理を採用すべきかは、係数行列 $A$ の性質に強く依存する。