Scientific Computing: An Introductory Survey, Second Edition

Contents......Page 6
1.1 - Introduction
......Page 20
1.2.1 - Sources of Approximation
......Page 21
1.2.2 - Data Error and Computational Error
......Page 22
1.2.3 - Truncation Error and Rounding Error
......Page 23
1.2.5 - Sensitivity and Conditioning
......Page 24
1.2.6 - Backward Error Analysis
......Page 25
1.3.1 - Floating-Point Numbers
......Page 27
1.3.3 - Properties of Floating-Point Systems
......Page 29
1.3.4 - Rounding
......Page 30
1.3.5 - Machine Precision
......Page 31
1.3.7 - Exceptional Values
......Page 32
1.3.8 - Floating-Point Arithmetic
......Page 33
1.3.9 - Cancellation
......Page 34
1.4 - Mathematical Software
......Page 39
1.4.1 - Mathematical Software Libraries
......Page 40
1.4.2 - Scientific Computing Environments
......Page 41
1.4.3 - Practical Advice on Software
......Page 42
1.5 - Historical Notes and Further Reading
......Page 44
Review Questions
......Page 45
Exercises
......Page 47
Computer Problems
......Page 50
2.1.1 - Singularity and Nonsingularity
......Page 56
2.2 - Solving Linear Systems
......Page 58
2.2.1 - Triangular Linear Systems
......Page 59
2.2.2 - Elementary Elimination Matrices
......Page 60
2.2.3 - Gaussian Elimination and LU Factorization
......Page 61
2.2.4 - Pivoting 
......Page 63
2.2.5 - Implementation of Gaussian Elimination
......Page 68
2.2.6 - Complexity of Solving Linear Systems
......Page 69
2.2.7 - Gauss-Jordan Elimination
......Page 70
2.2.8 - Solving Modified Problems
......Page 71
2.3.1 - Vector Norms
......Page 73
2.3.2 - Matrix Norms
......Page 75
2.3.3 - Condition Number of a Matrix
......Page 76
2.4.1 - Residual of a Solution
......Page 77
2.4.2 - Estimating Accuracy
......Page 79
2.4.3 - Improving Accuracy
......Page 81
2.5.1 - Symmetric Positive Definite Systems
......Page 82
2.5.2 - Symmetric Indefinite Systems
......Page 84
2.5.3 - Band Systems
......Page 85
2.7 - Software for Linear Systems
......Page 86
2.7.2 - Basic Linear Algebra Subprograms
......Page 88
2.8 - Historical Notes and Further Reading
......Page 89
Review Questions
......Page 90
Exercises
......Page 94
Computer Problems
......Page 97
3.1 - Data Fitting
......Page 102
3.2 - Linear Least Squares
......Page 103
3.3 - Normal Equations Method
......Page 104
3.3.1 - Orthogonality
......Page 105
3.3.2 - Normal Equations Method
......Page 106
3.4 - Orthogonalization Methods
......Page 108
3.4.3 - QR Factorization
......Page 109
3.4.4 - Householder Transformations
......Page 110
3.4.5 - Givens Rotations
......Page 114
3.4.6 - Gram-Schmidt Orthogonalization
......Page 117
3.4.7 - Rank Deficiency
......Page 120
3.4.8 - Column Pivoting
......Page 121
3.6 - Software for Linear Least Squares......Page 122
Review Questions
......Page 124
Exercises
......Page 127
Computer Problems
......Page 130
4.1 - Eigenvalues and Eigenvectors
......Page 134
4.1.2  - Characteristic Polynomials
......Page 135
4.1.3 - Properties of Eigenvalue Problems
......Page 136
4.1.4 - Similarity Transformations
......Page 137
4.1.5 - Conditioning of Eigenvalue Problems
......Page 139
4.2.1 - Characteristic Polynomials
......Page 140
4.2.2 - Jacobi Method for Symmetric Matrices
......Page 141
4.2.3 - QR Iteration
......Page 143
4.2.4 - Preliminary Reduction
......Page 144
4.3.1 - Power Method
......Page 145
4.3.2 - Normalization
......Page 146
4.3.4 - Shifts
......Page 147
4.3.6 - Inverse Iteration
......Page 148
4.3.7 - Rayleigh Quotient
......Page 149
4.3.8 - Rayleigh Quotient Iteration
......Page 150
4.3.9 - Lanczos Method for Symmetric Matrices
......Page 151
4.3.10 - Spectrum-Slicing Methods for Symmetric Matrices
......Page 152
4.4 - Generalized Eigenvalue Problems
......Page 154
4.5.1 - Singular Value Decomposition
......Page 155
4.5.2 - Applications of SVD
......Page 156
4.6 - Software for Eigenvalues and Singular Values
......Page 157
Review Questions
......Page 159
Exercises
......Page 162
Computer Problems
......Page 165
5.1 - Nonlinear Equations
......Page 170
5.1.1 - Solutions of Nonlinear Equations
......Page 171
5.1.2 - Convergence Rates of Iterative Methods
......Page 172
5.2.1 - Bisection Method
......Page 173
5.2.2 - Fixed-Point Iteration
......Page 174
5.2.3 - Newton's Method
......Page 177
5.2.4 - Secant Method
......Page 179
5.2.5 - Inverse Interpolation
......Page 181
5.2.6 - Linear Fractional Interpolation
......Page 182
5.2.7 - Safeguarded Methods
......Page 183
5.3 - Systems of Nonlinear Equations
......Page 184
5.3.1 - Fixed-Point Iteration
......Page 185
5.3.2 - Newton's Method
......Page 186
5.3.4 - Broyden's Method
......Page 188
5.4 - Software for Nonlinear Equations 
......Page 190
Review Questions
......Page 192
Exercises
......Page 195
Computer Problems
......Page 196
6.1 - Optimization Problems
......Page 202
6.1.1 - Local versus Global Optimization
......Page 203
6.1.2 - Relationship to Nonlinear Equations
......Page 204
6.2.1 - Golden Section Search
......Page 205
6.2.2 - Successive Parabolic Interpolation
......Page 207
6.2.3 - Newton's Method
......Page 208
6.3.2 - Steepest Descent Method
......Page 210
6.3.3 - Newton's Method
......Page 212
6.3.4 - Quasi-Newton Methods
......Page 214
6.3.5 - Secant Updating Methods
......Page 215
6.3.6 - Conjugate Gradient Method
......Page 216
6.4 - Nonlinear Least Squares
......Page 218
6.4.1 - Gauss-Newton Method
......Page 219
6.4.2 - Levenberg-Marquardt Method
......Page 220
6.5 - Constrained Optimization
......Page 221
6.5.1 - Linear Programming
......Page 224
6.6 - Software for Optimization
......Page 226
6.7 - Historical Notes and Further Reading
......Page 227
Review Questions
......Page 228
Exercises
......Page 231
Computer Problems
......Page 232
7.1.1 - Purposes for Interpolation
......Page 238
7.1.3 - Choice of Interpolating Function
......Page 239
7.1.4 - Basis Functions
......Page 240
7.2 - Polynomial Interpolation
......Page 241
7.2.2 - Lagrange Interpolation
......Page 243
7.2.3 - Newton Interpolation
......Page 244
7.2.4 - Orthogonal Polynomials
......Page 248
7.2.5 - Interpolating a Function
......Page 249
7.2.7 - Placement of Interpolation Points
......Page 250
7.3 - Piecewise Polynomial Interpolation
......Page 251
7.3.2 - Cubic Spline Interpolation
......Page 252
7.3.3 - Hermite Cubic versus Cubic Spline Interpolation
......Page 253
7.3.4 - B-splines
......Page 255
7.4 - Software for Interpolation
......Page 257
Review Questions
......Page 258
Exercises
......Page 260
Computer Problems
......Page 261
8.1 - Numerical Quadrature
......Page 264
8.2.1 - Newton-Cotes Quadrature Rules
......Page 265
8.2.2 - Method of Undetermined Coefficients
......Page 266
8.2.3 - Error Estimation
......Page 268
8.2.4 - Polynomial Degree
......Page 269
8.3.1 - Gaussian Quadrature Rules
......Page 270
8.3.2 - Change of Interval
......Page 272
8.3.3 - Gauss-Kronrod Quadrature Rules
......Page 273
8.4.1 - Composite Quadrature Rules
......Page 274
8.4.2 - Automatic and Adaptive Quadrature
......Page 275
8.5.3 - Double Integrals
......Page 276
8.5.4 - Multiple Integrals
......Page 277
8.6 - Integral Equations
......Page 278
8.7 - Numerical Differentiation
......Page 280
8.7.1 - Finite Difference Approximations......Page 281
8.8 - Richardson Extrapolation
......Page 282
8.9 - Software for Numerical Integration and Differentiation
......Page 285
Review Questions
......Page 286
Exercises
......Page 288
Computer Problems
......Page 290
9.1 - Ordinary Differential Equations
......Page 294
9.1.2 - Higher-Order ODE's
......Page 295
9.1.3 - Stable and Unstable ODE's
......Page 296
9.2.1 - Euler's Method
......Page 299
9.3.1 - Order of Accuracy
......Page 301
9.3.2 - Stability of a Numerical Method
......Page 303
9.3.3 - Stepsize Control
......Page 304
9.4 - Implicit Method
......Page 305
9.5 - Stiff Differential Equations
......Page 307
9.6.1 - Taylor Series Methods
......Page 309
9.6.2 - Runge-Kutta MEthods
......Page 310
9.6.4 - Multistep Methods
......Page 312
9.6.5 - Multivalue Methods
......Page 316
9.7 - Software for ODE Initial Value Problems
......Page 318
Review Questions
......Page 319
Exercises
......Page 322
Computer Problems
......Page 323
10.1 - Boundary Value Problems
......Page 328
10.2 - Shooting Method
......Page 329
10.4 - Finite Difference Method
......Page 331
10.5 - Finite Element Method
......Page 333
10.6 - Eigenvalue Problems
......Page 337
Review Questions
......Page 338
Computer Problems
......Page 340
11.1.1 - Classification of Partial Differential Equations
......Page 344
11.2 - Time-Dependent Problems
......Page 345
11.2.1 - Semidiscrete Methods Using Finite Differences
......Page 346
11.2.2 - Semidiscrete Methods Using Finite Elements
......Page 347
11.2.3 - Fully Discrete Methods
......Page 348
11.2.4 - Implicit Finite Difference Methods
......Page 351
11.2.5 - Hyperbolic versus Parabolic Problems
......Page 352
11.3.1 - Finite Difference Methods......Page 354
11.4 - Direct Methods for Sparse Linear Systems
......Page 356
11.4.1 - Sparse Factorization Methods
......Page 357
11.4.2 - Fast Direct Methods
......Page 359
11.5.1 - Stationary Iterative Methods
......Page 360
11.5.2 - Jacobi Method
......Page 361
11.5.3 - Gauss-Seidel Method
......Page 362
11.5.4 - Successive Over-Relaxation
......Page 363
11.5.5 - Conjugate Gradient Method
......Page 364
11.5.6 - Rate of Convergence
......Page 368
11.5.7 - Multigrid Methods
......Page 369
11.6 - Comparison of Methods
......Page 371
11.7 - Software for Partial Differential Equations
......Page 374
11.7.3 - Software for Sparse Systems
......Page 375
11.8 - Historical Notes and Further Reading
......Page 376
Review Questions
......Page 377
Exercises
......Page 380
Computer Problems
......Page 381
12.1 - Trigonometric Interpolation
......Page 386
12.1.1 - Continuous Fourier Transform
......Page 387
12.1.3 - Discrete Fourier Transform
......Page 388
12.2 - FFT Algorithm
......Page 391
12.2.1 - Limitations of the FFT
......Page 393
12.3 - Applications of DFT
......Page 394
12.3.1 - Fast Polynomial Multiplication
......Page 395
12.4 - Wavelets
......Page 396
12.6 - Historical Notes and Further Reading
......Page 397
Review Questions
......Page 398
Exercises
......Page 399
Computer Problems
......Page 400
13.1 - Stochastic Simulation
......Page 404
13.3 - Random Number Generators
......Page 405
13.3.1 - Congruential Generators
......Page 406
13.3.3 - Nonuniform Distributions
......Page 407
13.4 - Quasi-Random Sequences
......Page 408
Review Questions
......Page 409
Computer Problems
......Page 410
Bibliography
......Page 416
Index
......Page 433