On the stability of the $L_2$ projection in fractional Sobolev spaces

Summary.   In this paper we prove the stability of the projection onto the finite element trial space of piecewise polynomial, in particular, piecewise linear basis functions in for . We formulate explicit and computable local mesh conditions to be satisfied which depend on the Sobolev index s. In conclusion we prove a stability condition needed in the numerical analysis of mixed and hybrid boundary element methods as well as in the construction of efficient preconditioners in adaptive boundary and finite element methods. Received October 14, 1999 / Revised version received March 24, 2000 / Published online October 16, 2000     

A posteriori error estimate and h-adaptive algorithm on surfaces for Symm's integral equation

Summary. A residual-based a posteriori error estimate for boundary integral equations on surfaces is derived in this paper. A localisation argument involves a Lipschitz partition of unity such as nodal basis functions known from finite element methods. The abstract estimate does not use any property of the discrete solution, but simplifies for the Galerkin discretisation of Symm's integral equation if piecewise constants belong to the test space. The estimate suggests an isotropic adaptive algorithm for automatic mesh-refinement. An alternative motivation from a two-level error estimate is possible but then requires a saturation assumption. The efficiency of an anisotropic version is discussed and supported by numerical experiments. Received November 29, 1999 / Revised version received August 10, 2000 / Published online May 30, 2001     

Small data oscillation implies the saturation assumption

Summary. The saturation assumption asserts that the best approximation error in with piecewise quadratic finite elements is strictly smaller than that of piecewise linear finite elements. We establish a link between this assumption and the oscillation of , and prove that small oscillation relative to the best error with piecewise linears implies the saturation assumption. We also show that this condition is necessary, and asymptotically valid provided . Received November 17, 2000 / Published online July 25, 2001     

Multilevel Schwarz methods for elliptic problems with discontinuous coefficients in three dimensions

Summary. Multilevel Schwarz methods are developed for a conforming finite element approximation of second order elliptic problems. We focus on problems in three dimensions with possibly large jumps in the coefficients across the interface separating the subregions. We establish a condition number estimate for the iterative operator, which is independent of the coefficients, and grows at most as the square of the number of levels. We also characterize a class of distributions of the coefficients, called quasi-monotone, for which the weighted -projection is stable and for which we can use the standard piecewise linear functions as a coarse space. In this case, we obtain optimal methods, i.e. bounds which are independent of the number of levels and subregions. We also design and analyze multilevel methods with new coarse spaces given by simple explicit formulas. We consider nonuniform meshes and conclude by an analysis of multilevel iterative substructuring methods. Received April 6, 1994 / Revised version received December 7, 1994     

On a hybrid boundary element method

Summary. In this paper we study a symmetric boundary element method based on a hybrid discretization of the Steklov–Poincaré operator well suited for a symmetric coupling of finite and boundary elements. The representation used involves only single and double layer potentials and does not require the discretization of the hypersingular integral operator as in the symmetric formulation. The stability of the hybrid Galerkin discretization is based on a BBL–like stability condition for the trial spaces. Numerical examples confirm the theoretical results. Received December 15, 1997 / Revised version received December 21, 1998/ Published online November 17, 1999     

Composite finite elements for the approximation of PDEs on domains with complicated micro-structures

Summary. Usually, the minimal dimension of a finite element space is closely related to the geometry of the physical object of interest. This means that sometimes the resolution of small micro-structures in the domain requires an inadequately fine finite element grid from the viewpoint of the desired accuracy. This fact limits also the application of multi-grid methods to practical situations because the condition that the coarsest grid should resolve the physical object often leads to a huge number of unknowns on the coarsest level. We present here a strategy for coarsening finite element spaces independently of the shape of the object. This technique can be used to resolve complicated domains with only few degrees of freedom and to apply multi-grid methods efficiently to PDEs on domains with complex boundary. In this paper we will prove the approximation property of these generalized FE spaces. Received June 9, 1995 / Revised version received February 5, 1996     

Analysis of a Stokes interface problem

We consider a stationary Stokes problem with a piecewise constant viscosity coefficient. For the variational formulation of this problem we prove a well-posedness result in which the constants are uniform with respect to the jump in the viscosity coefficient. We apply a standard discretization with a pair of LBB stable finite element spaces. The main result of the paper is an infsup result for the discrete problem that is uniform with respect to the jump in the viscosity coefficient. From this we derive a robust estimate for the discretization error. We prove that the mass matrix with respect to some suitable scalar product yields a robust preconditioner for the Schur complement. Results of numerical experiments are presented that illustrate this robustness property. This author was supported by the German Research Foundation through the guest program of SFB 540     

Stability of a Cartesian grid projection method for zero Froude number shallow water flows

