求解线性方程组的一般共轭梯度法（英文）

本文在求解线性方程组的共轭方向法的基础上,通过引入非奇异对称矩阵,给出一般的共轭梯度法.该方法推广了共轭梯度法(CG),且不同于预优共轭梯度法(PCG).数值例子表明该方法有效.     

关于正定可对称化线性代数方程组的预对称正则化算法

1引言考虑线性代数方程组A_x=b,A∈R~(n×n)非奇异,x,b∈R~n(1)的求解．当系数矩阵是大型稀疏的正定可对称化矩阵,文[1,2]讨论了一类预对称共轭梯度算法(LRSCG算法是其中之一),这类算法的实质是利用非对称的系数矩阵可对称化的性质,并结合共轭梯度法而构造的一种预处理的共轭梯度法[12,16,17]．但非对称的系数     

对称正定Toeplitz型方程组的混合预处理

本文提出一个新的预条件子,用共轭梯度法求解对称正定的Teoplitz型线性方程组.该预处理子构造简单,易于实施快速傅里叶变换.理论和数值实验显示,我们的预处理子与T.Chan预处理子收敛性相近.     

试探算法与SSOR预处理共轭梯度算法的拟最佳因子

1引言在求解系数矩阵为对称正定的大型线性代数方程组Au=b (1．1)的迭代法方面,七十年代以来发展了各种预处理共轭梯度法．由于SSOR分裂中具有对称因子,可用于加速共轭梯度法,称为SSOR预处理共轭梯度法(简记为;SSORPCG．同时,由于当松弛因子ω∈(0,2)时,SSOR迭代法收敛,从而进一步发展了m步SSOR预处理共轭梯度法(简记为:m-step SSORPCG．胡家赣证明,经过最优的SSOR预条件,预优     

四阶微分方程Hermite有限元的预处理共轭梯度法

对一类四阶微分方程两点边值问题的Hermite有限元方法进行了研究.首先讨论了该方程通常意义下的Galerkin有限元离散,考虑到有限元离散得到的线性方程组的对称正定性,文中采用了预处理最速下降法和共轭梯度方法求解线性方程组,通过选择不同的预处理器,使得求解该方程组的迭代次数有了很大的改观.     

Toeplitz预条件子的统一构造与性能分析

１．引言考虑线性方程组ＴＮｘ＝ｂ（１．１）其中ＴＮ＝（ｔｉ,ｊ）是ＮｘＮ对称正定（ＳＰＤ）Ｔｏｅｐｌｉｔｚ矩阵,即ｔｉ,ｊ＝ｔ｜ｉ－ｊ｜（ｉ,ｊ＝０,１,...,Ｎ－１）且ＴＮ的所有特征值均为正数,并表为ＴＮ：＝Ｔ（ｔ。,ｔｉ,...,ｔＮ－１）．如果我们用预条件子共轭梯度法（ＰＣＧ）求解方程组（１．１）,最关健的任务是构造出高效的预条件子．而预条件子最自然的选择似乎其逆矩阵易求且构成矩阵ＴＮ的某种最优逼近．由于循环矩阵ＣＮ的逆矩阵ＣＲ'仍为循环矩阵,因此ＣＮ和ＣＨ'与向量的乘积可通ｉｓ速Ｆｏｕｒｉｅｒ…     

实对称正定Toeplitz矩阵的带位移的Sine预处理子

本文研究了求解实对称正定Toeplitz线性方程组的预处理共轭梯度法.基于实对称Toeplitz矩阵都有一个三角变换分裂(TTS)的事实,我们提出了带位移的Sine预处理子TS,分析了预处理矩阵的谱性质,并讨论了每步迭代的计算复杂度.数值实验表明该预处理子比T.Chan预处理子~([2])更有效.     

非奇异阵特征极值和条件数的近似计算

本文从共轭梯度法的公式推导出对称正定阵A与三对角阵B的相似关系,B的元素由共轭梯度法的迭代参数确定.因此,对称正定阵的条件数计算可以化成三对角阵条件数的计算,并且可以在共轭梯度法的计算中顺带完成.它只需增加O(s)次的计算量,s为迭代次数.这与共轭梯度法的计算量相比是可以忽略的.当A为非对称正定阵时,只要A非奇异,即可用共轭梯度法计算ATA的特征极值和条件数,从而得出A的条件数.对不同算例的计算表明,这是一种快速有效的简便方法.     

一种求解鞍点问题的预处理并行算法

研究了一种求解鞍点问题的并行预处理变形共轭梯度算法.通过应用迭代法进行预处理后,再采用变形共轭梯度求解的模式.首先构造系数矩阵近似逆的多项式表达式,以此作为预处理矩阵的逆矩阵,对方程组进行预处理;然后采用变形共轭梯度法并行求解预处理后的线性方程组.为减少运算量,采用迭代方式并行计算多项式与向量的乘法运算.通过调整迭代次数,即调整多项式次数,检验各种次数的多项式进行预处理后的求解方程的效果.数值试验结果表明,该算法明显优于未预处理的变形共轭梯度法,且当预处理迭代次数取4时效果最好.     

关于一种循环类预条件方程组的快速求解

１引言考虑下列Ｎ阶线性方程组其中Ｃ１＝,Ｃ２＝０≤ｉ,ｊ≤Ｎ－１,是Ｎ阶循环矩阵,Ｊ１＝（Ｊ）是Ｎ阶置换矩阵,其元素分别满足１９９３年,Ｔ,Ｋ．Ｋｕ,Ｃ．Ｃ．Ｊ．Ｋｕｏ在［１］中取Ｃ１,Ｃ２为实对称循环矩阵,而Ｃ１＋Ｊ１Ｃ２作为预条件矩阵来求解在数字信号处理中有一定应用的Ｔｏｅｐｌｉｔｚ加Ｈａｎｋｅｌ线性方程组［２］,得到了一种高效的预处理其轭梯度算法．当Ｔｏｅｅｌｉｔｚ与Ｈａｎｋｅｌ矩阵之和为正定矩阵且条件数适中时,所需运算量可达到０（Ｎｌｏｇ２Ｎ）,比原有算法［２,３,４］的运算量０（Ｎ２）…     

On Estimation of the A‐norm of the Error in CG and PCG

We concentrate on the preconditioned conjugate gradient method and describe a simple and numerically well‐justified way of estimation of the A‐norm of the error. In this way this note represents an extension of [5] and its aim is to mediate the analytic results from [5] to practical users of the preconditioned conjugate gradient method.     

两类下降的非线性共轭梯度法的全局收敛性

本文在文献[1]中提出了一类新共轭梯度法的基础上,给出求解无约束优化问题的两类新的非线性下降共轭梯度法,此两类方法在无任何线搜索下,能够保证在每次迭代中产生下降方向.对一般非凸函数,我们在Wolfe线搜索条件下证明了两类新方法的全局收敛性.     

A scaled BFGS preconditioned conjugate gradient algorithm for unconstrained optimization

This letter presents a scaled memoryless BFGS preconditioned conjugate gradient algorithm for solving unconstrained optimization problems. The basic idea is to combine the scaled memoryless BFGS method and the preconditioning technique in the frame of the conjugate gradient method. The preconditioner, which is also a scaled memoryless BFGS matrix, is reset when the Powell restart criterion holds. The parameter scaling the gradient is selected as the spectral gradient. Computational results for a set consisting of 750 test unconstrained optimization problems show that this new scaled conjugate gradient algorithm substantially outperforms known conjugate gradient methods such as the spectral conjugate gradient SCG of Birgin and Martínez [E. Birgin, J.M. Martínez, A spectral conjugate gradient method for unconstrained optimization, Appl. Math. Optim. 43 (2001) 117–128] and the (classical) conjugate gradient of Polak and Ribière [E. Polak, G. Ribière, Note sur la convergence de méthodes de directions conjuguées, Revue Francaise Informat. Reserche Opérationnelle, 3e Année 16 (1969) 35–43], but subject to the CPU time metric it is outperformed by L-BFGS [D. Liu, J. Nocedal, On the limited memory BFGS method for large scale optimization, Math. Program. B 45 (1989) 503–528; J. Nocedal. http://www.ece.northwestern.edu/~nocedal/lbfgs.html].     

Addendum to: A hybrid conjugate gradient method based on a quadratic relaxation of Dai–Yuan hybrid conjugate gradient parameter

Here, necessary corrections on computing the hybridization parameter of the quadratic hybrid conjugate gradient method of Babaie-Kafaki [S. Babaie-Kafaki, A hybrid conjugate gradient method based on a quadratic relaxation of Dai-Yuan hybrid conjugate gradient parameter, Optimization, DOI: 10.1080/02331934.2011.611512, 2011] are stated in brief. Throughout, we use the same notations and equation numbers as in Babaie-Kafaki (2011).     

New properties of a nonlinear conjugate gradient method

Summary. This paper provides several new properties of the nonlinear conjugate gradient method in [5]. Firstly, the method is proved to have a certain self-adjusting property that is independent of the line search and the function convexity. Secondly, under mild assumptions on the objective function, the method is shown to be globally convergent with a variety of line searches. Thirdly, we find that instead of the negative gradient direction, the search direction defined by the nonlinear conjugate gradient method in [5] can be used to restart any optimization method while guaranteeing the global convergence of the method. Some numerical results are also presented. Received March 12, 1999 / Revised version received April 25, 2000 / Published online February 5, 2001     

改进共轭梯度法求解无约束二次凸规划问题

针对共轭梯度法求解无约束二次凸规划时,在构造共轭方向上的局限性,对共轭梯度法进行了改进.给出了构造共轭方向的新方法,利用数学归纳法对新方法进行了证明.同时还给出了改进共轭梯度法在应用时的基本计算过程,并对方法的收敛性进行了证明.通过实例求解,说明了在求解二次无约束凸规划时,该方法相比共轭梯度法具有一定的优势.     

Preconditioned Conjugate Gradient Methods for Integral Equations of the Second Kind Defined on the Half-Line

1.IntroductionInthispaPer,westudynumericalsolutionstointegralequationsofthesecondkinddefinedonthehalfline.Morepreciselyweconsidertheequationy(t)+Iooa(t,s)y(s)ds=g(t),OS相似文献   

一个拟极小化左共轭梯度算法及其数值表现

左共轭梯度法是求解大型稀疏线性方程组的一种新兴的Krylov子空间方法.为克服该算法数值表现不稳定、迭代中断的缺点,本文对原方法进行等价变形,得到左共轭梯度方向的另一迭代格式,给出一个拟极小化左共轭梯度算法.数值结果证实了该变形算法与原算法的相关性.     

Nonlinear conjugate gradient methods with structured secant condition for nonlinear least squares problems

In this paper, we deal with conjugate gradient methods for solving nonlinear least squares problems. Several Newton-like methods have been studied for solving nonlinear least squares problems, which include the Gauss-Newton method, the Levenberg-Marquardt method and the structured quasi-Newton methods. On the other hand, conjugate gradient methods are appealing for general large-scale nonlinear optimization problems. By combining the structured secant condition and the idea of Dai and Liao (2001) [20], the present paper proposes conjugate gradient methods that make use of the structure of the Hessian of the objective function of nonlinear least squares problems. The proposed methods are shown to be globally convergent under some assumptions. Finally, some numerical results are given.     

A conjugate gradient method for the unconstrained minimization of strictly convex quadratic splines

In this paper, we show that an analogue of the classical conjugate gradient method converges linearly when applied to solving the problem of unconstrained minimization of a strictly convex quadratic spline. Since a strictly convex quadratic program with simple bound constraints can be reformulated as unconstrained minimization of a strictly convex quadratic spline, the conjugate gradient method is used to solve the unconstrained reformulation and find the solution of the original quadratic program. In particular, if the solution of the original quadratic program is nondegenerate, then the conjugate gradient method finds the solution in a finite number of iterations. This author's research is partially supported by the NASA/Langley Research Center under grant NCC-1-68 Supplement-15.