求解非对称线性方程组的QMRGCGS方法

1 引言 求解非对称线性方程组Ax=b的双共轭梯度方法(BCG)[3]和它的变形共轭梯度平方方法(CGS)[6]都有典型的不规则收敛行为,后来Freund和Nachtigal提出一种BCG类方法,即拟极小剩余方法(QMR)[7],用来补救BCG方法的收敛性并且产生了光滑的收敛曲线。然而,象BCG方法一样,QMR方法要用到系数矩阵A及其转置A~T与向量的乘积,为了解决这一问题,Freund提出TFQMR方法,此方法具有拟极小剩余性,同时不需用到A~T与向量的乘积。     

An extension of the conjugate residual method to nonsymmetric linear systems

The Conjugate Gradient (CG) method and the Conjugate Residual (CR) method are Krylov subspace methods for solving symmetric (positive definite) linear systems. To solve nonsymmetric linear systems, the Bi-Conjugate Gradient (Bi-CG) method has been proposed as an extension of CG. Bi-CG has attractive short-term recurrences, and it is the basis for the successful variants such as Bi-CGSTAB. In this paper, we extend CR to nonsymmetric linear systems with the aim of finding an alternative basic solver. Numerical experiments show that the resulting algorithm with short-term recurrences often gives smoother convergence behavior than Bi-CG. Hence, it may take the place of Bi-CG for the successful variants.     

By How Much Can Residual Minimization Accelerate the Convergence of Orthogonal Residual Methods?

We capitalize upon the known relationship between pairs of orthogonal and minimal residual methods (or, biorthogonal and quasi-minimal residual methods) in order to estimate how much smaller the residuals or quasi-residuals of the minimizing methods can be compared to those of the corresponding Galerkin or Petrov–Galerkin method. Examples of such pairs are the conjugate gradient (CG) and the conjugate residual (CR) methods, the full orthogonalization method (FOM) and the generalized minimal residual (GMRES) method, the CGNE and BiCG versions of applying CG to the normal equations, as well as the biconjugate gradient (BiCG) and the quasi-minimal residual (QMR) methods. Also the pairs consisting of the (bi)conjugate gradient squared (CGS) and the transpose-free QMR (TFQMR) methods can be added to this list if the residuals at half-steps are included, and further examples can be created easily.The analysis is more generally applicable to the minimal residual (MR) and quasi-minimal residual (QMR) smoothing processes, which are known to provide the transition from the results of the first method of such a pair to those of the second one. By an interpretation of these smoothing processes in coordinate space we deepen the understanding of some of the underlying relationships and introduce a unifying framework for minimal residual and quasi-minimal residual smoothing. This framework includes the general notion of QMR-type methods.     

Iterative methods for solvingAx=b,GMRES/FOM versus QMR/BiCG

We study the convergence of the GMRES/FOM and QMR/BiCG methods for solving nonsymmetric systems of equationsAx=b. We prove, in exact arithmetic, that any type of residual norm convergence obtained using BiCG can also be obtained using FOM but on a different system of equations. We consider practical comparisons of these procedures when they are applied to the same matrices. We use a unitary invariance shared by both methods, to construct test matrices where we can vary the nonnormality of the test matrix by variations in simplified eigenvector matrices. We used these test problems in two sets of numerical experiments. The first set of experiments was designed to study effects of increasing nonnormality on the convergence of GMRES and QMR. The second set of experiments was designed to track effects of the eigenvalue distribution on the convergence of QMR. In these tests the GMRES residual norms decreased significantly more rapidly than the QMR residual norms but without corresponding decreases in the error norms. Furthermore, as the nonnormality ofA was increased, the GMRES residual norms decreased more rapidly. This led to premature termination of the GMRES procedure on highly nonnormal problems. On the nonnormal test problems the QMR residual norms exhibited less sensitivity to changes in the nonnormality. The convergence of either type of procedure, as measured by the error norms, was delayed by the presence of large or small outliers and affected by the type of eigenvalues, real or complex, in the eigenvalue distribution ofA. For GMRES this effect can be seen only in the error norm plots.In honor of the 70th birthday of Ted RivlinThis work was supported by NSF grant GER-9450081.     

A-posteriori residual bounds for Arnoldi’s methods for nonsymmetric eigenvalue problems

