Piecewise-linear,discontinuous Galerkin method for a fractional diffusion equation

We use a piecewise-linear, discontinuous Galerkin method for the time discretization of a fractional diffusion equation involving a parameter in the range − 1 < α < 0. Our analysis shows that, for a time interval (0,T) and a spatial domain Ω, the error in L_￥((0,T);L₂(W))L_\infty\bigr((0,T);L_2(\Omega)\bigr) is of order k ^2 + α , where k denotes the maximum time step. Since derivatives of the solution may be singular at t = 0, our result requires the use of non-uniform time steps. In the limiting case α = 0 we recover the known O(k ²) convergence for the classical diffusion (heat) equation. We also consider a fully-discrete scheme that employs standard (continuous) piecewise-linear finite elements in space, and show that the additional error is of order h ²log(1/k). Numerical experiments indicate that our O(k ^2 + α ) error bound is pessimistic. In practice, we observe O(k ²) convergence even for α close to − 1.     

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.     

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

Some Exponential Inequalities for Positively Associated Random Variables and Rates of Convergence of the Strong Law of Large Numbers

We present some exponential inequalities for positively associated unbounded random variables. By these inequalities, we obtain the rate of convergence n ^−1/2 β _n log ^3/2 n in which β _n can be particularly taken as (log log n)^1/σ with any σ>2 for the case of geometrically decreasing covariances, which is faster than the corresponding one n ^−1/2(log log n)^1/2log ² n obtained by Xing, Yang, and Liu in J. Inequal. Appl., doi: (2008) for the case mentioned above, and derive the convergence rate n ^−1/2 β _n log ^1/2 n for the above β _n under the given covariance function, which improves the relevant one n ^−1/2(log log n)^1/2log n obtained by Yang and Chen in Sci. China, Ser. A 49(1), 78–85 (2006) for associated uniformly bounded random variables. In addition, some moment inequalities are given to prove the main results, which extend and improve some known results.     

Kinetic Spanners in ℝ<Superscript><Emphasis Type="Italic">d</Emphasis></Superscript>

We present a new (1+ε)-spanner for sets of n points in ℝ ^d . Our spanner has size O(n/ε ^d−1) and maximum degree O(log  ^d n). The main advantage of our spanner is that it can be maintained efficiently as the points move: Assuming that the trajectories of the points can be described by bounded-degree polynomials, the number of topological changes to the spanner is O(n ²/ε ^d−1), and using a supporting data structure of size O(nlog  ^d n), we can handle events in time O(log  ^d+1 n). Moreover, the spanner can be updated in time O(log n) if the flight plan of a point changes. This is the first kinetic spanner for points in ℝ ^d whose performance does not depend on the spread of the point set.     

New Expressions for Repeated Upper Tail Integrals of the Normal Distribution

Expressions are given for repeated upper tail integrals of the univariate normal density (and so also for the general Hermite function) for both positive and negative arguments. The expressions involve moments of the form E(x + i N) ⁿ and E1 / (x ² + N ²) ⁿ , where N is a unit normal random variable. Laplace transforms are provided for the Hermite functions and the moments. The practical use of these expressions is illustrated.     

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.     

Anharmonic Oscillators in the Complex Plane, $\boldsymbol{\mathcal{PT}}$-symmetry,and Real Eigenvalues

For integers m ≥ 3 and 1 ≤ ℓ ≤ m − 1, we study the eigenvalue problems − u ^″(z) + [( − 1)^ℓ(iz) ^m  − P(iz)]u(z) = λu(z) with the boundary conditions that u(z) decays to zero as z tends to infinity along the rays argz=-\fracp2±\frac(l+1)pm+2\arg z=-\frac{\pi}{2}\pm \frac{(\ell+1)\pi}{m+2} in the complex plane, where P is a polynomial of degree at most m − 1. We provide asymptotic expansions of the eigenvalues λ _n . Then we show that if the eigenvalue problem is PT\mathcal{PT}-symmetric, then the eigenvalues are all real and positive with at most finitely many exceptions. Moreover, we show that when gcd(m,l)=1\gcd(m,\ell)=1, the eigenvalue problem has infinitely many real eigenvalues if and only if one of its translations or itself is PT\mathcal{PT}-symmetric. Also, we will prove some other interesting direct and inverse spectral results.     

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.     

On the asymptotics of the eigenvalue counting function for random recursive Sierpinski gaskets

We consider natural Laplace operators on random recursive affine nested fractals based on the Sierpinski gasket and prove an analogue of Weyl’s classical result on their eigenvalue asymptotics. The eigenvalue counting function N(λ) is shown to be of order λ ^ds/2 as λ→∞ where we can explicitly compute the spectral dimension d _s . Moreover the limit N(λ) λ ^−ds/2 will typically exist and can be expressed as a deterministic constant multiplied by a random variable. This random variable is a power of the limiting random variable in a suitable general branching process and has an interpretation as the volume of the fractal. Received: 22 January 1999 / Revised version: 2 September 1999 /?Published online: 30 March 2000     

