Superconvergent error estimates for a class of discretization methods for a coupled first‐order system with discontinuous coefficients

Lithological discontinuities in a reservoir generate discontinuous coefficients for the first‐order system of equations used in the simulation of fluid flow in porous media. Systems of conservation laws with discontinuous coefficients also arise in many other physical applications. In this article, we present a class of discretization schemes that include variants of mixed finite element methods, finite volume element methods, and cell‐centered finite difference equations as special cases. Error estimates of the order O(h²) in certain discrete L²‐norms are established for both the primary independent variable and its flux, even in the presence of discontinuous coefficients in the flux term. © 1999 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 15: 267–283, 1999     

Locally Supported,Piecewise Polynomial Biorthogonal Wavelets on Nonuniform Meshes

In this paper, biorthogonal wavelets are constructed on nonuniform meshes. Both primal and dual wavelets are locally supported, continuous piecewise polynomials. The wavelets generate Riesz bases for the Sobolev spaces (H^s) for (|s| < 3/2). The wavelets at the primal side span standard Lagrange finite element spaces.     

Convergence analysis of the LDG method applied to singularly perturbed problems

Considering a two‐dimensional singularly perturbed convection–diffusion problem with exponential boundary layers, we analyze the local discontinuous Galerkin (DG) method that uses piecewise bilinear polynomials on Shishkin mesh. A convergence rate O(N^‐1 lnN) in a DG‐norm is established under the regularity assumptions, while the total number of mesh points is O(N²). The rate of convergence is uniformly valid with respect to the singular perturbation parameter ε. Numerical experiments indicate that the theoretical error estimate is sharp. © 2012 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2013     

Goal-oriented r-adaptivity based on the evaluation of the physical and material residual

This contribution is concerned with goal–oriented r-adaptivity based on energy minimization principles for the primal and the dual problem. We obtain a material residual of the primal and of the dual problem, which are indicators for non–optimal finite element meshes. For goal–oriented r-adaptivity we have to optimize the mesh with respect to the dual solution, because the error of a local quantity of interest depends on the error in the corresponding dual solution. We use the material residual of the primal and dual problem in order to obtain a procedure for mesh optimization with respect to a local quantity of interest. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Largest dual ellipsoids inscribed in dual cones

Suppose x? and s? lie in the interiors of a cone K and its dual K ^*, respectively. We seek dual ellipsoidal norms such that the product of the radii of the largest inscribed balls centered at x? and s? and inscribed in K and K ^*, respectively, is maximized. Here the balls are defined using the two dual norms. When the cones are symmetric, that is self-dual and homogeneous, the solution arises directly from the Nesterov–Todd primal–dual scaling. This shows a desirable geometric property of this scaling in symmetric cone programming, namely that it induces primal/dual norms that maximize the product of the distances to the boundaries of the cones.     

The multipliers‐free domain decomposition methods

This article concludes the development and summarizes a new approach to dual‐primal domain decomposition methods (DDM), generally referred to as “the multipliers‐free dual‐primal method.” Contrary to standard approaches, these new dual‐primal methods are formulated without recourse to Lagrange‐multipliers. In this manner, simple and unified matrix‐expressions, which include the most important dual‐primal methods that exist at present are obtained, which can be effectively applied to floating subdomains, as well. The derivation of such general matrix‐formulas is independent of the partial differential equations that originate them and of the number of dimensions of the problem. This yields robust and easy‐to‐construct computer codes. In particular, 2D codes can be easily transformed into 3D codes. The systematic use of the average and jump matrices, which are introduced in this approach as generalizations of the “average” and “jump” of a function, can be effectively applied not only at internal‐boundary‐nodes but also at edges and corners. Their use yields significant advantages because of their superior algebraic and computational properties. Furthermore, it is shown that some well‐known difficulties that occur when primal nodes are introduced are efficiently handled by the multipliers‐free dual‐primal method. The concept of the Steklov–Poincaré operator for matrices is revised by our theory and a new version of it, which has clear advantages over standard definitions, is given. Extensive numerical experiments that confirm the efficiency of the multipliers‐free dual‐primal methods are also reported here. © 2009 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2010     

