Preconditioning nonconforming finite element methods for treating Dirichlet boundary conditions. I

Summary This work deals with theL ² condition numbers and the distribution of theL ² singular values of the preconditioned operators {B _h ^–1 A_h}_{0, whereA h andB h are finite element discretizations of second order elliptic operators,A andB respectively. For conforming finite elements, it was shown in the work of Goldstein, Manteuffel and Parter that if the leading part ofB is a scalar multiple (1/) of the leading part ofA, then the singular values ofB h ^–1 A h cluster and fill-in the interval [ min, max], where 0< min max are the minimum and maximum of the factor . As a generalization of these results, the current work includes nonconforming finite element methods which deal with Dirichlet boundary conditions. It will be shown that, in this more general setting, theL ² condition numbers of {B h ^–1 A h } are uniformly bounded. Moreover, the singular values also cluster and fill-in the same interval. In particular, if the leading part ofB is the same as the leading part ofA, then the singular values cluster about the point {1}. Two specific methods are given as applications of this theory. They are the penalty method of Babuka and the method of nearly zero boundary conditions of Nitsche.This research was supported by the National Science Foundation under grant number DMS-8913091.}     

Preconditioning nonconforming finite element methods for treating Dirichlet boundary conditions. II

Summary This work deals with theH ¹ condition numbers and the distribution of theB _h singular values of the preconditioned operators {B _h ^–1 A _h }_{0, whereA h andB h are finite element discretizations of second order elliptic operators,A andB respectively.B is also assumed to be self-adjoint and positive definite. For conforming finite elements, Parter and Wong have shown that the singular values cluster in a positive finite interval. Goldstein also has derived results on the spectral distribution ofB h ^–1 A h using a different approach. As a generalization of the results of Parter and Wong, the current work includes nonconforming finite element methods which deal with Dirichlet boundary conditions. It will be shown that, in this more general setting, the singular values also cluster in a positive finite interval. In particular, if the leading part ofB is the same as the leading part ofA, then the singular values cluster about the point {1}. Two specific methods are given as applications of this theory. They are the penalty method of Babuka and the method of nearly zero boundary conditions of Nitsche. Finally, it will be shown that the same results can be proven by an approach generalized from the work of Goldstein.This research was supported by the National Science Foundation under grant number DMS-8913091.}     

PreconditioningP 1 nonconforming finite elements: Condition numbers and singular value distributions

Summary This work deals with the condition numbers and the distribution of theB _h singular values of the preconditioned operators {B _h ^–1 A _h }_{0, whereA h andB h are discretizations of second order elliptic operatorsA andB usingP 1 nonconforming finite elements of Crouzeix and Raviart.B is also assumed to be self-adjoint and positive definite. For conforming finite elements, Parter and Wong have shown that the singular values cluster in a positive finite interval. These reults are being extended to the aforementioned nonconforming finite elements. It will be shown that, for quasiuniform grids, theB h singular values are bounded above and below by positive constants which are independent of the grid sizeh. Moreover, they also cluster in a smaller but usually estimable interval. Issues of implementation are also discussed.This research was supported by the National Science Foundation under grant number DMS-8913091}     

A capacitance matrix method for Dirichlet problem on polygon region

Summary An efficient algorithm for the solution of linear equations arising in a finite element method for the Dirichlet problem is given. The cost of the algorithm is proportional toN ²log₂ N (N=1/h) where the cost of solving the capacitance matrix equations isNlog₂ N on regular grids andN ^3/2log₂ N on irregular ones.     

A locking-free nonconforming triangular element for planar elasticity with pure traction boundary condition

A new nonconforming triangular element for the equations of planar linear elasticity with pure traction boundary conditions is considered. By virtue of construction of the element, the discrete version of Korn’s second inequality is directly proved to be valid. Convergence rate of the finite element methods is uniformly optimal with respect to λ. Error estimates in the energy norm and L²-norm are O(h²) and O(h³), respectively.     

A remark on theL ∞ bounds of the Ritz operator associated with a finite element approximation

Summary For the elliptic operatorA of second order, its finite element approximationA _h is considered by piecewise linear trial functions. AnL bound on the Ritz operator is shown by Stampacchia's method, which implies a discrete elliptic-Sobolev inequality forA _h.     

A basic norm equivalence for the theory of multilevel methods

Summary Subspace decompositions of finite element spaces based onL ₂-like orthogonal projections play an important role for the construction and analysis of multigrid like iterative methods. Recently several authors have proved the equivalence of the associated discrete norms with theH ¹-norm. The present paper gives an elementary, self-contained derivation of this result which is based on the use ofK-functionals known from the theory of interpolation spaces.     