Convergence of the implicitly restarted Arnoldi (IRA) method for nonsymmetric eigenvalue problems has often been studied by deriving bounds for the angle between a desired eigenvector and the Krylov projection subspace. Bounds for residual norms of approximate eigenvectors have been less studied and this paper derives a new a-posteriori residual bound for nonsymmetric matrices with simple eigenvalues. The residual vector is shown to be a linear combination of exact eigenvectors and a residual bound is obtained as the sum of the magnitudes of the coefficients of the eigenvectors. We numerically illustrate that the convergence of the residual norm to zero is governed by a scalar term, namely the last element of the wanted eigenvector of the projected matrix. Both cases of convergence and non-convergence are illustrated and this validates our theoretical results. We derive an analogous result for implicitly restarted refined Arnoldi (IRRA) and for this algorithm, we numerically illustrate that convergence is governed by two scalar terms appearing in the linear combination which drives the residual norm to zero. We provide a set of numerical results that validate the residual bounds for both variants of Arnoldi methods.     

The generalized residual cutting method and its convergence characteristics

Iterative methods and especially Krylov subspace methods (KSM) are a very useful numerical tool in solving for large and sparse linear systems problems arising in science and engineering modeling. More recently, the nested loop KSM have been proposed that improve the convergence of the traditional KSM. In this article, we review the residual cutting (RC) and the generalized residual cutting (GRC) that are nested loop methods for large and sparse linear systems problems. We also show that GRC is a KSM that is equivalent to Orthomin with a variable preconditioning. We use the modified Gram–Schmidt method to derive a stable GRC algorithm. We show that GRC presents a general framework for constructing a class of “hybrid” (nested) KSM based on inner loop method selection. We conduct numerical experiments using nonsymmetric indefinite matrices from a widely used library of sparse matrices that validate the efficiency and the robustness of the proposed methods.     

Variants of the groupwise update strategy for short-recurrence Krylov subspace methods

Krylov subspace methods often use short-recurrences for updating approximations and the corresponding residuals. In the bi-conjugate gradient (Bi-CG) type methods, rounding errors arising from the matrix–vector multiplications used in the recursion formulas influence the convergence speed and the maximum attainable accuracy of the approximate solutions. The strategy of a groupwise update has been proposed for improving the convergence of the Bi-CG type methods in finite-precision arithmetic. In the present paper, we analyze the influence of rounding errors on the convergence properties when using alternative recursion formulas, such as those used in the bi-conjugate residual (Bi-CR) method, which are different from those used in the Bi-CG type methods. We also propose variants of a groupwise update strategy for improving the convergence speed and the accuracy of the approximate solutions. Numerical experiments demonstrate the effectiveness of the proposed method.     

Convergence analysis of multigrid methods with residual scaling techniques

In this paper, multigrid methods with residual scaling techniques for symmetric positive definite linear systems are considered. The idea of perturbed two-grid methods proposed in [7] is used to estimate the convergence factor of multigrid methods with residual scaled by positive constant scaling factors. We will show that if the convergence factors of the two-grid methods are uniformly bounded by σ (σ<0.5), then the convergence factors of the W-cycle multigrid methods are uniformly bounded by σ/(1−σ), whether the residuals are scaled at some or all levels. This result extends Notay’s Theorem 3.1 in [7] to more general cases. The result also confirms the viewpoint that the W-cycle multigrid method will converge sufficiently well as long as the convergence factor of the two-grid method is small enough. In the case where the convergence factor of the two-grid method is not small enough, by appropriate choice of the cycle index γ, we can guarantee that the convergence factor of the multigrid methods with residual scaling techniques still has a uniform bound less than σ/(1−σ). Numerical experiments are provided to show that the performance of multigrid methods can be improved by scaling the residual with a constant factor. The convergence rates of the two-grid methods and the multigrid methods show that the W-cycle multigrid methods perform better if the convergence rate of the two-grid method becomes smaller. These numerical experiments support the proposed theoretical results in this paper.     

Sparse grids and hybrid methods for the chemical master equation

The direct numerical solution of the chemical master equation (CME) is usually impossible due to the high dimension of the computational domain. The standard method for solution of the equation is to generate realizations of the chemical system by the stochastic simulation algorithm (SSA) by Gillespie and then taking averages over the trajectories. Two alternatives are described here using sparse grids and a hybrid method. Sparse grids, implemented as a combination of aggregated grids are used to address the curse of dimensionality of the CME. The aggregated components are selected using an adaptive procedure. In the hybrid method, some of the chemical species are represented macroscopically while the remaining species are simulated with SSA. The convergence of variants of the method is investigated for a growing number of trajectories. Two signaling cascades in molecular biology are simulated with the methods and compared to SSA results. AMS subject classification (2000)  65C20, 60J25, 92C45     

