連立1次方程式：正規方程式に対する共役勾配法

CGNR†

共役勾配法では正定値対称行列のみを対象としているが， 非対称行列には対応できないのだろうか． 前処理のところで元の方程式と等価になるように係数行列を変形させて条件数を改善したが， 同様にして非対称行列を対称行列にする前処理をすれば簡単に対応は可能である． つまり，

と変形すると，Aが非対称行列でもは(半)正定値対称行列になる． また，Aは正方行列でなくてもよく，の任意の行列で構成される正規方程式(Normal equations)に共役勾配法を適用できる． この式を方程式に当てはめると，

となり，を最小化する問題に帰着する． これは最小自乗法となる．この方法は一般的に未知数の数よりも方程式の数が多い問題に用いられる． つまり，において，となるような場合である． このような問題はNR(Normal equations to minimize the Residual)と呼ばれる． そのため，により対称行列を作り共役勾配法(CG法)を使って解く方法はCGNR法と呼ばれる．

CGNE†

CGNRとは別の方法として，と置き，

をについて共役勾配法で解き， からを求める方法もある． CGNR法と同様にして方程式に当てはめると，

今，，つまり，方程式の数よりも未知数の数が多い問題を考える． 解の一つをとすると，より，

となり，についてを最小化する問題となる． この方法はであるunderdeterminedな線形システムに用いられる． このような問題はNE(Normal equations to minimize the Error)と呼ばれ， これを共役勾配法を使って解く方法はCGNE法と呼ばれる．

CGNRとCGNEの収束性†

CGNRやCGNEを使うことで共役勾配法を正規方程式に適用できるが， これらの方法は特に条件数が大きいときの収束性に問題を抱えている． の条件数がのときの，の条件数(2乗ノルムの条件数)を求めてみる．

スペクトル半径と行列の2乗ノルムの間の関係式

を用いると，

このようにの条件数はの条件数の2乗となるので， が大きいと収束性はさらに悪化してしまう． 一方で2乗ノルムの条件数が1に近い場合は，とてもよい解法である．

参考文献†

• Yousef Saad, Iterative methods for sparse linear systems 2nd ed., SIAM, 2003.