Convergence analysis of a multigrid method for convection–diffusion equations

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

Computational complexity of a piecewise linear homotopy algorithm

We give a bound on the number of steps required by the piecewise linear algorithm based on component wise homotopy (proposed by the author for structured problems) when solving a linear problem. When the coefficient matrix is symmetric and positive definite, this bound is polynomial inn and linear in the condition number of the matrix. We also investigate the expected value of the bound for a particular distribution of such matrices. This research has been partially supported by the grant MCS 80-05154 from the National Science Foundation.     

Guaranteed a posteriori error estimates for nonconforming finite element approximations to a singularly perturbed reaction–diffusion problem

We derive guaranteed a posteriori error estimates for nonconforming finite element approximations to a singularly perturbed reaction–diffusion problem. First, an abstract a posteriori error bound is derived under a special equilibration condition. Based on conservative flux reconstruction, two error estimators are proposed and provide actual upper error bounds in the usual energy norm without unknown constants, one of which can be directly constructed without solving local Neumann problems and provide practical computable error bounds. The error estimators also provide local lower bounds but with the multiplicative constants dependent on the diffusion coefficient and mesh size, where the constants can be bounded for enough small mesh size comparable with the square root of the diffusion coefficient. By adding edge jumps with weights to the energy norm, two modified error estimators with additional edge tangential jumps are shown to be robust with respect to the diffusion coefficient and provide guaranteed upper bounds on the error in the modified norm. Finally, the performance of the estimators are illustrated by the numerical results.     

A numerical scheme for solving nonhomogeneous time-dependent problems

A numerical technique for solving time-dependent problems with variable coefficient governed by the heat, convection diffusion, wave, beam and telegraph equations is presented. The Sinc–Galerkin method is applied to construct the numerical solution. The method is tested on three problems and comparisons are made with the exact solutions. The numerical results demonstrate the reliability and efficiency of using the Sinc–Galerkin method to solve such problems.     

A new fractional finite volume method for solving the fractional diffusion equation

The inherent heterogeneities of many geophysical systems often gives rise to fast and slow pathways to water and chemical movement. One approach to model solute transport through such media is by fractional diffusion equations with a space–time dependent variable coefficient. In this paper, a two-sided space fractional diffusion model with a space–time dependent variable coefficient and a nonlinear source term subject to zero Dirichlet boundary conditions is considered.Some finite volume methods to solve a fractional differential equation with a constant dispersion coefficient have been proposed. The spatial discretisation employs fractionally-shifted Grünwald formulas to discretise the Riemann–Liouville fractional derivatives at control volume faces in terms of function values at the nodes. However, these finite volume methods have not been extended to two-dimensional and three-dimensional problems in a natural manner. In this paper, a new weighted fractional finite volume method with a nonlocal operator (using nodal basis functions) for solving this two-sided space fractional diffusion equation is proposed. Some numerical results for the Crank–Nicholson fractional finite volume method are given to show the stability, consistency and convergence of our computational approach. This novel simulation technique provides excellent tools for practical problems even when a complex transition zone is involved. This technique can be extend to two-dimensional and three-dimensional problems with complex regions.     

A numerical scheme for solving nonhomogeneous time-dependent problems

A numerical technique for solving time-dependent problems with variable coefficient governed by the heat, convection diffusion, wave, beam and telegraph equations is presented. The Sinc–Galerkin method is applied to construct the numerical solution. The method is tested on three problems and comparisons are made with the exact solutions. The numerical results demonstrate the reliability and efficiency of using the Sinc–Galerkin method to solve such problems. Received: January 18, 2005     

Ruin theory for classical risk process that is perturbed by diffusion with risky investments

In this paper, we study the ruin theory for classical risk process that is perturbed by diffusion with risky investments. We obtain the upper bound for the minimal ruin probability. We also investigate the relationships between the adjustment coefficient and the diffusion volatility parameter, the risk‐free rate and the correlation coefficient by numerical calculation. We give the relationships between ruin and investment. Copyright © 2008 John Wiley & Sons, Ltd.     

Lower bounds for densities of uniformly elliptic random variables on Wiener space

 In this article, we generalize the lower bound estimates for uniformly elliptic diffusion processes obtained by Kusuoka and Stroock. We define the concept of uniform elliptic random variable on Wiener space and show that with this definition one can prove a lower bound estimate of Gaussian type for its density. We apply our results to the case of the stochastic heat equation under the hypothesis of unifom ellipticity of the diffusion coefficient. Received: 6 November 2001 / Revised version: 27 February 2003 / Published online: 12 May 2003 Key words or phrases: Malliavin Calculus – Density estimates – Aronson estimates     

Space-time domain decomposition for parabolic problems

