Article

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
Summary:
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.
References:
 E.L. Allgower, K. Böhmer: Application of the mesh independence principle to mesh refinement strategies. SIAM J. Numer. Anal. 24 (1987), 1335-1351. DOI 10.1137/0724086 | MR 0917455
 E. L. Allgower K. Böhmer F. A. Potra, W. C. Rheinboldt: A mesh-independence principle for operator equations and their discretizations. SIAM J. Numer. Anal. 23 (1986), 160-169. DOI 10.1137/0723011 | MR 0821912
 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. MR 0678608
 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.
 O. Axelsson V. Eijkhout B. Polman, P. Vassilewski: Incomplete block-matrix factorization iterative methods for convection-diffusion problems. BIT 29(1989), 867-889. MR 1038134
 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.
 R. S. Dembo S. C. Eisenstat, T. Steihaug: Inexact Newton Methods. SIAM J. Numer. Anal. 19 (1982), 400-408. DOI 10.1137/0719025 | MR 0650059
 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.
 L. V. Kantorovich: On Newton's method for functional equations. Dokl. Akad. Nauk SSSR 59 (1948), 1237-1249.
 M.M. Vainberg: Variational Method and Method of Monotone Operators in the Theory of Nonlinear Equations. Wiley, New York, 1973. MR 0467428 | Zbl 0279.47022
 J. Xu: Oral communication, 1992. Zbl 1169.76302
 T. Yamamoto: A unified derivation of several error bounds for Newton's process. J. Соmр. Appl. Math. 12/13 (1985), 179-191. MR 0793952 | Zbl 0582.65047