Optimal-order convergence rates for Eulerian-Lagrangian localized adjoint methods for reactive transport and contamination in groundwater

Eulerian–Langrangian localized adjoint methods (ELLAM) were developed to solve convection–diffusion–reaction equations governing contaminant transport in groundwater flowing through a porous medium, subject to various combinations of boundary conditions. In this article, we prove optimal-order error estimates and some superconvergence results for the ELLAM schemes. In contrast to many existing estimates for a variety of numerical methods, which often contain the temporal derivatives of the exact solution, our error estimates contain the total derivatives of the exact solution but do not involve any temporal derivatives of the exact solution. © 1995 John Wiley & Sons, Inc.     

Eulerian-Lagrangian localized adjoint method: The theoretical framework

This is the second of a sequence of papers devoted to applying the localized adjoint method (LAM), in space-time, to problems of advective-diffusive transport. We refer to the resulting methodology as the Eulerian-Lagrangian localized adjoint method (ELLAM). The ELLAM approach yields a general formulation that subsumes many specific methods based on combined Lagrangian and Eulerian approaches, so-called characteristic methods (CM). In the first paper of this series the emphasis was placed in the numerical implementation and a careful treatment of implementation of boundary conditions was presented for one-dimensional problems. The final ELLAM approximation was shown to possess the conservation of mass property, unlike typical characteristic methods. The emphasis of the present paper is on the theoretical aspects of the method. The theory, based on Herrera's algebraic theory of boundary value problems, is presented for advection-diffusion equations in both one-dimensional and multidimensional systems. This provides a generalized ELLAM formulation. The generality of the method is also demonstrated by a treatment of systems of equations as well as a derivation of mixed methods. © 1993 John Wiley & Sons, Inc.     

Eulerian-Lagrangian method of cells based on localized adjoint method

The localized adjoint method, when applied using an Eulerian-Lagrangian frame, has been quite successful in treating advection-dominated transport. The resulting methodology is known as ELLAM. In previous work, bilinear functions were used as test functions. In this paper, local constant functions are used instead, leading to procedures which are appealing because, in addition to other advantages of ELLAM methods, they ensure local mass conservation, are easy to apply and can be combined without difficulty with existing solute-transport codes which are based on finite volumes. In addition, the procedures for deriving the algorithms presented here are used as an illustration of a general methodology for treating numerically partial differential equations, which is advocated by the authors. Such methodology consists in identifying the information about the sought solution which is contained in the approximate one and then using this insight to choose the interpolation procedure to be applied. © 1994 John Wiley & Sons, Inc.     

Numerical methods for time-dependent convection-diffusion equations

We examine a singularly perturbed linear parabolic initial-boundary value problem in one space variable. Various finite difference schemes are derived for this problem using a semidiscrete Petrov—Galerkin finite element method. These schemes do not have a cell Reynolds number restriction and are shown to be first-order accurate, uniformly in the perturbation parameter. Numerical results are also presented.     

Spacetime discontinuous Galerkin methods for convection-diffusion equations

We have developed two new methods for solving convection-diffusion systems, with particular focus on the compressible Navier-Stokes equations. Our methods are extensions of a spacetime discontinuous Galerkin method for solving systems of hyperbolic conservation laws [3]. Following the original scheme, we use entropy variables as degrees of freedom and entropy stable numerical fluxes for the nonlinear convection term. We examine two different approaches for incorporating the diffusion term: the interior penalty method and the local discontinuous Galerkin approach. For both extensions, we can show an entropy stability result for convection-diffusion systems. Although our schemes are designed for systems, we focus on scalar convectiondiffusion equations in this contribution. This allows us to highlight our main ideas behind the stability proofs, which are the same for scalar equations and systems, in a simplified setting.     

A-posteriori error analysis and adaptive finite element methods for singularly perturbed convection-diffusion equations

For singularly perturbed one-dimensional convection-diffusion equations, finite element approximations are constructed based on a so-called approximate symmetrization of the given unsymmetric problem. Local a-posteriori error estimates are established with respect to an appropriate energy norm where the bounds are proved to be realistic. The local bounds, called error indicators, provide a basis for a self-adaptive mesh refinement. For a model problem numerical results are presented showing that the adaptive method detects and resolves the boundary layer.     

