Scientific Computing with MATLAB and Octave

In this second edition of scientific computing with MATLAB and Octave we have enriched all the Chapters by introducing several new problems. Moreover, we have added new methods for the numerical solution of linear and nonlinear systems, the eigenvalue computation and the solution of initial-value problems. Another relevant improvement is that we also use the Octave programming environment.

Octave is a reimplementation of part of MATLAB which includes many numerical facilities of MATLAB and is freely distributed under the GNU General Public License. Throughout the book, we shall often make use of the expression “MATLAB command”: in this case, MATLAB should be understood as the language which is the common subset of both programs MATLAB and Octave. We have striven to ensure a seamless usage of our
codes and programs under both MATLAB and Octave. In the few cases where this does not apply, we shall write a short explanation notice at the end of each corresponding section.

For this second edition we would like to thank Paola Causin for having proposed several problems, Christophe Prud´homme, John W. Eaton and David Bateman for their help with Octave, and Silvia Quarteroni for the translation of the new sections.

Contents

1 What can’t be ignored . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 1
1.1 Real numbers . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . 2
1.1.1 How we represent them . . . . . . . . . . . . . . . . . . . .. . . . . . . 2
1.1.2 How we operate with floating-point numbers . . . . .  . .. . 4
1.2 Complex numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . .. . 6
1.3 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . .. . . . 8
1.4 Real functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.5 To err is not only human . . . . . . . . . . . . . . . . . . . . . . . .. . . . 23
1.6 The MATLAB and Octave environments . . . . . . . . . . . . .. . . 28
1.7 The MATLAB language . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 29
1.8 What we haven’t told you . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
1.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2 Nonlinear equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.1 The bisection method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.2 The Newton method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
2.3 Fixed point iterations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.4 Acceleration using Aitken method . . . . . . . . . . . . . . . . . . . . 56
2.5 Algebraic polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
2.6 What we haven’t told you . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
2.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3 Approximation of functions and data . . . . . . . . . . . . . . . . . . .. . . . 71
3.1 Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
3.2 Piecewise linear interpolation . . . . . . . . . . . . . . . . . . . . . . . . 86
3.3 Approximation by spline functions . . . . . . . . . . . . . . . . . . . . 88
3.4 The least-squares method. . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
3.5 What we haven’t told you . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
3.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
4 Numerical differentiation and integration . . . . . . . . . . . . .. . . . . . 101
4.1 Approximation of function derivatives . . . . . . . . . . . . . . . . . 103
4.2 Numerical integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
4.3 Interpolatory quadratures . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
4.4 Simpson adaptive formula . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
4.5 What we haven’t told you . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
4.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
5 Linear systems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
5.1 The LU factorization method . . . . . . . . . . . . . . . . . . . . . . . . 126
5.2 The pivoting technique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
5.3 How accurate is the LU factorization? . . . . . . . . . . . . . . . . . 136
5.4 How to solve a tridiagonal system . . . . . . . . . . . . . . . . . . . . 140
5.5 Overdetermined systems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
5.6 What is hidden behind the command
. . . . . . . . . . . . . . . 143
5.7 Iterative methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
5.7.1 How to construct an iterative method . . . . . . . . . . . . . . . . . 146
5.8 Richardson and gradient methods . . . . . . . . . . . . . . . . . . . . 150
5.9 The conjugate gradient method . . . . . . . . . . . . . . . . . . . . . . 153
5.10 When should an iterative method be stopped? . . . . . . . . . 156
5.11 To wrap-up: direct or iterative? . . . . . . . . . . . . . . . . . . . . . . 159
5.12 What we haven’t told you . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
5.13 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
6 Eigenvalues and eigenvectors . . . . . . . . . . . . . . . . . . . . . . . . . 167
6.1 The power method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
6.2 Generalization of the power method . . . . . . . . . . . . . . . . . . 174
6.3 How to compute the shift . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
6.4 Computation of all the eigenvalues . . . . . . . . . . . . . . . . . . . . 179
6.5 What we haven’t told you . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
6.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
7 Ordinary differential equations . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 187
7.1 The Cauchy problem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
7.2 Euler methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
7.3 The Crank-Nicolson method . . . . . . . . . . . . . . . . . . . . . . . . . 197
7.4 Zero-stability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
7.5 Stability on unbounded intervals . . . . . . . . . . . . . . . . . . . . . 202
7.6 High order methods. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
7.7 The predictor-corrector methods . . . . . . . . . . . . . . . . . . . . . 216
7.8 Systems of differential equations . . . . . . . . . . . . . . . . . . . . . . 219
7.9 Some examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
7.10 What we haven’t told you . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
7.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
8 Numerical methods for (initial-)boundary-value problems . . . .  . .. . . . . . . 237
8.1 Approximation of boundary-value problems . . . . . . . . . . . . . . . . . . 240
8.2 Finite difference approximation of the heat equation . . . . . . . .. . 253
8.3 The wave equation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
8.3.1 Approximation by finite differences . . . . . . . . . . . . . . . . . . . 260
8.4 What we haven’t told you . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
8.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264
9 Solutions of the exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 267