Superconvergence of Legendre projection methods for the eigenvalue problem of a compact integral operator

In this paper, we consider the Galerkin and collocation methods for the eigenvalue problem of a compact integral operator with a smooth kernel using the Legendre polynomials of degree ≤n. We prove that the error bounds for eigenvalues are of the order O(n^−2r) and the gap between the spectral subspaces are of the orders O(n^−r) in L₂-norm and O(n^1/2−r) in the infinity norm, where r denotes the smoothness of the kernel. By iterating the eigenvectors we show that the iterated eigenvectors converge with the orders of convergence O(n^−2r) in both L₂-norm and infinity norm. We illustrate our results with numerical examples.     

Bounds for the sample size to justify normal approximation of the confidence level

The normal approximation of the confidence level of the standard confidence intervals leaves an error of the order O(1/n) (and not only O(n ^-1/2)). We use the first order term in the error to obtain simple lower bounds for the sample size.     

A fast Fourier-collocation method for second boundary integral equations

In this paper we develop a fast collocation method for second boundary integral equations by the trigonometric polynomials. We propose a convenient way to compress the dense matrix representation of a compact integral operator with a smooth kernel under the Fourier basis and the corresponding collocation functionals. The compression leads to a sparse matrix with only O(nlog²n) number of nonzero entries, where 2n+1 denotes the order of the matrix. Thus we develop a fast Fourier-collocation method. We prove that the fast Fourier-collocation method gives the optimal convergence order up to a logarithmic factor. Moreover, we design a fast scheme for solving the corresponding truncated linear system. We establish that this algorithm preserves the quasi-optimal convergence of the approximate solution with requiring a number of O(nlog³n) multiplications.     

On approximations of transformed chi-squared distributions in statistical applications

We obtain some computable error bounds of order O(n ^?1) for the chi-squared approximation of transformed chi-squared random variables with n degrees of freedom. The results are applied to likelihood ratio statistics in the multivariate case.     

Superconvergence analysis and extrapolation of quasi-Wilson nonconforming finite element method for nonlinear Sobolev equations

Quasi-Wilson nonconforming finite element approximation for a class of nonlinear Sobolev equa-tions is discussed on rectangular meshes. We first prove that this element has two special characters by novel approaches. One is that (▽h ( u-Ihu )1, ▽hvh) h may be estimated as order O ( h2 ) when u ∈ H3 (Ω), where Ihu denotes the bilinear interpolation of u , vh is a polynomial belongs to quasi-Wilson finite element space and ▽h denotes the piecewise defined gradient operator, h is the mesh size tending to zero. The other is that the consistency error of this element is of order O ( h2 ) /O ( h3 ) in broken H 1-norm, which is one/two order higher than its interpolation error when u ∈ H3 (Ω) /H4 (Ω). Then we derive the optimal order error estimate and su- perclose property via mean-value method and the known high accuracy result of bilinear element. Furthermore, we deduce the global superconvergence through interpolation post processing technique. At last, an extrapola- tion result of order O ( h3 ), two order higher than traditional error estimate, is obtained by constructing a new suitable extrapolation scheme.     

Non-uniform bounds for short asymptotic expansions in the CLT for balls in a Hilbert space

We consider short asymptotic expansions for the probability of a sum of i.i.d. random elements to hit a ball in a Hilbert space H. The error bound for the expansion is of order O(n^-1). It depends on the first 12 eigenvalues of the covariance operator only. Moreover, the bound is non-uniform, i.e. the accuracy of the approximation becomes better as the distance between a boundary of the ball and the origin in H grows.     

Fast Fourier-Galerkin methods for solving singular boundary integral equations: Numerical integration and precondition

We develop a fast fully discrete Fourier-Galerkin method for solving a class of singular boundary integral equations. We prove that the number of multiplications used in generating the compressed matrix is O(nlog³n), and the solution of the proposed method preserves the optimal convergence order O(n^−t), where n is the order of the Fourier basis functions used in the method and t denotes the degree of regularity of the exact solution. Moreover, we propose a preconditioning which ensures the numerical stability when solving the preconditioned linear system. Numerical examples are presented to confirm the theoretical estimates and to demonstrate the approximation accuracy and computational efficiency of the proposed algorithm.     

Berry-Esseen bounds for wavelet estimator in a regression model with linear process errors

In this paper, we derive the Berry-Esseen bounds of the wavelet estimator for a nonparametric regression model with linear process errors generated by φ-mixing sequences. As application, by the suitable choice of some constants, the convergence rate O(n^−1/6) of uniformly asymptotic normality of the wavelet estimator is obtained. Our results generalize some known results in the literature.     

A priori error analysis of a discontinuous Galerkin approximation for a kind of compressible miscible displacement problems