Local convergence analysis of tensor methods for nonlinear equations

Tensor methods for nonlinear equations base each iteration upon a standard linear model, augmented by a low rank quadratic term that is selected in such a way that the mode is efficient to form, store, and solve. These methods have been shown to be very efficient and robust computationally, especially on problems where the Jacobian matrix at the root has a small rank deficiency. This paper analyzes the local convergence properties of two versions of tensor methods, on problems where the Jacobian matrix at the root has a null space of rank one. Both methods augment the standard linear model by a rank one quadratic term. We show under mild conditions that the sequence of iterates generated by the tensor method based upon an ideal tensor model converges locally and two-step Q-superlinearly to the solution with Q-order 3/2, and that the sequence of iterates generated by the tensor method based upon a practial tensor model converges locally and three-step Q-superlinearly to the solution with Q-order 3/2. In the same situation, it is known that standard methods converge linearly with constant converging to 1/2. Hence, tensor methods have theoretical advantages over standard methods. Our analysis also confirms that tensor methods converge at least quadratically on problems where the Jacobian matrix at the root is nonsingular.This paper is dedicated to Phil Wolfe on the occasion of his 65th birthday.Research supported by AFOSR grant AFOSR-90-0109, ARO grant DAAL 03-91-G-0151, NSF grants CCR-8920519 CCR-9101795.     

On the local convergence of adjoint Broyden methods

The numerical solution of nonlinear equation systems is often achieved by so-called quasi-Newton methods. They preserve the rapid local convergence of Newton’s method at a significantly reduced cost per step by successively approximating the system Jacobian though low-rank updates. We analyze two variants of the recently proposed adjoint Broyden update, which for the first time combines the classical least change property with heredity on affine systems. However, the new update does require, the evaluation of so-called adjoint vectors, namely products of the transposed Jacobian with certain dual direction vectors. The resulting quasi-Newton method is linear contravariant in the sense of Deuflhard (Newton methods for nonlinear equations. Springer, Heidelberg, 2006) and it is shown here to be locally and q-superlinearly convergent. Our numerical results on a range of test problems demonstrate that the new method usually outperforms Newton’s and Broyden’s method in terms of runtime and iterations count, respectively. Partially supported by the DFG Research Center Matheon “Mathematics for Key Technologies”, Berlin and the DFG grant WA 1607/2-1.     

A convergence analysis of hopscotch methods for fourth order parabolic equations

Summary Consider the ODE (ordinary differential equation) that arises from a semi-discretization (discretization of the spatial coordinates) of a first order system form of a fourth order parabolic PDE (partial differential equation). We analyse the stability of the finite difference methods for this fourth order parabolic PDE that arise if one applies the hopscotch idea to this ODE.Often the error propagation of these methods can be represented by a three terms matrix-vector recursion in which the matrices have a certain anti-hermitian structure. We find a (uniform) expression for the stability bound (or error propagation bound) of this recursion in terms of the norms of the matrices. This result yields conditions under which these methods are strongly asymptotically stable (i.e. the stability is uniform both with respect to the spatial and the time stepsizes (tending to 0) and the time level (tending to infinity)), also in case the PDE has (spatial) variable coefficients. A convergence theorem follows immediately.     

A note on Hermitian splitting induced relaxation methods for convection-diffusion equations

The solution of the linear system Ax = b by iterative methods requires a splitting of the coefficient matrix in the form A = M − N where M is usually chosen to be a diagonal or a triangular matrix. In this article we study relaxation methods induced by the Hermitian and skew-Hermitian splittings for the solution of the linear system arising from a compact fourth order approximation to the one dimensional convection-diffusion equation and compare the convergence rates of these relaxation methods to that of the widely used successive overrelaxation (SOR) method. Optimal convergence parameters are derived for each method and numerical experiments are given to supplement the theoretical estimates. For certain values of the diffusion parameter, a relaxation method based on the Hermitian splitting converges faster than SOR. For two-dimensional problems a block form of the iterative algorithm is presented. © 1998 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 14: 581–591, 1998     

Eulerian–Lagrangian localized adjoint methods for reactive transport with biodegradation