Adaptive finite element for semi-linear convection–diffusion problems

In this article a strategy of adaptive finite element for semi-linear problems, based on minimizing a residual-type estimator, is reported. We get an a posteriori error estimate which is asymptotically exact when the mesh size h tends to zero. By considering a model problem, the quality of this estimator is checked. It is numerically shown that without constraint on the mesh size h, the efficiency of the a posteriori error estimate can fail dramatically. This phenomenon is analysed and an algorithm which equidistributes the local estimators under the constraint h ⩽ h _max is proposed. This algorithm allows to improve the computed solution for semi-linear convection–diffusion problems, and can be used for stabilizing the Lagrange finite element method for linear convection–diffusion problems. This revised version was published online in June 2006 with corrections to the Cover Date.     

Some equilibrium finite element methods for two-dimensional elasticity problems

Summary We consider some equilibrium finite element methods for two-dimensional elasticity problems. The stresses and the displacements are approximated by using piecewise linear functions. We establishL ₂-estimates of orderO(h ²) for both stresses and displacements.     

Modified Mini finite element for the Stokes problem in ℝ2 or ℝ3

We analyze a modified version of the Mini finite element (or the Mini* finite element) for the Stokes problem in ℝ² or ℝ³. The cross‐grid element of order one in ℝ³ is also analyzed. The stability is verified with the aid of the macroelement technique introduced by Stenberg. Each of these methods converges with first order in h as the Mini element does. Numerical tests are given for the Mini* element in comparison with the Mini element when Ω is a unit square on ℝ². This revised version was published online in June 2006 with corrections to the Cover Date.     

On the finite volume element method

Summary The finite volume element method (FVE) is a discretization technique for partial differential equations. It uses a volume integral formulation of the problem with a finite partitioning set of volumes to discretize the equations, then restricts the admissible functions to a finite element space to discretize the solution. this paper develops discretization error estimates for general selfadjoint elliptic boundary value problems with FVE based on triangulations with linear finite element spaces and a general type of control volume. We establishO(h) estimates of the error in a discreteH ¹ semi-norm. Under an additional assumption of local uniformity of the triangulation the estimate is improved toO(h ²). Results on the effects of numerical integration are also included.This research was sponsored in part by the Air Force Office of Scientific Research under grant number AFOSR-86-0126 and the National Science Foundation under grant number DMS-8704169. This work was performed while the author was at the University of Colorado at Denver     

Zur numerischen Lösung des ersten biharmonischen Randwertproblems

Summary The system of equations resulting from a mixed finite element approximation of the first biharmonic boundary value problem is solved by various preconditioned Uzawa-type iterative methods. The preconditioning matrices are based on simple finite element approximations of the Laplace operator and some factorizations of the corresponding matrices. The most efficient variants of these iterative methods require asymptoticallyO(h ^–0,5In ^–1) iterations andO(h ^–p–0,5In ^–1) arithmetic operations only, where denotes the relative accuracy andh is a mesh-size parameter such that the number of unknowns grows asO(h ^–p ),h0.

     

Acceleration of convergence for finite element solutions of the Poisson equation

Summary Letu _h be the finite element solution to–u=f with zero boundary conditions in a convex polyhedral domain . Fromu _h we calculate for eachz and ||1 an approximationu _h ^– (z) toD u(z) with |D u(z)–u _h ^– (z)|=O(h ^2k–2) wherek is the order of the finite elements. The same superconvergence order estimates are obtained also for the boundary flux. We need not work on a regular mesh but we have to compute averages ofu _h where the diameter of the domain of integration must not depend onh.     

Superconvergence analysis of approximate boundary-flux calculations

