整理共轭梯度法及其基本性质

1、共轭梯度法及其根本性质预备知识定义1设是对称正定矩阵.称血乃是A-共轭的,是指品丄巧=0, Pi Ap > 0.对母？ >0.性质1设有5是彼此共轭的丹维向量,即£= 0, t H J.Pt 4p； n= 0,1,.,.|?0,那么化一定是线性无关的.证实假设有一组数弘满足印Fu十+ ©皿=°那么对一切心恥曲一定有= Pi卫珂+=圧层越r注意到pSE,由此得出 S 即所有的 = 0.因此,PWg 是线性无关的.性质2 设向量 亦站弧是线性无关的向量组,那么可通过它们的线性组合 得出一组向量5兀几,而丹小化是两两共轭的.证实我们用构造法来证实上面的结论.

2、S1:J«-l耳=十工站.i-0容易验证：外化符合性质2的要求.性质3设珂"“卞戏是两两A共轭的,勺巨対是任意指定的向量,那么从奄出发,逐次沿方向P皿搜索求WS-2几的极小值,所得序jt-iid证实由下山算法可知,从 勺出发,沿几方向搜索,获得从而Jl-1k-1+ Z务耳二=础十另刍口、亠 1M)性质4设丹申“】是两两A共轭的,那么从任意指定的可怎肝出发,依次 沿氏搜索,所得序列()uo满足：(1) PkAPk(2) 巧二匚,其中&是方程组(5.1.1)的解.证实(1)是性质3的直接推论,显然成立.(2)由于PPWXPz是两两A共轭的,故是线性无关的.所以对于向量心

3、一毛可用“21线性表出,即存在一组数使由于PqPj = 0 八1.宀1,得出于是得出于是与得出f 一样地,我们可以陆续得出:比照乳和D的表达式可知,©二兀证实完毕性质4是性质3的直接推论.但它给出了一种求5 . 1. 1的算法,这种 算法称之为共轭方向法结合性质2,我们可以得到如下的性质5.性质5设 跖弧3 是卅上的一组线性无关的向量,那么从任意指定的心丘炉出发,按以下迭代产生的序列S1:u昭谯心=吗+ a込取丹二斷,S2:计算琉恥,取內二宙十仇肌；计算玩那L,得出心工心+叫P1 ；如此进行下去,直到第n步:S n：计算门Pi "gjj-L 二门 nPi , E = U“,

4、母一2,Pi啦计算斗=专久一1如一1得出巧_+ °7卩屯1显然:根据性质4可知,不管采用什么方法,只要能够构造：个两两A共轭的向量 作为搜索方向,从任一初始向量出发,依次沿两两A共轭的方向进行搜索,经：步迭代后,便可得到正定方程组Ax = b的解.共轭梯度法算法步骤如下：预置步任意r - 7,计算'S,并令取：厂I指定算法终止常数->0,置= 0|,进入主步；主步(1)如果卜: 终止算法,输出 '否那么下行;(2)计算:也=耳+%久,歹脑1 =+i(3)计算:(4)置-1 ,转入(1)定理5 .2.1由共轭梯度法得到的向量组 也和®具有如下性质:1)

5、I T2) 才勺二 0, 2八 0<ifj<kf3) (4) 网兄乩心二陀仏,久二盟(4心上+1),其中忙(4®七+ 1)=网環阮肌r -,月怙(521 )通常称之为Krylov子空间.证实用归纳法当,；-1时,由于= -ro ri H% - %母°=石 6 ct尿 /几=0,PiPn = Cn +几乩孑禺=占占心-因此定理的结论成立.现在假设定理的结论对 闊成立,我们来证实其比照+】1也 成立.利用等式%如及归纳假设,有又由于故定理的结论1对k + 1成立.利用归纳假定有砕妙阮./=字曲Am仇L而由1所证知,-与上述子空间正交,从而有定理的结论2对：1也成立.

6、利用等式P屏1二J +炕刃和|"二疗-沁i并利用归纳法假定和2所证之结论,就有成立；而由炕的定义得厂厂Ap3 =阳皿$如=3 一诗益皿=°这样,定理的结论3对+1也成立.由归纳法假定知k,A -忙月叭用+i=矽妙进而為 G零蜩/% r月%屮心C田沏© ,血,旳于是ui =氐一他百 e KAfF + 2 = spatArQr- 九L %1 + E创已应几Z2=乎期b .A<-?川七I再注意到2和3所证的结论说明,向量组：1 '和 都是线性无关的,因此定理的结论4对：“同样成立.定理证毕定理521说明,向量心和丽鬥心分别是Krylov子空间心“屮 的正交

