Practical Extrapolation Methods: Theory and Applications

Avram Sidi9780521661591, 0521661595

An important problem that arises in many scientific and engineering applications is that of approximating limits of infinite sequences which in most instances converge very slowly. Thus, to approximate limits with reasonable accuracy, it is necessary to compute a large number of terms, and this is in general costly. These limits can be approximated economically and with high accuracy by applying suitable extrapolation (or convergence acceleration) methods to a small number of terms. This book is concerned with the coherent treatment, including derivation, analysis, and applications, of the most useful scalar extrapolation methods. The methods it discusses are geared toward problems that commonly arise in scientific and engineering disciplines. It differs from existing books on the subject in that it concentrates on the most powerful nonlinear methods, presents in-depth treatments of them, and shows which methods are most effective for different classes of practical nontrivial problems; it also shows how to fine-tune these methods to obtain the best numerical results. This state-of-the-art reference on the theory and practice of extrapolation methods will interest mathematicians interested in the theory of the relevant methods as well as giving applied scientists and engineers a practical guide to applying speed-up methods in the solution of difficult computational problems. Avram Sidi is Professor is Numerical Analysis in the Computer Science Department at the Technion-Israel Institute of Technology and holds the Technion Administration Chair in Computer Science. He has published extensively in various areas of numerical analysis and approximation theory and in journals such asMathematics of Computation, SIAM Review, SIAM Journal on Numerical Analysis, Journal of Approximation Theory, Journal of Computational and Applied Mathematics, Numerische Mathematik, and Journal of Scientific Computing. Professor Sidi’s work has involved the development of novel methods, their detailed mathematical analysis, design of efficient algorithms for their implementation, and their application to difficult practical problems. His methods and algorithms are successfully used in various scientific and engineering disciplines.

---

