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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bank, R.E., Rose, D.J.: Global approximate Newton methods. Numer. Math.37, 279–295 (1981)
Baudet, G.M.: Asynchronous iterative methods for multiprocessors. J. ACM25, 226–244 (1978)
Berman, A., Plemmons, R.J.: Nonnegative matrices in the mathematical sciences. New York: Academic Press 1979
Chazan, D., Miranker, W.: Chaotic relaxation. Linear Algebra Appl.2, 199–222 (1969)
Csordas, G., Varga, R.S.: Comparisons of regular splittings of matrices. Numer. Math.44, 23–35 (1984)
Dembo, R.S., Eisenstat, S.C., Steihaug, T.: Inexact newton methods. SIAM J. Numer. Anal.19, 400–408 (1982)
Diaz. J.C., Jines, W.R., Steihaug, T.: On a convergence criterion for linear (inner) iterative solvers for reservoir simulation. In: Proceedings of the 1985 SPE Reservoir Simulation Symposium, Richardson, Texas, 1985, Society of Petroleum Engineers, pp. 41–48. Paper SPE 13500
Elsner, L.: Comparisons of weak regular splittings and multisplitting methods. Numer. Math.56, 283–289 (1989)
Finogenov, S.A., Kusnetsov, Y.A.: Two-stage fictitious components methods for solving the Dirichlet boundary value problem. Sov. J. Numer. Anal. Math. Modelling3, 301–323 (1988)
Gantmacher, F.R.: Applications of the theory of matrices. New York: Interscience 1959
Golub, G.H., Overton, M.L.: Convergence of a two-stage Richardson iterative procedure for solving systems of linear equations. In: Numerical analysis (Proceedings of the Ninth Biennial Conference, Dundee, Scotland, 1981), Lecture Notes in Mathematics 912, G. Watson, ed., New York, 1982, Heidelberg Berlin New York: Springer, pp. 128–139
Golub, G.H., Overton, M.L.: The convergence of inexact Chebyshev and Richardson iterative methods for solving linear systems. Numer. Math.53, 571–593 (1988)
Marcus, M., Minc, H.: Survey of matrix theory and matrix inequalities. Boston: Allyn and Bacon 1964
Marek, I., Szyld, D.B.: Comparison theorems for weak splittings of bounded operators. Numer. Math.58, 387–397 (1990)
Miellou, J.-C.: Algorithmes de relaxation à retards. RAIRO9, 55–82 (1975)
Miller, V.A., Neumann, M.: A note on comparison theorems for nonnegative mtrices. Numer. Math.47, 427–434 (1985)
Neumann, M., Plemmons, R.J.: Convergence of parallel multisplitting methods forM-matrices. Linear Algebra Appl.88–89, 559–574 (1987)
Nichols, N.K.: On the convergence of two-stage iterative processes for solving linear equations. SIAM J. Numer. Anal.10, 460–469 (1973)
O'Leary, D.P., White, R.E.: Multi-splittings of matrices and parallel solution of linear systems. SIAM J. Algebraic Discrete Methods6, 630–640 (1985)
Ortega, J.M., Rheinboldt, W.C.: Monotone iterations for nonlinear equations with application to Gauss-Seidel methods. SIAM J. Numer. Anal.4, 171–190 (1967)
Ortega, J.M., Rheinboldt, W.C.: Iterative solution of nonlinear equations in several variables. New York London: Academic Press 1970
Rheinboldt, W.C., Vandergraft, J.S.: A simple approach to the Perron-Frobenius theory for positive operators on general partially-ordered finite-dimensional linear spaces. Math. Comput.27, 139–145 (1973)
Robert, F., Charnay, M., Musy, F.: Itérations chaotiques série-parallèle pour des équations non-linéaires de point fixe. Aplikace Matematiky20, 1–38 (1975)
Rodrigue, G.: Inner/outer iterative methods and numerical Schwarz algorithms. Parallel Comput.2, 205–218 (1985)
Varga, R.S.: Factorization and normalized iterative methods. In: Langer, R. E. (ed.), Boundary problems in differential equations. pp. 121–142, Madison: The University of Wisconsin Press 1960
Varga, R.S.: Matrix iterative analysis. Englewood Cliffs, New Jersey: Prentice-Hall 1962
Wachspress, E.L.: Iterative solution of ellipic systems. Englewood Cliffs, New Jersey: Prentice-Hall 1966
Woznicki, Z.: Two-sweep iterative methods for solving large linear systems and their applications to the numerical solution of multi-group multi-dimensional neutron diffusion equation. Ph.D thesis, Institute of Nuclear Research, Swierk k Otwocka, Poland 1973
Young, D.M.: Iterative solution of large linear systems. New York: Academic Press 1971
Author information
Authors and Affiliations
Additional information
Dedicated to Richard S. Varga on the occasion of his sixtieth birthday
P.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.
Rights and permissions
About this article
Cite this article
Lanzkron, P.J., Rose, D.J. & Szyld, D.B. Convergence of nested classical iterative methods for linear systems. Numer. Math. 58, 685–702 (1990). https://doi.org/10.1007/BF01385649
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01385649