Welcome to MathOverflow

Question

14

6

There are many known results proving convergence of finite element method for elliptic problems under certain assumptions on underlying mesh [e.g., Braess,2007]. Which of these common assumptions are indeed necessary? Can anyone recommend any exact reference to an example of a sequence of triangulations on which the finite element solutions do NOT converge to the real solution?

Let us give a model problem which is of particular interest. Let $\Omega$ be a convex polygon in the plane and $f:R^2\to R$ be a $C^2$-function. Let $u:\Omega\to R$ be a $C^2$-function such that $\Delta u=f$ inside $\Omega$, $u=0$ in $\partial\Omega$. Let $T_h$ be a sequence of triangulations of $\Omega$ such that maximal edge length of $T_h$ approaches zero. Let $u_h:\Omega\to R$ be a continuous piecewise-linear function on $T_h$ such that $u_h=0$ in $\partial\Omega$ and for any continuous piecewise-linear function $v:\Omega\to R$ on $T_h$ we have $\int_\Omega \nabla u_h\nabla v dA=\int_\Omega fv dA$. Suppose that there is a constant $\mathrm{const}>0$ (not depending on $h$) such that:

(1) the ratio of any two edges of $T_h$ is greater than $\mathrm{const}$;

(2) the angles of any triangle of $T_h$ is greater than $\mathrm{const}$.

Then $\max_{\Omega}|u_h-u|\to 0$ as $h\to 0$. [Ciarlet, Theorem 3.3.7]

Which of the assumptions (1) and (2) cannot be dropped here? What are counterexamples? I am mostly interested in uniform ($L_\infty$) convergence of values at the vertices but I would be also grateful for counterexamples for other norms.

[Braess] D. Braess, Finite elements. Theory, fast solvers, and applications in elasticity theory, transl. by L.L. Schumaker, Cambridge Univ. Press, 2007.

[Ciarlet] P.G. Ciarlet, The finite element method for elliptic problems, North-Holland, Amsterdam, 1978, 530 p.

edited Sep 13 2011 at 13:47

asked Sep 12 2011 at 20:01

mikhail skopenkov
966●2●13

2

I should guess that (1) can be dropped, because it is certainly not satisfied in methods using refinement in particular zones of interest. But (2) seems essential. I aggree with you that a specific counterexample should be useful. Perhaps it exists already somewhere. – Denis Serre Sep 12 2011 at 20:20

Nilima Nigam · Accepted Answer · 2011-09-13 02:18:03Z UTC

11

The maximum and minimum angle conditions for meshes are needed to prove various bounds on the error of interpolation. In other words, the solution of the PDE is a secondary concern; what goes wrong is that one cannot control the interpolation error.

Of the two, the minimum angle condition is less restrictive. What one may observe is that deteriorating conditioning of the linear system to solve for the unknown coefficients of the approximant as the minimum angle condition is violated.

There's a famous paper by Babuska and Aziz in a 1976 SIAM J. Numerical Analysis v. 13, no. 2, 'On the angle condition in the finite element method'. This also has a nice counter example showing why the interpolation error cannot be bounded unless the maximum angle is bounded away from $\pi$.

Please see http://www.bcamath.org/documentos_public/archivos/publicaciones/BraHanKorKri-SeMA.pdf for a survey and discussion of these ideas.

answered Sep 13 2011 at 2:18

Nilima Nigam
976●6●14

@Nilima Nigam: Thank you very much for your answer. Now I see that condition (2) above is even more important for estimation of interpolation error than for convergence. In the survey suggested by you the authors assert that condition (2) can be relaxed to the following one: (2') the angles of any triangle of $T_h$ are less than $\pi-\mathrm{const}$. But still no examples of nonconvergence are given, if (2') does not hold... – mikhail skopenkov Sep 13 2011 at 11:19

Dear Mikhail, the paper by Babuska and Aziz demonstrates a mesh in which the maximum angle condition is violated, and therefore the interpolation error estimate for piecewise linear finite elements cannot hold. – Nilima Nigam Sep 14 2011 at 0:13

But this does NOT mean nonconvergence, does it? – mikhail skopenkov Sep 15 2011 at 20:29

1

Mikhail, this means the accuracy of approximations can become quite bad. How bad? Depends on the function being approximated. J.Shewchuk has a nice account of this. In particular, he compiles a list of the errors (both of the interpolant, and of the errors in the derivative). Also, the dependence on the regularity is clearly seen - the interpolation error is show to be bounded below in case the meshes are of poor quality. This would imply non-convergence of the interpolant. cs.berkeley.edu/~jrs/papers/elem.pdf – Nilima Nigam Sep 17 2011 at 2:45

1

You are correct- I was thinking about the $H^1$ norm, in which the counterexample above fails to converge. If you are interested only in the failure of convergence in the $L^\infty$ norm, this may be hard to show under the hypotheses you have ($u\in C^2$, $\Omega$ convex). – Nilima Nigam Sep 20 2011 at 2:30

show 1 more comment

Joseph O'Rourke · Answer 2 · 2011-09-13 01:27:13Z UTC

7

This may not be what you seek, but in the 1996 paper, "Anisotropic refinement algorithms for finite elements" by Goodman, Samuelsson, and Szepessy (.ps link), they show an example of a function $u(x,y)=\frac{1}{2} y^2$, independent of $x$, which solves $\Delta u = 1$ on $\mathbb{R}^2$. But with the triangulation shown below, with $\delta \ll \epsilon$, as $\delta \rightarrow 0$, the finite element equation approximates $\Delta u = 0$ instead of $\Delta u = 1$.
Nonconvergence

edited Sep 13 2011 at 1:27

answered Sep 13 2011 at 0:36

Joseph O'Rourke
43.2k●1●49●214

2

@Joseph O'Rourke: Thank you very much! Of course this Schwarz lantern pattern is what one should first look at. I tried to study this particular example in detail but cannot follow the argument of these authors. Just the piecewise-linear extension $u_h$ of the initial function $u=y^2/2$ restricted to the vertices seems to be the finite element solution of the equation $\Delta u=1$. Thus we have CONVERGENCE here by trivial reasons: each $u_h$ simply equals to $u$ at the vertices. – mikhail skopenkov Sep 13 2011 at 13:44

Cool, I never heard of the "Schwartz lantern pattern"---an apt description! Sorry I cannot clarify their argument, which depends on "the standard Galerkin method" (p.14), about which I know little. – Joseph O'Rourke Sep 13 2011 at 14:30

Convergence of finite element method: counterexamples

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.