Numerical Analysis and Algorithms (3rd Edition) (Yu Wenjian)

This book is a textbook for courses such as \"Numerical Analysis\", \"Computational Methods\", and \"Numerical Analysis and Algorithms\". It is mainly aimed at undergraduate students majoring in information science and technology, as well as information and computing science in universities of science and engineering. The content of this book includes the foundation of numerical computing, numerical solutions to nonlinear equations, direct solutions and iterative solutions to linear equations, calculation of matrix eigenvalues ​​and eigenvectors, numerical approximation and interpolation, numerical integration methods, solutions to initial value problems of ordinary differential equations, and knowledge of numerical algorithms and applications. This book covers some of the most basic and commonly used knowledge and methods in the field of numerical analysis and matrix calculation, and adds some newer content in algorithms and applications. In terms of narration, it not only pays attention to the rigor of the theory, but also emphasizes the application background of the method, algorithm design, and comparison of different methods. Chapter 1 Introduction to Numerical Computing 1 1. 1 Overview 1 1. 1. 1 Numerical Computing and Numerical Algorithms 1 1. 1. 2 Problems and Strategies in Numerical Computing 2 1. 1. 3 Numerical Computing Software 4 1. 2 Fundamentals of Error Analysis 6 1. 2. 1 Approximation in Numerical Computing 6 1. 2. 2 Errors and Their Classification 7 1. 2. 3 Sensitivity of Problems and Estimation of Data Transfer Errors 11 1. 2. 4 Stability of Algorithms 14 1. 3 Computer Floating-Point Number Systems and Rounding Errors 16 1. 3. 1 Computer Floating-Point Number Systems 16 1. 3. 2 Rounding and Machine Precision 18 1. 3. 3 Rounding Errors in Floating-Point Operations 20 1. 3. 4 Cancellation Phenomenon 21 1. 4 Ensuring the Accuracy of Numerical Computing 22 1. 4. 1 Some Suggestions for Reducing Rounding Errors 22 1. 4. 2 The main factors affecting the accuracy of the results 25 Comments 26 The history behind the algorithm: William Kahen, the pioneer of floating-point operations 27 Exercises 28 Computer exercises 29 Chapter 2 Root-finding of nonlinear equations 31 2. 1 Introduction 31 2. 1. 1 Solutions of nonlinear equations 31 2. 1. 2 Sensitivity of the problem 32 2. 2 Bisection method 32 2. 2. 1 Principles of the method 32 2. 2. 2 Stability of the algorithm and accuracy of the results 34 2. 3 Fixed point iteration method 36 2. 3. 1 Basic principles 36 2. 3. 2 Sufficient conditions for global convergence 37 2. 3. 3 Local convergence 39 2. 3. 4 Stability and convergence order 40 2. 4 Newton iteration method 41 2. 4. 1 Principles of the method 42 2. 4. 2 Case of multiple roots 44 2. 4.3 Stopping Criteria 44 2.4.4 Problems with Newton\'s Method 45 2.5 Secant Method and Parabola Method 45 2.5.1 Secant Method 46 2.5.2 Parabola Method 47 2.6 Practical Equation Root-Finding Techniques 48 2.6.1 Damped Newton Method 48 2.6.2 Polynomial Equation Root-Finding 48 2.6.3 General Root-Finding Algorithm Zeroin 49 Application Example: How Deep Should Urban Water Pipes Be Buried Underground 52 2.7 Nonlinear Equations and Related Numerical Software 53 2.7.1 Nonlinear Equations 53 2.7.2 Nonlinear Equations Root-Finding Software 55 Commentary 56 The History Behind the Algorithm: Newton and Newton\'s Method 57 Exercises 58 Computer Problems 59 Chapter 3 Direct Solution of Linear Equations 61 3.1 3.1.1 Concepts in Linear Algebra 61 3.1.2 Vector Norm and Matrix Norm 64 3.1.3 Problem Sensitivity and Matrix Condition Number 68 3.2 Gaussian Elimination 71 3.2.1 Basic Gaussian Elimination 71 3.2.2 Gauss-Jordan Elimination 74 3.3 LU Decomposition of Matrices 78 3.3.1 Matrix Form of Gaussian Elimination 78 3.3.2 Direct LU Decomposition Algorithm of Matrices 81 3.3.3 Purpose of LU Decomposition 84 3.4 Pivoting Techniques and Algorithm Stability 86 3.4.1 Why Pivot 86 3.4.2 LU Decomposition Using Partial Pivot Technique 88 3.4.3 Other Pivoting Techniques 92 3.4.4 3.5 Stability of the Algorithm 93 3.5 Solution of Symmetric Positive Definite Matrices and Banded Matrices 94 3.5.1 Cho le Sky Decomposition of Symmetric Positive Definite Matrices 94 3.5.2 Solution of Banded Linear Equations 97 Application Example: Solution of Steady-State Circuit 100 3.6 Practical Techniques for Sparse Linear Equations 101 3.6.1 Basic Concepts of Sparse Matrices 102 3.6.2 Related Functions in MATLAB 104 3.7 Numerical Software 107 Review 109 History Behind the Algorithm: Wilkinson and Numerical Analysis 110 Exercises 111 Computer Problems 113 Chapter 4 Iterative Solution of Linear Equations 114 4.1 Basic Theory of Iterative Solution 114 4.1.1 Basic Concepts 114 4.1.2 Convergence of the First-Order Steady-State Iterative Method 115 4.1.3 Convergence order and convergence rate 118 4. 2 Classical iterative methods 120 4. 2. 1 Jacobi iteration method 120 4. 2. 2 Gauss-Seidel iteration method 121 4. 2. 3 Successive super relaxation iteration method 123 4. 2. 4 Convergence conditions of three iterative methods 125 Application example: stress analysis of truss structure 128 4. 3 Introduction to conjugate gradient method 130 4. 3. 1 Steepest descent method 130 4. 3. 2 Conjugate gradient method 133 4. 4 Comparison of various methods 137 4. 4. 1 Comparison between iterative methods 137 4. 4. 2 Comparison between direct method and iterative method 140 4. 5 Related numerical software 141 Review 142 History behind the algorithm: Jacobi 144 Exercises 145 Computer exercises 146 Chapter 5 Matrix Eigenvalue Calculation 148 5. 1 Basic Concepts and Eigenvalue Distribution 148 5. 1. 1 Basic Concepts and Properties 148 5. 1. 2 Estimation of Eigenvalue Distribution Range 152 5. 2 Power Method and Inverse Power Method 154 5. 2. 1 Power Method 154 5. 2. 2 Methods to Accelerate Convergence 158 5. 2. 3 Inverse Power Method 160 Application Example: Google\'s PageRank Algorithm 162 5. 3 Orthogonal Triangulation of Matrix 165 5. 3. 1 Housholde r Transformation 165 5. 3. 2 Givens Rotation Transformation 167 5. 3. 3 QR Decomposition of Matrix 168 5. 4 Calculation of All Eigenvalues ​​and QR Algorithm 172 5. 4. 1 Shrinkage Technology 172 5. 4. 2 5.5 Introduction to Singular Value Decomposition 179 5.5.1 Basic Concepts and Singular Value Decomposition Theorem 179 5.5.2 Related Properties and Calculation Methods 182 5.6 Related Numerical Software 184 Comments 186 History Behind the Algorithm: A. Housholder and Matrix Decomposition 187 Exercises 188 Computer Problems 191 Chapter 6 Function Approximation and Function Interpolation 193 6.1 Basic Concepts of Function Approximation 193 6.1.1 Function Space 193 6.1.2 Different Types of Function Approximation 196 6.2 Best Square Approximation of Continuous Functions 198 6.2.1 General Normal Equation Method 198 6.2.2 Approximation Using Orthogonal Function Families 202 6.3 Curve Fitting and Least Squares Method 206 6.3.1 Matrix Form of Problem and Normal Equation Method 206 6.3.2 Solving Least Squares Problem by Orthogonalization Method 209 Application Example: Energy Estimation of Atomic Bomb Explosion 213 6.4 Function Interpolation and Lagrange Interpolation Method 214 6.4.1 Basic Concept of Interpolation 214 6.4.2 Lagrange Interpolation Method 215 6.4.3 Error Estimation of Polynomial Interpolation 218 6.5 Newton Interpolation Method 220 6.5.1 Basic Idea 220 6.5.2 Difference quotient and Newton interpolation formula 221 6. 6 Piecewise polynomial interpolation 226 6. 6. 1 Ill-conditioned properties of high-order polynomial interpolation 226 6. 6. 2 Piecewise linear interpolation 227 6. 6. 3 Piecewise Hermite interpolation 228 6. 6. 4 Shape-preserving piecewise interpolation 231 6. 7 Spline interpolation function 233 6. 7. 1 Cubic spline interpolation 233 6. 7. 2 Construction of cubic spline interpolation function 234 6. 7. 3 B-spline function 236 Commentary 239 The history behind the algorithm: Lagrange and interpolation method 240 Exercises 242 Computer exercises 244 Chapter 7 Numerical integration and numerical differentiation 246 7. 1 Introduction to numerical integration 246 7. 1. 1 Basic ideas 246 7. 1. 2 Remainder of the quadrature formula and algebraic precision 248 7. 1. 3 Convergence and stability of the quadrature formula 249 7. 2 Newton-Cotes formula 250 7. 2. 1 Cotes coefficient and several low-order formulas 250 7. 2. 2 Algebraic precision of Newton-Cotes formula 252 7. 2. 3 Remainder of several low-order formulas 253 7. 3 Composite quadrature formula 254 7. 3. 1 Composite trapezoidal formula 254 7. 3. 2 Composite Simpson formula 255 7. 3. 3 Calculation of composite quadrature formula with halved step size 257 7. 4 Romberg integral algorithm and Richardson extrapolation 258 7. 4. 1 Remainder expansion of the composite trapezoidal formula 258 7. 4. 2 7.5 Adaptive integration algorithm 262 7.5.1 Principle of adaptive integration 262 7.5.2 A specific adaptive integration algorithm 263 7.6 Gaussian quadrature formula 265 7.6.1 General theory 266 7.6.2 Gaussian-Legendre integral formula and others 269 Application example: Calculation of lunar satellite orbit length 270 7.7 Numerical differentiation 272 7.7.1 Basic finite difference formula 272 7.7.2 Interpolation type derivative formula 274 7.7.3 Extrapolation algorithm for numerical differentiation 276 Commentary 277 The history behind the algorithm: \"Prince of Mathematics\" Gauss 279 Exercises 280 Computer exercises 281 Chapter 8 Solutions of Initial Value Problems for Ordinary Differential Equations 283 8.1 Introduction 283 8.1.1 Problem Classification and Solvability 283 8.1.2 Problem Sensitivity 284 8.2 Simple Numerical Solutions and Related Concepts 286 8.2.1 Euler Method 286 8.2.2 Stability and Accuracy of Numerical Solutions 288 8.2.3 Backward Euler Method and Trapezoidal Method 290 8.3 Runge-Kutta Method 292 8.3.1 Basic Idea 292 8.3.2 Several Explicit RK Formulas 293 8.3.3 Stability and Convergence of Explicit RK Formulas 297 8.3.4 RK Method with Automatic Variable Step Size 298 8.4 Multi-step Method 300 8.4.1 300 8.4.2 Adams formula 303 8.4.3 More discussion 307 8.5 Ordinary differential equations and practical techniques 307 8.5.1 First-order ordinary differential equations 308 8.5.2 Practical ODE solver in MATLAB 311 Application example: Lorenz attractor 314 Commentary 316 The history behind the algorithm: Euler, the \"hero of mathematicians\" 317 Exercises 318 Computer exercises 320 Appendix A Notes on mathematical notation 322 Appendix B Introduction to MATLAB 324 Appendix C Introduction to Python numerical computing 344 Appendix D Answers to some exercises 348 Algorithm index 352 Terminology index 354 References 362