1 Solution of equations by iteration 1
1.1 Introduction 1
1.2 Simple iteration 2
1.3 Iterative solution of equations 17
1.4 Relaxation and Newton’s method 19
1.5 The secant method 25
1.6 The bisection method 28
1.7 Global behaviour 29
1.8 Notes 32
Exercises 35
2 Solution of systems of linear equations 39
2.1 Introduction 39
2.2 Gaussian elimination 44
2.3 LU factorisation 48
2.4 Pivoting 52
2.5 Solution of systems of equations 55
2.6 Computational work 56
2.7 Norms and condition numbers 58
2.8 Hilbert matrix 72
2.9 Least squares method 74
2.10 Notes 79
Exercises 82
3 Special matrices 87
3.1 Introduction 87
3.2 Symmetric positive definite matrices 87
3.3 Tridiagonal and band matrices 93
3.4 Monotone matrices 98
3.5 Notes 101
Exercises 102
4 Simultaneous nonlinear equations 104
4.1 Introduction 104
4.2 Simultaneous iteration 106
4.3 Relaxation and Newton’s method 116
4.4 Global convergence 123
4.5 Notes 124
Exercises 126
5 Eigenvalues and eigenvectors of a symmetric matrix 133
5.1 Introduction 133
5.2 The characteristic polynomial 137
5.3 Jacobi’s method 137
5.4 The Gerschgorin theorems 145
5.5 Householder’s method 150
5.6 Eigenvalues of a tridiagonal matrix 156
5.7 The QRalgorithm 162
5.7.1 The QRfactorisation revisited 162
5.7.2 The definition of the QRalgorithm 164
5.8 Inverse iteration for the eigenvectors 166
5.9 The Rayleigh quotient 170
5.10 Perturbation analysis 172
5.11 Notes 174
Exercises 175
6 Polynomial interpolation 179
6.1 Introduction 179
6.2 Lagrange interpolation 180
6.3 Convergence 185
6.4 Hermite interpolation 187
6.5 Differentiation 191
6.6 Notes 194
Exercises 195
7 Numerical integration – I 200
7.1 Introduction 200
7.2 Newton–Cotes formulae 201
7.3 Error estimates 204
7.4 The Runge phenomenon revisited 208
7.5 Composite formulae 209
7.6 The Euler–Maclaurin expansion 211
7.7 Extrapolation methods 215
7.8 Notes 219
Exercises 220
8 Polynomial approximation in the -norm 224
8.1 Introduction 224
8.2 Normed linear spaces 224
8.3 Best approximation in the -norm 228
8.4 Chebyshev polynomials 241
8.5 Interpolation 244
8.6 Notes 247
Exercises 248
9 Approximation in the 2-norm 252
9.1 Introduction 252
9.2 Inner product spaces 253
9.3 Best approximation in the 2-norm 256
9.4 Orthogonal polynomials 259
9.5 Comparisons 270
9.6 Notes 272
Exercises 273
10 Numerical integration – II 277
10.1 Introduction 277
10.2 Construction of Gauss quadrature rules 277
10.3 Direct construction 280
10.4 Error estimation for Gauss quadrature 282
10.5 Composite Gauss formulae 285
10.6 Radau and Lobatto quadrature 287
10.7 Note 288
Exercises 288
11 Piecewise polynomial approximation 292
11.1 Introduction 292
11.2 Linear interpolating splines 293
11.3 Basis functions for the linear spline 297
11.4 Cubic splines 298
11.5 Hermite cubic splines 300
11.6 Basis functions for cubic splines 302
11.7 Notes 306
Exercises 307
12 Initial value problems for ODEs 310
12.1 Introduction 310
12.2 One-step methods 317
12.3 Consistency and convergence 321
12.4 An implicit one-step method 324
12.5 Runge–Kutta methods 325
12.6 Linear multistep methods 329
12.7 Zero-stability 331
12.8 Consistency 337
12.9 Dahlquist’s theorems 340
12.10 Systems of equations 341
12.11 Stiff systems 343
12.12 Implicit Runge–Kutta methods 349
12.13 Notes 353
Exercises 355
13 Boundary value problems for ODEs 361
13.1 Introduction 361
13.2 A model problem 361
13.3 Error analysis 364
13.4 Boundary conditions involving a derivative 367
13.5 The general self-adjoint problem 370
13.6 The Sturm–Liouville eigenvalue problem 373
13.7 The shooting method 375
13.8 Notes 380
Exercises 381
14 The finite element method 385
14.1 Introduction: the model problem 385
14.2 Rayleigh–Ritz and Galerkin principles 388
14.3 Formulation of the finite element method 391
14.4 Error analysis of the finite element method 397
14.5 A posteriori error analysis by duality 403
14.6 Notes 412
Exercises 414
Appendix A An overview of results from real analysis 419
Appendix B WWW-resources 423
Bibliography 424
Index 429