Nicholas J. Higham9780898715217, 0898715210
This second edition expands and updates the coverage of the first edition (1996) and includes numerous improvements to the original material. 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.
An expanded treatment of Gaussian elimination incorporates rook pivoting, along with a thorough discussion of the choice of pivoting strategy and the effects of scaling. The book’s detailed descriptions of floating point arithmetic and of software issues reflect the fact that IEEE arithmetic is now ubiquitous.
Although not designed specifically as a textbook, this new edition is a suitable reference for an advanced course. It can also be used by instructors at all levels as a supplementary text from which to draw examples, historical perspective, statements of results, and exercises. With its thorough indexes and extensive, up-to-date bibliography, the book provides a mine of information in a readily accessible form.
Table of contents :
Front cover ……Page 1
Title page ……Page 3
Date-line ……Page 4
Dedication ……Page 5
Contents ……Page 7
List of Figures ……Page 17
List of Tables ……Page 19
Preface to Second Edition ……Page 21
Preface to First Edition ……Page 25
About the Dedication ……Page 29
1 Principles of Finite Precision Computation ……Page 31
1.1 Notation and Background ……Page 32
1.2 Relative Error and Significant Digits ……Page 33
1.3 Sources of Errors ……Page 35
1.5 Backward and Forward Errors ……Page 36
1.6 Conditioning ……Page 38
1.7 Cancellation ……Page 39
1.8 Solving a Quadratic Equation ……Page 40
1.9 Computing the Sample Variance ……Page 41
1.10 Solving Linear Equations ……Page 42
1.10.1 GEPP Versus Cramer’s Rule ……Page 43
1.12 Instability Without Cancellation ……Page 44
1.12.2 An Innocuous Calculation? ……Page 45
1.12.3 An Infinite Sum ……Page 46
1.13 Increasing the Precision ……Page 47
1.14.1 Computing $(exp{x}-1)/x$ ……Page 49
1.14.2 QR Factorization ……Page 51
1.15 Rounding Errors Can Be Beneficial ……Page 52
1.16 Stability of an Algorithm Depends on the Problem ……Page 54
1.17 Rounding Errors Are Not Random ……Page 55
1.18 Designing Stable Algorithms ……Page 56
1.21 Notes and References ……Page 58
Problems ……Page 61
2 Floating Point Arithmetic ……Page 65
2.1 Floating Point Number System ……Page 66
2.2 Model of Arithmetic ……Page 70
2.3 IEEE Arithmetic ……Page 71
2.4 Aberrant Arithmetics ……Page 73
2.5 Exact Subtraction ……Page 75
2.6 Fused Multiply-Add Operation ……Page 76
2.7 Choice of Base and Distribution of Numbers ……Page 77
2.8 Statistical Distribution of Rounding Errors ……Page 78
2.9 Alternative Number Systems ……Page 79
2.10 Elementary Functions ……Page 80
2.11 Accuracy Tests ……Page 81
2.12 Notes and References ……Page 82
Problems ……Page 87
3 Basics ……Page 91
3.1 Inner and Outer Products ……Page 92
3.3 Running Error Analysis ……Page 95
3.4 Notation for Error Analysis ……Page 97
3.5 Matrix Multiplication ……Page 99
3.6 Complex Arithmetic ……Page 101
3.7 Miscellany ……Page 103
3.8 Error Analysis Demystified ……Page 104
3.10 Notes and References ……Page 106
Problems ……Page 107
4 Summation ……Page 109
4.1 Summation Methods ……Page 110
4.2 Error Analysis ……Page 111
4.3 Compensated Summation ……Page 113
4.5 Statistical Estimates of Accuracy ……Page 118
4.6 Choice of Method ……Page 119
4.7 Notes and References ……Page 120
Problems ……Page 121
5 Polynomials ……Page 123
5.1 Horner’s Method ……Page 124
5.2 Evaluating Derivatives ……Page 126
5.3 The Newton Form and Polynomial Interpolation ……Page 129
5.5 Notes and References ……Page 132
Problems ……Page 134
6 Norms ……Page 135
6.1 Vector Norms ……Page 136
6.2 Matrix Norms ……Page 137
6.3 The Matrix $p$-Norm ……Page 142
6.5 Notes and References ……Page 144
Problems ……Page 145
7 Perturbation Theory for Linear Systems ……Page 149
7.1 Normwise Analysis ……Page 150
7.2 Componentwise Analysis ……Page 152
7.3 Scaling to Minimize the Condition Number ……Page 155
7.4 The Matrix Inverse ……Page 157
7.5 Extensions ……Page 158
7.6 Numerical Stability ……Page 159
7.7 Practical Error Bounds ……Page 160
7.9 Notes and References ……Page 162
Problems ……Page 164
8 Triangular Systems ……Page 169
8.1 Backward Error Analysis ……Page 170
8.2 Forward Error Analysis ……Page 172
8.3 Bounds for the Inverse ……Page 177
8.4 A Parallel Fan-In Algorithm ……Page 179
8.5 Notes and References ……Page 181
Problems ……Page 183
9 LU Factorization and Linear Equations ……Page 187
9.1 Gaussian Elimination and Pivoting Strategies ……Page 188
9.2 LU Factorization ……Page 190
9.3 Error Analysis ……Page 193
9.4 The Growth Factor ……Page 196
9.5 Diagonally Dominant and Banded Matrices ……Page 200
9.6 Tridiagonal Matrices ……Page 204
9.7 More Error Bounds ……Page 206
9.8 Scaling and Choice of Pivoting Strategy ……Page 207
9.9 Variants of Gaussian Elimination ……Page 209
9.10 A Posteriori Stability Tests ……Page 210
9.11 Sensitivity of the LU Factorization ……Page 211
9.12 Rank-Revealing LU Factorizations ……Page 212
9.13 Historical Perspective ……Page 213
9.14 Notes and References ……Page 217
9.14.1 LAPACK ……Page 221
Problems ……Page 222
10 Cholesky Factorization ……Page 225
10.1 Symmetric Positive Definite Matrices ……Page 226
10.1.1 Error Analysis ……Page 227
10.3 Positive Semidefinite Matrices ……Page 231
10.3.1 Perturbation Theory ……Page 233
10.3.2 Error Analysis ……Page 235
10.4 Matrices with Positive Definite Symmetric Part ……Page 238
10.5 Notes and References ……Page 239
10.5.1 LAPACK ……Page 240
Problems ……Page 241
11 Symmetric Indefinite and Skew-Symmetric Systems ……Page 243
11.1 Block LDL$^T$ Factorization for Symmetric Matrices ……Page 244
11.1.1 Complete Pivoting ……Page 245
11.1.2 Partial Pivoting ……Page 246
11.1.3 Rook Pivoting ……Page 249
11.1.4 Tridiagonal Matrices ……Page 251
11.2 Aasen’s Method ……Page 252
11.2.1 Aasen’s Method Versus Block LDL$^T$ Factorization ……Page 254
11.3 Block LDL$^T$ Factorization for Skew-Symmetric Matrices ……Page 255
11.4 Notes and References ……Page 256
Problems ……Page 258
12 Iterative Refinement ……Page 261
12.1 Behaviour of the Forward Error ……Page 262
12.2 Iterative Refinement Implies Stability ……Page 265
12.3 Notes and References ……Page 270
Problems ……Page 272
13 Block LU Factorization ……Page 275
13.1 Block Versus Partitioned LU Factorization ……Page 276
13.2 Error Analysis of Partitioned LU Factorization ……Page 279
13.3 Error Analysis of Block LU Factorization ……Page 280
13.3.1 Block Diagonal Dominance ……Page 281
13.3.2 Symmetric Positive Definite Matrices ……Page 285
13.4 Notes and References ……Page 286
Problems ……Page 287
14 Matrix Inversion ……Page 289
14.1 Use and Abuse of the Matrix Inverse ……Page 290
14.2.1 Unblocked Methods ……Page 292
14.2.2 Block Methods ……Page 295
14.3.1 Method A ……Page 297
14.3.2 Method B ……Page 298
14.3.3 Method C ……Page 299
14.3.4 Method D ……Page 300
14.3.5 Summary ……Page 301
14.4 Gauss-Jordan Elimination ……Page 303
14.5 Parallel Inversion Methods ……Page 308
14.6 The Determinant ……Page 309
14.6.1 Hyman’s Method ……Page 310
14.7 Notes and References ……Page 311
14.7.1 LAPACK ……Page 312
Problems ……Page 313
15 Condition Number Estimation ……Page 317
15.1 How to Estimate Componentwise Condition Numbers ……Page 318
15.2 The $p$-Norm Power Method ……Page 319
15.3 LAPACK 1-Norm Estimator ……Page 322
15.4 Block 1-Norm Estimator ……Page 324
15.5 Other Condition Estimators ……Page 325
15.6 Condition Numbers of Tridiagonal Matrices ……Page 329
15.7 Notes and References ……Page 331
Problems ……Page 333
16 The Sylvester Equation ……Page 335
16.1 Solving the Sylvester Equation ……Page 337
16.2 Backward Error ……Page 338
16.2.1 The Lyapunov Equation ……Page 341
16.3 Perturbation Result ……Page 343
16.4 Practical Error Bounds ……Page 345
16.5 Extensions ……Page 346
16.6 Notes and References ……Page 347
Problems ……Page 348
17 Stationary Iterative Methods ……Page 351
17.1 Survey of Error Analysis ……Page 353
17.2 Forward Error Analysis ……Page 355
17.2.1 Jacobi’s Method ……Page 358
17.2.2 Successive Overrelaxation ……Page 359
17.3 Backward Error Analysis ……Page 360
17.4.1 Theoretical Background ……Page 361
17.4.2 Forward Error Analysis ……Page 363
17.5 Stopping an Iterative Method ……Page 365
Problems ……Page 367
18 Matrix Powers ……Page 369
18.1 Matrix Powers in Exact Arithmetic ……Page 370
18.2 Bounds for Finite Precision Arithmetic ……Page 376
18.4 Notes and References ……Page 381
Problems ……Page 382
19 QR Factorization ……Page 383
19.1 Householder Transformations ……Page 384
19.2 QR Factorization ……Page 385
19.3 Error Analysis of Householder Computations ……Page 387
19.4 Pivoting and Row-Wise Stability ……Page 392
19.5 Aggregated Householder Transformations ……Page 393
19.6 Givens Rotations ……Page 395
19.7 Iterative Refinement ……Page 398
19.8 Gram-Schmidt Orthogonalization ……Page 399
19.9 Sensitivity of the QR Factorization ……Page 403
19.10 Notes and References ……Page 404
19.10.1 LAPACK ……Page 407
Problems ……Page 408
20 The Least Squares Problem ……Page 411
20.1 Perturbation Theory ……Page 412
20.2 Solution by QR Factorization ……Page 414
20.4 The Normal Equations ……Page 416
20.5 Iterative Refinement ……Page 418
20.6 The Seminormal Equations ……Page 421
20.7 Backward Error ……Page 422
20.8 Weighted Least Squares Problems ……Page 425
20.9.1 Perturbation Theory ……Page 426
20.9.2 Methods ……Page 427
20.10 Proof of Wedin’s Theorem ……Page 430
20.11 Notes and References ……Page 432
Problems ……Page 435
21 Underdetermined Systems ……Page 437
21.1 Solution Methods ……Page 438
21.2 Perturbation Theory and Backward Error ……Page 439
21.3 Error Analysis ……Page 441
21.4 Notes and References ……Page 443
Problems ……Page 444
22 Vandermonde Systems ……Page 445
22.1 Matrix Inversion ……Page 446
22.2 Primal and Dual Systems ……Page 448
22.3 Stability ……Page 453
22.3.1 Forward Error ……Page 454
22.3.2 Residual ……Page 455
22.3.3 Dealing with Instability ……Page 456
22.4 Notes and References ……Page 458
Problems ……Page 460
23 Fast Matrix Multiplication ……Page 463
23.1 Methods ……Page 464
23.2 Error Analysis ……Page 468
23.2.1 Winograd’s Method ……Page 469
23.2.2 Strassen’s Method ……Page 470
23.2.3 Bilinear Noncommutative Algorithms ……Page 473
23.2.4 The 3M Method ……Page 474
23.3 Notes and References ……Page 476
Problems ……Page 478
24 The Fast Fourier Transform and Applications ……Page 481
24.1 The Fast Fourier Transform ……Page 482
24.2 Circulant Linear Systems ……Page 484
24.3 Notes and References ……Page 486
Problems ……Page 487
25 Nonlinear Systems and Newton’s Method ……Page 489
25.1 Newton’s Method ……Page 490
25.2 Error Analysis ……Page 491
25.3 Special Cases and Experiments ……Page 492
25.4 Conditioning ……Page 494
25.5 Stopping an Iterative Method ……Page 497
25.6 Notes and References ……Page 498
Problems ……Page 499
26 Automatic Error Analysis ……Page 501
26.1 Exploiting Direct Search Optimization ……Page 502
26.2 Direct Search Methods ……Page 504
26.3.1 Condition Estimation ……Page 507
26.3.2 Fast Matrix Inversion ……Page 508
26.3.3 Roots of a Cubic ……Page 509
26.4 Interval Analysis ……Page 511
26.5 Other Work ……Page 514
26.6 Notes and References ……Page 516
Problems ……Page 517
27 Software Issues in Floating Point Arithmetic ……Page 519
27.1 Exploiting IEEE Arithmetic ……Page 520
27.3 Cray Peculiarities ……Page 523
27.5 Determining Properties of Floating Point Arithmetic ……Page 524
27.6 Testing a Floating Point Arithmetic ……Page 525
27.7.1 Arithmetic Parameters ……Page 526
27.7.2 2×2 Problems in LAPACK ……Page 527
27.7.4 Models of Floating Point Arithmetic ……Page 528
27.8 Avoiding Underflow and Overflow ……Page 529
27.9 Multiple Precision Arithmetic ……Page 531
27.11 Patriot Missile Software Problem ……Page 533
27.12 Notes and References ……Page 534
Problems ……Page 535
28 A Gallery of Test Matrices ……Page 541
28.1 The Hilbert and Cauchy Matrices ……Page 542
28.2 Random Matrices ……Page 545
28.3 “Randsvd” Matrices ……Page 547
28.4 The Pascal Matrix ……Page 548
28.5 Tridiagonal Toeplitz Matrices ……Page 551
28.6 Companion Matrices ……Page 552
28.7 Notes and References ……Page 553
Problems ……Page 555
A Solutions to Problems ……Page 557
B Acquiring Software ……Page 603
B.2 Netlib ……Page 604
B.4 NAG Library and NAGWare F95 Compiler ……Page 605
C Program Libraries ……Page 607
C.1 Basic Linear Algebra Subprograms ……Page 608
C.4 LAPACK ……Page 609
C.4.1 Structure of LAPACK ……Page 610
D The Matrix Computation Toolbox ……Page 613
Bibliography ……Page 617
Name Index ……Page 687
Subject Index ……Page 697
Back cover ……Page 711
Reviews
There are no reviews yet.