An Introduction to Numerical Methods and Analysis (Revised Edition)(Hardcover)

Description

The objective of this book is for the reader to learn where approximation methods come from, why they work, why they sometimes don't work, and when to use which of many techniques that are available, and to do all this in a way that emphasizes readability and usefulness to the numerical methods novice. Each chapter and each section begins with the basic, elementary material and gradually builds up to more advanced topics. The text begins with a review of the important calculus results, and why and where these ideas play an important role throughout the book. Some of the concepts required for the study of computational mathematics are introduced, and simple approximations using Taylor's Theorem are treated in some depth. The exposition is intended to be lively and "student friendly". Exercises run the gamut from simple hand computations that might be characterized as "starter exercises", to challenging derivations and minor proofs, to programming exercises.

Table of Contents

Preface.
1. Introductory Concepts and Calculus Review.

1.1 Basic Tools of Calculus.

1.1.1 Taylor's Theorem.

1.1.2 Mean Value and Extreme Value Theorems.

1.2 Error, Approximate Equality, and Asymptotic Order Notation.

1.2.1 Error.

1.2.2 Notation: Approximate Equality.

1.2.3 Notation: Asymptotic Order.

1.3 A Primer on Computer Arithmetic.

1.4 A Word on Computer Languages and Software.

1.5 Simple Approximations.

1.6 Application: Approximating the Natural Logarithm.

References.

2. A Survey of Simple Methods and Tools.

2.1 Horner’s Rule and Nested Multiplication.

2.2 Difference Approximations to the Derivative.

2.3 Application: Euler’s Method for Initial Value Problems.

2.4 Linear Interpolation.

2.5 Application - The Trapezoid Rule.

2.6 Solution of Tridiagonal Linear Systems.

2.7 Application: Simple Two-Point Boundary Value Problems.

3. Root-Finding.

3.1 The Bisection Method.

3.2 Newton's Method: Derivation and Examples.

3.3 How to Stop Newton’s Method.

3.4 Application: Division Using Newton’s Method.

3.5 The Newton Error Formula.

3.6 Newton's Method: Theory and Convergence.

3.7 Application: Computation of the Square Root.

3.8 The Secant Method: Derivation and Examples.

3.9 Fixed Point Iteration.

3.10 Special Topics in Root-finding Methods.

3.10.1 Extrapolation and Acceleration.

3.10.2 Variants of Newton's Method.

3.10.3 The Secant Method: Theory and Convergence.

3.10.4 Multiple Roots.

3.10.5 In Search of Fast Global Convergence: Hybrid Algorithms.

3.11 Literature and Software Discussion 156.

References.

4. Interpolation and Approximation.

4.1 Lagrange Interpolation.

4.2 Interpolation and Divided Differences.

4.3 Interpolation Error.

4.4 Application: Muller’s Method and Inverse Quadratic Interpolation.

4.5 Application: More Approximations to the Derivative.

4.6 Hermite Interpolation.

4.7 Piecewise Polynomial Interpolation.

4.8 An Introduction to Splines.

4.8.1 Definition of the Problem.

4.8.2 Cubic B-Splines.

4.9 Application: Solution of Boundary Value Problems.

4.10 Least Squares Concepts in Approximation.

4.10.1 An Introduction to Data Fitting.

4.10.2 Least Squares Approximation and Orthogonal Polynomials.

4.11 Advanced Topics in Interpolation Error.

4.11.1 Stability of Polynomial Interpolation.

4.11.2 The Runge Example.

4.11.3 The Chebyshev nodes.

4.12 Literature and Software Discussion.

References.

5. Numerical Integration.

5.1 A Review of the Definite Integral.

5.2 Improving the Trapezoid Rule.

5.3 Simpson’s Rule and Degree of Precision.

5.4 The Midpoint Rule.

5.5 Application: Stirling's Formula.

5.6 Gaussian Quadrature.

5.7 Extrapolation Methods.

5.8 Special Topics in Numerical Integration.

5.8.1 Romberg Integration.

5.8.2 Quadrature with Non-Smooth Integrands.

5.8.3 Adaptive Integration.

5.8.4 Peano Estimates for the Trapezoid Rule.

5.9 Literature and Software Discussion.

References.

6. Numerical Methods for Ordinary Differential Equations.

6.1 The Initial Value Problem - Background.

6.2 Euler’s Method.

6.3 Analysis of Euler’s Method.

6.4 Variants of Euler’s Method.

6.4.1 The Residual and Truncation Error.

