Extrapolation applied to certain discretization methods solving the initial value problem for hyperbolic differential equations

Summary The procedurediwiex presented in this paper provides an approximate solution to Cauchy's initial value problem for general hyperbolic systems of first order. The procedurecharex can be applied to the initial value problem for a hyperbolic system of quasi-linear differential equations. This second method is a kind of method of characteristics. It produces a solution for the whole domain of determinancy. Both procedures use extrapolation to the limit. Editor's Note. In this fascile, prepublication of algorithms from the Approximations series of the Handbook for Automatic Computation is continued. Algorithms are published in ALGOL 60 reference language as approved by the IFIP. Contributions in this series should be styled after the most recently published ones     

A numerical method to boundary value problems for second order delay differential equations

Summary In the first part of this paper we are dealing with theoretical statements and conditions which lead to existence and uniqueness of the solution of a nonlinear boundary value problem with delay. Next we apply this method successfully to a numerical example. The computations have been carried out at the computer Siemens 4004. The data obtained are presented in two tables.     

The contraction number of a multigrid method for solving the Poisson equation

Summary The treatment of a multigrid method in the framework of numerical analysis elucidates that regularity of the solution is not necessary for the convergence of the multigrid algorithm but only for fast convergence. For the linear equations which arise from the discretization of the Poisson equation, a convergence factor 0,5 is established independent of the shape of the domain and of the regularity of the solution.Dedicated to Professor Dr.Dr.h.c. Lothar Collatz on the occasion of his 70 th birthday     

The method of lines for Poisson's equation with nonlinear or free boundary conditions

Summary The method of lines is used to solve Poisson's equation on an irregular domain with nonlinear or free boundary conditions. The partial differential equation is approximated by a system of second order ordinary differential equations subject to multi-point boundary conditions. The system is solved with an SOR iteration which employs invariant imbedding for each one dimensional problem. An application of the method to a boundary control problem and to a free surface problem arising in electrochemical machining is described. Finally, some theoretical convergence results are presented for a model problem with radiative boundary conditions on fixed boundaries.This work was supported by the U.S. Army Research Office under Grant DA-AG29-76-G-0261     

Higher order methods for a singularly perturbed problem

Summary A finite element method using piecewise polynomials of degree k is used to approximate the problem u+u=f, >0 a small parameter. A very irregular mesh is used. On this mesh error estimates of order0(h ^k+1) are obtained uniformly in ,h the maximum stepsize, fork2. The condition number of the system of linear equations one has to solve in order to get the approximation is estimated. Extension of the results to more complicated problems is briefly indicated. Finally, a numerical example is given.Work performed while visiting the IBM Thomas J. Watson Research Center, Yorktown Heights, N.Y.     

Extrapolation to the limit for numerical solutions of hyperbolic equations

Summary The application of extrapolation to the limit requires the existence of an asymptotic expansion in powers of the step size. In this paper one-and multi-step methods for the solution of hyperbolic systems of first order are considered. Conditions are formulated that ensure the asymptotic expansion. Methods of characteristics for quasilinear systems with two independent variables are included in this presentation. If a rectangular grid is used, also non-quasilinear systems are admissible. The main part of this paper deals with initial value problems. But it is shown that in some exceptional cases asymptotic expansions hold for initial-boundary problems, too.This paper is chiefly based on the author's doctoral thesis [7], written under the direction of Professor R. Bulirsch     

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.     

High order methods for the numerical integration of ordinary differential equations

Summary High order implicit integration formulae with a large region of absolute stability are developed for the approximate numerical integration of both stiff and non-stiff systems of ordinary differential equations. The algorithms derived behave essentially like one step methods and are demonstrated by direct application to certain particular examples.     

A new interpolation procedure for adapting Runge-Kutta methods to delay differential equations

This paper deals with adapting Runge-Kutta methods to differential equations with a lagging argument. A new interpolation procedure is introduced which leads to numerical processes that satisfy an important asymptotic stability condition related to the class of testproblemsU(t)=U(t)+U(t–) with , C, Re()<–||, and >0. Ifc _i denotes theith abscissa of a given Runge-Kutta method, then in thenth stept _n–1t _n :=t _n–1+h of the numerical process our interpolation procedure computes an approximation toU(t _n–1+c _i h–) from approximations that have already been generated by the process at pointst _j–1+c _i h(j=1,2,3,...). For two of these new processes and a standard process we shall consider the convergence behaviour in an actual application to a given, stiff problem.     

Unconditionally stable methods for second order differential equations

We use the concept of order stars (see [1]) to prove and generalize a recent result of Dahlquist [2] on unconditionally stable linear multistep methods for second order differential equations. Furthermore a result of Lambert-Watson [3] is generalized to the multistage case. Finally we present unconditionally stable Nyström methods of order 2s (s=1,2, ...) and an unconditionally stable modification of Numerov's method. The starting point of this paper was a discussion with G. Wanner and S.P. Nørsett. The author is very grateful to them.     

Stability of explicit time discretizations for solving initial value problems

