Convergence analysis of a multigrid method for convection–diffusion equations

Summary. This paper is concerned with the convergence analysis of robust multigrid methods for convection-diffusion problems. We consider a finite difference discretization of a 2D model convection-diffusion problem with constant coefficients and Dirichlet boundary conditions. For the approximate solution of this discrete problem a multigrid method based on semicoarsening, matrix-dependent prolongation and restriction and line smoothers is applied. For a multigrid W-cycle we prove an upper bound for the contraction number in the euclidean norm which is smaller than one and independent of the mesh size and the diffusion/convection ratio. For the contraction number of a multigrid V-cycle a bound is proved which is uniform for a class of convection-dominated problems. The analysis is based on linear algebra arguments only. Received April 26, 2000 / Published online June 20, 2001     

A uniformly convergent scheme for a system of reaction–diffusion equations

In this work a system of two parabolic singularly perturbed equations of reaction–diffusion type is considered. The asymptotic behaviour of the solution and its partial derivatives is given. A decomposition of the solution in its regular and singular parts has been used for the asymptotic analysis of the spatial derivatives. To approximate the solution we consider the implicit Euler method for time stepping and the central difference scheme for spatial discretization on a special piecewise uniform Shishkin mesh. We prove that this scheme is uniformly convergent, with respect to the diffusion parameters, having first-order convergence in time and almost second-order convergence in space, in the discrete maximum norm. Numerical experiments illustrate the order of convergence proved theoretically.     

Robust convergence of a compact fourth-order finite difference scheme for reaction–diffusion problems

We consider a singularly perturbed one-dimensional reaction–diffusion problem with strong layers. The problem is discretized using a compact fourth order finite difference scheme. Altough the discretization is not inverse monotone we are able to establish its maximum-norm stability and to prove its pointwise convergence on a Shishkin mesh. The convergence is uniform with respect to the perturbation parameter. Numerical experiments complement our theoretical results.     

The discrete maximum principle for linear simplicial finite element approximations of a reaction-diffusion problem

This paper provides a sufficient condition for the discrete maximum principle for a fully discrete linear simplicial finite element discretization of a reaction-diffusion problem to hold. It explicitly bounds the dihedral angles and heights of simplices in the finite element partition in terms of the magnitude of the reaction coefficient and the spatial dimension. As a result, it can be computed how small the acute simplices should be for the discrete maximum principle to be valid. Numerical experiments suggest that the bound, which considerably improves a similar bound in [P.G. Ciarlet, P.-A. Raviart, Maximum principle and uniform convergence for the finite element method, Comput. Methods Appl. Mech. Eng. 2 (1973) 17-31.], is in fact sharp.     

Mesh optimization for singular axisymmetric harmonic maps from the disc into the sphere

We describe in a mathematical setting the singular energy minimizing axisymmetric harmonic maps from the unit disc into the unit sphere; then, we use this as a test case to compute optimal meshes in presence of sharp boundary layers. For the well-posedness of the continuous minimizing problem, we introduce a lower semicontinuous extension of the energy with respect to weak convergence in BV, and we prove that the extended minimization problem has a unique singular solution. We then show how a moving finite element method, in which the mesh is an unknown of the discrete minimization problem obtained by finite element discretization, mimics this geometric point of view. Finally, we present numerical computations with boundary layers of zero thickness, and we give numerical evidence of the convergence of the method. This last aspect is proved in another paper. This work was supported by the Centre de Mathématiques et de Leurs Applications, Ecole Normale Supérieure de Cachan, 61 av. du Président Wilson, 94235 Cachan Cedex, France     

Infinite reload options: Pricing and analysis

Infinite reload options allow the user to exercise his reload right as often as he chooses during the lifetime of the contract. Each time a reload occurs, the owner receives new options where the strike price is set to the current stock price. We consider a modified version of the infinite reload option contract where the strike price of the new options received by the owner is increased by a certain percentage; we refer to this new contract as an increased reload option. The pricing problem for this modified contract is characterized as an impulse control problem resulting in a Hamilton–Jacobi–Bellman equation. We use fully implicit timestepping and prove that the discretized equations are monotone, stable and consistent, implying convergence to the viscosity solution. We also derive a globally convergent iterative method for solving the non-linear discrete equations. Numerical examples show that both the exercise policy and the option value are very sensitive to the percentage increase in the reload strike.     

Existence and approximation results for shape optimization problems in rotordynamics

We consider a shape optimization problem in rotordynamics where the mass of a rotor is minimized subject to constraints on the natural frequencies. Our analysis is based on a class of rotors described by a Rayleigh beam model including effects of rotary inertia and gyroscopic moments. The solution of the equation of motion leads to a generalized eigenvalue problem. The governing operators are non-symmetric due to the gyroscopic terms. We prove the existence of solutions for the optimization problem by using the theory of compact operators. For the numerical treatment of the problem a finite element discretization based on a variational formulation is considered. Applying results on spectral approximation of linear operators we prove that the solution of the discretized optimization problem converges towards the solution of the continuous problem if the discretization parameter tends to zero. Finally, a priori estimates for the convergence order of the eigenvalues are presented and illustrated by a numerical example.     

