Adaptive refinement for convection-diffusion problems based on a defect-correction technique and finite difference method

A difference method is presented for singularly perturbed convection-diffusion problems with discretization error estimates of high order (orderp), which hold uniformly in the singular perturbation parameterε. The method is based on the use of a defect-correction technique and special adaptively graded and patched meshes, with meshsizes varying betweenh andε ^3/2 h whenp=2, whereh is the meshsize, used in the part of the domain where the solution is smooth, andε ^3/2 h is the final meshsize in the boundary layer. Similar constructions hold for interior layers. The correction operator is a monotone operator, enabling the estimate of the error of optimal order in maximum norm. The total number of meshpoints used in ad-dimensional problem isO(ε ^?s)h ^?d+O(h ^?d), wheres is 1/p or 1/2p, respectively in the case of boundary or interior layer.     

Superconvergence of coupling techniques in combined methods for elliptic equations with singularities

Several coupling techniques, such as the nonconforming constraints, penalty, and hybrid integrals, of the Ritz-Galerkin and finite difference methods are presented for solving elliptic boundary value problems with singularities. Based on suitable norms involving discrete solutions at specific points, superconvergence rates on solution derivatives are exploited by using five combinations, e.g., the nonconforming combination, the penalty combination, Combinations I and II, and symmetric combination. For quasi-uniform rectangular grids, the superconvergence rates, O(h^2−δ), of solution derivatives by all five combinations can be achieved, where h is the maximal mesh length of difference grids used in the finite difference method, and δ(> 0) is an arbitrarily small number.Superconvergence analysis in this paper lies in estimates on error bounds caused by the coupling techniques and their incorporation with finite difference methods. Therefore, a similar analysis and conclusions may be extended to linear finite element methods using triangulation by referring to existing references. Moreover, the five combinations having O(h^2−δ) of solution derivatives are well suited to solving engineering problems with multiple singularities and multiple interfaces.     

Curved finite element methods for the solution of singular integral equations on surfaces in R3

We have shown in [1]that the singular integral equation (1.2) on a closed surface Γ of R³ admits a unique solution q and is variational and coercive in the Hilbert space $\text{H}{}^{\mathrm{<mtext>?</mtext><mtext>1</mtext><mtext>2</mtext>}}$(Γ). In this paper, with the help of curved finite elements, we introduce an approximate surface Γ_h, and an approximate problem on Γ_h, whose solution is q_h. Then we study the error of approximation |q ? q_h| in some Hubert spaces and also the associated error |u ? u_h| of the potential.     

A posteriori error estimation for discontinuous Galerkin solutions of hyperbolic problems

We analyze the spatial discretization errors associated with solutions of one-dimensional hyperbolic conservation laws by discontinuous Galerkin methods (DGMs) in space. We show that the leading term of the spatial discretization error with piecewise polynomial approximations of degree p is proportional to a Radau polynomial of degree p+1 on each element. We also prove that the local and global discretization errors are O(Δx^2(p+1)) and O(Δx^2p+1) at the downwind point of each element. This strong superconvergence enables us to show that local and global discretization errors converge as O(Δx^p+2) at the remaining roots of Radau polynomial of degree p+1 on each element. Convergence of local and global discretization errors to the Radau polynomial of degree p+1 also holds for smooth solutions as p→∞. These results are used to construct asymptotically correct a posteriori estimates of spatial discretization errors that are effective for linear and nonlinear conservation laws in regions where solutions are smooth.     

The accuracy of iterated JWBK approximations for Coulomb radial wave functions

Iterated JWBK approximations (IJWBK) can be used for the calculation of Coulomb radial wave functions, for non-negative energies and for values of the radial coordinate, r, such that the functions are oscillatory. Burgess (1963) has given analytical expressions for the first-order IJWBK amplitudes and phases. The second-order theory is discussed. Accurate Coulomb functions are computed using power-series expansions and are used to determine the errors in the zero-, first- and second-order IJWBK approximations. Values of r_l [δ] are given, such that for r > r_l [δ] the errors in the first-order approximation are less than δ, where δ = 10^-3 or 10^-4     

A nonconforming finite element method for a singularly perturbed boundary value problem

We analyze a new nonconforming Petrov-Galerkin finite element method for solving linear singularly perturbed two-point boundary value problems without turning points. The method is shown to be convergent, uniformly in the perturbation parameter, of orderh ^1/2 in a norm slightly stronger than the energy norm. Our proof uses a new abstract convergence theorem for Petrov-Galerkin finite element methods.     

