On HSS and AHSS iteration methods for nonsymmetric positive definite Toeplitz systems

Two iteration methods are proposed to solve real nonsymmetric positive definite Toeplitz systems of linear equations. These methods are based on Hermitian and skew-Hermitian splitting (HSS) and accelerated Hermitian and skew-Hermitian splitting (AHSS). By constructing an orthogonal matrix and using a similarity transformation, the real Toeplitz linear system is transformed into a generalized saddle point problem. Then the structured HSS and the structured AHSS iteration methods are established by applying the HSS and the AHSS iteration methods to the generalized saddle point problem. We discuss efficient implementations and demonstrate that the structured HSS and the structured AHSS iteration methods have better behavior than the HSS iteration method in terms of both computational complexity and convergence speed. Moreover, the structured AHSS iteration method outperforms the HSS and the structured HSS iteration methods. The structured AHSS iteration method also converges unconditionally to the unique solution of the Toeplitz linear system. In addition, an upper bound for the contraction factor of the structured AHSS iteration method is derived. Numerical experiments are used to illustrate the effectiveness of the structured AHSS iteration method.     

The effect of non-optimal bases on the convergence of Krylov subspace methods

Summary There are many examples where non-orthogonality of a basis for Krylov subspace methods arises naturally. These methods usually require less storage or computational effort per iteration than methods using an orthonormal basis (optimal methods), but the convergence may be delayed. Truncated Krylov subspace methods and other examples of non-optimal methods have been shown to converge in many situations, often with small delay, but not in others. We explore the question of what is the effect of having a non-optimal basis. We prove certain identities for the relative residual gap, i.e., the relative difference between the residuals of the optimal and non-optimal methods. These identities and related bounds provide insight into when the delay is small and convergence is achieved. Further understanding is gained by using a general theory of superlinear convergence recently developed. Our analysis confirms the observed fact that in exact arithmetic the orthogonality of the basis is not important, only the need to maintain linear independence is. Numerical examples illustrate our theoretical results.This revised version was published online in June 2005 due to a typesetting mistake in the footnote on page 7.     

Erratum to: “On the HSS iteration methods for positive definite Toeplitz linear systems” [J. Comput. Appl. Math. 224 (2009) 709-718]

In [1], Gu and Tian [Chuanqing Gu, Zhaolu Tian, On the HSS iteration methods for positive definite Toeplitz linear systems, J. Comput. Appl. Math. 224 (2009) 709-718] proposed the special HSS iteration methods for positive definite linear systems Ax=b with A∈C^n×n a complex Toeplitz matrix. But we find that the special HSS iteration methods are incorrect. Some examples are given in our paper.     

A note on the convergence of the MSMAOR method for linear complementarity problems

Modulus‐based splitting, as well as multisplitting iteration methods, for linear complementarity problems are developed by Zhong‐Zhi Bai. In related papers (see Bai, Z.‐Z., Zhang, L.‐L.: Modulus‐Based Synchronous Multisplitting Iteration Methods for Linear Complementarity Problems. Numerical Linear Algebra with Applications 20 (2013) 425–439, and the references cited therein), the problem of convergence for two‐parameter relaxation methods (accelerated overrelaxation‐type methods) is analyzed under the assumption that one parameter is greater than the other. Here, we will show how we can avoid this assumption and, consequently, improve the convergence area. Copyright © 2013 John Wiley & Sons, Ltd.     

A family of three-point methods of optimal order for solving nonlinear equations

A family of three-point iterative methods for solving nonlinear equations is constructed using a suitable parametric function and two arbitrary real parameters. It is proved that these methods have the convergence order eight requiring only four function evaluations per iteration. In this way it is demonstrated that the proposed class of methods supports the Kung-Traub hypothesis (1974) [3] on the upper bound 2ⁿ of the order of multipoint methods based on n+1 function evaluations. Consequently, this class of root solvers possesses very high computational efficiency. Numerical examples are included to demonstrate exceptional convergence speed with only few function evaluations.     

On the convergence of splittings for semidefinite linear systems

Recently, Lee et al. [Young-ju Lee, Jinbiao Wu, Jinchao Xu, Ludmil Zikatanov, On the convergence of iterative methods for semidefinite linear systems, SIAM J. Matrix Anal. Appl. 28 (2006) 634-641] introduce new criteria for the semi-convergence of general iterative methods for semidefinite linear systems based on matrix splitting. The new conditions generalize the classical notion of P-regularity introduced by Keller [H.B. Keller, On the solution of singular and semidefinite linear systems by iterations, SIAM J. Numer. Anal. 2 (1965) 281-290]. In view of their results, we consider here stipulations on a splitting A=M-N, which lead to fixed point systems such that, the iterative scheme converges to a weighted Moore-Penrose solution to the system Ax=b. Our results extend the result of Lee et al. to a more general case and we also show that it requires less restrictions on the splittings than Keller’s P-regularity condition to ensure the convergence of iterative scheme.     

A preconditioning approach to the pagerank computation problem

