See discussions, stats, and author profiles for this publication at: https://www.researchgate.

net/publication/200175469

Solving Ordinary Differential Equations I: Nonstiff

Problems

Book · January 1993

DOI: 10.1007/978-3-540-78862-1

CITATIONS READS

5,251 9,421

3 authors, including:

Ernst Hairer Syvert P. Norsett

University of Geneva Norwegian University of Science and Technology
265 PUBLICATIONS   26,587 CITATIONS    109 PUBLICATIONS   11,233 CITATIONS   

SEE PROFILE SEE PROFILE

Some of the authors of this publication are also working on these related projects:

i do not work since I retired View project

Numerical methods for ODEs View project

All content following this page was uploaded by Syvert P. Norsett on 21 May 2014.

The user has requested enhancement of the downloaded file.

E. Hairer G. Wanner

Solving Ordinary
Differential
Equations II
Stiff and Differential-Algebraic Problems

Second Revised Edition

With 137 Figures

Springer
Contents

Chapter IV. Stiff Problems - One-Step Methods

IV.l Examples of Stiff Equations 2
Chemical Reaction Systems 3
Electrical Circuits 4
Diffusion 6
A "Stiff' Beam 8
High Oscillations 11
Exercises 11
IV.2 Stability Analysis for Explicit RK Methods 15
Stability Analysis for Euler's Method 15
Explicit Runge-Kutta Methods 16
Extrapolation Methods 18
Analysis of the Examples of IV.l 18
Automatic Stiffness Detection 21
Step-Control Stability 24
A PI Step Size Control 28
Stabilized Explicit Runge-Kutta Methods 31
Exercises 37
IV.3 Stability Function of Implicit RK-Methods 40
The Stability Function 40
.4-Stability 42
L-Stability and A(a)-Stability 44
Numerical Results 46
Stability Functions of Order > $ 47
Pade Approximations to the Exponential Function 48
Exercises 49
IV.4 Order Stars 51
Introduction 51
Order and Stability for Rational Approximations 56
Stability of Pade Approximations 58
Comparing Stability Domains 58
Rational Approximations with Real Poles 61
The Real-Pole Sandwich 62
Multiple Real-Pole Approximations 67
Exercises 70
FV.5 Construction of Implicit Runge-Kutta Methods 71
Gauss Methods 71
Radau IA and Radau IIA Methods 72
X Contents

Lobatto niA, IIIB and IIIC Methods 75

The W -Transformation 77
Construction of Implicit Runge-Kutta Methods 83
Stability Function 84
Positive Functions 86
Exercises 89
IV.6 Diagonally Implicit RK Methods 91
Order Conditions 91
Stiffly Accurate SDIRK Methods 92
The Stability Function 96
Multiple Real-Pole Approximations with it(oo)=0 98
Choice of Method 99
Exercises 100
IV.7 Rosenbrock-Type Methods 102
Derivation of the Method 102
Order Conditions 104
The Stability Function 108
Construction of Methods of Order 4 108
Higher Order Methods Ill
Implementation of Rosenbrock-Type Methods Ill
The "Hump" 113
Methods with Inexact Jacobian ( W -Methods) 114
Exercises 117
IV.8 Implementation of Implicit Runge-Kutta Methods 118
Reformulation of the Nonlinear System 118
Simplified Newton Iterations 119
The Linear System 121
Step Size Selection 123
Implicit Differential Equations 127
An SDIRK-Code 128
SIRK-Methods 128
Exercises 130
IV.9 Extrapolation Methods 131
Extrapolation of Symmetric Methods 131
Smoothing 133
The Linearly Implicit Mid-Point Rule 134
Implicit and Linearly Implicit Euler Method 138
Implementation 139
Exercises 142
IV.IO Numerical Experiments 143
The Codes Used 143
Twelve Test Problems 144
Results and Discussion 152
Partitioning and Projection Methods 160
Exercises 165
IV.ll Contractivity for Linear Problems 167
Euclidean Norms (Theorem of von Neumann) 168
Error Growth Function for Linear Problems 169
Small Nonlinear Perturbations 172
Contractivity in )| • ||oo and j| • ||i 175
Study of the Threshold Factor 176
 Contents XI

Absolutely Monotonic Functions 178

