next up previous
Next: 3 本日すべきこと Up: 応用数理実験 連立 次方程式に対する CG Previous: 1 連絡事項

2 講義の内容の復習

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

$\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$ の性質に強く依存する。


next up previous
Next: 3 本日すべきこと Up: 応用数理実験 連立 次方程式に対する CG Previous: 1 連絡事項
Masashi Katsurada
平成16年11月28日