6.4.2 Implicit Methods and Predictor-Corrector Schemes.

6.4.3 Starting Values and Multistep Methods.

6.4.4 The Midpoint Method and Weak Stability.

6.5 Single Step Methods? Runge-Kutta.

6.6 Multi-step Methods.

6.6.1 The Adams Families.

6.6.2 The BDF Family.

6.7 Stability Issues.

6.7.1 Stability Theory for Multistep Methods.

6.7.2 Stability Regions.

6.8 Application to Systems of Equations.

6.8.1 Implementation Issues and Examples.

6.8.2 Stiff Equations.

6.8.3 A-Stability.

6.9 Adaptive Solvers.

6.10 Boundary Value Problems.

6.10.1 Simple Difference Methods.

6.10.2 Shooting Methods.

6.11 Literature and Software Discussion.

References.

7. Numerical Methods for the Solution of Systems of Equations.

7.1 Linear Algebra Review.

7.2 Linear Systems and Gaussian Elimination.

7.3 Operation Counts.

7.4 The LU Factorization.

7.5 Perturbation, Conditioning and Stability.

7.5.1 Vector and Matrix Norms.

7.5.2 The Condition Number and Perturbations.

7.5.3 Estimating the Condition Number.

7.5.4 Iterative Refinement.

7.6 SPD Matrices and the Cholesky Decomposition.

7.7 Iterative Methods for Linear Systems - A Brief Survey.

7.8 Nonlinear Systems: Newton's Method and Related Ideas.

7.8.1 Newton's Method.

7.8.2 Fixed Point Methods.

7.9 Application: Numerical Solution of Nonlinear BVP’s.

7.10 Literature and Software Discussion.

References.

8. Approximate Solution of the Algebraic Eigenvalue Problem.

8.1 Eigenvalue Review.

8.2 Reduction to Hessenberg Form.

8.3 Power Methods.

8.4 An Overview of the QR Iteration.

8.5 Literature and Software Discussion.

References.

9. A Survey of Finite Difference Methods for Partial Differential Equations.

9.1 Difference Methods for the Diffusion Equation.

9.1.1 The Basic Problem.

9.1.2 The Explicit Method and Stability.

9.1.3 Implicit Methods and the Crank-Nicolson Method.

9.2 Difference Methods for Poisson Equations.

9.2.1 Discretization.

9.2.2 Banded Cholesky Solvers.

9.2.3 Iteration and the Method of Conjugate Gradients.

9.3 Literature and Software Discussion.

References.

Appendix A: Proofs of Selected Theorems, and Other Additional Material.

A.1 Proofs of the Interpolation Error Theorems.

A.2 Proof of Stability.

A.3 Stiff Systems of Differential Equations and Eigenvalues.

A.4 The Matrix Perturbation Theorem.

Index.

描述

本書的目標是讓讀者了解近似方法的來源、為什麼它們有效、為什麼有時候無效，以及在什麼情況下使用可用的眾多技巧，並以強調可讀性和對數值方法初學者的實用性的方式進行。每個章節和每個部分都從基本的初等材料開始，逐漸發展到更高級的主題。文本以重要的微積分結果的回顧開始，並解釋了這些想法在整本書中扮演重要角色的原因和位置。介紹了計算數學研究所需的一些概念，並對使用泰勒定理進行簡單近似進行了深入探討。本書的撰寫旨在生動且“學生友好”。練習從簡單的手算練習（可以被視為“入門練習”）到具有挑戰性的推導和小證明，再到編程練習。

目錄

前言
1. 初級概念和微積分回顧
1.1 微積分的基本工具
1.1.1 泰勒定理
1.1.2 平均值和極值定理
1.2 誤差、近似相等和漸進順序符號
1.2.1 誤差
1.2.2 符號：近似相等
1.2.3 符號：漸進順序
1.3 關於計算機算術的入門知識
1.4 關於計算機語言和軟件的一點說明
1.5 簡單的近似
1.6 應用：近似自然對數
參考文獻
2. 簡單方法和工具的概述
2.1 霍納法則和嵌套乘法
2.2 導數的差分近似
2.3 應用：歐拉法解初值問題
2.4 線性插值
2.5 應用：梯形法則
2.6 解三對角線性系統
2.7 應用：簡單的兩點邊界值問題
3. 尋找根
3.1 二分法
3.2 牛頓法：推導和例子
3.3 如何停止牛頓法
3.4 應用：使用牛頓法進行除法