Quasi-<Emphasis Type="Italic">L</Emphasis><Superscript><Emphasis Type="Italic">p</Emphasis></Superscript> norm orthogonal Galerkin expansions in sums of Jacobi polynomials

In the study of differential equations on [ − 1,1] subject to linear homogeneous boundary conditions of finite order, it is often expedient to represent the solution in a Galerkin expansion, that is, as a sum of basis functions, each of which satisfies the given boundary conditions. In order that the functions be maximally distinct, one can use the Gram-Schmidt method to generate a set orthogonal with respect to a particular weight function. Here we consider all such sets associated with the Jacobi weight function, w(x) = (1 − x) ^α (1 + x) ^β . However, this procedure is not only cumbersome for sets of large degree, but does not provide any intrinsic means to characterize the functions that result. We show here that each basis function can be written as the sum of a small number of Jacobi polynomials, whose coefficients are found by imposing the boundary conditions and orthogonality to the first few basis functions only. That orthogonality of the entire set follows—a property we term “auto-orthogonality”—is remarkable. Additionally, these basis functions are shown to behave asymptotically like individual Jacobi polynomials and share many of the latter’s useful properties. Of particular note is that these basis sets retain the exponential convergence characteristic of Jacobi expansions for expansion of an arbitrary function satisfying the boundary conditions imposed. Further, the associated error is asymptotically minimized in an L ^p(α) norm given the appropriate choice of α = β. The rich algebraic structure underlying these properties remains partially obscured by the rather difficult form of the non-standard weighted integrals of Jacobi polynomials upon which our analysis rests. Nevertheless, we are able to prove most of these results in specific cases and certain of the results in the general case. However a proof that such expansions can satisfy linear boundary conditions of arbitrary order and form appears extremely difficult.     

Interpolation of rational functions by simple partial fractions

We study a generalized interpolation of a rational function at n nodes by a simple partial fraction of degree n and reduce the consideration to the solvability question for a special difference equation. We construct explicit interpolation formulas in the case where the equation order is equal to 1. We show that for functions A(x − a) ^m , m ? \mathbbN m \in \mathbb{N} , it is possible to reduce the consideration to a system of m + 1 independent first order equations and construct explicit interpolation formulas. Bibliography: 6 titles.     

Asymptotic stability and instability criteria for nonautonomous systems

The classical criterion of asymptotic stability of the zero solution of equations x′ = f(t, x) is that there exists a function V (t, x), a(∥x∥) ≤ V (t, x) ≤ b(∥x∥) for some a, b ∈ K such that [(V)\dot] \dot{V} (t, x) ≤ −c(∥x∥) for some c ∈ K. In this paper, we prove that if V^{(m + 1)} \mathop {V}\limits^{(m + {1})} (t, x) is bounded on some set [tk − T, tk + T] × BH(tk → +∞ as k → ∞), then the condition that [(V)\dot] \dot{V} (t, x) ≤ −c(∥x∥) can be weakened and replaced by that [(V)\dot] \dot{V} (t, x) ≤ 0 and − (−[(V)\dot] \dot{V} (tk, x)| + − [(V)\ddot] \ddot{V} (tk, x)| + ⋯ + − V^(m) \mathop {V}\limits^{(m)} (tk, x)|) ≤ −c′(∥x∥) for some c′ ∈ K. Moreover, the author also presents a corresponding instability criterion. [1–10]     

On the negative Pell equation

Let ε be the fundamental unit of a field Q( ?d ) Q\left( {\sqrt {d} } \right) . In the paper, it is proved that ε > d ^3/2/ log² d for almost all d such that N(ε) = −1. Bibliography: 6 titles.     

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     

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.     

A note on the Lehmer problem over short intervals

Let p be an odd prime, c be an integer with (c, p) = 1, and let N be a positive integer with N ≤ p − 1. Denote by r(N, c; p) the number of integers a satisfying 1 ≤ a ≤ N and 2 ∤ a + ā, where ā is an integer with 1 ≤ ā ≤ p − 1, aā ≡ c (mod p). It is well known that r(N, c; p) = 1/2N + O(p ^1/2log² p). The main purpose of this paper is to give an asymptotic formula for Σ _c=1 ^p−1(r(N, c; p) − 1/2N)².     

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     

Weighted compound integration rules with higher order convergence for all N

Quasi-Monte Carlo integration rules, which are equal-weight sample averages of function values, have been popular for approximating multivariate integrals due to their superior convergence rate of order close to 1/N or better, compared to the order 1/?N1/\sqrt{N} of simple Monte Carlo algorithms. For practical applications, it is desirable to be able to increase the total number of sampling points N one or several at a time until a desired accuracy is met, while keeping all existing evaluations. We show that although a convergence rate of order close to 1/N can be achieved for all values of N (e.g., by using a good lattice sequence), it is impossible to get better than order 1/N convergence for all values of N by adding equally-weighted sampling points in this manner. We then prove that a convergence of order N ^− α for α > 1 can be achieved by weighting the sampling points, that is, by using a weighted compound integration rule. We apply our theory to lattice sequences and present some numerical results. The same theory also applies to digital sequences.