Numerical Analysis for Applied Science

Myron B. Allen III, PhD, is Professor of Mathematics in the Department of Mathematics and Statistics at the University of Wyoming, Laramie, USA. His research focuses on the numerical analysis of fluid flows in porous media. The Late Eli L. Isaacson, PhD, was Professor Emeritus of Mathematics in the Department of Mathematics at the University of Wyoming, Laramie, USA. His work includes analytic and numerical methods for solving systems of hyperbolic conservation laws, including front-tracking methods.

• Preface v1 Some Useful Tools 11.1 Introduction 11.2 Bounded Sets 41.2.1 The Least Upper Bound Principle 41.2.2 Bounded Sets in Rn 51.3 Normed Vector Spaces 81.3.1 Vector Spaces 81.3.2 Matrices as Linear Operators 101.3.3 Norms 121.3.4 Inner Products 151.3.5 Norm Equivalence 171.4 Eigenvalues and Matrix Norms 191.4.1 Eigenvalues and Eigenvectors 191.4.2 Matrix Norms 211.5 Results from Calculus 261.5.1 Seven Theorems 261.5.2 The Taylor Theorem 281.6 Problems 332 Approximation of Functions 372.1 Introduction 372.2 Polynomial Interpolation 382.2.1 Motivation and Construction 382.2.2 Practical Considerations 422.2.3 Mathematical Details 432.2.4 Further Remarks 462.3 Piecewise Polynomial Interpolation 482.3.1 Motivation and Construction 482.3.2 Practical Considerations 502.3.3 Mathematical Details 542.3.4 Further Remarks 552.4 Hermite Interpolation 552.4.1 Motivation and Construction 552.4.2 Practical Considerations 592.4.3 Mathematical Details 602.5 Interpolation in Two Dimensions 632.5.1 Constructing Tensor-product Interpolants 642.5.2 Error Estimates for Tensor-product Methods 682.5.3 Interpolation on Triangles: Background 702.5.4 Construction of Planar Interpolants on Triangles 722.5.5 Error Estimates for Interpolation on Triangles 742.6 Splines 782.6.1 Motivation and Construction 782.6.2 Practical Considerations 842.6.3 Mathematical Details 852.6.4 Further Remarks 942.7 Least-squares Methods 952.7.1 Motivation and Construction 962.7.2 Practical Considerations 1002.7.3 Mathematical Details 1012.7.4 Further Remarks 1032.8 Trigonometric Interpolation 1042.8.1 Motivation and Construction 1052.8.2 Practical Considerations: Fast Fourier Transform 1092.8.3 Mathematical Details 1162.8.4 Further Remarks 1182.9 Problems 1183 Direct Methods for Linear Systems 1253.1 Introduction 1253.2 The Condition Number of a Linear System 1273.3 Gauss Elimination 1313.3.1 Motivation and Construction 1313.3.2 Practical Considerations 1333.3.3 Mathematical Details 1393.4 Variants of Gauss Elimination 1483.4.1 Motivation 1483.4.2 The Doolittle and Crout Methods 1483.4.3 Cholesky Decomposition 1523.5 Band Matrices 1553.5.1 Motivation and Construction 1553.5.2 Practical Considerations 1613.5.3 Mathematical Details 1633.5.4 Further Remarks 1663.6 Iterative Improvement 1673.7 Problems 1694 Solution of Nonlinear Equations 1754.1 Introduction 1754.2 Bisection 1794.2.1 Motivation and Construction 1794.2.2 Practical Considerations 1814.3 Successive Substitution in One Variable 1834.3.1 Motivation and Construction 1834.3.2 Practical Considerations 1844.3.3 Mathematical Details 1904.4 Newton’s Method in One Variable 1924.4.1 Motivation and Construction 1924.4.2 Practical Considerations 1944.4.3 Mathematical Details 1994.5 The Secant Method 2034.5.1 Motivation and Construction 2034.5.2 Practical Considerations 2054.5.3 Mathematical Details 2064.6 Successive Substitution: Several Variables 2114.6.1 Motivation and Construction 2114.6.2 Convergence Criteria 2134.6.3 An Application to Differential Equations 2174.7 Newton’s Method: Several Variables 2194.7.1 Motivation and Construction 2194.7.2 Practical Considerations 2214.7.3 Mathematical Details: Newton’s Method 2244.7.4 Mathematical Details: Finite-difference Newton Methods 2294.8 Problems 2335 Iterative Methods for Linear Systems 2395.1 Introduction 2395.2 Conceptual Foundations 2435.3 Matrix-Splitting Techniques 2485.3.1 Motivation and Construction: Jacobi and Gauss–Seidel Methods 2485.3.2 Practical Considerations 2545.3.3 Mathematical Details 2585.4 Successive Overrelaxation 2665.4.1 Motivation 2665.4.2 Practical Considerations 2665.4.3 Mathematical Details 2725.4.4 Further Remarks: The Power Method and Symmetric SOR 2795.5 Multigrid Methods 2805.5.1 Motivation: Error Reduction Versus Smoothing 2805.5.2 A Two-Grid Algorithm 2845.5.3 V-cycles and the Full Multigrid Algorithm 2895.6 The Conjugate-Gradient Method 2935.6.1 Motivation and Construction 2935.6.2 Practical Considerations 2985.6.3 Mathematical Details 3035.6.4 Further Remarks: Krylov Methods and Steepest Descent 3095.7 Problems 3116 Eigenvalue Problems 3176.1 More About Eigenvalues 3186.2 Power Methods 3236.2.1 Motivation and Construction 3236.2.2 Practical Considerations 3256.3 The QR Decomposition 3286.3.1 Geometry and Algebra of the QR Decomposition 3286.3.2 Application to Least-Squares Problems 3336.3.3 Further Remarks 3356.4 The QR Algorithm for Eigenvalues 3386.4.1 Motivation and Construction 3386.4.2 Practical Considerations 3416.4.3 Mathematical Details 3476.4.4 Further Remarks 3506.5 Singular Value Decomposition 3526.5.1 Theory of the Singular Value Decomposition 3526.5.2 Computing Singular Value Decompositions 3546.5.3 Application to Principal Component Analysis 3546.6 Problems 3587 Numerical Integration 3637.1 Introduction 3637.2 Newton–Cotes Formulas 3647.2.1 Motivation and Construction 3647.2.2 Practical Considerations: Composite Formulas 3677.2.3 Mathematical Details 3697.2.4 Further Remarks 3737.3 Romberg and Adaptive Quadrature 3737.3.1 Romberg Quadrature 3747.3.2 Adaptive Quadrature 3797.4 Gauss Quadrature 3857.4.1 Motivation and Construction 3857.4.2 Practical Considerations 3887.4.3 Mathematical Details 3907.5 Problems 3998 Ordinary Differential Equations 4038.1 Introduction 4038.2 One-Step Methods 4068.2.1 Motivation and Construction 4068.2.2 Practical Considerations 4098.2.3 Mathematical Details 4108.2.4 Further Remarks: The Runge–Kutta–Fehlberg Algorithm 4168.3 Multistep Methods: Consistency and Stability 4208.3.1 Motivation 4208.3.2 Adams–Bashforth and Adams–Moulton Methods 4228.3.3 Consistency of Multistep Methods 4238.3.4 Stability of Multistep Methods 4268.3.5 Predictor-Corrector Methods 4308.3.6 Mathematical Details: The Root Condition 4318.4 Multistep Methods: Convergence 4388.4.1 Convergence Implies Stability and Consistency 4398.4.2 Consistency and Stability Imply Convergence 4418.5 Problems 4489 Difference Methods for PDEs 4539.1 Introduction 4539.1.1 Classification 4549.1.2 Characteristic Curves and Characteristic Equations 4559.1.3 Grid Functions and Difference Operators 4609.2 The Poisson Equation 4629.2.1 The Five-Point Method 4639.2.2 Consistency and Convergence 4669.2.3 Accommodating Variable Coefficients 4719.2.4 Accommodating Other Boundary Conditions 4729.2.5 Accommodating Nonrectangular Domains 4739.3 The Advection Equation 4759.3.1 The Courant–Friedrichs–Lewy Condition 4769.3.2 Stability of Approximations to Time-Dependent Problems 4809.3.3 Sufficient Conditions for Convergence 4859.3.4 Further Remarks 4889.4 Other Time-Dependent Equations 4899.4.1 The Heat Equation 4899.4.2 The Advection-Diffusion Equation 4989.4.3 The Wave Equation 5039.5 Problems 50510 Introduction to Finite Elements 51110.1 Introduction and Background 51110.1.1 A Model Boundary-Value Problem 51210.1.2 Variational Formulation 51310.2 A Steady-State Problem 51710.2.1 Construction of a Finite-Element Approximation 51710.2.2 A Basic Error Estimate 52010.2.3 Optimal-Order Error Estimates 52510.2.4 Other Boundary Conditions 52810.2.5 Condition Number of the Finite-Element Matrix 53210.3 A Transient Problem 53710.3.1 A Semidiscrete Formulation 53710.3.2 A Fully Discrete Method 53910.3.3 Convergence of the Fully Discrete Method 54010.4 Problems 547A Divided Differences 549B Local Minima 553C Chebyshev Polynomials 555References 559Index 563