A priori error estimates for interior penalty versions of the local discontinuous Galerkin method applied to transport equations

The local discontinuous Galerkin method has been developed recently by Cockburn and Shu for convection‐dominated convection‐diffusion equations. In this article, we consider versions of this method with interior penalties for the numerical solution of transport equations, and derive a priori error estimates. We consider two interior penalty methods, one that penalizes jumps in the solution across interelement boundaries, and another that also penalizes jumps in the diffusive flux across such boundaries. For the first penalty method, we demonstrate convergence of order k in the L^∞(L²) norm when polynomials of minimal degree k are used, and for the second penalty method, we demonstrate convergence of order k+1/2. Through a parabolic lift argument, we show improved convergence of order k+1/2 (k+1) in the L²(L²) norm for the first penalty method with a penalty parameter of order one (h^?1). © 2001 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 17: 545–564, 2001     

Convergence analysis of a discontinuous Galerkin method for a sub-diffusion equation

We employ a piecewise-constant, discontinuous Galerkin method for the time discretization of a sub-diffusion equation. Denoting the maximum time step by k, we prove an a priori error bound of order k under realistic assumptions on the regularity of the solution. We also show that a spatial discretization using continuous, piecewise-linear finite elements leads to an additional error term of order h ² max (1,logk ^− 1). Some simple numerical examples illustrate this convergence behaviour in practice. We thank the University of New South Wales for financial support provided by a Faculty Research Grant.     

Finite Element Methods for Parabolic Stochastic PDE’s

We study the rate of convergence of some explicit and implicit numerical schemes for the solution of a parabolic stochastic partial differential equation driven by white noise. These include the forward and backward Euler and the Crank–Nicholson schemes. We use the finite element method. We find, as expected, that the rates of convergence are substantially similar to those found for finite difference schemes, at least when the size of the time step k is on the order of the square of the size of the space step h: all the schemes considered converge at a rate on the order of h^1/2+k^1/4, which is known to be optimal. We also consider cases where k is much greater than h², and find that only the backward Euler method always attains the optimal rate; other schemes, even though they are stable, can fail to convergence to the true solution if the time step is too long relative to the space step. The Crank–Nicholson scheme behaves particularly badly in this case, even though it is a higher-order method. Mathematics Subject Classifications (2000) 60H15, 60H35, 65N30, 35R60.     

A quadrature-based approach to improving the collocation method

Summary The collocation method is a popular method for the approximate solution of boundary integral equations, but typically does not achieve the high order of convergence reached by the Galerkin method in appropriate negative norms. In this paper a quadrature-based method for improving upon the collocation method is proposed, and developed in detail for a particular case. That case involves operators with even symbol (such as the logarithmic potential) operating on 1-periodic functions; a smooth-spline trial space of odd degree, with constant mesh spacingh=1/n; and a quadrature rule with 2n points (where ann-point quadrature rule would be equivalent to the collocation method). In this setting it is shown that a special quadrature rule (which depends on the degree of the splines and the order of the operator) can yield a maximum order of convergence two powers ofh higher than the collocation method.     

Finite element methods for symmetric hyperbolic equations

A finite difference method for the solution of symmetric positive differential equations has already been developped (Katsanis [4]). The finite difference solutions where shown to converge at the rateO(ith ^1/2) ash approaches zero,h being the maximum distance between two adjacent mesh points. Here we try to get a better rate of convergence, using a Rayleigh Ritz Galerkin method. We first give a “weak” formulation of the equations, slightly different from the usual one (Friedrichs [3]), in order to take into account the boundary conditions. We define a finite dimensional subspaceV _h ofH ¹(Ω), in which we look for an approximate solutionu _h . We show that when the exact solutionu is smooth enough, we get the error estimate: $$\left| {u - u_h } \right|L^2 (\Omega ) \leqq C\mathop {\inf }\limits_{v_h \in V_h } \left\{ {\left\| {u - v_h } \right\|H^1 (\Omega ) + \mathop {\sup }\limits_{w_h \in V_h } \frac{{\int\limits_\Gamma {\left| {u - v_h } \right|\left| {w_h } \right|d\Gamma } }}{{\left| {w_h } \right|L^2 (\Omega )}}} \right\}$$ where |·| denotes the Euclidean norm inR ^P . Thus, as is the case for elliptic or parabolic equations, the problem of estimating the error is reduced to questions in approximation theory. When those results are applied to finite element methods, with polynomial approximations of degree ≦k over eachn-simplex we obtain a rate of convergence ofO(h ^k) ash approaches zero,h being the supremum of the diameters of then-simplices.     