Summary Stability regions of explicit linear time discretization methods for solving initial value problems are treated. If an integration method needsm function evaluations per time step, then we scale the stability region by dividing bym. We show that the scaled stability region of a method, satisfying some reasonable conditions, cannot be properly contained in the scaled stability region of another method. Bounds for the size of the stability regions for three different purposes are then given: for general nonlinear ordinary differential systems, for systems obtained from parabolic problems and for systems obtained from hyperbolic problems. We also show how these bounds can be approached by high order methods.This research has been supported by the Swiss National Foundation, grant No. 82-524.077     

N-dimensional characteristic problem for the Mangeron equation of non-integer order

In the paper we consider a n-dimensional characteristic problem for a certain partial differential equation of non-integer order.We prove the existence and uniqueness of a solution of the problem in the spaces of integrable and continious functions, respectively. Morever, we give sufficient conditions under which the set of solutions is not empty and relatively compact in the space of integrable functions     

A Taylor series method for the numerical solution of two-point boundary value problems

Summary For the numerical solution of two-point boundary value problems a shooting algorithm based on a Taylor series method is developed. Series coefficients are generated automatically by recurrence formulas. The performance of the algorithm is demonstrated by solving six problems arising in nonlinear shell theory, chemistry and superconductivity.     

One-step methods of any order for ordinary differential equations with discontinuous right-hand sides

Summary The right-hand sides of a system of ordinary differential equations may be discontinuous on a certain surface. If a trajectory crossing this surface shall be computed by a one-step method, then a particular numerical analysis is necessary in a neighbourhood of the point of intersection. Such an analysis is presented in this paper. It shows that one can obtain any desired order of convergence if the method has an adequate order of consistency. Moreover, an asymptotic error theory is developed to justify Richardson extrapolation. A general one-step method is constructed satisfying the conditions of the preceding theory. Finally, a simplified Newton iteration scheme is used to implement this method.     

On the convergence of the conjugate gradient method for singular capacitance matrix equations from the Neumann problem of the Poisson equation

Summary It is shown analytically in this work that the conjugate gradient method is an efficient means of solving the singular capacitance matrix equations arising from the Neumann problem of the Poisson equation. The total operation count of the algorithm does not exceed constant timesN ²logN(N=1/h) for any bounded domain with sufficiently smooth boundary.Sponsored by the United States Army under Contract No. DAAG29-75-C-0024 and the National Science Foundation under Grant No. MCS75-17385. Also partially supported by the Energy Research and Development Administration     

On the numerical treatment of a small divisor problem

Summary Quasiperiodic solutions of perturbed integrable Hamiltonian equations such as weakly coupled harmonic oscillators can be found by constructing an appropriate coordinate transformation which leads to a small divisor problem. However the numerical difficulties are not merely caused by the small divisors but rather by the appearence of ghost solutions, which appear in any reasonable discretization of the problem. Our numerical treatment, based on a Newton-type iteration, guarantees an approximation of the relevant solution of the nonlinear problem. Numerical solutions are found up to a critical value of the coupling constant, which is much larger than the coupling constants allowed by the existence theory available so far.     

A second order splitting method for the Cahn-Hilliard equation

Summary A semi-discrete finite element method requiring only continuous element is presented for the approximation of the solution of the evolutionary, fourth order in space, Cahn-Hilliard equation. Optimal order error bounds are derived in various norms for an implementation which uses mass lumping. The continuous problem has an energy based Lyapunov functional. It is proved that this property holds for the discrete problem.Research partially supported by NSF Grant DMS-8896141     

Generalized Runge-Kutta methods of order four with stepsize control for stiff ordinary differential equations

Summary GeneralizedA()-stable Runge-Kutta methods of order four with stepsize control are studied. The equations of condition for this class of semiimplicit methods are solved taking the truncation error into consideration. For application anA-stable and anA(89.3°)-stable method with small truncation error are proposed and test results for 25 stiff initial value problems for different tolerances are discussed.     

Analysis of finite element methods for second order boundary value problems using mesh dependent norms

This paper presents a new approach to the analysis of finite element methods based onC ⁰-finite elements for the approximate solution of 2nd order boundary value problems in which error estimates are derived directly in terms of two mesh dependent norms that are closely ralated to theL ₂ norm and to the 2nd order Sobolev norm, respectively, and in which there is no assumption of quasi-uniformity on the mesh family. This is in contrast to the usual analysis in which error estimates are first derived in the 1st order Sobolev norm and subsequently are derived in theL ₂ norm and in the 2nd order Sobolev norm — the 2nd order Sobolev norm estimates being obtained under the assumption that the functions in the underlying approximating subspaces lie in the 2nd order Sobolev space and that the mesh family is quasi-uniform.     

The method of lines for nonlinear parabolic differential equations with mixed derivatives

Summary By the so-called longitudinal method of lines the first boundary value problem for a parabolic differential equation is transformed into an initial value problem for a system of ordinary differential equations. In this paper, for a wide class of nonlinear parabolic differential equations the spatial derivatives occuring in the original problem are replaced by suitable differences such that monotonicity methods become applicable. A convergence theorem is proved. Special interest is devoted to the equationu _t=f(x,t,u,u _x,u _xx), if the matrix of first order derivatives off(x,t,z,p,r) with respect tor may be estimated by a suitable Minkowski matrix.