A higher order richardson scheme for a singularly perturbed semilinear elliptic convection-diffusion equation

The Dirichlet problem on a vertical strip is examined for a singularly perturbed semilinear elliptic convection-diffusion equation. For this problem, the basic nonlinear difference scheme based on the classical approximations on piecewise uniform grids condensing in the vicinity of boundary layers converges ɛ-uniformly with an order at most almost one. The Richardson technique is used to construct a nonlinear scheme that converges ɛ-uniformly with an improved order, namely, at the rate O(N ₁⁻²ln² N ₁ + N ₂⁻²), where N ₁ + 1 and N ₂ + 1 are the number of grid nodes along the x ₁-axis and per unit interval of the x ₂-axis, respectively. This nonlinear basic scheme underlies the linearized iterative scheme, in which the nonlinear term is calculated using the values of the sought function found at the preceding iteration step. The latter scheme is used to construct a linearized iterative Richardson scheme converging ɛ-uniformly with an improved order. Both the basic and improved iterative schemes converge ɛ-uniformly at the rate of a geometric progression as the number of iteration steps grows. The upper and lower solutions to the iterative Richardson schemes are used as indicators, which makes it possible to determine the iteration step at which the same ɛ-uniform accuracy is attained as that of the non-iterative nonlinear Richardson scheme. It is shown that no Richardson schemes exist for the convection-diffusion boundary value problem converging ɛ-uniformly with an order greater than two. Principles are discussed on which the construction of schemes of order greater than two can be based.     

A finite difference scheme of improved accuracy on a priori adapted grids for a singularly perturbed parabolic convection-diffusion equation

In the case of the Dirichlet problem for a singularly perturbed parabolic convection-diffusion equation with a small parameter ɛ multiplying the higher order derivative, a finite difference scheme of improved order of accuracy that converges almost ɛ-uniformly (that is, the convergence rate of this scheme weakly depends on ɛ) is constructed. When ɛ is not very small, this scheme converges with an order of accuracy close to two. For the construction of the scheme, we use the classical monotone (of the first order of accuracy) approximations of the differential equation on a priori adapted locally uniform grids that are uniform in the domains where the solution is improved. The boundaries of such domains are determined using a majorant of the singular component of the grid solution. The accuracy of the scheme is improved using the Richardson technique based on two embedded grids. The resulting scheme converges at the rate of O((ɛ⁻¹ N ^−K ln² N)² + N ⁻²ln⁴ N + N ₀⁻²) as N, N ₀ → ∞, where N and N ₀ determine the number of points in the meshes in x and in t, respectively, and K is a prescribed number of iteration steps used to improve the grid solution. Outside the σ-neighborhood of the lateral boundary near which the boundary layer arises, the scheme converges with the second order in t and with the second order up to a logarithmic factor in x; here, σ = O(N ^{−(K − 1)}ln² N). The almost ɛ-uniformly convergent finite difference scheme converges with the defect of ɛ-uniform convergence ν, namely, under the condition N ⁻¹ ≪ ɛ^ν, where ν determining the required number of iteration steps K (K = K(ν)) can be chosen sufficiently small in the interval (0, 1]. When ɛ⁻¹ = O(N ^{K − 1}), the scheme converges at the rate of O(N ⁻²ln⁴ N + N ₀⁻²).     

Improved approximations of the solution and derivatives to a singularly perturbed reaction-diffusion equation based on the solution decomposition method

In the case of the Dirichlet problem for a singularly perturbed ordinary differential reaction-diffusion equation, a new approach is used to the construction of finite difference schemes such that their solutions and their normalized first- and second-order derivatives converge in the maximum norm uniformly with respect to a perturbation parameter ɛ ∈(0, 1]; the normalized derivatives are ɛ-uniformly bounded. The key idea of this approach to the construction of ɛ-uniformly convergent finite difference schemes is the use of uniform grids for solving grid subproblems for the regular and singular components of the grid solution. Based on the asymptotic construction technique, a scheme of the solution decomposition method is constructed such that its solution and its normalized first- and second-order derivatives converge ɛ-uniformly at the rate of O(N ⁻²ln² N), where N + 1 is the number of points in the uniform grids. Using the Richardson technique, an improved scheme of the solution decomposition method is constructed such that its solution and its normalized first and second derivatives converge ɛ-uniformly in the maximum norm at the same rate of O(N ⁻⁴ln⁴ N).     