Modified Lagrange–Galerkin methods of first and second order in time for convection–diffusion problems

We introduce modified Lagrange–Galerkin (MLG) methods of order one and two with respect to time to integrate convection–diffusion equations. As numerical tests show, the new methods are more efficient, but maintaining the same order of convergence, than the conventional Lagrange–Galerkin (LG) methods when they are used with either P ₁ or P ₂ finite elements. The error analysis reveals that: (1) when the problem is diffusion dominated the convergence of the modified LG methods is of the form O(h ^m+1 + h ² + Δt ^q ), q = 1 or 2 and m being the degree of the polynomials of the finite elements; (2) when the problem is convection dominated and the time step Δt is large enough the convergence is of the form O(\frach^m+1Dt+h²+Dt^q){O(\frac{h^{m+1}}{\Delta t}+h^{2}+\Delta t^{q})} ; (3) as in case (2) but with Δt small, then the order of convergence is now O(h ^m  + h ² + Δt ^q ); (4) when the problem is convection dominated the convergence is uniform with respect to the diffusion parameter ν (x, t), so that when ν → 0 and the forcing term is also equal to zero the error tends to that of the pure convection problem. Our error analysis shows that the conventional LG methods exhibit the same error behavior as the MLG methods but without the term h ². Numerical experiments support these theoretical results.     

Extended iterative methods for the solution of operator equations

