Greedy bisection generates optimally adapted triangulations
Open Access
- 28 September 2011
- journal article
- Published by American Mathematical Society (AMS) in Mathematics of Computation
- Vol. 81 (278) , 811-837
Abstract
We study the properties of a simple greedy algorithm for the generation of data-adapted anisotropic triangulations. Given a function f f , the algorithm produces nested triangulations T N \mathcal {T}_N and corresponding piecewise polynomial approximations f N f_N of f f . The refinement procedure picks the triangle which maximizes the local L p L^p approximation error, and bisects it in a direction which is chosen so to minimize this error at the next step. We study the approximation error in the L p L^p norm when the algorithm is applied to C 2 C^2 functions with piecewise linear approximations. We prove that as the algorithm progresses, the triangles tend to adopt an optimal aspect ratio which is dictated by the local hessian of f f . For convex functions, we also prove that the adaptive triangulations satisfy the convergence bound ‖ f − f N ‖ L p ≤ C N − 1 ‖ det ( d 2 f ) ‖ L τ \|f-f_N\|_{L^p} \leq CN^{-1}\|\sqrt {\det (d^2f)}\|_{L^\tau } with 1 τ := 1 p + 1 \frac 1 \tau :=\frac 1 p + 1 , which is known to be asymptotically optimal among all possible triangulations.Keywords
All Related Versions
This publication has 3 references indexed in Scilit:
- Optimal anisotropic meshes for minimizing interpolation errors in 𝐿^{𝑝}-normMathematics of Computation, 2006
- On the Error of Linear Interpolation and the Orientation, Aspect Ratio, and Internal Angles of a TriangleSIAM Journal on Numerical Analysis, 2005
- Nonlinear approximationActa Numerica, 1998