Exercises 179
IV.12 B-Stability and Contractivity 180
One-Sided Lipschitz Condition 180
B -Stability and Algebraic Stability 181
Some Algebraically Stable IRK Methods 183
AN -Stability 184
Reducible Runge-Kutta Methods 187
The Equivalence Theorem for 5-Irreducible Methods 188
Error Growth Function 193
Computation of ^ s ( ^ ) 195
Exercises 199
IV.13 Positive Quadrature Formulas and B-Stable RK-Methods .. 201
Quadrature Formulas and Related Continued Fractions 201
Number of Positive Weights 203
Characterization of Positive Quadrature Formulas 205
Necessary Conditions for Algebraic Stability 206
Characterization of Algebraically Stable Methods 209
The "Equivalence" of A- and B-Stability 211
Exercises 213
IV.14 Existence and Uniqueness of IRK Solutions 215
Existence 215
A Counterexample 217
Influence of Perturbations and Uniqueness 218
Computation of aoC^" 1 ) 220
Methods with Singular A 222
Lobatto inC Methods 223
Exercises 223
IV.15 B-Convergence 225
The Order Reduction Phenomenon 225
The Local Error 228
Error Propagation 229
B -Convergence for Variable Step Sizes 230
B -Convergence Implies Algebraic Stability 232
The Trapezoidal Rule 234
Order Reduction for Rosenbrock Methods 236
Exercises 237

Chapter V. Multistep Methods for Stiff Problems

V.I Stability of Multistep Methods 240
The Stability Region 240
Adams Methods 242
Predictor-Corrector Schemes 244
Nystrom Methods 245
BDF 246
The Second Dahlquist Barrier 247
Exercises 249
V.2 "Nearly" A-Stable Multistep Methods 250
A(a)-Stability and Stiff Stability 250
High Order ^(a)-Stable Methods 251
Approximating Low Order Methods with High Order Ones 253
XII Contents

A Disc Theorem 254

Accuracy Barriers for Linear Multistep Methods 254
Exercises 259
V.3 Generalized Multistep Methods 261
Second Derivative Multistep Methods of Enright 261
Second Derivative BDF Methods 265
Blended Multistep Methods 266
Extended Multistep Methods of Cash 267
Multistep Collocation Methods 270
Methods of "Radau" Type 273
Exercises 275
V.4 Order Stars on Riemann Surfaces 279
Riemann Surfaces 279
Poles Representing Numerical Work 283
Order and Order Stars 284
The "Daniel and Moore Conjecture" 286
Methods with Property C 288
General Linear Methods 290
Dual Order Stars 295
Exercises 297
V.5 Experiments with Multistep Codes 300
The Codes Used 300
Exercises 304
V.6 One-Leg Methods and G-Stability 305
One-Leg (Multistep) Methods 305
Existence and Uniqueness 306
G-Stability 307
An Algebraic Criterion 309
The Equivalence of A -Stability and G-Stability 310
A Criterion for Positive Functions 313
Error Bounds for One-Leg Methods 314
Convergence of A -Stable Multistep Methods 317
Exercises 319
V.7 Convergence for Linear Problems 321
Difference Equations for the Global Error 321
The Kreiss Matrix Theorem 323
Some Applications of the Kreiss Matrix Theorem 326
Global Error for Prothero and Robinson Problem 328
Convergence for Linear Systems with Constant Coefficients 329
Matrix Valued Theorem of von Neumann 330
Discrete Variation of Constants Formula 332
Exercises 337
V.8 Convergence for Nonlinear Problems 339
Problems Satisfying a One-Sided Lipschitz Condition 339
Multiplier Technique 342
Multipliers and Nonlinearities 346
Discrete Variation of Constants and Perturbations 348
Convergence for Nonlinear Parabolic Problems 349
Exercises 354
V.9 Algebraic Stability of General Linear Methods 356
G-Stability 356
 Contents XTTI

Algebraic Stability 357

AN -Stability and Equivalence Results 359
Multistep Runge-Kutta Methods 362
Simplifying Assumptions 363
Quadrature Formulas 365
Algebraically Stable Methods of Order 2s 366
B -Convergence 368
Exercises 370

Chapter VI. Singular Perturbation Problems

