Accurate Numerical Algorithms: A Collection of Research Papers

ISBN-13: 9783540514770 / Angielski / Miękka / 1989 / 234 str.

Christian Ullrich; Ja1/4rgen Wolff Von Gudenberg

Opis

The ESPRIT Project 1072, DIAMOND (Development and Integration of Accurate Mathematical Operations in Numerical Data-Processing) was carried out from January 1986 through April 1989 by the five partners Siemens Miinchen (prime contractor), CWI Amsterdam, University of Karlsruhe (Institut fiir Ange- wandte Mathematik), NAG Oxford and University of Bath (subcontractor to NAG). The technical work was divided into three main work packages with one additional work package for miscellaneous topics. The major goals of this project, according to its title, were to develop a set of accurate numerical algorithms (work package 3) and to provide tools to support their implementation by means of an embedding of accurate arithmetic into programming languages (work package 1) and by transform- ation techniques which either improve the accuracy of expression evaluation or detect and eliminate presumable deficiencies in accuracy in existing programs (work package 2). A great variety of working papers describing and discussing the results of these work packages have been written during the collaboration of the project. This book (Accurate Numericlll A 19oritltms) mainly summarizes the results of work package 3, carried through by the two partners Karlsruhe University and NAG Oxford under the leadership of the editors and Dr. G. S. Hodgson. Another book (Improving Floating-Point Programming, J. Tliley, to appear 1989), edited by P.J.L. Wallis, which is one of the DIAMOND project's final deliverables, concentrates more on the fundamental tools.

Spis treści

Highly Accurate Numerical Algorithms.- 0. Introduction.- 1. Design of E-Methods.- 2. Application of Brouwer’s Fixed-Point Theorem.- 3. Eigenvalues.- 4. The Application of Theorems on Zeros in the Complex Plane.- 5. Linear Systems for Sparse Matrices.- 6. Quadrature.- 7. Nonlinear Systems.- References.- Appendix. The PASCAL-SC Demonstration Package.- Solving the Complex Algebraic Eigenvalue Problem with Verified High Accuracy.- 1. Introduction.- 2. Mathematical Foundations.- 3. Inclusion of the Complex Algebraic Eigenvalue Problem.- 4. The Inclusion Algorithm.- References.- Techniques for Generating Accurate Eigensolutions in ADA.- 1. Introduction.- 2. Method.- 3. Implementation.- 4. Appendix.- 5. Glossary.- References.- Enclosing all Eigenvalues of Symmetric Matrices.- 1. Introduction.- 2. Simple Method for Computing Enclosures of Eigenvalues.- 3. Computing Eigenvector Approximations with High Accuracy.- 4. Computing Eigenvalue Enclosures with High Accuracy.- 5. Computing Eigenvector Enclosures.- 6. Numerical Examples.- References.- Computing Accurate Eigenvalues of a Hermitian Matrix.- 1. Introduction.- 2. A Jacobi Method for the Hermitian Eigenvalue Problem.- 3. Inclusion of the Estimated Eigenvalues.- 4. Improvement of the Eigensolution by Newton Iterations.- 5. Adapting the Algorithm to Ada.- 6. Ada Package Specification.- 7. Test Results.- 8. Conclusions.- References.- Verified Inclusion of all Roots of a Complex Polynomial by means of Circular Arithmetic.- 1. Introduction.- 2. Refinement of the Schur/Cohn Algorithm.- 3. Refined Bisecting Process.- 4. Solving Algorithm.- 5. Performance, Example.- 6. Conclusions.- Literature.- Verified Results for Linear Systems with Sparse Matrices.- 1. Introduction.- 2. Method Description.- 3. Method Implementation.- 4. Remarks.- References.- Self-Validating Numerical Quadrature.- 1. Review.- 2. Fundamentals.- 3. Verified Computation of the Procedure Error via Automatic Differentiation.- 4. Numerical Quadrature via Modified Romberg-Extrapolation.- 5. Faster Reduction of the Total Error via Adaptive Refinement.- 6. Numerical Results.- References.- Solving Nonlinear Equations with Verification of Results.- 1. Introduction.- 2. Inclusion of Zeros.- 3. Numerical Problems with Traditional Methods.- 4. Improvement of Theoretical Behaviour of Traditional Methods.- 5. Condition of a System of Nonlinear Equations.- 6. Implementation Aspects.- References.