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 ₀⁻²).     

A Richardson scheme of the decomposition method for solving singularly perturbed parabolic reaction-diffusion equation

For the one-dimensional singularly perturbed parabolic reaction-diffusion equation with a perturbation parameter ɛ, where ɛ ∈ (0, 1], the grid approximation of the Dirichlet problem on a rectangular domain in the (x, t)-plane is examined. For small ɛ, a parabolic boundary layer emerges in a neighborhood of the lateral part of the boundary of this domain. A new approach to the construction of ɛ-uniformly converging difference schemes of higher accuracy is developed for initial boundary value problems. The asymptotic construction technique is used to design the base decomposition scheme within which the regular and singular components of the grid solution are solutions to grid subproblems defined on uniform grids. The base scheme converges ɛ-uniformly in the maximum norm at the rate of O(N ⁻²ln² N + N ₀⁻¹), where N + 1 and N ₀ + 1 are the numbers of nodes in the space and time meshes, respectively. An application of the Richardson extrapolation technique to the base scheme yields a higher order scheme called the Richardson decomposition scheme. This higher order scheme convergesɛ-uniformly at the rate of O(N ⁻⁴ln⁴ N + N ₀⁻²). For fixed values of the parameter, the convergence rate is O(N ⁻⁴ + N ₀⁻²).     

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.     

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.     

Automatic grid control in adaptive BVP solvers

Grid adaptation in two-point boundary value problems is usually based on mapping a uniform auxiliary grid to the desired nonuniform grid. Here we combine this approach with a new control system for constructing a grid density function ϕ(x). The local mesh width Δx _j + 1/2 = x _j + 1 − x _j with 0 = x ₀ < x ₁ < ... < x _N  = 1 is computed as Δx _j + 1/2 = ε _N / φ _j + 1/2, where {j_j+1/2}₀^N-1\{\varphi_{j+1/2}\}_0^{N-1} is a discrete approximation to the continuous density function ϕ(x), representing mesh width variation. The parameter ε _N  = 1/N controls accuracy via the choice of N. For any given grid, a solver provides an error estimate. Taking this as its input, the feedback control law then adjusts the grid, and the interaction continues until the error has been equidistributed. Digital filters may be employed to process the error estimate as well as the density to ensure the regularity of the grid. Once ϕ(x) is determined, another control law determines N based on the prescribed tolerance TOL{\textsc {tol}}. The paper focuses on the interaction between control system and solver, and the controller’s ability to produce a near-optimal grid in a stable manner as well as correctly predict how many grid points are needed. Numerical tests demonstrate the advantages of the new control system within the bvpsuite solver, ceteris paribus, for a selection of problems and over a wide range of tolerances. The control system is modular and can be adapted to other solvers and error criteria.     

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).     

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.     

Symmetry breaking for a class of semilinear elliptic problems and the bifurcation diagram for a 1-dimensional problem

We study the behaviour of the positive solutions to the Dirichlet problem IR ⁿ in the unit ball in IR ^R wherep<(N+2)/(N−2) ifN≥3 and λ varies over IR. For a special class of functionsg viz.,g(x)=u ₀ ^p (x) whereu ₀ is the unique positive solution at λ=0, we prove that for certain λ’s nonradial solutions bifurcate from radially symmetric positive solutions. WhenN=1, we obtain the complete bifurcation diagram for the positive solution curve.     

On minimax identification of nonparametric autoregressive models

We consider the problem of nonparametric identification for a multi-dimensional functional autoregression y _t = f(y _{t −1}, …,y _t−d ) + e _t on the basis of N observations of y _t . In the case when the unknown nonlinear function f belongs to the Barron class, we propose an estimation algorithm which provides approximations of f with expected L ₂ accuracy O(N ^1/4ln^1/4 N). We also show that this approximation rate cannot be significantly improved. The proposed algorithms are “computationally efficient”– the total number of elementary computations necessary to complete the estimate grows polynomially with N. Received: 23 September 1997 / Revised version: 28 January 1999     

An estimate of the error for eigen functions in the eigenfunction problem for the operator of the linear elasticity theory

We consider an eigenfunction problem for a system of Lamé equations in a three-dimensional parallelepiped in the case of a mixed boundary-value condition on the boundary. By using Steklov averaging operators, the approximation error is given in divergent form. The accuracy of the difference scheme is studied for generalized solutions from the spaceW ₂ ³(Ω). An O(|h|^1.5)-estimate is obtained for eigenfunctions in the grid metric ofW ₂ ¹(ω). Bibliography: 5 titles. Translated fromObchyslyuval'na ta Prykladna Matematyka, No. 81, 1997, pp. 100–109.     

O(dlog?N)-Quantics Approximation of N-d Tensors in High-Dimensional Numerical Modeling