Continuous block implicit hybrid one-step methods for ordinary and delay differential equations

A class of high order continuous block implicit hybrid one-step methods has been proposed to solve numerically initial value problems for ordinary and delay differential equations. The convergence and Aω-stability of the continuous block implicit hybrid methods for ordinary differential equations are studied. Alternative form of continuous extension is constructed such that the block implicit hybrid one-step methods can be used to solve delay differential equations and have same convergence order as for ordinary differential equations. Some numerical experiments are conducted to illustrate the efficiency of the continuous methods.     

Globally and superlinearly convergent inexact Newton–Krylov algorithms for solving nonsmooth equations

This paper presents some variants of the inexact Newton method for solving systems of nonlinear equations defined by locally Lipschitzian functions. These methods use variants of Newton's iteration in association with Krylov subspace methods for solving the Jacobian linear systems. Global convergence of the proposed algorithms is established under a nonmonotonic backtracking strategy. The local convergence based on the assumptions of semismoothness and BD‐regularity at the solution is characterized, and the way to choose an inexact forcing sequence that preserves the rapid convergence of the proposed methods is also indicated. Numerical examples are given to show the practical viability of these approaches. Copyright © 2009 John Wiley & Sons, Ltd.     

Maintaining convergence properties of BiCGstab methods in finite precision arithmetic

It is well-known that Bi-CG can be adapted so that hybrid methods with computational complexity almost similar to Bi-CG can be constructed, in which it is attempted to further improve the convergence behavior. In this paper we will study the class of BiCGstab methods.In many applications, the speed of convergence of these methods appears to be determined mainly by the incorporated Bi-CG process, and the problem is that the Bi-CG iteration coefficients have to be determined from the BiCGstab process. We will focus our attention to the accuracy of these Bi-CG coefficients, and how rounding errors may affect the speed of convergence of the BiCGstab methods. We will propose a strategy for a more stable determination of the Bi-CG iteration coefficients and by experiments we will show that this indeed may lead to faster convergence.     

ML($n$)BiCGStab: Reformulation,Analysis and Implementation

With the aid of index functions, we re-derive the ML($n$)BiCGStab algorithm in [Yeung and Chan, SIAM J. Sci. Comput., 21 (1999), pp. 1263-1290] systematically. There are $n$ ways to define the ML($n$)BiCGStab residual vector. Each definition leads to a different ML($n$)BiCGStab algorithm. We demonstrate this by presenting a second algorithm which requires less storage. In theory, this second algorithm serves as a bridge that connects the Lanczos-based BiCGStab and the Arnoldi-based FOM while ML($n$)BiCG is a bridge connecting BiCG and FOM. We also analyze the breakdown situation from the probabilistic point of view and summarize some useful properties of ML($n$)BiCGStab. Implementation issues are also addressed.     

A Hybrid Approximate Extragradient – Proximal Point Algorithm Using the Enlargement of a Maximal Monotone Operator

We propose a modification of the classical extragradient and proximal point algorithms for finding a zero of a maximal monotone operator in a Hilbert space. At each iteration of the method, an approximate extragradient-type step is performed using information obtained from an approximate solution of a proximal point subproblem. The algorithm is of a hybrid type, as it combines steps of the extragradient and proximal methods. Furthermore, the algorithm uses elements in the enlargement (proposed by Burachik, Iusem and Svaiter) of the operator defining the problem. One of the important features of our approach is that it allows significant relaxation of tolerance requirements imposed on the solution of proximal point subproblems. This yields a more practical proximal-algorithm-based framework. Weak global convergence and local linear rate of convergence are established under suitable assumptions. It is further demonstrated that the modified forward-backward splitting algorithm of Tseng falls within the presented general framework.     

Circulant-block preconditioners for solving ordinary differential equations

Boundary value methods for solving ordinary differential equations require the solution of non-symmetric, large and sparse linear systems. In this paper, these systems are solved by using the generalized minimal residual (GMRES) method. A circulant-block preconditioner is proposed to speed up the convergence rate of the GMRES method. Theoretical and practical arguments are given to show that this preconditioner is more efficient than some other circulant-type preconditioners in some cases. A class of waveform relaxation methods is also proposed to solve the linear systems.     

A Linear Hybridization of Dai-Yuan and Hestenes-Stiefel Conjugate Gradient Method for Unconstrained Optimization