A Newton Method for Linear Programming

A fast Newton method is proposed for solving linear programs with a very large (10⁶) number of constraints and a moderate (10²) number of variables. Such linear programs occur in data mining and machine learning. The proposed method is based on the apparently overlooked fact that the dual of an asymptotic exterior penalty formulation of a linear program provides an exact least 2-norm solution to the dual of the linear program for finite values of the penalty parameter but not for the primal linear program. Solving the dual problem for a finite value of the penalty parameter yields an exact least 2-norm solution to the dual, but not a primal solution unless the parameter approaches zero. However, the exact least 2-norm solution to the dual problem can be used to generate an accurate primal solution if mn and the primal solution is unique. Utilizing these facts, a fast globally convergent finitely terminating Newton method is proposed. A simple prototype of the method is given in eleven lines of MATLAB code. Encouraging computational results are presented such as the solution of a linear program with two million constraints that could not be solved by CPLEX 6.5 on the same machine.     

A probabilistic analysis of a measure of combinatorial complexity for the central curve

We investigate certain combinatorial properties of the central curve associated with interior point methods for linear optimization. We define a measure of complexity for the curve in terms of the number of turns, or changes of direction, that it makes in a geometric sense, and then perform an average case analysis of this measure for P-matrix linear complementarity problems. We show that the expected number of nondegenerate turns taken by the central curve is bounded by n ²-n, where the expectation is taken with respect to a sign-invariant probability distribution on the problem data. As an alternative measure of complexity, we also consider the number of times the central curve intersects with a wide class of algebraic hypersurfaces, including such objects as spheres and boxes. As an example of the results obtained, we show that the primal and dual variables in each coordinate of the central curve cross each other at most once, on average. As a further example, we show that the central curve intersects any sphere centered at the origin at most twice, on average. Received May 28, 1998 / Revised version received October 12, 1999?Published online December 15, 1999     

Error estimate in L2 of a covolume method for the generalized Stokes problem

We investigate an L²‐error estimate of a covolume scheme for the Stokes problem recently introduced by Chou (Math Comp 66 (1997), 85–104). We show the error in L² norm is of second order provided the exact velocity is in H ³ and the exact pressure is in H². © 2005 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2006     

An expanded mixed covolume method for sobolev equation with convection term on triangular grids

The expanded mixed covolume method for the two‐dimensional Sobolev equation with convection term is developed and studied. This method uses the lowest‐order Raviart‐Thomas mixed finite element space as the trial function space. By introducing a transfer operator γ_h which maps the trial function space into the test function space and combining expanded mixed finite element with mixed covolume method, the continuous‐in‐time, discrete‐in‐time expanded mixed covolume schemes are constructed, and optimal error estimates for these schemes are obtained. Numerical results are given to examine the validity and effectiveness of the proposed schemes.© 2012 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2013     

Lp error estimates and superconvergence for covolume or finite volume element methods

We consider convergence of the covolume or finite volume element solution to linear elliptic and parabolic problems. Error estimates and superconvergence results in the L^p norm, 2 ≤ p ≤ ∞, are derived. We also show second‐order convergence in the L^p norm between the covolume and the corresponding finite element solutions and between their gradients. The main tools used in this article are an extension of the “supercloseness” results in Chou and Li [Math Comp 69(229) (2000), 103–120] to the L^p based spaces, duality arguments, and the discrete Green's function method. © 2003 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 19: 463–486, 2003     

On MAC schemes on triangular delaunay meshes,their convergence and application to coupled flow problems