The microbial degradation of organic contaminants in the subsurface holds significant potential as a mechanism for in-situ remediation strategies. The mathematical models that describe contaminant transport with biodegradation involve a set of advective–diffusive–reactive transport equations. These equations are coupled through the nonlinear reaction terms, which may involve reactions with all of the species and are themselves coupled to growth equations for the subsurface bacterial populations. In this article, we develop Eulerian–Lagrangian localized adjoint methods (ELLAM) to solve these transport equations. ELLAM are formulated to systematically adapt to the changing features of governing partial differential equations. The relative importance of retardation, advection, diffusion, and reaction is directly incorporated into the numerical method by judicious choice of the test functions that appear in the weak form of the governing equation. Different ELLAM schemes for linear variable–coefficient advective–diffusive–reactive transport equations are developed based on different operator splittings. Specific linearization techniques are discussed and are combined with the ELLAM schemes to solve the nonlinear, multispecies transport equations. © 1995 John Wiley & Sons, Inc.     

Multiwavelet approximation methods for pseudodifferential equations on curves. Stability and convergence analysis

We develop a stability and convergence analysis of Galerkin–Petrov schemes based on a general setting of multiresolution generated by several refinable functions for the numerical solution of pseudodifferential equations on smooth closed curves. Particular realizations of such a multiresolution analysis are trial spaces generated by biorthogonal wavelets or by splines with multiple knots. The main result presents necessary and sufficient conditions for the stability of the numerical method in terms of the principal symbol of the pseudodifferential operator and the Fourier transforms of the generating multiscaling functions as well as of the test functionals. Moreover, optimal convergence rates for the approximate solutions in a range of Sobolev spaces are established. This revised version was published online in June 2006 with corrections to the Cover Date.     

Fourier analysis of a robust multigrid method for convection-diffusion equations

Summary. We consider a two-grid method for solving 2D convection-diffusion problems. The coarse grid correction is based on approximation of the Schur complement. As a preconditioner of the Schur complement we use the exact Schur complement of modified fine grid equations. We assume constant coefficients and periodic boundary conditions and apply Fourier analysis. We prove an upper bound for the spectral radius of the two-grid iteration matrix that is smaller than one and independent of the mesh size, the convection/diffusion ratio and the flow direction; i.e. we have a (strong) robustness result. Numerical results illustrating the robustness of the corresponding multigrid -cycle are given. Received October 14, 1994     

On convergence of SOR methods for nonsmooth equations

We study the choice of relaxation parameters ω for convergence of the SOR Newton method and the SOR method for the system of equations F(x)=0 in a unified framework, where F is strongly monotone, locally Lipschitz continuous but not necessarily differentiable. Applications to non‐smooth Dirichlet problems are discussed. Copyright © 2001 John Wiley & Sons, Ltd.     

Local convergence of quasi-Newton methods for B-differentiable equations

We study local convergence of quasi-Newton methods for solving systems of nonlinear equations defined by B-differentiable functions. We extend the classical linear and superlinear convergence results for general quasi-Newton methods as well as for Broyden's method. We also show how Broyden's method may be applied to nonlinear complementarity problems and illustrate its computational performance on two small examples.     

Analysis of the cell boundary element methods for convection dominated convection-diffusion equations

We introduce two kinds of the cell boundary element (CBE) methods for convection dominated convection-diffusion equations: one is the CBE method with the exact bubble function and the other with inexact bubble functions. The main focus of this paper is on inexact bubble CBE methods. For inexact bubble CBE methods we introduce a family of numerical methods depending on two parameters, one for control of interior layers and the other for outflow boundary layers. Stability and convergence analysis are provided and numerical tests for inexact bubble CBEs with various choices of parameters are presented.     

Two-grid methods for characteristic finite volume element solution of semilinear convection-diffusion equations

Two-grid methods for characteristic finite volume element solutions are presented for a kind of semilinear convection-dominated diffusion equations. The methods are based on the method of characteristics, two-grid method and the finite volume element method. The nonsymmetric and nonlinear iterations are only executed on the coarse grid (with grid size H). And the fine-grid solution (with grid size h) can be obtained by a single symmetric and linear step. It is proved that the coarse grid can be much coarser than the fine grid. The two-grid methods achieve asymptotically optimal approximation as long as the mesh sizes satisfy H = O(h^1/3).