Most physical problems can be written in the form of mathematical equations (differential, integral, etc.). Mathematicians have always sought to find analytical solutions to the equations encountered in the different sciences of the engineer (mechanics, physics, biology, etc.). These equations are sometimes complicated and much effort is required to simplify them. In the middle of the 20th century, the arrival of the first computers gave birth to new methods of resolution that will be described by numerical methods. They allow solving numerically as precisely as possible the equations encountered (resulting from the modeling of course) and to approach the solution of the problems posed. The approximate solution is usually computed on a computer by means of a suitable algorithm.
The objective of this book is to introduce and study the basic numerical methods and those advanced to be able to do scientific computation. The latter refers to the implementation of approaches adapted to the treatment of a scientific problem arising from physics (meteorology, pollution, etc.) or engineering (structural mechanics, fluid mechanics, signal processing, etc.) .
Table of Contents
Preface xi
Part 1. Introduction 1
Chapter 1. Review of Linear Algebra 3
1.1. Vector spaces 3
1.1.1. General definitions 3
1.1.2. Free families, generating families and bases 4
1.2. Linear mappings 5
1.3. Matrices 7
1.3.1. Operations on matrices 7
1.3.2. Change-of-basis matrices 8
1.3.3. Matrix notations 9
1.4. Determinants 10
1.5. Scalar product 12
1.6. Vector norm 12
1.7. Matrix eigenvectors and eigenvalues 13
1.7.1. Definitions and properties 13
1.7.2. Matrix diagonalization 15
1.7.3. Triangularization of matrices 15
1.8. Using Matlab 16
Chapter 2. Numerical Precision 21
2.1. Introduction 21
2.2. Machine representations of numbers 22
2.3. Integers 23
2.3.1. External representation 23
2.3.2. Internal representation of positive integers 24
2.4. Real numbers 25
2.4.1. External representation 25
2.4.2. Internal encoding of real numbers 25
2.5. Representation errors 26
2.5.1. Properties of computer-based arithmetic 27
2.5.2. Operation of subtraction 28
2.5.3. Stability 29
2.6. Determining the best algorithm 29
2.7. Using Matlab 30
2.7.1. Definition of variables 30
2.7.2. Manipulating numbers 30
Part 2. Approximating Functions 35
Chapter 3. Polynomial Interpolation 37
3.1. Introduction 37
3.2. Interpolation problems 37
3.2.1. Linear interpolation 38
3.3. Polynomial interpolation techniques 38
3.4. Interpolation with the Lagrange basis 39
3.4.1. Polynomial interpolation error 43
3.4.2. Neville–Aitken method 46
3.5. Interpolation with the Newton basis 46
3.6. Interpolation using spline functions 48
3.6.1. Hermite interpolation 50
3.6.2. Spline interpolation error 55
3.7. Using Matlab 58
3.7.1. Operations on polynomials 58
3.7.2. Manipulating polynomials 59
3.7.3. Evaluation of polynomials 60
3.7.4. Linear and nonlinear interpolation 60
3.7.5. Lagrange function 63
3.7.6. Newton function 64
Chapter 4. Numerical Differentiation 67
4.1. First-order numerical derivatives and the truncation error 67
4.2. Higher-order numerical derivatives 70
4.3. Numerical derivatives and interpolation 71
4.4. Studying the differentiation error 73
4.5. Richardson extrapolation 77
4.6. Application to the heat equation 78
4.7. Using Matlab 81
Chapter 5. Numerical Integration 83
5.1. Introduction 83
5.2. Rectangle method 84
5.3. Trapezoidal rule 84
5.4. Simpson’s rule 87
5.5. Hermite’s rule 90
5.6. Newton–Côtes rules 91
5.7. Gauss–Legendre method 92
5.7.1. Problem statement 92
5.7.2. Legendre polynomials 94
5.7.3. Choosing the αi and xi (i = 0, , n) 99
5.8. Using Matlab 100
5.8.1. Matlab functions for numerical integration 100
5.8.2. Trapezoidal rule 101
5.8.3. Simpson’s rule 103
Part 3. Solving Linear Systems 107
Chapter 6. Matrix Norm and Conditioning 109
6.1. Introduction 109
6.2. Matrix norm 109
6.3. Condition number of a matrix 113
6.3.1. Approximation of K(A) 116
6.4. Preconditioning 116
6.5. Using Matlab 117
6.5.1. Matrices and vectors 117
6.5.2. Condition number of a matrix 119
Chapter 7. Direct Methods 123
7.1. Introduction 123
7.2. Method of determinants or Cramer’s method 123
7.2.1. Matrix inversion by Cramer’s method 124
7.3. Systems with upper triangular matrices 124
7.4. Gaussian method 125
7.4.1. Solving multiple systems in parallel 129
7.5. Gauss–Jordan method 129
7.5.1. Underlying principle 129
7.5.2. Computing the inverse of a matrix with the Gauss–Jordan algorithm 131
7.6. LU decomposition 132
7.7. Thomas algorithm 133
7.8. Cholesky decomposition 134
7.9. Using Matlab 136
7.9.1. Matrix operations 136
7.9.2. Systems of linear equations 138
Chapter 8. Iterative Methods 147
8.1. Introduction 147
8.2. Classical iterative techniques 148
8.2.1. Jacobi method 149
8.2.2. Gauss–Seidel method 151
8.2.3. Relaxation method 152
8.2.4. Block forms of the Jacobi, Gauss–Seidel and relaxation methods 154
8.3. Convergence of iterative methods 155
8.4. Conjugate gradient method 157
8.5. Using Matlab 159
8.5.1. Jacobi method 159
8.5.2. Relaxation method 160
Chapter 9. Numerical Methods for Computing Eigenvalues and Eigenvectors 163
9.1. Introduction 163
9.2. Computing det (A − λI) directly 164
9.3. Krylov methods 166
9.4. LeVerrier method 167
9.5. Jacobi method 168
9.6. Power iteration method 171
9.6.1. Deflation algorithm 172
9.7. Inverse power method 173
9.8. Givens–Householder method 174
9.8.1. Givens algorithm 175
9.9. Using Matlab 176
9.9.1. Application to a buckling beam 177
Chapter 10. Least-squares Approximation 185
10.1. Introduction 185
10.2. Analytic formulation 185
10.3. Algebraic formulation 191
10.3.1. Standard results on orthogonality 191
10.3.2. Least-squares problem 191
10.3.3. Solving by orthogonalization 192
10.4. Numerically solving linear equations by QR factorization 193
10.4.1. Householder transformations 193
10.4.2. QR factorization 193
10.4.3. Application to the least-squares problem 193
10.5. Applications 194
10.5.1. Curve fitting 194
10.5.2. Approximations of derivatives 195
10.6. Using Matlab 195
Part 4. Appendices 199
Appendix 1. Introduction to Matlab 201
Appendix 2. Introduction to Optimization 209
Bibliography 215
Index 217
