Scientific Computing with MATLAB and Octave – Fourth Edition

Scientific Computing with MATLAB and Octave – Fourth Edition
Texts in Computational Science and Engineering 2
Editors
Timothy J. Barth, Michael Griebel, David E. Keyes, Risto M. Nieminen, Dirk Roose, Tamar Schlick
Contents
1 What can’t be ignored . 1
1.1 The MATLAB and Octave environments 1
1.2 Real numbers . 3
1.2.1 How we represent them 3
1.2.2 How we operate with floating-point numbers 6
1.3 Complex numbers . 8
1.4 Matrices . 10
1.4.1 Vectors 14
1.5 Real functions 16
1.5.1 The zeros 19
1.5.2 Polynomials 20
1.5.3 Integration and differentiation 22
1.6 To err is not only human . 25
1.6.1 Talking about costs 28
1.7 The MATLAB language . 30
1.7.1 MATLAB statements 32
1.7.2 Programming in MATLAB . 34
1.7.3 Examples of differences between MATLAB
and Octave languages 38
1.8 What we haven’t told you 38
1.9 Exercises . 39
2 Nonlinear equations . 41
2.1 Some representative problems . 41
2.2 The bisection method 43
2.3 The Newton method . 47
2.3.1 How to terminate Newton’s iterations 50
2.4 The secant method 51
2.5 Systems of nonlinear equations 52
XIXII Contents
2.6 Fixed point iterations 56
2.6.1 How to terminate fixed point iterations 62
2.7 Acceleration using Aitken method . 63
2.8 Algebraic polynomials 67
2.8.1 H¨orner’s algorithm 68
2.8.2 The Newton-H¨orner method 70
2.9 What we haven’t told you 72
2.10 Exercises . 74
3 Approximation of functions and data 77
3.1 Some representative problems . 77
3.2 Approximation by Taylor’s polynomials 79
3.3 Interpolation 80
3.3.1 Lagrangian polynomial interpolation . 81
3.3.2 Stability of polynomial interpolation . 86
3.3.3 Interpolation at Chebyshev nodes . 87
3.3.4 Barycentric interpolation formula 90
3.3.5 Trigonometric interpolation and FFT 93
3.4 Piecewise linear interpolation . 98
3.5 Approximation by spline functions . 100
3.6 The least-squares method 104
3.7 What we haven’t told you 108
3.8 Exercises . 110
4 Numerical differentiation and integration 113
4.1 Some representative problems . 113
4.2 Approximation of function derivatives 115
4.3 Numerical integration 117
4.3.1 Midpoint formula . 118
4.3.2 Trapezoidal formula . 120
4.3.3 Simpson formula 121
4.4 Interpolatory quadratures 123
4.5 Simpson adaptive formula 127
4.6 Monte Carlo Methods for Numerical Integration . 131
4.7 What we haven’t told you 133
4.8 Exercises . 134
5 Linear systems . 137
5.1 Some representative problems . 137
5.2 Linear system and complexity . 142
5.3 The LU factorization method . 143
5.4 The pivoting technique . 154
5.4.1 The fill-in of a matrix . 157
5.5 How accurate is the solution of a linear system? . 158
5.6 How to solve a tridiagonal system . 162Contents XIII
5.7 Overdetermined systems 163
5.8 What is hidden behind the MATLAB command \ 166
5.9 Iterative methods 168
5.9.1 How to construct an iterative method 169
5.10 Richardson and gradient methods . 174
5.11 The conjugate gradient method . 177
5.12 When should an iterative method be stopped? 180
5.13 To wrap-up: direct or iterative? . 182
5.14 What we haven’t told you 188
5.15 Exercises . 188
6 Eigenvalues and eigenvectors 193
6.1 Some representative problems . 194
6.2 The power method 196
6.2.1 Convergence analysis 199
6.3 Generalization of the power method . 201
6.4 How to compute the shift . 203
6.5 Computation of all the eigenvalues . 206
6.6 What we haven’t told you 209
6.7 Exercises . 210
7 Numerical optimization 213
7.1 Some representative problems . 214
7.2 Unconstrained optimization . 217
7.3 Derivative free methods 219
7.3.1 Golden section and quadratic interpolation
methods . 219
7.3.2 Nelder and Mead method 223
7.4 The Newton method . 227
7.5 Descent (or line search) methods 228
7.5.1 Descent directions . 229
7.5.2 Strategies for choosing the steplength αk . 231
7.5.3 The descent method with Newton’s directions . 237
7.5.4 Descent methods with quasi-Newton directions 238
7.5.5 Gradient and conjugate gradient
descent methods 240
7.6 Trust region methods 242
7.7 The nonlinear least squares method 248
7.7.1 Gauss-Newton method . 249
7.7.2 Levenberg-Marquardt’s method . 252
7.8 Constrained optimization . 253
7.8.1 The penalty method . 259
7.8.2 The augmented Lagrangian method 264
7.9 What we haven’t told you 267
7.10 Exercises . 268XIV Contents
8 Ordinary differential equations 271
8.1 Some representative problems . 271
8.2 The Cauchy problem . 274
8.3 Euler methods 275
8.3.1 Convergence analysis 278
8.4 The Crank-Nicolson method 282
8.5 Zero-stability . 284
8.6 Stability on unbounded intervals 286
8.6.1 The region of absolute stability . 289
8.6.2 Absolute stability controls perturbations . 290
8.6.3 Stepsize adaptivity for the forward Euler
method 297
8.7 High order methods 300
8.8 The predictor-corrector methods 305
8.9 Systems of differential equations . 307
8.10 Some examples 313
8.10.1 The spherical pendulum 313
8.10.2 The three-body problem . 317
8.10.3 Some stiff problems 319
8.11 What we haven’t told you 325
8.12 Exercises . 326
9 Numerical approximation of boundary-value
problems 329
9.1 Some representative problems . 330
9.2 Approximation of boundary-value problems . 332
9.2.1 Finite difference approximation of the
one-dimensional Poisson problem 333
9.2.2 Finite difference approximation of a
convection-dominated problem 336
9.2.3 Finite element approximation of the
one-dimensional Poisson problem 337
9.2.4 Finite difference approximation of the
two-dimensional Poisson problem 341
9.2.5 Consistency and convergence of finite difference
discretization of the Poisson problem 347
9.2.6 Finite difference approximation of the
one-dimensional heat equation 348
9.2.7 Finite element approximation of the
one-dimensional heat equation 352
9.3 Hyperbolic equations: a scalar pure advection
problem 355
9.3.1 Finite difference discretization of the scalar
transport equation . 357Contents XV
9.3.2 Finite difference analysis for the scalar transport
equation . 359
9.3.3 Finite element space discretization of the scalar
advection equation 366
9.4 The wave equation 367
9.4.1 Finite difference approximation of the wave
equation . 369
9.5 What we haven’t told you 373
9.6 Exercises . 374
10 Solutions of the exercises 377
10.1 Chapter 1 377
10.2 Chapter 2 380
10.3 Chapter 3 385
10.4 Chapter 4 389
10.5 Chapter 5 394
10.6 Chapter 6 401
10.7 Chapter 7 404
10.8 Chapter 8 411
10.9 Chapter 9 422
References 429
Index . 435
Index
abs, 8
adaptive
Euler, 287
interpolation, 100
quadrature formulae, 127
Runge-Kutta, 301
algorithm, 28
backward substitutions, 144
forward substitutions, 144
Gauss, 145
H¨orner, 68
LU factorization, 145
Strassen, 29
synthetic division, 68
Thomas, 163, 334
Winograd and Coppersmith, 29
aliasing, 97
angle, 9
anonymous function, 16
ans, 31
arpackc, 210
artificial
diffusion flux, 359
viscosity, 340, 359
average, 111
axis, 203
backtracking strategy, 233
backward difference formula, 302
barycentric interpolation, 90
basis, 4
bicgstab, 179
boundary conditions, 332, 374
Dirichlet, 332
Neumann, 332, 374
boundary-value problem, 186, 329
Butcher array, 300, 301
cancellation, 7
Cauchy point, 245
CFL
condition, 361, 372
number, 361, 362
characteristic
curves, 356
variables, 368
chol, 151
clear, 32
coefficient
amplification, 362
dispersion, 362, 363
dissipation, 362, 363
Fourier, 361
compass, 9
complex, 8
complexity, 29
computational cost, 28
Cramuer rule, 142
LU factorization, 148
cond, 161
condest, 161
condition number, 161, 183, 344
of interpolation, 87
conditions
A. Quarteroni et al., Scientific Computing with MATLAB and Octave,
Texts in Computational Science and Engineering 2,
DOI 10.1007/978-3-642-45367-0, © Springer-Verlag Berlin Heidelberg 2014
435436 Index
Karush–Kuhn–Tucker, 256
Lagrange, 257
LICQ, 256
optimality, 218, 256
Wolfe, 232
strong, 232
conj, 9
consistency, 279, 281, 286, 347
constraint
active, 254
equality, 254
inequality, 254
contour lines, 226, 255, 405, 407, 409
conv, 21
convergence, 26, 65, 286
Euler method, 278, 280
factor
asymptotic, 60
finite differences, 347
Gauss-Seidel method, 173
global, 227
iterative method, 168, 169
Jacobi method, 173
local, 227
of interpolation, 86
order, 26
Newton method, 49
quadratic, 227
secant method, 52
super-linear, 52, 222, 238
power method, 199
Richardson method, 174
cos, 32
cputime, 30
cross, 15
cumtrapz, 121
Dahlquist barrier, 303, 304
dblquad, 134
deconv, 21
deflation, 68, 210
criterion, 69
descent direction, 177, 228
conjugate gradient, 229
gradient, 229
Newton, 229
quasi-Newton, 229
det, 12, 149
diag, 13
diff, 24
differential equation
ordinary, 271
partial, 271
digit
significant, 5
discretization step, 275
disp, 33
dispersion, 361–363
dissipation, 361, 362
domain of dependence, 368
dot, 15
dot operation, 15, 18
eig, 206
eigenvalue, 16, 193
extremal, 197
problem, 193
eigenvector, 16, 193
eigs, 208
end, 30
eps, 5, 6
equation
Burgers, 357
convection-diffusion, 336, 340
heat, 330, 348
hyperbolic, 355
Poisson, 329, 332
pure advection, 355
telegrapher’s, 331
transport, 357, 366
Van der Pol, 322
wave, 330, 367
equations
normal, 107
error
a-priori estimate, 162
absolute, 5, 26
computational, 26
estimator, 27, 50, 62, 127
a-posteriori, 299
increment, 180
interpolation, 83
local truncation, 279, 360
of quadrature, 119
perturbation, 291
relative, 5, 26
roundoff, 4, 5, 8, 26, 155, 158, 282
truncation, 26, 279, 347, 350Index 437
etime, 30
exit, 31
exp, 32
expectation, 131
exponent, 4
extrapolation
Aitken, 64
Richardson, 135
eye, 11
F, 5
factorization
Cholesky, 151, 183, 201
Gauss LU, 146
incomplete Cholesky, 183
incomplete LU, 187
LU, 143, 146, 150, 158, 201
QR, 55, 164, 239
Fast Fourier Transform, 93, 95
inverse, 96
FFT, 93, 95
fft, 95
fftshift, 96
Fibonacci sequence, 34, 40
figure, 203
fill-in, 157
find, 45
finite difference
backward, 116
centered, 116
forward, 115
fix, 379
fixed point, 57
convergence, 61, 65
iteration function, 57
iterations, 57
floating-point
number, 3, 4
operation, 28
system, 5
flux
numerical, 358
fminbnd, 223
fminsearch, 225
fminunc, 239, 247
for, 34
format, 4
formula
Euler, 8
fplot, 17, 99
fsolve, 73, 277
function, 16, 17, 35
convex, 218
cost, 213
derivative, 23
graph of, 17
interpolant, 81
iteration, 57, 62, 64
Lagrange characteristic, 83
Lagrangian, 256
augmented, 264
Lipschitz continuous, 218, 241
Lipschitz-continuous, 275, 285
objective, 213
penalty, 259
primitive, 23
Runge’s, 85, 89
shape, 339
strongly convex, 255
user-defined, 17, 35
function, 35
function handle, 16, 18
funtool, 24
fzero, 20
fzero, 19, 72, 73
gallery, 185
Gauss plane, 10
Gershgorin circles, 203, 204, 211
gmres, 179
golden ratio, 219
gradient, 217
grid, 17
griddata, 109
griddata3, 109
griddatan, 109
help, 32, 37
hold off, 203
hold on, 203
ichol, 183
if, 30
ifft, 96
ilu, 187
imag, 9
image, 208
imread, 208438 Index
Inf, 6
int, 24
interp1, 99
interp1q, 99
interp2, 109
interp3, 109
interpft, 96
interpolant, 81
Hermite, 104
Lagrange, 83
trigonometric, 93
interpolation
adaptive, 100
barycentric formula, 90
composite, 98, 109
convergence, 86
error, 83
Hermite piecewise, 104
Lagrange, 81
Gauss nodes, 87, 88
nodes, 80
piecewise linear, 98, 99
polynomial, 81
rational, 81
spline, 100
stability, 86
trigonometric, 81, 93
inv, 12
Kronecker symbol, 82
Lagrange
multipliers, 243, 256
LAPACK, 167
Laplace operator, 329
law
Fourier, 331
Kirchoff, 273
Ohm, 273
least-squares
method, 104
solution, 164, 166
Lebesgue constant, 87, 89
lexicographic order, 342
linear system, 137
banded, 183
direct methods, 149
methods
direct, 143, 182
iterative, 143, 168, 182
overdetermined, 163
underdetermined, 163
linearly independent system, 14, 201
linspace, 18
load, 32
loglog, 27
Lotka-Volterra equations, 272
lu, 149
m-file, 34
machine epsilon, 5
magic, 188
mantissa, 4
mass-lumping, 355
matlabFunction, 85
matrix, 10
bandwidth of, 152, 183, 184
bidiagonal, 162
companion, 73
complex definite positive, 151
determinant of, 12, 149
diagonal, 13
diagonally dominant, 150, 171, 205
finite difference, 183
full, 185
Hankel, 185
hermitian, 14, 151
Hessian, 217
Hilbert, 159, 161, 179, 180, 185
identity, 11
ill conditioned, 161, 183
inverse, 12
iteration, 169, 174
Jacobian, 322
Leslie, 195, 210
lower triangular, 13
mass, 354
non-symmetric, 186
norm of, 161
orthogonal, 164
pattern of, 152
permutation, 154
product, 11
pseudoinverse, 165
rank of, 164
Riemann, 186
semi positive definite, 151
similar, 206Index 439
singular value decomposition of,
164
sparse, 152, 156, 163, 166, 186, 344
spectrum, 196
splitting of, 169
square, 10
square root of, 400
strictly diagonal dominant, 173
sum, 11
symmetric, 14
symmetric positive definite, 151,
173
transpose of, 14
tridiagonal, 162, 173, 334
unitary, 165
upper triangular, 13
Vandermonde, 147, 185
well conditioned, 161
Wilkinson, 211
mesh, 344
contour, 417
meshgrid, 109, 417
method
θ−, 349
A-stable, 289
Adams-Bashforth, 302
Adams-Moulton, 302
adaptive Newton, 49
Aitken, 63
backward Euler/centered, 359
Bairstow, 73
barrier, 268
BFGS, 238
Bi-CGStab, 179, 187, 258
bisection, 43, 58
Bogacki and Shampine pair, 301
Broyden, 55, 73
conjugate gradient, 177, 231
consistent, 279, 347
Crank-Nicolson, 282, 350, 353
cyclic composite, 304
deflation, 68
Dekker-Brent, 72
derivative free, 218
descent, 218, 228, 235
Dormand-Prince pair, 301
Euler
adaptive forward, 287
backward, 276, 353
forward, 275, 287
forward adaptive, 297
improved, 305
explicit, 276
finite difference, 115, 239, 333, 336,
341, 357
finite element, 186, 337, 340, 366,
373
forward Euler/centered, 358
forward Euler/decentered, 358,
372
Gauss Elimination, 147
Gauss-Newton, 249
damped, 250
Gauss-Seidel, 172, 181
GMRES, 179, 185, 258
golden section, 219
gradient, 175, 231
Heun, 305, 306, 327
implicit, 276
inverse power, 201
iterative, 56
Jacobi, 170, 181
Krylov, 179, 188
Lanczos, 179, 210
Lax-Friedrichs, 358
Lax-Wendroff, 358, 372
Leap-Frog, 311, 370
least-squares, 104
Levenberg-Marquardt, 252
line search, 218, 228
cubic, 234
quadratic, 234
modified Newton, 49
Monte Carlo, 131, 379
multifrontal, 188
multigrid, 188
multistep, 285, 302
M¨ uller, 73
Newmark, 311, 312, 369
Newton, 47, 52, 62
Newton-H¨orner, 70
one-step, 276, 300
power, 197
power with shift, 201
preconditioned conjugate gradient,
178, 183
preconditioned gradient, 175
predictor-corrector, 305440 Index
QR, 206
quadratic interpolation, 222
quasi-Newton, 55, 73
relaxation, 173, 190, 398
Richardson
dynamic, 174
stationary, 174
Runge-Kutta, 300, 305
adaptive, 301
secant, 52, 54
SOR, 190
spectral, 184, 374
Steffensen, 64
successive over-relaxation, 190
trust region, 218, 242, 252
upwind, 358, 372
minimizer
global, 217
constrained, 254
local, 217
constrained, 254
mkpp, 102
model
Leontief, 139
Lotka and Leslie, 195
multipliers, 146, 155
Lagrange, 243
NaN, 7
nargin, 37
nargout, 37
nchoosek, 379
Newton
divided differences, 222
nodes
Chebyshev-Gauss, 88
Chebyshev-Gauss-Lobatto, 87
Gauss-Legendre-Lobatto, 126
norm
of matrix, 161
energy, 174
euclidean, 15
Frobenius, 215
norm, 15
normal equations, 164
number
complex, 8
floating-point, 4
normalized, 3
real, 3
ode, 301
ode113, 307
ode15s, 304
ode15s, 322
ode23, 301, 309
ode23s, 322, 323, 325
ode23tb, 301
ode45, 301, 309
ones, 14
operator
boolean, 32, 33
divergence, 330
Laplace, 329, 342
logical, 32, 33
relational, 32
short-circuit, 33
optimset, 223
order
of convergence, 26
overflow, 6, 7
P´eclet number
global, 336
local, 336
partial derivative, 53, 329
patch, 203
path, 34
pcg, 179
pchip, 104
pde, 346
pdetool, 109, 186, 373
phase plane, 308
pivot, 156
elements, 146
pivoting, 154
by row, 154
complete, 396
total, 156
plot, 18, 27
Pn, 19
point
admissible, 254
critical, 217
regular, 217
stationary, 217
poly, 39, 85
polyder, 22, 86Index 441
polyfit, 22, 83, 106
polyint, 22
polynomial, 20
characteristic, 193, 285
division of, 21, 69
Lagrangian interpolation, 81
Legendre, 125
product of, 21
roots of, 21
Taylor, 23, 79
polyval, 83
ppval, 102
preconditioner, 169, 174, 178
incomplete Cholesky factorization,
183
incomplete LU, 187
pretty, 378
problem
boundary value, 329
Cauchy, 274
convection-diffusion, 336, 340
convection-dominated, 336
Dirichlet, 332
least squares
nonlinear, 248
Neumann, 332
Poisson, 183, 184, 341
stiff, 319
product
inner, 15
scalar, 15
quadl, 126
quadratic programming, 257
quadrature
nodes, 123
weights, 123
quadrature formulae, 117
adaptive Simpson, 127, 128
composite midpoint, 118
composite rectangle, 118
composite Simpson, 121
composite trapezoidal, 120
degree of exactness, 119
error, 120, 122
Gauss, 133
Gauss-Legendre, 125
Gauss-Legendre-Lobatto, 184
interpolatory, 123
midpoint, 118
Newton-Cotes, 133
rectangle, 118
Simpson, 122
trapezoidal, 121
quit, 31
quiver, 15
quiver3, 15
rand, 30
rank, 164
Rayleigh quotient, 193
real, 9
realmax, 6
realmin, 6
region of absolute stability, 289, 303
regression line, 106
relaxation method, 190
residual, 50, 162, 180, 231
preconditioned, 170
relative, 176
return, 36
root
multiple, 19, 21, 49
simple, 19, 48
root condition, 285
roots, 21, 73
roundoff
error, 4, 5, 8, 26, 155, 158
unity, 5
rpmak, 109
rsmak, 109
rule
Armijo, 232
Cramer, 142
Laplace, 12
save, 32
scale
linear, 27, 28
logarithmic, 27
semi-logarithmic, 28
semi-discretization, 348, 353
semilogy, 28
Sequential Quadratic Programming,
268
series
discrete Fourier, 94
shift, 201442 Index
simple, 24, 399
simplex, 223
sin, 32
Singular Value Decomposition, 108,
164, 165
singular values, 165
sparse, 153
spdemos, 109
spdiags, 153, 163
spectral radius, 169
spectrometry, 138
spline, 100
error, 103
natural cubic, 100
not-a-knot condition, 102
spline, 102
spy, 152, 183, 344
sqrt, 32
stability
of interpolation, 86
absolute, 287, 289, 290
asymptotic, 349
of Adams methods, 303
region of absolute, 289, 327
zero-, 284, 286
statistical mean, 131
stencil, 343
step adaptivity, 297
steplength, 275
stopping test, 50, 62, 180
Sturm sequences, 73, 210
sum, 379
svd, 165
svds, 165
syms, 24, 399
system
hyperbolic, 368
linear, 137
nonlinear equations, 52
triangular, 144
underdetermined, 145
taylor, 24
taylortool, 79
theorem
Abel, 67
Cauchy, 68
Descartes, 67
first mean-value, 23
Lax-Richtmyer equivalence, 286
mean-value, 23
of integration, 22
Ostrowski, 59
zeros of continuous functions, 43
time-step, 275
title, 203
toolbox, 2, 32
trapz, 121
tril, 13
triu, 13
UMFPACK, 166, 167, 187
underflow, 6
vander, 147
varargin, 45
variance, 111, 389
vector
column, 10
component of, 15
conjugate transpose, 15
norm, 15
product, 15
row, 10
viscosity, 340, 359
wavelet, 109
wavelets, 109
weak
formulation, 338
solution, 357
while, 34
wilkinson, 211
workspace
workspace base, 32
xlabel, 203
ylabel, 203
zero
multiple, 19
of a function, 19
simple, 19, 48
zeros, 11, 14
كلمة سر فك الضغط : books-world.net
The Unzip Password : books-world.net