Analysis of iterative methods for saddle point problems: a unified approach

In this paper two classes of iterative methods for saddle point problems are considered: inexact Uzawa algorithms and a class of methods with symmetric preconditioners. In both cases the iteration matrix can be transformed to a symmetric matrix by block diagonal matrices, a simple but essential observation which allows one to estimate the convergence rate of both classes by studying associated eigenvalue problems. The obtained estimates apply for a wider range of situations and are partially sharper than the known estimates in literature. A few numerical tests are given which confirm the sharpness of the estimates.

     

On iterative methods for equilibrium problems

In this paper, we introduce a hybrid iterative scheme for finding a common element of the set of solutions of an equilibrium problem and the set of fixed points of finitely many nonexpansive mappings. We prove that the approximate solution converges strongly to a solution of a class of variational inequalities under some mild conditions, which is the optimality condition for some minimization problem. We also give some comments on the results of Plubtieng and Punpaeng [S. Plubtieng, R. Punpaeng, A general iterative method for equilibrium problems and fixed point problems in Hilbert spaces, J. Math. Anal. Appl. 336 (2007) 455–469]. Results obtained in this paper may be viewed as an improvement and refinement of the previously known results in this area.     

解线性方程组的松弛方法及其应用

线性方程组在科学和工程领域中有着重要的应用,松弛方法是求解线性方程组的有效算法之一.本文在著名的Gauss-Seidel迭代法的基础上,研究了一种有效的松弛方法.理论分析表明,该方法能收敛到线性方程组的唯一解.此外,我们还将该方法应用在鞍点问题和PageRank问题的求解上,并得出了相应的数值结果.结果表明该方法比现有的松弛方法更有效.     

Operator trigonometry of iterative methods

A new and general approach to the understanding and analysis of widely used iterative methods for the numerical solution of the equation Ax = b is presented. This class of algorithms, which includes CGN, GMRES. ORTHOMIN, BCG, CGS, and others of current importance, utilizes residual norm minimizing procedures, such as those often found under the general names Galerkin method, Arnoldi method, Lanczos method, and so on. The view here is different: the needed error minimizations are seen trigonometrically. © 1997 John Wiley & Sons, Ltd.     

Solution of nonsymmetric linear complementarity problems by iterative methods

Convergence is established for iterative algorithms for the solution of the nonsymmetric linear complementarity problem of findingz such thatMz+q0,z0,z ^T(Mz+q)=0, whereM is a givenn×n real matrix, not necessarily symmeetric, andq is a givenn-vector. It is first shown that, if the spectral radius of a matrix related toM is less than one, then the iterates generated by the general algorithm converge to a solution of the linear complementarity problem. It turns out that convergence properties are quite similar to those of linear systems of equations. As specific cases, two important classes of matrices, Minkowski matrices and quasi-dominant diagonal matrices, are shown to satisfy this convergence condition.The author is grateful to Professor O. L. Mangasarian and the referees for their substantive suggestions and corrections.     

On eigenvalue distribution of constraint‐preconditioned symmetric saddle point matrices

This paper is devoted to the analysis of the eigenvalue distribution of two classes of block preconditioners for the generalized saddle point problem. Most of the bounds developed improve those appeared in previously published works. Numerical results onto a realistic test problem give evidence of the effectiveness of the estimates on the spectrum of preconditioned matrices. Copyright © 2011 John Wiley & Sons, Ltd.     

Convergence of inexact inverse iteration with application to preconditioned iterative solves

In this paper we study inexact inverse iteration for solving the generalised eigenvalue problem A x=λM x. We show that inexact inverse iteration is a modified Newton method and hence obtain convergence rates for various versions of inexact inverse iteration for the calculation of an algebraically simple eigenvalue. In particular, if the inexact solves are carried out with a tolerance chosen proportional to the eigenvalue residual then quadratic convergence is achieved. We also show how modifying the right hand side in inverse iteration still provides a convergent method, but the rate of convergence will be quadratic only under certain conditions on the right hand side. We discuss the implications of this for the preconditioned iterative solution of the linear systems. Finally we introduce a new ILU preconditioner which is a simple modification to the usual preconditioner, but which has advantages both for the standard form of inverse iteration and for the version with a modified right hand side. Numerical examples are given to illustrate the theoretical results. AMS subject classification (2000)  65F15, 65F10     

A note on spectrum distribution of constraint preconditioned generalized saddle point matrices

In this note, results concerning the eigenvalue distribution and form of the eigenvectors of the constraint preconditioned generalized saddle point matrix and its minimal polynomial are given. These results extend previous ones that appeared in the literature. Copyright © 2009 John Wiley & Sons, Ltd.     