Summary Certain projection post-processing techniques have been proposed for computing the boundary flux for two-dimensional problems (e.g., see Carey, et al. [5]). In a series of numerical experiments on elliptic problems they observed that these post-processing formulas for approximate fluxes were almost (O(h ²)-accurate for linear triangular elements. In this paper we prove that the computed boundary flux isO(h ² ln 1/h)-accurate in the maximum norm for the partial method of [5]. If the solutionuH ³() then the boundary flux error isO(h ^3/2) in theL ²-norm.     

A two-grid method for finite volume element approximations of second-order nonlinear hyperbolic equations

The two-grid method is studied for solving a two-dimensional second-order nonlinear hyperbolic equation using finite volume element method. The method is based on two different finite element spaces defined on one coarse grid with grid size H and one fine grid with grid size h, respectively. The nonsymmetric and nonlinear iterations are only executed on the coarse grid and the fine grid solution can be obtained in a single symmetric and linear step. It is proved that the coarse grid can be much coarser than the fine grid. A prior error estimate in the H¹-norm is proved to be O(h+H³|lnH|) for the two-grid semidiscrete finite volume element method. With these proposed techniques, solving such a large class of second-order nonlinear hyperbolic equations will not be much more difficult than solving one single linearized equation. Finally, a numerical example is presented to validate the usefulness and efficiency of the method.     

A note onC o Galerkin methods for two-point boundary problems

Summary As is known [4]. theC ^o Galerkin solution of a two-point boundary problem using piecewise polynomial functions, hasO(h ^2k ) convergence at the knots, wherek is the degree of the finite element space. Also, it can be proved [5] that at specific interior points, the Gauss-Legendre points the gradient hasO(h ^k+1) convergence, instead ofO(h ^k ). In this note, it is proved that on any segment there arek–1 interior points where the Galerkin solution is ofO(h ^k+2), one order better than the global order of convergence. These points are the Lobatto points.     

Incomplete block-matrix factorization iterative methods for convection-diffusion problems

Standard Galerkin finite element methods or finite difference methods for singular perturbation problems lead to strongly unsymmetric matrices, which furthermore are in general notM-matrices. Accordingly, preconditioned iterative methods such as preconditioned (generalized) conjugate gradient methods, which have turned out to be very successful for symmetric and positive definite problems, can fail to converge or require an excessive number of iterations for singular perturbation problems.This is not so much due to the asymmetry, as it is to the fact that the spectrum can have both eigenvalues with positive and negative real parts, or eigenvalues with arbitrary small positive real parts and nonnegligible imaginary parts. This will be the case for a standard Galerkin method, unless the meshparameterh is chosen excessively small. There exist other discretization methods, however, for which the corresponding bilinear form is coercive, whence its finite element matrix has only eigenvalues with positive real parts; in fact, the real parts are positive uniformly in the singular perturbation parameter.In the present paper we examine the streamline diffusion finite element method in this respect. It is found that incomplete block-matrix factorization methods, both on classical form and on an inverse-free (vectorizable) form, coupled with a general least squares conjugate gradient method, can work exceptionally well on this type of problem. The number of iterations is sometimes significantly smaller than for the corresponding almost symmetric problem where the velocity field is close to zero or the singular perturbation parameter =1.The 2 ^nd author's research was sponsored by Control Data Corporation through its PACER fellowship program.The 3 ^rd author's research was supported by the Netherlands organization for scientific research (NWO).On leave from the Institute of Mathematics, Academy of Science, 1090 Sofia, P.O. Box 373, Bulgaria.     

Interpolation error estimates in W 1,p for degenerate Q 1 isoparametric elements

Optimal order error estimates in H ¹, for the Q ₁ isoparametric interpolation were obtained in Acosta and Durán (SIAM J Numer Anal37, 18–36, 1999) for a very general class of degenerate convex quadrilateral elements. In this work we show that the same conlusions are valid in W ^1,p for 1≤ p < 3 and we give a counterexample for the case p ≥ 3, showing that the result cannot be generalized for more regular functions. Despite this fact, we show that optimal order error estimates are valid for any p ≥ 1, keeping the interior angles of the element bounded away from 0 and π, independently of the aspect ratio. We also show that the restriction on the maximum angle is sharp for p ≥ 3.     

Inf-sup stable non-conforming finite elements of arbitrary order on triangles

We introduce a family of scalar non-conforming finite elements of arbitrary order k≥1 with respect to the H¹-norm on triangles. Their vector-valued version generates together with a discontinuous pressure approximation of order k−1 an inf-sup stable finite element pair of order k for the Stokes problem in the energy norm. For k=1 the well-known Crouzeix-Raviart element is recovered.     

Characteristics difference method for incompressible miscible flow in porous media

Two-phase ,incompressible miscible flow in porous media is governed by a system ofnonlinear partial differential equations. The pressure equation ,which is e11iptic in appearance ,isdiseretizod by a standard five-points difference method, The concentration equation is treated byan impliclt finite difference method that appbes a form of the method of characterlstics to thetransport terms. A class of biquadlatle interpolation is introduced for the method of chracteristics.Convergence rate is proved to be O(△t h^2)。