and Index 1 Problems
VI.l Solving Index 1 Problems 372
Asymptotic Solution of van der Pol's Equation 372
The e -Embedding Method for Problems of Index 1 374
State Space Form Method 375
A Transistor Amplifier 376
Problems of the Form Mu' =v>(u) 378
Convergence of Runge-Kutta Methods 380
Exercises 381
VI.2 Multistep Methods 382
Methods for Index 1 Problems 382
Convergence for Singular Perturbation Problems 383
Exercises 387
VI.3 Epsilon Expansions for Exact and RK Solutions 388
Expansion of the Smooth Solution 388
Expansions with Boundary Layer Terms 389
Estimation of the Remainder 391
Expansion of the Runge-Kutta Solution 392
Convergence of RK-Methods for Differential-Algebraic Systems 394
Existence and Uniqueness of the Runge-Kutta Solution 397
Influence of Perturbations 398
Estimation of the Remainder in the Numerical Solution 399
Numerical Confirmation 403
Perturbed Initial Values 405
Exercises 406
VI.4 Rosenbrock Methods 407
Definition of the Method 407
Derivatives of the Exact Solution 408
Trees and Elementary Differentials 409
Taylor Expansion of the Exact Solution 411
Taylor Expansion of the Numerical Solution 412
Order Conditions 415
Convergence 416
Stiffly Accurate Rosenbrock Methods 418
Construction of RODAS, a Stiffly Accurate Embedded Method.. 420
Inconsistent Initial Values 422
Exercises 424
VI.5 Extrapolation Methods 426
Linearly Implicit Euler Discretization 426
Perturbed Asymptotic Expansion 428
Order Tableau 431
XIV Contents

Error Expansion for Singular Perturbation Problems 433

Dense Output 438
Exercises 441
VI.6 Quasilinear Problems 442
Example: Moving Finite Elements 442
Problems of Index One 445
Numerical Treatment of C(y)y' — f(y) 446
Extrapolation Methods 447
Exercises 448

Chapter VII. Differential-Algebraic Equations

of Higher Index
VII.1 The Index and Various Examples 452
Linear Equations with Constant Coefficients 452
Differentiation Index 454
Differential Equations on Manifolds 457
The Perturbation Index 459
Control Problems 461
Mechanical Systems 463
Exercises 465
VII.2 Index Reduction Methods 468
Index Reduction by Differentiation 468
Stabilization by Projection 470
Differential Equations with Invariants 472
Methods Based on Local State Space Forms 474
Overdetermined Differential-Algebraic Equations 477
Unstructured Higher Index Problems 478
Exercises 480
VII.3 Multistep Methods for Index 2 DAE 481
Existence and Uniqueness of Numerical Solution 482
Influence of Perturbations 484
The Local Error 485
Convergence for BDF 486
General Multistep Methods 489
Solution of the Nonlinear System by Simplified Newton 490
Exercises 491
VII.4 Runge-Kutta Methods for Index 2 DAE 492
The Nonlinear System 492
Estimation of the Local Error 494
Convergence for the y-Component 496
Convergence for the z -Component 497
Collocation Methods 498
Superconvergence of Collocation Methods 500
Projected Runge-Kutta Methods 502
Summary of Convergence Results 504
Exercises 505
VH.5 Order Conditions for Index 2 DAE 506
Derivatives of the Exact Solution 506
Trees and Elementary Differentials 507
Taylor Expansion of the Exact Solution 508
 Contents XV

Derivatives of the Numerical Solution 510

Order Conditions 512
Simplifying Assumptions 514
Projected Runge-Kutta Methods 515
Exercises 518
VII.6 Half-Explicit Methods for Index 2 Systems 519
Half-Explicit Runge-Kutta Methods 520
Extrapolation Methods 525
0-Blocked Multistep Methods 527
Exercises 529
VII.7 Computation of Multibody Mechanisms 530
Description of the Model 530
Fortran Subroutines 533
Computation of Consistent Initial Values 535
Numerical Computations 536
A Stiff Mechanical System 541
Exercises 542
VII.8 Symplectic Methods for Constrained Hamiltonian Systems .. 543
Properties of the Exact Flow 544
First Order Symplectic Method 545
SHAKE and RATTLE 548
The Lobatto mA-ITIB Pair 550
Composition Methods 554
Backward Error Analysis (for ODEs) 555
Backward Error Analysis on Manifolds 559
Exercises 562

Appendix. Fortran Codes 565

Driver for the Code RADAU5 566
Subroutine RADAU5 568
Subroutine RADAUP 574
Subroutine RODAS 574
Subroutine SEULEX 575
Problems with Special Structure 575
Use of SOLOUT and of Dense Output 576

Bibliography 577

Symbol Index 605

Subject Index 607

View publication