On mesh independence and Newton-type methods

Owe Axelsson

Applications of Mathematics (1993)

  • Volume: 38, Issue: 4-5, page 249-265
  • ISSN: 0862-7940

Abstract

top
Mesh-independent convergence of Newton-type methods for the solution of nonlinear partial differential equations is discussed. First, under certain local smoothness assumptions, it is shown that by properly relating the mesh parameters H and h for a coarse and a fine discretization mesh, it suffices to compute the solution of the nonlinear equation on the coarse mesh and subsequently correct it once using the linearized (Newton) equation on the fine mesh. In this way the iteration error will be of the same order as the discretization error. The proper relation is found to be H = h 1 / α where in the ideal case, α = 4 . This means that in practice the coarse mesh is very coarse. To solve the coarse mesh problem it is shown that under a Hölder continuity assumption, a truncated and approximate generalized conjugate gradient method with search directions updated from an (inexact) Newton direction vector, converges globally, i.e. independent of the initial vector. Further, it is shown that the number of steps before the superlinear rate of convergence sets in is bounded, independent of the mesh parametr.

How to cite

top

Axelsson, Owe. "On mesh independence and Newton-type methods." Applications of Mathematics 38.4-5 (1993): 249-265. <http://eudml.org/doc/15753>.

@article{Axelsson1993,
abstract = {Mesh-independent convergence of Newton-type methods for the solution of nonlinear partial differential equations is discussed. First, under certain local smoothness assumptions, it is shown that by properly relating the mesh parameters $H$ and $h$ for a coarse and a fine discretization mesh, it suffices to compute the solution of the nonlinear equation on the coarse mesh and subsequently correct it once using the linearized (Newton) equation on the fine mesh. In this way the iteration error will be of the same order as the discretization error. The proper relation is found to be $H=h^1^/^\alpha $where in the ideal case, $\alpha =4$. This means that in practice the coarse mesh is very coarse. To solve the coarse mesh problem it is shown that under a Hölder continuity assumption, a truncated and approximate generalized conjugate gradient method with search directions updated from an (inexact) Newton direction vector, converges globally, i.e. independent of the initial vector. Further, it is shown that the number of steps before the superlinear rate of convergence sets in is bounded, independent of the mesh parametr.},
author = {Axelsson, Owe},
journal = {Applications of Mathematics},
keywords = {nonlinear problems; Newton methods; mesh-independent convergence; two-evel mesh method; nonlinear strongly monotone operator equations; Hilbert space; iteration error; discretization error; global convergence; conjugate gradient type method; superlinear rate of convergence; mesh independence; Newton-type methods; nonlinear strongly monotone operator equations; Hilbert space; iteration error; discretization error; global convergence; conjugate gradient type method; superlinear rate of convergence},
language = {eng},
number = {4-5},
pages = {249-265},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {On mesh independence and Newton-type methods},
url = {http://eudml.org/doc/15753},
volume = {38},
year = {1993},
}

TY - JOUR
AU - Axelsson, Owe
TI - On mesh independence and Newton-type methods
JO - Applications of Mathematics
PY - 1993
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 38
IS - 4-5
SP - 249
EP - 265
AB - Mesh-independent convergence of Newton-type methods for the solution of nonlinear partial differential equations is discussed. First, under certain local smoothness assumptions, it is shown that by properly relating the mesh parameters $H$ and $h$ for a coarse and a fine discretization mesh, it suffices to compute the solution of the nonlinear equation on the coarse mesh and subsequently correct it once using the linearized (Newton) equation on the fine mesh. In this way the iteration error will be of the same order as the discretization error. The proper relation is found to be $H=h^1^/^\alpha $where in the ideal case, $\alpha =4$. This means that in practice the coarse mesh is very coarse. To solve the coarse mesh problem it is shown that under a Hölder continuity assumption, a truncated and approximate generalized conjugate gradient method with search directions updated from an (inexact) Newton direction vector, converges globally, i.e. independent of the initial vector. Further, it is shown that the number of steps before the superlinear rate of convergence sets in is bounded, independent of the mesh parametr.
LA - eng
KW - nonlinear problems; Newton methods; mesh-independent convergence; two-evel mesh method; nonlinear strongly monotone operator equations; Hilbert space; iteration error; discretization error; global convergence; conjugate gradient type method; superlinear rate of convergence; mesh independence; Newton-type methods; nonlinear strongly monotone operator equations; Hilbert space; iteration error; discretization error; global convergence; conjugate gradient type method; superlinear rate of convergence
UR - http://eudml.org/doc/15753
ER -

References

top
  1. E.L. Allgower, K. Böhmer, 10.1137/0724086, SIAM J. Numer. Anal. 24 (1987), 1335-1351. (1987) MR0917455DOI10.1137/0724086
  2. E. L. Allgower K. Böhmer F. A. Potra, W. C. Rheinboldt, 10.1137/0723011, SIAM J. Numer. Anal. 23 (1986), 160-169. (1986) MR0821912DOI10.1137/0723011
  3. O. Axelsson, On global convergence of iterative methods in Iterative Solution of Nonlinear Systems of Equations, LNM # 953 (editors R. Ansore et al), Springer Verlag, 1980. (1980) MR0678608
  4. O. Axelsson, On the global convergence of Newton step nonlinear generalized conjugate gradient methods, Report 9118, Department of Mathematics, University of Nijmegen, the Netherlands, 1991. (1991) 
  5. O. Axelsson V. Eijkhout B. Polman, P. Vassilewski, Incomplete block-matrix factorization iterative methods for convection-diffusion problems, BIT 29(1989), 867-889. (1989) MR1038134
  6. O. Axelsson, B. Layton, A two-level methods for the discretization of nonlinear boundary value problems, Report, Department of Mathematics, University of Nijmegen, the Netherlands, 1992. (1992) 
  7. R. S. Dembo S. C. Eisenstat, T. Steihaug, 10.1137/0719025, SIAM J. Numer. Anal. 19 (1982), 400-408. (1982) MR0650059DOI10.1137/0719025
  8. P. Deuflhaard, F. A. Potra, Asymptotic mesh independence of Newton-Galerkin methods via a refined Mysovskii theorem, Preprint SC 90-9, Konrad-Zuse-Zentrum für Informationstechnik, Berlin, 1990. (1990) 
  9. L. V. Kantorovich, On Newton's method for functional equations, Dokl. Akad. Nauk SSSR 59 (1948), 1237-1249. (1948) 
  10. M.M. Vainberg, Variational Method and Method of Monotone Operators in the Theory of Nonlinear Equations, Wiley, New York, 1973. (1973) Zbl0279.47022MR0467428
  11. J. Xu, [unknown], Oral communication, 1992. (1992) Zbl1169.76302
  12. T. Yamamoto, A unified derivation of several error bounds for Newton's process, J. Соmр. Appl. Math. 12/13 (1985), 179-191. (1985) Zbl0582.65047MR0793952

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.