Finite element analysis of the vibration problem of a plate coupled with a fluid

Summary. We consider the approximation of the vibration modes of an elastic plate in contact with a compressible fluid. The plate is modelled by Reissner-Mindlin equations while the fluid is described in terms of displacement variables. This formulation leads to a symmetric eigenvalue problem. Reissner-Mindlin equations are discretized by a mixed method, the equations for the fluid with Raviart-Thomas elements and a non conforming coupling is used on the interface. In order to prove that the method is locking free we consider a family of problems, one for each thickness , and introduce appropriate scalings for the physical parameters so that these problems attain a limit when . We prove that spurious eigenvalues do not arise with this discretization and we obtain optimal order error estimates for the eigenvalues and eigenvectors valid uniformly on the thickness parameter t. Finally we present numerical results confirming the good performance of the method. Received February 4, 1998 / Revised version received May 26, 1999 / Published online June 21, 2000     

Analysis of a stabilized three-fields domain decomposition method

Summary. In this paper we prove that, for suitable choices of the bilinear form involved in the stabilization procedure, the stabilized three fields domain decomposition method proposed in [8] is stable and convergent uniformly in the number of subdomains and with respect to their sizes under quite general assumptions on the decomposition and on the discretization spaces. The same is proven to hold for the resulting discrete Steklov-Poincaré operator. Received April 4, 2000 / Revised version received January 9, 2001 / Published online June 17, 2002     

Domain decomposition for multiscale PDEs

We consider additive Schwarz domain decomposition preconditioners for piecewise linear finite element approximations of elliptic PDEs with highly variable coefficients. In contrast to standard analyses, we do not assume that the coefficients can be resolved by a coarse mesh. This situation arises often in practice, for example in the computation of flows in heterogeneous porous media, in both the deterministic and (Monte–Carlo simulated) stochastic cases. We consider preconditioners which combine local solves on general overlapping subdomains together with a global solve on a general coarse space of functions on a coarse grid. We perform a new analysis of the preconditioned matrix, which shows rather explicitly how its condition number depends on the variable coefficient in the PDE as well as on the coarse mesh and overlap parameters. The classical estimates for this preconditioner with linear coarsening guarantee good conditioning only when the coefficient varies mildly inside the coarse grid elements. By contrast, our new results show that, with a good choice of subdomains and coarse space basis functions, the preconditioner can still be robust even for large coefficient variation inside domains, when the classical method fails to be robust. In particular our estimates prove very precisely the previously made empirical observation that the use of low-energy coarse spaces can lead to robust preconditioners. We go on to consider coarse spaces constructed from multiscale finite elements and prove that preconditioners using this type of coarsening lead to robust preconditioners for a variety of binary (i.e., two-scale) media model problems. Moreover numerical experiments show that the new preconditioner has greatly improved performance over standard preconditioners even in the random coefficient case. We show also how the analysis extends in a straightforward way to multiplicative versions of the Schwarz method. We would like to thank Bill McLean for very useful discussions concerning this work. We would also like to thank Maksymilian Dryja for helping us to improve the result in Theorem 4.3.     

Adaptive frame methods for nonlinear variational problems

In this paper we develop adaptive numerical solvers for certain nonlinear variational problems. The discretization of the variational problems is done by a suitable frame decomposition of the solution, i.e., a complete, stable, and redundant expansion. The discretization yields an equivalent nonlinear problem on the space of frame coefficients. The discrete problem is then adaptively solved using approximated nested fixed point and Richardson type iterations. We investigate the convergence, stability, and optimal complexity of the scheme. A theoretical advantage, for example, with respect to adaptive finite element schemes is that convergence and complexity results for the latter are usually hard to prove. The use of frames is further motivated by their redundancy, which, at least numerically, has been shown to improve the conditioning of the discretization matrices. Also frames are usually easier to construct than Riesz bases. We present a construction of divergence-free wavelet frames suitable for applications in fluid dynamics and magnetohydrodynamics. M. Fornasier acknowledges the financial support provided through the Intra-European Individual Marie Curie Fellowship Programme, under contract MOIF-CT-2006-039438. All of the authors acknowledge the hospitality of Dipartimento di Metodi e Modelli Matematici per le Scienze Applicate, Università di Roma “La Sapienza”, Italy, during the early preparation of this work. The authors want to thank Daniele Boffi, Dorina Mitrea, and Karsten Urban for the helpful and fruitful discussions on divergence-free function spaces.     

A numerical scheme for the Maxwell equations in the quasi-static regime with a non-local source

In this paper we study a non-linear evolution equation, based on quasi-static electromagnetic fields, with a non-local field-dependent source. This model occurs in transformer driven active magnetic shielding. We present a numerical scheme for both time and space discretization and prove convergence of this scheme. We also derive the corresponding error estimates.     

Additive Schwarz methods for thep-version finite element method

