High-order adaptive finite element-singly implicit Runge-Kutta methods for parabolic differential equations

We describe an adaptive mesh refinement finite element method-of-lines procedure for solving one-dimensional parabolic partial differential equations. Solutions are calculated using Galerkin's method with a piecewise hierarchical polynomial basis in space and singly implicit Runge-Kutta (SIRK) methods in time. A modified SIRK formulation eliminates a linear systems solution that is required by the traditional SIRK formulation and leads to a new reduced-order interpolation formula. Stability and temporal error estimation techniques allow acceptance of approximate solutions at intermediate stages, yielding increased efficiency when solving partial differential equations. A priori energy estimates of the local discretization error are obtained for a nonlinear scalar problem. A posteriori estimates of local spatial discretization errors, obtained by order variation, are used with the a priori error estimates to control the adaptive mesh refinement strategy. Computational results suggest convergence of the a posteriori error estimate to the exact discretization error and verify the utility of the adaptive technique.This research was partially supported by the U.S. Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant Number AFOSR-90-0194; the U.S. Army Research Office under Contract Number DAAL 03-91-G-0215; by the National Science Foundation under Grant Number CDA-8805910; and by a grant from the Committee on Research, Tulane University.     

Probabilistic and deterministic convergence proofs for software for initial value problems

The numerical solution of initial value problems for ordinary differential equations is frequently performed by means of adaptive algorithms with user-input tolerance τ. The time-step is then chosen according to an estimate, based on small time-step heuristics, designed to try and ensure that an approximation to the local error commited is bounded by τ. A question of natural interest is to determine how the global error behaves with respect to the tolerance τ. This has obvious practical interest and also leads to an interesting problem in mathematical analysis. The primary difficulties arising in the analysis are that: (i) the time-step selection mechanisms used in practice are discontinuous as functions of the specified data; (ii) the small time-step heuristics underlying the control of the local error can break down in some cases. In this paper an analysis is presented which incorporates these two difficulties. For a mathematical model of an error per unit step or error per step adaptive Runge–Kutta algorithm, it may be shown that in a certain probabilistic sense, with respect to a measure on the space of initial data, the small time-step heuristics are valid with probability one, leading to a probabilistic convergence result for the global error as τ→0. The probabilistic approach is only valid in dimension m>1 this observation is consistent with recent analysis concerning the existence of spurious steady solutions of software codes which highlights the difference between the cases m=1 and m>1. The breakdown of the small time-step heuristics can be circumvented by making minor modifications to the algorithm, leading to a deterministic convergence proof for the global error of such algorithms as τ→0. An underlying theory is developed and the deterministic and probabilistic convergence results proved as particular applications of this theory. This revised version was published online in June 2006 with corrections to the Cover Date.     

Derivation of continuous explicit two-step Runge–Kutta methods of order three

We describe a construction of continuous extensions to a new representation of two-step Runge–Kutta methods for ordinary differential equations. This representation makes possible the accurate and reliable estimation of local discretization error, facilitates the efficient implementation of these methods in variable stepsize environment, and adapts readily to the numerical solution of a class of delay differential equations. A number of numerical tests carried out on the obtained methods of order 3 with quadratic interpolants show their efficiency and robust performance which allow them to compete with the state-of-the-art dde23 code from Matlab.     

Stability and oscillations of numerical solutions for differential equations with piecewise continuous arguments of alternately advanced and retarded type

This paper is concerned with the numerical properties of θ-methods for the solution of alternately advanced and retarded differential equations with piecewise continuous arguments. Using two θ-methods, namely the one-leg θ-method and the linear θ-method, the necessary and sufficient conditions under which the analytic stability region is contained in the numerical stability region are obtained, and the conditions of oscillations for the θ-methods are also obtained. It is proved that oscillations of the analytic solution are preserved by the θ-methods. Furthermore, the relationships between stability and oscillations are revealed. Some numerical experiments are presented to illustrate our results.     

Time-stepping and preserving orthonormality

