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–Cotes 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