In the present paper, we discuss the novel concept of super-compressed tensor-structured data formats in high-dimensional applications. We describe the multifolding or quantics-based tensor approximation method of O(dlog N)-complexity (logarithmic scaling in the volume size), applied to the discrete functions over the product index set {1,…,N}^⊗d , or briefly N-d tensors of size N ^d , and to the respective discretized differential-integral operators in ℝ ^d . As the basic approximation result, we prove that a complex exponential sampled on an equispaced grid has quantics rank 1. Moreover, a Chebyshev polynomial, sampled over a Chebyshev Gauss–Lobatto grid, has separation rank 2 in the quantics tensor format, while for the polynomial of degree m over a Chebyshev grid the respective quantics rank is at most 2m+1. For N-d tensors generated by certain analytic functions, we give a constructive proof of the O(dlog Nlog ε ⁻¹)-complexity bound for their approximation by low-rank 2-(dlog N) quantics tensors up to the accuracy ε>0. In the case ε=O(N ^−α ), α>0, our approach leads to the quantics tensor numerical method in dimension d, with the nearly optimal asymptotic complexity O(d/αlog ² ε ⁻¹). From numerical examples presented here, we observe that the quantics tensor method has proved its value in application to various function related tensors/matrices arising in computational quantum chemistry and in the traditional finite element method/boundary element method (FEM/BEM). The tool apparently works.     

Uniform mesh approximation to nonsmooth solutions of a singularly perturbed convection-diffusion equation in a rectangle

Here nonsmooth solutions of a differential equation are treated as solutions for which the compatibility conditions are not required to hold at the corner points of the domain and hence corner singularities can occur. In the present paper, we drop the compatibility conditions at three of the four vertices of a rectangle. At the remaining vertex, from which a characteristic (inclined) of the reduced equation issues, we impose compatibility conditions providing the C ^3,λ -smoothness of the desired solution in a neighborhood of that vertex as well as additional conditions leading to the smoothness of solutions of the reduced equation occurring in the regular component of the solution of the considered problem. Under our assumptions and for a sufficient smoothness of the coefficients of the equation and its right-hand side, we show that the classical five-point upwind approximation on a Shishkin piecewise uniform mesh preserves the accuracy specific for the smooth case; i.e., the mesh solution uniformly (with respect to a small parameter) converges in the L _∞ ^h -norm to the exact solution at the rate O(N ⁻¹ ln² N), where N is the number of mesh nodes in each of the coordinate directions.     

Large deviations and concentration properties for ∇ϕ interface models