Certain applications produce initial value ODEs whose solutions, regarded as time-dependent matrices, preserve orthonormality. Such systems arise in the computation of Lyapunov exponents and the construction of smooth singular value decompositions of parametrized matrices. For some special problem classes, there exist time-stepping methods that automatically inherit the orthonormality preservation. However, a more widely applicable approach is to apply a standard integrator and regularly replace the approximate solution by an orthonormal matrix. Typically, the approximate solution is replaced by the factorQ from its QR decomposition (computed, for example, by the modified Gram-Schmidt method). However, the optimal replacement—the one that is closest in the Frobenius norm—is given by the orthonormal polar factor. Quadratically convergent iteration schemes can be used to compute this factor. In particular, there is a matrix multiplication based iteration that is ideally suited to modern computer architectures. Hence, we argue that perturbing towards the orthonormal polar factor is an attractive choice, and we consider performing a fixed number of iterations. Using the optimality property we show that the perturbations improve the departure from orthonormality without significantly degrading the finite-time global error bound for the ODE solution. Our analysis allows for adaptive time-stepping, where a local error control process is driven by a user-supplied tolerance. Finally, using a recent result of Sun, we show how the global error bound carries through to the case where the orthonormal QR factor is used instead of the orthonormal polar factor. This work was supported by Engineering and Physical Sciences Research Council grants GR/H94634 and GR/K80228.     

On quasi-consistent integration by Nordsieck methods

In this paper we study advantages of numerical integration by quasi-consistent Nordsieck formulas. All quasi-consistent numerical methods possess at least one important property for practical use, which has not attracted attention yet, i.e. the global error of a quasi-consistent method has the same order as its local error. This means that the usual local error control will produce a numerical solution for the prescribed accuracy requirement if the principal term of the local error dominates strongly over remaining terms. In other words, the global error control can be as cheap as the local error control in the methods under discussion.     

The Sinc-collocation method for solving the Thomas–Fermi equation

A numerical technique for solving nonlinear ordinary differential equations on a semi-infinite interval is presented. We solve the Thomas–Fermi equation by the Sinc-Collocation method that converges to the solution at an exponential rate. This method is utilized to reduce the nonlinear ordinary differential equation to some algebraic equations. This method is easy to implement and yields very accurate results.     

Local error control inSDIRK-methods

This paper describes some problems that are encountered in the implementation of a class of Singly Diagonally Implicit Runge-Kutta (SDIRK) methods. The contribution to the local error from the local truncation error and the residual error from the algebraic systems involved are analysed. A section describes a special interpolation formula. This is used as a prediction stage in the iterative solution of the algebraic equations. A strategy for computing a starting stepsize is presented. The techniques are applied to numerical examples.     

Multiscale asymptotic expansion and finite element methods for the mixed boundary value problems of second order elliptic equation in perforated domains

