Inexact Inverse Iteration for Generalized Eigenvalue Problems

In this paper, we study an inexact inverse iteration with inner-outer iterations for solving the generalized eigenvalu problem Ax = Bx, and analyze how the accuracy in the inner iterations affects the convergence of the outer iterations. By considering a special stopping criterion depending on a threshold parameter, we show that the outer iteration converges linearly with the inner threshold parameter as the convergence rate. We also discuss the total amount of work and asymptotic equivalence between this stopping criterion and a more standard one. Numerical examples are given to illustrate the theoretical results.     

Modified Hermitian and skew‐Hermitian splitting methods for non‐Hermitian positive‐definite linear systems

To further study the Hermitian and non‐Hermitian splitting methods for a non‐Hermitian and positive‐definite matrix, we introduce a so‐called lopsided Hermitian and skew‐Hermitian splitting and then establish a class of lopsided Hermitian/skew‐Hermitian (LHSS) methods to solve the non‐Hermitian and positive‐definite systems of linear equations. These methods include a two‐step LHSS iteration and its inexact version, the inexact Hermitian/skew‐Hermitian (ILHSS) iteration, which employs some Krylov subspace methods as its inner process. We theoretically prove that the LHSS method converges to the unique solution of the linear system for a loose restriction on the parameter α. Moreover, the contraction factor of the LHSS iteration is derived. The presented numerical examples illustrate the effectiveness of both LHSS and ILHSS iterations. Copyright © 2007 John Wiley & Sons, Ltd.     

Inexact inverse subspace iteration for generalized eigenvalue problems

n this paper, we present an inexact inverse subspace iteration method for computing a few eigenpairs of the generalized eigenvalue problem Ax=λBx. We first formulate a version of inexact inverse subspace iteration in which the approximation from one step is used as an initial approximation for the next step. We then analyze the convergence property, which relates the accuracy in the inner iteration to the convergence rate of the outer iteration. In particular, the linear convergence property of the inverse subspace iteration is preserved. Numerical examples are given to demonstrate the theoretical results.     

Inexact Rayleigh Quotient-Type Methods for Eigenvalue Computations

We consider the computation of an eigenvalue and corresponding eigenvector of a Hermitian positive definite matrix A , assuming that good approximations of the wanted eigenpair are already available, as may be the case in applications such as structural mechanics. We analyze efficient implementations of inexact Rayleigh quotient-type methods, which involve the approximate solution of a linear system at each iteration by means of the Conjugate Residuals method. We show that the inexact version of the classical Rayleigh quotient iteration is mathematically equivalent to a Newton approach. New insightful bounds relating the inner and outer recurrences are derived. In particular, we show that even if in the inner iterations the norm of the residual for the linear system decreases very slowly, the eigenvalue residual is reduced substantially. Based on the theoretical results, we examine stopping criteria for the inner iteration. We also discuss and motivate a preconditioning strategy for the inner iteration in order to further accelerate the convergence. Numerical experiments illustrate the analysis.     

On inexact alternating direction implicit iteration for continuous Sylvester equations

In this paper, we study the alternating direction implicit (ADI) iteration for solving the continuous Sylvester equation AX + XB = C , where the coefficient matrices A and B are assumed to be positive semi‐definite matrices (not necessarily Hermitian), and at least one of them to be positive definite. We first analyze the convergence of the ADI iteration for solving such a class of Sylvester equations, then derive an upper bound for the contraction factor of this ADI iteration. To reduce its computational complexity, we further propose an inexact variant of the ADI iteration, which employs some Krylov subspace methods as its inner iteration processes at each step of the outer ADI iteration. The convergence is also analyzed in detail. The numerical experiments are given to illustrate the effectiveness of both ADI and inexact ADI iterations.     

A modified modulus method for symmetric positive‐definite linear complementarity problems

By reformulating the linear complementarity problem into a new equivalent fixed‐point equation, we deduce a modified modulus method, which is a generalization of the classical one. Convergence for this new method and the optima of the parameter involved are analyzed. Then, an inexact iteration process for this new method is presented, which adopts some kind of iterative methods for determining an approximate solution to each system of linear equations involved in the outer iteration. Global convergence for this inexact modulus method and two specific implementations for the inner iterations are discussed. Numerical results show that our new methods are more efficient than the classical one under suitable conditions. Copyright © 2008 John Wiley & Sons, Ltd.     

Banach空间中Reich-Takahashi迭代法的强收敛定理