Conjugate gradient methods are interesting iterative methods that solve large scale unconstrained optimization problems. A lot of recent research has thus focussed on developing a number of conjugate gradient methods that are more effective. In this paper, we propose another hybrid conjugate gradient method as a linear combination of Dai-Yuan (DY) method and the Hestenes-Stiefel (HS) method. The sufficient descent condition and the global convergence of this method are established using the generalized Wolfe line search conditions. Compared to the other conjugate gradient methods, the proposed method gives good numerical results and is effective.     

On inertial proximal algorithm for split variational inclusion problems

ABSTRACT

In this paper, a hybrid proximal algorithm with inertial effect is introduced to solve a split variational inclusion problem in real Hilbert spaces. Under mild conditions on the parameters, we establish weak convergence results for the proposed algorithm. Unlike the earlier iterative methods, we do not impose any conditions on the sequence generated by the proposed algorithm. Also, we extend our results to find a common solution of a split variational inclusion problem and a fixed-point problem. Finally, some numerical examples are given to discuss the convergence and superiority of the proposed iterative methods.     

Steepest descent preconditioning for nonlinear GMRES optimization

Steepest descent preconditioning is considered for the recently proposed nonlinear generalized minimal residual (N‐GMRES) optimization algorithm for unconstrained nonlinear optimization. Two steepest descent preconditioning variants are proposed. The first employs a line search, whereas the second employs a predefined small step. A simple global convergence proof is provided for the N‐GMRES optimization algorithm with the first steepest descent preconditioner (with line search), under mild standard conditions on the objective function and the line search processes. Steepest descent preconditioning for N‐GMRES optimization is also motivated by relating it to standard non‐preconditioned GMRES for linear systems in the case of a standard quadratic optimization problem with symmetric positive definite operator. Numerical tests on a variety of model problems show that the N‐GMRES optimization algorithm is able to very significantly accelerate convergence of stand‐alone steepest descent optimization. Moreover, performance of steepest‐descent preconditioned N‐GMRES is shown to be competitive with standard nonlinear conjugate gradient and limited‐memory Broyden–Fletcher–Goldfarb–Shanno methods for the model problems considered. These results serve to theoretically and numerically establish steepest‐descent preconditioned N‐GMRES as a general optimization method for unconstrained nonlinear optimization, with performance that appears promising compared with established techniques. In addition, it is argued that the real potential of the N‐GMRES optimization framework lies in the fact that it can make use of problem‐dependent nonlinear preconditioners that are more powerful than steepest descent (or, equivalently, N‐GMRES can be used as a simple wrapper around any other iterative optimization process to seek acceleration of that process), and this potential is illustrated with a further application example. Copyright © 2012 John Wiley & Sons, Ltd.     

A new shrinking gradient-like projection method for equilibrium problems

The paper proposes a new shrinking gradient-like projection method for solving equilibrium problems. The algorithm combines the generalized gradient-like projection method with the monotone hybrid method. Only one optimization program is solved onto the feasible set at each iteration in our algorithm without any extra-step dealing with the feasible set. The absence of an optimization problem in the algorithm is explained by constructing slightly different cutting-halfspace in the monotone hybrid method. Theorem of strong convergence is established under standard assumptions imposed on equilibrium bifunctions. An application of the proposed algorithm to multivalued variational inequality problems (MVIP) is presented. Finally, another algorithm is introduced for MVIPs in which we only use a value of main operator at the current approximation to construct the next approximation. Some preliminary numerical experiments are implemented to illustrate the convergence and computational performance of our algorithms over others.     

Relaxed inertial proximal Peaceman-Rachford splitting method for separable convex programming

The strictly contractive Peaceman-Rachford splitting method is one of effective methods for solving separable convex optimization problem, and the inertial proximal Peaceman-Rachford splitting method is one of its important variants. It is known that the convergence of the inertial proximal Peaceman-Rachford splitting method can be ensured if the relaxation factor in Lagrangian multiplier updates is underdetermined, which means that the steps for the Lagrangian multiplier updates are shrunk conservatively. Although small steps play an important role in ensuring convergence, they should be strongly avoided in practice. In this article, we propose a relaxed inertial proximal Peaceman-Rachford splitting method, which has a larger feasible set for the relaxation factor. Thus, our method provides the possibility to admit larger steps in the Lagrangian multiplier updates. We establish the global convergence of the proposed algorithm under the same conditions as the inertial proximal Peaceman-Rachford splitting method. Numerical experimental results on a sparse signal recovery problem in compressive sensing and a total variation based image denoising problem demonstrate the effectiveness of our method.