Numerical Methods for Ordinary Differential Equations (3^rd Ed.)

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.

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

J.C Butcher, Emeritus Professor, University of Auckland, New Zealand