Some spectral properties of the transition matrix of an oriented graph indicate the preconditioning of Euler-Richardson (ER) iterative scheme as a good way to compute efficiently the vertexrank vector associated with such graph. We choose the preconditioner from an algebra U of matrices, thereby obtaining an ER_U method, and we observe that ER_U can outperform ER in terms of rate of convergence. The proposed preconditioner can be updated at a very low cost whenever the graph changes, as is the case when it represents a generic set of information. The particular U utilized requires a surplus of operations per step and memory allocations, which make ER_U superior to ER for not too wide graphs. However, the observed high improvement in convergence rate obtained by preconditioning and the general theory developed, are a reason for investigating different choices of U, more efficient for huge graphs.     

On generalized successive overrelaxation methods for augmented linear systems

For the augmented system of linear equations, Golub, Wu and Yuan recently studied an SOR-like method (BIT 41(2001)71–85). By further accelerating it with another parameter, in this paper we present a generalized SOR (GSOR) method for the augmented linear system. We prove its convergence under suitable restrictions on the iteration parameters, and determine its optimal iteration parameters and the corresponding optimal convergence factor. Theoretical analyses show that the GSOR method has faster asymptotic convergence rate than the SOR-like method. Also numerical results show that the GSOR method is more effective than the SOR-like method when they are applied to solve the augmented linear system. This GSOR method is further generalized to obtain a framework of the relaxed splitting iterative methods for solving both symmetric and nonsymmetric augmented linear systems by using the techniques of vector extrapolation, matrix relaxation and inexact iteration. Besides, we also demonstrate a complete version about the convergence theory of the SOR-like method. Subsidized by The Special Funds For Major State Basic Research Projects (No. G1999032803) and The National Natural Science Foundation (No. 10471146), P.R. China     

Preconditioning Landweber iteration in Hilbert scales

In this paper we investigate convergence of Landweber iteration in Hilbert scales for linear and nonlinear inverse problems. As opposed to the usual application of Hilbert scales in the framework of regularization methods, we focus here on the case s≤0, which (for Tikhonov regularization) corresponds to regularization in a weaker norm. In this case, the Hilbert scale operator L^−2s appearing in the iteration acts as a preconditioner, which significantly reduces the number of iterations needed to match an appropriate stopping criterion. Additionally, we carry out our analysis under significantly relaxed conditions, i.e., we only require instead of which is the usual condition for regularization in Hilbert scales. The assumptions needed for our analysis are verified for several examples and numerical results are presented illustrating the theoretical ones. supported by the Austrian Science Foundation (FWF) under grant SFB/F013     

Preconditioned GAOR methods for solving weighted linear least squares problems

In this paper, we present the preconditioned generalized accelerated overrelaxation (GAOR) method for solving linear systems based on a class of weighted linear least square problems. Two kinds of preconditioning are proposed, and each one contains three preconditioners. We compare the spectral radii of the iteration matrices of the preconditioned and the original methods. The comparison results show that the convergence rate of the preconditioned GAOR methods is indeed better than the rate of the original method, whenever the original method is convergent. Finally, a numerical example is presented in order to confirm these theoretical results.     

Sets of convergence and stability regions

This paper continues the authors' study of the convergence of dynamic iteration methods for large systems of linear initial value problems. We ask for convergence on [0, ) and show how the convergence can be reduced to a graphical test relating the splitting of the matrix to the stability properties of the discretization method.     

Two-step modulus-based matrix splitting iteration method for linear complementarity problems

Bai has recently presented a modulus-based matrix splitting iteration method, which is a powerful alternative for solving the large sparse linear complementarity problems. In this paper, we further present a two-step modulus-based matrix splitting iteration method, which consists of a forward and a backward sweep. Its convergence theory is proved when the system matrix is an H ₊-matrix. Moreover, for the two-step modulus-based relaxation iteration methods, more exact convergence domains are obtained without restriction on the Jacobi matrix associated with the system matrix, which improve the existing convergence theory. Numerical results show that the two-step modulus-based relaxation iteration methods are superior to the modulus-based relaxation iteration methods for solving the large sparse linear complementarity problems.     

ADI preconditioned Krylov methods for large Lyapunov matrix equations

In the present paper, we propose preconditioned Krylov methods for solving large Lyapunov matrix equations AX+XA^T+BB^T=0. Such problems appear in control theory, model reduction, circuit simulation and others. Using the Alternating Direction Implicit (ADI) iteration method, we transform the original Lyapunov equation to an equivalent symmetric Stein equation depending on some ADI parameters. We then define the Smith and the low rank ADI preconditioners. To solve the obtained Stein matrix equation, we apply the global Arnoldi method and get low rank approximate solutions. We give some theoretical results and report numerical tests to show the effectiveness of the proposed approaches.     

Convergent nonnegative matrices and iterative methods for consistent linear systems