We consider the massless field with zero boundary conditions outside D _N ≡D∩ (ℤ ^d /N) (N∈ℤ⁺), D a suitable subset of ℝ ^d , i.e. the continuous spin Gibbs measure ℙ _N on ℝ ^ℤd/N with Hamiltonian given by H(ϕ) = ∑ _{x,y:|x−y|=1} V(ϕ(x) −ϕ(y)) and ϕ(x) = 0 for x∈D _N ^C . The interaction V is taken to be strictly convex and with bounded second derivative. This is a standard effective model for a (d + 1)-dimensional interface: ϕ represents the height of the interface over the base D _N . Due to the choice of scaling of the base, we scale the height with the same factor by setting ξ _N = ϕ/N. We study various concentration and relaxation properties of the family of random surfaces {ξ _N } and of the induced family of gradient fields ∇ ^N ξ _N as the discretization step 1/N tends to zero (N→∞). In particular, we prove a large deviation principle for {ξ _N } and show that the corresponding rate function is given by ∫ _D σ(∇u(x))dx, where σ is the surface tension of the model. This is a multidimensional version of the sample path large deviation principle. We use this result to study the concentration properties of ℙ _N under the volume constraint, i.e. the constraint that (1/N ^d ) ∑ _x∈DN ξ _N (x) stays in a neighborhood of a fixed volume v > 0, and the hard–wall constraint, i.e. ξ _N (x) ≥ 0 for all x. This is therefore a model for a droplet of volume v lying above a hard wall. We prove that under these constraints the field {ξ _N of rescaled heights concentrates around the solution of a variational problem involving the surface tension, as it would be predicted by the phenomenological theory of phase boundaries. Our principal result, however, asserts local relaxation properties of the gradient field {∇ ^N ξ _N (·)} to the corresponding extremal Gibbs states. Thus, our approach has little in common with traditional large deviation techniques and is closer in spirit to hydrodynamic limit type of arguments. The proofs have both probabilistic and analytic aspects. Essential analytic tools are ? _p estimates for elliptic equations and the theory of Young measures. On the side of probability tools, a central role is played by the Helffer–Sj?strand [31] PDE representation for continuous spin systems which we rewrite in terms of random walk in random environment and by recent results of T. Funaki and H. Spohn [25] on the structure of gradient fields. Received: 3 March 1999 / Revised version: 9 August 1999 / Published online: 30 March 2000     

A critically loaded multirate link with trunk reservation

We consider a loss system model of interest in telecommunications. There is a single service facility with N servers and no waiting room. There are K types of customers, with type ί customers requiring A _ί servers simultaneously. Arrival processes are Poisson and service times are exponential. An arriving type ί customer is accepted only if there are Rί(⩾A_ί ) idle servers. We examine the asymptotic behavior of the above system in the regime known as critical loading where both N and the offered load are large and almost equal. We also assume that R ₁,..., R _K-1 remain bounded, while R _K ^N ←∞ and R _K ^N /√N ← 0 as N ← ∞. Our main result is that the K dimensional “queue length” process converges, under the appropriate normalization, to a particular K dimensional diffusion. We show that a related system with preemption has the same limit process. For the associated optimization problem where accepted customers pay, we show that our trunk reservation policy is asymptotically optimal when the parameters satisfy a certain relation. This revised version was published online in June 2006 with corrections to the Cover Date.     

The Wirtinger-Steklov inequality between the norm of a periodic function and the norm of the positive cutoff of its derivative

We prove that there is no single uniform tight frame in Euclidean (unitary) space such that a solution of the ℓ ₁-norm minimization problem for the frame representation is attained on the frame coefficients. Then we find an exact solution of the ℓ ₁-minimization problem for the Mercedes-Benz frame in ℝ ^N . We also give some examples of connections between optimization problems of various types.     

Gumbel statistics for the longest interval of identical spins in a one-dimensional Gibbs measure

We consider one-dimensional Gibbs measures on spin configurations σ ∈ {–1,+1}^ℤ. For N ∈ ℕ let l _N denote the length of the longest interval of consecutive spins of the same kind in the interval [0,N]. We show that the distribution of a suitable continuous modification l _c (N) of l _N converges to the Gumbel distribution, i.e., for some α, β ∈ (0, ∞) and γ ∈ ℝ, lim _{N →∞} ℙ(l _c (N) ≤ α log N + βx + γ) = e ^{–e –x} . Received: 2 September 2002     

On a multi-channel change-point problem

A continuous change-point problem is studied in which N independent diffusion processes X _j are observed. Each process X _j is associated with a “channel”, each has an unknown piecewise constant drift and the unit diffusion coefficient. All the channels are connected only by a common change-point of drift. As the result, a change-point problem is defined in which the unknown and unidentifiable drift forms a 2N-dimensional nuisance parameter. The asymptotics of the minimax rate in estimating the change-point is studied as N → ∞. This rate is compared with the case of the known drift. This problem is a special case of an open change-point detection problem in the high-dimensional diffusion with nonparametric drift.      

Approximations for a Three Dimensional Scan Statistic

Let X _ijk ,1 ≤ i ≤ N ₁,1 ≤ j ≤ N ₂, 1 ≤ k ≤ N ₃ be a sequence of independent and identically distributed 0 − 1 Bernoulli trials. X _ijk  = 1 if an event has occurred at the i,j,k ^th location in a three dimensional rectangular region and X _ijk  = 0, otherwise. For 2 ≤ m _j  ≤ N _j  − 1,1 ≤ j ≤ 3, a three dimensional discrete scan statistic is defined as the maximum number of events in any m ₁×m ₂×m ₃ rectangular sub-region in the entire N ₁×N ₂×N ₃ rectangular region. In this article, a product-type approximation and three Poisson approximations are derived for the distribution of this three dimensional scan statistic. Numerical results are presented to evaluate the accuracy of these approximations and their use in testing for randomness.     

Wave atoms and time upscaling of wave equations

We present a new geometric strategy for the numerical solution of hyperbolic wave equations in smoothly varying, two-dimensional time-independent periodic media. The method consists in representing the time-dependent Green’s function in wave atoms, a tight frame of multiscale, directional wave packets obeying a precise parabolic balance between oscillations and support size, namely wavelength ~(diameter).² Wave atoms offer a uniquely structured representation of the Green’s function in the sense that

On a Banach space approximable by Jacobi polynomials

Let X represent either the space C[-1,1] L _p ^(α,β) (w), 1 ≦ p < ∞ on [-1, 1]. Then Xare Banach spaces under the sup or the p norms, respectively. We prove that there exists a normalized Banach subspace X ¹ _αβ of Xsuch that every f ∈ X ¹ _αβ can be represented by a linear combination of Jacobi polynomials to any degree of accuracy. Our method to prove such an approximation problem is Fourier–Jacobi analysis based on the convergence of Fourier–Jacobi expansions. This revised version was published online in June 2006 with corrections to the Cover Date.