×

Backward step control for Hilbert space problems. (English) Zbl 1412.65039

Summary: We analyze backward step control globalization for finding zeros of Gâteaux-differentiable functions that map from a Banach space to a Hilbert space. The results include global convergence to a distinctive solution characterized by propagating the initial guess by a generalized Newton flow with guaranteed bounds on the discrete nonlinear residual norm decrease and an (also numerically) easily controllable asymptotic linear residual convergence rate. The convergence theory can be exploited to construct efficient numerical methods, which we demonstrate for the case of a Krylov-Newton method and an approximation-by-discretization multilevel framework. Both approaches optimize the asymptotic linear residual convergence rate, either over the Krylov subspace or through adaptive discretization, which in turn yields practical and efficient stopping criteria and refinement strategies that balance the nonlinear residuals with the relative residuals of the linear systems. We apply these methods to the class of nonlinear elliptic boundary value problems and present numerical results for the Carrier equation and the minimum surface equation.

MSC:

65J15 Numerical solutions to equations with nonlinear operators
65F08 Preconditioners for iterative methods
58C15 Implicit function theorems; global Newton methods on manifolds
74S05 Finite element methods applied to problems in solid mechanics
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ainsworth, M., Oden, J.T.: A posteriori error estimation in finite element analysis. Pure and Applied Mathematics (New York). Wiley, New York (2000) · Zbl 1008.65076 · doi:10.1002/9781118032824
[2] Amann, H.: Ordinary Differential Equations, de Gruyter Studies in Mathematics, vol. 13. Walter de Gruyter & Co., Berlin (1990) · doi:10.1515/9783110853698
[3] Ascher, U., Osborne, M.: A note on solving nonlinear equations and the natural criterion function. J. Optim. Theory Appl. 55(1), 147-152 (1987) · Zbl 0622.90074 · doi:10.1007/BF00939050
[4] Bangerth, W., Davydov, D., Heister, T., Heltai, L., Kanschat, G., Kronbichler, M., Maier, M., Turcksin, B., Wells, D.: The deal.II library, version 8.4. J. Numer. Math. 24(3), 135-141 (2016) · Zbl 1348.65187 · doi:10.1515/jnma-2016-1045
[5] Bangerth, W., Hartmann, R., Kanschat, G.: deal.II - a general purpose object oriented finite element library. ACM Trans. Math. Softw. 33(4), 24/1-24/27 (2007) · Zbl 1365.65248 · doi:10.1145/1268776.1268779
[6] Bank, R.E., Rose, D.J.: Global approximate Newton methods. Numer. Math. 37(2), 279-295 (1981) · Zbl 0442.65034 · doi:10.1007/BF01398257
[7] Battles, Z., Trefethen, L.N.: An extension of MATLAB to continuous functions and operators. SIAM J. Sci. Comput. 25(5), 1743-1770 (2004) · Zbl 1057.65003 · doi:10.1137/S1064827503430126
[8] Becker, R., Rannacher, R.: An optimal control approach to a posteriori error estimation in finite element methods. Acta Numer. 10, 1-102 (2001) · Zbl 1105.65349 · doi:10.1017/S0962492901000010
[9] Bender, C.M., Orszag, S.A.: Advanced Mathematical Methods for Scientists and Engineers. I. Springer, New York (1999). Asymptotic methods and perturbation theory, Reprint of the 1978 original · Zbl 0938.34001 · doi:10.1007/978-1-4757-3069-2
[10] Birkisson, A., Driscoll, T.A.: Automatic Fréchet differentiation for the numerical solution of boundary-value problems. ACM Trans. Math. Software 38(4), Article 26, 29 pages (2012) · Zbl 1365.65192 · doi:10.1145/2331130.2331134
[11] Bock, H.G.: Randwertproblemmethoden Zur Parameteridentifizierung in Systemen Nichtlinearer Differentialgleichungen, Bonner Mathematische Schriften, vol. 183. Bonn, Universität Bonn (1987) · Zbl 0622.65064
[12] Bock, H.G., Kostina, E.A., Schlöder, J.P.: On the role of natural level functions to achieve global convergence for damped Newton methods. In: Powell, M.J.D., Scholtes, S. (eds.) System Modelling and Optimization. Methods, Theory and Applications, pp. 51-74, Kluwer (2000) · Zbl 0982.65068
[13] Brezinski, C.: Numerical stability of a quadratic method for solving systems of nonlinear equations. Computing 14(3), 205-211 (1975) · Zbl 0302.65042 · doi:10.1007/BF02246426
[14] Davidenko, D.F.: On a new method of numerical solution of systems of nonlinear equations. Doklady Akad. Nauk SSSR (N.S.) 88, 601-602 (1953)
[15] Dembo, R.S., Eisenstat, S.C., Steihaug, T.: Inexact Newton methods. SIAM J. Numer. Anal. 19(2), 400-408 (1982) · Zbl 0478.65030 · doi:10.1137/0719025
[16] Dennis, J.E. Jr, Moré, J.J.: Quasi-Newton methods, motivation and theory. SIAM Rev. 19(1), 46-89 (1977) · Zbl 0356.65041 · doi:10.1137/1019005
[17] Deuflhard, P.: A modified Newton method for the solution of ill-conditioned systems of nonlinear equations with applications to multiple shooting. Numer. Math. 22, 289-311 (1974) · Zbl 0313.65070 · doi:10.1007/BF01406969
[18] Deuflhard, P.: Global inexact Newton methods for very large scale nonlinear problems. Impact Comput. Sci. Engrg. 3(4), 366-393 (1991) · Zbl 0745.65032 · doi:10.1016/0899-8248(91)90004-E
[19] Deuflhard, P.: Newton Methods for Nonlinear Problems, Springer Series in Computational Mathematics, vol. 35. Springer, Heidelberg (2011). Affine invariance and adaptive algorithms · Zbl 1226.65043
[20] Deuflhard, P., Weiser, M.: Global inexact Newton multilevel FEM for nonlinear elliptic problems. In: Multigrid Methods V (Stuttgart, 1996), Lect. Notes Comput. Sci. Eng., vol. 3, pp. 71-89. Springer, Berlin (1998) · Zbl 0926.65135
[21] Driscoll, T.A., Hale, N., Trefethen, L.N. (eds.): Chebfun Guide. Pafnuty Publications, Oxford (2014)
[22] Evans, L.C.: Partial Differential Equations, Graduate Studies in Mathematics, 2nd edn., vol. 19. American Mathematical Society, Providence (2010)
[23] Gago, J.P. de S.R., Kelly, D.W., Zienkiewicz, O.C., Babuška, I.: A posteriori error analysis and adaptive processes in the finite element method. II. Adaptive mesh refinement. Int. J. Numer. Methods Eng. 19(11), 1621-1656 (1983) · Zbl 0534.65069 · doi:10.1002/nme.1620191104
[24] Galántai, A., Abaffy, J.: Always convergent iteration methods for nonlinear equations of Lipschitz functions. Numer. Algor. 69(2), 443-453 (2015) · Zbl 1319.65036 · doi:10.1007/s11075-014-9905-1
[25] Gasparo, M.G., Papini, A., Pasquali, A.: Some properties of GMRES in Hilbert spaces. Numer. Funct. Anal. Optim. 29(11-12), 1276-1285 (2008) · Zbl 1167.65023 · doi:10.1080/01630560802580786
[26] Goldberg, H., Kampowsky, W., Tröltzsch, F.: On Nemytskij operators in Lp-spaces of abstract functions. Math. Nachr. 155, 127-140 (1992) · Zbl 0760.47031 · doi:10.1002/mana.19921550110
[27] Grätsch, T., Bathe, K.J.: A posteriori error estimation techniques in practical finite element analysis. Comput. Struct. 83(4-5), 235-265 (2005) · doi:10.1016/j.compstruc.2004.08.011
[28] Günnel, A., Herzog, R., Sachs, E.: A note on preconditioners and scalar products in Krylov subspace methods for self-adjoint problems in Hilbert space. Electron. Trans. Numer. Anal. 41, 13-20 (2014) · Zbl 1295.65062
[29] Hairer, E., Wanner, G.: Solving Ordinary Differential Equations II, Springer Series in Computational Mathematics, 2nd edn., vol. 14. Springer, Berlin (1996) · Zbl 1192.65097 · doi:10.1007/978-3-642-05221-7
[30] Hamilton, R.S.: The inverse function theorem of Nash and Moser. Bull. Amer. Math. Soc. (N.S.) 7(1), 65-222 (1982) · Zbl 0499.58003 · doi:10.1090/S0273-0979-1982-15004-2
[31] Hestenes, M.R., Stiefel, E.: Methods of conjugate gradients for solving linear systems. J. Res. Natl. Bur. Stand. 49, 409-436 (1952) · Zbl 0048.09901 · doi:10.6028/jres.049.044
[32] Hohmann, A.: Inexact Gauss Newton Methods for Parameter Dependent Nonlinear Problems. Ph.D. thesis, Freie Universität Berlin (1994) · Zbl 0941.65517
[33] Janssen, B., Kanschat, G.: Adaptive multilevel methods with local smoothing for H1- and Hcurl-conforming high order finite element methods. SIAM J. Sci. Comput. 33(4), 2095-2114 (2011) · Zbl 1230.65133 · doi:10.1137/090778523
[34] Kelly, D.W., Gago, J.P. de S.R., Zienkiewicz, O.C., Babuška, I.: A posteriori error analysis and adaptive processes in the finite element method. I. Error analysis. Int. J. Numer. Methods Eng. 19(11), 1593-1619 (1983) · Zbl 0534.65068 · doi:10.1002/nme.1620191103
[35] Kronbichler, M., Kormann, K.: A generic interface for parallel cell-based finite element operator application. Comput. Fluids 63, 135-147 (2012) · Zbl 1365.76121 · doi:10.1016/j.compfluid.2012.04.012
[36] Lieb, E.H., Loss, M.: Analysis, Graduate Studies in Mathematics, 2nd edn., vol. 14. American Mathematical Society, Providence (2001)
[37] Nevanlinna, O.: Convergence of iterations for linear equations. Lectures in mathematics. Birkhäuser, Basel, Boston, Berlin (1993) · Zbl 0846.47008
[38] Olver, S., Townsend, A.: A fast and well-conditioned spectral method. SIAM Rev. 55(3), 462-489 (2013) · Zbl 1273.65182 · doi:10.1137/120865458
[39] Paige, C.C., Saunders, M.A.: Solutions of sparse indefinite systems of linear equations. SIAM J. Numer. Anal. 12(4), 617-629 (1975) · Zbl 0319.65025 · doi:10.1137/0712047
[40] Potschka, A.: A Direct Method for Parabolic PDE Constrained Optimization Problems. Advances in Numerical Mathematics. Springer, Berlin (2013)
[41] Potschka, A.: Backward step control for global Newton-type methods. SIAM J. Numer. Anal. 54(1), 361-387 (2016) · Zbl 1382.65145 · doi:10.1137/140968586
[42] Rannacher, R., Vihharev, J.: Adaptive finite element analysis of nonlinear problems: balancing of discretization and iteration errors. J. Numer. Math. 21(1), 23-61 (2013) · Zbl 1267.65184 · doi:10.1515/jnum-2013-0002
[43] Saad, Y., Schultz, M.H.: GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Stat. Comput. 7(3), 856-869 (1986) · Zbl 0599.65018 · doi:10.1137/0907058
[44] Trefethen, L.N.: Computing numerically with functions instead of numbers. Math. Comput. Sci. 1(1), 9-19 (2007) · Zbl 1145.41302 · doi:10.1007/s11786-007-0001-y
[45] Wachsmuth, G.: Differentiability of implicit functions: beyond the implicit function theorem. J. Math. Anal. Appl. 414(1), 259-272 (2014) · Zbl 1316.47050 · doi:10.1016/j.jmaa.2014.01.007
[46] Yosida, K.: Functional Analysis, 5th edn. Springer, Berlin (1978) · Zbl 0365.46001 · doi:10.1007/978-3-642-96439-8
[47] Ypma, T.J.: Local convergence of inexact Newton methods. SIAM J. Numer. Anal. 21(3), 583-590 (1984) · Zbl 0566.65037 · doi:10.1137/0721040
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.