Lectures on Finite Precision Computations

This book combines techniques from engineering and mathematics to describe the rigorous and novel theory of computability in finite precision.

Françoise Chaitin–chateli (Author), Valérie Frayssé (Author)

9780898713589

Paperback / softback, published 28 February 1997

252 pages
22.8 x 15.1 x 1.4 cm, 0.455 kg

'Chaitin-Chatelin and Frayssé provide a rigorous basis for error analysis and asses the quality and reliability of computations. ... Problems and algorithm derivations, toolboxes for computer experimentation, are given in a clear succinct form.' D. E. Bentil, CHOICE

Devoted to the assessment of the quality of numerical results produced by computers, this book addresses the question: How does finite precision affect the convergence of numerical methods on the computer when convergence has been proven in exact arithmetic? Finite precision computations are at the heart of the daily activities of many engineers and researchers in all branches of applied mathematics. Written in an informal style, the book combines techniques from engineering and mathematics to describe the rigorous and novel theory of computability in finite precision. In the challenging cases of nonlinear problems, theoretical analysis is supplemented by software tools to explore the stability on the computer. Roundoff errors are often considered negatively, as a severe limitation on the purity of exact computations. The authors show how the necessarily finite precision of the computer arithmetic can be turned into an asset to describe physical phenomena.

Foreword Iain S. Duff
Preface
General Presentation Notations. Part I. Computability in Finite Precision: Well-Posed Problems
Approximations
Convergence in Exact Arithmetic
Computability in Finite Precision
Gaussian Elimination
Forward Error Analysis
The Influence of Singularities
Numerical Stability in Exact Arithmetic
Computability in Finite Precision for Iterative and Approximate Methods
The Limit of Numerical Stability in Finite Precision
Arithmetically Robust Convergence
The Computed Logistic
Bibliographical Comments. Part II. Measures of Stability for Regular Problems: Choice of Data and Class of Perturbations
Choice of Norms: Scaling
Conditioning of Regular Problems
Simple Roots of Polynomials
Factorizations of a Complex Matrix
Solving Linear Systems
Functions of a Square Matrix
Concluding Remarks
Bibliographical Comments. Part III. Computation in the Neighbourhood of a Singularity: Singular Problems Which are Well-Posed
Condition Numbers of Hölder-Singularities
Computability of Ill-Posed Problems
Singularities of z ----> A - zI
Distances to Singularity
Unfolding of Singularity
Spectral Portraits
Bibliographical Comments. Part IV. Arithmetic Quality of Reliable Algorithms: Forward and Backward Analyses
Backward Error
Quality of Reliable Software
Formulae for Backward Errors
Influence of the Class of Perturbations
Iterative Refinement for Backward Stability
Robust Reliability and Arithmetic Quality
Bibliographical Comments. Part V. Numerical Stability in Finite Precision: Iterative and Approximate Methods
Numerical Convergence of Iterative Solvers
Stopping Criteria in Finite Precision
Robust Convergence
The Computed Logistic Revisited
Care of Use
Bibliographical Comments. PartVI. Software Tools for Round-Off Error Analysis in Algorithms. A Historical Perspective
The Assessment of the Quality of the Numerical Software
Backward Error Analysis in Libraries
Sensitivity Analysis
Interval Analysis
Probabilisitc Models
Computer Algebra
Bibliographical Comments. Part VII. The Toolbox PRECISE for Computer Experimentation. What is PRECISE?
Module for Backward Error Analysis
Sample Size
Backward Analysis with PRECISE
Dangerous Border and Unfolding of a Singularity
Summary of Module 1
Bibliographical Comments. Part VIII. Experiments with PRECISE. Format of the Examples
Backward Error Analysis for Linear Systems
Computer Unfolding of Singularity
Dangerous Border and Distance to Singularity
Roots of Polynomials
Eigenvalue Problems
Conclusion
Bibliographical Comments. Part IX. Robustness to Nonnormality. Nonnormality and Spectral Instability
Nonnormality in Physics and Technology
Convergence of Numerical Methods in Exact Arithmetic
Influence on Numerical Software
Bibliographical Comments. Part V. Qualitative Computing. Sensitivity and Pseudosolutions for F (x) = y: Pseudospectra of Matrices
Pseudozeroes of Polynomials
Divergence Portrait for the Complex Logistic Iteration
Qualitative Computation of a Jordan Form
Beyond Linear Perturbation Theory
Bibliographical Comments. Part XI. More Numerical Illustrations with PRECISE: Annex: The Toolbox PRECISE for MATLAB
Index
Bibliography.

Subject Areas: Miscellaneous items [WZ]