An optimal triangulation for second-order elliptic problems

Let Ω be a polygonal domain in $\text{R}{}^{\mathrm{n}}$, τ_h an associated triangulation and u_h the finite element solution of a well-posed second-order elliptic problem on (Ω, τ_h). Let M = {M_i}^{p + q}_{i = 1} be the set of nodes which defines the vertices of the triangulation τ_h: for each i,$\text{M}{}_{\mathrm{i}}\text{= {x}{}_{\mathrm{i}}{}^{\mathrm{l}}\text{¦1 ? l ?n}}$ in Rⁿ. The object of this paper is to provide a computational tool to approximate the best set of positions M? of the nodes and hence the best triangulation $\text{}\text{?}\text{gt}{}_{\mathrm{h}}$ which minimizes the solution error in the natural norm associated with the problem.The main result of this paper are theorems which provide explicit expressions for the partial derivatives of the associated energy functional with respect to the coordinates x_i^l, 1 ? l ? n, of each of the variable nodes M_i, i = 1,…, p.     

Stability of Galerkin multistep procedures in time-homogeneous hyperbolic problems

Linear and time-homogeneous hyperbolic initial boundary value problems are approximated using Galerkin procedures for the space directions and linear multistep methods for the time direction. At first error bounds are proved for multistep methods having a stability interval [?ω, 0], 0<ω, and systemsY″=AY+C(t) under the condition that \(\Delta t^2 \left\| A \right\| \leqslant \omega \) Δt time step. Then these error bounds are applied to derive bounds for the error in hyperbolic problems. The result shows that the initial error and the discretization error grow liket andt ² respectively. But the initial error is multiplied with a factor which becomes large if the mesh width of the space discretization is small.     

Piecewise cubic monotone interpolation with assigned slopes

An algorithm to construct a monotonicity preserving cubicC ¹ interpolant without modification of the assigned slopes is proposed. AnO(h ⁴) convergence result is obtained when exact function and derivative values are available andO(h ^p ) convergence can be obtained withp=min(4,q) forO(h ^q ) accurate function and derivative values. Numerical experiments carried out on data coming from functions with very different behaviours are presented. The results show that the method can interpolate monotone data in a visually pleasing way, even for data which present rapid variations.     

The fast Fourier transform for general order

An elementary and transparent representation of the fast Fourier transform is given. Instead of using the usual and highly algebraic approach it is shown how a Fourier transform of the ordern=p·m can be reduced top Fourier transforms of orderm by performing essentiallym Fourier transforms of orderp on the data. The resulting process is discussed in more detail forn=3 ^q andn=5 ^q . The problem of retrieval of the wanted coefficients from the final data is solved by a simple argument. The generalization for an ordern equal to a product of powers of prime numbers is immediate.     

Analysis of the efficiency of the Chor-Rivest cryptosystem implementation in a safe-parameter range

The Chor-Rivest cryptosystem, based on a high-density knapsack problem on a finite field F_q^h, was broken by Vaudenay for q≈200,h≈24, and h admitting a factor s verifying a certain condition. A new set of parameters q and h, which prevent this cryptosystem against Vaudenay’s attack, is presented and the computational aspects of its implementation in the Magma computational algebra system are analyzed.     

Optimal Error Estimates for the Fully Discrete Interior Penalty DG Method for the Wave Equation

In Grote et al. (SIAM J. Numer. Anal., 44:2408–2431, 2006) a symmetric interior penalty discontinuous Galerkin (DG) method was presented for the time-dependent wave equation. In particular, optimal a-priori error bounds in the energy norm and the L ²-norm were derived for the semi-discrete formulation. Here the error analysis is extended to the fully discrete numerical scheme, when a centered second-order finite difference approximation (“leap-frog” scheme) is used for the time discretization. For sufficiently smooth solutions, the maximal error in the L ²-norm error over a finite time interval converges optimally as O(h ^p+1+Δt ²), where p denotes the polynomial degree, h the mesh size, and Δt the time step.     

Stability and absolute stability of a three-point difference scheme