We analyze a space-time domain decomposition iteration, for a model advection diffusion equation in one and two dimensions. The discretization of this iteration is the block red-black variant of the waveform relaxation method, and our analysis provides new convergence results for this scheme. The asymptotic convergence rate is super-linear, and it is governed by the diffusion of the error across the overlap between subdomains. Hence, it depends on both the size of this overlap and the diffusion coefficient in the equation. However it is independent of the number of subdomains, provided the size of the overlap remains fixed. The convergence rate for the heat equation in a large time window is initially linear and it deteriorates as the number of subdomains increases. The duration of the transient linear regime is proportional to the length of the time window. For advection dominated problems, the convergence rate is initially linear and it improves as the the ratio of advection to diffusion increases. Moreover, it is independent of the size of the time window and of the number of subdomains. Numerical calculations illustrate our analysis.     

A uniform optimal‐order estimate for an Eulerian‐Lagrangian discontinuous Galerkin method for transient advection–diffusion equations

We prove an optimal‐order error estimate in a weighted energy norm for the Eulerian‐Lagrangian discontinuous Galerkin method for unsteady‐state advection–diffusion equations with general inflow and outflow boundary conditions. It is well‐known that these problems admit dynamic fronts with interior and boundary layers. The estimate holds uniformly with respect to the vanishing diffusion coefficient. © 2008 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2009     

Kronecker product approximation preconditioners for convection–diffusion model problems

We consider the iterative solution of linear systems arising from four convection–diffusion model problems: scalar convection–diffusion problem, Stokes problem, Oseen problem and Navier–Stokes problem. We design preconditioners for these model problems that are based on Kronecker product approximations (KPAs). For this we first identify explicit Kronecker product structure of the coefficient matrices, in particular for the convection term. For the latter three model cases, the coefficient matrices have a 2 × 2 block structure, where each block is a Kronecker product or a summation of several Kronecker products. We then use this structure to design a block diagonal preconditioner, a block triangular preconditioner and a constraint preconditioner. Numerical experiments show the efficiency of the three KPA preconditioners, and in particular of the constraint preconditioner that usually outperforms the other two. This can be explained by the relationship that exists between these three preconditioners: the constraint preconditioner can be regarded as a modification of the block triangular preconditioner, which at its turn is a modification of the block diagonal preconditioner based on the cell Reynolds number. Copyright © 2009 John Wiley & Sons, Ltd.     

A high‐order Godunov method for one‐dimensional convection‐diffusion‐reaction problems

In this article we develop a high‐order Godunov method for one‐dimensional convection‐diffusion‐reaction problems where convection dominates diffusion. The heart of this method comes from incorporating the diffusion term via the slope of the linear representation (recovery) of the solution on each grid cell. The method is conservative and explicit. Therefore, it is efficient in computing time. For constant coefficient linear convection, diffusion, and Lipschitz‐type reaction, the properties of the total variation stability and monotonicity preservation are proved. An error estimation is derived. Computational examples are presented and compared with the exact solutions. © 2000 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 16: 495–512, 2000     

Uniform boundedness and convergence of solutions to the systems with cross-diffusions dominated by self-diffusions

Uniform boundedness and convergence of global solutions are proved for quasilinear parabolic systems with cross-diffusions dominated by self-diffusions in population dynamics. Gagliardo–Nirenberg-type inequalities are used in the estimates of solutions in order to establish W₂¹-bounds uniform in time. In each step of estimates the contribution of the diffusion coefficients is emphasized, and it is concluded that the uniform bound remains independent of the growth of the diffusion coefficient in the system. Hence, convergence of solutions is established for systems with large diffusion coefficients.     

Wavelet estimation of the diffusion coefficient in time dependent diffusion models

The estimation problem for diffusion coefficients in diffusion processes has been studied in many papers,where the diffusion coefficient function is assumed to be a 1-dimensional bounded Lipschitzian function of the state or the time only.There is no previous work for the nonparametric estimation of time-dependent diffusion models where the diffusion coefficient depends on both the state and the time.This paper introduces and studies a wavelet estimation of the time-dependent diffusion coefficient under a more general assumption that the diffusion coefficient is a linear growth Lipschitz function.Using the properties of martingale,we translate the problems in diffusion into the nonparametric regression setting and give the L~r convergence rate.A strong consistency of the estimate is established.With this result one can estimate the time-dependent diffusion coefficient using the same structure of the wavelet estimators under any equivalent probability measure.For example, in finance,the wavelet estimator is strongly consistent under the market probability measure as well as the risk neutral probability measure.     

Uniform Boundedness and Convergence of Solutions to Cross-Diffusion Systems

Uniform boundedness and convergence of global solutions are proved for cross-diffusion systems in population dynamics. Gagliardo-Nirenberg type inequalities are used in the estimates of solutions in order to establish W₂¹-bounds uniform in time. In each step of estimates the contribution of the diffusion coefficients are emphasized, and it is concluded that the uniform bound remains independent of the growth of the diffusion coefficient in the system. Hence convergence of solutions are established for systems with large diffusion coefficients.     

Group method solution for solving nonlinear heat diffusion problems

