Nicholas J. Higham9780898713558, 0898713552
Table of contents :
Contents……Page 8
List of Figures……Page 18
List of Tables……Page 20
Preface……Page 22
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 33
1.3 Sources of Errors……Page 34
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.11 Accumulation of Rounding Errors……Page 45
1.12.2 An Innocuous Calculation?……Page 46
1.12.3 An Infinite Sum……Page 47
1.13 Increasing the Precision……Page 48
1.14 Cancellation of Rounding Errors……Page 50
1.14.1 Computing……Page 51
1.14.2 QR Factorization……Page 53
1.15 Rounding Errors Can Be Beneficial……Page 55
1.16 Stability of an Algorithm Depends on the Problem……Page 56
1.17 Rounding Errors Are Not Random……Page 58
1.18 Designing St able Algorithms……Page 59
1.19 Misconceptions……Page 60
1.21 Notes and References……Page 61
Problems……Page 65
2 Floating Point Arithmetic……Page 68
2.1 Floating Point Number System……Page 69
2.2 Model of Arithmetic……Page 73
2.3 IEEE Arithmetic……Page 74
2.4 Aberrant Arithmetics……Page 77
2.5 Choice of Base and Distribution of Numbers……Page 80
2.6 Statistical Distribution of Rounding Errors……Page 81
2.7 Alternative Number Systems……Page 82
2.8 Accuracy Tests……Page 83
2.9 Notes and References……Page 85
Problems……Page 91
3 Basics……Page 96
3.1 Inner and Outer Products……Page 97
3.2 The Purpose of Rounding Error Analysis……Page 100
3.3 Running Error Analysis……Page 101
3.4 Notation for Error Analysis……Page 102
3.5 Matrix Multiplication……Page 105
3.6 Complex Arithmetic……Page 107
3.7 Miscellany……Page 109
3.8 Error Analysis Demystified……Page 111
3.9 Other Approaches……Page 112
Problems……Page 113
4 Summation……Page 116
4.1 Summation Methods……Page 117
4.2 Error Analysis……Page 118
4.3 Compensated Summation……Page 121
4.4 Other Summation Methods……Page 126
4.6 Choice of Method……Page 127
Problems……Page 129
5 Polynomials……Page 132
5.1 Horner`s Method……Page 133
5.2 Evaluating Derivatives……Page 135
5.3 The Newton Form and Polynomial Interpolation……Page 138
5.4 Notes and References……Page 142
Problems……Page 143
6 Norms……Page 146
6.1 Vector Norms……Page 147
6.2 Matrix Norms……Page 149
6.3 The Matrix p-Norm……Page 153
6.4 Notes and References……Page 155
Problems……Page 156
7 Perturbation Theory for Linear Systems……Page 160
7.1 Normwise Analysis……Page 161
7.2 Componentwise Analysis……Page 163
7.3 Scaling to Minimize the Condition Number……Page 166
7.5 Extensions……Page 169
7.6 Numerical Stability……Page 170
7.7 Practical Error Bounds……Page 171
7.8 Perturbation Theory by Calculus……Page 173
7.9 Notes and References……Page 174
Problems……Page 176
8 Triangular Systems……Page 180
8.1 Backward Error Analysis……Page 181
8.2 Forward Error Analysis……Page 184
8.3 Bounds for the Inverse……Page 188
8.4 A Parallel Fan-In Algorithm……Page 191
8.5 Notes and References……Page 193
Problems……Page 195
9 LU Factorization and Linear Equations……Page 198
9.1 Gaussian Elimination……Page 199
9.2 Error Analysis……Page 203
9.3 The Growth Factor……Page 206
9.4 Special Matrices……Page 210
9.5 Tridiagonal Matrices……Page 212
9.6 Historical Perspective……Page 215
9.7 Scaling……Page 220
9.8 A Posteriori Stability Tests……Page 221
9.9 Sensitivity of the LU Factorization……Page 223
9.10 Notes and References……Page 224
9.10.1 LAPACK……Page 227
Problems……Page 228
10 Cholesky Factorization……Page 232
10.1 Symmetric Positive Definite Matrices……Page 233
10.1.1 Error Analysis……Page 234
10.2 Sensitivity of the Cholesky Factorization……Page 238
10.3 Positive Semidefinite Matrices……Page 239
10.3.1 Perturbation Theory……Page 240
10.3.2 Error Analysis……Page 243
10.4 Symmetric Indefinite Matrices and Diagonal Pivoting Method……Page 247
10.4.1 Complete Pivoting……Page 248
10.4.2 Partial Pivoting……Page 250
10.5 Nonsymmetric Positive Definite Matrices……Page 252
10.6 Notes and References……Page 253
10.6.1 LAPACK……Page 255
Problems……Page 256
11 Iterative Refinement……Page 260
11.1 Convergence of Iterative Refinement……Page 261
11.2 Iterative Refinement Implies Stability……Page 264
11.3 Notes and References……Page 270
Problems……Page 272
12 Block LU Factorization……Page 274
12.1 Block Versus Partitioned LU Factorization……Page 275
12.2 Error Analysis of Partitioned LU Factorization……Page 277
12.3 Error Analysis of Block LU Factorization……Page 279
12.3.1 Block Diagonal Dominance……Page 280
12.3.2 Symmetric Positive Definite Matrices……Page 284
12.4 Notes and References……Page 286
Problems……Page 287
13 Matrix Inversion……Page 290
13.1 Use and Abuse of the Matrix Inverse……Page 291
13.2.1 Unblocked Methods……Page 294
13.2.2 Block Methods……Page 296
13.3.1 Method A……Page 299
13.3.2 Method B……Page 300
13.3.3 Method C……Page 301
13.3.4 Method D……Page 302
13.4 Gauss-Jordan Elimination……Page 304
13.5 The Determinant……Page 310
13.5.1 Hyman’s Method……Page 311
13.6 Notes and References……Page 312
Problems……Page 314
14 Condition Number Estimation……Page 318
14.1 How to Estimate Componentwise Condition Numbers……Page 319
14.2 The p-Norm Power Method……Page 320
14.3 LAPACK l-Norm Estimator……Page 323
14.4 Other Condition Estimators……Page 326
14.5 Condition Numbers of Tridiagonal Matrices……Page 330
14.6 Notes and References……Page 333
Problems……Page 335
15 The Sylvester Equation……Page 338
15.1 Solving the Sylvester Equation……Page 340
15.2 Backward Error……Page 342
15.2.1 The Lyapunov Equation……Page 345
15.3 Perturbation Result……Page 347
15.4 Practical Error Bounds……Page 349
15.5 Extensions……Page 350
15.6 Notes and References……Page 351
Problems……Page 353
16 Stationary Iterative Methods……Page 354
16.1 Survey of Error Analysis……Page 356
16.2 Forward Error Analysis……Page 358
16.2.1 Jacobi’s Method……Page 361
16.3 Backward Error Analysis……Page 363
16.4.1 Theoretical Background……Page 365
16.4.2 Forward Error Analysis……Page 367
16.5 Stopping an Iterative Method……Page 370
Problems……Page 372
17 Matrix Powers……Page 374
17.1 Matrix Powers in Exact Arithmetic……Page 375
17.2 Bounds for Finite Precision Arithmetic……Page 382
17.4 Notes and References……Page 387
Problems……Page 388
18 QR Factorization……Page 390
18.1 Householder Transformations……Page 391
18.2 QR Factorization……Page 392
18.3 Error Analysis of Householder Computations……Page 393
18.4 Aggregated Householder Transformations……Page 399
18.5 Givens Rotations……Page 400
18.6 Iterative Refinement……Page 404
18.7 Gram-Schmidt Orthogonalization……Page 405
18.8 Sensitivity of the QR Factorization……Page 410
18.9 Notes and References……Page 412
18.9.1 LAPACK……Page 415
Problems……Page 416
19 The Least Squares Problem……Page 420
19.1 Perturbation Theory……Page 421
19.2 Solution by QR Factorization……Page 424
19.3 Solution by the Modified Gram-Schmidt Method……Page 425
19.4 The Normal Equations……Page 426
19.5 Iterative Refinement……Page 428
19.6 The Seminormal Equations……Page 432
19.7 Backward Error……Page 433
19.8 Proof of Wedin’s Theorem……Page 436
19.9 Notes and References……Page 438
Problems……Page 441
20 Underdetermined Systems……Page 444
20.1 Solution Methods……Page 445
20.2 Perturbation Theory……Page 446
20.3 Error Analysis……Page 448
20.4 Notes and References……Page 451
Problems……Page 452
21 Vandermonde Systems……Page 454
21.1 Matrix Inversion……Page 455
21.2 Primal and Dual Systems……Page 457
21.3 Stability……Page 463
21.3.1 Forward Error……Page 464
21.3.2 Residual……Page 466
21.3.3 Dealing with Instability……Page 467
21.4 Notes and References……Page 469
Problems……Page 470
22 Fast Matrix Multiplication……Page 474
22.1 Methods……Page 475
22.2 Error Analysis……Page 479
22.2.1 Winograd’s Method……Page 480
22.2.2 Strassen’s Method……Page 481
22.2.3 Bilinear Noncommutative Algorithms……Page 485
22.2.4 The 3M Method……Page 487
22.3 Notes and References……Page 488
Problems……Page 490
23 The Fast Fourier Transform and Applications……Page 494
23.1 The Fast Fourier Transform……Page 495
23.2 Circulant Linear Systems……Page 497
23.3 Notes and References……Page 499
Problems……Page 500
24 Automatic Error Analysis……Page 502
24.1 Exploiting Direct Search Optimization……Page 503
24.2 Direct Search Methods……Page 506
24.3 Examples of Direct Search……Page 508
24.3.1 Condition Estimation……Page 509
24.3.2 Fast Matrix Inversion……Page 510
24.3.3 Solving a Cubic……Page 512
24.4 Interval Analysis……Page 514
24.5 Other Work……Page 516
24.6 Notes and References……Page 518
Problems……Page 519
25 Software Issues in Floating Point Arithmetic……Page 520
25.1 Exploiting IEEE Arithmetic……Page 521
25.2 Subtleties of Floating Point Arithmetic……Page 524
25.3 Cray Peculiarities……Page 525
25.5 Determining Properties of Floating Point Arithmetic……Page 526
25.6 Testing a Floating Point Arithmetic……Page 527
25.7.1 Arithmetic Parameters……Page 528
25.7.2 22 Problems in LAPACK……Page 529
25.7.4 Models of Floating Point Arithmetic……Page 530
25.8 Avoiding Underflow and Overflow……Page 531
25.9 Multiple Precision Arithmetic……Page 533
25.10 Patriot Missile Software Problem……Page 535
25.11 Notes and References……Page 536
Problems……Page 537
26 A Gallery of Test Matrices……Page 542
26.1 The Hilbert and Cauchy Matrices……Page 543
26.2 Random Matrices……Page 546
26.3 “Randsvd” Matrices……Page 548
26.4 The Pascal Matrix……Page 549
26.5 Tridiagonal Toeplitz Matrices……Page 553
26.6 Companion Matrices……Page 554
26.7 Notes and References……Page 555
Problems……Page 556
A Solutions to Problems……Page 558
B Singular Value Decomposition, M-Matrices……Page 608
B.2 M-Matrices……Page 609
C Acquiring Software……Page 610
C.2 Netlib……Page 611
C.4 NAG Library and FTN90 Compiler……Page 612
D Program Libraries……Page 614
D.1 Basic Linear Algebra Subprograms……Page 615
D.4 LAPACK……Page 616
D.4.1 Structure of LAPACK……Page 617
E The Test Matrix Toolbox……Page 620
Bibliography……Page 624
Name Index……Page 694
Subject Index……Page 704
Reviews
There are no reviews yet.