A kind of compressible miscible displacement problems which include molecular diffusion and dispersion in porous media are investigated.A symmetric interior penalty discontinuous Galerkin (SIPG) method is applied to the coupled system of flow and transport.Using the induction hypotheses instead of the cut-off operator and the interpolation projection properties,a priori hp error estimates are presented.The error bounds in L2(H1) norm for concentration and in L∞(L2) norm for velocity are optimal in h and suboptimal in p with a loss of power 1/2.     

Linear information for approximation of the Itô integrals

We study optimal approximation of stochastic integrals in the Itô sense when linear information, consisting of certain integrals of trajectories of Brownian motion, is available. Upper bounds on the nth minimal error, where n is the fixed cardinality of information, are obtained by the Wagner–Platen algorithm and are O(n ^???3/2) or O(n ^???2), depending on considered class of integrands. We also show that Ω(n ^???2) is a lower bound which holds even for very smooth integrands.     

Norms of powers of matrices with constrained spectra

If a matrix A of unit norm on n-dimensional Hilbert space has eigenvalues close to zero, then 6Aⁿ6 must be small. It is proved here that 6Aⁿ6 ?nr+O(r²), where r is the spectral radius of A, and the rate at which 6Aⁿ6 can approach 1 as r→1 is also ascertained [1?6Aⁿ6? O((1?r)^2n?1)]. More precise bounds for 6Aⁿ6 are obtained, some in terms of r and others in terms of all the eigenvalues of A.     

A discontinuous Galerkin method for time fractional diffusion equations with variable coefficients

We propose a piecewise-linear, time-stepping discontinuous Galerkin method to solve numerically a time fractional diffusion equation involving Caputo derivative of order μ ∈ (0, 1) with variable coefficients. For the spatial discretization, we apply the standard continuous Galerkin method of total degree ≤ 1 on each spatial mesh elements. Well-posedness of the fully discrete scheme and error analysis will be shown. For a time interval (0, T) and a spatial domain Ω, our analysis suggest that the error in \(L^{2}\left ((0,T),L^{2}({\Omega })\right )\)-norm is \(O(k^{2-\frac {\mu }{2}}+h^{2})\) (that is, short by order \(\frac {\mu }{2}\) from being optimal in time) where k denotes the maximum time step, and h is the maximum diameter of the elements of the (quasi-uniform) spatial mesh. However, our numerical experiments indicate optimal O(k² + h²) error bound in the stronger \(L^{\infty }\left ((0,T),L^{2}({\Omega })\right )\)-norm. Variable time steps are used to compensate the singularity of the continuous solution near t = 0.     

EQ 1 rot nonconforming finite element method for nonlinear dual phase lagging heat conduction equations

EQ rot 1 nonconforming finite element approximation to a class of nonlinear dual phase lagging heat conduction equations is discussed for semi-discrete and fully-discrete schemes. By use of a special property, that is, the consistency error of this element is of order O(h2 ) one order higher than its interpolation error O(h), the superclose results of order O(h2 ) in broken H1 -norm are obtained. At the same time, the global superconvergence in broken H1 -norm is deduced by interpolation postprocessing technique. Moreover, the extrapolation result with order O(h4 ) is derived by constructing a new interpolation postprocessing operator and extrapolation scheme based on the known asymptotic expansion formulas of EQ rot 1 element. Finally, optimal error estimate is gained for a proposed fully-discrete scheme by different approaches from the previous literature.     

Empty pseudo-triangles in point sets

We study empty pseudo-triangles in a set P of n points in the plane, where an empty pseudo-triangle has its vertices at the points of P, and no points of P lie inside. We give bounds on the minimum and maximum number of empty pseudo-triangles. If P lies inside a triangle whose corners must be the convex vertices of the pseudo-triangle, then there can be between Θ(n²) and Θ(n³) empty pseudo-triangles. If the convex vertices of the pseudo-triangle are also chosen from P, this number lies between Θ(n³) and Θ(n⁶). If we count only star-shaped pseudo-triangles, the bounds are Θ(n²) and Θ(n⁵). We also study optimization problems: minimizing or maximizing the perimeter or the area over all empty pseudo-triangles defined by P. If P lies inside a triangle whose corners must be used, we can solve these problems in O(n³) time. In the general case, the running times are O(n⁶) for the maximization problems and O(nlogn) for the minimization problems.     

Stability and convergence of fully discrete finite element schemes for the acoustic wave equation

In this paper, we investigate the stability and convergence of some fully discrete finite element schemes for solving the acoustic wave equation where a discontinuous Galerkin discretization in space is used. We first review and compare conventional time-stepping methods for solving the acoustic wave equation. We identify their main properties and investigate their relationship. The study includes the Newmark algorithm which has been used extensively in applications. We present a rigorous stability analysis based on the energy method and derive sharp stability results covering some well-known CFL conditions. A convergence analysis is carried out and optimal a priori error estimates are obtained. For sufficiently smooth solutions, we demonstrate that the maximal error in the L ²-norm error over a finite time interval converges optimally as O(h ^p+1+??t ^s ), where p denotes the polynomial degree, s=1 or 2, h the mesh size, and ??t the time step.     

