Explicit and efficient error estimation for convex minimization problems

Bartels, Sören; Kaltenbach, Alex

doi:10.1090/mcom/3821

Explicit and efficient error estimation for convex minimization problems
HTML articles powered by AMS MathViewer

by Sören Bartels and Alex Kaltenbach HTML | PDF

Math. Comp. 92 (2023), 2247-2279 Request permission

Abstract:

We combine a systematic approach for deriving general a posteriori error estimates for convex minimization problems based on convex duality relations with a recently derived generalized Marini formula. The a posteriori error estimates are quasi constant-free and apply to a large class of variational problems including the $p$-Dirichlet problem, as well as degenerate minimization, obstacle and image de-noising problems. In addition, these a posteriori error estimates are based on a comparison to a given non-conforming finite element solution. For the $p$-Dirichlet problem, these a posteriori error bounds are equivalent to residual type a posteriori error bounds and, hence, reliable and efficient.

References

Mark Ainsworth and J. Tinsley Oden, A posteriori error estimation in finite element analysis, Pure and Applied Mathematics (New York), Wiley-Interscience [John Wiley & Sons], New York, 2000. MR 1885308, DOI 10.1002/9781118032824
A. C. Aitken, On Bernoulli’s numerical solution of algebraic equations, Proc. Roy. Soc. Edinburgh (1926), 280–305, DOI 10.1017/S0370164600022070.
Immanuel Anjam and Dirk Pauly, An elementary method of deriving a posteriori error equalities and estimates for linear partial differential equations, Comput. Methods Appl. Math. 19 (2019), no. 2, 311–322. MR 3935892, DOI 10.1515/cmam-2017-0060
D. N. Arnold and F. Brezzi, Mixed and nonconforming finite element methods: implementation, postprocessing and error estimates, RAIRO Modél. Math. Anal. Numér. 19 (1985), no. 1, 7–32 (English, with French summary). MR 813687, DOI 10.1051/m2an/1985190100071
Balay S., et al. 2019. PETSc web page, https://www.mcs.anl.gov/petsc.
John W. Barrett and W. B. Liu, Finite element approximation of the $p$-Laplacian, Math. Comp. 61 (1993), no. 204, 523–537. MR 1192966, DOI 10.1090/S0025-5718-1993-1192966-4
Sören Bartels, Numerical methods for nonlinear partial differential equations, Springer Series in Computational Mathematics, vol. 47, Springer, Cham, 2015. MR 3309171, DOI 10.1007/978-3-319-13797-1
Sören Bartels, Nonconforming discretizations of convex minimization problems and precise relations to mixed methods, Comput. Math. Appl. 93 (2021), 214–229. MR 4253261, DOI 10.1016/j.camwa.2021.04.014
Sören Bartels and Alex Kaltenbach, Error estimates for total-variation regularized minimization problems with singular dual solutions, Numer. Math. 152 (2022), no. 4, 881–906. MR 4511189, DOI 10.1007/s00211-022-01324-w
Sören Bartels and Marijo Milicevic, Primal-dual gap estimators for a posteriori error analysis of nonsmooth minimization problems, ESAIM Math. Model. Numer. Anal. 54 (2020), no. 5, 1635–1660. MR 4127951, DOI 10.1051/m2an/2019074
Sören Bartels and Zhangxian Wang, Orthogonality relations of Crouzeix-Raviart and Raviart-Thomas finite element spaces, Numer. Math. 148 (2021), no. 1, 127–139. MR 4265901, DOI 10.1007/s00211-021-01199-3
Sören Bartels and Carsten Carstensen, A convergent adaptive finite element method for an optimal design problem, Numer. Math. 108 (2008), no. 3, 359–385. MR 2365822, DOI 10.1007/s00211-007-0122-x
Liudmila Belenki, Lars Diening, and Christian Kreuzer, Optimality of an adaptive finite element method for the $p$-Laplacian equation, IMA J. Numer. Anal. 32 (2012), no. 2, 484–510. MR 2911397, DOI 10.1093/imanum/drr016
Dietrich Braess and Joachim Schöberl, Equilibrated residual error estimator for edge elements, Math. Comp. 77 (2008), no. 262, 651–672. MR 2373174, DOI 10.1090/S0025-5718-07-02080-7
Dietrich Braess, Finite elements, 3rd ed., Cambridge University Press, Cambridge, 2007. Theory, fast solvers, and applications in elasticity theory; Translated from the German by Larry L. Schumaker. MR 2322235, DOI 10.1017/CBO9780511618635
Susanne C. Brenner and L. Ridgway Scott, The mathematical theory of finite element methods, 3rd ed., Texts in Applied Mathematics, vol. 15, Springer, New York, 2008. MR 2373954, DOI 10.1007/978-0-387-75934-0
C. Carstensen and D. J. Liu, Nonconforming FEMs for an optimal design problem, SIAM J. Numer. Anal. 53 (2015), no. 2, 874–894. MR 3327357, DOI 10.1137/130927103
J. Manuel Cascon, Christian Kreuzer, Ricardo H. Nochetto, and Kunibert G. Siebert, Quasi-optimal convergence rate for an adaptive finite element method, SIAM J. Numer. Anal. 46 (2008), no. 5, 2524–2550. MR 2421046, DOI 10.1137/07069047X
Antonin Chambolle and Thomas Pock, Crouzeix-Raviart approximation of the total variation on simplicial meshes, J. Math. Imaging Vision 62 (2020), no. 6-7, 872–899. MR 4126455, DOI 10.1007/s10851-019-00939-3
Andrej Cherkaev, Variational methods for structural optimization, Applied Mathematical Sciences, vol. 140, Springer-Verlag, New York, 2000. MR 1763123, DOI 10.1007/978-1-4612-1188-4
M. Crouzeix and P.-A. Raviart, Conforming and nonconforming finite element methods for solving the stationary Stokes equations. I, Rev. Française Automat. Informat. Recherche Opérationnelle Sér. Rouge 7 (1973), no. R-3, 33–75. MR 343661
Philippe Destuynder and Brigitte Métivet, Explicit error bounds in a conforming finite element method, Math. Comp. 68 (1999), no. 228, 1379–1396. MR 1648383, DOI 10.1090/S0025-5718-99-01093-5
Lars Diening and Christian Kreuzer, Linear convergence of an adaptive finite element method for the $p$-Laplacian equation, SIAM J. Numer. Anal. 46 (2008), no. 2, 614–638. MR 2383205, DOI 10.1137/070681508
Willy Dörfler, A convergent adaptive algorithm for Poisson’s equation, SIAM J. Numer. Anal. 33 (1996), no. 3, 1106–1124. MR 1393904, DOI 10.1137/0733054
Carsten Ebmeyer and WB. Liu, Quasi-norm interpolation error estimates for the piecewise linear finite element approximation of $p$-Laplacian problems, Numer. Math. 100 (2005), no. 2, 233–258. MR 2135783, DOI 10.1007/s00211-005-0594-5
Ivar Ekeland and Roger Témam, Convex analysis and variational problems, Corrected reprint of the 1976 English edition, Classics in Applied Mathematics, vol. 28, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1999. Translated from the French. MR 1727362, DOI 10.1137/1.9781611971088
Alexandre Ern and Jean-Luc Guermond, Finite elements I—Approximation and interpolation, Texts in Applied Mathematics, vol. 72, Springer, Cham, [2021] ©2021. MR 4242224, DOI 10.1007/978-3-030-56341-7
Alexandre Ern and Martin Vohralík, Adaptive inexact Newton methods with a posteriori stopping criteria for nonlinear diffusion PDEs, SIAM J. Sci. Comput. 35 (2013), no. 4, A1761–A1791. MR 3072765, DOI 10.1137/120896918
Alexandre Ern and Martin Vohralík, Four closely related equilibrated flux reconstructions for nonconforming finite elements, C. R. Math. Acad. Sci. Paris 351 (2013), no. 1-2, 77–80 (English, with English and French summaries). MR 3019767, DOI 10.1016/j.crma.2013.01.001
Thirupathi Gudi, A new error analysis for discontinuous finite element methods for linear elliptic problems, Math. Comp. 79 (2010), no. 272, 2169–2189. MR 2684360, DOI 10.1090/S0025-5718-10-02360-4
Thirupathi Gudi, Some nonstandard error analysis of discontinuous Galerkin methods for elliptic problems, Calcolo 47 (2010), no. 4, 239–261. MR 2739021, DOI 10.1007/s10092-010-0022-9
Alexander Haberl, Dirk Praetorius, Stefan Schimanko, and Martin Vohralík, Convergence and quasi-optimal cost of adaptive algorithms for nonlinear operators including iterative linearization and algebraic solver, Numer. Math. 147 (2021), no. 3, 679–725. MR 4224933, DOI 10.1007/s00211-021-01176-w
Weimin Han, A posteriori error analysis via duality theory, Advances in Mechanics and Mathematics, vol. 8, Springer-Verlag, New York, 2005. With applications in modeling and numerical approximations. MR 2101057
I. Hlaváček, J. Haslinger, J. Nečas, and J. Lovíšek, Solution of variational inequalities in mechanics, Applied Mathematical Sciences, vol. 66, Springer-Verlag, New York, 1988. Translated from the Slovak by J. Jarník. MR 952855, DOI 10.1007/978-1-4612-1048-1
Hunter, J. D. 2007. Matplotlib: a 2d graphics environment, Comput. Sci. Eng. 9, 90–95. DOI 10.1109/MCSE.2007.55.
D. J. Liu and Z. R. Chen, The adaptive finite element method for the P-Laplace problem, Appl. Numer. Math. 152 (2020), 323–337. MR 4067381, DOI 10.1016/j.apnum.2019.11.018
D. J. Liu, A. Q. Li, and Z. R. Chen, Nonconforming FEMs for the $p$-Laplace problem, Adv. Appl. Math. Mech. 10 (2018), no. 6, 1365–1383. MR 3859897, DOI 10.4208/aamm
Wenbin Liu and Ningning Yan, Quasi-norm a priori and a posteriori error estimates for the nonconforming approximation of $p$-Laplacian, Numer. Math. 89 (2001), no. 2, 341–378. MR 1855829, DOI 10.1007/PL00005470
Wenbin Liu and Ningning Yan, Quasi-norm local error estimators for $p$-Laplacian, SIAM J. Numer. Anal. 39 (2001), no. 1, 100–127. MR 1860718, DOI 10.1137/S0036142999351613
Wenbin Liu and Ningning Yan, On quasi-norm interpolation error estimation and a posteriori error estimates for $p$-Laplacian, SIAM J. Numer. Anal. 40 (2002), no. 5, 1870–1895. MR 1950626, DOI 10.1137/S0036142901393589
Anders Logg and Garth N. Wells, DOLFIN: automated finite element computing, ACM Trans. Math. Software 37 (2010), no. 2, Art. 20, 28. MR 2738227, DOI 10.1145/1731022.1731030
R. Luce and B. I. Wohlmuth, A local a posteriori error estimator based on equilibrated fluxes, SIAM J. Numer. Anal. 42 (2004), no. 4, 1394–1414. MR 2114283, DOI 10.1137/S0036142903433790
Luisa Donatella Marini, An inexpensive method for the evaluation of the solution of the lowest order Raviart-Thomas mixed method, SIAM J. Numer. Anal. 22 (1985), no. 3, 493–496. MR 787572, DOI 10.1137/0722029
W. Prager and J. L. Synge, Approximations in elasticity based on the concept of function space, Quart. Appl. Math. 5 (1947), 241–269. MR 25902, DOI 10.1090/S0033-569X-1947-25902-8
P.-A. Raviart and J. M. Thomas, A mixed finite element method for 2nd order elliptic problems, Mathematical aspects of finite element methods (Proc. Conf., Consiglio Naz. delle Ricerche (C.N.R.), Rome, 1975) Lecture Notes in Math., Vol. 606, Springer, Berlin, 1977, pp. 292–315. MR 0483555
Sergey Repin, A posteriori estimates for partial differential equations, Radon Series on Computational and Applied Mathematics, vol. 4, Walter de Gruyter GmbH & Co. KG, Berlin, 2008. MR 2458008, DOI 10.1515/9783110203042
S. I. Repin, A posteriori error estimates for approximate solutions to variational problems with strongly convex functionals, J. Math. Sci. (New York) 97 (1999), no. 4, 4311–4328. Problems of mathematical physics and function theory. MR 1788233, DOI 10.1007/BF02365047
Sergey I. Repin and Leonidas S. Xanthis, A posteriori error estimation for nonlinear variational problems, C. R. Acad. Sci. Paris Sér. I Math. 324 (1997), no. 10, 1169–1174 (English, with English and French summaries). MR 1451942, DOI 10.1016/S0764-4442(97)87906-2
Sergey I. Repin, A posteriori error estimation for variational problems with uniformly convex functionals, Math. Comp. 69 (2000), no. 230, 481–500. MR 1681096, DOI 10.1090/S0025-5718-99-01190-4
Iain Smears and Martin Vohralík, Simple and robust equilibrated flux a posteriori estimates for singularly perturbed reaction-diffusion problems, ESAIM Math. Model. Numer. Anal. 54 (2020), no. 6, 1951–1973. MR 4160328, DOI 10.1051/m2an/2020034
Rob Stevenson, Optimality of a standard adaptive finite element method, Found. Comput. Math. 7 (2007), no. 2, 245–269. MR 2324418, DOI 10.1007/s10208-005-0183-0
Andreas Veeser, Convergent adaptive finite elements for the nonlinear Laplacian, Numer. Math. 92 (2002), no. 4, 743–770. MR 1935808, DOI 10.1007/s002110100377
Eberhard Zeidler, Nonlinear functional analysis and its applications. II/A, Springer-Verlag, New York, 1990. Linear monotone operators; Translated from the German by the author and Leo F. Boron. MR 1033497, DOI 10.1007/978-1-4612-0985-0