Table of contents :
Cover……Page 1
Half-title……Page 3
Series-title……Page 5
Title……Page 7
Copyright……Page 8
Contents……Page 9
Preface……Page 21
0.1 Why Extrapolation–Convergence Acceleration?……Page 25
0.2 Antilimits Versus Limits……Page 28
0.3 General Algebraic Properties of Extrapolation Methods……Page 29
0.3.1 Linear Summability Methods and the Silverman–Toeplitz Theorem……Page 31
0.4 Remarks on Algorithms for Extrapolation Methods……Page 32
0.5.2 Remarks on Study of Stability……Page 34
0.5.3 Further Remarks……Page 37
0.6 Remark on Iterated Forms of Extrapolation Methods……Page 38
0.7 Relevant Issues in Extrapolation……Page 39
Part I The Richardson Extrapolation Process and Its Generalizations……Page 43
1.1 Introduction and Background……Page 45
1.2 The Idea of Richardson Extrapolation……Page 51
1.3 A Recursive Algorithm for the Richardson Extrapolation Process……Page 52
1.4.1 A Related Set of Polynomials……Page 53
1.4.2 An Equivalent Alternative Definition of Richardson Extrapolation……Page 55
1.5.1 Convergence of Columns……Page 57
1.5.2 Convergence of Diagonals……Page 58
1.6 Stability Analysis of the Richardson Extrapolation Process……Page 61
1.7 A Numerical Example: Richardson Extrapolation on the Zeta Function Series……Page 62
1.8.1 Regularity of Column Sequences……Page 63
1.8.2 Regularity of Diagonal Sequences……Page 64
1.9 The Richardson Extrapolation Process for Infinite Sequences……Page 65
2.1 Richardson Extrapolation with Near Geometric and Harmonic {yl}……Page 66
2.2 Polynomial Richardson Extrapolation……Page 67
2.3 Application to Numerical Differentiation……Page 72
2.4 Application to Numerical Quadrature: Romberg Integration……Page 76
2.5 Rational Extrapolation……Page 79
3.1 Introduction……Page 81
3.2 Algebraic Properties……Page 83
3.3 Recursive Algorithms for A……Page 85
3.3.1 The FS-Algorithm……Page 86
3.3.2 The E-Algorithm……Page 88
3.4 Numerical Assessment of Stability……Page 90
3.5 Analysis of Column Sequences……Page 91
3.5.1 Convergence of the Gamma……Page 92
3.5.2 Convergence and Stability of the A……Page 93
3.5.3 Convergence of the Alpha……Page 96
3.5.4 Conditioning of the System (3.1.4)……Page 97
3.5.5 Conditioning of (3.1.4) for the Richardson Extrapolation Process on Diagonal Sequences……Page 98
3.6 Further Results for Column Sequences……Page 100
3.7 Further Remarks on (3.1.4): “Related” Convergence Acceleration Methods……Page 101
3.8 Epilogue: What Is the E-Algorithm? What Is It Not?……Page 103
4.1 The Set F……Page 105
4.2 Definition of the Extrapolation Method GREP……Page 109
4.3 General Remarks on F and GREP……Page 111
4.4 A Convergence Theory for GREP……Page 112
4.4.1 Study of Process I……Page 113
4.4.2 Study of Process II……Page 114
4.4.3 Further Remarks on Convergence Theory……Page 115
4.5 Remarks on Stability of GREP……Page 116
4.6 Extensions of GREP……Page 117
5.1 The Class B and Related Asymptotic Expansions……Page 119
5.1.1 Description of the Class A……Page 120
5.1.2 Description of the Class B……Page 122
5.1.3 Asymptotic Expansion of F(x) When f(x)………Page 124
5.2 Definition of the D-Transformation……Page 127
5.3 A Simplification of the D-Transformation: The s D-Transformation……Page 129
5.4.1 By Trial and Error……Page 130
5.4.2 Upper Bounds on m……Page 131
5.5 Numerical Examples……Page 135
5.6 Proof of Theorem 5.1.12……Page 136
5.7.1 Integral Properties of Functions in A……Page 141
5.7.2 A Characterization Theorem for Functions in B……Page 142
6.1 The Class b and Related Asymptotic Expansions……Page 145
6.1.1 Description of the Class A……Page 146
6.1.2 Description of the Class b……Page 147
6.1.3 Asymptotic Expansion of A When {a}………Page 150
6.1.4 Remarks on the Asymptotic Expansion of A and a Simplification……Page 153
6.2 Definition of the d-Transformation……Page 154
6.2.2 The d-Transformation for Infinite Sequences……Page 155
6.3.1 The d-Transformation……Page 156
6.4 How to Determine m……Page 157
6.4.2 Upper Bounds on m……Page 158
6.5 Numerical Examples……Page 161
6.6.1 The Function Class A and Its Summation Properties……Page 164
6.6.2 The Sequence Class b and a Characterization Theorem……Page 166
6.6.3 Asymptotic Expansion of A When {an}………Page 169
6.6.4 The d-Transformation……Page 171
6.6.5 Does…A Heuristic Approach……Page 172
6.7 Summary of Properties of Sequences in b……Page 174
6.8 A General Family of Sequences in b……Page 176
6.8.1 Sums of Logarithmic Sequences……Page 177
6.8.2 Sums of Linear Sequences……Page 179
A Special Application……Page 180
6.8.3 Mixed Sequences……Page 181
7.1 Introduction……Page 182
7.2 The W-Algorithm for GREP……Page 183
7.2.1 A Special Case: Phi (y) = y……Page 187
7.3.1 Ordering of the Phi (t)t……Page 188
7.3.2 Technical Preliminaries……Page 190
7.3.3 Putting It All Together……Page 191
7.3.4 Simplifications for the Cases m = 1 and m = 2……Page 195
7.4 Implementation of the d-Transformation by the W-Algorithm……Page 196
7.5 The EW-Algorithm for an Extended GREP……Page 197
8.1 Introduction and Error Formula for A……Page 200
8.2 Examples of Slowly Varying a(t)……Page 204
8.3 Slowly Varying Phi(t) with Arbitrary t……Page 205
8.4.1 Process I with Phi(t) = t H (t) and Complex Delta……Page 209
8.4.2 Process II with Phi(t) = t……Page 213
8.4.3 Process II with Phi(t) = t H (t) and Real Delta……Page 214
8.5 Slowly Varying Phi (t) with lim (tl+1/tl ) = Omega…(0, 1)……Page 217
8.6.1 The Case Phi(t) = t……Page 220
8.6.2 The Case Phi(t) = t H (t) with Real Delta………Page 223
9.1 Introduction……Page 227
9.2 Examples of Quickly Varying a(t)……Page 228
9.3 Analysis of Process I……Page 229
9.4 Analysis of Process II……Page 231
9.5 Can {t} Satisfy (9.1.4) and (9.4.1) Simultaneously?……Page 234
10.2.1 Treatment of the Choice lim………Page 236
10.2.2 Treatment of the Choice………Page 239
10.3 Quickly Varying a(t)……Page 240
11.1 Reduction of GREP for Oscillatory A(y)……Page 242
11.1.1 Review of the W-Algorithm for Infinite-Range Integrals……Page 243
11.2.1 Direct Reduction of the D-Transformation……Page 244
11.2.2 Reduction of the s D-Transformation……Page 245
11.3 Application of the D-Transformation to Fourier Transforms……Page 246
11.4 Application of the D-Transformation to Hankel Transforms……Page 247
11.5 The D-Transformation……Page 248
11.6 Application of the D-Transformation to Hankel Transforms……Page 249
11.7 Application of the D-Transformation to Integrals of Products of Bessel Functions……Page 250
11.8.1 Description of the Class B……Page 251
11.8.2 The W-and m W-Transformations……Page 252
Inverse Laplace Transforms……Page 255
Variants for Hankel Transforms……Page 256
Variants for General Integral Transforms with Oscillatory Kernels……Page 257
11.8.4 Further Variants of the m W-Transformation……Page 258
11.9 Convergence and Stability……Page 259
11.10 Extension to Products of Oscillatory Functions……Page 260
12.2 The d-Transformation on Power Series……Page 262
12.3.1 Rational d-Approximants……Page 264
12.3.2 Closed-Form Expressions for m = 1……Page 265
12.4.1 Padé-like Properties……Page 266
12.4.2 Recursive Computation by the W-Algorithm……Page 268
12.5 Prediction Properties of Rational d-Approximants……Page 269
12.6 Approximation of Singular Points……Page 270
12.7 Efficient Application of the d-Transformation to Power Series with APS……Page 271
12.8 The d-Transformation on Factorial Series……Page 273
12.9 Numerical Examples……Page 274
13.1 Introduction……Page 277
13.2.2 Complex Series Approach……Page 278
13.2.3 Justification of the Complex Series Approach and APS……Page 279
13.3.1 Chebyshev Series……Page 280
13.3.3 Fourier–Legendre Series……Page 281
13.3.4 Fourier–Bessel Series……Page 282
13.5 Direct Approach……Page 283
13.6 Extension of the Complex Series Approach……Page 284
13.7 The H-Transformation……Page 285
14.1.1 The Extrapolation Process and the SGRom-Algorithm……Page 287
14.1.2 Treatment of Column Sequences……Page 289
14.1.3 Treatment of Diagonal Sequences……Page 290
14.1.4 A Further Problem……Page 291
14.2 Computation of Derivatives of Limits and Antilimits……Page 292
14.2.1 Derivative of the Richardson Extrapolation Process……Page 293
14.2.2 GREP: Derivative of GREP……Page 298
Part II Sequence Transformations……Page 301
15.2.1 Derivation of the Method……Page 303
15.2.2 Analytic Properties……Page 305
15.3.1 General Discussion of the Delta-Process……Page 307
15.3.2 Iterated Delta-Process……Page 310
15.3.3 Two Applications of the Iterated Delta-Process……Page 311
15.3.4 A Modified Delta-Process for Logarithmic Sequences……Page 313
15.4 The Lubkin W-Transformation……Page 314
15.5.1 Stability of the Iterated Delta-Process……Page 317
15.5.2 Stability of the Iterated Lubkin Transformation……Page 318
15.7 Further Convergence Results……Page 319
16.1 Derivation of the Shanks Transformation……Page 321
16.2 Algorithms for the Shanks Transformation……Page 325
16.3 Error Formulas……Page 326
16.4 Analysis of Column Sequences When………Page 327
16.4.1 Extensions……Page 333
16.4.2 Application to Numerical Quadrature……Page 336
16.5.1 Linear Sequences……Page 337
16.5.3 Factorial Sequences……Page 340
16.6.1 Totally Monotonic Sequences……Page 341
16.6.2 The Shanks Transformation on Totally Monotonic Sequences……Page 342
16.6.3 Totally Oscillating Sequences……Page 344
16.7 Modifications of the Epsilon-Algorithm……Page 345
17.1 Introduction……Page 347
17.2 Algebraic Structure of the Padé Table……Page 349
17.3 Padé Approximants for Some Hypergeometric Functions……Page 351
17.4 Identities in the Padé Table……Page 353
17.5 Computation of the Padé Table……Page 354
17.6.1 Definition and Algebraic Properties of Continued Fractions……Page 356
17.6.2 Regular C-Fractions and the Padé Table……Page 357
17.7 Padé Approximants and Exponential Interpolation……Page 360
17.8.1 de Montessus’s Theorem and Extensions……Page 362
Treatment of Intermediate Rows……Page 364
17.8.2 Generalized Koenig’s Theorem and Extensions……Page 365
17.9 Convergence of Padé Approximants from Moment Series……Page 366
17.10 Convergence of Padé Approximants from Pólya Frequency Series……Page 369
17.11 Convergence of Padé Approximants from Entire Functions……Page 370
18.2 Padé-Type Approximants……Page 372
18.3 Vanden Broeck–Schwartz Approximations……Page 374
18.4 Multipoint Padé Approximants……Page 375
18.4.1 Two-Point Padé Approximants……Page 377
18.5 Hermite–Padé Approximants……Page 378
18.5.2 Differential Hermite–Padé Approximants……Page 379
18.6.1 Linear (Cross-Multiplied) Approximations……Page 380
18.6.2 Nonlinear (Properly Expanded) Approximations……Page 382
Chebyshev–Padé Table……Page 383
18.7 Baker–Gammel Approximants……Page 384
18.8 Padé–Borel Approximants……Page 386
19.2.1 Derivation of the L-Transformation……Page 387
19.2.2 Algebraic Properties……Page 389
19.2.3 Convergence and Stability……Page 391
19.3 The Sidi S-Transformation……Page 393
19.4 A Note on Factorially Divergent Sequences……Page 395
20.1.1 The Wynn Rho-Algorithm……Page 399
20.1.2 Modification of the Rho-Algorithm……Page 400
20.2 The Brezinski Theta-Algorithm……Page 403
20.2.1 Convergence and Stability of the Theta-Algorithm……Page 404
20.2.2 A Further Convergence Result……Page 407
21.1 The G-Transformation……Page 408
21.2 The Higher-Order G-Transformation……Page 409
21.3.1 The rs-Algorithm……Page 410
21.3.2 The FS/qd-Algorithm……Page 411
21.3.3 Operation Counts of the rs-and FS/qd-Algorithms……Page 413
22.1 The Transformation of Overholt……Page 414
22.2 The Transformation of Wimp……Page 415
22.3.1 Analysis of Overholt’s Method……Page 416
22.3.2 Analysis of Wimp’s Method……Page 418
23.1.1 Derivation of Confluent Forms……Page 420
23.1.2 Convergence Analysis of a Special Case……Page 423
23.2.1 Confluent Epsilon-Algorithm……Page 425
23.2.2 Confluent Form of the Higher-Order G-Transformation……Page 426
23.2.3 Confluent Rho-Algorithm……Page 427
23.2.4 Confluent Overholt Method……Page 428
23.3.1 Application to the D-Transformation and Fourier Integrals……Page 429
24.1 Introduction……Page 431
24.2 Regularity and Acceleration……Page 432
24.2.1 Linearly Convergent Sequences……Page 433
24.2.2 Logarithmically Convergent Sequences……Page 434
24.3 Concluding Remarks……Page 435
Part III Further Applications……Page 437
Multidimensional Euler–Maclaurin Expansions……Page 439
Application of the d-Transformation for Infinite Sequences to {Q}……Page 441
25.1.2 Use of Variable Transformations……Page 442
25.2 Extrapolation of Numerical Solutions of Ordinary Differential Equations……Page 445
25.3.1 Description of Periodic Integral Equations……Page 446
25.3.2 “Corrected” Quadrature Formulas……Page 447
Treatment of the Singular Case……Page 449
Treatment of the Weakly Singular Case……Page 450
25.3.4 Further Developments……Page 451
25.4 Derivation of Numerical Schemes for Time-Dependent Problems from Rational Approximations……Page 452
25.5 Derivation of Numerical Quadrature Formulas from Sequence Transformations……Page 454
25.6.1 Via Numerical Quadrature Followed by Extrapolation……Page 457
25.6.2 Via Extrapolation Followed by Numerical Quadrature……Page 458
25.6.3 Via Extrapolation in a Parameter……Page 459
25.7.2 Gaussian-Type Quadrature Formulas for the Bromwich Integral……Page 461
25.7.3 Inversion via Rational Approximations……Page 463
25.7.4 Inversion via the Discrete Fourier Transform……Page 464
25.8 Simple Problems Associated with {a}………Page 465
25.9 Acceleration of Convergence of Infinite Series with Special Sign Patterns……Page 466
25.10 Acceleration of Convergence of Rearrangements of Infinite Series……Page 467
25.11 Acceleration of Convergence of Infinite Products……Page 468
25.11.1 Extensions……Page 469
25.12 Computation of Infinite Multiple Integrals and Series……Page 470
25.12.2 Sequential d-Transformation for s-D Series……Page 471
25.13 A Hybrid Method: The Richardson–Shanks Transformation……Page 473
25.13.1 An Application……Page 474
25.14 Application of Extrapolation Methods to Ill-Posed Problems……Page 477
25.15 Logarithmically Convergent Fixed-Point Iteration Sequences……Page 478
Part IV Appendices……Page 481
A.1 The O, o, and ~ Symbols……Page 483
A.2 Asymptotic Expansions……Page 484
A.3 Operations with Asymptotic Expansions……Page 485
B.2 Watson’s Lemma……Page 487
C The Gamma Function……Page 489
D.1 Bernoulli Numbers and Polynomials……Page 491
D.2.1 The Euler–Maclaurin Formula for Sums……Page 492
D.2.2 The Euler–Maclaurin Formula for Integrals……Page 493
D.3.1 Application to Harmonic Numbers……Page 494
D.4 A Further Development……Page 495
D.5.1 Algebraic Singularity at One Endpoint……Page 496
D.5.2 Algebraic-Logarithmic Singularity at One Endpoint……Page 497
D.5.3 Algebraic-Logarithmic Singularities at Both Endpoints……Page 498
D.6 Application to Singular Periodic Integrands……Page 499
E.2 Asymptotic Expansion………Page 501
F.2 Chebyshev Polynomials and Expansions……Page 504
3. Richardson Extrapolation Process with Confluence (REP-CONF)……Page 507
8. Higher-Order G-Transformation (G-TRAN)……Page 508
11. The d-Transformation (d-TRAN)……Page 509
14. The Rho-, Rho(Gamma )-, and Rho(Gamma, p)-Algorithms [RHO(Gamma, p)]……Page 510
17. The Wimp Transformation (WIMP)……Page 511
2. Exponential Sequences with Confluence……Page 512
6. Sequences in b/LIN……Page 513
9. Sums of Sequences in b/LOG /LIN /FAC……Page 514
13. (Generalized) Fourier Series and Series of Special Functions……Page 515
Concluding Remarks on Sequence Transformations……Page 516
I.1 General Description……Page 517
I.2 The Code……Page 518
Bibliography……Page 525
Index……Page 539