Summary In this paper, we study some additive Schwarz methods (ASM) for thep-version finite element method. We consider linear, scalar, self adjoint, second order elliptic problems and quadrilateral elements in the finite element discretization. We prove a constant bound independent of the degreep and the number of subdomainsN, for the condition number of the ASM iteration operator. This optimal result is obtained first in dimension two. It is then generalized to dimensionn and to a variant of the method on the interface. Numerical experiments confirming these results are reported. As is the case for other additive Schwarz methods, our algorithms are highly parallel and scalable.This work was supported in part by the Applied Math. Sci. Program of the U.S. Department of Energy under contract DE-FG02-88ER25053 and, in part, by the National Science Foundation under Grant NSF-CCR-9204255     

Performance and analysis of saddle point preconditioners for the discrete steady-state Navier-Stokes equations

Summary. We examine the convergence characteristics of iterative methods based on a new preconditioning operator for solving the linear systems arising from discretization and linearization of the steady-state Navier-Stokes equations. With a combination of analytic and empirical results, we study the effects of fundamental parameters on convergence. We demonstrate that the preconditioned problem has an eigenvalue distribution consisting of a tightly clustered set together with a small number of outliers. The structure of these distributions is independent of the discretization mesh size, but the cardinality of the set of outliers increases slowly as the viscosity becomes smaller. These characteristics are directly correlated with the convergence properties of iterative solvers. Received August 5, 2000 / Published online June 20, 2001     

A cascadic multigrid algorithm for semilinear elliptic problems

Summary. We propose a cascadic multigrid algorithm for a semilinear elliptic problem. The nonlinear equations arising from linear finite element discretizations are solved by Newton's method. Given an approximate solution on the coarsest grid on each finer grid we perform exactly one Newton step taking the approximate solution from the previous grid as initial guess. The Newton systems are solved iteratively by an appropriate smoothing method. We prove that the algorithm yields an approximate solution within the discretization error on the finest grid provided that the start approximation is sufficiently accurate and that the initial grid size is sufficiently small. Moreover, we show that the method has multigrid complexity. Received February 12, 1998 / Revised version received July 22, 1999 / Published online June 8, 2000     

A robust a posteriori estimator for the Residual-free Bubbles method applied to advection-diffusion problems

Summary. We develop the a posteriori error analysis for the RFB method, applied to the linear advection-diffusion problem: the numerical error, measured in suitable norms, is estimated in terms of the numerical residual. The robustness is investiged, in the sense that we prove uniform equivalence between a norm of the numerical residual and a particular norm of the error. Received January 21, 2000 / Published online March 20, 2001     

Multigrid in H (div) and H (curl)

Summary. We consider the solution of systems of linear algebraic equations which arise from the finite element discretization of variational problems posed in the Hilbert spaces and in three dimensions. We show that if appropriate finite element spaces and appropriate additive or multiplicative Schwarz smoothers are used, then the multigrid V-cycle is an efficient solver and preconditioner for the discrete operator. All results are uniform with respect to the mesh size, the number of mesh levels, and weights on the two terms in the inner products. Received June 12, 1998 / Revised version received March 12, 1999 / Published online January 27, 2000     

An almost fourth order uniformly convergent difference scheme for a semilinear singularly perturbed reaction-diffusion problem

Summary. This paper is concerned with a high order convergent discretization for the semilinear reaction-diffusion problem: , for , subject to , where . We assume that on , which guarantees uniqueness of a solution to the problem. Asymptotic properties of this solution are discussed. We consider a polynomial-based three-point difference scheme on a simple piecewise equidistant mesh of Shishkin type. Existence and local uniqueness of a solution to the scheme are analysed. We prove that the scheme is almost fourth order accurate in the discrete maximum norm, uniformly in the perturbation parameter . We present numerical results in support of this result. Received February 25, 1994     

Positive definite balancing Neumann–Neumann preconditioners for nearly incompressible elasticity

In this paper, a positive definite Balancing Neumann–Neumann (BNN) solver for the linear elasticity system is constructed and analyzed. The solver implicitly eliminates the interior degrees of freedom in each subdomain and solves iteratively the resulting Schur complement, involving only interface displacements, using a BNN preconditioner based on the solution of a coarse elasticity problem and local elasticity problems with natural and essential boundary conditions. While the Schur complement becomes increasingly ill-conditioned as the materials becomes almost incompressible, the BNN preconditioned operator remains well conditioned. The main theoretical result of the paper shows that the proposed BNN method is scalable and quasi-optimal in the constant coefficient case. This bound holds for material parameters arbitrarily close to the incompressible limit. While this result is due to an underlying mixed formulation of the problem, both the interface problem and the preconditioner are positive definite. Numerical results in two and three dimensions confirm these good convergence properties and the robustness of the methods with respect to the almost incompressibility of the material.     

A stabilized mixed finite element method for the biharmonic equation based on biorthogonal systems

We propose a stabilized finite element method for the approximation of the biharmonic equation with a clamped boundary condition. The mixed formulation of the biharmonic equation is obtained by introducing the gradient of the solution and a Lagrange multiplier as new unknowns. Working with a pair of bases forming a biorthogonal system, we can easily eliminate the gradient of the solution and the Lagrange multiplier from the saddle point system leading to a positive definite formulation. Using a superconvergence property of a gradient recovery operator, we prove an optimal a priori estimate for the finite element discretization for a class of meshes.