In this paper a Godunov-type projection method for computing approximate solutions of the zero Froude number (incompressible) shallow water equations is presented. It is second-order accurate and locally conserves height (mass) and momentum. To enforce the underlying divergence constraint on the velocity field, the predicted numerical fluxes, computed with a standard second order method for hyperbolic conservation laws and applied to an auxiliary system, are corrected in two steps. First, a MAC-type projection adjusts the advective velocity divergence. In a second projection step, additional momentum flux corrections are computed to obtain new time level cell-centered velocities, which satisfy another discrete version of the divergence constraint. The scheme features an exact and stable second projection. It is obtained by a Petrov–Galerkin finite element ansatz with piecewise bilinear trial functions for the unknown height and piecewise constant test functions. The key innovation compared to existing finite volume projection methods is a correction of the in-cell slopes of the momentum by the second projection. The stability of the projection is proved using a generalized theory for mixed finite elements. In order to do so, the validity of three different inf-sup conditions has to be shown. The results of preliminary numerical test cases demonstrate the method’s applicability. On fixed grids the accuracy is improved by a factor four compared to a previous version of the scheme.     

An unusual stabilized finite element method for a generalized Stokes problem

Summary. An unusual stabilized finite element is presented and analyzed herein for a generalized Stokes problem with a dominating zeroth order term. The method consists in subtracting a mesh dependent term from the formulation without compromising consistency. The design of this mesh dependent term, as well as the stabilization parameter involved, are suggested by bubble condensation. Stability is proven for any combination of velocity and pressure spaces, under the hypotheses of continuity for the pressure space. Optimal order error estimates are derived for the velocity and the pressure, using the standard norms for these unknowns. Numerical experiments confirming these theoretical results, and comparisons with previous methods are presented. Received April 26, 2001 / Revised version received July 30, 2001 / Published online October 17, 2001 Correspondence to: Gabriel R. Barrenechea     

A finite volume method based on the Crouzeix–Raviart element for elliptic PDE's in two dimensions

We introduce and analyse a finite volume method for the discretization of elliptic boundary value problems in . The method is based on nonuniform triangulations with piecewise linear nonconforming spaces. We prove optimal order error estimates in the –norm and a mesh dependent –norm. Received September 10, 1997 / Revised version received March 18, 1998     

Multilevel preconditioning

Summary This paper is concerned with multilevel techniques for preconditioning linear systems arising from Galerkin methods for elliptic boundary value problems. A general estimate is derived which is based on the characterization of Besov spaces in terms of weighted sequence norms related to corresponding multilevel expansions. The result brings out clearly how the various ingredients of a typical multilevel setting affect the growth rate of the condition numbers. In particular, our analysis indicates how to realize even uniformly bounded condition numbers. For example, the general results are used to show that the Bramble-Pasciak-Xu preconditioner for piecewise linear finite elements gives rise to uniformly bounded condition numbers even when the refinements of the underlying triangulations are highly nonuniform. Furthermore, they are applied to a general multivariate setting of refinable shift-invariant spaces, in particular, covering those induced by various types of wavelets.The work of this author was partially supported by the Air Force Office of Scientific Research (Contract No. 89/0455) and by the Office of Naval Research (Contract No. N00014/90/1343) during her stay at the Department of Mathematics, University of South Carolina, Columbia, SC 29208, USA.     

The approximation theory for the p-version finite element method and application to non-linear elliptic PDEs

Approximation theoretic results are obtained for approximation using continuous piecewise polynomials of degree p on meshes of triangular and quadrilateral elements. Estimates for the rate of convergence in Sobolev spaces , are given. The results are applied to estimate the rate of convergence when the p-version finite element method is used to approximate the -Laplacian. It is shown that the rate of convergence of the p-version is always at least that of the h-version (measured in terms of number of degrees of freedom used). If the solution is very smooth then the p-version attains an exponential rate of convergence. If the solution has certain types of singularity, the rate of convergence of the p-version is twice that of the h-version. The analysis generalises the work of Babuska and others to the case . In addition, the approximation theoretic results find immediate application for some types of spectral and spectral element methods. Received August 2, 1995 / Revised version received January 26, 1998     

Mixed finite elements for elasticity

Summary. There have been many efforts, dating back four decades, to develop stable mixed finite elements for the stress-displacement formulation of the plane elasticity system. This requires the development of a compatible pair of finite element spaces, one to discretize the space of symmetric tensors in which the stress field is sought, and one to discretize the space of vector fields in which the displacement is sought. Although there are number of well-known mixed finite element pairs known for the analogous problem involving vector fields and scalar fields, the symmetry of the stress field is a substantial additional difficulty, and the elements presented here are the first ones using polynomial shape functions which are known to be stable. We present a family of such pairs of finite element spaces, one for each polynomial degree, beginning with degree two for the stress and degree one for the displacement, and show stability and optimal order approximation. We also analyze some obstructions to the construction of such finite element spaces, which account for the paucity of elements available. Received January 10, 2001 / Published online November 15, 2001     

Schwarz methods for inequalities with contraction operators

