Numerical Methods in Scientific Computing: Volume 1

Cover Page......Page 1
Title Page......Page 4
ISBN 9780898716443......Page 5
1 Principles of Numerical Calculations......Page 8
2 How to Obtain and Estimate Accuracy......Page 9
3 Series, Operators, and Continued Fractions......Page 10
4 Interpolation and Approximation......Page 11
5 Numerical Integration......Page 12
6 Solving Scalar Nonlinear Equations......Page 13
Online Appendix B: A MATLAB Multiple Precision Package......Page 14
Online Appendix C: Guide to Literature......Page 15
List of Figures......Page 16
List of Tables......Page 20
List of Conventions......Page 22
Preface......Page 24
1.1 Common Ideas and Concepts......Page 30
1.1.1 Fixed-Point Iteration......Page 31
1.1.2 Newton’s Method......Page 34
1.1.3 Linearization and Extrapolation......Page 38
1.1.4 Finite Difference Approximations......Page 40
Problems and Computer Exercises......Page 44
1.2.1 Solving a Quadratic Equation......Page 45
1.2.2 Recurrence Relations......Page 46
1.2.3 Divide and Conquer Strategy......Page 49
1.2.4 Power Series Expansions......Page 51
Problems and Computer Exercises......Page 52
1.3.1 Matrix Multiplication......Page 55
1.3.2 Solving Linear Systems by LU Factorization......Page 57
1.3.3 Sparse Matrices and Iterative Methods......Page 67
1.3.4 Software for Matrix Computations......Page 70
Problems and Computer Exercises......Page 72
1.4 The Linear Least Squares Problem......Page 73
1.4.1 Basic Concepts in Probability and Statistics......Page 74
1.4.2 Characterization of Least Squares Solutions......Page 75
1.4.3 The Singular Value Decomposition......Page 79
1.4.4 The Numerical Rank of a Matrix......Page 81
Problems and Computer Exercises......Page 83
1.5.1 Euler’s Method......Page 84
1.5.2 An Introductory Example......Page 85
1.5.3 Second Order Accurate Methods......Page 88
1.5.4 Adaptive Choice of Step Size......Page 90
Problems and Computer Exercises......Page 92
1.6.1 Origin of Monte Carlo Methods......Page 93
1.6.2 Generating and Testing Pseudorandom Numbers......Page 95
1.6.3 Random Deviates for Other Distributions......Page 102
1.6.4 Reduction of Variance......Page 106
Review Questions\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 110
Problems and Computer Exercises......Page 111
Notes and References......Page 112
2.1.1 Sources of Error......Page 116
2.1.2 Absolute and Relative Errors......Page 119
2.1.3 Rounding and Chopping......Page 120
2.2.1 The Position System......Page 122
2.2.2 Fixed- and Floating-Point Representation......Page 124
2.2.3 IEEE Floating-Point Standard......Page 128
2.2.4 Elementary Functions......Page 131
2.2.5 Multiple Precision Arithmetic......Page 133
Problems and Computer Exercises......Page 134
2.3.1 Floating-Point Arithmetic......Page 136
2.3.2 Basic Rounding Error Results......Page 142
2.3.3 Statistical Models for Rounding Errors......Page 145
2.3.4 Avoiding Overflow and Cancellation......Page 147
Problems and Computer Exercises......Page 151
2.4.1 Numerical Problems, Methods, and Algorithms......Page 155
2.4.2 Propagation of Errors and Condition Numbers......Page 156
2.4.3 Perturbation Analysis for Linear Systems......Page 163
2.4.4 Error Analysis and Stability of Algorithms......Page 166
Problems and Computer Exercises......Page 171
2.5.1 Running Error Analysis......Page 174
2.5.2 Experimental Perturbations......Page 175
2.5.3 Interval Arithmetic......Page 176
2.5.4 Range of Functions......Page 179
2.5.5 Interval Matrix Computations......Page 182
Review Questions\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 183
Notes and References......Page 184
3.1.1 Introduction......Page 186
3.1.2 Taylor’s Formula and Power Series......Page 191
3.1.3 Analytic Continuation......Page 200
3.1.4 Manipulating Power Series......Page 202
3.1.5 Formal Power Series......Page 210
Review Questions\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 213
Problems and Computer Exercises......Page 214
3.2.1 Laurent and Fourier Series......Page 220
3.2.2 The Cauchy–FFT Method......Page 222
3.2.3 Chebyshev Expansions......Page 227
3.2.4 Perturbation Expansions......Page 232
3.2.5 Ill-Conditioned Series......Page 235
3.2.6 Divergent or Semiconvergent Series......Page 241
Problems and Computer Exercises......Page 244
3.3.1 Properties of Difference Operators......Page 249
3.3.2 The Calculus of Operators......Page 254
3.3.3 The Peano Theorem......Page 266
3.3.4 Approximation Formulas by Operator Methods......Page 271
3.3.5 Single Linear Difference Equations......Page 280
Problems and Computer Exercises......Page 290
3.4.1 Introduction......Page 300
3.4.2 Comparison Series and Aitken Acceleration......Page 301
3.4.3 Euler’s Transformation......Page 307
3.4.4 Complete Monotonicity and Related Concepts......Page 313
3.4.5 Euler–Maclaurin’s Formula......Page 321
3.4.6 Repeated Richardson Extrapolation......Page 331
Problems and Computer Exercises......Page 338
3.5.1 Algebraic Continued Fractions......Page 350
3.5.2 Analytic Continued Fractions......Page 355
3.5.3 The Padé Table......Page 358
3.5.4 The Epsilon Algorithm......Page 365
3.5.5 The qd Algorithm......Page 368
Problems and Computer Exercises......Page 374
Notes and References......Page 377
4.1.1 Introduction......Page 380
4.1.2 Bases for Polynomial Interpolation......Page 381
4.1.3 Conditioning of Polynomial Interpolation......Page 384
Problems and Computer Exercises......Page 386
4.2.1 Newton’s Interpolation Formula......Page 387
4.2.2 Inverse Interpolation......Page 395
4.2.3 Barycentric Lagrange Interpolation......Page 396
4.2.4 Iterative Linear Interpolation......Page 400
4.2.5 Fast Algorithms for Vandermonde Systems......Page 402
4.2.6 The Runge Phenomenon......Page 406
Problems and Computer Exercises......Page 409
4.3.1 Hermite Interpolation......Page 410
4.3.2 Complex Analysis in Polynomial Interpolation......Page 414
4.3.3 Rational Interpolation......Page 418
4.3.4 Multidimensional Interpolation......Page 424
4.3.5 Analysis of a Generalized Runge Phenomenon......Page 427
Problems and Computer Exercises......Page 436
4.4 Piecewise Polynomial Interpolation......Page 439
4.4.1 Bernštein Polynomials and Bézier Curves......Page 440
4.4.2 Spline Functions......Page 446
4.4.3 The B-Spline Basis......Page 455
4.4.4 Least Squares Splines Approximation......Page 463
Review Questions\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 465
Problems and Computer Exercises......Page 466
4.5 Approximation and Function Spaces......Page 468
4.5.1 Distance and Norm......Page 469
4.5.2 Operator Norms and the Distance Formula......Page 473
4.5.3 Inner Product Spaces and Orthogonal Systems......Page 479
4.5.4 Solution of the Approximation Problem......Page 483
4.5.5 Mathematical Properties of Orthogonal Polynomials......Page 486
4.5.6 Expansions in Orthogonal Polynomials......Page 495
4.5.7 Approximation in the Maximum Norm......Page 500
Review Questions\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 507
Problems and Computer Exercises......Page 508
4.6 Fourier Methods......Page 511
4.6.1 Basic Formulas and Theorems......Page 512
4.6.2 Discrete Fourier Analysis......Page 516
4.6.3 Periodic Continuation of a Function......Page 520
4.6.4 Convergence Acceleration of Fourier Series......Page 521
4.6.5 The Fourier Integral Theorem......Page 523
4.6.6 Sampled Data and Aliasing......Page 526
Problems and Computer Exercises......Page 529
4.7.1 The FFT Algorithm......Page 532
4.7.2 Discrete Convolution by FFT......Page 538
4.7.3 FFTs of Real Data......Page 539
4.7.4 Fast Trigonometric Transforms......Page 541
4.7.5 The General Case FFT......Page 544
Review Questions\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 545
Problems and Computer Exercises......Page 546
Notes and References......Page 547
5.1.1 Introduction......Page 550
5.1.2 Treating Singularities......Page 554
5.1.3 Some Classical Formulas......Page 556
5.1.4 Superconvergence of the Trapezoidal Rule......Page 560
5.1.5 Higher-Order Newton–Cotes’ Formulas......Page 562
5.1.6 Fejér and Clenshaw–Curtis Rules......Page 567
Problems and Computer Exercises......Page 571
5.2.1 The Euler–Maclaurin Formula......Page 575
5.2.2 Romberg’s Method......Page 577
5.2.3 Oscillating Integrands......Page 583
5.2.4 Adaptive Quadrature......Page 589
Problems and Computer Exercises......Page 593
5.3.1 Method of Undetermined Coefficients......Page 594
5.3.2 Gauss–Christoffel Quadrature Rules......Page 597
5.3.3 Gauss Quadrature with Preassigned Nodes......Page 602
5.3.4 Matrices, Moments, and Gauss Quadrature......Page 605
5.3.5 Jacobi Matrices and Gauss Quadrature......Page 609
Problems and Computer Exercises......Page 614
5.4 Multidimensional Integration......Page 616
5.4.1 Analytic Techniques......Page 617
5.4.2 Repeated One-Dimensional Integration......Page 618
5.4.3 Product Rules......Page 619
5.4.4 Irregular Triangular Grids......Page 623
5.4.5 Monte Carlo Methods......Page 628
5.4.6 Quasi–Monte Carlo and Lattice Methods......Page 630
Review Questions\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 633
Problems and Computer Exercises......Page 634
Notes and References......Page 635
6.1.1 Introduction......Page 638
6.1.2 The Bisection Method......Page 639
6.1.3 Limiting Accuracy and Termination Criteria......Page 643
6.1.4 Fixed-Point Iteration......Page 647
6.1.5 Convergence Order and Efficiency......Page 650
Problems and Computer Exercises......Page 653
6.2.1 Method of False Position......Page 655
6.2.2 The Secant Method......Page 657
6.2.3 Higher-Order Interpolation Methods......Page 660
6.2.4 A Robust Hybrid Method......Page 663
Review Questions\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 664
Problems and Computer Exercises......Page 665
6.3.1 Newton’s Method......Page 666
6.3.2 Newton’s Method for Complex Roots......Page 673
6.3.3 An Interval Newton Method......Page 675
6.3.4 Higher-Order Methods......Page 676
Review Questions\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 681
Problems and Computer Exercises......Page 682
6.4.1 Introduction......Page 685
6.4.2 Unimodal Functions and Golden Section Search......Page 686
6.4.3 Minimization by Interpolation......Page 689
Problems and Computer Exercises......Page 690
6.5.1 Some Elementary Results......Page 691
6.5.2 Ill-Conditioned Algebraic Equations......Page 694
6.5.3 Three Classical Methods......Page 697
6.5.4 Deflation and Simultaneous Determination of Roots......Page 700
6.5.5 A Modified Newton Method......Page 704
6.5.6 Sturm Sequences......Page 706
6.5.7 Finding Greatest Common Divisors......Page 709
Review Questions\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 711
Problems and Computer Exercises......Page 712
Notes and References......Page 714
Bibliography......Page 716
Index......Page 736
A.1.1 Linear Vector Spaces......Page 748
A.1.2 Matrix and Vector Algebra......Page 750
A.1.3 Rank and Linear Systems......Page 752
A.1.4 Special Matrices......Page 753
A.2 Submatrices and Block Matrices......Page 755
A.2.1 Block Gaussian Elimination......Page 757
A.3 Permutations and Determinants......Page 759
A.4.1 The Characteristic Equation......Page 763
A.4.2 The Schur and Jordan Normal Forms......Page 764
A.4.3 Norms of Vectors and Matrices......Page 765
Review Questions......Page 768
Problems......Page 769
B.1.1 Number Representation......Page 771
B.1.3 Basic Arithmetic Operations......Page 773
B.2.1 Elementary Functions......Page 774
B.2.2 Mulprec Vector Algorithms......Page 775
Computer Exercises......Page 776
Bibliography......Page 778
C.2 Textbooks in Numerical Analysis......Page 779
C.3 Handbooks and Collections......Page 783
C.4 Encyclopedias, Tables, and Formulas......Page 784
C.5 Selected Journals......Page 786
C.6 Algorithms and Software......Page 787
C.7 Public Domain Software......Page 788
Back Page......Page 793