A new edition of this classic work, comprehensively revised to present exciting new developments in this important subject
The study of numerical methods for solving ordinary differential equations is constantly developing and regenerating, and this third edition of a popular classic volume, written by one of the world’s leading experts in the field, presents an account of the subject which reflects both its historical and well-established place in computational science and its vital role as a cornerstone of modern applied mathematics.
In addition to serving as a broad and comprehensive study of numerical methods for initial value problems, this book contains a special emphasis on Runge-Kutta methods by the mathematician who transformed the subject into its modern form dating from his classic 1963 and 1972 papers. A second feature is general linear methods which have now matured and grown from being a framework for a unified theory of a wide range of diverse numerical schemes to a source of new and practical algorithms in their own right. As the founder of general linear method research, John Butcher has been a leading contributor to its development; his special role is reflected in the text. The book is written in the lucid style characteristic of the author, and combines enlightening explanations with rigorous and precise analysis. In addition to these anticipated features, the book breaks new ground by including the latest results on the highly efficient G-symplectic methods which compete strongly with the well-known symplectic Runge-Kutta methods for long-term integration of conservative mechanical systems.
This third edition of Numerical Methods for Ordinary Differential Equations will serve as a key text for senior undergraduate and graduate courses in numerical analysis, and is an essential resource for research workers in applied mathematics, physics and engineering.
Table of Contents:
Foreword xiii
Preface to the first edition xv
Preface to the second edition xix
Preface to the third edition xxi
1 Differential and Difference Equations 1
10 Differential Equation Problems 1
100 Introduction to differential equations 1
101 The Kepler problem 4
102 A problem arising from the method of lines 7
103 The simple pendulum 11
104 A chemical kinetics problem 14
105 The Van der Pol equation and limit cycles 16
106 The Lotka–Volterra problem and periodic orbits 18
107 The Euler equations of rigid body rotation 20
11 Differential Equation Theory 22
110 Existence and uniqueness of solutions 22
111 Linear systems of differential equations 24
112 Stiff differential equations 26
12 Further Evolutionary Problems 28
120 Many-body gravitational problems 28
121 Delay problems and discontinuous solutions 30
122 Problems evolving on a sphere 33
123 Further Hamiltonian problems 35
124 Further differential-algebraic problems 36
13 Difference Equation Problems 38
130 Introduction to difference equations 38
131 A linear problem 39
132 The Fibonacci difference equation 40
133 Three quadratic problems 40
134 Iterative solutions of a polynomial equation 41
135 The arithmetic-geometric mean 43
14 Difference Equation Theory 44
140 Linear difference equations 44
141 Constant coefficients 45
142 Powers of matrices 46
15 Location of Polynomial Zeros 50
150 Introduction 50
151 Left half-plane results 50
152 Unit disc results 52
Concluding remarks 53
2 Numerical Differential Equation Methods 55
20 The Euler Method 55
200 Introduction to the Euler method 55
201 Some numerical experiments 58
202 Calculations with stepsize control 61
203 Calculations with mildly stiff problems 65
204 Calculations with the implicit Euler method 68
21 Analysis of the Euler Method 70
210 Formulation of the Euler method 70
211 Local truncation error 71
212 Global truncation error 72
213 Convergence of the Euler method 73
214 Order of convergence 74
215 Asymptotic error formula 78
216 Stability characteristics 79
217 Local truncation error estimation 84
218 Rounding error 85
22 Generalizations of the Euler Method 90
220 Introduction 90
221 More computations in a step 90
222 Greater dependence on previous values 92
223 Use of higher derivatives 92
224 Multistep–multistage–multiderivative methods 94
225 Implicit methods 95
226 Local error estimates 96
23 Runge–Kutta Methods 97
230 Historical introduction 97
231 Second order methods 98
232 The coefficient tableau 98
233 Third order methods 99
234 Introduction to order conditions 100
235 Fourth order methods 101
236 Higher orders 103
237 Implicit Runge–Kutta methods 103
238 Stability characteristics 104
239 Numerical examples 108
24 Linear MultistepMethods 111
240 Historical introduction 111
241 Adams methods 111
242 General form of linear multistep methods 113
243 Consistency, stability and convergence 113
244 Predictor–corrector Adams methods 115
245 The Milne device 117
246 Starting methods 118
247 Numerical examples 119
25 Taylor Series Methods 120
250 Introduction to Taylor series methods 120
251 Manipulation of power series 121
252 An example of a Taylor series solution 122
253 Other methods using higher derivatives 123
254 The use of f derivatives 126
255 Further numerical examples 126
26 MultivalueMulitistage Methods 128
260 Historical introduction 128
261 Pseudo Runge–Kutta methods 128
262 Two-step Runge–Kutta methods 129
263 Generalized linear multistep methods 130
264 General linear methods 131
265 Numerical examples 133
27 Introduction to Implementation 135
270 Choice of method 135
271 Variable stepsize 136
272 Interpolation 138
273 Experiments with the Kepler problem 138
274 Experiments with a discontinuous problem 139
Concluding remarks 142
3 Runge–KuttaMethods 143
30 Preliminaries 143
300 Trees and rooted trees 143
301 Trees, forests and notations for trees 146
302 Centrality and centres 147
303 Enumeration of trees and unrooted trees 150
304 Functions on trees 153
305 Some combinatorial questions 155
306 Labelled trees and directed graphs 156
307 Differentiation 159
308 Taylor’s theorem 161
31 Order Conditions 163
310 Elementary differentials 163
311 The Taylor expansion of the exact solution 166
312 Elementary weights 168
313 The Taylor expansion of the approximate solution 171
314 Independence of the elementary differentials 174
315 Conditions for order 174
316 Order conditions for scalar problems 175
317 Independence of elementary weights 178
318 Local truncation error 180
319 Global truncation error 181
32 Low Order ExplicitMethods 185
320 Methods of orders less than 4 185
321 Simplifying assumptions 186
322 Methods of order 4 189
323 New methods from old 195
324 Order barriers 200
325 Methods of order 5 204
326 Methods of order 6 206
327 Methods of order greater than 6 209
33 Runge–Kutta Methods with Error Estimates 211
330 Introduction 211
331 Richardson error estimates 211
332 Methods with built-in estimates 214
333 A class of error-estimating methods 215
334 The methods of Fehlberg 221
335 The methods of Verner 223
336 The methods of Dormand and Prince 223
34 Implicit Runge–Kutta Methods 226
340 Introduction 226
341 Solvability of implicit equations 227
342 Methods based on Gaussian quadrature 228
343 Reflected methods 233
344 Methods based on Radau and Lobatto quadrature 236
35 Stability of Implicit Runge–Kutta Methods 243
350 A-stability, A(α)-stability and L-stability 243
351 Criteria for A-stability 244
352 Padé approximations to the exponential function 245
353 A-stability of Gauss and related methods 252
354 Order stars 253
355 Order arrows and the Ehle barrier 256
356 AN-stability 259
357 Non-linear stability 262
358 BN-stability of collocation methods 265
359 The V and W transformations 267
36 Implementable Implicit Runge–Kutta Methods 272
360 Implementation of implicit Runge–Kutta methods 272
361 Diagonally implicit Runge–Kutta methods 273
362 The importance of high stage order 274
363 Singly implicit methods 278
364 Generalizations of singly implicit methods 283
365 Effective order and DESIRE methods 285
37 Implementation Issues 288
370 Introduction 288
371 Optimal sequences 288
372 Acceptance and rejection of steps 290
373 Error per step versus error per unit step 291
374 Control-theoretic considerations 292
375 Solving the implicit equations 293
38 Algebraic Properties of Runge–Kutta Methods 296
380 Motivation 296
381 Equivalence classes of Runge–Kutta methods 297
382 The group of Runge–Kutta tableaux 299
383 The Runge–Kutta group 302
384 A homomorphism between two groups 308
385 A generalization of G1 309
386 Some special elements of G 311
387 Some subgroups and quotient groups 314
388 An algebraic interpretation of effective order 316
39 Symplectic Runge–Kutta Methods 323
390 Maintaining quadratic invariants 323
391 Hamiltonian mechanics and symplectic maps 324
392 Applications to variational problems 325
393 Examples of symplectic methods 326
394 Order conditions 327
395 Experiments with symplectic methods 328
4 Linear Multistep Methods 333
40 Preliminaries 333
400 Fundamentals 333
401 Starting methods 334
402 Convergence 335
403 Stability 336
404 Consistency 336
405 Necessity of conditions for convergence 338
406 Sufficiency of conditions for convergence 339
41 The Order of Linear Multistep Methods 344
410 Criteria for order 344
411 Derivation of methods 346
412 Backward difference methods 347
42 Errors and Error Growth 348
420 Introduction 348
421 Further remarks on error growth 350
422 The underlying one-step method 352
423 Weakly stable methods 354
424 Variable stepsize 355
43 Stability Characteristics 357
430 Introduction 357
431 Stability regions 359
432 Examples of the boundary locus method 360
433 An example of the Schur criterion 363
434 Stability of predictor–corrector methods 364
44 Order and Stability Barriers 367
440 Survey of barrier results 367
441 Maximum order for a convergent k-step method 368
442 Order stars for linear multistep methods 371
443 Order arrows for linear multistep methods 373
45 One-leg Methods and G-stability 375
450 The one-leg counterpart to a linear multistep method 375
451 The concept of G-stability 376
452 Transformations relating one-leg and linear multistep methods 379
453 Effective order interpretation 380
454 Concluding remarks on G-stability 380
46 Implementation Issues 381
460 Survey of implementation considerations 381
461 Representation of data 382
462 Variable stepsize for Nordsieck methods 385
463 Local error estimation 386
Concluding remarks 387
5 General Linear Methods 389
50 RepresentingMethods in General Linear Form 389
500 Multivalue–multistage methods 389
501 Transformations of methods 391
502 Runge–Kutta methods as general linear methods 392
503 Linear multistep methods as general linear methods 393
504 Some known unconventional methods 396
505 Some recently discovered general linear methods 398
51 Consistency, Stability and Convergence 400
510 Definitions of consistency and stability 400
511 Covariance of methods 401
512 Definition of convergence 403
513 The necessity of stability 404
514 The necessity of consistency 404
515 Stability and consistency imply convergence 406
52 The Stability of General Linear Methods 412
520 Introduction 412
521 Methods with maximal stability order 413
522 Outline proof of the Butcher–Chipman conjecture 417
523 Non-linear stability 419
524 Reducible linear multistep methods and G-stability 422
53 The Order of General Linear Methods 423
530 Possible definitions of order 423
531 Local and global truncation errors 425
532 Algebraic analysis of order 426
533 An example of the algebraic approach to order 428
534 The underlying one-step method 429
54 Methods with Runge–Kutta stability 431
540 Design criteria for general linear methods 431
541 The types of DIMSIM methods 432
542 Runge–Kutta stability 435
543 Almost Runge–Kutta methods 438
544 Third order, three-stage ARK methods 441
545 Fourth order, four-stage ARK methods 443
546 A fifth order, five-stage method 446
547 ARK methods for stiff problems 446
55 Methods with Inherent Runge–Kutta Stability 448
550 Doubly companion matrices 448
551 Inherent Runge–Kutta stability 450
552 Conditions for zero spectral radius 452
553 Derivation of methods with IRK stability 454
554 Methods with property F 457
555 Some non-stiff methods 458
556 Some stiff methods 459
557 Scale and modify for stability 460
558 Scale and modify for error estimation 462
56 G-symplectic methods 464
560 Introduction 464
561 The control of parasitism 467
562 Order conditions 471
563 Two fourth order methods 474
564 Starters and finishers for sample methods 476
565 Simulations 480
566 Cohesiveness 481
567 The role of symmetry 487
568 Efficient starting 492
Concluding remarks 497
References 499
Index 509
About the Author :
J.C Butcher, Emeritus Professor, University of Auckland, New Zealand
Review :
"I enjoyed reading this book. It is well written and quite approachable." ("Mathematical Reviews," 2004c) ..".covers now all the material that is modern standard in this field... belongs into any mathematical library..." (Zentralblatt Math, Vol.1040, No.09, 2004)
“I enjoyed reading this book. It is well written and quite approachable.” ("Mathematical Reviews", 2004c) "…covers now all the material that is modern standard in this field… belongs into any mathematical library..." (Zentralblatt Math, Vol.1040, No.09, 2004)
" I enjoyed reading this book. It is well written and quite approachable." ("Mathematical Reviews," 2004c) .".. covers now all the material that is modern standard in this field... belongs into any mathematical library..." (Zentralblatt Math, Vol.1040, No.09, 2004)
