共轭梯度法及其基本性质

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

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

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

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

5、立假定共轭梯度法计算到步出现，那么有此外，对计算过程中的任一步，有设是属于的任一向量，则由定理5.2.1的（）知，可以表示为，于是而.，再利用定理 5.2.1的（）就可以推出于是定理得证定理证毕由定理 5.2.1 ，我们容易得出由此可得(5.2.4)另外，从理论上讲，该迭代法经次迭代，便能得到精确解但考虑到计算误差，可以作为无限迭代算法进行计算，直到为止从而，我们得到如下实用的共轭梯度算法：预置步 任意，计算，并令取：指定算法终止常数，置，进入主步；主步 （）计算：，.（）如果，转入（ 3）否则，终止算法，输出计算结果（）计算：（）置，转入（ 1）注：在算法主步中，引入变量，及，可以简化计算。

6、结合程序设计的特点，共轭梯度法可改为如下实用形式：算法··（解对称正定方程组：实用共轭梯度法）；whileandifelseendend.共轭梯度法作为一种实用的迭代法，它主要有下面的优点：算法中，系数矩阵的作用仅仅是用来由已知向量产生向量，这不仅可充分利用的稀疏性，而且对某些提供矩阵较为困难而由已知向量产生向量又十分方便的应用问题是很有益的；不需要预先估计任何参数就可以计算，这一点不像等；每次迭代所需的计算，主要是向量之间的运算，便于并行化。5.2.3收敛性分析将共轭梯度法作为一种迭代法，它的收敛性怎样呢？这是本节下面主要讨论的问题：定理 .2.3如果而且，则共轭梯度法至

7、多迭代步即可得到方程组的精确解。证明注意到蕴含着子空间的维数不会超过，由定理 .2.1 即知定理的结论成立。定理证毕定理 5·2·3 表明，若线性方程组（ 5·1·1）的系数矩阵与单位相关一个秩的矩阵，而且 很小时，则共轭梯度法将会收敛得很快。定理 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”的偏差值最小的多项式。即于是，我们有因此，定理得证。定理证毕虽然定理 5· 2&