Regularization of nonlinear ill-posed problems by exponential integrators

Marlis Hochbruck; Michael Hönig; Alexander Ostermann

ESAIM: Mathematical Modelling and Numerical Analysis (2009)

  • Volume: 43, Issue: 4, page 709-720
  • ISSN: 0764-583X

Abstract

top
The numerical solution of ill-posed problems requires suitable regularization techniques. One possible option is to consider time integration methods to solve the Showalter differential equation numerically. The stopping time of the numerical integrator corresponds to the regularization parameter. A number of well-known regularization methods such as the Landweber iteration or the Levenberg-Marquardt method can be interpreted as variants of the Euler method for solving the Showalter differential equation. Motivated by an analysis of the regularization properties of the exact solution of this equation presented by [U. Tautenhahn, Inverse Problems10 (1994) 1405–1418], we consider a variant of the exponential Euler method for solving the Showalter ordinary differential equation. We discuss a suitable discrepancy principle for selecting the step sizes within the numerical method and we review the convergence properties of [U. Tautenhahn, Inverse Problems10 (1994) 1405–1418], and of our discrete version [M. Hochbruck et al., Technical Report (2008)]. Finally, we present numerical experiments which show that this method can be efficiently implemented by using Krylov subspace methods to approximate the product of a matrix function with a vector.

How to cite

top

Hochbruck, Marlis, Hönig, Michael, and Ostermann, Alexander. "Regularization of nonlinear ill-posed problems by exponential integrators." ESAIM: Mathematical Modelling and Numerical Analysis 43.4 (2009): 709-720. <http://eudml.org/doc/250593>.