7、基和共轭正交基.由此可见,共轭梯度法最多鬥步便可得到方程组的解恥.因此,理论上来讲,共轭梯度法是直接法.定理5.2.2用共轭梯度法计算得到的近似解、满足:xex0(52 2)(52 3)_ x*IL=111111 Ik _x* IL: xe 码+jc(a® 对其中卜b二佇加,儿是方程组加的解,心心Q是由5.2.1 所定 义的Krylov子空间.证实 注意到：叭E斗疋占鬲二広忌丁占0 叭,贝y 5.2.2 和523是 等价的,因此我们下面只证实5.2.3成立.假定共轭梯度法计算到/步出现= °,那么有=心十Po+%Pi +场此外,对计算过程中的任一步：,有片几二珀+ 

8、3;2°戸口 +理屜尹9丘可+tcAtrGrk设0是属于可+双儿朮的任一向量,那么由定理5.2.1的4知,X可以 表示为?于是凡一疋二珂一旳肌+口1 一班丹+3一抡7戸+勺尸上+ °1刃小而仏一心二再利用定理521的(3)就可以推出h -IIM附-r0p0 十+臨ju 2|"lA十十円吨丹II二忖忑于是定理得证.定理证毕由定理5.2.1 ,我们容易得出由此可得524另外,从理论上讲,该迭代法经,：次迭代,便能得到精确解但考虑到计算 误差,可以作为无限迭代算法进行计算,直到I卜至占为止.从而,我们得到如下实用的共轭梯度算法：预置步任意宀-二,计算f' 

9、9; _ ''',并令取：；"指定算法终止 常数小,置N,进入主步；主步(1)计算:4 N, a'jui =九 + &如(2)如果lliII,转入(3).否那么,终止算法,输出计算结果(3)计算:(4)置已二丘*1,转入(1)F_ji,可以简注：在算法主步中,引入变量 "如,及0二血1 化计算.结合程序设计的特点,共轭梯度法可改为如下实用形式:算法531 (解对称正定方程组：实用共轭梯度法).-'l ；7elseE = EE,p = r-v a?end>V = Ap, a = pl prwt X= A 十晔1 r = r

10、-G. p = p p=升end共轭梯度法作为一种实用的迭代法,它主要有下面的优点:算法中,系数矩阵A的作用仅仅是用来由向量 左产生向量 宀血,这不仅可充分利用A的稀疏性,而且对某些提供矩阵A 较为困难而由向量去产生向量二幼又十分方便的应用问题 是很有益的；不需要预先估计任何参数就可以计算,这一点不像SOR等； 每次迭代所需的计算,主要是向量之间的运算,便于并行化.523收敛性分析将共轭梯度法作为一种迭代法,它的收敛性怎样呢？这是本节下面主要讨论 的问题：定理5 23如果+百而且垃嵌=r,那么共轭梯度法至多迭代尸+1步 即可得到方程组的精确解.证实注意到3二厂蕴含着子空间的维数不会超过厂+ 1

11、,由定理5 .2.1即知定理的结论成立.定理证毕定理5 2 3说明,假设线性方程组(5 1 1 )的系数矩阵与单位相关一个秩 的矩阵,而且很小时,那么共轭梯度法将会收敛得很快.定理5 2 4用共轭梯度法求得的勺有如下的误差估计<2(5 -2 -5)其中咕衍十屮-打证实 由定理5 - 2-1可知,对任意的兀巨+巩&5崗,有X* 一 2 X* 巧 十#灯心 十口扭用心 十"" + V1-rQ=卫虫心-占两十僅打/巾+口£力+q H十皿屈/Sq=甘16+%上+ 口盟"I 眄血甘% =川/ + %月+ %/ 咳才心以=1 +另口昇卫记I ,那么卩汎心是常数项为1的丘次实系数多项式.令耳为所有常数项为1的次数不超过M的实系数多项式的全体,那么由定理 5 - 2 -2和引 理5-1-1得卜4 _咄11二血|片_氛11：応九十忙3必,幼二戸擁片九伽L=蟲恢屮让兰聘汕甑斥恫-叼L,其中° V応二入玄兰卞是Z的特征值.由Chebyshev多项式逼近定理及Chebyshev多项式的性质,定义在-1 , 1区间上的次Chebyshev多项式:二皿懐唇小是所有常数项为1的次数不超过疋的实系数多项式中,在-1 ,1上与“0的偏差值最小的多项式.且偏差值为1,对应的交错点组为：xi -