Analysis of Discretization Methods for Ordinary Differential Equations

ISBN-13: 9783642654732 / Angielski / Miękka / 2011 / 390 str.

Hans J. Stetter

Opis

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."

Spis treści

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.