We study the convergence of two generalized marker‐and‐cell covolume schemes for the incompressible Stokes and Navier–Stokes equations introduced by Cavendish, Hall, Nicolaides, and Porsching. The schemes are defined on unstructured triangular Delaunay meshes and exploit the Delaunay–Voronoi duality. The study is motivated by the fact that the related discrete incompressibility condition allows to obtain a discrete maximum principle for the finite volume solution of an advection–diffusion problem coupled to the flow. The convergence theory uses discrete functional analysis and compactness arguments based on recent results for finite volume discretizations for the biharmonic equation. For both schemes, we prove the strong convergence in L² for the velocities and the discrete rotations of the velocities for the Stokes and the Navier–Stokes problem. Further, for one of the schemes, we also prove the strong convergence of the pressure in L². These predictions are confirmed by numerical examples presented in the article. © 2014 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 30: 1397–1424, 2014     

Stability of a combined finite element ‐ finite volume discretization of convection‐diffusion equations

We consider a time‐dependent and a stationary convection‐diffusion equation. These equations are approximated by a combined finite element – finite volume method: the diffusion term is discretized by Crouzeix‐Raviart piecewise linear finite elements on a triangular grid, and the convection term by upwind barycentric finite volumes. In the nonstationary case, we use an implicit Euler approach for time discretization. This scheme is shown to be L²‐stable uniformly with respect to the diffusion coefficient. In addition, it turns out that stability is unconditional in the time‐dependent case. These results hold if the underlying grid satisfies a condition that is fulfilled, for example, by some structured meshes. © 2012 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 28: 402–424, 2012     

An Error Analysis of Discontinuous Finite Element Methods for the Optimal Control Problems Governed by Stokes Equation

In this article, an abstract framework for the error analysis of discontinuous finite element method is developed for the distributed and Neumann boundary control problems governed by the stationary Stokes equation with control constraints. A priori error estimates of optimal order are derived for velocity and pressure in the energy norm and the L²-norm, respectively. Moreover, a reliable and efficient a posteriori error estimator is derived. The results are applicable to a variety of problems just under the minimal regularity possessed by the well-posedness of the problem. In particular, we consider the abstract results with suitable stable pairs of velocity and pressure spaces like as the lowest-order Crouzeix–Raviart finite element and piecewise constant spaces, piecewise linear and constant finite element spaces. The theoretical results are illustrated by the numerical experiments.     

A layer adaptive B‐spline collocation method for singularly perturbed one‐dimensional parabolic problem with a boundary turning point

In this article, we develop a parameter uniform numerical method for a class of singularly perturbed parabolic equations with a multiple boundary turning point on a rectangular domain. The coefficient of the first derivative with respect to x is given by the formula a₀(x, t)x^p, where a₀(x, t) ≥ α > 0 and the parameter p ∈ [1,∞) takes the arbitrary value. For small values of the parameter ε, the solution of this particular class of problem exhibits the parabolic boundary layer in a neighborhood of the boundary x = 0 of the domain. We use the implicit Euler method to discretize the temporal variable on uniform mesh and a B‐spline collocation method defined on piecewise uniform Shishkin mesh to discretize the spatial variable. Asymptotic bounds for the derivatives of the solution are established by decomposing the solution into smooth and singular component. These bounds are applied in the convergence analysis of the proposed scheme on Shishkin mesh. The resulting method is boundary layer resolving and has been shown almost second‐order accurate in space and first‐order accurate in time. It is also shown that the proposed method is uniformly convergent with respect to the singular perturbation parameter ε. Some numerical results are given to confirm the predicted theory and comparison of numerical results made with a scheme consisting of a standard upwind finite difference operator on a piecewise uniform Shishkin mesh. © 2010 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 27: 1143–1164, 2011     

Analysis of an augmented mixed‐primal formulation for the stationary Boussinesq problem

