《共轭梯度法及其基本性质.docx》由会员分享，可在线阅读，更多相关《共轭梯度法及其基本性质.docx（10页珍藏版）》请在三一办公上搜索。
1、共轭梯度法及其基本性质共轭梯度法及其基本性质 预备知识 定义1 设是对称正定矩阵。称是A-共轭的，是指 性质1 设有是彼此共轭的维向量，即 则一定是线性无关的。 证明若有一组数满足 则对一切一定有 注意到是线性无关的 性质 设向量得出一组向量，由此得出：即所有的因此，是线性无关的向量组，则可通过它们的线性组合，而是两两共轭的 证明我们用构造法来证实上面的结论 ：取； ：令 m：令 ，取 取 容易验证：符合性质的要求 性质设从列出发，逐次沿方向，满足： 是两两共轭的，搜索求是任意指定的向量，那么的极小值，所得序 证明由下山算法可知，从出发，沿方向搜索，获得 从而 性质设沿是两两共轭的，则从任意指
2、定的搜索，所得序列满足： 出发，依次，其中是方程组(5.1.1)的解 证明是性质的直接推论，显然成立 由于以对于向量可用是两两共轭的，故是线性无关的所使 线性表出，即存在一组数由于及，得出 ， 于是，再由得出 于是，与得出一样地，我们可以陆续得出： 对比和的表达式可知， 证明完毕 性质是性质的直接推论但它给出了一种求的算法，这种算法称之为共轭方向法结合性质，我们可以得到如下的性质 性质设是上的一组线性无关的向量，则从任意指定的： 出发，按以下迭代产生的序列：取，； ：计算，取； 计算，得出； 如此进行下去，直到第n步： n：计算取 计算，得出 显然： 根据性质可知，不论采用什么方法，只要能够构
3、造个两两共轭的向量作为搜索方向，从任一初始向量出发，依次沿两两共轭的方向进行搜索，经步迭代后，便可得到正定方程组的解 共轭梯度法 算法步骤如下： 预置步任意常数，置，计算，进入主步； ，并令取：指定算法终止主步如果，终止算法，输出；否则下行； 计算： 计算： 置，转入 定理.2.1 由共轭梯度法得到的向量组和具有如下性质： ，其中 通常称之为Krylov子空间 证明用归纳法当时，因为 ， 因此定理的结论成立现在假设定理的结论对成立，我们来证明其对成立 利用等式及归纳假设，有 也又由于 ， 故定理的结论对成立 利用归纳假定有 而由所证知，也成立 与上述子空间正交，从而有定理的结论对利用等式 和
4、并利用归纳法假定和所证之结论，就有 ， 成立；而由的定义得 这样，定理的结论对由归纳法假定知 也成立 进而 于是 再注意到和所证的结论表明，向量组都是线性无关的，因此定理的结论对同样成立 和定理证毕 定理5.2.1表明，向量和分别是Krylov子空间的正交基和共轭正交基由此可见，共轭梯度法最多步便可得到方程组的解因此，理论上来讲，共轭梯度法是直接法 定理5.2.2 用共轭梯度法计算得到的近似解满足 或 其中，义的Krylov子空间 证明 注意到：是方程组的解，是由所定，则和(5.2.3)是等价的，因此我们下面只证明(5.2.3)成立 假定共轭梯度法计算到步出现，那么有 此外，对计算过程中的任一
5、步，有 设是属于表示为 的任一向量，则由定理5.2.1的知，可以， 于是 而 ， 再利用定理5.2.1的就可以推出 于是定理得证 定理证毕 由定理5.2.1，我们容易得出 由此可得 (5.2.4) 另外，从理论上讲，该迭代法经次迭代，便能得到精确解但考虑到计算误差，可以作为无限迭代算法进行计算，直到从而，我们得到如下实用的共轭梯度算法： 预置步任意常数，置，计算，进入主步； ，并令取：指定算法终止为止 主步计算：， 如果，转入否则，终止算法，输出计算结果 计算： 置，转入 注：在算法主步中，引入变量化计算。 ，及，可以简结合程序设计的特点，共轭梯度法可改为如下实用形式： 算法 ； whilei
6、f and else end end 共轭梯度法作为一种实用的迭代法，它主要有下面的优点： 算法中，系数矩阵的作用仅仅是用来由已知向量产生向量，这不仅可充分利用的稀疏性，而且对某些提供矩阵较为困难而由已知向量产生向量是很有益的； 不需要预先估计任何参数就可以计算，这一点不像等； 每次迭代所需的计算，主要是向量之间的运算，便于并行化。 又十分方便的应用问题5.2.3 收敛性分析 将共轭梯度法作为一种迭代法，它的收敛性怎样呢？这是本节下面主要讨论的问题： 定理.2.3 如果即可得到方程组的精确解。 证明 注意到蕴含着子空间 而且，则共轭梯度法至多迭代步的维数不会超过，由定理.2.1即知定理的结论成
7、立。 定理证毕 定理523表明，若线性方程组的系数矩阵与单位相关一个秩的矩阵，而且很小时，则共轭梯度法将会收敛得很快。 定理524 用共轭梯度法求得的有如下的误差估计 其中 证明由定理521可知，对任意的，有 记，则是常数项为1的次实系数多项式。令为所有常数项为1的次数不超过的实系数多项式的全体，则由定理522和引理511得 其中是的特征值。由Chebyshev多项式逼近定理及Chebyshev多项式的性质，定义在-1，1区间上的次Chebyshev多项式：是所有常数项为1的次数不超过的实系数多项式中，在-1，1上与“0”的偏差值最小的多项式。且偏差值为1，对应的交错点组为：。因此，多项式 是中在上与“0”的偏差值最小的多项式。即 于是，我们有 因此，定理得证。 定理证毕 虽然定理525所给出的估计是十分粗糙的，而且实际计算时其收敛速度往往要比这个估计快得多，但是它却提示了共轭梯度法的一个重要的性质：只要线性方程组的系数矩阵是十分良态的，则共轭梯度法
