4.3 CONVERGENCE AND ERROR ANALYSIS 111
where I mnJ is the length of edge {m, n}, and h, h' are to be counted
algebraically, in the direction of the outward normal (thus, h < 0 if the
circumcenter C is outside T, as on Fig. 4.10, right part). This way, in the
case where ~t is uniform,
M m n =--~L
(h + h')/Imnl, negative indeed if
the circle condition is satisfied.
This quantity happens to be the flux of ~t grad Kn out of the Voronoi
cell of node m (Exercise 4.12: Prove this, under some precise assumption).
This coincidence is explained in inset: Although
the Voronoi cell and the barycentric box don't
coincide, the flux through their boundaries is the
same, because ~t VK n is divergence-free in the
region in between. But beware: Not only does
this argument break down when there is an obtuse
angle (cf. Exer. 4.12), but it doesn't extend to
dimension 3, where circumcenter and gravity
center of a face do not coincide.
Still, there is some seduction in a formula
m
such as (5), and it
has
a three-dimensional analogue. Look again at Fig.
4.9, middle. The formulas
,.-,_., ,.-,_., ,.-,_.,
Mmn = - [~
F
(area(F) ~(F)]/ I mnl, Mnn = - ~m~ N Mmn'
where F is an ad-hoc index for the small triangles of the dual cell
{m, n}", do provide negative exchange coefficients between n and m,
and hence a matrix with Stieltjes principal submatrices. This is a quite
interesting discretization method, but not the finite element one, and
M~M.
Exercise 4.13. Interpret this "finite volume" method in terms of fluxes
through Voronoi cells.
4.3 CONVERGENCE AND ERROR ANALYSIS
We now consider a family M of tetrahedral meshes of a bounded spatial
domain D. Does q0 m converge toward % in the sense that IIq0- q01I,
tends to zero, when rn... when
m what,
exactly? The difficulty is
mathematical, not semantic: We need some structure 1° on the set M to
validly talk about convergence and limit.
1°The right concept is that
of filter
[Ca]. But it would be pure folly to smuggle that into
an elementary course.
112 CHAPTER 4 The Approximate Scalar Potential: Properties and Shortcomings
The first idea that comes to mind in this respect is to gauge the
"coarseness" of m, as follows. Let us denote by
~n(m), or
simply
~/n'
the
maximum distance between x n and a point of its cluster D n. Call
grain
of the mesh, denoted 7(m) or simply 1, the least upper bound of the 7n s,
which is also the maximum distance between two points which belong to
the same tetrahedron T, or maximum
diameter
of the T's.
Now, the statement to prove would seem to be, in the time-honored
¢-8 tradition of calculus, "Given ¢> 0, there exists 8 > 0 such that, if
7(m) < 8, then IIq0 m - q011, < ¢." Unfortunately, this is plainly
false.
There are
straight counter-examples of meshes of arbitrary small grain for which
the energy of the computed field stays above the energy minimum by a
finite amount: Obtuse angles, larger and larger, do the trick [BA].
What we may expect, however, and which turns out to be true, is the
validity of the above statement if the family of meshes is
restricted
by
some qualifying conditions. "Acuteness", for instance, defined as the
absence of obtuse dihedral angles between any two adjacent faces, happens
to work: The statement "Given ¢ > 0, there exists 8 > 0 such that,
if m is
acute,
and if 7(m) < 8, then IIq0 m - q011~ < ¢" is true (we'll prove it).
Such
convergence
results are essential, because it would make no sense
to use the Galerkin method in their absence. But in practice, they are not
enough: We should like to know which kind of mesh to build to obtain a
prescribed accuracy. Knowing how the above 8 depends on ¢ would
be ideal: Given ¢, make a mesh the grain of which is lower than 8(¢).
No such general results are known, however, and we shall have to be
content with
asymptotic estimates
of the following kind:
(6) IIq0- q011, < C T(m) ~,
where (z is a known positive exponent and C a constant 11 which
depends on the true solution q), but not on the mesh. Again, C cannot
be known in advance in general, but (6) tells how
fast
the error will
decrease when the grain tends to 0, and this is quite useful. One usually
concentrates on the exponent (z, which depends on the shape functions.
Typically, (z= 1 for the P1 elements.
We shall first present the general method by which estimates like (6)
can be obtained, then address the question of which restrictions to force
on M in order to make them valid.
11From now on, all C's in error estimates will be constants of this kind, not necessarily
the same at different places, which may depend on q0 (via its derivatives of order 2 and
higher, as we shall see), but not on the mesh.
4.3 CONVERGENCE AND ERROR ANALYSIS 113
4.3.1 Interpolation error and approximation error
Let's develop an idea that was only suggested in Section 2.3.
First, a definition: Given a family M of
meshes, an
interpolation procedure
is a similarly
indexed family of linear mappings
r m • U --4 ~m' where U is
dense
in ~*. Let's give
an example immediately: U is made of all
continuous functions over D that vanish on
sh0, and its m-interpolate is
rmU
= Zn ~ NU(Xn) )n.
D
In other words, u is sampled at nodes, and linearly interpolated in
between. This explains why u cannot coincide with ~* (the complete
space), which contains non-continuous functions, for which nodal values
may not make sense. In fact, for technical reasons that soon will be
obvious, we further restrict u to piecewise 2-smooth functions that
vanish on sh0 . The energy distance Ilu - Gull,
=
[I D ~ I grad(u
-
rmU) [2] 1/2
between a function and its interpolate is called the
interpolation error.
Next, let's suppose we know something of the same form as (6) about
the interpolation error,
(7) llu - rmUll . < C(u) $(m) ~.
Then, two things may happen. If the true solution q0 is a member of the
class u, the remark of Section 3.3 (cf. Fig. 3.4) about the approximation
error llq~ m - q011, being lower 12 than the interpolation error llr q0- q011,
immediately yields (6), with C = C(q~). So we may conclude that for
meshes of the family for which (7) holds, r q~ converges in energy
toward q0 when the grain tends to 0. Moreover, the speed of the
convergence is what the interpolation procedure provides.
This situation does not present itself all the time, however, because
the solution may not be smooth enough to belong to u (cf. the example
of Exer. 3.6). But the density of u still allows us to conclude: Given ¢,
there exists some u ~ u such that Ilu - q011, < ~ / 2, and since
IIq~ m - q~ll, <_ Ilru - q~ll, _< IlrmU - ull, + Ilu - q~ll,,
Ilrmu - ull, will be smaller that the still unspent half-epsilon for ~(m)
12Note that rmU ~ ~I if u ~ ~I with the present interpolation procedure, if one turns a
blind eye to possible variational crimes at the boundary. This is important in asserting that
IIq~m - q011~ _< IIr,,q~ - ¢p II,.
114 CHAPTER 4 The Approximate Scalar Potential: Properties and Shortcomings
small enough, hence the convergence. The convergence
speed,
however,
is no longer under control. This is not a practical difficulty, because
singularities of q~ are usually located at predictable places (corners,
spikes), and special precautions about the mesh (pre-emptive refinement,
or special shape functions) can be taken there.
4.3.2 Taming the interpolation error: Zlamal's condition
We may therefore concentrate on the interpolation error. By the very
definition of hat functions, one has
(8)
~n e N ~n(x) (Xn-- X) -- 0 V X E D,
which makes sense as a weighted sum of
vectors
X n-
X.
Let u be an element of U. We'll make use of its second-order
Taylor expansion about x, in integral form, as follows:
1 Au(X ' y)(y x). (y-x)
(9) u(y) = u(x) + Vu(x). (y- x) + -~ -
where, denoting
02U
the matrix of second derivatives of u,
Au(X, y)
= ~01
(1
- t 2) ~2u(x +
t(y - x)) dt,
a symmetric matrix that smoothly depends on x and y. Note that
Vu(x) is treated as a vector in (9), and that A u acts on vector y- x.
Remark
4.3. The validity of formula (9) is restricted to pairs of points
{x, y} which are linked by a segment entirely contained in D. Not to be
bothered by this, we assume u has a smooth extension to the convex
hull of D. Anyway, only values of Au(X, y) for points x and y close to
each other will matter. 0
It is intuitive that the distance between u and its interpolate rmU
should depend on the grain in some way. Our purpose is to show that if
the mesh is "well behaved", in a precise sense to be discovered, the
quadratic semi-norm, which differs only in an inessential way from the
energy one,
Ilu - rmUll
= [~D ] V(U -- rmu) I 2] 1/2,
is bounded by ~(m), up to a multiplicative constant that depends on u
(via its derivatives of order 2).
By Taylor's formula (9), we have, for all node locations x n,
4.3 CONVERGENCE AND ERROR ANALYSIS 115
1 au(X , Xn)(Xn _ x). (X n - x).
U(Xn) -- U(X) n t- VU(X) . (X n -- X) q- -~
Multiplying this by Kn, then using (8) and (9), we see that
Finn(x) = u(x)
+ £n~ N ~n(x) O~n(X)*
where
(10)
CZn(X) = -~1 Au (x,
x)(x n - x) . (x n - x).
Therefore,
(11) V(r u- u) =
£neN~ n Van+ Zne Nl~n V~ n.
On D, after (10), I VO~nl is bounded by Yn' up to a multiplicative
constant. Fields )n gOWn are thus uniformly bounded by C y on D, and
the first term on the right in (11) is on the order of y(m). The one term we
may worry about is therefore
1
ne NO~n V~ n •
n
R(T)
FIGURE
4.11. The norm Ig2~nl is 1/an, where a n is the length of the altitude
drawn from node n to the opposite face. Right (in 2D for clarity, but this
generalizes without problem), the ratio an/Y is always larger than r(T)/R(T),
hence "Zlamal's condition" [Z1]: R(T)/r(T) < C, for all triangles and all meshes
in the family. It amounts to the same as requiring that the smallest angle (or in
3D, the smallest dihedral angle) be bounded from below.
And worry we should, for
V~ n can
become very large: Its amplitude
within tetrahedron T is the inverse of the distance a n from node n to
the opposite face in T (Fig. 4.11), so there is no necessary link between
I VKnl and Yn- But it's not difficult to establish such a link if the mesh
behaves. Remarking that, for x in T (refer to Fig. 4.11, right, for the
notation),
IXn--Xl Iv2~n(x) I < Yn/an< R(T)/r(T),
we are led to introduce the dimensionless number
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.