Ebook: Condition: The Geometry of Numerical Algorithms
- Tags: Algorithms, Mathematics of Computing, Probability Theory and Stochastic Processes, Computational Mathematics and Numerical Analysis, Computational Science and Engineering, Optimization
- Series: Grundlehren der mathematischen Wissenschaften 349
- Year: 2013
- Publisher: Springer-Verlag Berlin Heidelberg
- Edition: 1
- Language: English
- pdf
This book gathers threads that have evolved across different mathematical disciplines into seamless narrative. It deals with condition as a main aspect in the understanding of the performance ---regarding both stability and complexity--- of numerical algorithms. While the role of condition was shaped in the last half-century, so far there has not been a monograph treating this subject in a uniform and systematic way. The book puts special emphasis on the probabilistic analysis of numerical algorithms via the analysis of the corresponding condition. The exposition's level increases along the book, starting in the context of linear algebra at an undergraduate level and reaching in its third part the recent developments and partial solutions for Smale's 17th problem which can be explained within a graduate course. Its middle part contains a condition-based course on linear programming that fills a gap between the current elementary expositions of the subject based on the simplex method and those focusing on convex programming.
This book gathers threads that have evolved across different mathematical disciplines into seamless narrative. It deals with condition as a main aspect in the understanding of the performance ---regarding both stability and complexity--- of numerical algorithms. While the role of condition was shaped in the last half-century, so far there has not been a monograph treating this subject in a uniform and systematic way. The book puts special emphasis on the probabilistic analysis of numerical algorithms via the analysis of the corresponding condition. The exposition's level increases along the book, starting in the context of linear algebra at an undergraduate level and reaching in its third part the recent developments and partial solutions for Smale's 17th problem which can be explained within a graduate course. Its middle part contains a condition-based course on linear programming that fills a gap between the current elementary expositions of the subject based on the simplex method and those focusing on convex programming.
This book gathers threads that have evolved across different mathematical disciplines into seamless narrative. It deals with condition as a main aspect in the understanding of the performance ---regarding both stability and complexity--- of numerical algorithms. While the role of condition was shaped in the last half-century, so far there has not been a monograph treating this subject in a uniform and systematic way. The book puts special emphasis on the probabilistic analysis of numerical algorithms via the analysis of the corresponding condition. The exposition's level increases along the book, starting in the context of linear algebra at an undergraduate level and reaching in its third part the recent developments and partial solutions for Smale's 17th problem which can be explained within a graduate course. Its middle part contains a condition-based course on linear programming that fills a gap between the current elementary expositions of the subject based on the simplex method and those focusing on convex programming.
Content:
Front Matter....Pages I-XXXI
Front Matter....Pages 1-1
Normwise Condition of Linear Equation Solving....Pages 3-19
Probabilistic Analysis....Pages 21-58
Error Analysis of Triangular Linear Systems....Pages 59-75
Probabilistic Analysis of Rectangular Matrices....Pages 77-100
Condition Numbers and Iterative Algorithms....Pages 101-117
Back Matter....Pages 119-120
Front Matter....Pages 121-121
A Condition Number for Polyhedral Conic Systems....Pages 123-145
The Ellipsoid Method....Pages 147-154
Linear Programs and Their Solution Sets....Pages 155-171
Interior-Point Methods....Pages 173-192
The Linear Programming Feasibility Problem....Pages 193-199
Condition and Linear Programming Optimization....Pages 201-222
Average Analysis of the RCC Condition Number....Pages 223-232
Probabilistic Analyses of the GCC Condition Number....Pages 233-254
Back Matter....Pages 255-258
Front Matter....Pages 259-259
A Geometric Framework for Condition Numbers....Pages 261-282
Homotopy Continuation and Newton’s Method....Pages 283-294
Homogeneous Polynomial Systems....Pages 295-329
Smale’s 17th Problem: I....Pages 331-365
Smale’s 17th Problem: II....Pages 367-390
Real Polynomial Systems....Pages 391-417
Probabilistic Analysis of Conic Condition Numbers: I. The Complex Case....Pages 419-437
Back Matter....Pages 467-554
Probabilistic Analysis of Conic Condition Numbers: II. The Real Case....Pages 439-465