In this article, we propose and analyze a new mixed variational formulation for the stationary Boussinesq problem. Our method, which uses a technique previously applied to the Navier–Stokes equations, is based first on the introduction of a modified pseudostress tensor depending nonlinearly on the velocity through the respective convective term. Next, the pressure is eliminated, and an augmented approach for the fluid flow, which incorporates Galerkin‐type terms arising from the constitutive and equilibrium equations, and from the Dirichlet boundary condition, is coupled with a primal‐mixed scheme for the main equation modeling the temperature. In this way, the only unknowns of the resulting formulation are given by the aforementioned nonlinear pseudostress, the velocity, the temperature, and the normal derivative of the latter on the boundary. An equivalent fixed‐point setting is then introduced and the corresponding classical Banach Theorem, combined with the Lax–Milgram Theorem and the Babu?ka–Brezzi theory, are applied to prove the unique solvability of the continuous problem. In turn, the Brouwer and the Banach fixed‐point theorems are used to establish existence and uniqueness of solution, respectively, of the associated Galerkin scheme. In particular, Raviart–Thomas spaces of order k for the pseudostress, continuous piecewise polynomials of degree ≤ k+1 for the velocity and the temperature, and piecewise polynomials of degree ≤ k for the boundary unknown become feasible choices. Finally, we derive optimal a priori error estimates, and provide several numerical results illustrating the good performance of the augmented mixed‐primal finite element method and confirming the theoretical rates of convergence. © 2015 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 32: 445–478, 2016     

Analysis and convergence of a MAC-like scheme for the generalized Stokes problem

We introduce a MAC-like scheme (a covolume method on rectangular grids) for approximating the generalized Stokes problem on an axiparallel domain. Two staggered grids are used in the derivation of the discretization. The velocity is approximated by conforming bilinears over rectangular elements, and the pressure by piecewise constants over macro-rectangular elements. The error in the velocity in the H¹ norm and the pressure in the L² norm are shown to be of first order, provided that the exact velocity is in H² and the exact pressure in H¹, and that the partition family of the domain is regular. © 1997 John Wiley & Sons, Inc.     

Convergence analysis of a balancing domain decomposition method for solving a class of indefinite linear systems

A variant of balancing domain decomposition method by constraints (BDDC) is proposed for solving a class of indefinite systems of linear equations of the form (K?σ²M)u=f, which arise from solving eigenvalue problems when an inverse shifted method is used and also from the finite element discretization of Helmholtz equations. Here, both K and M are symmetric positive definite. The proposed BDDC method is closely related to the previous dual–primal finite element tearing and interconnecting method (FETI‐DP) for solving this type of problems (Appl. Numer. Math. 2005; 54 :150–166), where a coarse level problem containing certain free‐space solutions of the inherent homogeneous partial differential equation is used in the algorithm to accelerate the convergence. Under the condition that the diameters of the subdomains are small enough, the convergence rate of the proposed algorithm is established, which depends polylogarithmically on the dimension of the individual subdomain problems and which improves with a decrease of the subdomain diameters. These results are supported by numerical experiments of solving a two‐dimensional problem. Copyright © 2009 John Wiley & Sons, Ltd.     

Multi-Duality in Minimal Surface—Type Problems

The multi-duality of the nonlinear variational problem inf J(u, Λu) is studied for minimal surfaces-type problems. By using the method developed by Gao and Strang [1], the Fenchel-Rockafellar's duality theory is generalized to the problems with affine operator Λ. Two dual variational principles are established for nonparametric surfaces with constant mean curvature. We show that for the same primal problem, there may exist different dual problems. The primal problem may or may not possess a solution, whereas each dual problem possesses a unique solution. An evolutionary method for solving the nonlinear optimal-shape design problem is presented with numerical results.     

Success Guarantee of Dual Search in Integer Programming: p-th Power Lagrangian Method

Although the Lagrangian method is a powerful dual search approach in integer programming, it often fails to identify an optimal solution of the primal problem. The p-th power Lagrangian method developed in this paper offers a success guarantee for the dual search in generating an optimal solution of the primal integer programming problem in an equivalent setting via two key transformations. One other prominent feature of the p-th power Lagrangian method is that the dual search only involves a one-dimensional search within [0,1]. Some potential applications of the method as well as the issue of its implementation are discussed.