1 Error Analysis ......1
1.1 Introduction ............ 1
1.2 Sources of Errors .... 2
1.3 Errors and Significant Digits .......... 4
1.4 Error Propagation ... 8
1.5 Qualitative Analysis and Control of Errors ............ 9
1.5.1 Ill-condition Problem and Condition Number....................... 9
1.5.2 The Stability of Algorithm .. 10
1.5.3 The Control of Errors .......... 11
1.6 Computer Experiments................. 14
1.6.1 Functions Needed in the Experiments by Mathematica ...... 14
1.6.2 Experiments by Mathematica...................... 14
1.6.3 Functions Needed in the Experiments by Matlab................ 16
1.6.4 Experiments by Matlab ....... 16
Exercises 1..................... 17
2 Interpolating.......19
2.1 Introduction .......... 20
2.2 Basic Concepts ..... 21
2.3 Lagrange Interpolation ................. 22
2.3.1 Linear and Parabolic Interpolation .............. 22
2.3.2 Lagrange Interpolation Polynomial............. 24
2.3.3 Interpolation Remainder and Error Estimate....................... 25
2.4 Divided-differences and Newton Interpolation .... 29
2.5 Differences and Newton Difference Formulae..... 33
2.5.1 Differences .. 33
2.5.2 Newton Difference Formulae ...................... 35
2.6 Hermite Interpolation ................... 38
2.7 Piecewise Low Degree Interpolation.................... 42
2.7.1 Ill-posed Properties of High Degree Interpolation .............. 42
2.7.2 Piecewise Linear Interpolation .................... 43
2.7.3 Piecewise Cubic Hermite Interpolation....... 44
2.8 Cubic Spline Interpolation............ 45
2.8.1 Definition of Cubic Spline... 45
2.8.2 The Construction of Cubic Spline ............... 46
2.9 Computer Experiments................. 49
2.9.1 Functions Needed in the Experiments by Mathematica ...... 49
2.9.2 Experiments by Mathematica...................... 50
2.9.3 Experiments by Matlab ....... 56
Exercises 2................... 64
3 Best Approximation ...................68
3.1 Introduction .......... 68
3.2 Norms ................... 69
3.2.1 Vector Norms ...................... 69
3.2.2 Matrix Norms ...................... 74
3.3 Spectral Radius..... 76
3.4 Best Linear Approximation .......... 79
3.4.1 Basic Concepts and Theories....................... 79
3.4.2 Best Linear Approximation . 81
3.5 Discrete Least Squares Approximation ................ 82
3.6 Least Squares Approximation and Orthogonal Polynomials........ 87
3.7 Rational Function Approximation 94
3.7.1 Continued Fractions ............ 94
3.7.2 Padé Approximation............ 97
3.8 Computer Experiments................. 99
3.8.1 Functions Needed in The Experiments by Mathematica..... 99
3.8.2 Experiments by Mathematica.................... 100
3.8.3 Functions Needed in The Experiments by Matlab ............ 106
3.8.4 Experiments by Matlab ..... 106
Exercises 3................. 111
4 Numerical Integration and Differentiation ........114
4.1 Introduction ........ 115
4.2 Interpolatory Quadratures........... 116
4.2.1 Interpolatory Quadratures.. 116
4.2.2 Degree of Accuracy........... 117
4.3 Newton-Cotes Quadrature Formula.................... 118
4.4 Composite Quadrature Formula . 123
4.4.1 Composite Trapezoidal Rule ..................... 123
4.4.2 Composite Simpson’s Rule ....................... 124
4.5 Romberg Integration................... 125
4.5.1 Recursive Trapezoidal Rule ...................... 125
4.5.2 Romberg Algorithm .......... 126
4.5.3 Richardson’s Extrapolation ....................... 128
4.6 Gaussian Quadrature Formula .... 129
4.7 Multiple Integrals ....................... 134
4.8 Numerical Differentiation........... 135
4.8.1 Numerical Differentiation . 135
4.8.2 Differentiation Polynomial Interpolation .. 137
4.8.3 Richardson’s Extrapolation ....................... 141
4.9 Computer Experiments............... 144
4.9.1 Functions Needed in the Experiments by Mathematica .... 144
4.9.2 Experiments by Mathematica.................... 144
4.9.3 Experiments by Matlab ..... 149
Exercises 4................... 153
5 Solution of Nonlinear Equations ......................156
5.1 Introduction ........ 156
5.2 Basic Theories .... 158
5.3 Bisection Method 159
5.4 Iterative Method and Its Convergence................ 162
5.4.1 Fixed Point and Iteration ... 162
5.4.2 Global Convergence.......... 163
5.4.3 Local Convergence............ 165
5.4.4 Order of Convergence ....... 167
5.5 Accelerating Convergence.......... 168
5.6 Newton’s Method ....................... 170
5.6.1 Newton’s Method and Its Convergence .... 170
5.6.2 Reduced Newton Method and Newton’s Descent Method ....................... 172
5.6.3 The Case of Multiple Roots....................... 173
5.7 Secant Method and Muller Method .................... 174
5.7.1 Secant Method................... 174
5.7.2 Muller Method................... 175
5.8 Systems of Nonlinear Equations. 176
5.9 Computer Experiments............... 179
5.9.1 Functions Needed in the Experiments by Mathematica .... 179
5.9.2 Experiments by Mathematica.................... 180
5.9.3 Experiments by Matlab ..... 185
Exercises 5................. 188
6 Direct Methods for Solving Linear Systems ....191
6.1 Introduction ........ 192
6.2 Gaussian Elimination.................. 193
6.2.1 Basic Gaussian Elimination....................... 193
6.2.2 Triangular Decomposition. 197
6.3 Gaussian Elimination with Column Pivoting ..... 200
6.4 Methods of the Triangular Decomposition......... 202
6.4.1 The Direct Methods of The Triangular Decomposition .... 202
6.4.2 The Square Root Method .. 203
6.4.3 The Speedup Method......... 206
6.5 Analysis of Round-off Errors ..... 210
6.5.1 Condition Number............. 210
6.5.2 Iterative Refinement .......... 214
6.6 Computer Experiments............... 215
6.6.1 Functions Needed in the Experiments by Mathematica .... 215
6.6.2 Experiments by Mathematica.................... 215
6.6.3 Functions Needed in the Experiments by Matlab.............. 222
6.6.4 Experiments by Matlab ..... 222
Exercises 6................... 227
7 Iterative Techniques for Solving Linear Systems ....................230
7.1 Introduction ........ 231
7.2 Basic Iterative Methods .............. 233
7.2.1 Jacobi Method ................... 234
7.2.2 Gauss-Seidel Method ........ 236
7.2.3 SOR Method...................... 237
7.3 Iterative Method Convergence ... 238
7.3.1 Basic Theorems ................. 238
7.3.2 Some Special Systems of Equations.......... 243
7.4 Computer Experiments............... 247
7.4.1 Functions Needed in The Experiments by Mathematica... 247
7.4.2 Experiments by Mathematica.................... 247
7.4.3 Experiments by Matlab ..... 251
Exercises 7................... 255
8 Numerical Solution of Ordinary Differential Equations ............258
8.1 Introduction ........ 258
8.2 The Existence and Uniqueness of Solutions....... 260
8.3 Taylor-Series Method................. 262
8.4 Euler’s Method ... 263
8.5 Single-step Methods ................... 267
8.5.1 Single-step Methods.......... 267
8.5.2 Local Truncation Error ...... 267
8.6 Runge-Kutta Methods ................ 268
8.6.1 Second-Order Runge-Kutta Method.......... 268
8.6.2 Fourth-Order Runge-Kutta Method........... 270
8.7 Multistep Methods...................... 271
8.7.1 General Formulas of Multistep Methods... 272
8.7.2 Adams Explicit and Implicit Formulas...... 273
8.8 Systems and Higher-Order Differential Equations..................... 275
8.8.1 Vector Notation ................. 276
8.8.2 Taylor-Series Method for Systems............ 278
8.8.3 Fourth-Order Runge-Kutta Formula for Systems.............. 279
8.9 Computer Experiments............... 281
8.9.1 Functions Needed in the Experiments by Mathematica .... 281
8.9.2 Experiments by Mathematica.................... 281
8.9.3 Experiments by Matlab ..... 286
Exercises 8................... 290
Appendix ...............293
Appendix A Mathematica Basic Operations ............ 293
Appendix B Matlab Basic Operations ...................... 309
Appendix C Answers to Selected Question.............. 327
Reference..............332