共轭梯度法和基本性质

共轭梯度法及其基本性质预备知识定义1设心初是对称正定矩阵。称匹些是A-共轭的，是指是彼此共轭的芝向量，即［证明］若有一组数性*满足则对一切一定有注意到就虹2是线性无关的.，由此得出:%=0.即所有的国=0.因此，座主性质2设向是彼此共轭的芝向量，即［证明］若有一组数性*满足则对一切一定有注意到就虹2是线性无关的.，由此得出:%=0.即所有的国=0.因此，座主性质2设向量既「即…冶视是线性无关的向量组，则可通过它们的线性组合得出一组向量处次1广"％是两两共轭的.性质1设有所如…八（幽E定是线性无关的。［证明］我们用构造法来证实上面的结论.Sm：令取容易验证：&，芦1广"』符合性质2的要求.性质3设|为，儿…，残|是两两A—共轭的，也气是任意指定的向量，那么姻出发:逐次沿方向砧，…还搜索求丽=2g的极小值，所得［证明］由下山算法可知，从园出发，沿国方向搜索，获得从而

出发，依次性质4设出发，依次性质4设”挪/,"I|是两两A共轭的，则从任意指定的左芝沿的土"、外T搜索，所得序列阡”心满足:其中曰是方程组(5.1.1)其中曰是方程组(5.1.1)的解.(2)［证明］(1)是性质3的直接推论，显然成立.(2)由于|乩，西-1是两两A共轭的，故|知F/-%-】是线性无关的.所以对于向量|&一列可用|乩书/线性表出，即存在一组数

对比田和园的表达式可知，对比田和园的表达式可知，证明完毕性质4是性质3的直接推论.但它给出了一种求（5.1.1）的算法，这种算法称之为共轭方向法.结合性质2,我们可以得到如下的性质5.如此进行下去，直到第n步:根据性质4可知，不论采用什么方法，只要能够构造囹个两两A共轭的向量作为搜索方向，从任一初始向量出发，依次沿两两A共轭的方向进行搜索，经回步迭代后，便可得到正定方程组匹邑的解.

共轭梯度法算法步骤如下:［预置步］任意叫*舟I,计算脩7-生I,并令取：I处/|指定算法终止常数扑，置虹=听进入主步:［主步］(1)如果欧"I,终止算法，输出|战5，|：否则下行:(2)计算:(2)计算:(4)置"=把十1|，转入(1).通常称之为Krylov子空间.［证明］用归纳法.当时，因为PLF曰4二尸D-口□他口，凡二门+编如,Pori=rori=4（肖口一处）二尸口『口一Qoro^Pa=°因此定理的结论成立.现在假设定理的结论对旧成立，我们来证明其对页也成立.利用等式脆1二/一 及归纳假设，有pXw=p"-勤气=S0<:<k-l又由于故定理的结论（1）对由成立.利用归纳假定有疑血，…用二span{pOr--,pk}T而由（1）所证知，应与上述子空间正交，从而有定理的结论（2）对三!也成立.利用等式并利用归纳法假定和（2）所证之结论，就有