Conservative finite difference scheme for a singularly perturbed elliptic reaction-diffusion equation: Approximation of solutions and derivatives

A boundary value problem for a singularly perturbed elliptic reaction-diffusion equation in a vertical strip is considered. The derivatives are written in divergent form. The derivatives in the differential equation are multiplied by a perturbation parameter ɛ², where ɛ takes arbitrary values in the interval (0, 1]. As ɛ → 0, a boundary layer appears in the solution of this problem. Using the integrointerpolational method and the condensing grid technique, conservative finite difference schemes on flux grids are constructed that converge ɛ-uniformly at a rate of O(N ₁⁻²ln² N ₁ + N ₂⁻²), where N ₁ + 1 and N ₂ + 1 are the number of mesh points on the x ₁-axis and the minimal number of mesh points on a unit interval of the x ₂-axis respectively. The normalized difference derivatives ɛ ^k (∂ ^k /∂x ₁ ^k )u(x) (k = 1, 2), which are ɛ-uniformly bounded and approximate the normalized derivatives in the direction across the boundary layer, and the derivatives along the boundary layer (∂ ^k /∂ x ₂ ^k )u(x) (k = 1, 2) converge ɛ-uniformly at the same rate.     

Conditioning and stability of finite difference schemes on uniform meshes for a singularly perturbed parabolic convection-diffusion equation

For a singularly perturbed parabolic convection-diffusion equation, the conditioning and stability of finite difference schemes on uniform meshes are analyzed. It is shown that a convergent standard monotone finite difference scheme on a uniform mesh is not ?-uniformly well conditioned or ?-uniformly stable to perturbations of the data of the grid problem (here, ? is a perturbation parameter, ? ∈ (0, 1]). An alternative finite difference scheme is proposed, namely, a scheme in which the discrete solution is decomposed into regular and singular components that solve grid subproblems considered on uniform meshes. It is shown that this solution decomposition scheme converges ?-uniformly in the maximum norm at an O(N ^?1lnN + N ₀ ^?1 ) rate, where N + 1 and N ₀ + 1 are the numbers of grid nodes in x and t, respectively. This scheme is ?-uniformly well conditioned and ?-uniformly stable to perturbations of the data of the grid problem. The condition number of the solution decomposition scheme is of order O(δ^?2lnδ^?1 + δ ₀ ^?1 ); i.e., up to a logarithmic factor, it is the same as that of a classical scheme on uniform meshes in the case of a regular problem. Here, δ = N ^?1lnN and δ₀ = N ₀ ^?1 are the accuracies of the discrete solution in x and t, respectively.     

Conditional ɛ-uniform convergence of adaptive algorithms in the finite element method as applied to singularly perturbed problems

The boundary value problem for the ordinary differential equation of reaction-diffusion on the interval [−1, 1] is examined. The highest derivative in this equation appears with a small parameter ɛ² (ɛ ∈ (0, 1]). As the small parameter approaches zero, boundary layers arise in the neighborhood of the interval endpoints. An algorithm for the construction of a posteriori adaptive piecewise uniform grids is proposed. In the adaptation process, the edges of the boundary layers are located more accurately and the grid on the boundary layers is repeatedly refined. To find an approximate solution, the finite element method is used. The sequence of grids constructed by the algorithm is shown to converge “conditionally ɛ-uniformly” to some limit partition for which the error estimate O(N ⁻²ln³ N) is proved. The main results are obtained under the assumption that ɛ ≪ N ⁻¹, where N is number of grid nodes; thus, conditional ɛ-uniform convergence is dealt with. The proofs use the Galerkin projector and its property to be quasi-optimal.     

The Richardson scheme for the singularly perturbed parabolic reaction-diffusion equation in the case of a discontinuous initial condition