Rectangular arrays

In this paper we studied m×n arrays with row sums $\text{nr}\text{(n,m)}$ and column sums $\text{mr}\text{(n,m)}$ where (n,m) denotes the greatest common divisor of m and n. We were able to show that the function H_m,n(r), which enumerates m×n arrays with row sums and column sums $\text{nr}\text{(m,n)}$ and $\text{mr}\text{(n,m)}$ respectively, is a polynomial in r of degree (m?1)(n?1). We found simple formulas to evaluate these polynomials for negative values, ?r, and we show that certain small negative integers are roots of these polynomials. When we considered the generating function G_m,n(y) = Σ_r?0H_m,n(r)y^r, it was found to be rational of degree less than zero. The denominator of G_m,n(y) is of the form (1?y)^(m?1)(n?1)+3, and the coefficients of the numerator are non-negative integers which enjoy a certain symmetric relation.     

Application of fast spherical Fourier transform to density estimation

This paper is on density estimation on the 2-sphere, S², using the orthogonal series estimator corresponding to spherical harmonics. In the standard approach of truncating the Fourier series of the empirical density, the Fourier transform is replaced with a version of the discrete fast spherical Fourier transform, as developed by Driscoll and Healy. The fast transform only applies to quantitative data on a regular grid. We will apply a kernel operator to the empirical density, to produce a function whose values at the vertices of such a grid will be the basis for the density estimation. The proposed estimation procedure also contains a deconvolution step, in order to reduce the bias introduced by the initial kernel operator. The main issue is to find necessary conditions on the involved discretization and the bandwidth of the kernel operator, to preserve the rate of convergence that can be achieved by the usual computationally intensive Fourier transform. Density estimation is considered in L²(S²) and more generally in Sobolev spaces H_v(S²), any v?0, with the regularity assumption that the probability density to be estimated belongs to H_s(S²) for some s>v. The proposed technique to estimate the Fourier transform of an unknown density keeps computing cost down to order O(n), where n denotes the sample size.     

Unbounded knapsack problems with arithmetic weight sequences

We investigate a special case of the unbounded knapsack problem in which the item weights form an arithmetic sequence. We derive a polynomial time algorithm for this special case with running time O(n⁸), where n denotes the number of distinct items in the instance. Furthermore, we extend our approach to a slightly more general class of knapsack instances.     

Enumeration of arrays of a given size

Enumeration of arrays whose row and column sums are specified have been studied by a number of people. It has been determined that the function that enumerates square arrays of dimension n, whose rows and columns sum to a fixed non-negative integer r, is a polynomial in r of degree (n ? 1)².In this paper we consider rectangular arrays whose rows sum to a fixed non-negative integer r and whose columns sum to a fixed non-negative integer s, determined by ns = mr. in particular, we show that the functions which enumerate 2 × n and 3 × n arrays with fixed row sums $\text{nr}\text{(2, n)}$ and $\text{nr}\text{(3, n)}$, where the symbol (a, b) denotes the greatest common divisor of a and b, and fixed column sums, are polynomials in r of degrees (n ? 1) and 2(n ? 1) respectively. We have found simple formulas to evaluate these polynomials for negative values, - r, and we show that for certain small negative integers our polynomials will always be zero. We also considered the generating functions of these polynomials and show that they are rational functions of degrees less than zero, whose denominators are of the forms (1 ? y)ⁿ and (1 ? y)²ⁿ?1 respectively and whose numerators are polynomials in y whose coefficients satisfy certain properties. In the last section we list the actual polynomials and generating functions in the 2 × n and 3 × n cases for small specific values of n.     

Bound reduction using pairs of linear inequalities

We describe a procedure to reduce variable bounds in mixed integer nonlinear programming (MINLP) as well as mixed integer linear programming (MILP) problems. The procedure works by combining pairs of inequalities of a linear programming (LP) relaxation of the problem. This bound reduction procedure extends the feasibility based bound reduction technique on linear functions, used in MINLP and MILP. However, it can also be seen as a special case of optimality based bound reduction, a method to infer variable bounds from an LP relaxation of the problem. For an LP relaxation with m constraints and n variables, there are O(m ²) pairs of constraints, and a naïve implementation of our bound reduction scheme has complexity O(n ³) for each pair. Therefore, its overall complexity O(m ² n ³) can be prohibitive for relatively large problems. We have developed a more efficient procedure that has complexity O(m ² n ²), and embedded it in two Open-Source solvers: one for MINLP and one for MILP. We provide computational results which substantiate the usefulness of this bound reduction technique for several instances.