Consider a three-point difference scheme −h⁻²Δ⁽²⁾y_n + q_n(h)y_n = f_n(h), n ϵ Z = {0, ±1, ±2, …}, where h ϵ (0, h₀], h₀ is a given positive number, Δ⁽²⁾y_n = y_n+1 + y_n−1, f(h) = {f_n(h)}_{n ϵ Z} ϵ L_∞(h), L_∞(h) = {f(h) : ∥f(h)∥_L∞(h) < ∞}, ∥f(h)∥_L∞(h) = sup_nϵZ ∥f_n(h)∥.We assume a unique a priori requirement 0 <- q_n(h) < ∞ for any n ϵ Z and h ϵ (0, h₀]. The main results are a criterion of stability and absolute stability of the difference scheme (1) in the space L_∞(h).     

Comparison of peak and RMS gains for discrete-time systems

A convolution system can have a frequency response which is small for all frequencies, yet still greatly amplify the peaks of signals passing though it. For finite-dimensional systems, however, we establish the simple bound |h|₁ ≤ (2n + 1) |h|h|_H^∞ where |h|₁ is the peak gain of the system, |h|_H^∞ is the maximum frequency response of the system, and n its dimension. The same result for continuous-time systems is due to Gohberg and Doyle and it is mentioned in [6].The bound implies that H^∞-optimal controllers, which minimize the maximum of some disturbance-to-error transfer function, cannot have very large peak gains from the disturbance to error.     

The finite volume element method with quadratic basis functions

The paper presents a box scheme with quadratic basis functions for the discretisation of elliptic boundary value problems. The resulting discretisation matrix is non-symmetrical (and also not an M-matrix). The stability analysis is based on an elementwise estimation of the scalar product <A _h u _h ,u _h >. Sufficient conditions placed on the triangles of the triangulation lead to discrete ellipticity. Proof of anO(h ²) error estimate is given for these conditions.     

An error bound for approximate solutions of two-point boundary value problems

A new error bound for any approximate solutionu of the two-point boundary value problemAy:=?(py′)′+qy=f,y(0)=0, y(1)=0, is proposed. This error bound depends on the deviationAu?fjust like the one which is proportional to ‖Au?f‖₂, but in the case of Ritz-Galerkin approximations by cubic splines it behaves asymptotically likeh ³, whereh is the knot distance, i.e., it is by one order of magnitude better. An important advantage of this error bound is that it can be used even in the case of generalized solutions and of piecewise linear approximations. An error bound for the approximation of the derivative results also from these considerations. This error bound behaves in the above case asymptotically also likeh ³, i.e. it has the same asymptotic behaviour as the actual approximation error of the derivative.     

The numerical solution of fourth order mildly quasi-linear parabolic initial boundary value problem of second kind

In this article, we report on three-level implicit stable finite difference formulas of O(k ² + h ²) and O(k ² + h ⁴) for the numerical integration of certain mildly quasi-liner fourth order parabolic partial differential equations in one-space dimension. The numerical solution of u _xx is obtained as a by-product of the method. In all cases, we use only (3 + 3 + 3)-grid points and a single computational cell. Difference schemes for the fourth order linear parabolic equation in polar coordinates are also discussed. The stability analysis for the model linear problem is given as a representative example. Numerical results are presented to demonstrate the order and accuracy of the proposed methods.     

A posteriori discontinuous finite element error estimation for two-dimensional hyperbolic problems

We analyze the discontinuous finite element errors associated with p-degree solutions for two-dimensional first-order hyperbolic problems. We show that the error on each element can be split into a dominant and less dominant component and that the leading part is O(h^p+1) and is spanned by two (p+1)-degree Radau polynomials in the x and y directions, respectively. We show that the p-degree discontinuous finite element solution is superconvergent at Radau points obtained as a tensor product of the roots of (p+1)-degree Radau polynomial. For a linear model problem, the p-degree discontinuous Galerkin solution flux exhibits a strong O(h^2p+2) local superconvergence on average at the element outflow boundary. We further establish an O(h^2p+1) global superconvergence for the solution flux at the outflow boundary of the domain. These results are used to construct simple, efficient and asymptotically correct a posteriori finite element error estimates for multi-dimensional first-order hyperbolic problems in regions where solutions are smooth.     

A study ofB-convergence of linearly implicit Runge-Kutta methods

This paper deals withB-convergence analysis of linearly implicit Runge-Kutta methods as applied to stiff, semilinear problems of the formy′(t)=Ty(t)+g(t,y). We analyse the discrepancy between the local and global order reduction. We show that linearly implicit Runge-Kutta methods ofB-consistency orderq have theB-convergence orderq+1 for many singularly perturbed problems with constant stiff part. Numerical examples illustrate the theoretical results.