The Dirichlet problem for a singularly perturbed parabolic reaction-diffusion equation with a piecewise continuous initial condition in a rectangular domain is considered. The higher order derivative in the equation is multiplied by a parameter ?², where ? ∈ (0, 1]. When ? is small, a boundary and an interior layer (with the characteristic width ?) appear, respectively, in a neighborhood of the lateral part of the boundary and in a neighborhood of the characteristic of the reduced equation passing through the discontinuity point of the initial function; for fixed ?, these layers have limited smoothness. Using the method of additive splitting of singularities (induced by the discontinuities of the initial function and its low-order derivatives) and the condensing grid method (piecewise uniform grids that condense in a neighborhood of the boundary layers), a finite difference scheme is constructed that converges ?-uniformly at a rate of O(N ^?2ln² N + n ₀ ^?1 ), where N + 1 and N ₀ + 1 are the numbers of the mesh points in x and t, respectively. Based on the Richardson technique, a scheme that converges ?-uniformly at a rate of O(N ^?3 + N ₀ ^?2 ) is constructed. It is proved that the Richardson technique cannot construct a scheme that converges in ?-uniformly in x with an order greater than three.     

Approximation of singularly perturbed parabolic equations in unbounded domains subject to piecewise smooth boundary conditions in the case of solutions that grow at infinity

The initial-boundary value problem in a domain on a straight line that is unbounded in x is considered for a singularly perturbed reaction-diffusion parabolic equation. The higher order derivative in the equation is multiplied by a parameter ɛ², where ɛ ∈ (0, 1]. The right-hand side of the equation and the initial function grow unboundedly as x → ∞ at a rate of O(x ²). This causes the unbounded growth of the solution at infinity at a rate of O(Ψ(x)), where Ψ(x) = x ² + 1. The initialboundary function is piecewise smooth. When ɛ is small, a boundary and interior layers appear, respectively, in a neighborhood of the lateral part of the boundary and in a neighborhood of the characteristics of the reduced equation passing through the discontinuity points of the initial function. In the problem under examination, the error of the grid solution grows unboundedly in the maximum norm as x → ∞ even for smooth solutions when ɛ is fixed. In this paper, the proximity of solutions of the initial-boundary value problem and its grid approximations is considered in the weighted maximum norm ∥·∥ ^w with the weighting function Ψ⁻¹(x); in this norm, the solution of the initial-boundary value problem is ɛ-uniformly bounded. Using the method of special grids that condense in a neighborhood of the boundary layer or in neighborhoods of the boundary and interior layers, special finite difference schemes are constructed and studied that converge ɛ-uniformly in the weighted norm. It is shown that the convergence rate considerably depends on the type of nonsmoothness in the initial-boundary conditions. Grid approximations of the Cauchy problem with the right-hand side and the initial function growing as O(Ψ(x)) that converge ɛ-uniformly in the weighted norm are also considered.     

The use of solutions on embedded grids for the approximation of singularly perturbed parabolic convection-diffusion equations on adapted grids

The Dirichlet problem on a closed interval for a parabolic convection-diffusion equation is considered. The higher order derivative is multiplied by a parameter ? taking arbitrary values in the semi-open interval (0, 1]. For the boundary value problem, a finite difference scheme on a posteriori adapted grids is constructed. The classical approximations of the equation on uniform grids in the main domain are used; in some subdomains, these grids are subjected to refinement to improve the grid solution. The subdomains in which the grid should be refined are determined using the difference of the grid solutions of intermediate problems solved on embedded grids. Special schemes on a posteriori piecewise uniform grids are constructed that make it possible to obtain approximate solutions that converge almost ?-uniformly, i.e., with an error that weakly depends on the parameter ?: |u(x, t) ? z(x, t)| ≤ M[N ₁ ^?1 ln² N ₁ + N ₀ ^?1 lnN ₀ + ?^?1 N ₁ ^?K ln ^K?1 N ₁], (x, t) ε ? _h , where N ₁ + 1 and N ₀ + 1 are the numbers of grid points in x and t, respectively; K is the number of refinement iterations (with respect to x) in the adapted grid; and M = M(K). Outside the σ-neighborhood of the outflow part of the boundary (in a neighborhood of the boundary layer), the scheme converges ?-uniformly at a rate O(N ₁ ^?1 ln² N ₁ + N ₀ ^?1 lnN ₀), where σ ≤ MN ₁ ^{?K + 1} ln ^K?1 N ₁ for K ≥ 2.     