设E是具有一致正规结构的实Banach空间,其范数是一致Gateaux可微的;设D是E的非空有界闭凸子集,T:D→D是渐近非扩张映象.本文证明了,在一些适当的条件下,由修正的Reich-Takahashi迭代法(1.2)式所定义的序列{xn}强收敛到渐近非扩张映象的不动点,其中x0是D中一任给点,{αn},{β}是区间[0,1]中满足某些限制的实数列.     

Uzawa methods for a class of block three‐by‐three saddle‐point problems

In this work, we consider numerical methods for solving a class of block three‐by‐three saddle‐point problems, which arise from finite element methods for solving time‐dependent Maxwell equations and some other applications. The direct extension of the Uzawa method for solving this block three‐by‐three saddle‐point problem requires the exact solution of a symmetric indefinite system of linear equations at each step. To avoid heavy computations at each step, we propose an inexact Uzawa method, which solves the symmetric indefinite linear system in some inexact way. Under suitable assumptions, we show that the inexact Uzawa method converges to the unique solution of the saddle‐point problem within the approximation level. Two special algorithms are customized for the inexact Uzawa method combining the splitting iteration method and a preconditioning technique, respectively. Numerical experiments are presented, which demonstrated the usefulness of the inexact Uzawa method and the two customized algorithms.     

ON HERMITIAN AND SKEW-HERMITIAN SPLITTING ITERATION METHODS FOR CONTINUOUS SYLVESTER EQUATIONS

We present a Hermitian and skew-Hermitian splitting (HSS) iteration method for solving large sparse continuous Sylvester equations with non-Hermitian and positive definite/semi-definite matrices. The unconditional convergence of the HSS iteration method is proved and an upper bound on the convergence rate is derived. Moreover, to reduce the computing cost, we establish an inexact variant of the HSS iteration method and analyze its convergence property in detail. Numerical results show that the HSS iteration method and its inexact variant are efficient and robust solvers for this class of continuous Sylvester equations.     

Inner iterations in the shift-invert residual Arnoldi method and the Jacobi-Davidson method

We establish a general convergence theory of the Shift-Invert Residual Arnoldi(SIRA)method for computing a simple eigenvalue nearest to a given targetσand the associated eigenvector.In SIRA,a subspace expansion vector at each step is obtained by solving a certain inner linear system.We prove that the inexact SIRA method mimics the exact SIRA well,i.e.,the former uses almost the same outer iterations to achieve the convergence as the latter does if all the inner linear systems are iteratively solved with low or modest accuracy during outer iterations.Based on the theory,we design practical stopping criteria for inner solves.Our analysis is on one step expansion of subspace and the approach applies to the Jacobi-Davidson(JD)method with the fixed targetσas well,and a similar general convergence theory is obtained for it.Numerical experiments confirm our theory and demonstrate that the inexact SIRA and JD are similarly effective and are considerably superior to the inexact SIA.     

On a Chebyshev accelerated splitting iteration method with application to two‐by‐two block linear systems

The Chebyshev accelerated preconditioned modified Hermitian and skew‐Hermitian splitting (CAPMHSS) iteration method is presented for solving the linear systems of equations, which have two‐by‐two block coefficient matrices. We derive an iteration error bound to show that the new method is convergent as long as the eigenvalue bounds are not underestimated. Even when the spectral information is lacking, the CAPMHSS iteration method could be considered as an exponentially converging iterative scheme for certain choices of the method parameters. In this case, the convergence rate is independent of the parameters. Besides, the linear subsystems in each iteration can be solved inexactly, which leads to the inexact CAPMHSS iteration method. The iteration error bound of the inexact method is derived also. We discuss in detail the implementation of CAPMHSS for solving two models arising from the Galerkin finite‐element discretizations of distributed control problems and complex symmetric linear systems. The numerical results show the robustness and the efficiency of the new methods.     

Iterative Solutions of Nonlinear Equations of the Strongly Accretive Type

Let E be a real q-uniformly smooth Banach space. Suppose T is a strongly pseudo-contractive map with open domain D(T) in E. Suppose further that T has a fixed point in D(T). Under various continuity assumptions on T it is proved that each of the Mann iteration process or the Ishikawa iteration method converges strongly to the unique fixed point of T. Related results deal with iterative solutions of nonlinear operator equations involving strongly accretive maps. Explicit error estimates are also provided.     

Tuned preconditioners for inexact two‐sided inverse and Rayleigh quotient iteration

