Convergence theorems for block splitting iterative methods for linear systems

In this paper, we will present the block splitting iterative methods with general weighting matrices for solving linear systems of algebraic equations Ax=b$\mathit{Ax}=b$ when the coefficient matrix A is symmetric positive definite of block form, and establish the convergence theories with respect to the general weighting matrices but special splittings. Finally, a numerical example shows the advantage of this method.     

High order splitting methods for analytic semigroups exist

In this paper, we are concerned with the construction and analysis of high order exponential splitting methods for the time integration of abstract evolution equations which are evolved by analytic semigroups. We derive a new class of splitting methods of orders three to fourteen based on complex coefficients. An optimal convergence analysis is presented for the methods when applied to equations on Banach spaces with unbounded vector fields. These results resolve the open question whether there exist splitting schemes with convergence rates greater then two in the context of semigroups. As a concrete application we consider parabolic equations and their dimension splittings. The sharpness of our theoretical error bounds is further illustrated by numerical experiments.     

P-proper splittings

In this article we introduce the notion of P-proper splitting for square matrices. For an inconsistent linear system of equations \(Ax =b\), we associate an iterative method based on a P-proper splitting of A, which if convergent, converges to the best least squares solution of this system. We extend a result of Stein, using which we prove that if A is positive semidefinite, then the said iterative method converges. Also, we generalize Sylvester’s law of inertia and as an application of this generalization we establish some properties of P-proper splittings. Finally, we prove a comparison theorem for iterative methods associated with P-proper splittings of a positive semidefinite matrix.     

Semiconvergence of nonnegative splittings for singular matrices

Summary. In this paper, we discuss semiconvergence of the matrix splitting methods for solving singular linear systems. The concepts that a splitting of a matrix is regular or nonnegative are generalized and we introduce the terminologies that a splitting is quasi-regular or quasi-nonnegative. The equivalent conditions for the semiconvergence are proved. Comparison theorem on convergence factors for two different quasi-nonnegative splittings is presented. As an application, the semiconvergence of the power method for solving the Markov chain is derived. The monotone convergence of the quasi-nonnegative splittings is proved. That is, for some initial guess, the iterative sequence generated by the iterative method introduced by a quasi-nonnegative splitting converges towards a solution of the system from below or from above. Received August 19, 1997 / Revised version received August 20, 1998 / Published online January 27, 2000     

Defect-based local error estimators for splitting methods,with application to Schrödinger equations,Part I: The linear case

We introduce a defect correction principle for exponential operator splitting methods applied to time-dependent linear Schrödinger equations and construct a posteriori local error estimators for the Lie–Trotter and Strang splitting methods. Under natural commutator bounds on the involved operators we prove asymptotical correctness of the local error estimators, and along the way recover the known a priori convergence bounds. Numerical examples illustrate the theoretical local and global error estimates.     

A class of two‐stage iterative methods for systems of weakly nonlinear equations

The discretizations of many differential equations by the finite difference or the finite element methods can often result in a class of system of weakly nonlinear equations. In this paper, by applying the two-tage iteration technique and in accordance with the special properties of this weakly nonlinear system, we first propose a general two-tage iterative method through the two-tage splitting of the system matrix. Then, by applying the accelerated overrelaxation (AOR) technique of the linear iterative methods, we present a two-tage AOR method, which particularly uses the AOR iteration as the inner iteration and is substantially a relaxed variant of the afore-presented method. For these two classes of methods, we establish their local convergence theories, and precisely estimate their asymptotic convergence factors under some suitable assumptions when the involved nonlinear mapping is only B-differentiable. When the system matrix is either a monotone matrix or an H-matrix, and the nonlinear mapping is a P-bounded mapping, we thoroughly set up the global convergence theories of these new methods. Moreover, under the assumptions that the system matrix is monotone and the nonlinear mapping is isotone, we discuss the monotone convergence properties of the new two-tage iteration methods, and investigate the influence of the matrix splittings as well as the relaxation parameters on the convergence behaviours of these methods. Numerical computations show that our new methods are feasible and efficient for solving the system of weakly nonlinear equations. This revised version was published online in June 2006 with corrections to the Cover Date.     

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 note on properties of splittings of singular symmetric positive semidefinite matrices

Summary. Recently, Benzi and Szyld have published an important paper [1] concerning the existence and uniqueness of splittings for singular matrices. However, the assertion in Theorem 3.9 on the inheriting property of P-regular splitting for singular symmetric positive semidefinite matrices seems to be incorrect. As a complement of paper [1], in this short note we point out that if a matrix T is resulted from a P-regular splitting of a symmetric positive semidefinite matrix A, then splittings induced by T are not all P-regular. Received January 7, 1999 / Published online December 19, 2000     

