Analysis of Discretization Methods for Ordinary Differential Equations

Due to the fundamental role of differential equations in science and engineering it has long been a basic task of numerical analysts to generate numerical values of solutions to differential equations. Nearly all approaches to this task involve a "finitization" of the original differential equation problem, usually by a projection into a finite-dimensional space. By far the most popular of these finitization processes consists of a reduction to a difference equation problem for functions which take values only on a grid of argument points. Although some of these finite­ difference methods have been known for a long time, their wide applica­ bility and great efficiency came to light only with the spread of electronic computers. This in tum strongly stimulated research on the properties and practical use of finite-difference methods. While the theory or partial differential equations and their discrete analogues is a very hard subject, and progress is consequently slow, the initial value problem for a system of first order ordinary differential equations lends itself so naturally to discretization that hundreds of numerical analysts have felt inspired to invent an ever-increasing number of finite-difference methods for its solution. For about 15 years, there has hardly been an issue of a numerical journal without new results of this kind; but clearly the vast majority of these methods have just been variations of a few basic themes. In this situation, the classical text­ book by P.

1 General Discretization Methods.- 1.1. Basic Definitions.- 1.1.1 Discretization Methods.- 1.1.2 Consistency.- 1.1.3 Convergence.- 1.1.4 Stability.- 1.2 Results Concerning Stability.- 1.2.1 Existence of the Solution of the Discretization.- 1.2.2 The Basic Convergence Theorem.- 1.2.3 Linearization.- 1.2.4 Stability of Neighboring Discretizations.- 1.3 Asymptotic Expansions of the Discretization Errors.- 1.3.1 Asymptotic Expansion of the Local Discretization Error.- 1.3.2 Asymptotic Expansion of the Global Discretization Error.- 1.3.3 Asymptotic Expansions in Even Powers of n.- 1.3.4 The Principal Error Terms.- 1.4 Applications of Asymptotic Expansions.- 1.4.1 Richardson Extrapolation.- 1.4.2 Linear Extrapolation.- 1.4.3 Rational Extrapolation.- 1.4.4 Difference Correction.- 1.5 Error Analysis.- 1.5.1 Computing Error.- 1.5.2 Error Estimates.- 1.5.3 Strong Stability.- 1.5.4 Richardson-extrapolation and Error Estimation.- 1.5.5 Statistical Analysis of Round-off Errors.- 1.6 Practical Aspects.- 2 Forward Step Methods.- 2.1 Preliminaries.- 2.1.1 Initial Value Problems for Ordinary Differential Equations.- 2.1.2 Grids.- 2.1.3 Characterization of Forward Step Methods.- 2.1.4 Restricting the Interval.- 2.1.5 Notation.- 2.2 The Meaning of Consistency, Convergence, and Stability with Forward Step Methods.- 2.2.1 Our Choice of Norms in En and En0.- 2.2.2 Other Definitions of Consistency and Convergence.- 2.2.3 Other Definitions of Stability.- 2.2.4 Spijker’s Norm for En0.- 2.2.5 Stability of Neighboring Discretizations.- 2.3 Strong Stability of f.s.m..- 2.3.1 Perturbation of IVP 1.- 2.3.2 Discretizations of {IVP 1}T.- 2.3.3 Exponential Stability for Difference Equations on [0,?).- 2.3.4 Exponential Stability of Neighboring Discretizations.- 2.3.5 Strong Exponential Stability.- 2.3.6 Stability Regions.- 2.3.7 Stiff Systems of Differential Equations.- 3 Runge-Kutta Methods.- 3.1 RK-procedures.- 3.1.1 Characterization.- 3.1.2 Local Solution and Increment Function.- 3.1.3 Elementary Differentials.- 3.1.4 The Expansion of the Local Solution.- 3.1.5 The Exact Increment Function.- 3.2 The Group of RK-schemes.- 3.2.1 RK-schemes.- 3.2.2 Inverses of RK-schemes.- 3.2.3 Equivalent Generating Matrices.- 3.2.4 Explicit and Implicit RK-schemes.- 3.2.5 Symmetric RK-procedures.- 3.3 RK-methods and Their Orders.- 3.3.1 RK-methods.- 3.3.2 The Order of Consistency.- 3.3.3 Construction of High-order RK-procedures.- 3.3.4 Attainable Order of m-stage RK-procedures.- 3.3.5 Effective Order of RK-schemes.- 3.4 Analysis of the Discretization Error.- 3.4.1 The Principal Error Function.- 3.4.2 Asymptotic Expansion of the Discretization Error.- 3.4.3 The Principal Term of the Global Discretization Error.- 3.4.4 Estimation of the Local Discretization Error.- 3.5 Strong Stability of RK-methods.- 3.5.1 Strong Stability for Sufficiently Large n.- 3.5.2 Strong Stability for Arbitrary n.- 3.5.3 Stability Regions of RK-methods.- 3.5.4 Use of Stability Regions for General {IVP 1}T.- 3.5.5 Suggestion for a General Approach.- 4 Linear Multistep Methods.- 4.1 Linear k-step Schemes.- 4.1.1 Characterization.- 4.1.2 The Order of Linear k-step Schemes.- 4.1.3 Construction of Linear k-step Schemes of High Order.- 4.2 Uniform Linear k-step Methods.- 4.2.1 Characterization, Consistency.- 4.2.2 Auxiliary Results.- 4.2.3 Stability of Uniform Linear k-step Methods.- 4.2.4 Convergence.- 4.2.5 Highest Obtainable Orders of Convergence.- 4.3 Cyclic Linear k-step Methods.- 4.3.1 Stability of Cyclic Linear k-step Methods.- 4.3.2 The Auxiliary Method.- 4.3.3 Attainable Order of Cyclic Linear Multistep Methods.- 4.4 Asymptotic Expansions.- 4.4.1 The Local Discretization Error.- 4.4.2 Asymptotic Expansion of the Global Discretization Error, Preparations.- 4.4.3 The Case of No Extraneous Essential Zeros.- 4.4.4 The Case of Extraneous Essential Zeros.- 4.5 Further Analysis of the Discretization Error.- 4.5.1 Weak Stability.- 4.5.2 Smoothing.- 4.5.3 Symmetric Linear k-step Schemes.- 4.5.4 Asymptotic Expansions in Powers of h2.- 4.5.5 Estimation of the Discretization Error.- 4.6 Strong Stability of Linear Multistep Methods.- 4.6.1 Strong Stability for Sufficiently Large n.- 4.6.2 Stability Regions of Linear Multistep Methods.- 4.6.3 Strong Stability for Arbitrary n.- 5 Multistage Multistep Methods.- 5.1 General Analysis.- 5.1.1 A General Class of Multistage Multistep Procedures.- 5.1.2 Simple m-stage k-step Methods.- 5.1.3 Stability and Convergence of Simple m-stage k-step Methods.- 5.2 Predictor-corrector Methods.- 5.2.1 Characterization, Subclasses.- 5.2.2 Stability and Order of Predictor-corrector Methods.- 5.2.3 Analysis of the Discretization Error.- 5.2.4 Estimation of the Local Discretization Error.- 5.2.5 Estimation of the Global Discretization Error.- 5.3 Predictor-corrector Methods with Off-step Points.- 5.3.1 Characterization.- 5.3.2 Determination of the Coefficients and Attainable Order.- 5.3.3 Stability of High Order PC-methods with Off-step Points.- 5.4 Cyclic Forward Step Methods.- 5.4.1 Characterization.- 5.4.2 Stability and Error Propagation.- 5.4.3 Primitive m-cyclic k-step Methods.- 5.4.4 General Straight m-cyclic k-step Methods.- 5.5 Strong Stability.- 5.5.1 Characteristic Polynomial, Stability Regions.- 5.5.2 Stability Regions of PC-methods.- 5.5.3 Stability Regions of Cyclic Methods.- 6 Other Discretization Methods for IVP 1.- 6.1 Discretization Methods with Derivatives of f.- 6.1.1 Recursive Computation of Higher Derivatives of the Local Solution.- 6.1.2 Power Series Methods.- 6.1.3 The Perturbation Theory of Groebner-Knapp-Wanner.- 6.1.4 Groebner-Knapp-Wanner Methods.- 6.1.5 Runge-Kutta-Fehlberg Methods.- 6.1.6 Multistep Methods with Higher Derivatives.- 6.2 General Multi-value Methods.- 6.2.1 Nordsieck’s Approach.- 6.2.2 Nordsieck Predictor-corrector Methods.- 6.2.3 Equivalence of Generalized Nordsieck Methods.- 6.2.4 Appraisal of Nordsieck Methods.- 6.3 Extrapolation Methods.- 6.3.1 The Structure of an Extrapolation Method.- 6.3.2 Gragg’s Method.- 6.3.3 Strong Stability of MG.- 6.3.4 The Gragg-Bulirsch-Stoer Extrapolation Method.- 6.3.5 Extrapolation Methods for Stiff Systems.