Convergence results are provided for inexact two‐sided inverse and Rayleigh quotient iteration, which extend the previously established results to the generalized non‐Hermitian eigenproblem and inexact solves with a decreasing solve tolerance. Moreover, the simultaneous solution of the forward and adjoint problem arising in two‐sided methods is considered, and the successful tuning strategy for preconditioners is extended to two‐sided methods, creating a novel way of preconditioning two‐sided algorithms. Furthermore, it is shown that inexact two‐sided Rayleigh quotient iteration and the inexact two‐sided Jacobi‐Davidson method (without subspace expansion) applied to the generalized preconditioned eigenvalue problem are equivalent when a certain number of steps of a Petrov–Galerkin–Krylov method is used and when this specific tuning strategy is applied. Copyright © 2014 John Wiley & Sons, Ltd.     

Strong Convergence of an Inexact Proximal Point Algorithm for Equilibrium Problems in Banach Spaces

We develop an inexact proximal point algorithm for solving equilibrium problems in Banach spaces which consists of two principal steps and admits an interesting geometric interpretation. At a certain iterate, first we solve an inexact regularized equilibrium problem with a flexible error criterion to obtain an axillary point. Using this axillary point and the inexact solution of the previous iterate, we construct two appropriate hyperplanes which separate the current iterate from the solution set of the given problem. Then the next iterate is defined as the Bregman projection of the initial point onto the intersection of two halfspaces obtained from the two constructed hyperplanes containing the solution set of the original problem. Assuming standard hypotheses, we present a convergence analysis for our algorithm, establishing that the generated sequence strongly and globally converges to a solution of the problem which is the closest one to the starting point of the algorithm.     

Convergence analysis of projected fixed‐point iteration on a low‐rank matrix manifold

In this paper, we analyze the convergence of a projected fixed‐point iteration on a Riemannian manifold of matrices with fixed rank. As a retraction method, we use the projector splitting scheme. We prove that the convergence rate of the projector splitting scheme is bounded by the convergence rate of standard fixed‐point iteration without rank constraints multiplied by the function of initial approximation. We also provide counterexample to the case when conditions of the theorem do not hold. Finally, we support our theoretical results with numerical experiments.     

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     

An approximate bundle method for solving nonsmooth equilibrium problems

We present an approximate bundle method for solving nonsmooth equilibrium problems. An inexact cutting-plane linearization of the objective function is established at each iteration, which is actually an approximation produced by an oracle that gives inaccurate values for the functions and subgradients. The errors in function and subgradient evaluations are bounded and they need not vanish in the limit. A descent criterion adapting the setting of inexact oracles is put forward to measure the current descent behavior. The sequence generated by the algorithm converges to the approximately critical points of the equilibrium problem under proper assumptions. As a special illustration, the proposed algorithm is utilized to solve generalized variational inequality problems. The numerical experiments show that the algorithm is effective in solving nonsmooth equilibrium problems.     

Convergence analysis of generalized nonlinear inexact Uzawa algorithm for stabilized saddle point problems

This paper deals with a modified nonlinear inexact Uzawa (MNIU) method for solving the stabilized saddle point problem. The modified Uzawa method is an inexact inner-outer iteration with a variable relaxation parameter and has been discussed in the literature for uniform inner accuracy. This paper focuses on the general case when the accuracy of inner iteration can be variable and the convergence of MNIU with variable inner accuracy, based on a simple energy norm. Sufficient conditions for the convergence of MNIU are proposed. The convergence analysis not only greatly improves the existing convergence results for uniform inner accuracy in the literature, but also extends the convergence to the variable inner accuracy that has not been touched in literature. Numerical experiments are given to show the efficiency of the MNIU algorithm.     

φ-强伪压缩映象隐迭代过程的收敛性分析

在任意Banach空间讨论了有限个φ-强伪压缩映射族隐迭代过程的收敛性问题.利用φ的性质和迭代过程本身的特性,得到了隐迭代过程收敛于公共不动点的若干结果.这些结果补充和推广了过去的研究成果.因此它丰富和发展了隐迭代法的理论.     

Banach空间中非线性$\Phi$-伪压缩映象不动点的迭代逼近

本文研究了非线性拟$\Phi$-伪压缩映象与$\Phi$-伪压缩映象的不动点的迭代逼近问题.研究结果表明: 在任意实的Banach空间$E$中,拟$\Phi$-伪压缩映象与$\Phi$-伪压缩映象$T$~($T$不必连续)的具误差的Ishikawa与Mann迭代序列强收敛于$T$的唯一不动点.所得结果不但改进和推广了最近一些文献的相关结果,而且也改进了定理的证明方法.