下载文档原格式
共轭梯度法求解线性方程组的收敛性分析与研究引言1.初始化初始解x0和残差r0=b-Ax0。
2.计算初始方向d0=r0。
3.对于k=0,1,2,...，进行以下迭代步骤：3.1 计算步长αk，使得x_{k+1}=xk + αkd。
3.2 更新残差rk+1=rk - αkAd。
3.3 计算方向dk+1=rk+1 + βkdk，其中βk=(rk+1·rk+1)/(rk·rk)。
3.4迭代直到达到指定的收敛条件。
迭代次数共轭梯度法是一种迭代算法，因此需要考虑它的迭代次数。
理论上，对于一个n阶的对称正定矩阵A，共轭梯度法最多需要n次迭代才能达到精确解。
这是因为在每一次迭代中，共轭梯度法都能找到一个与前面的方向相互正交的新方向，从而有效地减小了残差的范数。
因此，在实际应用中，共轭梯度法通常具有较快的收敛速度。
误差收敛性共轭梯度法的误差收敛性是衡量其收敛性好坏的重要指标。
理论分析表明，共轭梯度法在最多n次迭代后可以达到精确解。
在实际应用中，共轭梯度法通常在较少的迭代次数后可以达到较高的精度。
这是因为共轭梯度法利用了方向的正交性质，在每一次迭代中都能有效地减小误差。
影响共轭梯度法收敛性的因素1.矩阵A的条件数：矩阵A的条件数越大，共轭梯度法的收敛速度越慢。
2.初始解x0的选择：初始解x0的选择对共轭梯度法的收敛性有较大影响。
通常情况下，可以选择Ax0=b的最小二乘解作为初始解。
3.矩阵A的对称性：矩阵A的对称性可以加速共轭梯度法的收敛速度。
4.终止条件的选择：共轭梯度法的收敛速度和终止条件有关。
通常情况下，可选择残差的范数小于其中一预定精度作为终止条件。
5.迭代次数：共轭梯度法的收敛速度和迭代次数有关。
通常情况下，可以根据实际应用需求，选择合适的迭代次数。
总结与展望共轭梯度法是求解线性方程组的一种重要算法，具有收敛速度快，存储量小等优点。
本文对共轭梯度法的收敛性进行了分析与研究，并讨论了影响共轭梯度法收敛性的因素。
一种修正的DY 共轭梯度法的全局收敛性敖卫斌（重庆师范大学 数学学院，重庆 401331）摘要：本文提出了一种新的非线性修正的DY 共轭梯度算法（MDYCG ）,该算法得到的搜索方向为下降方向，它既不受线搜索规则的影响，也不受目标函数的凸性影响。
在精确线搜索下，MDYCG 算法化归为标准的DY 共轭梯度算法。
证明了该方法在Armijo 型线搜索下的全局收敛性，给出了初步的数值结果。
关键词：无约束优化；共轭梯度法；Armijo 型线搜索；全局收敛性 中图分类号：0182.11. 引言考虑无约束优化问题：min (),,n f x x R ∈ （1）其中:nf R R →为连续可微函数，其梯度向量记为()g x ，简记为g 。
共轭梯度法是求解大规模无约束优化问题的有效算法之一，它像最速下降法一样在每步迭代中不需要存储和计算矩阵，其迭代格式为：1k k k k x x d α+=+ (2)1,1;,1,k k k k k g k d g d k β--=⎧=⎨-+>⎩ (3)其中，()k k g f x =∇，k d 为搜索方向，k α是通过一维线搜索获得的步长，k β为标量。
不同的k β对应着不同的共轭梯度算法。
1964, Fletcher 和 Reeves 首先提出非线性共轭梯度法参数k β，它定义为221k FR k k g g β-=([2]). 还有其他著名的k β，比如121T PRP k k kk g y g β--=( [3-4])，111THSk k kTk k g y d y β---=([5]), 111T LSk k k Tk k g y d g β---=-([6]), 211kDY k k k g d y βT --=([7]), 211kCDkk k g d g βT --=-（[8]）；收稿日期：2013-05-07;作者简介: 敖卫斌（1987-），男，重庆九龙坡人，硕士研究生，主要从事最优化理论与研究.其中||||⋅为欧几里得范数,11k k k y g g --=-。
FR 方法、CD 方法和DY 方法具有较好的理论收敛性，然而PRP 方法、HS 方法和LS 方法具有较好的数值计算结果。
张丽在文献[9]中提出了修正的FR 方法的搜索方向，1,1;,1,k k FRk k k k g k d g d k θβ--=⎧⎪=⎨-+>⎪⎩从 而使得新的算法具有充分下降性和全局收敛性，得到了较好的数值试验结果。
本文在文献[9]的启发下，选取不同的k β，提出了一种修正的DY 算法（MDYCG ）并证明了该算法在Armijo 型线搜索下的全局收敛性。
所采用的Armijo 型线搜索准则：取步长max{,0,1,2,}j k j αρ== （4）满足 2212()()Tk k k k k k k k k f x d f x g d d αδαδα+≤+- （5）其中12(0,1),(0,1),0ρδδ∈∈>。
2. 修正的DY 新算法本文给出的新算法迭代格式为（2）和1,1;,1,k k DYk k k k g k d g d k θβ--=⎧⎪=⎨-+>⎪⎩ (6) 其中DYk kββ=，1111T k k k T k k g dd y θ---=+我们称 (2) 和(6)为 MDY 方法。
当线搜索为精确线搜索时，MDYCG 就得到标准的DY 共轭梯度法。
同时由DYkβ和式（6），易知对1k ≥,有：2Tk k kg d g =- （7）下面给出新的算法步骤：（1）给出1nx R ∈，12(0,1),(0,1),(0,1),0ρδδε∈∈∈≥，令 k:=1,11d g =-，若1g ε≤，立即停止；（2）找到0k α>满足Armijo 型线搜索规则；（3）令1k k k k x x d α+=+, 且11()k k g g x ++=，若k g ε≤，立即停止； （4）通过计算DYkβ,并由式（6）得1k d +；（5）令k:=k+1，返回（2）。
本文做如下假设：（A ）()f x 在水平集{}1|()()nx R f x f x Ω=∈≤有下界，其中1x 为初始点。
（B ）Ω的一个领域N 内，f 连续可微且其梯度向量满足Lipschitz 条件，即存在常数0L >，使得()(),,g x g y L x y x y N -≤-∀∈。
（8） 同时由上述的假设可以得到存在正常数β和γ满足： ,(),.x g x x βγ≤≤∀∈Ω。
（9）3.算法的收敛性引理 3.1 假设A ，B 成立，MDYCG 算法中k α满足Armijo 型线搜索，则有22k k kg cd α≥ 成立，其中()()121min 1,0c L δρδ⎧⎫-⎪⎪=>⎨⎬+⎪⎪⎩⎭。
证明：如果1k α=, 有2Tk k k k kg d g d g ⋅≥=，再由 (7) 和施瓦兹不等式, 得||||1.||||k k g d ≤ 则对1c =成立。
如果1k α<, 由 Armijo 型线搜索规则, 1k ρα- 不满足不等式(5). 则有： ()()2112212,k k k k k k k kf x d f xg d d ραδραδρα--T-+->- （10）由中值定理和假设B , 存在某一个()0,1k t ∈使得()()()()()111111k k k k k k k k k kk kk k k k k k kkf x d f xg x t d d g d g x t d g d ραραραραραραT---T-T--+-=+=++-2122.k k k k k g d L d ραρα-T -≤+ （11）结合不等式（10）、（11）和（7）得()()2212221k k k kkg g cL d d δραδ-≥≥+ 证毕。
引理 3.2假设A ，B 成立，MDYCG 算法中k α满足Armijo 型线搜索，则有Zoutendijk条件421k k kg d ≥<∞∑（12）证明： 由假设A 和（5）, 有()22120k k k k kk g d d δαδαT≥-+<∞∑，再由式子（7）有()22kkk d α≥<∞∑ （13）由引理1和（13），可以得到421k k kg d ≥<∞∑，证毕。
定理3.3若假设A 和B 成立，MDYCG 算法中k α满足Armijo 型线搜索，或者对某个k 成立，或者有0liminfk k g →∞=。
证明：反正法。
假设结论不成立，则存在一个常数ε使得k g ε≥，0k ∀≥成立 （14） 由（6）有()222212DY T k k k k k k k kd d d g g βθθ-=--。
两边同时除以()2Tk k g d ，结合（7）和（14）有()()()()222222142222k kk k kDY k k T T T T k k kk k k k k kd d d g d g g g d g d g d θθβ-==--=()22221222112k k k T Tk k kkkkg d d y g g g d θθ---⎛⎫⎪+-⎪⎝⎭=()()21222111211k kT T k k k kk d g dg d g θθ-----+-- =()2212222111k k T kkk k kd g g dg g θ----++214211k k kd g g --≤+12201k i ikg ε-=≤≤∑，则由最后一个不等式有422111k k k kg kd ε≥≥≥=∞∑∑这与（12）矛盾，证毕。
4.数值试验本节在标准Armijo 型非精确线搜索准则下，利用MARTLAB7.1， MDY 方法对测试函数[10]进行试算。
表格中Problem 表示测试函数的名称,NI/NF/NG 分别代表迭代次数、函数迭代次数、梯度迭代次数，Dim 表示测试函数自变量的个数，—表示迭代失败。
计算中参数=0.5σ，=0.8ρ，取ε=-510，VP 代表极值点，OV代表极值。
终止条件为510k g -≤。
参考文献[1] SHI Z J. Convergence of line search methods for unconstrained optimization [J]. Applied Mathematics and Computation, 2004,157:393-405[2]FLETCHER R, REEVES C. Function minimization by conjugate gradients[J]. Computer Journal, 1964, 7:149-154[3] POLAK E ，RIBIERE G. Note sur la convergence de directions conjugees[J]. Rev Francaise Informat Recherche Operatinelle, 3e Annee, 1969, 16: 35-43[4] POLAK B T. The conjugate gradient method in extremem problems, USSR Comp Math and Math. Phys.1969,9: 94-112[5] HESTENES M R , STEIFEL E L. Methods of conjugate gradients for solving linear systems[J]. J Res Nat Bur Standards Sect. 1952, 5(49): 409-436[6] LIU Y , STIEFEL C. Efficient generalized conjugate gradient algorithms[J]. JOTA, 1991 , 69(1): 129-152[7] DAI Y H , YUAN Y X. A nonlinear conjugate gradient with a strong global convergence property[J]. SIAM Journal on Optimization, 1999, 10(1): 177-182[8] FLETCHER R. Practical methods of optimization [M]. New York: Unconstrained Optimization,1987[9] ZHANG L, ZHOU W J. LI D H. Global convergence of a modified Fletcher-Reeves conjugate gradient method method with Armijo-type line search[J]. Numerische Mathematik2006,104(4):561-572[10]MORE J J,GARBOW B S,HILLSTROMK E. Testing unconstrained optimization software[J].ACM Trans,Math.Software,1981,7(1):17-41Global convergence of a conjugate gradient method for modified DY formulaAo Wei-bin（College of Mathematics, Chongqing Normal University, Chongqing ，401331）Abstract: The article presents a nonlinear modified DY conjugate gradient (MDYCG) method. The direction generated by the method is a descent direction for the objective function, and this property depends neither on the line search used, nor on the convexity of the objective function. The modified method reduces to the standard DY method if line search is exact. Global convergence of the MDYCG method with an Armijo-type line search is proved, Preliminary numerical experiment results are reported.Key words: unconstrained optimization; conjugate gradient method; Armijo-type line search; Global convergence。
