Heath 2/e, presents a broad overview of numerical methods for solving all the major problems in scientific computing, including linear and nonlinear equations, least squares, eigenvalues, optimization, interpolation, integration, ordinary and partial differential equations, fast Fourier transforms, and random number generators. The treatment is comprehensive yet concise, software-oriented yet compatible with a variety of software packages and programming languages. The book features more than 160 examples, 500 review questions, 240 exercises, and 200 computer problems. Changes for the second edition include: expanded motivational discussions and examples; formal statements of all major algorithms; expanded discussions of existence, uniqueness, and conditioning for each type of problem so that students can recognize "good" and "bad" problem formulations and understand the corresponding quality of results produced; and expanded coverage of several topics, particularly eigenvalues and constrained optimization. The book contains a wealth of material and can be used in a variety of one- or two-term courses in computer science, mathematics, or engineering. Its comprehensiveness and modern perspective, as well as the software pointers provided, also make it a highly useful reference for practicing professionals who need to solve computational problems.
Author(s): Michael T. Heath
Edition: 2nd
Publisher: The McGraw-Hill Companies, Inc.
Year: 1997
Language: English
Pages: 563
Tags: Математика;Вычислительная математика;
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
