V-cycle convergence of some multigrid methods for ill-posed problems
HTML articles powered by AMS MathViewer
- by Barbara Kaltenbacher PDF
- Math. Comp. 72 (2003), 1711-1730 Request permission
Abstract:
For ill-posed linear operator equations we consider some V-cycle multigrid approaches, that, in the framework of Bramble, Pasciak, Wang, and Xu (1991), we prove to yield level independent contraction factor estimates. Consequently, we can incorporate these multigrid operators in a full multigrid method, that, together with a discrepancy principle, is shown to act as an iterative regularization method for the underlying infinite-dimensional ill-posed problem. Numerical experiments illustrate the theoretical results.References
- D. Braess and W. Hackbusch, A new convergence proof for the multigrid method including the $V$-cycle, SIAM J. Numer. Anal. 20 (1983), no. 5, 967–975. MR 714691, DOI 10.1137/0720066
- James H. Bramble, Multigrid methods, Pitman Research Notes in Mathematics Series, vol. 294, Longman Scientific & Technical, Harlow; copublished in the United States with John Wiley & Sons, Inc., New York, 1993. MR 1247694
- James H. Bramble, Zbigniew Leyk, and Joseph E. Pasciak, The analysis of multigrid algorithms for pseudodifferential operators of order minus one, Math. Comp. 63 (1994), no. 208, 461–478. MR 1254145, DOI 10.1090/S0025-5718-1994-1254145-2
- James H. Bramble and Joseph E. Pasciak, New estimates for multilevel algorithms including the $V$-cycle, Math. Comp. 60 (1993), no. 202, 447–471. MR 1176705, DOI 10.1090/S0025-5718-1993-1176705-9
- James H. Bramble, Joseph E. Pasciak, and Panayot S. Vassilevski, Computational scales of Sobolev norms with application to preconditioning, Math. Comp. 69 (2000), no. 230, 463–480. MR 1651742, DOI 10.1090/S0025-5718-99-01106-0
- James H. Bramble, Joseph E. Pasciak, Jun Ping Wang, and Jinchao Xu, Convergence estimates for multigrid algorithms without regularity assumptions, Math. Comp. 57 (1991), no. 195, 23–45. MR 1079008, DOI 10.1090/S0025-5718-1991-1079008-4
- James H. Bramble, Joseph E. Pasciak, and Jinchao Xu, Parallel multilevel preconditioners, Math. Comp. 55 (1990), no. 191, 1–22. MR 1023042, DOI 10.1090/S0025-5718-1990-1023042-6
- Achi Brandt, Multi-level adaptive solutions to boundary-value problems, Math. Comp. 31 (1977), no. 138, 333–390. MR 431719, DOI 10.1090/S0025-5718-1977-0431719-X
- H. W. Engl and A. Neubauer, On projection methods for solving linear ill-posed problems, Model optimization in exploration geophysics (Berlin, 1986) Theory Practice Appl. Geophys., vol. 1, Friedr. Vieweg, Braunschweig, 1987, pp. 73–92. MR 1008254
- Heinz W. Engl, Martin Hanke, and Andreas Neubauer, Regularization of inverse problems, Mathematics and its Applications, vol. 375, Kluwer Academic Publishers Group, Dordrecht, 1996. MR 1408680
- Charles W. Groetsch, Inverse problems in the mathematical sciences, Vieweg Mathematics for Scientists and Engineers, Friedr. Vieweg & Sohn, Braunschweig, 1993. MR 1247696, DOI 10.1007/978-3-322-99202-4
- C. W. Groetsch and A. Neubauer, Convergence of a general projection method for an operator equation of the first kind, Houston J. Math. 14 (1988), no. 2, 201–208. MR 978726
- Christian Großmann and Hans-Görg Roos, Numerik partieller Differentialgleichungen, 2nd ed., Teubner Studienbücher Mathematik. [Teubner Mathematical Textbooks], B. G. Teubner, Stuttgart, 1994 (German). MR 1312608, DOI 10.1007/978-3-322-96752-7
- Wolfgang Hackbusch, Multigrid methods and applications, Springer Series in Computational Mathematics, vol. 4, Springer-Verlag, Berlin, 1985. MR 814495, DOI 10.1007/978-3-662-02427-0
- Martin Hanke and Curtis R. Vogel, Two-level preconditioners for regularized inverse problems. I. Theory, Numer. Math. 83 (1999), no. 3, 385–402. MR 1715577, DOI 10.1007/s002110050455
- Barbara Kaltenbacher, A projection-regularized Newton method for nonlinear ill-posed problems and its application to parameter identification problems with finite element discretization, SIAM J. Numer. Anal. 37 (2000), no. 6, 1885–1908. MR 1766852, DOI 10.1137/S0036142998347322
- Barbara Kaltenbacher, Regularization by projection with a posteriori discretization level choice for linear and nonlinear ill-posed problems, Inverse Problems 16 (2000), no. 5, 1523–1539. MR 1800607, DOI 10.1088/0266-5611/16/5/322
- Barbara Kaltenbacher, On the regularizing properties of a full multigrid method for ill-posed problems, Inverse Problems 17 (2001), no. 4, 767–788. Special issue to celebrate Pierre Sabatier’s 65th birthday (Montpellier, 2000). MR 1861481, DOI 10.1088/0266-5611/17/4/313
- B. Kaltenbacher, V-cycle convergence of some multigrid methods for ill-posed problems, SFB013-report, University of Linz, 2000.
- B. Kaltenbacher, M. Kaltenbacher, S. Reitzinger, Identification of nonlinear $B-H$ curves based on magnetic field computations and using multigrid preconditioners for ill-posed problems, to appear in Europ. J. Appl. Math., 2002.
- B. Kaltenbacher, J. Schicho, A multigrid method with a priori and a posteriori level choice for the regularization of nonlinear ill-posed problems, Numer. Math., DOI 10.1007/s002110100375, January 2002.
- J. Thomas King, Multilevel algorithms for ill-posed problems, Numer. Math. 61 (1992), no. 3, 311–334. MR 1151773, DOI 10.1007/BF01385512
- Alfred Karl Louis, Inverse und schlecht gestellte Probleme, Teubner StudienbĂĽcher Mathematik. [Teubner Mathematical Textbooks], B. G. Teubner, Stuttgart, 1989 (German). MR 1002946, DOI 10.1007/978-3-322-84808-6
- V. A. Morozov, Regularization methods for ill-posed problems, CRC Press, Boca Raton, FL, 1993. Translated from the 1987 Russian original. MR 1244325
- Frank Natterer, Regularisierung schlecht gestellter Probleme durch Projektionsverfahren, Numer. Math. 28 (1977), no. 3, 329–341 (German, with English summary). MR 488721, DOI 10.1007/BF01389972
- F. Natterer, The mathematics of computerized tomography, B. G. Teubner, Stuttgart; John Wiley & Sons, Ltd., Chichester, 1986. MR 856916
- Peter Oswald, Multilevel finite element approximation, Teubner Skripten zur Numerik. [Teubner Scripts on Numerical Mathematics], B. G. Teubner, Stuttgart, 1994. Theory and applications. MR 1312165, DOI 10.1007/978-3-322-91215-2
- Sergei V. Pereverzev and Siegfried Prössdorf, On the characterization of self-regularization properties of a fully discrete projection method for Symm’s integral equation, J. Integral Equations Appl. 12 (2000), no. 2, 113–130. MR 1771514, DOI 10.1216/jiea/1020282166
- Andreas Rieder, A wavelet multilevel method for ill-posed problems stabilized by Tikhonov regularization, Numer. Math. 75 (1997), no. 4, 501–522. MR 1431213, DOI 10.1007/s002110050250
- A. N. Tihonov and V. Ja. Arsenin, Metody resheniya nekorrektnykh zadach, “Nauka”, Moscow, 1979 (Russian). Second edition, revised and supplemented. MR 566400
- G. M. VaÄnikko and U. A. Khyamarik, Projection methods and self-regularization in ill-posed problems, Izv. Vyssh. Uchebn. Zaved. Mat. 10 (1985), 3–17, 84 (Russian). MR 828379
- G. M. VaÄnikko and A. Yu. Veretennikov, Iteratsionnye protsedury v nekorrektnykh zadachakh, “Nauka”, Moscow, 1986 (Russian). MR 859375
Additional Information
- Barbara Kaltenbacher
- Affiliation: SFB013 Numerical and Symbolic Scientific Computing, University of Linz, Freitaedterstrasse 313, A-4040 Linz, Austria
- Email: barbara.kaltenbacher@sfb013.uni-linz.ac.at
- Received by editor(s): November 21, 2000
- Received by editor(s) in revised form: April 11, 2002
- Published electronically: May 1, 2003
- Additional Notes: The author was supported by the Fonds zur Förderung der wissenschaftlichen Forschung under grant T 7-TEC and project F1308 within Spezialforschungsbereich F013
- © Copyright 2003 American Mathematical Society
- Journal: Math. Comp. 72 (2003), 1711-1730
- MSC (2000): Primary 65J20, 65R30, 65N55
- DOI: https://doi.org/10.1090/S0025-5718-03-01533-3
- MathSciNet review: 1986801