Finite difference schemes for the singularly perturbed reaction-diffusion equation in the case of spherical symmetry

The boundary value problem for the singularly perturbed reaction-diffusion parabolic equation in a ball in the case of spherical symmetry is considered. The derivatives with respect to the radial variable appearing in the equation are written in divergent form. The third kind boundary condition, which admits the Dirichlet and Neumann conditions, is specified on the boundary of the domain. The Laplace operator in the differential equation involves a perturbation parameter ?², where ? takes arbitrary values in the half-open interval (0, 1]. When ? → 0, the solution of such a problem has a parabolic boundary layer in a neighborhood of the boundary. Using the integro-interpolational method and the condensing grid technique, conservative finite difference schemes on flux grids are constructed that converge ?-uniformly at a rate of O(N ^?2ln² N + N ₀ ^?1 ), where N + 1 and N ₀ + 1 are the numbers of the mesh points in the radial and time variables, respectively.     

Necessary conditions for ɛ-uniform convergence of finite difference schemes for parabolic equations with moving boundary layers

A grid approximation of the boundary value problem for a singularly perturbed parabolic reaction-diffusion equation is considered in a domain with the boundaries moving along the axis x in the positive direction. For small values of the parameter ? (this is the coefficient of the higher order derivatives of the equation, ? ∈ (0, 1]), a moving boundary layer appears in a neighborhood of the left lateral boundary S ₁ ^L . In the case of stationary boundary layers, the classical finite difference schemes on piece-wise uniform grids condensing in the layers converge ?-uniformly at a rate of O(N ^?1lnN + N ₀), where N and N ₀ define the number of mesh points in x and t. For the problem examined in this paper, the classical finite difference schemes based on uniform grids converge only under the condition N ^?1 + N ₀ ^?1 ? ?. It turns out that, in the class of difference schemes on rectangular grids that are condensed in a neighborhood of S ₁ ^L with respect to x and t, the convergence under the condition N ^?1 + N ₀ ^?1 ≤ ?^1/2 cannot be achieved. Examination of widths that are similar to Kolmogorov’s widths makes it possible to establish necessary and sufficient conditions for the ?-uniform convergence of approximations of the solution to the boundary value problem. These conditions are used to design a scheme that converges ?-uniformly at a rate of O(N ^?1lnN + N ₀).     

Conditioning of finite difference schemes for a singularly perturbed convection-diffusion parabolic equation

In the case of the boundary value problem for a singularly perturbed convection-diffusion parabolic equation, conditioning of an ε-uniformly convergent finite difference scheme on a piecewise uniform grid is examined. Conditioning of a finite difference scheme on a uniform grid is also examined provided that this scheme is convergent. For the condition number of the scheme on a piecewise uniform grid, an ε-uniform bound O(δ ₁ ^?2 lnδ ₁ ^?1 + δ ₀ ^?1 ) is obtained, where δ₁ and δ₀ are the error components due to the approximation of the derivatives with respect to x and t, respectively. Thus, this scheme is ε-uniformly well-conditioned. For the condition number of the scheme on a uniform grid, we have the estimate O(ε^?1δ ₁ ^?2 + δ ₀ ^?1 ); this scheme is not ε-uniformly well-conditioned. In the case of the difference scheme on a uniform grid, there is an additional error due to perturbations of the grid solution; this error grows unboundedly as ε → 0, which reduces the accuracy of the grid solution (the number of correct significant digits in the grid solution is reduced). The condition numbers of the matrices of the schemes under examination are the same; both have an order of O(ε^?1δ ₁ ^?2 + δ ₀ ^?1 ). Neither the matrix of the ε-uniformly convergent scheme nor the matrix of the scheme on a uniform grid is ε-uniformly well-conditioned.     

Approximation of a system of singularly perturbed reaction-diffusion parabolic equations in a rectangle

