Summary
We consider the numerical solution of indefinite systems of linear equations arising in the calculation of saddle points. We are mainly concerned with sparse systems of this type resulting from certain discretizations of partial differential equations. We present an iterative method involving two levels of iteration, similar in some respects to the Uzawa algorithm. We relate the rates of convergence of the outer and inner iterations, proving that, under natural hypotheses, the outer iteration achieves the rate of convergence of the inner iteration. The technique is applied to finite element approximations of the Stokes equations.
Similar content being viewed by others
References
Arnold, D.N., Brezzi, F., Fortin, M. Astable finite element for the Stokes equations. Calcolo21, 337–344 (1984)
Aziz, A.K., Babuška I.: Part I, survey lectures on the mathematical foundations of the finite element method. In: The mathematical foundations of the finite element method with applications to partial differential equations, pp. 1–362. New York: Academic Press 1972
Bank, R.E., Dupont, T.F.: Analysis of a two level scheme for solving finite element equations. Tech. Rep. CNA-159, Center for Numerical Analysis, University of Texas at Austin 1980
Bank, R.E., Dupont, T.F., Yserentant, H.: The hierarchical basis multigrid method. Numer. Math.52, 427–458 (1988)
Bramble, J.H., Pasciak, J.E.: A preconditioning technique for indefinite systems resulting from mixed approximations of elliptic problems. Math. Comput.181, 1–17 (1988)
Brezzi, F.: On the existence, uniqueness and approximation of saddle-point problems arising from Lagrange multipliers. R.A.I.R.O.8, 129–151 (1974)
Axelsson, O.: Preconditioning indefinite problems by regularization. SIAM J. Numer. Anal.16, 58–69 (1979)
Dyn, N., Ferguson, W.E.: Numerical solution of equality constrained quadratic programming problems. Math. Comput.41, 165–170 (1983)
Girault, V., Raviart, P.: Finite element methods for Navier-Stokes equations. Berlin Heidelberg New York: Springer 1986
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)
Hackbusch, W.: Multigrid methods and applications. Berlin Heidelberg New York: Springer 1985
Maitre, J.F., Musy, F., Nigon, P.: A fast solver for the Stokes equations using multigrid with a Uzawa smoother, In: Notes on numerical fluid mechanics, pp. 77–83. Braunschweig: Vieweg 1985
McCormick, S. (Editor): Multigrid methods. SIAM, Philadelphia 1987
Verfürth, R.: A combined conjugate gradient-multigrid algorithm for the numerical solution of the Stokes problem. IMA J. Numer. Anal.4, 441–455 (1984)
Verfürth, R.: Iterative methods for the numerical solution of mixed finite element approximations of the Stokes problem. Tech. Rep. 379, Institut National de Recherche en Informatique et en Automatique 1985
Verfürth, R.: A multilevel algorithm for mixed problems. SIAM J. Numer. Anal.21, 264–271 (1984)
Verfürth, R.: A multilevel algorithm for mixed problems. II. treatment of the mini-element. SIAM J. Numer. Anal.25, 285–293 (1988)
Wittum, G.: Multigrid methods for Stokes and Navier stokes equations. Transforming smoothers: algorithms and numerical results. Numer. Math.54, 543–563 (1989)
Wittum, G.: On the convergence of multigrid methods with transforming smoothers: theory with applications to the Navier-Stokes equations. Tech. Rep. 468, Sonderforschungsbereich 123, Universität Heidelberg 1988
Yserentant, H.: On the multi-level splitting of finite element space. Numer. Math.49, 379–412 (1986)
Author information
Authors and Affiliations
Additional information
The work of this author was supported by the Office of Naval Research under contract N00014-82K-0197, by Avions Marcel Dassault, 78 Quai Marcel Dassault, 92214 St Cloud, France, and by Direction des Recherches Etudes et Techniques, 26 boulevard Victor, F-75996 Paris Armées, France
The work of this author was supported by Avions Marcel Daussault-Breguet Aviation, 78 quai Marcel Daussault, F-92214 St Cloud, France and by Direction des Recherches Etudes et Techniques, 26 boulevard Victor, F-75996 Paris Armées, France
The work of this author was supported by Konrad-Zuse-Zentrum für Informationstechnik Berlin, Federal Republic of Germany
Rights and permissions
About this article
Cite this article
Bank, R.E., Welfert, B.D. & Yserentant, H. A class of iterative methods for solving saddle point problems. Numer. Math. 56, 645–666 (1989). https://doi.org/10.1007/BF01405194
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01405194