Accuracy and stability of numerical algorithms

Select an Action

Place Hold(s)
Add to My Lists
Email
Print

Title:

Personal Author:

Higham, Nicholas J., 1961-

Edition:

2nd ed.

Publication Information:

Philadelphia, PA : Society for Industrial and Applied Mathematics, 2002

ISBN:

9780898715217

Subject Term:

Numerical analysis -- Data processing

Computer algorithms

Available:*

Library	Item Barcode	Call Number	Material Type	Item Category 1	Status
Searching... PSZ JB	30000010134104	QA297 H53 2002	Open Access Book	Book	Searching... Unknown

This book gives a thorough, up-to-date treatment of the behaviour of numerical algorithms in finite precision arithmetic. It combines algorithmic derivations, perturbation theory, and rounding error analysis, all enlivened by historical perspective and informative quotations. The coverage of the first edition has been expanded and updated, involving numerous improvements. Two new chapters treat symmetric indefinite systems and skew-symmetric systems, and nonlinear systems and Newton's method. Twelve new sections include coverage of additional error bounds for Gaussian elimination, rank revealing LU factorizations, weighted and constrained least squares problems, and the fused multiply-add operation found on some modern computer architectures. This new edition is a suitable reference for an advanced course and can also be used at all levels as a supplementary text from which to draw examples, historical perspective, statements of results, and exercises. In addition the thorough indexes and extensive, up-to-date bibliography are in a readily accessible form.

Author Notes

Nicholas J. Higham is Richardson Professor of Applied Mathematics at the University of Manchester, England. He is the author of more than 80 publications and is a member of the editorial boards of Foundations of Computational Mathematics , the IMA Journal of Numerical Analysis, Linear Algebra and Its Applications , and the SIAM Journal on Matrix Analysis and Applications . His book Handbook of Writing for the Mathematical Sciences (second edition) was published by SIAM in 1998, and his book MATLAB Guide , co-authored with Desmond J. Higham, was published by SIAM in 2000.

Reviews 1

Choice Review

Higham provides a comprehensive exposition of the behavior of numerical algorithms in finite precision arithmetic. The book is highly technical and requires adequate working knowledge of numerical linear algebra and mathematical analysis. Derivation of algorithms, perturbation theory, and rounding error analysis are presented in a unified form, and the use of software tools, especially LAPACK and MATLAB, are emphasized throughout. Comparable to James H. Wilkinson's Rounding Errors in Algebraic Processes (CH, Mar'65), it is unique in the sense that motivation to problems and algorithmic derivations are given in a succinct form: although rounding errors, for example, can be difficult to understand, Higham attempts to treat this topic clearly and concisely. Extensive citations and historical perspectives make it a suitable resource for an advanced course in numerical linear algebra. Recommended. Graduate; faculty; professional. D. E. Bentil University of Vermont