Summary Given an iterative methodM ₀, characterized byx ^(k+1=G ₀(x( ^k )) (k0) (x(⁰) prescribed) for the solution of the operator equationF(x)=0, whereF:XX is a given operator andX is a Banach space, it is shown how to obtain a family of methodsM _p characterized byx ^(k+1=G _p (x( ^k )) (k0) (x(⁰) prescribed) with order of convergence higher than that ofM _o. The infinite dimensional multipoint methods of Bosarge and Falb [2] are a special case, in whichM ₀ is Newton's method.Analogues of Theorems 2.3 and 2.36 of [2] are proved for the methodsM _p, which are referred to as extensions ofM ₀. A number of methods with order of convergence greater than two are discussed and existence-convergence theorems for some of them are proved.Finally some computational results are presented which illustrate the behaviour of the methods and their extensions when used to solve systems of nonlinear algebraic equations, and some applications currently being investigated are mentioned.     

Superconvergence of H 1-Galerkin mixed finite element methods for parabolic problems

In this article, we study the semidiscrete H ¹-Galerkin mixed finite element method for parabolic problems over rectangular partitions. The well-known optimal order error estimate in the L ²-norm for the flux is of order 𝒪(h ^k+1) (SIAM J. Numer. Anal. 35 (2), (1998), pp. 712–727), where k ≥ 1 is the order of the approximating polynomials employed in the Raviart–Thomas element. We derive a superconvergence estimate of order 𝒪(h ^k+3) between the H ¹-Galerkin mixed finite element approximation and an appropriately defined local projection of the flux variable when k ≥ 1. A the new approximate solution for the flux with superconvergence of order 𝒪(h ^k+3) is realized via a postprocessing technique using local projection methods.     

Galerkin discontinuous approximation of the transport equation and viscoelastic fluid flow on quadrilaterals

Numerical simulation of industrial processes involving viscoelastic liquids is often based on finite element methods on quadrilateral meshes. However, numerical analysis of these methods has so far been limited to triangular meshes. In this work, we consider quadrilateral meshes. We first study the approximation of the transport equation by a Galerkin discontinuous method and prove an 𝒪(h^k+1/2) error estimates for the Q_k finite element. Then we study a differential model for viscoelastic flow with unknowns u the velocity, p the pressure, and σ the viscoelastic part of the extra-stress tensor. The approximations are ((Q₁)² transforms of) Q_k+1 continuous for u, Q_k discontinuous for σ, and P_k discontinuous for p, with k ≥ 1. Upwinding for σ is obtained by the Galerkin discontinuous method. We show that an error estimate of order 𝒪(h^k+1/2) is valid in the energy norm for the three unknowns. © 1998 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 14: 97–114, 1998     

Galerkin finite element method and error analysis for the fractional cable equation

The cable equation is one of the most fundamental equations for modeling neuronal dynamics. These equations can be derived from the Nernst-Planck equation for electro-diffusion in smooth homogeneous cylinders. Fractional cable equations are introduced to model electrotonic properties of spiny neuronal dendrites. In this paper, a Galerkin finite element method(GFEM) is presented for the numerical simulation of the fractional cable equation(FCE) involving two integro-differential operators. The proposed method is based on a semi-discrete finite difference approximation in time and Galerkin finite element method in space. We prove that the numerical solution converges to the exact solution with order O(τ+h^l+1) for the lth-order finite element method. Further, a novel Galerkin finite element approximation for improving the order of convergence is also proposed. Finally, some numerical results are given to demonstrate the theoretical analysis. The results show that the numerical solution obtained by the improved Galerkin finite element approximation converges to the exact solution with order O(τ²+h^l+1).     

Correction of Numerov's eigenvalue estimates

Summary The error in the estimate of thekth eigenvalue of a regular Sturm-Liouville problem obtained by Numerov's method with mesh lengthh isO(k ⁶ h ⁴). We show that a simple correction technique of Paine, de Hoog and Anderssen reduces the error to one ofO(k ³ h ⁴). Numerical examples demonstrate the usefulness of this correction even for low values ofk.     

Compact difference schemes for heat equation with Neumann boundary conditions (II)

This is the further work on compact finite difference schemes for heat equation with Neumann boundary conditions subsequent to the paper, [Sun, Numer Methods Partial Differential Equations (NMPDE) 25 (2009), 1320–1341]. A different compact difference scheme for the one‐dimensional linear heat equation is developed. Truncation errors of the proposed scheme are O(τ² + h⁴) for interior mesh point approximation and O(τ² + h³) for the boundary condition approximation with the uniform partition. The new obtained scheme is similar to the one given by Liao et al. (NMPDE 22 (2006), 600–616), while the major difference lies in no extension of source terms to outside the computational domain any longer. Compared with ones obtained by Zhao et al. (NMPDE 23 (2007), 949–959) and Dai (NMPDE 27 (2011), 436–446), numerical solutions at all mesh points including two boundary points are computed in our new scheme. The significant advantage of this work is to provide a rigorous analysis of convergence order for the obtained compact difference scheme using discrete energy method. The global accuracy is O(τ² + h⁴) in discrete maximum norm, although the spatial approximation order at the Neumann boundary is one lower than that for interior mesh points. The analytical techniques are important and can be successfully used to solve the open problem presented by Sun (NMPDE 25 (2009), 1320–1341), where analyzed theoretical convergence order of the scheme by Liao et al. (NMPDE 22 (2006), 600–616) is only O(τ² + h^3.5) while the numerical accuracy is O(τ² + h⁴), and convergence order of theoretical analysis for the scheme by Zhao et al. (NMPDE 23 (2007), 949–959) is O(τ² + h^2.5), while the actual numerical accuracy is O(τ² + h³). Following the procedure used for the new obtained difference scheme in this work, convergence orders of these two schemes can be proved rigorously to be O(τ² + h⁴) and O(τ² + h³), respectively. Meanwhile, extension to the case involving the nonlinear reaction term is also discussed, and the global convergence order O(τ² + h⁴) is proved. A compact ADI difference scheme for solving two‐dimensional case is derived. Finally, several examples are given to demonstrate the numerical accuracy of new obtained compact difference schemes. © 2012 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2013     

Onk-step methods with almost constant coefficients

A class ofk-step methods where the coefficients are functions ofh andf/y is studied. It is shown that stability and consistency are necessary and sufficient for convergence, and that we can find stable methods of any order k+1 (ork+2 ifk is even) that are not weakly stable.     

Superconvergence of the direct discontinuous Galerkin method for a time‐fractional initial‐boundary value problem

A time‐fractional reaction–diffusion initial‐boundary value problem with periodic boundary condition is considered on Q ? Ω × [0, T] , where Ω is the interval [0, l] . Typical solutions of such problem have a weak singularity at the initial time t = 0. The numerical method of the paper uses a direct discontinuous Galerkin (DDG) finite element method in space on a uniform mesh, with piecewise polynomials of degree k ≥ 2 . In the temporal direction we use the L1 approximation of the Caputo derivative on a suitably graded mesh. We prove that at each time level of the mesh, our L1‐DDG solution is superconvergent of order k + 2 in L²(Ω) to a particular projection of the exact solution. Moreover, the L1‐DDG solution achieves superconvergence of order (k + 2) in a discrete L²(Q) norm computed at the Lobatto points, and order (k + 1) superconvergence in a discrete H¹(Q) seminorm at the Gauss points; numerical results show that these estimates are sharp.     

Further results on ultraconvergence derivative recovery for odd-order rectangular finite elements

For rectangular finite element, we give a superconvergence method by SPR technique based on the generalization of a new ultraconvergence record and the sharp Green function estimates, by which we prove that the derivative has ultra-convergence of order O(h ^k+3) (k ⩾ 3 being odd) and displacement has order of O(h ^k+4) (k ⩾ 4 being even) at the locally symmetry points.      

Tension spline solution of nonlinear sine-Gordon equation

The sine-Gordon equation plays an important role in modern physics. By using spline function approximation, two implicit finite difference schemes are developed for the numerical solution of one-dimensional sine-Gordon equation. Stability analysis of the method has been given. It has been shown that by choosing the parameters suitably, we can obtain two schemes of orders O(k²+k²h²+h²)\mathcal{O}(k^{2}+k^{2}h^{2}+h^{2}) and O(k²+k²h²+h⁴)\mathcal{O}(k^{2}+k^{2}h^{2}+h^{4}). At the end, some numerical examples are provided to demonstrate the effectiveness of the proposed schemes.     

Contractible edges in triangle-free graphs

An edge of a graph is calledk-contractible if the contraction of the edge results in ak-connected graph. Thomassen [5] proved that everyk-connected graph of girth at least four has ak-contractible edge. In this paper, we study the distribution ofk-contractible edges in triangle-free graphs and show the following: Whenk≧2, everyk-connected graph of girth at least four and ordern≧3k, hasn+(3/2)k ²-3k or morek-contractible edges.     

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.     

On the order of composite multistep methods for ordinary differential equations

Summary In this paper, a general class ofk-step methods for the numerical solution of ordinary differential equations is discussed. It is shown that methods with order of consistencyq have order of convergence (q+1) if a very simple condition is satisfied. This result gives a new aspect to previous results of Spijker; it also serves as a starting point for a new theory of cyclick-step methods, completing an approach of Donelson and Hansen. It facilitates the practical determination of high-order cyclick-step methods, especially of stiffly stable,k-step methods.     

Bilateral difference method for solving the boundary value problem for an ordinary differential equation

A method is proposed for calculating the bilateral approximations of the solution of the boundary value problem on [0, 1] for the equation y+p(x)y-q(x)y=f(x) and the derivative of the solution having the maximum deviation O(h² (h)+h³) on {kh} _k ^N =0, where(t) is the sum of the continuity moduli of the functions p, q,f, on the set of points {kh} _k ^N =0, h=1/N by means of O(N) operations. The data obtained for fairly smooth p, q,f allow interpolation to be used for calculating the bilateral approximations of the solution and its higher derivatives having the maximum deviation O(h³) on [0, 1].Translated from Matematicheskie Zametkii, Vol. 11, No. 4, pp. 421–430, April, 1972.