ALBERT

Description: We show the existence and uniqueness of a solution for the nonlocal vector-valued Allen–Cahn variational inequality in a formulation involving Lagrange multipliers for local and nonlocal constraints. Furthermore, we propose and analyse a primal–dual active set (PDAS) method for local and nonlocal vector-valued Allen–Cahn variational inequalities. The local convergence behaviour of the PDAS algorithm is studied by interpreting the approach as a semismooth Newton method and numerical simulations are presented demonstrating its efficiency.

Description: In this paper, we will present a generalized convolution quadrature for solving linear parabolic and hyperbolic evolution equations. The original convolution quadrature method by Lubich works very nicely for equidistant time steps while the generalization of the method and its analysis to nonuniform time stepping is by no means obvious. We will introduce the generalized convolution quadrature allowing for variable time steps and develop a theory for its error analysis. This method opens the door for further development towards adaptive time stepping for evolution equations. As the main application of our new theory, we will consider the wave equation in exterior domains which is formulated as a retarded boundary integral equation.

Description: We address the error control of Galerkin discretization (in space) of linear second-order hyperbolic problems. More specifically, we derive a posteriori error bounds in the L ( L 2 ) norm for finite element methods for the linear wave equation, under minimal regularity assumptions. The theory is developed for both the space-discrete case and for an implicit fully discrete scheme. The derivation of these bounds relies crucially on carefully constructed space and time reconstructions of the discrete numerical solutions, in conjunction with a technique introduced by Baker (1976, Error estimates for finite element methods for second-order hyperbolic equations. SIAM J. Numer. Anal. , 13 , 564–576) in the context of a priori error analysis of Galerkin discretization of the wave problem in weaker-than-energy spatial norms.

Description: The surface finite element method can be used to approximate curvatures on embedded hypersurfaces and to discretize geometric partial differential equations. In this paper, we present a definition of discrete Ricci curvature on polyhedral hypersurfaces of arbitrary dimension based on the discretization of a weak formulation with isoparametric finite elements. We prove that for a piecewise quadratic approximation of a two- or three-dimensional hypersurface R n +1 , this definition approximates the Ricci curvature of with a linear order of convergence in the L 2 ( ) norm. By using a smoothing scheme in the case of a piecewise linear approximation of , we still get a convergence of order 2/3 in the L 2 ( ) norm and of order 1/3 in the W 1, 2 ( ) norm.

Description: We give general conditions which guarantee that the sequence generated by a descent algorithm converges to an equilibrium point. The convergence result is based on the Lojasiewicz gradient inequality; optimal convergence rates are also derived, as well as a stability result. We show how our results apply to a large variety of standard time discretizations of gradient-like flows. Schemes with variable time step are considered and optimal conditions on the maximal step size are derived. Applications to time and space discretizations of the Allen–Cahn equation, the sine–Gordon equation and a damped wave equation are given.

Description: This paper presents quadratic finite-volume methods for elliptic and parabolic problems on quadrilateral meshes that use Barlow points (optimal stress points) for dual partitions. Introducing Barlow points into the finite-volume formulations results in better approximation properties at the cost of loss of symmetry. The novel ‘symmetrization’ technique adopted in this paper allows us to derive optimal-order error estimates in the H 1 - and L 2 -norms for elliptic problems and in the L ( H 1 )- and L ( L 2 )-norms for parabolic problems. Superconvergence of the difference between the gradients of the finite-volume solution and the interpolant can also be derived. Numerical results confirm the proved error estimates.

Description: A linear parabolic differential equation on a moving surface is discretized in space by evolving-surface finite elements and in time by backward difference formulas (BDFs). Using results from Dahlquist's G-stability theory and Nevanlinna & Odeh's multiplier technique together with properties of the spatial semidiscretization, stability of the full discretization is proved for BDF methods up to order 5 and optimal-order convergence is shown. Numerical experiments illustrate the behaviour of the fully discrete method.

Description: In this article, we develop the a priori and a posteriori error analysis of hp -version interior penalty discontinuous Galerkin finite element methods for strongly monotone quasi-Newtonian fluid flows in a bounded Lipschitz domain R d , d = 2, 3. In the latter case, computable upper and lower bounds on the error are derived in terms of a natural energy norm, which are explicit in the local mesh size and local polynomial degree of the approximating finite element method. A series of numerical experiments illustrate the performance of the proposed a posteriori error indicators within an automatic hp -adaptive refinement algorithm.

Description: In recent years, it has become increasingly clear that the critical issue in gradient methods is the choice of the step length, whereas using gradient as the search direction may lead to very effective algorithms, whose surprising behaviour has only been partially explained, mostly in terms of the spectrum of the Hessian matrix. On the other hand, the convergence of the classical Cauchy steepest descent (SD) method has been analysed extensively and related to the spectral properties of the Hessian matrix, but the connection with the spectrum of the Hessian has not been exploited much to modify the method in order to improve its behaviour. In this work, we show how, for convex quadratic problems, moving from some theoretical properties of the SD method, second-order information provided by the step length can be exploited to dramatically improve the usually poor practical behaviour of this method. This allows us to achieve computational results comparable with those of the Barzilai and Borwein algorithm, with the further advantage of monotonic behaviour.

Description: In recent years, there has been an enormous interest in developing methods for the approximation of manifold-valued functions. In this paper, we focus on the manifold of symmetric positive-definite (SPD) matrices. We investigate the use of SPD-matrix means to adapt linear positive approximation methods to SPD-matrix-valued functions. Specifically, we adapt corner-cutting subdivision schemes and Bernstein operators. We present the concept of admissible matrix means and study the adapted approximation schemes based on them. Two important cases of admissible matrix means are treated in detail: the exp–log and the geometric matrix means. We derive special properties of the approximation schemes based on these means. The geometric mean is found to be superior in the sense of preserving more properties of the data, such as monotonicity and convexity. Furthermore, we give error bounds for the approximation of univariate SPD-matrix-valued functions by the adapted operators.

Description: We present a mass-preserving scheme for the stochastic nonlinear Schrödinger equation with multiplicative noise of Stratonovich type. It is a splitting scheme and we present an explicit formula for solving the sub-step related to the nonlinear part. The scheme is unconditionally stable in the L 2 norm. For the linear stochastic Schrödinger equation, we prove that the scheme has a strong convergence rate in time equal to 1, which is not common for stochastic partial differential equations with noise depending on space and time.

Description: A numerical scheme for the approximation of the elastic flow of inextensible curves is devised and convergence of approximations to exact solutions of the nonlinear time-dependent partial differential equation is proved. The nonlinear, pointwise constraint of local length preservation is linearized about a previous solution in each time step which leads to a sequence of linear saddle-point problems. The spatial discretization is based on piecewise Bézier curves and the resulting semiimplicit scheme is unconditionally stable and convergent.

Description: We study the coercivity properties and the norm dependence on the wave-number k of certain regularized combined field boundary integral operators that we recently introduced for the solution of two- and three-dimensional acoustic scattering problems with Neumann boundary conditions. We show that in the case of circular and spherical boundaries, our regularized combined field boundary integral operators are L 2 coercive for large enough values of the coupling parameter, and that the norms of these operators are bounded by constant multiples of the coupling parameter. We establish that the norms of the regularized combined field boundary integral operators grow modestly with the wave-number k for smooth boundaries and we provide numerical evidence that these operators are L 2 coercive for two-dimensional starlike boundaries. We present and analyse a fully discrete collocation (Nyström) method for the solution of two-dimensional acoustic scattering problems with Neumann boundary conditions based on regularized combined field integral equations. In particular, for analytic boundaries and boundary data, we establish pointwise superalgebraic convergence rates of the discrete solutions.

Description: The classical theory of Gaussian quadrature assumes a positive weight function. We will show that in some cases Gaussian rules can be constructed with respect to an oscillatory weight, yielding methods with complex quadrature nodes and positive weights. These rules are well suited to highly oscillatory integrals because they attain optimal asymptotic order. We show that, for the Fourier oscillator, this approach yields the numerical method of steepest descent, a method with optimal asymptotic order that has previously been proposed for this class of integrals. However, the approach readily extends to more general kernels, such as Bessel functions that appear as the kernel of the Hankel transform.

