共轭梯度法及其基本性质

1、共轭梯度法及其根本性质预备知识定义1 设是对称正定矩阵。称是A-共轭的，是指性质1 设有是彼此共轭的维向量，即那么一定是线性无关的。证明假设有一组数满足那么对一切一定有注意到，由此得出：即所有的因此，是线性无关的性质设向量是线性无关的向量组，那么可通过它们的线性组合得出一组向量，而是两两共轭的证明我们用构造法来证实上面的结论：取；：令，取m：令取容易验证：符合性质的要求性质设是两两共轭的，是任意指定的向量，那么从出发，逐次沿方向搜索求的极小值，所得序列，满足：证明由下山算法可知，从出发，沿方向搜索，获得从而性质设是两两共轭的，那么从任意指定的出发，依次沿搜索，所得序列满足：，其中是方程组(5.

2、1.1)的解证明是性质的直接推论，显然成立由于是两两共轭的，故是线性无关的所以对于向量可用线性表出，即存在一组数使由于及，得出，于是，再由得出于是，与得出一样地，我们可以陆续得出：比照和的表达式可知，证明完毕性质是性质的直接推论但它给出了一种求.的算法，这种算法称之为共轭方向法结合性质，我们可以得到如下的性质性质设是上的一组线性无关的向量，那么从任意指定的出发，按以下迭代产生的序列：取，；：计算，取；计算，得出；如此进行下去，直到第n步：n：计算取计算，得出显然：根据性质可知，不管采用什么方法，只要能够构造个两两共轭的向量作为搜索方向，从任一初始向量出发，依次沿两两共轭的方向进行搜索，经步迭代

3、后，便可得到正定方程组的解共轭梯度法算法步骤如下：预置步任意，计算，并令取：指定算法终止常数，置，进入主步；主步 如果，终止算法，输出；否那么下行；计算：计算：置，转入定理.2.1由共轭梯度法得到的向量组和具有如下性质：，其中            5.2.1通常称之为Krylov子空间证明用归纳法当时，因为，因此定理的结论成立现在假设定理的结论对成立，我们来证明其对也成立利用等式及归纳假设，有又由于，故定理的结论对成立利用归纳假定有而由所证知，与上述子空间正交，从而有定理的结论对也成

4、立利用等式和，并利用归纳法假定和所证之结论，就有成立；而由的定义得这样，定理的结论对也成立由归纳法假定知进而于是再注意到和所证的结论说明，向量组和都是线性无关的，因此定理的结论对同样成立定理证毕定理5.2.1说明，向量和分别是Krylov子空间的正交基和共轭正交基由此可见，共轭梯度法最多步便可得到方程组的解因此，理论上来讲，共轭梯度法是直接法定理5.2.2用共轭梯度法计算得到的近似解满足             5.2.或    

5、60;  5.2.其中，是方程组的解，是由5.2.1所定义的Krylov子空间证明注意到：，那么5.2.2和(5.2.3)是等价的，因此我们下面只证明(5.2.3)成立假定共轭梯度法计算到步出现，那么有此外，对计算过程中的任一步，有设是属于的任一向量，那么由定理5.2.1的知，可以表示为，于是而，再利用定理5.2.1的就可以推出于是定理得证定理证毕由定理5.2.1，我们容易得出由此可得                 

6、;       (5.2.4)另外，从理论上讲，该迭代法经次迭代，便能得到精确解但考虑到计算误差，可以作为无限迭代算法进行计算，直到为止从而，我们得到如下实用的共轭梯度算法：预置步任意，计算，并令取：指定算法终止常数，置，进入主步；主步计算：，如果，转入3否那么，终止算法，输出计算结果 计算：置，转入1注：在算法主步中，引入变量，及，可以简化计算。结合程序设计的特点，共轭梯度法可改为如下实用形式：算法··解对称正定方程组：实用共轭梯度法；while and if elseendend共轭梯度法作为一种实用的迭代法，

7、它主要有下面的优点：算法中，系数矩阵的作用仅仅是用来由向量产生向量，这不仅可充分利用的稀疏性，而且对某些提供矩阵较为困难而由向量产生向量又十分方便的应用问题是很有益的；不需要预先估计任何参数就可以计算，这一点不像等；每次迭代所需的计算，主要是向量之间的运算，便于并行化。5.2.3 收敛性分析将共轭梯度法作为一种迭代法，它的收敛性怎样呢？这是本节下面主要讨论的问题：定理.2.3如果而且，那么共轭梯度法至多迭代步即可得到方程组的精确解。证明注意到蕴含着子空间的维数不会超过，由定理.2.1即知定理的结论成立。定理证毕定理5·2·3说明，假设线性方程组5·1·1

8、的系数矩阵与单位相关一个秩的矩阵，而且很小时，那么共轭梯度法将会收敛得很快。定理5·2·4 用共轭梯度法求得的有如下的误差估计               5·2·5其中证明 由定理5·2·1可知，对任意的，有记，那么是常数项为1的次实系数多项式。令为所有常数项为1的次数不超过的实系数多项式的全体，那么由定理5·2·2和引理5·1·1得其中是的特征值。由Chebyshev多项式逼近定理及Chebyshev多项式的性质，定义在-1，1区间上的次Chebyshev多项式：是所有常数项为1的次数不超过的实系数多项式中，在-1，1上与“0的偏差值最小的多项式。且偏差值为1，对应的交错点组为：。因此，多项式是中在上与“0的偏差值最小的多项式。即于是，我们有因此，定理得证。定理