In this paper, we will discuss the mixed boundary value problems for the second order elliptic equation with rapidly oscillating coefficients in perforated domains, and will present the higher-order multiscale asymptotic expansion of the solution for the problem, which will play an important role in the numerical computation . The convergence theorems and their rigorous proofs will be given. Finally a multiscale finite element method and some numerical results will be presented. This work is Supported by National Natural Science Foundation of China (grant # 10372108, # 90405016), and Special Funds for Major State Basic Research Projects( grant # TG2000067102)     

Convergence results for the MATLAB ode23 routine

We prove convergence results on finite time intervals, as the user-defined tolerance τ→0, for a class of adaptive timestepping ODE solvers that includes the ode23 routine supplied in MATLAB Version 4.2. In contrast to existing theories, these convergence results hold with error constants that are uniform in the neighbourhood of equilibria; such uniformity is crucial for the derivation of results concerning the numerical approximation of dynamical systems. For linear problems the error estimates are uniform on compact sets of initial data. The analysis relies upon the identification of explicit embedded Runge-Kutta pairs for which all but the leading order terms of the expansion of the local error estimate areO(∥f(u∥)²). This work was partially supported by NSF Grant DMS-95-04879.     

Parallel defect control

How can small-scale parallelism best be exploited in the solution of nonstiff initial value problems? It is generally accepted that only modest gains inefficiency are possible, and it is often the case that “fast” parallel algorithms have quite crude error control and stepsize selection components. In this paper we consider the possibility of using parallelism to improvereliability andfunctionality rather than efficiency. We present an algorithm that can be used with any explicit Runge-Kutta formula. The basic idea is to take several smaller substeps in parallel with the main step. The substeps provide an interpolation facility that is essentially free, and the error control strategy can then be based on a defect (residual) sample. If the number of processors exceeds (p ? 1)/2, wherep is the order of the Runge-Kutta formula, then the interpolant and the error control scheme satisfy very strong reliability conditions. Further, for a given orderp, the asymptotically optimal values for the substep lengths are independent of the problem and formula and hence can be computed a priori. Theoretical comparisons between the parallel algorithm and optimal sequential algorithms at various orders are given. We also report on numerical tests of the reliability and efficiency of the new algorithm, and give some parallel timing statistics from a 4-processor machine.     

On the finite volume element method

Summary The finite volume element method (FVE) is a discretization technique for partial differential equations. It uses a volume integral formulation of the problem with a finite partitioning set of volumes to discretize the equations, then restricts the admissible functions to a finite element space to discretize the solution. this paper develops discretization error estimates for general selfadjoint elliptic boundary value problems with FVE based on triangulations with linear finite element spaces and a general type of control volume. We establishO(h) estimates of the error in a discreteH ¹ semi-norm. Under an additional assumption of local uniformity of the triangulation the estimate is improved toO(h ²). Results on the effects of numerical integration are also included.This research was sponsored in part by the Air Force Office of Scientific Research under grant number AFOSR-86-0126 and the National Science Foundation under grant number DMS-8704169. This work was performed while the author was at the University of Colorado at Denver     

A multi-grid method with a priori and a posteriori level choice for the regularization of nonlinear ill-posed problems

Summary In this paper we study a multi-grid method for the numerical solution of nonlinear systems of equations arising from the discretization of ill-posed problems, where the special eigensystem structure of the underlying operator equation makes it necessary to use special smoothers. We provide uniform contraction factor estimates and show that a nested multigrid iteration together with an a priori or a posteriori chosen stopping index defines a regularization method for the ill-posed problem, i.e., a stable solution method, that converges to an exact solution of the underlying infinite-dimensional problem as the data noise level goes to zero, with optimal rates under additional regularity conditions. Supported by the Fonds zur F?rderung der wissenschaftlichen Forschung under grant T 7-TEC and project F1308 within Spezialforschungsbereich 13     

Global error estimation and control in linearly-implicit parallel two-step peer W-methods

The class of linearly-implicit parallel two-step peer W-methods has been designed recently for efficient numerical solutions of stiff ordinary differential equations. Those schemes allow for parallelism across the method, that is an important feature for implementation on modern computational devices. Most importantly, all stage values of those methods possess the same properties in terms of stability and accuracy of numerical integration. This property results in the fact that no order reduction occurs when they are applied to very stiff problems. In this paper, we develop parallel local and global error estimation schemes that allow the numerical solution to be computed for a user-supplied accuracy requirement in automatic mode. An algorithm of such global error control and other technical particulars are also discussed here. Numerical examples confirm efficiency of the presented error estimation and stepsize control algorithm on a number of test problems with known exact solutions, including nonstiff, stiff, very stiff and large-scale differential equations. A comparison with the well-known stiff solver RODAS is also shown.     

Singular integral equations — The convergence of the Nyström interpolant of the Gauss-Chebyshev method

Nyström's interpolation formula is applied to the numerical solution of singular integral equations. For the Gauss-Chebyshev method, it is shown that this approximation converges uniformly, provided that the kernel and the input functions possess a continuous derivative. Moreover, the error of the Nyström interpolant is bounded from above by the Gaussian quadrature errors and thus convergence is fast, especially for smooth functions. ForC input functions, a sharp upper bound for the error is obtained. Finally numerical examples are considered. It is found that the actual computational error agrees well with the theoretical derived bounds.This research has been partially supported by a grant from the Rutgers Research Council.     

The life-span of backward error analysis for numerical integrators

Summary. Backward error analysis is a useful tool for the study of numerical approximations to ordinary differential equations. The numerical solution is formally interpreted as the exact solution of a perturbed differential equation, given as a formal and usually divergent series in powers of the step size. For a rigorous analysis, this series has to be truncated. In this article we study the influence of this truncation to the difference between the numerical solution and the exact solution of the perturbed differential equation. Results on the long-time behaviour of numerical solutions are obtained in this way. We present applications to the numerical phase portrait near hyperbolic equilibrium points, to asymptotically stable periodic orbits and Hopf bifurcation, and to energy conservation and approximation of invariant tori in Hamiltonian systems. Received October 18, 1995 / Revised version received February 28, 1996     

A note on error expressions for reflected and averaged implicit Runge-Kutta methods

In addition to their usefulness in the numerical solution of initial value ODE's, the implicit Runge-Kutta (IRK) methods are also important for the solution of two-point boundary value problems. Recently, several classes of modified IRK methods which improve significantly on the efficiency of the standard IRK methods in this application have been presented. One such class is the Averaged IRK methods; a member of the class is obtained by applying an averaging operation to a non-symmetric IRK method and its reflection. In this paper we investigate the forms of the error expressions for reflected and averaged IRK methods. Our first result relates the expression for the local error of the reflected method to that of the original method. The main result of this paper relates the error expression of an averaged method to that of the method upon which it is based. We apply these results to show that for each member of the class of the averaged methods, there exists an embedded lower order method which can be used for error estimation, in a formula-pair fashion.This work was supported by the Natural Science and Engineering Research Council of Canada.     

Problems and methods in partial differential equations

Summary The method of singularities is used to solve theCauchy problem for simple hyperbolic partial differential equations, namely, the wave equation and the damped wave equation. The representation formula for the solution of theCauchy problem is written in terms of finite parts and logarithmic parts of certain divergent integrals. A process of analytic continuation is also used to solve theCauchy problems under consideration. However, to obtain explicitly the representation formulas for the solutions, one must actually perform the analytic continuation. It is shown that this is best achieved by making use of finite and logarithmic parts. Simple examples were purposely chosen so as to show that consideration of finite and logarithmic parts is naturally unavoidable and ? in the very nature of things ?. To Enrico Bompiani on his scientific Jubilee. This work was sponsored in part by the Air Force Office of Scientific Research of the Air Research and Development Command, United States Air Force, through its European Office.     

Error growth analysis via stability regions for discretizations of initial value problems

This paper deals with numerical methods for the solution of linear initial value problems. Two main theorems are presented on the stability of these methods. Both theorems give conditions guaranteeing a mild error growth, for one-step methods characterized by a rational function ϕ(z). The conditions are related to the stability regionS={z:z∈ℂ with |ϕ(z)|≤1}, and can be viewed as variants to the resolvent condition occurring in the reputed Kreiss matrix theorem. Stability estimates are presented in terms of the number of time stepsn and the dimensions of the space. The first theorem gives a stability estimate which implies that errors in the numerical process cannot grow faster than linearly withs orn. It improves previous results in the literature where various restrictions were imposed onS and ϕ(z), including ϕ′(z)≠0 forz∈σS andS be bounded. The new theorem is not subject to any of these restrictions. The second theorem gives a sharper stability result under additional assumptions regarding the differential equation. This result implies that errors cannot grow faster thann ^β, with fixed β<1. The theory is illustrated in the numerical solution of an initial-boundary value problem for a partial differential equation, where the error growth is measured in the maximum norm.     

A Nyström interpolant for some weakly singular linear Volterra integral equations

We consider a second kind weakly singular Volterra integral equation defined by a non-compact operator and derive a Nyström type interpolant of the solution based on Gauss-Radau nodes. Assuming the stability of the interpolant, which is confirmed by the numerical tests, we derive convergence estimates.