Description: We consider anisotropic Allen–Cahn equations with interfacial energy induced by an anisotropic surface energy density . Assuming that is positive, positively homogeneous of degree 1, strictly convex in tangential directions to the unit sphere and sufficiently smooth, we show the stability of various time discretizations. In particular, we consider a fully implicit and a linearized time discretization of the interfacial energy combined with implicit and semiimplicit time discretizations of the double-well potential. In the semiimplicit variant, concave terms are taken explicitly. The arising discrete spatial problems are solved by globally convergent truncated nonsmooth Newton multigrid methods. Numerical experiments show the accuracy of the different discretizations. We also illustrate that pinch-off under anisotropic mean curvature flow is no longer invariant under rotation of the initial configuration for a fixed orientation of the anisotropy.

Description: In this paper, we define a new finite element method for numerically approximating the solution of a partial differential equation in a bulk region coupled with a surface partial differential equation posed on the boundary of the bulk domain. The key idea is to take a polyhedral approximation of the bulk region consisting of a union of simplices, and to use piecewise polynomial boundary faces as an approximation of the surface. Two finite element spaces are defined, one in the bulk region and one on the surface, by taking the set of all continuous functions which are also piecewise polynomial on each bulk simplex or boundary face. We study this method in the context of a model elliptic problem; in particular, we look at well-posedness of the system using a variational formulation, derive perturbation estimates arising from domain approximation and apply these to find the optimal-order error estimates. A numerical experiment is described which demonstrates the order of convergence.

Description: As a model of more general contour integration problems we consider the numerical calculation of high-order derivatives of holomorphic functions using Cauchy's integral formula. Bornemann (2011, Accuracy and stability of computing high-order derivatives of analytic functions by Cauchy integrals. Found. Comput. Math. , 11 , 1–63) showed that the condition number of the Cauchy integral strongly depends on the chosen contour and solved the problem of minimizing the condition number for circular contours. In this paper, we minimize the condition number within the class of grid paths of step size h using Provan's algorithm for finding a shortest enclosing walk in weighted graphs embedded in the plane. Numerical examples show that optimal grid paths yield small condition numbers even in those cases where circular contours are known to be of limited use, such as for functions with branch-cut singularities.

Description: Anisotropic meshes are important for efficiently resolving incompressible flow problems that include boundary layer or corner singularity phenomena. Unfortunately, the stability of standard inf–sup stable mixed approximation methods is prone to degeneracy whenever the mesh aspect ratio becomes large. As an alternative, a stabilized mixed approximation method is considered here. Specifically, a robust a priori error estimate for the local jump stabilized Q 1 – P 0 approximation introduced by Kechkar & Silvester (1992, Analysis of locally stabilized mixed finite element methods for the Stokes problem. Math. Comp. , 58 , 1–10) is established for anisotropic meshes. Our numerical results demonstrate that the stabilized Q 1 – P 0 method is competitive with the nonconforming, nonparametric, rotated approximation method introduced by Rannacher & Turek (1992, Simple nonconforming quadrilateral Stokes element. Numer. Meth. Partial Differential Equations , 8 , 97–111).

Description: This work is about the numerical solution of the time-domain Maxwell's equations in dispersive propagation media by a discontinuous Galerkin time-domain method. The Debye model is used to describe the dispersive behaviour of the media. The resulting system of differential equations is solved using a centred-flux discontinuous Galerkin formulation for the discretization in space and a second-order leapfrog scheme for the integration in time. The numerical treatment of the dispersive model relies on an auxiliary differential equation approach similar to that which is adopted in the finite difference time-domain method. Stability estimates are derived through energy considerations and convergence is proved for both the semidiscrete and the fully discrete schemes.

Description: The parabolic singularly perturbed problem u xx ( x , t ) – x α u t ( x , t ) = f ( x , t ) is considered on the rectangular domain = (0,1) x (0, T ] with Dirichlet initial and boundary conditions. Here, is a small positive parameter and α is a positive constant. This problem is degenerate since the coefficient x α of u t vanishes along the side x = 0 of . Bounds on the derivatives of u are used to design a nonuniform mesh and a finite difference method on this mesh is constructed to solve the problem numerically. As the solution u is not in general uniformly bounded with respect to in the maximum norm, the convergence analysis of the numerical method requires the use of some unusual barrier functions and a special weighted discrete norm. Numerical examples are provided to support the theoretical results.

Description: We consider the numerical approximation of a general second-order semilinear parabolic stochastic partial differential equation driven by multiplicative and additive space–time noise. We examine convergence of exponential integrators for multiplicative and additive noise. We consider noise that is in a trace class and give a convergence proof in the root-mean-square L 2 norm. We discretize in space with the finite element method and in our implementation we examine both the finite element and the finite volume methods. We present results for a linear reaction–diffusion equation in two dimensions as well as a nonlinear example of a two-dimensional stochastic advection–diffusion–reaction equation motivated from realistic porous media flow.

Description: Sparse grids (Zenger, C. (1990) Sparse grids. Parallel Algorithms for Partial Differential Equations (W. Hackbusch ed.) Notes on Numerical Fluid Dynamics 31. Proceedings of the Sixth GAMM-Seminar; Bungartz, H.-J. & Griebel, M. (2004) Sparse grids. Acta Numer. , 13 , 1–123.) are tailored to the approximation of smooth high-dimensional functions. On a d -dimensional tensor product space, the number of grid points is N = O( h –1 |log h | d –1 ), where h is a mesh parameter. The so-called combination technique, based on hierarchical decomposition and extrapolation, requires specific multivariate error expansions of the discretization error on Cartesian grids to hold. We derive such error expansions for linear difference schemes through an error correction technique of semi-discretizations. We obtain overall error formulae of the type = O ( h p |log h | d –1 ) and analyse the convergence, with its dependence on dimension and smoothness, by examples of linear elliptic and parabolic problems, with numerical illustrations in up to eight dimensions.

Description: The numerical simulation of two-phase flow in a porous medium may lead, when using coupled finite volume schemes on structured grids, to the appearance of the so-called Grid Orientation Effect (GOE). We propose in this paper a procedure to eliminate this phenomenon, based on the use of new fluxes with a new stencil in the discrete version of the convection equation, without changing the discrete scheme for computing the pressure field. Numerical results show that the GOE does not significantly decrease with the size of the discretization using the initial scheme on the coupled problem, but that it is efficiently suppressed by the new procedure, even on coarse meshes. A mathematical study, based on a weak BV inequality using the new fluxes, confirms the convergence of the modified scheme in a particular case.

Description: The celebrated truncated T-matrix method for wave propagation models belongs to a class of the reduced basis methods (RBMs), with the parameters being incident waves and incident directions. The T-matrix characterizes the scattering properties of the obstacles independent of the incident and receiver directions. In the T-matrix method the reduced set of basis functions for representation of the scattered field is constructed analytically and hence, unlike other classes of the RBM, the T-matrix RBM avoids computationally intensive empirical construction of a reduced set of parameters and the associated basis set. However, establishing a convergence analysis and providing practical a priori estimates for reducing the number of basis functions in the T-matrix method has remained an open problem for several decades. In this work we solve this open problem for time-harmonic acoustic scattering in two and three dimensions. We numerically demonstrate the convergence analysis and the a priori parameter estimates for both point-source and plane-wave incident waves. Our approach can be used in conjunction with any numerical method for solving the forward wave propagation problem.

Description: We derive an algorithm for the adaptive approximation of solutions to parabolic equations. It is based on adaptive finite elements in space and the implicit Euler discretization in time with adaptive time-step sizes. We prove that, given a positive tolerance for the error, the adaptive algorithm reaches the final time with a space–time error between continuous and discrete solution that is below the given tolerance. Numerical experiments reveal a more than competitive performance of our algorithm ASTFEM (adaptive space–time finite element method).

Description: We propose and analyse a new family of nonconforming elements for the Brinkman problem of porous media flow. The corresponding finite element methods are robust with respect to the limiting case of Darcy flow, and the discretely divergence-free functions are in fact divergence-free. Therefore, in the absence of sources and sinks, the method is strongly mass-conservative. We also show how the proposed elements are part of a discrete de Rham complex.

