This volume is a self-contained, exhaustive exposition of the extrapolation methods theory, and of the various algorithms and procedures for accelerating the convergence of scalar and vector sequences. Many subroutines (written in FORTRAN 77) with instructions for their use are provided on a floppy disk in order to demonstrate to those working with sequences the advantages of the use of extrapolation methods. Many numerical examples showing the effectiveness of the procedures and a consequent chapter on applications are also provided – including some never before published results and applications. Although intended for researchers in the field, and for those using extrapolation methods for solving particular problems, this volume also provides a valuable resource for graduate courses on the subject.
Author(s): Claude Brezinski, Michela Redivo Zaglia
Series: Studies in Computational Mathematics 2
Publisher: Elsevier, Academic Press
Year: 1991
Language: English
Pages: 474
Contents......Page 8
Preface......Page 6
1.1 First steps......Page 11
1.2 What is an extrapolation method?......Page 15
1.3 What is an extrapolation algorithm?......Page 18
1.4 Quasi-linear sequence transformations......Page 21
1.5 Sequence transformations as ratios of determinants......Page 28
1.6 Triangular recursive schemes......Page 31
1.7 Normal forms of the algorithms......Page 36
1.8 Progressive forms of the algorithms......Page 38
1.9 Particular rules of the algorithms......Page 44
1.10 Accelerability and non-accelerability......Page 49
1.11 Optimality......Page 52
1.12 Asymptotic behaviour of sequences......Page 57
2.1 The E-algorithm......Page 64
2.2 Richardson extrapolation process......Page 81
2.3 The \epsilon-algorithm......Page 87
2.4 The G-transformation......Page 104
2.5 Rational extrapolation......Page 110
2.6 Generalizations of the \epsilon-algorithm......Page 117
2.7 Levin's transforms......Page 122
2.8 Overholt's process......Page 128
2.9 \Theta-type algorithms......Page 130
2.10 The iterated \Delta^2 process......Page 137
2.11 Miscellaneous algorithms......Page 140
3.1 Error estimates and acceleration......Page 153
3.2 Convergence tests and acceleration......Page 159
3.3 Construction of asymptotic expansions......Page 167
3.4 Construction of extrapolation processes......Page 173
3.5 Extraction procedures......Page 182
3.6 Automatic selection......Page 186
3.7 Composite sequence transformations......Page 193
3.8 Error control......Page 201
3.9 Contractive sequence transformations......Page 209
3.10 Least squares extrapolation......Page 218
4 Vector Extrapolation Algorithms......Page 221
4.1 The vector \epsilon-algorithm......Page 224
4.2 The topological \epsilon-algorithm......Page 228
4.3 The vector E-algorithm......Page 236
4.4 The recursive projection algorithm......Page 241
4.5 The H-algorithm......Page 246
4.6 The Ford-Sidi algorithms......Page 252
4.7 Miscellaneous algorithms......Page 255
5 Continuous Prediction Algorithms......Page 261
5.1 The Taylor expansion......Page 262
5.2 Confluent Overholt's process......Page 263
5.3 Confluent \epsilon-algorithms......Page 264
5.4 Confluent \rho-algorithm......Page 270
5.5 Confluent G-transform......Page 273
5.6 Confluent E-algorithm......Page 274
5.7 \Theta-type confluent algorithms......Page 275
6 Applications......Page 277
6.1.1 Simple sequences......Page 278
6.1.2 Double sequences......Page 286
6.1.3 Chebyshev and Fourier series......Page 290
6.1.4 Continued fractions......Page 292
6.1.5 Vector sequences......Page 306
6.2 Systems of equations......Page 310
6.2.1 Linear systems......Page 311
6.2.2 Projection methods......Page 315
6.2.3 Regularization and penalty techniques......Page 317
6.2.4 Nonlinear equations......Page 323
6.2.5 Continuation methods......Page 338
6.3 Eigenelements......Page 340
6.3.1 Eigenvalues and eigenvectors......Page 341
6.3.2 Derivatives of eigensystems......Page 344
6.4 Integral and differential equations......Page 346
6.4.1 Implicit Runge-Kutta methods......Page 347
6.4.2 Boundary value problems......Page 348
6.4.3 Nonlinear methods......Page 354
6.4.4 Laplace transform inversion......Page 356
6.4.5 Partial differential equations......Page 360
6.5 Interpolation and approximation......Page 362
6.6 Statistics......Page 365
6.6.1 The jackknife......Page 366
6.6.2 ARMA models......Page 367
6.6.3 Monte-Carlo methods......Page 369
6.7 Integration and differentiation......Page 373
6.7.1 Acceleration of quadrature formulae......Page 374
6.7.2 Nonlinear quadrature formulae......Page 380
6.7.3 Cauchy's principal values......Page 381
6.7.4 Infinite integrals......Page 386
6.7.5 Multiple integrals......Page 395
6.8 Prediction......Page 397
7.1 Programming the algorithms......Page 404
7.2 Computer arithmetic......Page 407
7.3 Programs......Page 410
Bibliography......Page 420
Index......Page 461
