Preface
Chapter 1 Mathematical Review and Error Analysis 1
1.1 Mathematical Review 1
1.2 Errors and Significant Digits 3
1.2.1 Truncation Error and Round-off Error 4
1.2.2 Absolute Error and Relative Error 5
1.2.3 Significant Digits 6
1.3 Avoid the Loss of Accuracy 8
1.3.1 Avoid the Subtraction of Nearly Equal Numbers.8
1.3.2 Avoid Big Numbers “Swallowing” Small Numbers 9
1.3.3 Reduce Computations 9
1.3.4 Avoid Dividing by a Number with Small Absolute Value 10
1.3.5 Use Stable Algorithms 10
1.4 Exercises 11
Chapter 2 Solutions of Equations in One Variable 13
2.1 The Bisection Method 13
2.2 Fixed-Point Iteration 15
2.2.1 Basic Concepts 15
2.2.2 Convergence and Error Estimation 16
2.2.3 Local Convergence and Order of Convergence 19
2.3 Newton’s Method and Secant Method 21
2.3.1 Newton’s Method 21
2.3.2 Secant Method 23
2.3.3 Newton’s Method for Finding Multiple Roots 24
2.4 Acceleration Techniques 28
2.5 Programs 31
2.6 Exercises 34
Chapter 3 Interpolation 36
3.1 Lagrange Interpolation 36
3.2 Newton Interpolation 41
3.3 Aitken’s Method 47
3.4 Hermite Interpolation 49
3.5 Piecewise Polynomial Interpolation 52
3.6 Cubic Spline Interpolation 53
3.7 Programs 58
3.8 Exercises.60
Chapter 4 Curve Fitting and Orthogonal Polynomials 63
4.1 Least Square Method 63
4.2 Least Square Approximation 70
4.3 Orthogonal Polynomials.73
4.4 Programs 79
4.4.1 Least Square Method 79
4.4.2 Least Square Approximation 79
4.5 Exercises 80
Chapter 5 Direct Methods for Linear Systems .82
5.1 Gaussian Elimination Method 82
5.1.1 Linear Systems of Equation 82
5.1.2 Gaussian Elimination with Backward-Substitution 83
5.2 Gaussian Elimination with Partial Pivoting 87
5.3 Matrix Factorization 90
5.4 Two Special Types of Matrices 96
5.5 Gaussian Elimination on Tridiagonal Linear Systems 99
5.6 Norms of Vectors and Matrices 101
5.6.1 Norms of Vectors 101
5.6.2 Norms of Matrices 102
5.7 Ill-Conditioned Linear System and Condition Number 104
5.8 Programs 106
5.9 Exercises 109
Chapter 6 Iterative Methods for Linear Systems 112
6.1 Iterative Methods 112
6.1.1 Jacobi Iterative Method.112
6.1.2 Gauss-Seidel Iterative Method 116
6.1.3 SOR Method.120
6.2 Convergence Analysis for Iterative Methods 123
6.3 Programs 126
6.4 Exercises 129
Chapter 7 Numerical Differentiation and Integration 132
7.1 Numerical Differentiation 132
7.1.1 Three-Point Formulas and Five-Point Formulas 132
7.1.2 The Method by Using Cubic Spline Interpolating Function 135
7.1.3 Varying Step Size Midpoint Method 135
7.1.4 Richardson Extrapolation 137
7.2 Elements of Numerical Integration 139
7.3 Newton-Cotes Quadrature Formulas.143
7.3.1 Basic Concepts of Newton-Cotes Quadrature Formulas 143
7.3.2 Some Common Newton-Cotes Formulas 145
7.4 Composite Numerical Integration 146
7.5 Romberg Integration 151
7.5.1 Recursive Trapezoidal Rule 151
7.5.2 Romberg Integration 154
7.6 Gaussian Quadrature 156
7.6.1 Basic Concepts 156
7.6.2 Two Common Gaussian Quadrature Formulas 160
7.6.3 Stability and Convergence 163
7.7 Programs 164
7.8 Exercises 170
Chapter 8 Numerical Solutions of Ordinary Differential Equations 172
8.1 Elements of Initial Problems 172
8.2 Euler Method and Modified Euler Method 173
8.2.1 Euler Method and Trapezoidal Method.173
8.2.2 Modified Euler Method 175
8.2.3 Local Truncation Error 176
8.3 Runge-Kutta Methods 178
8.3.1 Second-Order Runge-Kutta Methods 178
8.3.2 Some Common Third-and Fourth-Order Runge-Kutta Methods 181
8.4 Stability and Convergence 183
8.5 Multistep Methods 189
8.6 Programs 192
8.7 Exercises 196
Chapter 9 Approximating Eigenvalues and Eigenvectors 199
9.1 Fundamental Theorems 199
9.2 The Power Method 204
9.3 Accelerating Convergence 208
9.4 Inverse Power Method 209
9.5 Householder’s Method 212
9.6 The QR method 218
9.7 Programs 226
9.8 Exercises 228
References 231
Appendix A English-Chinese Math Key Words 232
Appendix B Some Math Expressions and Pronunciations 239
Sample Pages Preview
Abstract
Chapter 1 Mathematical Review and Error Analysis This chapter contains a short review of those topics from elementary single-variable calculus that will be needed in later chapters， together with an introduction to error analysis. 1.1 Mathematical Review The concepts of limit and continuity of a function are fundamental to the study of calculus and the analysis of numerical techniques. Definition 1.1 A function f defined on a set of real numbers has the limit L at xo， written as lim， if， given any real number， there exists a real Definition 1.2 Let be a function defined on a set X of real numbers and. Then f is continuous at if lim. Moreover， f is called a continuous function on the interval， if it is continuous at every point of. Definition 1.3 Let be a function defined in an open interval containing xq. The function f is differentiable at if exists. The number is called the derivative of f at xq. A function that has a derivative at each number in a set is differentiable on . Theorem 1.1 (Mean Value Theorem) If and f is differentiable on，then a number c between a and b exists with (1.1) Theorem 1.2 (Rolle’s Theorem) Suppose that and f is differentiable on (a， b). If，then a number c in (a， b) exists with (1.2) Theorem 1.3 (Generalized Rolle，s Theorem) Let， be distinct zeros of. Suppose that f and its derivatives of order up to n are all continuous on. Then there exists a number c in such that (1.3) Theorem 1.4 (Intermediate Value Theorem) If and u is any number between and， then there exists a number such that (1.4) Corollary 1.1 (Existence Theorem for Roots) Let. If and are opposite in sign， then there exists at least one number c in (a， b) such that (1.5) Theorem 1.5 (Boundedness Theorem) If， then there exist numbers M and m such that (1.6) Corollary 1.2 Supposed that ， and ci， are positive constants. Then there exists a number c between and with the property (1.7) Definition 1.4 The Riemann integral of the function f on the interval [a， b] is the following limit， provided it exists: (1.8) where the numbers，satisfy a and is arbitrary chosen in the interval for each . Theorem 1.6 (Weighted Mean Value Theorem for Integrals) Supposed that f， the Riemann integral of g exists on， and does not change sign on [a， b]. Then there exists a number c in (a， b) such that (1.9) When 1，Theorem 1.6 is the usual Mean Value Theorem for Integrals. Theorem 1.7 (Taylor’s Theorem) Let f G Cn[a，b] and [a，b]. Then for any ， there exists anumber between and x such that (1.10) where， called the n-th Taylor polynomial， is in the form (1.11) and Rn(x)， called the error term or the remainder term， is in the form (1.12) 1.2 Errors and Significant Digits Numerical analysis is the branch of mathematics that provides tools and methods for solving mathematical problems in numerical form. The objective is to develop detailed computational procedures， capable of being implemented on computers， and to study their performance characteristics. The exact solution to a problem is called an analytical solution. Unfortunately， very few analytical solutions can be obtained in practice. Therefore， the numerical solutions， approximations to analytical solutions， are considered. They can be found with a suitable type of calculation-intensive process， known as a numerical method called algorithm. The term “algorithm” is used for a systematic procedure that solves a problem or approximates a solution to the problem. A major advantage of numerical analysis is that a numerical answer can be obtained even when a problem has no analytical solution. Furthermore， only the required mathematical operations are additions， subtractions， multiplications， and divisions as well as comparisons. Because these simple operations are exactly the functions that computers can perform， computers and numerical analysis make a perfect combination. Numerical answers to problems generally contain errors which arise in two areas-those inherent in mathematical formulation of the problem and those incurred in finding the solution numerically. One source of inherent errors incurs when the mathematical statement of a problem is only an approximation to the physical situation. Such errors， called modeling errors， are negligible. Another source of inherent error is the inaccuracies in the physical data. Such errors， called observational errors， are also generally negligible when they are caused by inaccuracies in physical constants (e.g. the gravitational constant). Numerical analysis is interested in the errors caused by solving the mathematical models using numerical methods. Generally speaking， two types of errors， called truncation error and round-off error， are mainly concerned in numerical computing. 1.2.1 Truncation Error and Round-off Error A truncation error is an error made by numerical