@article{Hochbruck2009,
abstract = { The numerical solution of ill-posed problems requires suitable regularization techniques. One possible option is to consider time integration methods to solve the Showalter differential equation numerically. The stopping time of the numerical integrator corresponds to the regularization parameter. A number of well-known regularization methods such as the Landweber iteration or the Levenberg-Marquardt method can be interpreted as variants of the Euler method for solving the Showalter differential equation. Motivated by an analysis of the regularization properties of the exact solution of this equation presented by [U. Tautenhahn, Inverse Problems10 (1994) 1405–1418], we consider a variant of the exponential Euler method for solving the Showalter ordinary differential equation. We discuss a suitable discrepancy principle for selecting the step sizes within the numerical method and we review the convergence properties of [U. Tautenhahn, Inverse Problems10 (1994) 1405–1418], and of our discrete version [M. Hochbruck et al., Technical Report (2008)]. Finally, we present numerical experiments which show that this method can be efficiently implemented by using Krylov subspace methods to approximate the product of a matrix function with a vector. },
author = {Hochbruck, Marlis, Hönig, Michael, Ostermann, Alexander},
journal = {ESAIM: Mathematical Modelling and Numerical Analysis},
keywords = {Nonlinear ill-posed problems; asymptotic regularization; exponential integrators; variable step sizes; convergence; optimal convergence rates.; nonlinear ill-posed problems; variable step sizes; optimal convergence rates},
language = {eng},
month = {7},
number = {4},
pages = {709-720},
publisher = {EDP Sciences},
title = {Regularization of nonlinear ill-posed problems by exponential integrators},
url = {http://eudml.org/doc/250593},
volume = {43},
year = {2009},
}

TY - JOUR
AU - Hochbruck, Marlis
AU - Hönig, Michael
AU - Ostermann, Alexander
TI - Regularization of nonlinear ill-posed problems by exponential integrators
JO - ESAIM: Mathematical Modelling and Numerical Analysis
DA - 2009/7//
PB - EDP Sciences
VL - 43
IS - 4
SP - 709
EP - 720
AB - The numerical solution of ill-posed problems requires suitable regularization techniques. One possible option is to consider time integration methods to solve the Showalter differential equation numerically. The stopping time of the numerical integrator corresponds to the regularization parameter. A number of well-known regularization methods such as the Landweber iteration or the Levenberg-Marquardt method can be interpreted as variants of the Euler method for solving the Showalter differential equation. Motivated by an analysis of the regularization properties of the exact solution of this equation presented by [U. Tautenhahn, Inverse Problems10 (1994) 1405–1418], we consider a variant of the exponential Euler method for solving the Showalter ordinary differential equation. We discuss a suitable discrepancy principle for selecting the step sizes within the numerical method and we review the convergence properties of [U. Tautenhahn, Inverse Problems10 (1994) 1405–1418], and of our discrete version [M. Hochbruck et al., Technical Report (2008)]. Finally, we present numerical experiments which show that this method can be efficiently implemented by using Krylov subspace methods to approximate the product of a matrix function with a vector.
LA - eng
KW - Nonlinear ill-posed problems; asymptotic regularization; exponential integrators; variable step sizes; convergence; optimal convergence rates.; nonlinear ill-posed problems; variable step sizes; optimal convergence rates
UR - http://eudml.org/doc/250593
ER -

References

top
  1. C. Böckmann and P. Pornsawad, Iterative Runge-Kutta-type methods for nonlinear ill-posed problems. Inverse Problems24 (2008) 025002.  
  2. J. Daniel, W.B. Gragg, L. Kaufman and G.W. Stewart, Reorthogonalization and stable algorithms for updating the Gram-Schmidt QR factorization. Math. Comp. 30 (1976) 772–795.  
  3. V.L. Druskin and L.A. Knizhnerman, Krylov subspace approximations of eigenpairs and matrix functions in exact and computer arithmetic. Numer. Lin. Alg. Appl.2 (1995) 205–217.  
  4. H.W. Engl, K. Kunisch and A. Neubauer, Convergence rates for Tikhonov regularization of nonlinear ill-posed problems. Inverse Problems5 (1989) 523–540.  
  5. B. Hackl, Geometry Variations, Level Set and Phase-field Methods for Perimeter Regularized Geometric Inverse Problems. Ph.D. Thesis, Johannes Keppler Universität Linz, Austria (2006).  
  6. M. Hanke, A regularizing Levenberg-Marquardt scheme, with applications to inverse groundwater filtration problems. Inverse Problems13 (1997) 79–95.  
  7. M. Hanke, A. Neubauer and O. Scherzer, A convergence analysis of the Landweber iteration for nonlinear ill-posed problems. Numer. Math.72 (1995) 21–37.  
  8. M. Hochbruck and C. Lubich, On Krylov subspace approximations to the matrix exponential operator. SIAM J. Numer. Anal.34 (1997) 1911–1925.  
  9. M. Hochbruck and A. Ostermann, Explicit exponential Runge-Kutta methods for semilinear parabolic problems. SIAM J. Numer. Anal.43 (2005) 1069–1090.  
  10. M. Hochbruck, M. Hönig and A. Ostermann, A convergence analysis of the exponential Euler iteration for nonlinear ill-posed problems. Inv. Prob.25 (2009) 075009.  
  11. M. Hochbruck, A. Ostermann and J. Schweitzer, Exponential Rosenbrock-type methods. SIAM J. Numer. Anal.47 (2009) 786–803.  
  12. T. Hohage and S. Langer, Convergence analysis of an inexact iteratively regularized Gauss-Newton method under general source conditions. Journal of Inverse and Ill-Posed Problems15 (2007) 19–35.  
  13. M. Hönig, Asymptotische Regularisierung schlecht gestellter Probleme mittels steifer Integratoren. Diplomarbeit, Universität Karlsruhe, Germany (2004).  
  14. B. Kaltenbacher, A. Neubauer and O. Scherzer, Iterative Regularization Methods for Nonlinear Ill-Posed Problems. De Gruyter, Berlin, New York (2008).  
  15. A. Neubauer, Tikhonov regularization for non-linear ill-posed problems: optimal convergence rates and finite-dimensional approximation. Inverse Problems5 (1989) 541–557.  
  16. A. Rieder, On the regularization of nonlinear ill-posed problems via inexact Newton iterations. Inverse Problems15 (1999) 309–327.  
  17. A. Rieder, On convergence rates of inexact Newton regularizations. Numer. Math.88 (2001) 347–365.  
  18. A. Rieder, Inexact Newton regularization using conjugate gradients as inner iteration. SIAM J. Numer. Anal.43 (2005) 604–622.  
  19. A. Rieder, Runge-Kutta integrators yield optimal regularization schemes. Inverse Problems21 (2005) 453–471.  
  20. T.I. Seidman and C.R. Vogel, Well-posedness and convergence of some regularization methods for nonlinear ill-posed problems. Inverse Problems5 (1989) 227–238.  
  21. D. Showalter, Representation and computation of the pseudoinverse. Proc. Amer. Math. Soc.18 (1967) 584–586.  
  22. U. Tautenhahn, On the asymptotical regularization of nonlinear ill-posed problems. Inverse Problems10 (1994) 1405–1418.  
  23. J. van den Eshof and M. Hochbruck, Preconditioning Lanczos approximations to the matrix exponential. SIAM J. Sci. Comp.27 (2006) 1438–1457.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.