Analysis of iterative methods for saddle point problems: a unified approach

Zulehner, Walter

doi:10.1090/S0025-5718-01-01324-2

Analysis of iterative methods for saddle point problems: a unified approach
HTML articles powered by AMS MathViewer

by Walter Zulehner PDF

Math. Comp. 71 (2002), 479-505 Request permission

Abstract:

In this paper two classes of iterative methods for saddle point problems are considered: inexact Uzawa algorithms and a class of methods with symmetric preconditioners. In both cases the iteration matrix can be transformed to a symmetric matrix by block diagonal matrices, a simple but essential observation which allows one to estimate the convergence rate of both classes by studying associated eigenvalue problems. The obtained estimates apply for a wider range of situations and are partially sharper than the known estimates in literature. A few numerical tests are given which confirm the sharpness of the estimates.

References

Kenneth J. Arrow, Leonid Hurwicz, and Hirofumi Uzawa, Studies in linear and non-linear programming, Stanford Mathematical Studies in the Social Sciences, II, Stanford University Press, Stanford, Calif., 1958. With contributions by H. B. Chenery, S. M. Johnson, S. Karlin, T. Marschak, R. M. Solow. MR 0108399
Randolph E. Bank, Bruno D. Welfert, and Harry Yserentant, A class of iterative methods for solving saddle point problems, Numer. Math. 56 (1990), no. 7, 645–666. MR 1031439, DOI 10.1007/BF01405194
James H. Bramble and Joseph E. Pasciak, A preconditioning technique for indefinite systems resulting from mixed approximations of elliptic problems, Math. Comp. 50 (1988), no. 181, 1–17. MR 917816, DOI 10.1090/S0025-5718-1988-0917816-8
James H. Bramble, Joseph E. Pasciak, and Apostol T. Vassilev, Analysis of the inexact Uzawa algorithm for saddle point problems, SIAM J. Numer. Anal. 34 (1997), no. 3, 1072–1092. MR 1451114, DOI 10.1137/S0036142994273343
Franco Brezzi and Michel Fortin, Mixed and hybrid finite element methods, Springer Series in Computational Mathematics, vol. 15, Springer-Verlag, New York, 1991. MR 1115205, DOI 10.1007/978-1-4612-3172-1
Howard C. Elman and Gene H. Golub, Inexact and preconditioned Uzawa algorithms for saddle point problems, SIAM J. Numer. Anal. 31 (1994), no. 6, 1645–1661. MR 1302679, DOI 10.1137/0731085
Michel Fortin and Roland Glowinski, Augmented Lagrangian methods, Studies in Mathematics and its Applications, vol. 15, North-Holland Publishing Co., Amsterdam, 1983. Applications to the numerical solution of boundary value problems; Translated from the French by B. Hunt and D. C. Spicer. MR 724072
Wolfgang Hackbusch, Iterative solution of large sparse systems of equations, Applied Mathematical Sciences, vol. 95, Springer-Verlag, New York, 1994. Translated and revised from the 1991 German original. MR 1247457, DOI 10.1007/978-1-4612-4288-8
J. Iliash, T. Rossi, and J. Toivanen, Two iterative methods for solving the Stokes problem, Tech. Report 2, University of Jyväskylä, Department of Mathematics, Laboratory of Scientific Computing, 1993.
Werner Queck, The convergence factor of preconditioned algorithms of the Arrow-Hurwicz type, SIAM J. Numer. Anal. 26 (1989), no. 4, 1016–1030. MR 1005523, DOI 10.1137/0726057
David Silvester and Andrew Wathen, Fast iterative solution of stabilised Stokes systems. II. Using general block preconditioners, SIAM J. Numer. Anal. 31 (1994), no. 5, 1352–1367. MR 1293519, DOI 10.1137/0731070
R. Verfürth, A combined conjugate gradient-multigrid algorithm for the numerical solution of the Stokes problem, IMA J. Numer. Anal. 4 (1984), no. 4, 441–455. MR 768638, DOI 10.1093/imanum/4.4.441