Description: In this paper we investigate the superconvergence of local discontinuous Galerkin (LDG) methods for solving one-dimensional linear time-dependent fourth-order problems. We prove that the error between the LDG solution and a particular projection of the exact solution, e u , achieves th-order superconvergence when polynomials of degree k ( k ≥ 1) are used. Numerical experiments with P k polynomials, with 1 ≤ k ≤ 3, are displayed to demonstrate the theoretical results, which show that the error e u actually achieves ( k +2)th-order superconvergence, indicating that the error bound for e u obtained in this paper is suboptimal. Initial boundary value problems, nonlinear equations and solutions having singularities, are numerically investigated to verify that the conclusions hold true for very general cases.

Description: The discrete mollification method, a convolution-based filtering procedure for the regularization of illposed problems, is applied here to stabilize explicit schemes, which were first analysed by Karlsen & Risebro (2001, An operator splitting method for nonlinear convection–diffusion equations. M2AN Math. Model. Numer. Anal. 35 , 239–269) for the solution of initial value problems of strongly degenerate parabolic partial differential equations in two space dimensions. Two new schemes are proposed, which are based on directionwise and two-dimensional discrete mollification of the second partial derivatives forming the Laplacian of the diffusion function. The mollified schemes permit substantially larger time steps than the original (basic) scheme. It is proven that both schemes converge to the unique entropy solution of the initial value problem. Numerical examples demonstrate that the mollified schemes are competitive in efficiency, and in many cases significantly more efficient, than the basic scheme.

Description: A family of explicit adaptive algorithms is designed to solve nonlinear scalar one-dimensional conservation laws. Based on the Godunov scheme on a uniform grid, a first strategy uses the multiresolution analysis of the solution to design an adaptive grid that evolves in time according to the time-dependent local smoothness. The method is furthermore enhanced by a local time-stepping strategy. Both numerical schemes are shown to converge towards the unique entropy solution.

Description: In this paper the first error analyses of hybridizable discontinuous Galerkin (HDG) methods for convection–diffusion equations for variable-degree approximations and nonconforming meshes are presented. The analysis technique is an extension of the projection-based approach recently used to analyse the HDG method for the purely diffusive case. In particular, for approximations of degree k on all elements and conforming meshes, we show that the order of convergence of the error in the diffusive flux is k + 1 and that of a projection of the error in the scalar unknown is 1 for k = 0 and k + 2 for k 〉 0. When nonconforming meshes are used our estimates do not rule out a degradation of 1/2 in the order of convergence in the diffusive flux and a loss of 1 in the order of convergence of the projection of the error in the scalar variable. However, they do guarantee the optimal convergence of order k + 1 of the scalar variable.

Description: Fast multigrid solvers are considered for the linear systems arising from the bilinear finite element discretizations of second-order elliptic equations with anisotropic diffusion. Optimal convergence of Vcycle multigrid methods in the semicoarsening case and nearly optimal convergence of V-cycle multigrid method with line smoothing in the uniformly-coarsening case are established using the Xu-Zikatanov identity. Since the ‘regularity assumption’ is not used in the analysis, the results can be extended to general domains consisting of rectangles.

Description: In this paper we consider a class of incompressible viscous fluids whose viscosity depends on the shear rate and pressure. We deal with isothermal steady flow and analyse the Galerkin discretization of the corresponding equations. We discuss the existence and uniqueness of discrete solutions and their convergence to the solution of the original problem. In particular, we derive a priori error estimates, which provide optimal rates of convergence with respect to the expected regularity of the solution. Finally, we demonstrate the achieved results by numerical experiments. The fluid models under consideration appear in many practical problems, for instance, in elastohydrodynamic lubrication where very high pressures occur. Here we consider shear-thinning fluid models similar to the power-law/Carreau model. A restricted sublinear dependence of the viscosity on the pressure is allowed. The mathematical theory concerned with the self-consistency of the governing equations has emerged only recently. We adopt the established theory in the context of discrete approximations. To our knowledge, this is the first analysis of the finite element method for fluids with pressure-dependent viscosity. The derived estimates coincide with the optimal error estimates established recently for Carreau-type models, which are covered as a special case.

Description: Discrete maximum principles (DMPs) are established for finite element approximations of systems of nonlinear parabolic partial differential equations with mixed boundary and interface conditions. The results are based on an algebraic DMP for suitable systems of ordinary differential equations.

Description: The adaptive cubic regularization algorithm described in Cartis et al. (2009, Adaptive cubic regularisation methods for unconstrained optimization. Part I: motivation, convergence and numerical results. Math. Program. , 127 , 245–295; 2010, Adaptive cubic regularisation methods for unconstrained optimization. Part II: worst-case function- and derivative-evaluation complexity [online]. Math. Program. , DOI: 10.1007/s10107-009-0337-y) is adapted to the problem of minimizing a nonlinear, possibly nonconvex, smooth objective function over a convex domain. Convergence to first-order critical points is shown under standard assumptions, without any Lipschitz continuity requirement on the objective's Hessian. A worst-case complexity analysis in terms of evaluations of the problem's function and derivatives is also presented for the Lipschitz continuous case and for a variant of the resulting algorithm. This analysis extends the best-known bound for general unconstrained problems to nonlinear problems with convex constraints.

