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 1-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.
Similar content being viewed by others
References
Alefeld, G. (1982): On the convergence of the symmetric SOR method for matrices with red-black ordering. Numer. Math.39, 113–117
Alefeld, G., Varga, R.S. (1976): Zur Konvergenz des symmetrischen Relationsverfahrens. Numer. Math.25, 291–295
Axelsson, O. (1977): Solution of linear systems of equations: Iterative methods. In: V.A. Baker, ed., Sparse matrix techniques — Copenhagen 1976. Lecture Notes in Mathematics 572. Springer, Berlin Heidelberg New York, pp. 1–15
Beawens, R. (1979): Factorization iterative methods,M-operators andH-operators. Numer. Math.31, 335–357; Errata in Numer. Math.49, 457 (1986)
Berman, A., Plemmons, J. (1979): Nonnegative matrices in the mathematical sciences. Academic Press, New York
Collatz, L. (1952): Aufgaben monotoner Art. Arch. Math.3, 366–376
Dembo, R.S., Eisenstat, S.C., Steihaug, T. (1982): Inexact Newton methods. SIAM J. Numer. Anal.19, 400–408
Fan, K. (1958): Topological proofs of certain theorems on matrices with non-negative elements. Monatshefte für Mathematik62, 219–237
Frommer, A., Mayer, G. (1989): Convergence of relaxed parallel multisplitting methods. Linear Algebra Appl.119, 141–152
Golub, G.H., Overton, M.L. (1982): Convergence of a two-stage Richardson iterative procedure for solving systems of linear equations. In: G.A. Watson, ed., Numerical analysis (Proceedings of the Ninth Biennial Conference, Dundee, Scotland, 1981). Lecture Notes in Mathematics 912, Springer, Berlin Heidelberg New York, pp. 128–139
Golub, G.H., Overton, M.L. (1988): The convergence of inexact Chebyshev and Richardson iterative methods for solving linear systems. Numer. Math.53, 571–593
Johnson, C.R., Bru, R. (1990): The spectral radius of a product of nonnegative matrices. Linear Algebra Appl.141, 227–240
Krishna, L.B. (1983): Some results on unsymmetric successive overrelaxation method. Numer. Math.42, 155–160
Lanzkron, P.J., Rose, D.J., Szyld, D.B. (1991): Convergence of nested classical iterative methods for linear systems. Numer. Math.58, 685–702
Marek, I., Szyld, D.B. (1990): Comparison theorems for weak splittings of bounded operators. Numer. Math.58, 387–397
Marek, I., Szyld, D.B. (1990): Splittings ofM-operators: Irreducibility and the index of the iteration operator. Numer. Funct. Anal. Optimization,11, 529–553
Mayer, G. (1987): Comparison theorems for iterative methods based on strong splittings. SIAM J. Numer. Anal.24, 215–227
Moré, J.J. (1971): Global convergence of Newton-Gauss-Seidel methods. SIAM J. Numer. Anal.8, 325–336
Neumaier, A. (1984): New techniques for the analysis of linear interval equations. Linear Algebra Appl.58, 273–325
Neumaier, A. (1986): On the comparison ofH-matrices withM-matrices. Linear Algebra Appl.83, 135–141
Neumaier, A. (1990): Interval methods for systems of equations. Cambridge University Press, Cambridge New York
Neumaier, A., Varga, R.S. (1984): Exact convergence and divergence domains for the symmetric successive overrelaxation iterative (SSOR) method applied toH-matrices. Linear Algebra Appl.58, 261–272
Neumann, M. (1984): On bounds for the convergence of the SSOR method forH-matrices. Linear Multilinear Algebra15, 13–21
Nichols, N.K. (1973): On the convergence of two-stage iterative processes for solving linear equations. SIAM J. Numer. Anal.10, 460–469
Ortega, J.M. (1972): Numerical analysis. A second course. Academic Press, New York (reprinted by SIAM, Philadelphia, 1990)
Ortega, J.M., Rheinboldt, W.C. (1970): Iterative solution of nonlinear equations in several variables. Academic Press, New York London
Ostrowski, A.M. (1937): Über die Determinanten mit überwiegender Hauptdiagonale. Comentarii Mathematici Helvetici10, 69–96
Ostrowski, A.M. (1956): Determination mit überwiegender Hauptdiagonale und die absolute Konvergenz von linearen Iterationprozessen. Comentarii Mathematici Helvetici30, 175–210
Rheinboldt, W.C., Vandergraft, J.S. (1973): A simple approach to the Perron-Frobenius theory for positive operators on general partially-ordered finite-dimensional linear spaces. Math. Comput.27, 139–145
Robert, F., Charnay, M., Musy, F. (1975): Itérations chaotiques série-parallèle pour des équations non-linéaires de point fixe. Aplikace Matematiky20, 1–38
Robert, F., (1969): Blocs-H-matrices et convergence des méthodes itératives classiques par blocs. Linear Algebra Appl.2, 223–265
Schneider, H. (1984): Theorems onM-splittings of a singularM-matrix which depend on graph structure. Linear Algebra Appl.58, 407–424
Sherman, A.H. (1978): On Newton-iterative methods for the solution of systems of nonlinear equations. SIAM J. Numer. Anal.15, 755–771
Szyld, D.B., Jones, M.T. (1992): Two-stage and multisplitting methods for the parallel solution of linear systems. SIAM J. Matrix Anal. Appl.13, 671–679
Szyld, D.B., Widlung, O.B. (1992): Variational analysis of some conjugate gradient methods. East-West J. Numer. Anal.1, 1–25
Varga, R.S. (1960): Factorization and normalized iterative methods. In: R.E. Langer, ed., Boundary problems in differential equations. The University of Wisconsin Press, Wisconsin, pp. 121–142
Varga, R.S. (1962): Matrix iterative analysis. Prentice-Hall, Englewood Cliffs, New Jersey
Varga, R.S. (1976): On recurring theorems on diagonal dominance. Linear Algebra Appl.13, 1–9
Varga, R.S., Saff, E.B., Mehrmann, V. (1980): Incomplete factorizations of matrices and connections withH-matrices. SIAM J. Numer. Anal.17, 787–793
Wachspress, E.L. (1966): Iterative Solution of Elliptic Systems. Prentice-Hall, Englewood Cliffs, New Jersey
Young, D.M. (1971): Iterative solution of large linear systems. Academic Press, New York
Author information
Authors and Affiliations
Additional information
This work was supported in part by a Temple University Summer Research Fellowship.
Rights and permissions
About this article
Cite this article
Frommer, A., Szyld, D.B. H-Splittings and two-stage iterative methods. Numer. Math. 63, 345–356 (1992). https://doi.org/10.1007/BF01385865
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01385865