Operator-splitting methods in respect of eigenvalue problems for nonlinear equations and applications for Burgers equations

In this article we consider iterative operator-splitting methods for nonlinear differential equations with respect to their eigenvalues. The main focus of the proposed idea is the fixed-point iterative scheme that linearizes our underlying equations. On the basis of the approximated eigenvalues of such linearized systems we choose the order of the operators for our iterative splitting scheme. The convergence properties of such a mixed method are studied and demonstrated. We confirm with numerical applications the effectiveness of the proposed scheme in comparison with the standard operator-splitting methods by providing improved results and convergence rates. We apply our results to deposition processes.     

On multisplitting methods for band matrices

Summary. We present new theoretical results on two classes of multisplitting methods for solving linear systems iteratively. These classes are based on overlapping blocks of the underlying coefficient matrix which is assumed to be a band matrix. We show that under suitable conditions the spectral radius of the iteration matrix does not depend on the weights of the method even if these weights are allowed to be negative. For a certain class of splittings we prove an optimality result for with respect to the weights provided that is an M–matrix. This result is based on the fact that the multisplitting method can be represented by a single splitting which in our situation surprisingly turns out to be a regular splitting. Furthermore we show by numerical examples that weighting factors may considerably improve the convergence. Received July 18, 1994 / Revised version received November 20, 1995     

Parallel multisplitting two-stage iterative methods for large sparse systems of weakly nonlinear equations

The finite difference or the finite element discretizations of many differential or integral equations often result in a class of systems of weakly nonlinear equations. In this paper, by reasonably applying both the multisplitting and the two-stage iteration techniques, and in accordance with the special properties of this system of weakly nonlinear equations, we first propose a general multisplitting two-stage iteration method through the two-stage multiple splittings of the system matrix. Then, by applying the accelerated overrelaxation (AOR) technique of the linear iterative methods, we present a multisplitting two-stage AOR method, which particularly uses the AOR-like iteration as inner iteration and is substantially a relaxed variant of the afore-presented method. These two methods have a forceful parallel computing function and are much more suitable to the high-speed multiprocessor systems. For these two classes of methods, we establish their local convergence theories, and precisely estimate their asymptotic convergence factors under some suitable assumptions when the involved nonlinear mapping is only directionally differentiable. When the system matrix is either an H-matrix or a monotone matrix, and the nonlinear mapping is a P-bounded mapping, we thoroughly set up the global convergence theories of these new methods. Moreover, under the assumptions that the system matrix is monotone and the nonlinear mapping is isotone, we discuss the monotone convergence properties of the new multisplitting two-stage iteration methods, and investigate the influence of the multiple splittings as well as the relaxation parameters upon the convergence behaviours of these methods. Numerical computations show that our new methods are feasible and efficient for parallel solving of the system of weakly nonlinear equations. This revised version was published online in August 2006 with corrections to the Cover Date.     

The splitting finite-difference time-domain methods for Maxwell's equations in two dimensions

In this paper, we consider splitting methods for Maxwell's equations in two dimensions. A new kind of splitting finite-difference time-domain methods on a staggered grid is developed. The corresponding schemes consist of only two stages for each time step, which are very simple in computation. The rigorous analysis of the schemes is given. By the energy method, it is proved that the scheme is unconditionally stable and convergent for the problems with perfectly conducting boundary conditions. Numerical dispersion analysis and numerical experiments are presented to show the efficient performance of the proposed methods. Furthermore, the methods are also applied to solve a scattering problem successfully.     

H-Splittings and two-stage iterative methods

Summary Convergence of two-stage iterative methods for the solution of linear systems is studied. Convergence of the non-stationary method is shown if the number of inner iterations becomes sufficiently large. TheR ₁-factor of the two-stage method is related to the spectral radius of the iteration matrix of the outer splitting. Convergence is further studied for splittings ofH-matrices. These matrices are not necessarily monotone. Conditions on the splittings are given so that the two-stage method is convergent for any number of inner iterations.This work was supported in part by a Temple University Summer Research Fellowship.     

SIGN MATRIX, REGULAR SPLITTINGS AND MONOTONIC ENCLOSURE OF SOLUTIONS FOR NONLINEAR SYSTEM OF EQUATIONS, PARTI

In this paper we introduce the sign matrix of a nonlinear system of equations x = Gx to characterize its hybrid and asynchronous monotonicity as well as convexity. Based on the configuration of the matrix, we define a new type of regular splittings of the system with which the solvability and construction of solutions for the system are transformed to those of the couple systems of the splitting formIt is shown that this couple systems is a general model for developing monotonic enclosure methods of solutions for various types of nonlinear system of equations.     

