Numerical Methods for Ordinary Differential Equations

Cover......Page 1
Numerical Methods for Ordinary Differential Equations (Second Edition)......Page 4
Copyright......Page 5
Contents......Page 6
Preface to the first edition......Page 14
Preface to the second edition......Page 18
100 Introduction to differential equations......Page 22
101 The Kepler problem......Page 25
102 A problem arising from the method of lines......Page 28
103 The simple pendulum......Page 31
104 A chemical kinetics problem......Page 35
105 The Van der Pol equation and limit cycles......Page 37
106 The Lotka–Volterra problem and periodic orbits\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 39
107 The Euler equations of rigid body rotation......Page 41
110 Existence and uniqueness of solutions......Page 43
111 Linear systems of differential equations......Page 45
112 Stiff differential equations......Page 47
120 Many-body gravitational problems......Page 49
121 Delay problems and discontinuous solutions......Page 52
122 Problems evolving on a sphere......Page 53
123 Further Hamiltonian problems......Page 55
124 Further differential-algebraic problems......Page 57
131 A linear problem......Page 59
133 Three quadratic problems......Page 61
134 Iterative solutions of a polynomial equation......Page 62
135 The arithmetic-geometric mean......Page 64
140 Linear difference equations......Page 65
141 Constant coefficients......Page 66
142 Powers of matrices......Page 67
200 Introduction to the Euler methods......Page 72
201 Some numerical experiments......Page 75
202 Calculations with stepsize control......Page 79
203 Calculations with mildly stiff problems......Page 81
204 Calculations with the implicit Euler method......Page 84
210 Formulation of the Euler method......Page 86
212 Global truncation error......Page 87
213 Convergence of the Euler method......Page 89
214 Order of convergence......Page 90
215 Asymptotic error formula......Page 93
216 Stability characteristics......Page 95
217 Local truncation error estimation......Page 100
218 Rounding error......Page 101
220 Introduction......Page 106
221 More computations in a step......Page 107
222 Greater dependence on previous values......Page 108
223 Use of higher derivatives......Page 109
224 Multistep–multistage–multiderivative methods\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 111
226 Local error estimates......Page 112
231 Second order methods......Page 114
232 The coefficient tableau......Page 115
234 Introduction to order conditions......Page 116
235 Fourth order methods......Page 119
237 Implicit Runge–Kutta methods\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 120
238 Stability characteristics......Page 121
239 Numerical examples......Page 124
241 Adams methods......Page 126
243 Consistency, stability and convergence......Page 128
244 Predictor–corrector Adams methods\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 130
245 The Milne device......Page 132
246 Starting methods......Page 133
247 Numerical examples......Page 134
250 Introduction to Taylor series methods......Page 135
251 Manipulation of power series......Page 136
252 An example of a Taylor series solution......Page 137
253 Other methods using higher derivatives......Page 140
254 The use of f derivatives......Page 141
255 Further numerical examples......Page 142
260 Historical introduction......Page 143
261 Pseudo Runge–Kutta methods\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 144
263 General linear methods......Page 145
264 Numerical examples......Page 148
270 Choice of method......Page 149
271 Variable stepsize......Page 151
272 Interpolation......Page 152
273 Experiments with the Kepler problem......Page 153
274 Experiments with a discontinuous problem......Page 154
300 Rooted trees......Page 158
301 Functions on trees......Page 160
302 Some combinatorial questions......Page 162
304 Enumerating non-rooted trees......Page 165
305 Differentiation......Page 167
306 Taylor’s theorem......Page 169
310 Elementary differentials......Page 171
311 The Taylor expansion of the exact solution......Page 174
312 Elementary weights......Page 176
313 The Taylor expansion of the approximate solution......Page 180
314 Independence of the elementary differentials......Page 181
316 Order conditions for scalar problems......Page 183
317 Independence of elementary weights......Page 184
318 Local truncation error......Page 186
319 Global truncation error......Page 187
320 Methods of orders less than 4......Page 191
321 Simplifying assumptions......Page 192
322 Methods of order 4......Page 196
323 New methods from old......Page 202
324 Order barriers......Page 208
325 Methods of order 5......Page 211
326 Methods of order 6......Page 213
327 Methods of orders greater than 6......Page 216
331 Richardson error estimates......Page 219
332 Methods with built-in estimates......Page 222
333 A class of error-estimating methods......Page 223
334 The methods of Fehlberg......Page 229
335 The methods of Verner......Page 231
336 The methods of Dormand and Prince......Page 232
340 Introduction......Page 234
341 Solvability of implicit equations......Page 235
342 Methods based on Gaussian quadrature......Page 236
343 Reflected methods......Page 240
344 Methods based on Radau and Lobatto quadrature......Page 243
351 Criteria for A-stability......Page 251
352 Padé approximations to the exponential function......Page 253
353 A-stability of Gauss and related methods......Page 259
354 Order stars......Page 261
355 Order arrows and the Ehle barrier......Page 264
356 AN-stability......Page 266
357 Non-linear stability......Page 269
358 BN-stability of collocation methods......Page 273
359 The V and W transformations......Page 275
360 Implementation of implicit Runge–Kutta methods\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 280
361 Diagonally implicit Runge–Kutta methods\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 282
362 The importance of high stage order......Page 283
363 Singly implicit methods......Page 287
364 Generalizations of singly implicit methods......Page 292
365 Effective order and DESIRE methods......Page 294
370 Maintaining quadratic invariants......Page 296
371 Examples of symplectic methods......Page 297
372 Order conditions......Page 298
373 Experiments with symplectic methods......Page 299
380 Motivation......Page 301
381 Equivalence classes of Runge–Kutta methods\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 302
382 The group of Runge–Kutta methods\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 305
383 The Runge–Kutta group\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 308
384 A homomorphism between two groups......Page 311
385 A generalization of G_1......Page 312
386 Recursive formula for the product......Page 313
387 Some special elements of G......Page 318
388 Some subgroups and quotient groups......Page 321
389 An algebraic interpretation of effective order......Page 323
391 Optimal sequences......Page 329
392 Acceptance and rejection of steps......Page 331
393 Error per step versus error per unit step......Page 332
394 Control-theoretic considerations......Page 333
395 Solving the implicit equations......Page 334
400 Fundamentals......Page 338
401 Starting methods......Page 339
402 Convergence......Page 340
404 Consistency......Page 341
405 Necessity of conditions for convergence......Page 343
406 Sufficiency of conditions for convergence......Page 345
410 Criteria for order......Page 350
411 Derivation of methods......Page 351
412 Backward difference methods......Page 353
420 Introduction......Page 354
421 Further remarks on error growth......Page 356
422 The underlying one-step method......Page 358
423 Weakly stable methods......Page 360
424 Variable stepsize......Page 361
430 Introduction......Page 363
431 Stability regions......Page 365
432 Examples of the boundary locus method......Page 367
434 Stability of predictor–corrector methods\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 370
440 Survey of barrier results......Page 373
441 Maximum order for a convergent k-step method......Page 374
442 Order stars for linear multistep methods......Page 377
443 Order arrows for linear multistep methods......Page 379
450 The one-leg counterpart to a linear multistep method......Page 381
451 The concept of G-stability......Page 382
452 Transformations relating one-leg and linear multistep methods......Page 385
454 Concluding remarks on G-stability......Page 386
460 Survey of implementation considerations......Page 387
461 Representation of data......Page 388
462 Variable stepsize for Nordsieck methods......Page 392
463 Local error estimation......Page 393
500 Multivalue–multistage methods\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 394
501 Transformations of methods......Page 396
502 Runge–Kutta methods as general linear methods\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 397
503 Linear multistep methods as general linear methods......Page 398
504 Some known unconventional methods......Page 401
505 Some recently discovered general linear methods......Page 403
510 Definitions of consistency and stability......Page 406
511 Covariance of methods......Page 407
512 Definition of convergence......Page 408
513 The necessity of stability......Page 409
514 The necessity of consistency......Page 410
515 Stability and consistency imply convergence......Page 411
520 Introduction......Page 418
521 Methods with maximal stability order......Page 419
522 Outline proof of the Butcher–Chipman conjecture\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 423
523 Non-linear stability......Page 426
524 Reducible linear multistep methods and G-stability......Page 428
525 G-symplectic methods......Page 429
530 Possible definitions of order......Page 431
531 Local and global truncation errors......Page 433
532 Algebraic analysis of order......Page 434
533 An example of the algebraic approach to order......Page 435
534 The order of a G-symplectic method......Page 437
535 The underlying one-step method......Page 438
541 The types of DIMSIM methods......Page 441
542 Runge–Kutta stability\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 444
543 Almost Runge–Kutta methods\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 447
544 Third order, three-stage ARK methods......Page 450
545 Fourth order, four-stage ARK methods......Page 452
546 A fifth order, five-stage method......Page 454
547 ARK methods for stiff problems......Page 455
550 Doubly companion matrices......Page 457
551 Inherent Runge–Kutta stability\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 459
552 Conditions for zero spectral radius......Page 461
553 Derivation of methods with IRK stability......Page 463
554 Methods with property F......Page 466
555 Some non-stiff methods......Page 467
556 Some stiff methods......Page 468
557 Scale and modify for stability......Page 469
558 Scale and modify for error estimation......Page 471
References......Page 474
Index......Page 480