The linear transformation group approach is developed to simulate heat diffusion problems in a media with the thermal conductivity and the heat capacity are nonlinear and obeyed a striking power law relation, subject to nonlinear boundary conditions due to radiation exchange at the interface according to the fourth power law. The application of a one-parameter transformation group reduces the number of independent variables by one so that the governing partial differential equation with the boundary conditions reduces to an ordinary differential equation with appropriate corresponding conditions. The Runge–Kutta shooting method is used to solve the nonlinear ordinary differential equation. Different parametric studies are worked out and plotted to study the effect of heat transfer coefficient, density and radiation number on the surface temperature.     

Sparse regression Chebyshev polynomial interval method for nonlinear dynamic systems under uncertainty

This paper proposes a new higher-efficiency interval method for the response bound estimation of nonlinear dynamic systems, whose uncertain parameters are bounded. This proposed method uses sparse regression and Chebyshev polynomials to help the interval analysis applied on the estimation. It is also a non-intrusive method which needs much fewer evaluations of original nonlinear dynamic systems than the other Chebyshev polynomials based interval methods. By using the proposed method, the response bound estimation of nonlinear dynamic systems can be performed more easily, even if the numerical simulation in nonlinear dynamic systems is costly or the number of uncertain parameters is higher than usual. In our approach, the sparse regression method “elastic net” is adopted to improve the sampling efficiency, but with sufficient accuracy. It alleviates the sample size required in coefficient calculation of the Chebyshev inclusion function in the sampling based methods. Moreover, some mature technologies are adopted to further reduce the sample size and to guarantee the accuracy of the estimation. So that the number of sampling, which solves the certain ordinary differential equations (ODEs), can be reduced significantly in the Chebyshev interval method. Three numerical examples are presented to illustrate the efficiency of proposed interval method. In particular, the last two examples are high dimension uncertain problems, which can further exhibit the ability to reduce the computational cost.     

Probability density function of SDEs with unbounded and path-dependent drift coefficient

In this paper, we first prove that the existence of a solution of SDEs under the assumptions that the drift coefficient is of linear growth and path-dependent, and diffusion coefficient is bounded, uniformly elliptic and Hölder continuous. We apply Gaussian upper bound for a probability density function of a solution of SDE without drift coefficient and local Novikov condition, in order to use Maruyama–Girsanov transformation. The aim of this paper is to prove the existence with explicit representations (under linear/super-linear growth condition), Gaussian two-sided bound and Hölder continuity (under sub-linear growth condition) of a probability density function of a solution of SDEs with path-dependent drift coefficient. As an application of explicit representation, we provide the rate of convergence for an Euler–Maruyama (type) approximation, and an unbiased simulation scheme.     

Lavrentiev regularization + Ritz approximation = uniform finite element error estimates for differential equations with rough coefficients

We consider a parametric family of boundary value problems for a diffusion equation with a diffusion coefficient equal to a small constant in a subdomain. Such problems are not uniformly well-posed when the constant gets small. However, in a series of papers, Bakhvalov and Knyazev have suggested a natural splitting of the problem into two well-posed problems. Using this idea, we prove a uniform finite element error estimate for our model problem in the standard parameter-independent Sobolev norm. We also study uniform regularity of the transmission problem, needed for approximation. A traditional finite element method with only one additional assumption, namely, that the boundary of the subdomain with the small coefficient does not cut any finite element, is considered.

One interpretation of our main theorem is in terms of regularization. Our FEM problem can be viewed as resulting from a Lavrentiev regularization and a Ritz-Galerkin approximation of a symmetric ill-posed problem. Our error estimate can then be used to find an optimal regularization parameter together with the optimal dimension of the approximation subspace.

     

Analytical solution of a spatially variable coefficient advection–diffusion equation in up to three dimensions

Analytical solutions are provided for the two- and three-dimensional advection–diffusion equation with spatially variable velocity and diffusion coefficients. We assume that the velocity component is proportional to the distance and that the diffusion coefficient is proportional to the square of the corresponding velocity component. There is a simple transformation which reduces the spatially variable equation to a constant coefficient problem for which there are available a large number of known analytical solutions for general initial and boundary conditions. These solutions are also solutions to the spatially variable advection–diffusion equation. The special form of the spatial coefficients has practical relevance and for divergent free flow represent corner or straining flow. Unlike many other analytical solutions, we use the transformation to obtain solutions of the spatially variable coefficient advection–diffusion equation in two and three dimensions. The analytical solutions, which are simple to evaluate, can be used to validate numerical models for solving the advection–diffusion equation with spatially variable coefficients. For numerical schemes which cannot handle flow stagnation points, we provide analytical solution to the spatially variable coefficient advection–diffusion equation for two-dimensional corner flow which contains an impermeable flow boundary. The impermeable flow boundary coincides with a streamline along which the fluid velocity is finite but the concentration vanishes. This example is useful for validating numerical schemes designed to predict transport around a curved boundary.