Scientific Computing: An Introductory Survey, Revised 2nd Edition......Page 6
Contents......Page 10
Preface to the Classics Edition......Page 14
Preface......Page 16
Notation......Page 20
1.1 Introduction......Page 22
1.1.1 Computational Problems......Page 23
1.1.2 General Strategy......Page 24
1.2.1 Sources of Approximation......Page 25
1.2.2 Absolute Error and Relative Error......Page 26
1.2.3 Data Error and Computational Error......Page 27
1.2.4 Truncation Error and Rounding Error......Page 29
1.2.5 Forward Error and Backward Error......Page 31
1.2.6 Sensitivity and Conditioning......Page 34
1.3.1 Floating-Point Numbers......Page 37
1.3.3 Properties of Floating-Point Systems......Page 39
1.3.4 Rounding......Page 40
1.3.5 Machine Precision......Page 41
1.3.7 Exceptional Values......Page 42
1.3.8 Floating-Point Arithmetic......Page 43
1.3.9 Cancellation......Page 45
1.3.10 Other Arithmetic Systems......Page 50
1.3.11 Complex Arithmetic......Page 52
1.4.1 Mathematical Software Libraries......Page 54
1.4.2 Scientific Computing Environments......Page 55
1.4.4 Practical Advice on Software......Page 56
1.5 Historical Notes and Further Reading......Page 58
Review Questions......Page 60
Exercises......Page 62
2.1 Linear Systems......Page 69
2.2 Existence and Uniqueness......Page 71
2.3 Sensitivity and Conditioning......Page 72
2.3.1 Vector Norms......Page 73
2.3.2 Matrix Norms......Page 74
2.3.3 Matrix Condition Number......Page 76
2.3.4 Error Bounds......Page 79
2.3.5 Residual......Page 82
2.4.1 Problem Transformations......Page 83
2.4.2 Triangular Linear Systems......Page 84
2.4.3 Elementary Elimination Matrices......Page 86
2.4.4 Gaussian Elimination and LU Factorization......Page 88
2.4.5 Pivoting......Page 90
2.4.6 Implementation of Gaussian Elimination......Page 97
2.4.8 Gauss-Jordan Elimination......Page 99
2.4.9 Solving Modified Problems......Page 101
2.4.10 Improving Accuracy......Page 103
2.5 Special Types of Linear Systems......Page 104
2.5.1 Symmetric Positive Definite Systems......Page 105
2.5.2 Symmetric Indefinite Systems......Page 107
2.5.3 Banded Systems......Page 108
2.7 Software for Linear Systems......Page 109
2.7.1 LINPACK and LAPACK......Page 110
2.7.2 Basic Linear Algebra Subprograms......Page 111
2.8 Historical Notes and Further Reading......Page 112
Review Questions......Page 113
Exercises......Page 117
3.1 Linear Least Squares Problems......Page 125
3.2 Existence and Uniqueness......Page 129
3.2.1 Normal Equations......Page 130
3.2.2 Orthogonality and Orthogonal Projectors......Page 131
3.3 Sensitivity and Conditioning......Page 133
3.4.1 Normal Equations......Page 137
3.4.2 Augmented System......Page 138
3.4.3 Orthogonal Transformations......Page 139
3.4.5 QR Factorization......Page 140
3.5.1 Householder Transformations......Page 141
3.5.2 Givens Rotations......Page 147
3.5.3 Gram-Schmidt Orthogonalization......Page 151
3.5.4 Rank Deficiency......Page 155
3.6 Singular Value Decomposition......Page 157
3.6.1 Other Applications of SVD......Page 159
3.7 Comparison of Methods......Page 163
3.8 Software for Linear Least Squares......Page 164
Review Questions......Page 166
Exercises......Page 169
Computer Problems......Page 173
4.1 Eigenvalues and Eigenvectors......Page 177
4.2.1 Characteristic Polynomial......Page 180
4.2.2 Multiplicity and Diagonalizability......Page 182
4.2.4 Properties of Matrices and Eigenvalue Problems......Page 183
4.2.5 Localizing Eigenvalues......Page 185
4.3 Sensitivity and Conditioning......Page 186
4.4 Problem Transformations......Page 189
4.4.1 Diagonal, Triangular, and Block Triangular Forms......Page 190
4.5.1 Power Iteration......Page 193
4.5.2 Inverse Iteration......Page 196
4.5.3 Rayleigh Quotient Iteration......Page 198
4.5.4 Deflation......Page 199
4.5.5 Simultaneous Iteration......Page 200
4.5.6 QR Iteration......Page 201
4.5.7 Krylov Subspace Methods......Page 208
4.5.8 Jacobi Method......Page 212
4.5.9 Bisection or Spectrum-Slicing......Page 215
4.5.10 Divide-and-Conquer......Page 216
4.5.11 Relatively Robust Representation......Page 218
4.5.12 Comparison of Methods......Page 220
4.6 Generalized Eigenvalue Problems......Page 221
4.8 Software for Eigenvalue Problems......Page 222
4.9 Historical Notes and Further Reading......Page 224
Review Questions......Page 225
Exercises......Page 228
Computer Problems......Page 231
5.1 Nonlinear Equations......Page 236
5.2 Existence and Uniqueness......Page 237
5.3 Sensitivity and Conditioning......Page 241
5.4 Convergence Rates and Stopping Criteria......Page 242
5.5.1 Interval Bisection......Page 244
5.5.2 Fixed-Point Iteration......Page 246
5.5.3 Newton's Method......Page 249
5.5.4 Secant Method......Page 251
5.5.5 Inverse Interpolation......Page 253
5.5.6 Linear Fractional Interpolation......Page 255
5.5.8 Zeros of Polynomials......Page 256
5.6.1 Fixed-Point Iteration......Page 257
5.6.2 Newton's Method......Page 258
5.6.3 Secant Updating Methods......Page 260
5.6.4 Robust Newton-Like Methods......Page 262
5.7 Software for Nonlinear Equations......Page 263
5.8 Historical Notes and Further Reading......Page 264
Review Questions......Page 266
Exercises......Page 268
Computer Problems......Page 270
6.1 Optimization Problems......Page 276
6.2 Existence and Uniqueness......Page 279
6.2.1 Convexity......Page 280
6.2.2 Unconstrained Optimality Conditions......Page 281
6.2.3 Constrained Optimality Conditions......Page 284
6.3 Sensitivity and Conditioning......Page 289
6.4.1 Golden Section Search......Page 290
6.4.2 Successive Parabolic Interpolation......Page 293
6.4.3 Newton's Method......Page 294
6.4.4 Safeguarded Methods......Page 295
6.5.2 Steepest Descent......Page 296
6.5.3 Newton's Method......Page 298
6.5.5 Secant Updating Methods......Page 301
6.5.6 Conjugate Gradient Method......Page 303
6.5.7 Truncated or Inexact Newton Methods......Page 304
6.6 Nonlinear Least Squares......Page 305
6.6.1 Gauss-Newton Method......Page 306
6.6.2 Levenberg-Marquardt Method......Page 307
6.7.1 Sequential Quadratic Programming......Page 308
6.7.2 Penalty and Barrier Methods......Page 311
6.7.3 Linear Programming......Page 313
6.8 Software for Optimization......Page 315
6.9 Historical Notes and Further Reading......Page 316
Review Questions......Page 319
Exercises......Page 321
Computer Problems......Page 323
7.1 Interpolation......Page 329
7.2 Existence, Uniqueness, and Conditioning......Page 332
7.3.1 Monomial Basis......Page 333
7.3.2 Lagrange Interpolation......Page 336
7.3.3 Newton Interpolation......Page 338
7.3.4 Orthogonal Polynomials......Page 341
7.3.5 Interpolating Continuous Functions......Page 344
7.4 Piecewise Polynomial Interpolation......Page 346
7.4.2 Cubic Spline Interpolation......Page 347
7.4.3 B-splines......Page 349
7.5 Software for Interpolation......Page 352
7.6 Historical Notes and Further Reading......Page 353
Review Questions......Page 354
Exercises......Page 356
Computer Problems......Page 357
8.1 Integration......Page 359
8.2 Existence, Uniqueness, and Conditioning......Page 361
8.3 Numerical Quadrature......Page 362
8.3.1 Newton-Cotes Quadrature......Page 366
8.3.2 Clenshaw-Curtis Quadrature......Page 370
8.3.3 Gaussian Quadrature......Page 371
8.3.4 Progressive Gaussian Quadrature......Page 374
8.3.5 Composite Quadrature......Page 375
8.3.6 Adaptive Quadrature......Page 376
8.4.2 Improper Integrals......Page 379
8.4.4 Multiple Integrals......Page 381
8.5 Integral Equations......Page 382
8.6.1 Finite Difference Approximations......Page 385
8.6.2 Automatic Differentiation......Page 388
8.7 Richardson Extrapolation......Page 389
8.8 Software for Integration and Differentiation......Page 391
Review Questions......Page 393
Exercises......Page 396
Computer Problems......Page 398
9.1 Ordinary Differential Equations......Page 402
9.2 Existence, Uniqueness, and Conditioning......Page 407
9.3 Numerical Solution of ODEs......Page 410
9.3.1 Euler's Method......Page 411
9.3.2 Accuracy and Stability......Page 414
9.3.3 Implicit Methods......Page 418
9.3.4 Stiffness......Page 421
9.3.5 Taylor Series Methods......Page 424
9.3.6 Runge-Kutta Methods......Page 425
9.3.8 Multistep Methods......Page 427
9.3.9 Multivalue Methods......Page 430
9.4 Software for ODE Initial Value Problems......Page 433
9.5 Historical Notes and Further Reading......Page 434
Review Questions......Page 435
Exercises......Page 437
Computer Problems......Page 438
10.1 Boundary Value Problems......Page 442
10.2 Existence, Uniqueness, and Conditioning......Page 444
10.3 Shooting Method......Page 447
10.4 Finite Difference Method......Page 450
10.5 Collocation Method......Page 452
10.6 Galerkin Method......Page 456
10.7 Eigenvalue Problems......Page 460
10.8 Software for ODE Boundary Value Problems......Page 461
Review Questions......Page 462
Exercises......Page 463
Computer Problems......Page 464
11.1 Partial Differential Equations......Page 467
11.2.1 Semidiscrete Methods......Page 473
11.2.2 Fully Discrete Methods......Page 476
11.3.1 Finite Difference Methods......Page 481
11.3.2 Finite Element Methods......Page 483
11.4.1 Sparse Factorization Methods......Page 484
11.5 Iterative Methods for Linear Systems......Page 487
11.5.1 Stationary Iterative Methods......Page 488
11.5.2 Jacobi Method......Page 489
11.5.3 Gauss-Seidel Method......Page 490
11.5.4 Successive Over-Relaxation......Page 491
11.5.5 Conjugate Gradient Method......Page 492
11.5.6 Rate of Convergence......Page 497
11.5.7 Multigrid Methods......Page 498
11.6 Comparison of Methods......Page 500
11.7 Software for Partial Differential Equations......Page 503
11.7.2 Software for Boundary Value Problems......Page 504
11.8 Historical Notes and Further Reading......Page 505
Review Questions......Page 507
Exercises......Page 510
Computer Problems......Page 511
12.1 Trigonometric Interpolation......Page 515
12.1.1 Discrete Fourier Transform......Page 516
12.2 FFT Algorithm......Page 518
12.2.1 Limitations of FFT......Page 521
12.3 Applications of DFT......Page 522
12.3.1 Fast Polynomial Multiplication......Page 523
12.4 Wavelets......Page 524
12.5 Software for FFT......Page 525
Review Questions......Page 526
Exercises......Page 527
Computer Problems......Page 528
13.1 Stochastic Simulation......Page 531
13.2 Randomness and Random Numbers......Page 532
13.3.1 Congruential Generators......Page 533
13.3.3 Nonuniform Distributions......Page 534
13.4 Quasi-Random Sequences......Page 535
13.6 Historical Notes and Further Reading......Page 536
Exercises......Page 537
Computer Problems......Page 538
Bibliography......Page 543
Index......Page 574