The Dirichlet problem for a system of singularly perturbed reaction-diffusion parabolic equations in a rectangle is considered. The higher order derivatives of the equations are multiplied by a perturbation parameter ?², where ? takes arbitrary values in the interval (0, 1]. When ? vanishes, the system of parabolic equations degenerates into a system of ordinary differential equations with respect to t. When ? tends to zero, a parabolic boundary layer with a characteristic width ? appears in a neighborhood of the boundary. Using the condensing grid technique and the classical finite difference approximations of the boundary value problem, a special difference scheme is constructed that converges ?-uniformly at a rate of O(N ^?2ln² N + N ₀ ^?1 , where \(N = \mathop {\min }\limits_s N_s \), N ^s + 1 and N ₀ + 1 are the numbers of mesh points on the axes x _s and t, respectively.     

Strong stability of a scheme on locally uniform meshes for a singularly perturbed ordinary differential convection-diffusion equation

The Dirichlet problem for a singularly perturbed ordinary differential convection-diffusion equation with a small parameter ? (? ?? (0, 1]) multiplying the higher order derivative is considered. For the problem, a difference scheme on locally uniform meshes is constructed that converges in the maximum norm conditionally, i.e., depending on the relation between the parameter ? and the value N defining the number of nodes in the mesh used; in particular, the scheme converges almost ?-uniformly (i.e., its accuracy depends weakly on ?). The stability of the scheme with respect to perturbations in the data and its conditioning are analyzed. The scheme is constructed using classical monotone approximations of the boundary value problem on a priori adapted grids, which are uniform on subdomains where the solution is improved. The boundaries of these subdomains are determined by a majorant of the singular component of the discrete solution. On locally uniform meshes, the difference scheme converges at a rate of O(min[?^?1 N ^?K lnN, 1] + N ^?1lnN), where K is a prescribed number of iterations for refining the discrete solution. The scheme converges almost ?-uniformly at a rate of O(N ^?1lnN) if N ^?1 ?? ?^??, where ?? (the defect of ?-uniform convergence) determines the required number K of iterations (K = K(??) ?? ??^?1) and can be chosen arbitrarily small from the half-open interval (0, 1]. The condition number of the difference scheme satisfies the bound ?? _P = O(?^?1/K ln^1/K ?^?1??^{?(K + 1)/K} ), where ?? is the accuracy of the solution of the scheme in the maximum norm in the absence of perturbations. For sufficiently large K, the scheme is almost ?-uniformly strongly stable.     

Improved difference scheme of the solution decomposition method for a singularly perturbed reaction-diffusion equation

A Dirichlet problem is considered for a singularly perturbed ordinary differential reaction-diffusion equation. For this problem, a new approach is developed in order to construct difference schemes that converge uniformly with respect to the perturbation parameter ?, ? ∈ (0, 1]. The approach is based on the decomposition of a discrete solution into regular and singular components, which are solutions of discrete subproblems on uniform grids. Using the asymptotic construction technique, a difference scheme of the solution decomposition method is constructed that converges ?-uniformly in the maximum norm at the rate O (N ^?2 ln² N), where N + 1 is the number of nodes in the grid used; for fixed values of the parameter ?, the scheme converges at the rate O(N ^?2). Using the Richardson technique, an improved scheme of the solution decomposition method is constructed, which converges ?-uniformly in the maximum norm at the rate O(N ^?4 ln⁴ N).     

Approximation by Conic Splines

We show that the complexity of a parabolic or conic spline approximating a sufficiently smooth curve with non-vanishing curvature to within Hausdorff distance ɛ is c ₁ɛ^−1/4 + O(1), if the spline consists of parabolic arcs, and c ₂ɛ^−1/5 + O(1), if it is composed of general conic arcs of varying type. The constants c ₁ and c ₂ are expressed in the Euclidean and affine curvature of the curve. We also show that the Hausdorff distance between a curve and an optimal conic arc tangent at its endpoints is increasing with its arc length, provided the affine curvature along the arc is monotone. This property yields a simple bisection algorithm for the computation of an optimal parabolic or conic spline. The research of SG and GV was partially supported by grant 6413 of the European Commission to the IST-2002 FET-Open project Algorithms for Complex Shapes in the Sixth Framework Program.     

A method of asymptotic constructions with improved accuracy for a quasilinear singularly perturbed parabolic convection-diffusion equation

The Dirichlet problem on an interval for quasilinear singularly perturbed parabolic convection-diffusion equation is considered. The higher order derivative of the equation is multiplied by a parameter ε that takes any values from the half-open interval (0, 1]. For this type of linear problems, the order of the ε-uniform convergence (with respect to x and t) for the well-known schemes is not higher than unity (in the maximum norm). For the boundary value problem under consideration, grid approximations are constructed that converge ε-uniformly at the rate of O(N ^?2ln² N + N ^?2 ₀), where N + 1 and N ₀ + 1 are the numbers of the mesh points with respect to x and t, respectively. On the x axis, piecewise uniform meshes that condense in the boundary layer are used. If the parameter value is small compared to the effective step of the spatial grid, the domain decomposition method is used, which is motivated by “asymptotic constructions.” Monotone approximations of “auxiliary” subproblems describing the main terms of the asymptotic expansion of the solution outside a neighborhood of the boundary layer neighborhood are used. In the neighborhood of the boundary layer (of the width O(ε ln N)) the first derivative with respect to x is approximated by the central difference derivative. These subproblems are successively solved in the subdomains on uniform grids. If the parameter values are not sufficiently small (compared to the effective step of the mesh with respect to x), the classical implicit difference schemes approximating the first derivative with respect to x by the central difference derivative are applied. To improve the accuracy in t, the defect correction technique is used. Notice that the calculation of the solution of the constructed difference scheme (the scheme based on the method of asymptotic constructions) can be considerably simplified for sufficiently small values of the parameter ε.     

Approximation of the solution and its derivative for the singularly perturbed Black-Scholes equation with nonsmooth initial data

A problem for the black-Scholes equation that arises in financial mathematics is reduced, by a transformation of variables, to the Cauchy problem for a singularly perturbed parabolic equation with the variables x, t and a perturbation parameter ɛ, ɛ ∈ (0, 1]. This problem has several singularities such as the unbounded domain, the piecewise smooth initial function (its first-order derivative in x has a discontinuity of the first kind at the point x = 0), an interior (moving in time) layer generated by the piecewise smooth initial function for small values of the parameter ɛ, etc. In this paper, a grid approximation of the solution and its first-order derivative is studied in a finite domain including the interior layer. On a uniform mesh, using the method of additive splitting of a singularity of the interior layer type, a special difference scheme is constructed that allows us to ɛ-uniformly approximate both the solution to the boundary value problem and its first-order derivative in x with convergence orders close to 1 and 0.5, respectively. The efficiency of the constructed scheme is illustrated by numerical experiments. The text was submitted by the authors in English.     

Scale limit of a variational inequality modeling diffusive flux in a domain with small holes and strong adsorption in case of a critical scaling

In this paper we study the asymptotic behavior of solutions u _ɛ of the elliptic variational inequality for the Laplace operator in domains periodically perforated by balls with radius of size C ₀ɛ_α, C ₀ > 0, α = n/n−2, and distributed with period ɛ. On the boundary of balls, we have the following nonlinear restrictions u _ɛ ≥ 0, ∂_ν u _ɛ ≥ −ɛ^−ασ(x, u _ɛ), u _ɛ(∂_ν u _ɛ + ɛ^−ασ(x, u _ɛ)) = 0. The weak convergence of the solutions u _ɛ to the solution of an effective variational equality is proved. In this case, the effective equation contains a nonlinear term which has to be determined as solution of a functional equation. Furthermore, a corrector result with respect to the energy norm is given.     

Mosaic approximations of discrete analogs of Calderón-Zygmund operators

Asymptotic estimates of the form mrA = O(InN · ln ^d ɛ ⁻¹), whered is the dimension of the initial space, for mosaic ranks of discrete analog of Calderón-Zygmund operators are obtained for various mosaic covers. Translated fromMatematicheskie Zametki, Vol. 63, No. 1, pp. 81–94, January, 1998.