Field-of-values analysis of preconditioned iterative methods for nonsymmetric elliptic problems

Summary. The convergence rate of Krylov subspace methods for the solution of nonsymmetric systems of linear equations, such as GMRES or FOM, is studied. Bounds on the convergence rate are presented which are based on the smallest real part of the field of values of the coefficient matrix and of its inverse. Estimates for these quantities are available during the iteration from the underlying Arnoldi process. It is shown how these bounds can be used to study the convergence properties, in particular, the dependence on the mesh-size and on the size of the skew-symmetric part, for preconditioners for finite element discretizations of nonsymmetric elliptic boundary value problems. This is illustrated for the hierarchical basis and multilevel preconditioners which constitute popular preconditioning strategies for such problems. Received May 3, 1996     

Preconditioning and iterative solution of symmetric indefinite linear systems arising from interior point methods for linear programming

We propose to compute the search direction at each interior-point iteration for a linear program via a reduced augmented system that typically has a much smaller dimension than the original augmented system. This reduced system is potentially less susceptible to the ill-conditioning effect of the elements in the (1,1) block of the augmented matrix. A preconditioner is then designed by approximating the block structure of the inverse of the transformed matrix to further improve the spectral properties of the transformed system. The resulting preconditioned system is likely to become better conditioned toward the end of the interior-point algorithm. Capitalizing on the special spectral properties of the transformed matrix, we further proposed a two-phase iterative algorithm that starts by solving the normal equations with PCG in each IPM iteration, and then switches to solve the preconditioned reduced augmented system with symmetric quasi-minimal residual (SQMR) method when it is advantageous to do so. The experimental results have demonstrated that our proposed method is competitive with direct methods in solving large-scale LP problems and a set of highly degenerate LP problems. Research supported in parts by NUS Research Grant R146-000-076-112 and SMA IUP Research Grant.     

Preconditioned iterative methods for diffusion problems with high‐contrast inclusions

This paper is concerned with robust numerical treatment of an elliptic PDE with high‐contrast coefficients, for which classical finite‐element discretizations yield ill‐conditioned linear systems. This paper introduces a procedure by which the discrete system obtained from a linear finite element discretization of the given continuum problem is converted into an equivalent linear system of the saddle‐point type. Three preconditioned iterative procedures—preconditioned Uzawa, preconditioned Lanczos, and preconditioned conjugate gradient for the square of the matrix—are discussed for a special type of the application, namely, highly conducting particles distributed in the domain. Robust preconditioners for solving the derived saddle‐point problem are proposed and investigated. Robustness with respect to the contrast parameter and the discretization scale is also justified. Numerical examples support theoretical results and demonstrate independence of the number of iterations of the proposed iterative schemes on the contrast in parameters of the problem and the mesh size.     

PAHSS-PTS alternating splitting iterative methods for nonsingular saddle point problems

In this paper, we propose the PAHSS-PTS alternating splitting iterative methods for nonsingular saddle point problems. Convergence properties of the proposed methods are studied and corresponding convergence results are given under some suitable conditions. Numerical experiments are presented to confirm the theoretical results, which impliy that PAHSS-PTS iterative methods are effective and feasible.     

The corrected Uzawa method for solving saddle point problems

In this paper, we consider the solution of linear systems of saddle point type by correcting the Uzawa algorithm, which has been proposed in [K. Arrow, L. Hurwicz, H. Uzawa, Studies in nonlinear programming, Stanford University Press, Stanford, CA, 1958]. We call this method as corrected Uzawa (CU) method. The convergence of the CU method is analyzed for solving nonsingular saddle point problem as well as the semi‐convergence for the singular case. First, the corrected model for the Uzawa algorithm is established, and the CU algorithm is presented. Then we study the geometric meaning of the CU model. Moreover, we introduce the overall reduction coefficient α to measure the effect of the CU process. It is shown that the CU method converges faster than the Uzawa method and several other methods if the overall reduction coefficient α satisfies certain conditions. Numerical experiments are presented to illustrate the theoretical results and examine the numerical effectiveness of the CU method. Copyright © 2015 John Wiley & Sons, Ltd.     

More results on the convergence of iterative methods for the symmetric linear complementarity problem