List of Figures	p. xvii
List of Tables	p. xix
Preface to Second Edition	p. xxi
Preface to First Edition	p. xxv
About the Dedication	p. xxix
1 Principles of Finite Precision Computation	p. 1
1.1 Notation and Background	p. 2
1.2 Relative Error and Significant Digits	p. 3
1.3 Sources of Errors	p. 5
1.4 Precision Versus Accuracy	p. 6
1.5 Backward and Forward Errors	p. 6
1.6 Conditioning	p. 8
1.7 Cancellation	p. 9
1.8 Solving a Quadratic Equation	p. 10
1.9 Computing the Sample Variance	p. 11
1.10 Solving Linear Equations	p. 12
1.11 Accumulation of Rounding Errors	p. 14
1.12 Instability Without Cancellation	p. 14
1.13 Increasing the Precision	p. 17
1.14 Cancellation of Rounding Errors	p. 19
1.15 Rounding Errors Can Be Beneficial	p. 22
1.16 Stability of an Algorithm Depends on the Problem	p. 24
1.17 Rounding Errors Are Not Random	p. 25
1.18 Designing Stable Algorithms	p. 26
1.19 Misconceptions	p. 28
1.20 Rounding Errors in Numerical Analysis	p. 28
1.21 Notes and References	p. 28
Problems	p. 31
2 Floating Point Arithmetic	p. 35
2.1 Floating Point Number System	p. 36
2.2 Model of Arithmetic	p. 40
2.3 IEEE Arithmetic	p. 41
2.4 Aberrant Arithmetics	p. 43
2.5 Exact Subtraction	p. 45
2.6 Fused Multiply-Add Operation	p. 46
2.7 Choice of Base and Distribution of Numbers	p. 47
2.8 Statistical Distribution of Rounding Errors	p. 48
2.9 Alternative Number Systems	p. 49
2.10 Elementary Functions	p. 50
2.11 Accuracy Tests	p. 51
2.12 Notes and References	p. 52
Problems	p. 57
3 Basics	p. 61
3.1 Inner and Outer Products	p. 62
3.2 The Purpose of Rounding Error Analysis	p. 65
3.3 Running Error Analysis	p. 65
3.4 Notation for Error Analysis	p. 67
3.5 Matrix Multiplication	p. 69
3.6 Complex Arithmetic	p. 71
3.7 Miscellany	p. 73
3.8 Error Analysis Demystified	p. 74
3.9 Other Approaches	p. 76
3.10 Notes and References	p. 76
Problems	p. 77
4 Summation	p. 79
4.1 Summation Methods	p. 80
4.2 Error Analysis	p. 81
4.3 Compensated Summation	p. 83
4.4 Other Summation Methods	p. 88
4.5 Statistical Estimates of Accuracy	p. 88
4.6 Choice of Method	p. 89
4.7 Notes and References	p. 90
Problems	p. 91
5 Polynomials	p. 93
5.1 Horner's Method	p. 94
5.2 Evaluating Derivatives	p. 96
5.3 The Newton Form and Polynomial Interpolation	p. 99
5.4 Matrix Polynomials	p. 102
5.5 Notes and References	p. 102
Problems	p. 104
6 Norms	p. 105
6.1 Vector Norms	p. 106
6.2 Matrix Norms	p. 107
6.3 The Matrix p-Norm	p. 112
6.4 Singular Value Decomposition	p. 114
6.5 Notes and References	p. 114
Problems	p. 115
7 Perturbation Theory for Linear Systems	p. 119
7.1 Normwise Analysis	p. 120
7.2 Componentwise Analysis	p. 122
7.3 Scaling to Minimize the Condition Number	p. 125
7.4 The Matrix Inverse	p. 127
7.5 Extensions	p. 128
7.6 Numerical Stability	p. 129
7.7 Practical Error Bounds	p. 130
7.8 Perturbation Theory by Calculus	p. 132
7.9 Notes and References	p. 132
Problems	p. 134
8 Triangular Systems	p. 139
8.1 Backward Error Analysis	p. 140
8.2 Forward Error Analysis	p. 142
8.3 Bounds for the Inverse	p. 147
8.4 A Parallel Fan-In Algorithm	p. 149
8.5 Notes and References	p. 151
Problems	p. 153
9 LU Factorization and Linear Equations	p. 157
9.1 Gaussian Elimination and Pivoting Strategies	p. 158
9.2 LU Factorization	p. 160
9.3 Error Analysis	p. 163
9.4 The Growth Factor	p. 166
9.5 Diagonally Dominant and Banded Matrices	p. 170
9.6 Tridiagonal Matrices	p. 174
9.7 More Error Bounds	p. 176
9.8 Scaling and Choice of Pivoting Strategy	p. 177
9.9 Variants of Gaussian Elimination	p. 179
9.10 A Posteriori Stability Tests	p. 180
9.11 Sensitivity of the LU Factorization	p. 181
9.12 Rank-Revealing LU Factorizations	p. 182
9.13 Historical Perspective	p. 183
9.14 Notes and References	p. 187
Problems	p. 192
10 Cholesky Factorization	p. 195
10.1 Symmetric Positive Definite Matrices	p. 196
10.2 Sensitivity of the Cholesky Factorization	p. 201
10.3 Positive Semidefinite Matrices	p. 201
10.4 Matrices with Positive Definite Symmetric Part	p. 208
10.5 Notes and References	p. 209
Problems	p. 211
11 Symmetric Indefinite and Skew-Symmetric Systems	p. 213
11.1 Block LDL[superscript T] Factorization for Symmetric Matrices	p. 214
11.2 Aasen's Method	p. 222
11.3 Block LDL[superscript T] Factorization for Skew-Symmetric Matrices	p. 225
11.4 Notes and References	p. 226
Problems	p. 228
12 Iterative Refinement	p. 231
12.1 Behaviour of the Forward Error	p. 232
12.2 Iterative Refinement Implies Stability	p. 235
12.3 Notes and References	p. 240
Problems	p. 242
13 Block LU Factorization	p. 245
13.1 Block Versus Partitioned LU Factorization	p. 246
13.2 Error Analysis of Partitioned LU Factorization	p. 249
13.3 Error Analysis of Block LU Factorization	p. 250
13.4 Notes and References	p. 256
Problems	p. 257
14 Matrix Inversion	p. 259
14.1 Use and Abuse of the Matrix Inverse	p. 260
14.2 Inverting a Triangular Matrix	p. 262
14.3 Inverting a Full Matrix by LU Factorization	p. 267
14.4 Gauss-Jordan Elimination	p. 273
14.5 Parallel Inversion Methods	p. 278
14.6 The Determinant	p. 279
14.7 Notes and References	p. 281
Problems	p. 283
15 Condition Number Estimation	p. 287
15.1 How to Estimate Componentwise Condition Numbers	p. 288
15.2 The p-Norm Power Method	p. 289
15.3 LAPACK 1-Norm Estimator	p. 292
15.4 Block 1-Norm Estimator	p. 294
15.5 Other Condition Estimators	p. 295
15.6 Condition Numbers of Tridiagonal Matrices	p. 299
15.7 Notes and References	p. 301
Problems	p. 303
16 The Sylvester Equation	p. 305
16.1 Solving the Sylvester Equation	p. 307
16.2 Backward Error	p. 308
16.3 Perturbation Result	p. 313
16.4 Practical Error Bounds	p. 315
16.5 Extensions	p. 316
16.6 Notes and References	p. 317
Problems	p. 318
17 Stationary Iterative Methods	p. 321
17.1 Survey of Error Analysis	p. 323
17.2 Forward Error Analysis	p. 325
17.3 Backward Error Analysis	p. 330
17.4 Singular Systems	p. 331
17.5 Stopping an Iterative Method	p. 335
17.6 Notes and References	p. 337
Problems	p. 337
18 Matrix Powers	p. 339
18.1 Matrix Powers in Exact Arithmetic	p. 340
18.2 Bounds for Finite Precision Arithmetic	p. 346
18.3 Application to Stationary Iteration	p. 351
18.4 Notes and References	p. 351
Problems	p. 352
19 QR Factorization	p. 353
19.1 Householder Transformations	p. 354
19.2 QR Factorization	p. 355
19.3 Error Analysis of Householder Computations	p. 357
19.4 Pivoting and Row-Wise Stability	p. 362
19.5 Aggregated Householder Transformations	p. 363
19.6 Givens Rotations	p. 365
19.7 Iterative Refinement	p. 368
19.8 Gram-Schmidt Orthogonalization	p. 369
19.9 Sensitivity of the QR Factorization	p. 373
19.10 Notes and References	p. 374
Problems	p. 378
20 The Least Squares Problem	p. 381
20.1 Perturbation Theory	p. 382
20.2 Solution by QR Factorization	p. 384
20.3 Solution by the Modified Gram-Schmidt Method	p. 386
20.4 The Normal Equations	p. 386
20.5 Iterative Refinement	p. 388
20.6 The Seminormal Equations	p. 391
20.7 Backward Error	p. 392
20.8 Weighted Least Squares Problems	p. 395
20.9 The Equality Constrained Least Squares Problem	p. 396
20.10 Proof of Wedin's Theorem	p. 400
20.11 Notes and References	p. 402
Problems	p. 405
21 Underdetermined Systems	p. 407
21.1 Solution Methods	p. 408
21.2 Perturbation Theory and Backward Error	p. 409
21.3 Error Analysis	p. 411
21.4 Notes and References	p. 413
Problems	p. 414
22 Vandermonde Systems	p. 415
22.1 Matrix Inversion	p. 416
22.2 Primal and Dual Systems	p. 418
22.3 Stability	p. 423
22.4 Notes and References	p. 428
Problems	p. 430
23 Fast Matrix Multiplication	p. 433
23.1 Methods	p. 434
23.2 Error Analysis	p. 438
23.3 Notes and References	p. 446
Problems	p. 448
24 The Fast Fourier Transform and Applications	p. 451
24.1 The Fast Fourier Transform	p. 452
24.2 Circulant Linear Systems	p. 454
24.3 Notes and References	p. 456
Problems	p. 457
25 Nonlinear Systems and Newton's Method	p. 459
25.1 Newton's Method	p. 460
25.2 Error Analysis	p. 461
25.3 Special Cases and Experiments	p. 462
25.4 Conditioning	p. 464
25.5 Stopping an Iterative Method	p. 467
25.6 Notes and References	p. 468
Problems	p. 469
26 Automatic Error Analysis	p. 471
26.1 Exploiting Direct Search Optimization	p. 472
26.2 Direct Search Methods	p. 474
26.3 Examples of Direct Search	p. 477
26.4 Interval Analysis	p. 481
26.5 Other Work	p. 484
26.6 Notes and References	p. 486
Problems	p. 487
27 Software Issues in Floating Point Arithmetic	p. 489
27.1 Exploiting IEEE Arithmetic	p. 490
27.2 Subtleties of Floating Point Arithmetic	p. 493
27.3 Cray Peculiarities	p. 493
27.4 Compilers	p. 494
27.5 Determining Properties of Floating Point Arithmetic	p. 494
27.6 Testing a Floating Point Arithmetic	p. 495
27.7 Portability	p. 496
27.8 Avoiding Underflow and Overflow	p. 499
27.9 Multiple Precision Arithmetic	p. 501
27.10 Extended and Mixed Precision BLAS	p. 503
27.11 Patriot Missile Software Problem	p. 503
27.12 Notes and References	p. 504
Problems	p. 505
28 A Gallery of Test Matrices	p. 511
28.1 The Hilbert and Cauchy Matrices	p. 512
28.2 Random Matrices	p. 515
28.3 "Randsvd" Matrices	p. 517
28.4 The Pascal Matrix	p. 518
28.5 Tridiagonal Toeplitz Matrices	p. 521
28.6 Companion Matrices	p. 522
28.7 Notes and References	p. 523
Problems	p. 525
A Solutions to Problems	p. 527
B Acquiring Software	p. 573
B.1 Internet	p. 574
B.2 Netlib	p. 574
B.3 MATLAB	p. 575
B.4 NAG Library and NAGWare F95 Compiler	p. 575
C Program Libraries	p. 577
C.1 Basic Linear Algebra Subprograms	p. 578
C.2 EISPACK	p. 579
C.3 LINPACK	p. 579
C.4 LAPACK	p. 579
D The Matrix Computation Toolbox	p. 583
Bibliography	p. 587

Available:*

On Order

Summary

Summary

Author Notes

Reviews 1

Choice Review

Table of Contents