The Convergence Theory Analysis Of Two-stage Iterations And Matrix Multisplitting For Solution Of Linear Systems Of Equations

The two-stage iterative methods for solution of large sparse linear systems of equations have been attention-getting never before with the advent of parallel matrix multisplitting methods since nineties early last century.The two-stage iterative methods are composed of inner and outer iterations,so they are also called inner and outer iterative methods or nested iterative methods.The inner iterations make it possible to avoid solving systems of equations exactly in whole iterative process.To get the exact solutions repeatedly may be a big work,it is therefore an effective approach to get the approximation solutions through a certain(inner) iteration process simply in computing and storing.In multiprocessors,the precondition of implementing effective parallel computing is a good overall load balance in each processor.The flexible choice of the number of inner iterations in two-stage iterative methods provides a feasible approach for a good load balance.This paper discusses two-stage iterative methods for the solution of large sparse nonsingular linear systems of equations which coefficient matrices are mostly monotone or H-matrix.The study involves asymptotic rate of convergence,optimal number of inner iterations,the convergence of relaxed two-stage multisplitting methods and the convergence theories for matrix multisplitting sequence or two-stage multisplitting sequence.The main and innovative work in this paper includes several aspects as follow.1.It is showed that the iteration sequence of stationary two-stage iterative methods converges uniformly to that of outer iterative methods and its convergence rate is decided by the R₁ - factor of inner iterations.An estimation of R₁-factor of two-stage iterative methods are obtained using the R₁-factor of inner and outer iterative methods, along with the number of inner iterations.For monotone matrices,it is showed that the convergence rate of non-stationary two-stage iterative methods is never faster than that of outer iterative methods and it is possible for both to become equal.According to the analysis for convergence rate,we discuss the block SOR two-stage iterative methods of which the outer iterative methods are block SOR iterations.The numerical instance is presented and the minimal number of inner iterations required to converge is estimated for block SOR two-stage iterative methods.2.A more fine estimations of R₁-factor is found out for stationary block Jacobi two-stage iterative methods for M-matrix.A comparison theorem is presented when the inner iterations is point SOR or point Jacobi methods.The objective function to optimize the number of inner iterations is established and approximately optimal number of inner iterations is defined for stationary block Jacobi two-stage iterative methods. 3.A union of two-stage methods and matrix multisplitting brings the two-stage muttisplitting methods.For the relaxed two-stage multisplitting methods of which the relaxation factor is introduced by extrapolation in inner iterations,an comparison theorem is obtained,the convergence interval of relaxation factor is improved from well known interval(0,1]to a new one(0,ω₀),1＜ω₀≤2,under the same or weakly conditions.Moreover,the same results are obtained when ILU factorization is used for inner splittings.4.Nonstationary two-stage multisplitting methods fall into the iterative methods based on matix multisplitting sequence.We obtained the more concision convergence conditions for synchronous and asynchronous methods of matrix multisplitting sequence.Moreover,these conditions are showed prerequisite for convergence. Different convergence conditions are showed for synchronous and asynchronous methods,as well as deffirent asynchronous models.Using these results,some new convergence properties are obtained for the iterative methods based on matrix two-stage multisplitting sequence.