Summary In this paper we study linear stationary iterative methods with nonnegative iteration matrices for solving singular and consistent systems of linear equationsAx=b. The iteration matrices for the schemes are obtained via regular and weak regular splittings of the coefficients matrixA. In certain cases when only some necessary, but not sufficient, conditions for the convergence of the iterations schemes exist, we consider a transformation on the iteration matrices and obtain new iterative schemes which ensure convergence to a solution toAx=b. This transformation is parameter-dependent, and in the case where all the eigenvalues of the iteration matrix are real, we show how to choose this parameter so that the asymptotic convergence rate of the new schemes is optimal. Finally, some applications to the problem of computing the stationary distribution vector for a finite homogeneous ergodic Markov chain are discussed.Research sponsored in part by US Army Research Office     

On algebraic multi-level methods for non-symmetric systems - Comparison results

We establish theoretical comparison results for algebraic multi-level methods applied to non-singular non-symmetric M-matrices. We consider two types of multi-level approximate block factorizations or AMG methods, the AMLI and the MAMLI method. We compare the spectral radii of the iteration matrices of these methods. This comparison shows, that the spectral radius of the MAMLI method is less than or equal to the spectral radius of the AMLI method. Moreover, we establish how the quality of the approximations in the block factorization effects the spectral radii of the iteration matrices. We prove comparisons results for different approximations of the fine grid block as well as for the used Schur complement. We also establish a theoretical comparison between the AMG methods and the classical block Jacobi and block Gauss-Seidel methods.     

GSOR方法最优迭代参数的简化推导

对于增广线性系统,Bai等研究了广义SOR方法（Bai Z Z,Parlett B,Wang Z Q.On generaliged successive overrelaxation methods for augmented linear systems.Numerische Mathematik,2005,102（1）：1-38）,并得到其最优迭代参数.给出了另外一种推导最优迭代参数的简化方法,这种方法对于求解其他参数加速定常迭代方法的最优迭代参数非常有意义.     

The rate of convergence of GMRES on a tridiagonal toeplitz linear system. II

This paper continues the recent work of the authors’ [R.-C. Li, W. Zhang, The rate of convergence of GMRES on a tridiagonal Toeplitz linear system, Numer. Math. 112 (2009) 267-293 (electronically published on 19 December 2008)] on the rate of convergence of GMRES for a tridiagonal Toeplitz linear system Ax=b. Much simpler formulas than the earlier ones for GMRES residuals when b is the first or the last column of the identity matrix are established, and these formulas allow us to confirm the rate of convergence that was conjectured but only partially proven earlier. Simpler and sharper bounds than earlier ones when all b’s entries, except its first and last ones, are zeros are also obtained.     

Preconditioned iterative methods for a class of nonlinear eigenvalue problems

This paper proposes new iterative methods for the efficient computation of the smallest eigenvalue of symmetric nonlinear matrix eigenvalue problems of large order with a monotone dependence on the spectral parameter. Monotone nonlinear eigenvalue problems for differential equations have important applications in mechanics and physics. The discretization of these eigenvalue problems leads to nonlinear eigenvalue problems with very large sparse ill-conditioned matrices monotonically depending on the spectral parameter. To compute the smallest eigenvalue of large-scale matrix nonlinear eigenvalue problems, we suggest preconditioned iterative methods: preconditioned simple iteration method, preconditioned steepest descent method, and preconditioned conjugate gradient method. These methods use only matrix-vector multiplications, preconditioner-vector multiplications, linear operations with vectors, and inner products of vectors. We investigate the convergence and derive grid-independent error estimates for these methods. Numerical experiments demonstrate the practical effectiveness of the proposed methods for a model problem.     

Accelerated Landweber iterations for the solution of ill-posed equations

Summary In this paper, the potentials of so-calledlinear semiiterative methods are considered for the approximate solution of linear ill-posed problems and ill conditioned matrix equations. Several efficient two-step methods are presented, most of which have been introduced earlier in the literature. Stipulating certain conditions concerning the smoothness of the solution, a notion of optimal speed of convergence may be formulated. Various direct and converse results are derived to illustrate the properties of this concept.If the problem's right hand side data are contaminated by noise, semiiterative methods may be used asregularization methods. Assuming optimal rate of convergence of the iteration for the unperturbed problem, the regularized approximations will be of order optimal accuracy.To derive these results, specific properties of polynomials are used in connection with the basic theory of solving ill-posed problems. Rather recent results onfast decreasing polynomials are applied to answer an open question of Brakhage.Numerical examples are given including a comparison to the method of conjugate gradients.This research was sponsored by the Deutsche Forschungsgemeinschaft (DFG).     

An additional projection step to He and Liao's method for solving variational inequalities

In this paper, we proposed a modified extragradient method for solving variational inequalities. The method can be viewed as an extension of the method proposed by He and Liao [Improvement of some projection methods for monotone variational inequalities, J. Optim. Theory Appl. 112 (2002) 111–128], by performing an additional projection step at each iteration and another optimal step length is employed to reach substantial progress in each iteration. We used a self-adaptive technique to adjust parameter ρ$\rho$ at each iteration. Under certain conditions, the global convergence of the proposed method is proved. Preliminary numerical experiments are included to compare our method with some known methods.