Accuracy and Stability of Numerical Algorithms, Second Edition

Cover......Page 1
Accuracy and Stability of Numerical Algorithms......Page 2
Copyright - ISBN: 0898715210......Page 3
Contents......Page 6
List of Figures......Page 16
List of Tables......Page 18
Preface to Second Edition......Page 20
Preface to First Edition......Page 24
About the Dedication......Page 28
1 Principles of Finite Precision Computation......Page 30
1.1 Notation and Background......Page 31
1.2 Relative Error and Significant Digits......Page 32
1.3 Sources of Errors......Page 34
1.5 Backward and Forward Errors......Page 35
1.6 Conditioning......Page 37
1.7 Cancellation......Page 38
1.8 Solving a Quadratic Equation......Page 39
1.9 Computing the Sample Variance......Page 40
1.10 Solving Linear Equations......Page 41
1.10.1 GEPP Versus Cramer's Rule......Page 42
1.12 Instability Without Cancellation......Page 43
1.12.2 An Innocuous Calculation?......Page 44
1.12.3 An Infinite Sum......Page 45
1.13 Increasing the Precision......Page 46
1.14.1 Computing (e^x - 1)/x......Page 48
1.14.2 QR Factorization......Page 50
1.15 Rounding Errors Can Be Beneficial......Page 51
1.16 Stability of an Algorithm Depends on the Problem......Page 53
1.17 Rounding Errors Are Not Random......Page 54
1.18 Designing Stable Algorithms......Page 55
1.21 Notes and References......Page 57
Problems......Page 60
2 Floating Point Arithmetic......Page 64
2.1 Floating Point Number System......Page 65
2.2 Model of Arithmetic......Page 69
2.3 IEEE Arithmetic......Page 70
2.4 Aberrant Arithmetics......Page 72
2.5 Exact Subtraction......Page 74
2.6 Fused Multiply-Add Operation......Page 75
2.7 Choice of Base and Distribution of Numbers......Page 76
2.8 Statistical Distribution of Rounding Errors......Page 77
2.9 Alternative Number Systems......Page 78
2.10 Elementary Functions......Page 79
2.11 Accuracy Tests......Page 80
2.12 Notes and References......Page 81
Problems......Page 86
3 Basics......Page 90
3.1 Inner and Outer Products......Page 91
3.3 Running Error Analysis......Page 94
3.4 Notation for Error Analysis......Page 96
3.5 Matrix Multiplication......Page 98
3.6 Complex Arithmetic......Page 100
3.7 Miscellany......Page 102
3.8 Error Analysis Demystified......Page 103
3.10 Notes and References......Page 105
Problems......Page 106
4 Summation......Page 108
4.1 Summation Methods......Page 109
4.2 Error Analysis......Page 110
4.3 Compensated Summation......Page 112
4.5 Statistical Estimates of Accuracy......Page 117
4.6 Choice of Method......Page 118
4.7 Notes and References......Page 119
Problems......Page 120
5 Polynomials......Page 122
5.1 Horner's Method......Page 123
5.2 Evaluating Derivatives......Page 125
5.3 The Newton Form and Polynomial Interpolation......Page 128
5.5 Notes and References......Page 131
Problems......Page 133
6 Norms......Page 134
6.1 Vector Norms......Page 135
6.2 Matrix Norms......Page 136
6.3 The Matrix p-Norm......Page 141
6.5 Notes and References......Page 143
Problems......Page 144
7 Perturbation Theory for Linear Systems......Page 148
7.1 Normwise Analysis......Page 149
7.2 Componentwise Analysis......Page 151
7.3 Scaling to Minimize the Condition Number......Page 154
7.4 The Matrix Inverse......Page 156
7.5 Extensions......Page 157
7.6 Numerical Stability......Page 158
7.7 Practical Error Bounds......Page 159
7.9 Notes and References......Page 161
Problems......Page 163
8 Triangular Systems......Page 168
8.1 Backward Error Analysis......Page 169
8.2 Forward Error Analysis......Page 171
8.3 Bounds for the Inverse......Page 176
8.4 A Parallel Fan-In Algorithm......Page 178
8.5 Notes and References......Page 180
Problems......Page 182
9 LU Factorization and Linear Equations......Page 186
9.1 Gaussian Elimination and Pivoting Strategies......Page 187
9.2 LU Factorization......Page 189
9.3 Error Analysis......Page 192
9.4 The Growth Factor......Page 195
9.5 Diagonally Dominant and Banded Matrices......Page 199
9.6 Tridiagonal Matrices......Page 203
9.7 More Error Bounds......Page 205
9.8 Scaling and Choice of Pivoting Strategy......Page 206
9.9 Variants of Gaussian Elimination......Page 208
9.10 A Posteriori Stability Tests......Page 209
9.11 Sensitivity of the LU Factorization......Page 210
9.12 Rank-Revealing LU Factorizations......Page 211
9.13 Historical Perspective......Page 212
9.14 Notes and References......Page 216
9.14.1 LAPACK......Page 220
Problems......Page 221
10 Cholesky Factorization......Page 224
10.1 Symmetric Positive Definite Matrices......Page 225
10.1.1 Error Analysis......Page 226
10.3 Positive Semidefinite Matrices......Page 230
10.3.1 Perturbation Theory......Page 232
10.3.2 Error Analysis......Page 234
10.4 Matrices with Positive Definite Symmetric Part......Page 237
10.5 Notes and References......Page 238
10.5.1 LAPACK......Page 239
Problems......Page 240
11 Symmetric Indefinite and Skew-Symmetric Systems......Page 242
11.1 Block LDL^T Factorization for Symmetric Matrices......Page 243
11.1.1 Complete Pivoting......Page 244
11.1.2 Partial Pivoting......Page 245
11.1.3 Rook Pivoting......Page 248
11.1.4 Tridiagonal Matrices......Page 250
11.2 Aasen's Method......Page 251
11.2.1 Aasen's Method Versus Block LDL^T Factorization......Page 253
11.3 Block LDL^T Factorization for Skew-Symmetric Matrices......Page 254
11.4 Notes and References......Page 255
Problems......Page 257
12 Iterative Refinement......Page 260
12.1 Behaviour of the Forward Error......Page 261
12.2 Iterative Refinement Implies Stability......Page 264
12.3 Notes and References......Page 269
Problems......Page 271
13 Block LU Factorization......Page 274
13.1 Block Versus Partitioned LU Factorization......Page 275
13.2 Error Analysis of Partitioned LU Factorization......Page 278
13.3 Error Analysis of Block LU Factorization......Page 279
13.3.1 Block Diagonal Dominance......Page 280
13.3.2 Symmetric Positive Definite Matrices......Page 284
13.4 Notes and References......Page 285
Problems......Page 286
14 Matrix Inversion......Page 288
14.1 Use and Abuse of the Matrix Inverse......Page 289
14.2.1 Unblocked Methods......Page 291
14.2.2 Block Methods......Page 294
14.3.1 Method A......Page 296
14.3.2 Method B......Page 297
14.3.3 Method C......Page 298
14.3.4 Method D......Page 299
14.3.5 Summary......Page 300
14.4 Gauss-Jordan Elimination......Page 302
14.5 Parallel Inversion Methods......Page 307
14.6 The Determinant......Page 308
14.6.1 Hyman's Method......Page 309
14.7 Notes and References......Page 310
14.7.1 LAPACK......Page 311
Problems......Page 312
15 Condition Number Estimation......Page 316
15.1 How to Estimate Componentwise Condition Numbers......Page 317
15.2 The p-Norm Power Method......Page 318
15.3 LAPACK 1-Norm Estimator......Page 321
15.4 Block 1-Norm Estimator......Page 323
15.5 Other Condition Estimators......Page 324
15.6 Condition Numbers of Tridiagonal Matrices......Page 328
15.7 Notes and References......Page 330
Problems......Page 332
16 The Sylvester Equation......Page 334
16.1 Solving the Sylvester Equation......Page 336
16.2 Backward Error......Page 337
16.2.1 The Lyapunov Equation......Page 340
16.3 Perturbation Result......Page 342
16.4 Practical Error Bounds......Page 344
16.5 Extensions......Page 345
16.6 Notes and References......Page 346
Problems......Page 347
17 Stationary Iterative Methods......Page 350
17.1 Survey of Error Analysis......Page 352
17.2 Forward Error Analysis......Page 354
17.2.1 Jacobi's Method......Page 357
17.2.2 Successive Overrelaxation......Page 358
17.3 Backward Error Analysis......Page 359
17.4.1 Theoretical Background......Page 360
17.4.2 Forward Error Analysis......Page 362
17.5 Stopping an Iterative Method......Page 364
Problems......Page 366
18 Matrix Powers......Page 368
18.1 Matrix Powers in Exact Arithmetic......Page 369
18.2 Bounds for Finite Precision Arithmetic......Page 375
18.4 Notes and References......Page 380
Problems......Page 381
19 QR Factorization......Page 382
19.1 Householder Transformations......Page 383
19.2 QR Factorization......Page 384
19.3 Error Analysis of Householder Computations......Page 386
19.4 Pivoting and Row-Wise Stability......Page 391
19.5 Aggregated Householder Transformations......Page 392
19.6 Givens Rotations......Page 394
19.7 Iterative Refinement......Page 397
19.8 Gram-Schmidt Orthogonalization......Page 398
19.9 Sensitivity of the QR Factorization......Page 402
19.10 Notes and References......Page 403
19.10.1 LAPACK......Page 406
Problems......Page 407
20 The Least Squares Problem......Page 410
20.1 Perturbation Theory......Page 411
20.2 Solution by QR Factorization......Page 413
20.4 The Normal Equations......Page 415
20.5 Iterative Refinement......Page 417
20.6 The Seminormal Equations......Page 420
20.7 Backward Error......Page 421
20.8 Weighted Least Squares Problems......Page 424
20.9.1 Perturbation Theory......Page 425
20.9.2 Methods......Page 426
20.10 Proof of Wedin's Theorem......Page 429
20.11 Notes and References......Page 431
Problems......Page 434
21 Underdetermined Systems......Page 436
21.1 Solution Methods......Page 437
21.2 Perturbation Theory and Backward Error......Page 438
21.3 Error Analysis......Page 440
21.4 Notes and References......Page 442
Problems......Page 443
22 Vandermonde Systems......Page 444
22.1 Matrix Inversion......Page 445
22.2 Primal and Dual Systems......Page 447
22.3 Stability......Page 452
22.3.1 Forward Error......Page 453
22.3.2 Residual......Page 454
22.3.3 Dealing with Instability......Page 455
22.4 Notes and References......Page 457
Problems......Page 459
23 Fast Matrix Multiplication......Page 462
23.1 Methods......Page 463
23.2 Error Analysis......Page 467
23.2.1 Winograd's Method......Page 468
23.2.2 Strassen's Method......Page 469
23.2.3 Bilinear Noncommutative Algorithms......Page 472
23.2.4 The 3M Method......Page 473
23.3 Notes and References......Page 475
Problems......Page 477
24 The Fast Fourier Transform and Applications......Page 480
24.1 The Fast Fourier Transform......Page 481
24.2 Circulant Linear Systems......Page 483
24.3 Notes and References......Page 485
Problems......Page 486
25 Nonlinear Systems and Newton's Method......Page 488
25.1 Newton's Method......Page 489
25.2 Error Analysis......Page 490
25.3 Special Cases and Experiments......Page 491
25.4 Conditioning......Page 493
25.5 Stopping an Iterative Method......Page 496
25.6 Notes and References......Page 497
Problems......Page 498
26 Automatic Error Analysis......Page 500
26.1 Exploiting Direct Search Optimization......Page 501
26.2 Direct Search Methods......Page 503
26.3.1 Condition Estimation......Page 506
26.3.2 Fast Matrix Inversion......Page 507
26.3.3 Roots of a Cubic......Page 508
26.4 Interval Analysis......Page 510
26.5 Other Work......Page 513
26.6 Notes and References......Page 515
Problems......Page 516
27 Software Issues in Floating Point Arithmetic......Page 518
27.1 Exploiting IEEE Arithmetic......Page 519
27.3 Cray Peculiarities......Page 522
27.5 Determining Properties of Floating Point Arithmetic......Page 523
27.6 Testing a Floating Point Arithmetic......Page 524
27.7.1 Arithmetic Parameters......Page 525
27.7.2 2 x 2 Problems in LAPACK......Page 526
27.7.4 Models of Floating Point Arithmetic......Page 527
27.8 Avoiding Underflow and Overflow......Page 528
27.9 Multiple Precision Arithmetic......Page 530
27.11 Patriot Missile Software Problem......Page 532
27.12 Notes and References......Page 533
Problems......Page 534
28 A Gallery of Test Matrices......Page 540
28.1 The Hilbert and Cauchy Matrices......Page 541
28.2 Random Matrices......Page 544
28.3 "Randsvd" Matrices......Page 546
28.4 The Pascal Matrix......Page 547
28.5 Tridiagonal Toeplitz Matrices......Page 550
28.6 Companion Matrices......Page 551
28.7 Notes and References......Page 552
Problems......Page 554
Ch.1......Page 556
Ch.2......Page 560
Ch.3......Page 564
Ch.4......Page 567
Ch.5......Page 570
Ch.6......Page 571
Ch.7......Page 574
Ch.8......Page 578
Ch.9......Page 580
Ch.10......Page 582
Ch.11......Page 583
Ch.13......Page 585
Ch.14......Page 587
Ch.16......Page 590
Ch.18......Page 591
Ch.19......Page 592
Ch.20......Page 594
Ch.22......Page 597
Ch.25......Page 598
Ch.27......Page 599
B Acquiring Software......Page 602
B.2 Netlib......Page 603
B.4 NAG Library and NAGWare F95 Compiler......Page 604
C Program Libraries......Page 606
C.1 Basic Linear Algebra Subprograms......Page 607
C.4 LAPACK......Page 608
C.4.1 Structure of LAPACK......Page 609
D The Matrix Computation Toolbox......Page 612
Bibliography......Page 616
Name Index......Page 686
Subject Index......Page 696
Back Cover......Page 710