Sequence Transformations

ISBN-13: 9783642648021 / Angielski / Miękka / 2011 / 252 str.

Jean-Paul Delahaye;Claude Brezinski

Opis

The book gives a very clear and concise summary of the important fields of sequence transformations and convergence acceleration methods. Some of the outstanding features are: - precise definitions of algorithmic sequence transformations, - a study of the power of sequence transformations, - proof of negative results on acceleration methods (namely, that some sequence families are not accelerable), - new algorithms for convergence acceleration (in particular automatic selection procedures). For researchers and graduate students working in or with convergence acceleration methods and sequence transformations, this book is sure to become an important tool. This book is a contribution to the theory and practice of convergence acceleration methods. It gives a new survey point of view on the subject, with positive results (new method of acceleration) and negative results (proofs that some sequence families are not accelerable).

Spis treści

1 The Various Kinds of Algorithmic Sequence Transformations.- 1 — Sequence Transformations.- 2 — Algorithms for Sequences and Algorithmic Transformations.- 3 — k-Normal Algorithms and k-Normal Transformations.- 4 — k-Memories Algorithms and k-Memories Transformations.- 5 — k-Stationary Algorithms and k-Stationary Transformations.- 6 — Rational Transformations and Linear Transformations.- 7 — Diagram of Inclusions.- References.- 2 Decidability and Undecidability in the Limit.- 1 — Definitions and the Normalisation Theorem.- 2 — Problems Concerning Convergence, Turbulence and Periodicity of Sequences.- 3 — Algorithms for Counting the Number of Accumulation Points.- 4 — Algorithms for Determining the Period of an Asymptotically Periodic Sequence.- (a) Methods of Detector Coefficients.- (b) Methods Using Barycenters.- (c) Limitation Results.- 5 — Families of Sequences of Iterations.- 6 — Two General Results Concerning the Decidability in the Limit.- Appendix 1 — Strength of an Accumulation Point and Quickness of a Sequence.- (a) Strength of an Accumulation Point.- (b) Quickness of a Sequence.- Appendix 2 — Decidability in the Limit and Recursivity..- Appendix 3 — Decidability of the Convergence, Turbulence and Asymptotic Periodicity of a Continuous Function.- References.- 3 Algorithms for Extracting Convergent Subsequences.- 1 — T-Algorithms.- 2 — S-Algorithms.- 3 — U-Algorithms.- 4 — Limitation Results.- References.- 4 The Partially Ordered Systems of Accelerable Families.- 1 — Acceleration Velocity, Acceleration, Prediction.- 2 — Transformations for Convergence Acceleration, Accelerable Families.- 3 — Examples of Accelerable Families of Sequences.- 4 — Relationships Between the Ordered Systems of Accelerable Families.- 5 — Maximal Accelerable Families.- References.- 5 Non-Accelerable Families of Sequences.- 1 — Remanence and First Applications.- 2 — Families of Monotones Sequences.- 3 — Alternating and Oscillating Sequences.- 4 — Families of Linearly Convergent Sequences.- 5 — Families of Logarithmically Convergent Sequences.- 6 — Table of Results.- References.- 6 Accelerating the Convergence of Linear Sequences.- 1 — Linearly Convergent and Periodico-Linearly Convergent Sequences.- (a) Problems on Convergence.- (b) Problems on Pseudo-Periodicity.- (c) Applications.- 2 — Acceleration of Periodico-Linear Sequences.- 3 — Optimality of the ?2 of Aitken.- (a) Algebraical Optimality.- (b) The Impossibility of Enlarging Lin.- (c) Acceleration of Degree 1+s on Lin.- References.- 7 Automatic Selection of Sequence Transformations.- 1 — General Methods.- (a) General Definitions for Selection Methods.- (b) Two Results on Selection Methods.- (c) Numerical Experiments.- 2 — Automatic Choice of Sequences of Parameters in the Richardson Extrapolation.- (a) Exactness Properties of the Transformations Obtained from the Richardson Process.- (b) Selection Among k-th Column Transformations.- (c) Selection Among k-th Diagonal Transformations.- (d) Selection Among Fast Diagonal Transformations.- References.