Operator splitting methods for pricing American options under stochastic volatility

We consider the numerical pricing of American options under Heston’s stochastic volatility model. The price is given by a linear complementarity problem with a two-dimensional parabolic partial differential operator. We propose operator splitting methods for performing time stepping after a finite difference space discretization. The idea is to decouple the treatment of the early exercise constraint and the solution of the system of linear equations into separate fractional time steps. With this approach an efficient numerical method can be chosen for solving the system of linear equations in the first fractional step before making a simple update to satisfy the early exercise constraint. Our analysis suggests that the Crank–Nicolson method and the operator splitting method based on it have the same asymptotic order of accuracy. The numerical experiments show that the operator splitting methods have comparable discretization errors. They also demonstrate the efficiency of the operator splitting methods when a multigrid method is used for solving the systems of linear equations.     

Existence and uniqueness of splittings for stationary iterative methods with applications to alternating methods

Summary. Given a nonsingular matrix , and a matrix of the same order, under certain very mild conditions, there is a unique splitting , such that . Moreover, all properties of the splitting are derived directly from the iteration matrix . These results do not hold when the matrix is singular. In this case, given a matrix and a splitting such that , there are infinitely many other splittings corresponding to the same matrices and , and different splittings can have different properties. For instance, when is nonnegative, some of these splittings can be regular splittings, while others can be only weak splittings. Analogous results hold in the symmetric positive semidefinite case. Given a singular matrix , not for all iteration matrices there is a splitting corresponding to them. Necessary and sufficient conditions for the existence of such splittings are examined. As an illustration of the theory developed, the convergence of certain alternating iterations is analyzed. Different cases where the matrix is monotone, singular, and positive (semi)definite are studied. Received September 5, 1995 / Revised version received April 3, 1996     

Comparison of splittings used with the conjugate gradient algorithm

We consider several possible criteria for comparing splittings used with the conjugate gradient algorithm. We present sharp upper bounds for the error at each step of the algorithm and compare several widely used splittings with respect to their effect on these sharp upper bounds. We then consider a more stringent comparison test, and present necessary and sufficient conditions for the error at each step with one splitting to be smaller than that with another, for all pairs of corresponding initial guesses.     

Regular splittings and monotone iteration functions

Summary In this paper we introduce the set of so-called monotone iteration functions (MI-functions) belonging to a given function. We prove necessary and sufficient conditions in order that a given MI-function is (in a precisely defined sense) at least as fast as a second one.Regular splittings of a function which were initially introduced for linear functions by R.S. Varga in 1960 are generating MI-functions in a natural manner.For linear functions every MI-function is generated by a regular splitting. For nonlinear functions, however, this is generally not the case.     

Convergence of nested classical iterative methods for linear systems

Summary Classical iterative methods for the solution of algebraic linear systems of equations proceed by solving at each step a simpler system of equations. When this system is itself solved by an (inner) iterative method, the global method is called a two-stage iterative method. If this process is repeated, then the resulting method is called a nested iterative method. We study the convergence of such methods and present conditions on the splittings corresponding to the iterative methods to guarantee convergence forany number of inner iterations. We also show that under the conditions presented, the spectral radii of the global iteration matrices decrease when the number of inner iterations increases. The proof uses a new comparison theorem for weak regular splittings. We extend our results to larger classes of iterative methods, which include iterative block Gauss-Seidel. We develop a theory for the concatenation of such iterative methods. This concatenation appears when different numbers of inner interations are performed at each outer step. We also analyze block methods, where different numbers of inner iterations are performed for different diagonal blocks.Dedicated to Richard S. Varga on the occasion of his sixtieth birthdayP.J. Lanzkron was supported by Exxon Foundation Educational grant 12663 and the UNISYS Corporation; D.J. Rose was supported by AT&T Bell Laboratories, the Microelectronic Center of North Carolina and the Office of Naval Research under contract number N00014-85-K-0487; D.B. Szyld was supported by the National Science Foundation grant DMS-8807338.     

Heegaard splittings of twisted torus knots

Little is known on the classification of Heegaard splittings for hyperbolic 3-manifolds. Although Kobayashi gave a complete classification of Heegaard splittings for the exteriors of 2-bridge knots, our knowledge of other classes is extremely limited. In particular, there are very few hyperbolic manifolds that are known to have a unique minimal genus splitting. Here we demonstrate that an infinite class of hyperbolic knot exteriors, namely exteriors of certain “twisted torus knots” originally studied by Morimoto, Sakuma and Yokota, have a unique minimal genus Heegaard splitting of genus two. We also conjecture that these manifolds possess irreducible yet weakly reducible splittings of genus three. There are no known examples of such Heegaard splittings.