In an earlier paper, the author has given some necessary and sufficient conditions for the convergence of iterative methods for solving the linear complementarity problem. These conditions may be viewed as global in the sense that they apply to the methods regardless of the constant vector in the linear complementarity problem. More precisely, the conditions characterize a certain class of matrices for which the iterative methods will converge, in a certain sense, to a solution of the linear complementarity problem for all constant vectors. In this paper, we improve on our previous results and establish necessary and sufficient conditions for the convergence of iterative methods for solving each individual linear complementarity problem with a fixed constant vector. Unlike the earlier paper, our present analysis applies only to the symmetric linear complementarity problem. Various applications to a strictly convex quadratic program are also given.The author gratefully acknowledges several stimulating conversations with Professor O. Mangasarian on the subject of this paper. He is also grateful to a referee, who has suggested Lemma 2.2 and the present (stronger) version of Theorem 2.1 as well as several other constructive comments.This research was based on work supported by the National Science Foundation under Grant No. ECS-81-14571, sponsored by the United States Army under Contract No. DAAG29-80-C-0041, and was completed while the author was visiting the Mathematics Research Center at the University of Wisconsin, Madison, Wisconsin.     

Perturbed fixed point iterative methods based on pattern structure

We introduce a new idea of algorithmic structure, called assigning algorithm, using a finite collection of a subclass of strictly quasi‐nonexpansive operators. This new algorithm allows the iteration vectors to take steps on a pattern which is based on a connected directed acyclic graph. The sequential, simultaneous, and string‐averaging methods for solving convex feasibility problems are the special cases of the new algorithm which may be used to reduce idle time of processors in parallel implementations. We give a convergence analysis for such algorithmic structure with perturbation. Also, we extend some existence results of the split common fixed point problem based on the new algorithm. The performance of the new algorithm is illustrated with numerical examples from computed tomography.     

Necessary and sufficient conditions for the convergence of iterative methods for the linear complementarity problem

Necessary and sufficient conditions are established for the convergence of various iterative methods for solving the linear complementarity problem. The fundamental tool used is the classical notion of matrix splitting in numerical analysis. The results derived are similar to some well-known theorems on the convergence of iterative methods for square systems of linear equations. An application of the results to a strictly convex quadratic program is also given.This research was based on work supported by the National Science Foundation under Grant No. ECS-81-14571.The author gratefully acknowledges several comments by K. Truemper on the topics of this paper.     

Strong convergence of composite iterative methods for equilibrium problems and fixed point problems

We introduce a new composite iterative scheme by viscosity approximation method for finding a common point of the set of solutions of an equilibrium problem and the set of fixed points of a nonexpansive mapping in a Hilbert space. It is proved that the sequence generated by the iterative scheme converges strongly to a common point of the set of solutions of an equilibrium problem and the set of fixed points of a nonexpansive mapping. Our results substantially improve the corresponding results of Takahashi and Takahashi [A. Takahashi, W. Takahashi, Viscosity approximation methods for equilibrium problems and fixed point problems in Hilbert spaces, J. Math. Anal. Appl. 331 (2007) 506-515]. Essentially a new approach for finding solutions of equilibrium problems and the fixed points of nonexpansive mappings is provided.     

A class of iterative methods for solving nonlinear projection equations

A class of globally convergent iterative methods for solving nonlinear projection equations is provided under a continuity condition of the mappingF. WhenF is pseudomonotone, a necessary and sufficient condition on the nonemptiness of the solution set is obtained.The author would like to thank two referees for their useful comments on this paper and one of them, in particular, for bringing Ref. 15 to his attention. The author also thanks Professor He for sending him Ref. 23.     

An iterative method for the least squares symmetric solution of matrix equation AXB = C

This paper an iterative method is presented to solve the minimum Frobenius norm residual problem: with unknown symmetric matrix . By the iterative method, for any initial symmetric matrix , a solution can be obtained within finite iteration steps in the absence of roundoff errors, and the solution with least Frobenius norm can be obtained by choosing a special kind of initial symmetric matrix. In addition, in the solution set of the minimum Frobenius norm residual problem, the unique optimal approximation solution to a given matrix in Frobenius norm can be expressed as , where is the least norm symmetric solution of the new minimum residual problem: with . Given numerical examples are show that the iterative method is quite efficient.Research supported by Scientific Research Fund of Hunan Provincial Education Department of China (05C797), by China Postdoctoral Science Foundation (2004035645) and by National Natural Science Foundation of China (10571047).     

A Posteriori Error Estimation for the Dual Mixed Finite Element Method of the Stokes Problem

The paper presents an a posteriori error estimator of residual type for the stationary Stokes problem in a possibly multiply-connected polygonal domain of the plane, using the dual mixed finite element method (FEM). We prove lower and upper error bounds with the explicit dependence of the viscosity parameter and without any regularity assumption on the solution.