Description: This work is intended to provide a convenient tool for the mathematical analysis of a particular kind of finite volume approximation which can be used, for instance, in the context of nonlinear and/or anisotropic diffusion operators in three dimensions (3D). Following the so-called DDFV (discrete duality finite volume) approach developed by Hermeline (1998, Une méthode de volumes finis pour les équations elliptiques du second ordre. C. R. Math. Acad. Sci. Paris , 326 , 1433–1436 (in French); 2000, A finite volume method for the approximation of diffusion operators on distorted meshes. J. Comput. Phys. , 160 , 481–499) and by Domelevo & Omnès (2005, A finite volume method for the Laplace equation on almost arbitrary two-dimensional grids. M2AN Math. Model. Numer. Anal. , 39 , 1203–1249) in 3D, we consider a ‘double’ covering T of a 3D domain by a rather general primal mesh and by a well-chosen ‘dual’ mesh. The associated discrete divergence operator div  T is obtained by the standard finite volume approach. A simple and consistent discrete gradient operator T is defined by a local affine interpolation that takes into account the geometry of the double mesh. Under mild geometrical constraints on the choice of the dual volumes, we show that –div  T and T are linked by the ‘discrete duality property’, which is an analogue of the integration-by-parts formula. The primal mesh need not be conformal, and its interfaces can be general polygons. We give several numerical examples for anisotropic linear diffusion problems; good convergence properties are observed. The sequel, Andreianov et al. (2011a, On 3D DDFV discretization of gradient and divergence operators. II. Discrete functional analysis tools and applications to degenerate parabolic problems. HAL preprint available at http://hal.archives-ouvertes.fr/hal-00567342 ) to this paper will summarize some key discrete functional analysis tools for DDFV schemes and give applications to proving convergence of DDFV schemes for several nonlinear degenerate parabolic partial differential equations.

Description: This work is concerned with the numerical implementation of the discrepancy principle for nonsmooth Tikhonov regularization for linear inverse problems. First, some theoretical properties of the solutions to the discrepancy equation, i.e., uniqueness and upper bounds, are discussed. Then, the idea of Padé approximation is exploited for designing model functions with model parameters iteratively updated. Two algorithms are proposed for its efficient numerical realization, i.e., a two-parameter algorithm based on model functions and a quasi-Newton method, and their convergence properties are briefly discussed. Numerical results for four nonsmooth models are presented to demonstrate the accuracy of the principle and to illustrate the efficiency and robustness of the proposed algorithms.

Description: This paper is devoted to the convergence analysis of the upwind finite volume scheme for the initialand boundary-value problems associated with the linear transport equation in any dimension, on general unstructured meshes. We are particularly interested in the case where the initial and boundary data are in L and the advection vector field has low regularity properties, namely L 1 (]0, T [, ( W 1,1 ()) d ), with suitable assumptions on its divergence. In this general framework, we prove uniform in time strong convergence in L p (), with p 〈 +, of the approximate solution towards the unique weak solution of the problem as well as the strong convergence of its trace. The proof relies, in particular, on the Friedrichs' commutator argument, which is classical in the renormalized solutions theory. Note that this result remains valid if the data are suitably approximated in L 1 . This is nothing but the discrete counterpart of the nice compactness properties deduced from the renormalized solution theory. We conclude with some numerical experiments showing that the convergence rate seems to be 1/2, as in the case of smoother advection fields, but this is still an open question up to now.

Description: In this paper, we study the existence, uniqueness and regularity properties of solutions for the nonstandard Volterra integral equation . We then present a collocation method to solve this equation, and analyse the convergence and superconvergence of piecewise polynomial collocation approximations. We also illustrate the theoretical results by extensive numerical experiments.

Description: In this paper we consider the discretization error in space and time of an H 1 gradient flow for an energy integral where the energy density is given by the sum of a double-well potential term and a bending energy term. We show that the problem is equivalent to a nonlinear heat equation with nonlocal nonlinearity and adapt the standard error analysis theory developed for the nonlinear heat equation to our case. In doing so we bound the discretization error in terms of the mesh size and time step as well as energy parameters. In particular, we carefully track how the size of the bending energy affects the error bounds.

Description: A local convergence analysis of Newton's method for finding a singularity of a differentiable vector field defined on a complete Riemannian manifold, based on the majorant principle, is presented in this paper. This analysis provides a clear relationship between the majorant function, which relaxes the Lipschitz continuity of the derivative, and the vector field under consideration. It also allows us to obtain the optimal convergence radius and the biggest range for the uniqueness of the solution and to unify some previously unrelated results.

Description: For analytic functions we study the kernel of the remainder terms of Gaussian quadrature rules with respect to Bernstein–Szego weight functions where 0〈 α 〈 β , β != 2 α , | |〈 β – α , and whose denominator is an arbitrary polynomial of exact degree 2 that remains positive on [–1, 1]. The subcase α =1, β =2/(1+ ), –1〈 〈0 and =0 has been considered recently by Spalevíc, M. M. & Praníc, M. S. ((2010) Error bounds of certain Gaussian quadrature formulae. J. Comput. Appl. Math., 234 , 1049–1057). The location on the elliptic contours where the modulus of the kernel attains its maximum value is investigated. This leads to effective error bounds for the corresponding Gaussian quadratures. The approach we use in this paper, which is different from the one adopted in Spalevíc, M. M. & Praníc, M. S. ((2010) Error bounds of certain Gaussian quadrature formulae. J. Comput. Appl. Math., 234 , 1049–1057), ensures that the actual conditions for determining the locations on the elliptic contours where the modulus of the kernel attains its maximum value are approximated very precisely.

Description: We consider an electromagnetic scattering problem produced by a perfect conductor. We pose the problem in a bounded region surrounding the obstacle and impose on the exterior boundary of the computational domain an impedance boundary condition inspired by the asymptotic behaviour of the scattered field at infinity. The operator associated with our problem belongs to a class of operators for which a suitable decomposition of the energy space plays an essential role in the analysis. This decomposition is performed here through a regularizing projector that takes into account the boundary conditions. The discrete version of this projector is the key tool to prove that a Galerkin scheme based on Nédélec’s edge elements is well posed and convergent under general topological assumptions on the scatterer and without assuming special requirements on the triangulations.

Description: Gould and Robinson (2010, SIAM J. Optim. , 20 , 2023–2048; 2010, SIAM J. Optim. , 20 , 2049–2079) introduced a second-derivative sequential quadratic programming method (S2QP) for solving nonlinear nonconvex optimization problems. We proved that the method is globally and locally superlinearly convergent under common assumptions. A critical component of the algorithm is the so-called predictor step, which is computed from a strictly convex quadratic program with a trust-region constraint. This step is essential for proving global convergence but its propensity to identify the optimal active set is paramount for achieving fast local convergence. Thus the global and local efficiency of the method is intimately coupled with the quality of the predictor step. In this paper we study the effects of removing the trust-region constraint from the computation of the predictor step. This is reasonable since the resulting problem is still strictly convex and thus well defined. Although it is interesting theoretically to verify that the same convergence guarantees hold when no trust-region constraint is used, our motivation is based on the practical behaviour of the algorithm. Preliminary numerical experience with S2QP indicates that the trust-region constraint occasionally degrades the quality of the predictor step and diminishes its ability to correctly identify the optimal active set. Moreover, removal of the trust-region constraint allows for re-use of the predictor step over a sequence of failed iterations, thus reducing computation. We show that the modified algorithm remains globally convergent and preserves local superlinear convergence provided that a nonmonotone strategy is incorporated.

Description: We consider a recently proposed finite-element space that consists of piecewise affine functions with discontinuities across a smooth given interface (a curve in two dimensions, a surface in three dimensions). Contrary to existing extended finite element methodologies, the space is a variant of the standard conforming $${\mathbb{P}}_{1}$$ space that can be implemented element by element. Further, it neither introduces new unknowns nor deteriorates the sparsity structure. It is proved that, for u arbitrary in $${W}^{1,p}(\Omega \setminus \Gamma )\cap {W}^{2,s}(\Omega \setminus \Gamma )$$ , the interpolant $${\mathcal{I}}_{h}u$$ defined by this new space satisfies where h is the mesh size, $$\Omega \subset {\mathbb{R}}^{d}$$ is the domain, $$p 〉 d$$ , $$p\ge q$$ , $$s\ge q$$ and standard notation has been adopted for the function spaces. This result proves the good approximation properties of the finite-element space as compared to any space consisting of functions that are continuous across , which would yield an error in the $${L}^{q}(\Omega )$$ -norm of order . These properties make this space especially attractive for approximating the pressure in problems with surface tension or other immersed interfaces that lead to discontinuities in the pressure field. Furthermore, the result still holds for interfaces that end within the domain, as happens for example in cracked domains.

Description: A linear parabolic differential equation on a moving surface is first discretized in space by evolving surface finite elements and then in time by an implicit Runge–Kutta (RK) method. For algebraically stable and stiffly accurate RK methods unconditional stability of the full discretization is proven and the convergence properties are analysed. Moreover, the implementation is described for the case of the Radau IIA time discretization. Numerical experiments illustrate the behaviour of the fully discrete method.

Description: In this paper we develop the a priori and a posteriori error analyses of a mixed finite element method for the coupling of fluid flow with nonlinear porous media flow. Flows are governed by the Stokes and nonlinear Darcy equations, respectively, and the corresponding transmission conditions are given by mass conservation, balance of normal forces and the Beavers–Joseph–Saffman law. We consider dual-mixed formulations in both domains, and in order to handle the nonlinearity involved, we introduce the pressure gradient in the Darcy region as an auxiliary unknown. In addition, the transmission conditions become essential, which leads to the introduction of the traces of the porous media pressure and the fluid velocity as the associated Lagrange multipliers. As a consequence, the resulting variational formulation can be written, conveniently, as a twofold saddle point operator equation. Thus, a well-known generalization of the classical Babuska–Brezzi theory is applied to show the well-posedness of the continuous and discrete formulations and to derive the corresponding a priori error estimate. In particular, the set of feasible finite element subspaces includes Raviart–Thomas elements of lowest order and piecewise constants for the velocities and pressure, respectively, in both domains, together with piecewise constant vectors for the Darcy pressure gradient and continuous piecewise linear elements for the traces. Then, we employ classical approaches and use known estimates to derive a reliable and efficient residual-based a posteriori error estimator for the coupled problem. Finally, several numerical results confirming the good performance of the method and the theoretical properties of the a posteriori error estimator, and illustrating the capability of the corresponding adaptive algorithm to localize the singularities of the solution, are reported.

Description: We consider a piecewise linear, discontinuous Galerkin method for the time discretization of a fractional diffusion equation involving a parameter in the range –1 〈 α 〈 0. Our analysis shows that, for a time interval (0, T ) and a spatial domain , the uniform error in L ((0, T ); L 2 ( )) is of order k , where = min g (2, +α) and k denotes the maximum time step. Thus, if –1/2 ≤ α 〈 0, then we have optimal O( k 2 ) convergence, just as for the classical diffusion (heat) equation.

Description: We propose a mixed finite-element method for the motion of a strongly viscous, ideal and isentropic gas. At the boundary we impose a Navier slip condition such that the velocity equation can be posed in mixed form with the vorticity as an auxiliary variable. In this formulation we design a finite-element method, where the velocity and vorticity are approximated with the div- and curl-conforming Nédélec elements, respectively, of the first order and first kind. The mixed scheme is coupled to a standard piecewise constant upwind discontinuous Galerkin discretization of the continuity equation. For the time discretization implicit Euler time stepping is used. Our main result is that the numerical solution converges to a weak solution as the discretization parameters go to zero. The convergence analysis is inspired by the continuous analysis of Feireisl and Lions for the compressible Navier–Stokes equations. Tools used in the analysis include an equation for the effective viscous flux and various renormalizations of the density scheme.

Description: This paper aims to present a unified framework for deriving analytical formulas for smoothing factors in arbitrary dimensions, under certain simplifying assumptions. To derive these expressions we rely on complex analysis and geometric considerations, using the maximum modulus principle and Möbius transformations. We restrict our attention to pointwise and block lexicographic Gauss–Seidel smoothers on a d -dimensional uniform mesh, where the computational molecule of the associated discrete operator forms a (2 d +1)-point star. In the pointwise case, the effect of a relaxation parameter is analysed. Our results apply to any number of spatial dimensions and are applicable to high-dimensional versions of a few common model problems with constant coefficients, including the Poisson and anisotropic diffusion equations, as well as a special case of the convection–diffusion equation. We show that in most cases our formulas, exact under the simplifying assumptions of local Fourier analysis, form tight upper bounds for the asymptotic convergence of geometric multigrid in practice. We also show that there are asymmetric cases where lexicographic Gauss–Seidel smoothing outperforms red–black Gauss–Seidel smoothing; this occurs for certain model convection–diffusion equations with high mesh Reynolds numbers.

Description: We study the stability properties of, and the phase error present in, several higher-order (in space) staggered finite difference schemes for Maxwell's equations coupled with a Debye or Lorentz polarization model. We present a novel expansion of the finite difference approximations, of arbitrary (even) order, of the first-order spatial derivative operator. This alternative representation allows the derivation of a concise formula for the numerical dispersion relation for all even order schemes applied to each model, including the limiting (infinite-order) case. We further derive a closed-form analytical stability condition for these schemes as a function of the order of the method. Using representative numerical values for the physical parameters, we validate the stability criterion while quantifying numerical dissipation. Lastly, we demonstrate the effect that the spatial discretization order, and the corresponding stability constraint, has on the dispersion error.

Description: The aim of this paper is to analyse a numerical method to solve transient eddy current problems with input current intensities as data, formulated in terms of the magnetic field in a bounded domain including conductors and dielectrics. To this end, we introduce a time-dependent weak formulation and prove its well-posedness. We propose a finite element method for space discretization based on the Nédélec edge elements on tetrahedral meshes, for which we obtain error estimates. Then we introduce a backward Euler scheme for time discretization and prove error estimates for the fully discrete problem, too. Furthermore, a magnetic scalar potential is introduced to deal with the curl-free condition in the dielectric domain, which leads to an important saving in computational effort. Finally, the method is applied to solve two problems: a test with a known analytical solution and an application to electromagnetic forming.

Description: In this paper a quadrature method for Cauchy singular integral equations having constant coefficients and index equal to –1 is proposed. A polynomial approximation of the solution is constructed by solving a determined and well-conditioned linear system. Error estimates and numerical tests are also included.

Description: We introduce a novel technique for constructing higher-order variational integrators for Hamiltonian systems of ordinary differential equations. In the construction of the discrete Lagrangian we adopt Hermite interpolation polynomials and the Euler–Maclaurin quadrature formula and apply collocation to the Euler–Lagrange equation and its prolongation. Considerable attention is devoted to the order analysis of the resulting variational integrators in terms of approximation properties of the Hermite polynomials and quadrature errors. In particular, the order of the variational integrator can be computed a priori based on the quadrature error estimate. The analysis in the paper is straightforward compared to the order theory for Runge–Kutta methods. Finally, a performance comparison is presented on a selection of these integrators.

Description: Linear systems of equations Ax = b , where the matrix A has some particular structure, arise frequently in applications. Very often, structured matrices have huge condition numbers and, therefore, standard algorithms fail to compute accurate solutions of Ax = b . We say in this paper that a computed solution is accurate if being the unit roundoff. In this work we introduce a framework that allows many classes of structured linear systems to be solved accurately, independently of the condition number of A and efficiently, that is, with cost For most of these classes no algorithms are known that are both accurate and efficient. The approach in this work relies on first computing an accurate rank-revealing decomposition of A , an idea that has been widely used in the last decades to compute singular value and eigenvalue decompositions of structured matrices with high relative accuracy. In particular, we illustrate the new method by accurately solving Cauchy and Vandermonde linear systems with any distribution of nodes, that is, without requiring A to be totally positive for most right-hand sides b .

Description: This paper is concerned with a staggered discontinuous Galerkin method for the curl–curl operator arising from the time-harmonic Maxwell equations. One distinctive feature of the method is that the discrete operators preserve the properties of the differential operators. Moreover, the numerical solution automatically satisfies a discrete divergence-free condition. Stability and optimal convergence of the method are analysed. Numerical experiments for smooth and singular solutions are shown to verify the optimal order of convergence. Furthermore, the method is applied to the corresponding eigenvalue problem. Numerical results for rectangular and L-shaped domains show that our method is able to produce nonspurious eigenvalues.

Description: We propose a general framework that allows for a new natural coupling of boundary element and a wide class of finite element methods (FEMs) for a model second-order elliptic problem. This class of FEMs includes mixed methods, discontinuous Galerkin methods and the continuous Galerkin method. We provide sufficient conditions guaranteeing the well-posedness of the methods and give several examples that include new as well as old methods.

Description: The Lippmann–Schwinger integral equation describes the scattering of acoustic waves from an inhomogeneous medium. For scattering problems in free space, Vainikko proposed a fast spectral solution method exploiting the convolution structure of this equation's integral operator and the fast Fourier transform. Although the integral operator of the Lippmann–Schwinger integral equation for scattering in a planar three-dimensional waveguide is not a convolution, we show in this paper that the separable structure of the kernel allows to construct fast spectral collocation methods. The numerical analysis of this method requires smooth material parameters; for discontinuous materials there is no theoretical convergence statement. Therefore, we construct a Galerkin variant of Vainikko's method avoiding this drawback. For several distant scattering objects inside the three-dimensional waveguide this discretization technique would lead to a computational domain consisting of one large box containing all scatterers and hence many unnecessary unknowns. However, the integral equation can be reformulated as a coupled system with unknowns defined on the different parts of the scatterer. Discretizing this coupled system by a combined spectral/multipole approach yields an efficient method for waveguide scattering from multiple objects.

Description: The aim of this paper is to investigate the stability of time integration schemes for the solution of a finite element semi-discretization of a scalar convection–diffusion equation defined on a moving domain. An arbitrary Lagrangian–Eulerian formulation is used to reformulate the governing equation with respect to a moving reference frame. We devise an adaptive -method time integrator that is shown to be unconditionally stable and asymptotically second-order accurate for smoothly evolving meshes. An essential feature of the method is that it satisfies a discrete equivalent of the well-known geometric conservation law. Numerical experiments are presented to confirm the findings of the analysis.

Description: Stochastic collocation methods facilitate the numerical solution of partial differential equations (PDEs) with random data and give rise to long sequences of similar linear systems. When elliptic PDEs with random diffusion coefficients are discretized with mixed finite element methods in the physical domain we obtain saddle point systems. These are trivial to solve when considered individually; the challenge lies in exploiting their similarities to recycle information and minimize the cost of solving the entire sequence. We apply stochastic collocation to a model stochastic elliptic problem and discretize in physical space using Raviart–Thomas elements. We propose an efficient solution strategy for the resulting linear systems that is more robust than any other in the literature. In particular, we show that it is feasible to use finely-tuned algebraic multigrid preconditioning if key set-up information is reused. The proposed solver is robust with respect to variations in the discretization and statistical parameters for stochastically linear and nonlinear data.

Description: We address numerically the question of the asymptotic stability of equilibria for a Gurtin–MacCamy model with age-dependent spatial diffusion. The problem reduces to the study of a finite number of simpler models without diffusion, which are parametrized by the eigenvalues of the Laplacian operator. Here the approach in Breda et al. (2007, Stability analysis of age-structured population equations by pseudospectral differencing methods. J. Math. Biol. , 54 , 701–720; 2008, Stability analysis of the Gurtin–MacCamy model. SIAM J. Numer. Anal. , 46 , 980–995), which is based on pseudospectral methods, is adapted to the reduced models and the error analysis is revisited in order to prove the preservation of convergence of infinite order.

Description: The moving least squares (MLS) method provides an approximation û of a function u based solely on values u ( x j ) of u on scattered ‘meshless’ nodes x j . Derivatives of u are usually approximated by derivatives of û . In contrast to this, we directly estimate derivatives of u from the data, without any detour via derivatives of û . This is a generalized MLS technique, and we prove that it produces diffuse derivatives as introduced by Nyroles et al. (1992, Generalizing the finite element method: diffuse approximation and diffuse elements. Comput. Mech. , 10 , 307–318). Consequently, these turn out to be efficient direct estimates of the true derivatives, without anything ‘diffuse’ about them, and we prove optimal rates of convergence towards the true derivatives. Numerical examples confirm this, and we finally show how the use of shifted and scaled polynomials as basis functions in the generalized and standard MLS approximation stabilizes the algorithm.

Description: The differential linear variational inequality consists of a system of n ordinary differential equations (ODEs) and a parametric linear variational inequality as the constraint. The right-hand side function in the ODEs is not differentiable and cannot be evaluated exactly. Existing numerical methods provide only approximate solutions. In this paper we present a reliable error bound for an approximate solution x h ( t ) delivered by the time-stepping method, which takes all discretization and roundoff errors into account. In particular, we compute two trajectories x j h ( t )± j h ( t ) to determine the existence region of the exact solution for each . Moreover, we have . Numerical examples of bridge collapse, earthquake-induced structural pounding and circuit simulation are given to illustrate the efficiency of the error bound.

Description: We present a comprehensive convergence analysis for discontinuous piecewise polynomial approximations of a first-kind Volterra integral equation with smooth convolution kernel, examining the attainable order of (super-) convergence in collocation, quadrature discontinuous Galerkin (QDG) and full discontinuous Galerkin (DG) methods. We introduce new polynomial basis functions with properties that greatly simplify the convergence analysis for collocation methods. This also enables us to determine explicit formulae for the location of superconvergence points (i.e., discrete points at which the convergence order is one higher than the global bound) for all convergent collocation schemes. We show that a QDG method, which is based on piecewise polynomials of degree m and uses exactly m + 1 quadrature points and nonzero quadrature weights, is equivalent to a collocation scheme, and so its convergence properties are fully determined by the previous collocation analysis and they depend only on the quadrature point location (in particular, they are completely independent of the accuracy of the quadrature rule). We also give a complete analysis for QDG with more than m + 1 quadrature points when the degree of precision (d.o.p.) is at least 2 m + 1. The behaviour (but not the approximation) is the same as that for a DG scheme when the d.o.p. is at least 2 m + 2. Numerical test results confirm that the theoretical convergence rates are optimal.

Description: The contact between two membranes can be described by a system of variational inequalities, where the unknowns are the displacements of the membranes and the action of a membrane on the other one. A discretization of this system is proposed in Part 1 of this work, where the displacements are approximated by standard finite elements and the action by a local postprocessing, which admits an equivalent mixed reformulation. Here we perform the a posteriori analysis of this discretization and prove optimal error estimates. Then we present numerical experiments that confirm the efficiency of the error indicators.

Description: In this paper we design high-order accurate and stable finite difference schemes for the initial–boundary–value problem associated with the magnetic induction equation with resistivity. We use summation-by-parts finite difference operators to approximate spatial derivatives and a simultaneous approximation term technique for implementing boundary conditions. The resulting schemes are shown to be energy stable. Various numerical experiments demonstrating both the stability and the high order of accuracy of the schemes are presented.

Description: Time-stepping procedures for the solution of evolution equations can be performed on parallel architecture by parallelizing the space computation at each time step. This, however, requires heavy communication between processors and becomes inefficient when many time steps are to be computed and many processors are available. In such cases parallelization in time is advantageous. In this paper we present a method for parallelization in time of linear multistep discretizations of linear evolution problems; we consider a model parabolic problem and a model hyperbolic problem and their, respectively, A ()-stable and A -stable linear multistep discretizations. The method consists of a discrete decoupling procedure, whereby N +1 decoupled Helmholtz problems with complex frequencies are obtained; N being the number of time steps computed in parallel. The usefulness of the method rests on our ability to solve these Helmholtz problems efficiently. We discuss the theory and give numerical examples for multigrid preconditioned iterative solvers of relevant complex frequency Helmholtz problems. The parallel approach can easily be combined with a time-stepping procedure, thereby obtaining a block time-stepping method where each block of steps is computed in parallel. In this way we are able to optimize the algorithm with respect to the number of processors available, the difficulty of solving the Helmholtz problems and the possibility of both time and space adaptivity. Extensions to other linear evolution problems and to Runge–Kutta time discretization are briefly mentioned.

Description: We consider two algorithms to approximate the solution Z of a class of stable operator Lyapunov equations of the form AZ + ZA * + BB * = 0. The algorithms utilize time snapshots of solutions of certain linear infinite-dimensional differential equations to construct the approximations. Matrix approximations of the operators A and B are not required and the algorithms are applicable as long as the rank of B is relatively small. The first algorithm produces an optimal low-rank approximate solution using proper orthogonal decomposition. The second algorithm approximates the product of the solution with a few vectors and can be implemented with a minimal amount of storage. Both algorithms are known for the matrix case. However, the extension of the algorithms to infinite dimensions appears to be new. We establish easily verifiable convergence theory and a priori error bounds for both algorithms and present numerical results for two model problems.

Description: We study several discontinuous Galerkin methods for solving the Signorini problem. A unified error analysis is provided for the methods. The error estimates are of optimal order for linear elements. A numerical example is reported to illustrate numerical convergence orders.

Description: This paper considers the stability of both continuous and discrete time-varying linear systems. Stability estimates are obtained in either case in terms of the Lipschitz constant for the governing matrices and the assumed uniform decay rate of the corresponding frozen time linear systems. The main techniques used in the analysis are comparison methods, scaling and the application of continuous stability estimates to the discrete case. Counterexamples are presented to show the necessity of the stability hypotheses. The discrete results are applied to derive sufficient conditions for the stability of a backward Euler approximation of a time-varying system and a one-leg linear multistep approximation of a scalar system.

Description: The classical error analysis for Nédélec edge interpolation requires the so-called regularity assumption on the elements. However, in Nicaise (2001, SIAM J. Numer. Anal. , 39 , 784–816) optimal error estimates were obtained for the lowest order case under the weaker hypothesis of the maximum angle condition. This assumption allows for anisotropic meshes that become useful, for example, for the approximation of solutions with edge singularities. In this paper we prove optimal error estimates for the edge interpolation of any order under the maximum angle condition. We also obtain sharp stability results for that interpolation on appropriate families of elements. mixed finite elements; edge elements; anisotropic finite elements.

Description: This paper deals with a fluid–solid interaction problem inspired by a biomechanical brain model. The problem consists of determining the response to prescribed static forces of an elastic solid containing a barotropic and inviscid fluid at rest. The solid is described by means of displacement variables, whereas displacement potential and pressure are used for the fluid. This approach leads to a well-posed symmetric mixed problem, which is discretized by standard Lagrangian finite elements of arbitrary order for all the variables. Optimal-order error estimates in the H 1 - and L 2 -norms are proved for this method. A residual a posteriori error estimator is also proposed, for which efficiency and reliability estimates are proved. Finally, some numerical tests are reported to assess the performance of the method and that of an adaptive scheme based on the error estimator.

Description: A numerical method of second order of accuracy for computing conditional Wiener integrals of smooth functionals of a general form is proposed. The method is based on the simulation of a Brownian bridge via the corresponding stochastic differential equations (SDEs) and on ideas of the weak-sense numerical integration of SDEs. A convergence theorem is proved. Special attention is paid to integral-type functionals. A generalization to the case of pinned diffusions is considered. Results of some numerical experiments are presented.

Description: In this paper we utilize affine biquadratic elements and a two-step temporal discretization to develop a finite volume element method for parabolic problems on quadrilateral meshes. The method is proved to have an optimal order convergence rate in L 2 (0, T ; H 1 ()) under the ‘asymptotically parallelogram’ mesh assumption. Numerical experiments that corroborate the theoretical analysis are also presented.

Description: An error analysis is given for a discretization of the Gross–Pitaevskii equation by Strang splitting in time and Hermite collocation in space. A second-order error bound in L 2 for the semidiscretization error of the Strang splitting in time is proven under suitable regularity assumptions on the exact solution. For the semidiscretization in space, high-order convergence is shown, depending on the regularity of the exact solution. The analyses of the semidiscretizations in time and space are finally combined into an error analysis of the fully discrete method.

Description: In this paper we consider the finite-volume-element method for general second-order quasilinear elliptic problems over a convex polygonal domain in the plane. Using reasonable assumptions, we show the existence and uniqueness of the finite-volume-element approximations. It is proved that the finite-volume-element approximations are convergent with , where r 〉 2, and in the H 1 -, W 1, - and L 2 -norms, respectively, for u W 2, r () and u W 2, () W 3, p (), where p 〉 1. Moreover, the optimal-order error estimates in the W 1, - and L 2 -norms and an estimate in the L -norm are derived under the assumption that u W 2, () H 3 (). Numerical experiments are presented to confirm the estimates.

Description: We present guaranteed , robust and computable a posteriori error estimates for nonconforming approximations of elliptic problems. Our analysis is based on a Helmholtz-type decomposition of the error expressed in terms of fluxes. Such a decomposition results in a gradient term and a divergence-free term, that are the exact solutions of two auxiliary problems. We suggest a new approach to deriving computable two-sided bounds of the norms of these solutions. The a posteriori estimates obtained in this paper differ from those that are based on projections of nonconforming approximations to a conforming space. Numerical experiments confirm that these new estimates provide very accurate error bounds, and can be efficiently exploited in practical computations.

Description: The numerical solution for a class of sub-diffusion equations involving a parameter in the range – 1 〈 α 〈 0 is studied. For the time discretization, we use an implicit finite-difference Crank–Nicolson method and show that the error is of order k 2+ α , where k denotes the maximum time step. A nonuniform time step is employed to compensate for the singular behaviour of the exact solution at t = 0. We also consider a fully discrete scheme obtained by applying linear finite elements in space to the proposed time-stepping scheme. We prove that the additional error is of order h 2 max(1, log k –1 ), where h is the parameter for the space mesh. Numerical experiments on some sample problems demonstrate our theoretical result.

Description: The inf–sup stability and optimal convergence of an isogeometric C 1 discretization for the Stokes problem are shown. In this discretization the velocities are the pushforward through the geometrical map of cubic C 1 non-uniform rational B-spline (NURBS) functions and the pressures are the pushforward of quadratic C 1 NURBS. This paper follows the work in Bazilevs et al. (2006, Math. Models Methods Appl. Sci. , 16 , 1031–1090) where the authors showed the numerical result of this discretization and proved the inf–sup stability for C 0 NURBS functions. The use of more regular functions is useful to decrease the degrees of freedom and thus the computational cost. The analysis is performed by means of the Verfürth trick, the macro-element technique, some approximation properties and the inf–sup condition for tensor products of B-spline spaces.

Description: The question in the title is answered using tools of potential theory. Convergence and divergence rates of interpolants of analytic functions on the unit interval are analysed. The starting point is a complex variable contour integral formula for the remainder in radial basis function (RBF) interpolation. We study a generalized Runge phenomenon and explore how the location of centres affects convergence. Special attention is given to Gaussian and inverse quadratic radial functions, but some of the results can be extended to other smooth basis functions. Among other things, we prove that, under mild conditions, inverse quadratic RBF interpolants of functions that are analytic inside the strip |Im ( z )| 〈 (1/2 ), where is the shape parameter, converge exponentially.

Description: We address in this paper the approximation of functions in an equilateral triangle by a linear combination of Laplace–Neumann eigenfunctions. The Laplace–Neumann basis exhibits a number of advantages. The approximations converge fairly fast and their speed of convergence can be much improved by using techniques familiar in Fourier analysis and spectral methods, in particular, the hyperbolic cross and polynomial subtraction. Moreover, expansion coefficients can be computed rapidly by a mixture of asymptotic methods and Birkhoff–Hermite quadratures.

Description: This paper analyses a globalized inexact smoothing Newton method for the numerical solution of optimal control problems subject to mixed control-state constraints. The method uses the smoothed Fischer–Burmeister function to reformulate first-order necessary conditions and aims at minimizing the squared residual norm using Newton steps and gradient-like steps. Numerical experiments are provided to illustrate the convergence results.

Description: Perhaps, the most astonishing idea in eigenvalue computation is Rutishauser's idea of applying the LR transform to a matrix for generating a sequence of similar matrices that become more and more triangular. The same idea is the foundation of the ubiquitous QR algorithm. It is well known that this idea originated in Rutishauser's qd algorithm, which precedes the LR algorithm and can be understood as applying LR to a tridiagonal matrix. But how did Rutishauser discover qd and when did he find the qd–LR connection? We checked some of the early sources and have come up with an explanation.

Description: In this article we prove the convergence of adaptive finite-element methods for Steklov eigenvalue problems under very general assumptions for simple as well as multiple eigenvalues starting from any initial triangulation. We also prove the optimality of the approximations, assuming Dörfler's strategy for marking when we consider simple eigenvalues.

Description: We propose, analyse and demonstrate a discontinuous Galerkin method for fractal conservation laws. Various stability estimates are established along with error estimates for regular solutions of linear equations. Moreover, in the nonlinear case and whenever piecewise constant elements are utilized, we prove a rate of convergence towards the unique entropy solution. We present numerical results for different types of solutions of linear and nonlinear fractal conservation laws.

Description: In this paper we discuss a numerical solution of the delay differential equation where a , b != 0 are complex numbers, 0 〈 q 〈 1 is a real number and f is a complex-valued function satisfying as t -〉 for a suitable real scalar β . After a brief review of the equation’s basic stability and asymptotic properties, we analyse these characteristics for its -methods discretizations. Doing this, we consider meshes with a constant step size and a variable step size proposed by other authors for theoretical as well as computational reasons. Further, we discuss the consequences of our results for numerical investigations of the pantograph equation, especially with respect to a possible correspondence between the asymptotics of exact and numerical solutions. Some illustrating examples and calculations conclude the paper.

Description: This paper is concerned with the cyclic block coordinate descent method, also known as the nonlinear Gauss–Seidel (GS) method, where the solution of an optimization problem is achieved by partitioning the variables in blocks and successively minimizing with respect to each block. The properties of the objective function that guarantee the convergence of such alternating scheme have been widely investigated in the literature and it is well known that without suitable convexity hypotheses, the method may fail to locate the stationary points when more than two blocks of variables are employed. In this paper the general constrained nonconvex case is considered, presenting three contributions. First, a general method allowing an approximate solution of each block minimization subproblem is devised and the related convergence analysis is developed, showing that the proposed inexact method has the same convergence properties as the standard nonlinear GS method. Then a cyclic block gradient projection method is analysed, proving that it leads to stationary points for every number of blocks. Finally, the cyclic block gradient method is applied to large-scale problems arising from the non-negative matrix factorization approach. The results of a numerical experimentation on image recognition problems are also reported.

Description: This paper deals with a finite element approximation of the vibration modes of fluid–structure systems coupled on curved interfaces. It is based on a displacement formulation for both the fluid and the solid. Lowest order Raviart–Thomas elements are used for the fluid and standard continuous linear elements for the solid. Compatibility conditions are weakly imposed at a polygonal approximation of the fluid–solid interface by means of a Lagrange multiplier. Convergence, nonexistence of spurious or circulation nonzero frequency modes and optimal order error estimates for eigenfunctions/eigenvalues are proved. To do this, we use recent results about spectral approximations for noncompact operators to nonconforming hybrid finite element methods. The validity of a discrete compactness property for the discrete spaces considered here is also discussed.

Description: The Lavrentiev gap phenomenon is a well-known effect in the calculus of variations, related to singularities of minimizers. In its presence, conforming finite-element methods are incapable of reaching the energy minimum. By contrast, it is shown in this work that for convex variational problems the nonconforming Crouzeix–Raviart finite-element discretization always converges to the correct minimizer and that the discrete energy converges to the correct limit.

Description: We derive a variational characterization of the exact discrete Hamiltonian, which is a Type II generating function for the exact flow of a Hamiltonian system, by considering a Legendre transformation of Jacobi’s solution of the Hamilton–Jacobi equation. This provides an exact correspondence between continuous and discrete Hamiltonian mechanics, which arise from the continuous- and discrete-time Hamilton’s variational principle on phase space, respectively. The variational characterization of the exact discrete Hamiltonian naturally leads to a class of generalized Galerkin Hamiltonian variational integrators that includes the symplectic partitioned Runge–Kutta methods. This extends the framework of variational integrators to Hamiltonian systems with degenerate Hamiltonians, for which the standard theory of Lagrangian variational integrators cannot be applied. We also characterize the group invariance properties of discrete Hamiltonians that lead to a discrete Noether’s theorem.

Description: We propose a numerical method for computing transport and diffusion on a moving surface. The approach is based on a diffuse interface model in which a bulk diffusion–advection equation is solved on a layer of thickness containing the surface. The conserved quantity in the bulk domain is the concentration weighted by a density which vanishes on the boundary of the thin domain. Such a density arises naturally in double obstacle phase field models. The discrete equations are then formulated on a moving narrow band consisting of grid points on a fixed mesh. We show that the discrete equations are solvable subject to a natural constraint on the evolution of the discrete narrow band. Mass is conserved and the discrete solution satisfies stability bounds. Numerical experiments indicate that the method is second-order accurate in space.

Description: We prove a priori error estimates for a family of Eulerian–Lagrangian methods for time-dependent convection–diffusion equations with degenerate diffusion. The estimates depend only on certain Sobolev norms of the initial and right side data of the problem but not on the lower bound of the diffusion or any norms of the true solution. Thus these estimates hold uniformly with respect to the degenerate diffusion. On a general unstructured mesh, these estimates are suboptimal but sharp when the Courant number is less than unity and are optimal otherwise. We further prove an optimal-order error estimate and a superconvergence estimate for a special case of d -linear approximations on a d -dimensional rectangular domain with a uniform rectangular partition. We then use the interpolation of spaces and stability estimates to derive an estimate for problems with minimal or intermediate regularity, where the convergence rates are proportional to certain Besov norms of the initial and right side data. Numerical experiments are presented to confirm the theoretical results.

Description: We analyse the adaptive finite-element approximation to solutions of partial differential equations in variational formulation. Assuming well-posedness of the continuous problem and requiring only basic properties of the adaptive algorithm, we prove convergence of the sequence of discrete solutions to the true one. The proof is based on the ideas by Morin, Siebert and Veeser but replaces local efficiency of the estimator by a local density property of the adaptively generated finite-element spaces. As a result, estimators without a discrete lower bound are also included in our theory. The assumptions of the presented framework are fulfilled by a large class of important applications, estimators and adaptive strategies.

Description: Methods for the numerical evaluation of the Weber parabolic cylinder functions W ( a , ± x ), which are independent solutions of the inverted harmonic oscillator y '' + ( x 2 /4 – a ) y = 0, are described. The functions appear in the solution of many physical problems and notably in quantum mechanics. It is shown that the combined use of Maclaurin series, Chebyshev series, uniform asymptotic expansions for large a and/or x and the integration of the differential equation by local Taylor series are enough for computing the functions accurately in a wide rage of parameters. Differently from previous methods, the computational scheme is stable in the sense that high accuracy is retained: only two or three digits may be lost in double precision computations.

Description: Higham (2002, IMA J. Numer. Anal. , 22 , 329–343) considered two types of nearest correlation matrix problems, namely the W -weighted case and the H -weighted case. While the W -weighted case has since been well studied to make several Lagrangian dual-based efficient numerical methods available, the H -weighted case remains numerically challenging. The difficulty of extending those methods from the W -weighted case to the H -weighted case lies in the fact that an analytic formula for the metric projection onto the positive semidefinite cone under the H -weight, unlike the case under the W -weight, is not available. In this paper we introduce an augmented Lagrangian dual-based approach that avoids the explicit computation of the metric projection under the H -weight. This method solves a sequence of unconstrained convex optimization problems, each of which can be efficiently solved by an inexact semismooth Newton method combined with the conjugate gradient method. Numerical experiments demonstrate that the augmented Lagrangian dual approach is not only fast but also robust.

Description: This work is devoted to obtaining optimal error estimates (for the velocity and the pressure) for a first-order time-discrete splitting scheme (using decomposition of the viscosity) for solving the incompressible time-dependent Navier–Stokes equations in three-dimensional domains. This scheme has been previously studied by other authors (Blasco et al. 1997 Int. J. Numer. Methods Fluids , 28 , 1391–1419; Blasco & Codina, 2004, Appl. Numer. Math. , 51 , 1–17), but the main novelty of this paper is to establish optimal error estimates for the pressure. This behaviour has been numerically observed, but never hitherto proved. Moreover, owing to the introduction of a weight for the initial steps, these optimal error estimates are obtained without imposing either constraints on the time step or global compatibility conditions for the pressure at the initial time (related to further regularity hypotheses on the exact solution).

Description: An initial boundary-value problem for a semilinear reaction–diffusion equation is considered. Its diffusion parameter 2 is arbitrarily small, which induces initial and boundary layers. It is shown that the conventional implicit method might produce incorrect computed solutions on uniform meshes. Therefore we propose a stabilized method that yields a unique qualitatively correct solution on any mesh. Constructing discrete upper and lower solutions, we prove existence and investigate the accuracy of discrete solutions on layer-adapted meshes of Bakhvalov and Shishkin types. It is established that the two considered methods enjoy second-order convergence in space and first-order convergence in time (with, in the case of the Shishkin mesh, a logarithmic factor) in the maximum norm, if ≤ C ( N –1 + M –1/2 ), where N and M are the numbers of mesh intervals in the space and time directions, respectively. Numerical results are presented that support the theoretical conclusions.

Description: In this paper we study an accuracy-increasing postprocessing technique for full discretizations of nonlinear convection–diffusion problems. The spatial discretization is based on finite elements. Once the fully discrete standard Galerkin approximation is computed at any fixed time, a discrete stationary convection–diffusion problem with data based on the Galerkin approximation is solved. The semidiscrete in space case was first considered in de Frutos, García-Archilla and Novo (2009, IMA J. Numer. Anal. , 30, 2010, 1137–1158). A posteriori error estimates, based on this postprocessing technique, are obtained both for the semidiscrete in space and for the fully discrete cases. We prove that the semidiscrete error estimator proposed in this paper is efficient and asymptotically exact. In the fully discrete case the estimates have the property of giving a measure of the spatial errors that is independent of temporal errors. Some numerical experiments are provided.

Description: We consider a Clenshaw–Curtis–Filon-type method for highly oscillatory Bessel transforms. It is based on a special Hermite interpolation polynomial at the Clenshaw–Curtis points that can be efficiently evaluated using $$\hbox{ O }\left(NlogN\right)$$ operations, where N is the number of Clenshaw–Curtis points in the interval of integration. Moreover, we derive corresponding error bounds in terms of the frequency and the approximating polynomial. We then show that this method yields an efficient numerical approximation scheme for a class of Volterra integral equations containing highly oscillatory Bessel kernels (a problem for which standard numerical methods fail), and it also allows the study of the asymptotics of the solutions. Numerical examples are used to illustrate the efficiency and accuracy of the Clenshaw–Curtis–Filon-type method for approximating these highly oscillatory integrals and integral equations.

Description: We study the numerical approximation to the solution of the steady convection–diffusion equation. The diffusion term is discretized by using the hybrid mimetic method (HMM), which is the unified formulation for the hybrid finite-volume (FV) method, the mixed FV method and the mimetic finite-difference method recently proposed in Droniou et al. (2010, Math. Models Methods Appl. Sci. , 20 , 265–295). In such a setting we discuss several techniques to discretize the convection term that are mainly adapted from the literature on FV or FV schemes. For this family of schemes we provide a full proof of convergence under very general regularity conditions of the solution field and derive an error estimate when the scalar solution is in H 2 (). Finally, we compare the performance of these schemes on a set of test cases selected from the literature in order to document the accuracy of the numerical approximation in both diffusion- and convection-dominated regimes. Moreover, we numerically investigate the behaviour of these methods in the approximation of solutions with boundary layers or internal regions with strong gradients.