We prove the convergence of some multiplicative and additive Schwarz methods for inequalities which contain contraction operators. The problem is stated in a reflexive Banach space and it generalizes the well-known fixed-point problem in the Hilbert spaces. Error estimation theorems are given for three multiplicative algorithms and two additive algorithms. We show that these algorithms are in fact Schwarz methods if the subspaces are associated with a decomposition of the domain. Also, for the one- and two-level methods in the finite element spaces, we write the convergence rates as functions of the overlapping and mesh parameters. They are similar with the convergence rates of these methods for linear problems. Besides the direct use of the five algorithms for the inequalities with contraction operators, we can use the above results to obtain the convergence rate of the Schwarz method for other types of inequalities or nonlinear equations. In this way, we prove the convergence and estimate the error of the one- and two-level Schwarz methods for some inequalities in Hilbert spaces which are not of the variational type, and also, for the Navier–Stokes problem. Finally, we give conditions of existence and uniqueness of the solution for all problems we consider. We point out that these conditions and the convergence conditions of the proposed algorithms are of the same type.     

An augmented mixed finite element method for 3D linear elasticity problems

In this paper we introduce and analyze a new augmented mixed finite element method for linear elasticity problems in 3D. Our approach is an extension of a technique developed recently for plane elasticity, which is based on the introduction of consistent terms of Galerkin least-squares type. We consider non-homogeneous and homogeneous Dirichlet boundary conditions and prove that the resulting augmented variational formulations lead to strongly coercive bilinear forms. In this way, the associated Galerkin schemes become well posed for arbitrary choices of the corresponding finite element subspaces. In particular, Raviart-Thomas spaces of order 0 for the stress tensor, continuous piecewise linear elements for the displacement, and piecewise constants for the rotation can be utilized. Moreover, we show that in this case the number of unknowns behaves approximately as 9.5 times the number of elements (tetrahedrons) of the triangulation, which is cheaper, by a factor of 3, than the classical PEERS in 3D. Several numerical results illustrating the good performance of the augmented schemes are provided.     

Convergent adaptive finite elements for the nonlinear Laplacian

Summary. The numerical solution of the homogeneous Dirichlet problem for the p-Laplacian, , is considered. We propose an adaptive algorithm with continuous piecewise affine finite elements and prove that the approximate solutions converge to the exact one. While the algorithm is a rather straight-forward generalization of those for the linear case p=2, the proof of its convergence is different. In particular, it does not rely on a strict error reduction. Received December 29, 2000 / Revised version received August 30, 2001 / Published online December 18, 2001 RID="*" ID="*" Current address: Dipartimento di Matematica, Università degli Studi di Milano, Via C. Saldini 50, 20133 Milano, Italy; e-mail: veeser@mat.unimi.it     

On the quadratic finite element approximation to the obstacle problem

Summary. In this paper, we obtain the error bound for any , for the piecewise quadratic finite element approximation to the obstacle problem, without the hypothesis that the free boundary has finite length (see [3]). Received October 31, 2000 / Revised version received July 23, 2001 / Published online October 17, 2001 The project was supported by the National Natural Science Foundation of China     

The hierarchical basis multigrid method

Summary We derive and analyze the hierarchical basis-multigrid method for solving discretizations of self-adjoint, elliptic boundary value problems using piecewise linear triangular finite elements. The method is analyzed as a block symmetric Gauß-Seidel iteration with inner iterations, but it is strongly related to 2-level methods, to the standard multigridV-cycle, and to earlier Jacobi-like hierarchical basis methods. The method is very robust, and has a nearly optimal convergence rate and work estimate. It is especially well suited to difficult problems with rough solutions, discretized using highly nonuniform, adaptively refined meshes.     

Crouzeix-Raviart type finite elements on anisotropic meshes

Summary. The paper deals with a non-conforming finite element method on a class of anisotropic meshes. The Crouzeix-Raviart element is used on triangles and tetrahedra. For rectangles and prismatic (pentahedral) elements a novel set of trial functions is proposed. Anisotropic local interpolation error estimates are derived for all these types of element and for functions from classical and weighted Sobolev spaces. The consistency error is estimated for a general differential equation under weak regularity assumptions. As a particular application, an example is investigated where anisotropic finite element meshes are appropriate, namely the Poisson problem in domains with edges. A numerical test is described. Received May 19, 1999 / Revised version received February 2, 2000 / Published online February 5, 2001     

An algorithm for coarsening unstructured meshes

Summary. We develop and analyze a procedure for creating a hierarchical basis of continuous piecewise linear polynomials on an arbitrary, unstructured, nonuniform triangular mesh. Using these hierarchical basis functions, we are able to define and analyze corresponding iterative methods for solving the linear systems arising from finite element discretizations of elliptic partial differential equations. We show that such iterative methods perform as well as those developed for the usual case of structured, locally refined meshes. In particular, we show that the generalized condition numbers for such iterative methods are of order , where is the number of hierarchical basis levels. Received December 5, 1994