IP：如山二上EiS-切）十成药为h,i二1处成立；而由网的定义得歹3也^=(0+S**Aa&=底1曲\-忒也^=。这样，定理的结论（3）对电也成立.由归纳法假定知S*E就其6正+1）二乎做!虹&"・・工与』进而于是g=伞R弥（工土,上+2）二中帛PW=膈+扁■#RE +2）=疑血）再注意到（2）再注意到（2）和（3）所证的结论表明，向量组广"1,…刀+1都是线性无关的，因此定理的结论（4）对5同样成立.定理证毕定理5.2.1表明，向量"办…心!和树0广"」分别是Krylov子空间盛正司的正交基和共轭正交基.由此可见，共轭梯度法最多回步便可得到方程组的解园.因此，理论上来讲，共轭梯度法是直接法.定理5.2.2用共轭梯度法计算得到的近似解园满足

例X）例X）二血伽N）：x5 同(5.2.2)(5.2.3)其中|l■疽I,兄!是方程组由=M的解.k叫占相I是由（5.2.1）所定义的Krylov子空间.证明注意到：冼兀=”—iQ’&x一孔）|,贝^（5.2.2）和（5.2.3）是等价的，因此我们下面只证明（5.2.3）成立.假定共轭梯度法计算到回步出现那么有假定共轭梯度法计算到回步出现那么有=册+冲"5+.T%iPt此外，对计算过程中的任一步E如二而+%处+…+淳3声1卜1E财+尤（&岳先）.设图是属于|曲&（&%先）|的任一向量，则由定理5.2.1的（4）知，园可以表示为应二工口+知气+ViPi+.・・+Yjc-iPk-ik.-二二(％-丫口)胃口+怎］-片)召1+…+0*1-斥♦)夕ai+〃曷+，,■+L战二%兴+…+知1久-1再利用定理5.2.1的（3）就可以推出I"-圳;=凶气—外）？D+•••+ 一/jt-i"）P卜i匕+||%A_+・・・+%/」£

乏底孔十・・・+%*ilE=h-^X-于是定理得证.定理证毕由定理5.2.1,我们容易得出由此可得(5.2.4)另外，从理论上讲，该迭代法经囹次迭代，便能得到精确解.但考虑到计算误差，可以作为无限迭代算法进行计算，直到应可为止.从而，我们得到如下实用的共轭梯度算法：［预置步］任意网聂1计算脩7一玉，并令取：棚，•指定算法终止常数|倍利，置|4=。|，进入主步;:z j~~［主步］（1）计算：：孔出」 L|上1一气-%刃乩（2）如果|岳】‘q,转入（3）.否则，终止算法，输出计算结果冬"萱（3）计算： 轻 （4）置|化：=把十1|，转入（1）注：在算法［主步］中，引入变量S&4何及何=《】知|,可以简化计算。结合程序设计的特点，共轭梯度法可改为如下实用形式：算法5-3-1（解对称正定方程组：实用共轭梯度法）A二初■值^7=0,r=b-Ax,p=rwhilewhilewhilewhileifelseendend共轭梯度法作为一种实用的迭代法，它主要有下面的优点:算法中，系数矩阵A的作用仅仅是用来由已知向量网产生向量MS,这不仅可充分利用A的稀疏性，而且对某些提供矩阵A较为困难而由已知向量网产生向量仁迫又十分方便的应用问题是很有益的；不需要预先估计任何参数就可以计算，这一点不像SOR等；每次迭代所需的计算，主要是向量之间的运算，便于并行化。5.2.3收敛性分析将共轭梯度法作为一种迭代法，它的收敛性怎样呢？这是本节下面主要讨论的问题:定理5.2.3如果月而且忡点㈤二"则共轭梯度法至多迭代匚同步即可得到方程组的精确解。证明注意到忡球咨=叫蕴含着子空间3皿虹应"・・，甘昂二砂砌""5,・・・按昂的维数不会超过反EH,由定理5.2.1即知定理的结论成立。定理证毕定理5-2-3表明，若线性方程组（5・1・1）的系数矩阵与单位相关一个秩四的矩阵，而且四很小时，则共轭梯度法将会收敛得很快。定理5-2-4用共轭梯度法求得的区有如下的误差估计其中忡=以为=|观||炉||,证明由定理5-2-1可知，对任意的|券气&（&岳浏，有忘一汇二X.一扃十知％十巧盘』司十・・・十口*4口4=A1（月一Axq+亦们工丘|+e即元'厂］H 口）=H】（*）+ +口妣招'广］莅威R"o）=冼一1（项+巧11/4+占砖占' 就耽』*）光A&W=1十£皿息父3 —77—1 I—I一I记 I,则兽々是常数项为1的四次实系数多项式。令也为所有常数项为1的次数不超过囹的实系数多项式的全体，则由定理5・2・2和引理5-1-1得g—“JLi二皿I"—"IL冒丘知十行化）J二尹枭件稣册卜L牌小皿疽认JCJt rCJt—器陪IL占赠燃Jw*•-知其中』s不三…M 」是叵］的特征值。由Chebyshev多项式逼近定理及Chebyshev多项式的性质，定义在［-1,1］区间上的回次Chebyshev多项式：吐③二s’E呵是所有常数项为1的次数不超过网的实系数多项式中，在［-1,1］上与“0”的偏差值最小的多项式。且偏差值为1,对应的交错点组为：［xi—cos—,i—0」，・・・，立 — 。因此，多项式

中在叵列上与“0”的偏差