Miller / Wrathall Software for Roundoff Analysis of Matrix Algorithms

1. Auflage 2014
ISBN: 978-1-4832-6515-5
Verlag: Elsevier Science & Techn.
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 166 Seiten, Web PDF

Computer Science and Applied Mathematics: A Series of Monographs and Textbooks: Software for Roundoff Analysis of Matrix Algorithms focuses on the presentation of techniques and software tools for analyzing the propagation of rounding error in matrix algorithms. The publication looks into some elements of error analysis, concepts from linear algebra and analysis, and directed graphs. Discussions focus on arithmetic graphs, sums of path products, linear transformations, Minkowski sums and Cartesian products, and elementary concepts from analysis. The text then examines software for roundoff analysis, including rounding and perturbations of the computational problem, comparing rounding errors with problem sensitivity, reverse condition numbers, and comparing two algorithms. The book ponders on case studies, as well as Gaussian elimination with iterative improvement, Cholesky factorization, Gauss-Jordan elimination, variants of the Gram-Schmidt method, and Cholesky factors after rank-one modifications. The text is a valuable reference for researchers interested in the techniques and software tools involved in the analysis of the propagation of rounding error in matrix algorithms.

Autoren/Hrsg.

Miller, Webb

Wrathall, Celia

Inhaltsverzeichnis

1;Front Cover;1
2;Software for Roundoff Analysis of Matrix Algorithms;4
3;Copyright Page;5
4;Table of Contents;6
5;Preface;8
6;CHAPTER 1. SOME ELEMENTS OF ERROR ANALYSIS;14
6.1;1.1 Introduction;14
6.2;1.2 Errors in Computation;17
6.3;1.3 The Machine Rounding Unit;26
6.4;1.4 Backward Roundoff Analysis;29
6.5;1.5 Case Study 1: Triangular Matrix Inversion;35
6.6;1.6 Case Study 2: The Normal Equations;39
6.7;1.7 Case Study 3: The Hat Matrix;41
6.8;Notes and References;48
7;CHAPTER 2. CONCEPTS FROM LINEAR ALGEBRA AND ANALYSIS;50
7.1;2.1 Introduction;50
7.2;2.2 Elementary Concepts from Analysis;51
7.3;2.3 Wilkinson Numbers;55
7.4;2.4 Norms;57
7.5;2.5 Linear Transformations;60
7.6;2.6 Minkowski Sums and Cartesian Products;65
7.7;2.7 Computing Wilkinson Numbers;66
7.8;2.8 Operator Norms;71
7.9;2.9 Differentiation;72
8;CHAPTER 3. DIRECTED GRAPHS;76
8.1;3.1 Introduction;76
8.2;3.2 Arithmetic Graphs;79
8.3;3.3 The Weak Composition Model;84
8.4;3.4 Sums of Path Products;86
8.5;3.5 Differentiation in Graphs;90
8.6;3.6 Improved Calculation of Derivatives;95
9;CHAPTER 4. SOFTWARE FOR ROUNDOFF ANALYSIS;98
9.1;4.1 Introduction;98
9.2;4.2 Rounding and Perturbations of the Computational Problem;99
9.3;4.3 Comparing Rounding Errors with Problem Sensitivity;102
9.4;4.4 The Weak Composition Model;107
9.5;4.5 Reverse Condition Numbers;109
9.6;4.6 Comparing Two Algorithms;116
9.7;4.7 Using the Software Package;118
10;CHAPTER 5. CASE STUDIES;126
10.1;5.1 Case Study 4: The Cholesky Factorization;126
10.2;5.2 Case Study 5: Gaussian Elimination;129
10.3;5.3 Case Study 6: Gaussian Elimination with Iterative Improvement;133
10.4;5.4 Case Study 7: Gauss-Jordan Elimination;134
10.5;5.5 Case Study 8: Householder Transformations for Least-Squares Problems;135
10.6;5.6 Case Study 9: Rational QR Methods;138
10.7;5.7 Case Study 10: Downdating the QR Factorization;141
10.8;5.8 Case Study 11: The Characteristic Polynomial;142
10.9;5.9 Case Study 12: Representations of Symmetric Matrices;144
10.10;5.10 Case Study 13: Variants of the Gram-Schmidt Method;147
10.11;5.11 Case Study 14: Cholesky Factors after Rank-One Modifications;150
11;Appendix: Fast Givens Transformations;154
12;Bibliography;156
13;Index ;162