Elementary Numerical Analysis – An Algorithmic Approach
Updated with MATLAB
S. D. Conte, Carl de Boor
CONTENTS
Preface to the Classics Edition xiii
Preface xv
Introduction xvii
Errata xix
Chapter 1 Number Systems and Errors 1
1.1 The Representation of Integers 1
1.2 The Representation of Fractions 4
1.3 Floating-Point Arithmetic 7
1.4 Loss of Significance and Error Propagation;
Condition and Instability 12
1.5 Computational Methods for Error Estimation 18
1.6 Some Comments on Convergence of Sequences 19
1.7 Some Mathematical Preliminaries 25
Chapter 2 Interpolation by Polynomial 31
2.1 Polynomial Forms 31
2.2 Existence and Uniqueness of the Interpolating Polynomial 38
2.3 The Divided-Difference Table 41
*2.4 Interpolation at an Increasing Number of
Interpolation Points 46
2.5 The Error of the Interpolating Polynomial 51
2.6 Interpolation in a Function Table Based on Equally
Spaced Points 55
*2.7 The Divided Difference as a Function of Its Arguments
and Osculatory Interpolation 62
·Sections marked with an asterisk may be omitted without loss of continuity.
ixx CONTENTS
Chapter 3 The Solution of Nonlinear Equations 72
3.1 A Survey of Iterative Methods 74
3.2 Fortran Programs for Some Iterative Methods 81
3.3 Fixed-Point Iteration 88
3.4 Convergence Acceleration for Fixed-Point Iteration 95
·3.5 Convergence of the Newton and Secant Methods 100
3.6 Polynomial Equations: Real Roots 110
·3.7 Complex Roots and Muller’s Method 120
Chapter 4 Matrices and Systems of Linear Equations 128
4.1 Properties of Matrices 128
4.2 The Solution of Linear Systems by Elimination 147
4.3 The Pivoting Strategy 157
4.4 The Triangular Factorization 160
4.5 Error and Residual of an Approximate Solution; Norms 169
4.6 Backward-Error Analysis and Iterative Improvement 177
·4.7 Determinants 185
*4.8 The Eigenvalue Problem 189
Olapter ·S Systems of Equations and Unconstrained
Optimization 208
*5.1 Optimization and Steepest Descent 209
·5.2 Newton’s Method 216
·5.3 Fixed-Point Iteration and Relaxation Methods 223
Chapter 6 Approximation 235
6.1 Uniform Approximation by Polynomials 235
6.2 Data Fitting 245
·6.3 Orthogonal Polynomials 251
·6.4 Least..Squares Approximation by Polynomials 259
·6.5 Approximation by Trigonometric Polynomials 268
·6.6 Fast Fourier Transforms 277
6.7 Piecewise-Polynomial Approximation 284
Chapter 7 Differentiation and Integration 294
7.1 Numerical Differentiation 295
7.2 Numerical Integration: Some Basic Rules 303
7.3 Numerical Integration: Gaussian Rules 311
7.4 Numerical Integration: Composite Rules 319
7.5 Adaptive Quadrature 328
·7.6 Extrapolation to the Limit 333
·7.7 Romberg Integration 340Chapter 8
The Solution of Differential Equations
Mathematical Preliminaries
Simple Difference Equations
Numerical Integration by Taylor Series
Error Estimates and Convergence of Euler’s Method
Runge-Kutta Methods
Step-Size Control with Runge-Kutta Methods
Multistep Formulas
Predictor-Corrector Methods
The Adams-Moulton Method
Stability of Numerical Methods
Round-off-Error Propagation and Control
Systems of Differential Equations
Stiff Differential Equations
Boundary Value Problems
Finite Difference Methods
Shooting Methods
Collocation Methods
Appendix: Subroutine Libraries
Appendix: New MATLAB Programs
References
Index
CONTENTS xi
INDEX
Acceleration, 95ff.
(See also Extrapolation to the limit)
Adams-Bashforth method, 373-376
predictor form, 383
program, 377
stability of, 392-394
Adams-Moulton method, 382-388
program, 387
stability of ~ 394
for systems, 399
Adaptive quadrature, 328ff.
Aitken’s algorithm for polynomial interpolation,
50
Aitken’s ~2_process, 98, 196,333
algorithm, 98
Aliasing, 273
Alternation in sign, 237
Analytic substitution, 294ff., 339
Angular frequency, 271
Approximation, 235ff.
Chebyshev, 235- 244
least-squares (see Least-squares
approximation)
uniform, 235-244
Back-substitution, 148, 156, 163
algorithm, 148, 163
program, 164
Backward error analysis, 9-11, 19, 160,
179-181
Base of a number system, 1-4
Basis for n-vectors, 140, 141, 196
Bessel interpolation, 288
Bessel’s function, zeros of, 124-125, 127
Binary search, 87
Binary system, 1-3
Binomial coefficient, 57
Binomial function, 57, 373
Binomial theorem, 58
Bisection method, 74-75, 81-84
algorithm, 75
program, 81 – 84
Boundary value problems, 406-419
collocation method for, 416-419
finite difference methods for,
406-412
second-order equation, 407ff.
shooting methods for, 412-416
Breakpoints of a piecewise-polynomial function,
284,319
Broken-line interpolation, 284- 285
Broyden’s method, 222
Central-difference formula, 298, 407
Chain rule, 28
Characteristic equation:
of a difference equation, 350~ 391
of a differential equation, 348, 392, 394
of a matrix, 201
Characteristic polynomial of a matrix, 202
Chebyshev approximation (see Approximation,
uniform)
Chebyshev points, 54, 242-244, 318
Chebyshev polynomials, 32, 239-241,
255-256, 293, 317, 354
nested multiplication for, 258
451452 INDEX
Choleski’s method, 160, 169
Chopping, 8
Compact schemes, 160, 169
Composite rules for numerical integration,
319ff.
Condition, 14-15 .
Condition number, 175, 177
Continuation method, 218
Convergence:
geometric, 22
linear, 95
order of, 102
quadratic, l00ff.
of a sequence, 19ff.
of a vector sequence, 191, 223
Convergence acceleration, 95ff.
(See also Extrapolation to the limit)
Conversion:
binary to decimal, 2, 6, 113
decimal to binary, 3, 6
Corrected trapezoid rule, 309, 310, 321, 323
program, 324
Corrector formulas, 379-388
Adams-Moulton, 382-384
Milne’s, 385
Cramer’s rule, 144, 187
Critical point, 209
Cubic spline, 289, 302
interpolation, 289-293
Damped Newton’s method, 219-220
Damping for convergence encouragement,
219
Data fitting, 245ff.
Decimal system, 1
Deflation, 117-119, 124, 203
for power method, 207
Degree of polynomial, 29, 32
Descartes’ rule of sign, 110- 11C 119
Descent direction, 213
Determinants, 144, 185ff., 201ff.
Diagonally dominant (see Matrix)
Difference equations, 349ff., 360, 361, 390,
391,392
initial value, 351
linear, 349
Difference operators, 61
Differential equations, 346ff.
basic notions, 346-348
boundary value problems, 406-419
Euler’s method, 356ff.
initial value problems, 347, 354
Differential equations:
linear, with constant coefficients t 347- 349
multistep methods, 373ff.
Runge-Kutta methods, 362ff.
stiff, 401ff.
systems of, 398- 401
Taylor’s algorithm, 354-359
Differential remainder for Taylor’s formula,
28
Differentiation:
numerical, 290, 295-303
symbolic, 356
Direct methods for solving linear systems,
147-185, 209
Discrete Fourier transform, 278
Discretization error, 300, 359, 361 t 389
dist, 236
Divided difference, 40, 41ff., 62ff., 79, 236
table, 41ff.
Double precision, 7, 11, 18
accumulation, 396
partial, 396
of scalar products, 183
DVERK subroutine for differential equations,
370-372, 400-401
Eigenvalues, 189ff.
program for, 194
Eigenvectors, 189, 191, 194
complete set of, 196
EISPACK, 422
Equivalence of linear systems, 149
Error, 12ff.
Euler’s formula, 30, 269
Euler’s method, 356, 359-362, 373, 379,
395
Exactness of a rule, 311
Exponent of a floating-point number, 7
Exponential growth, 390, 391
Extrapolation, 54
Extrapolation to the limit, 333ff., 366, 410
algorithm, 338-339
(See also Aitken ‘8 ~2_process)
Factorization of a matrix, 160-166, 169, 187,
229
False position method (see Regula falsi)
Fast Fourier transform, 277 – 284
program, 281-282
Finite-difference methods, 406-411
Fixed point, 88Fixed-point iteration, 79, 88-99, 108, 223ff.,
381
algorithm, 89
for linear systems, 224 – 232
algorithm, 227
for systems, 223 – 234
Floating-point arithmetic, 7ff.
Forward difference:
formula, 297
operator ~, 56ff., 373
table, 58-61
Forward-shift operator, 57
Fourier coefficients, 269
Fourier series, 269ff.
Fourier transform:
discrete, 278
fast, 277 – 284
Fraction:
binary, 5
decimal, 4
Fractional part of a number, 4
Fundamental theorem of algebra, 29, 202
Gauss elimination, 145, 149ff.
algorithm, 152-153
program, 164- 166
for tridiagonal systems, 153- 156
program, 155
Gauss-Seidel iteration, 230-232, 234, 412
algorithm, 230
Gaussian rules for numerical integration,
311-319,325-327
Geometric series, 22
Gershgorin’s disks, 200
Gradient ~ 209
Gram-Schmidt algorithm, 250
Hermite interpolation, 286
Hermite polynomials, 256, 318
Hessenberg matrix, 197
Homogeneous difference equation, 350-352
Homogeneous differential equation,
347-348
Homogeneous linear system, 135-140
Homer’s method (see Nested multiplication)
Householder reflections, ]97
Ill-conditioned, 181, 249
IMSL (International Mathematical and
Statistical Library), 370, 421
INDEX 453
Initial-value problem, 347
numerical solution of, 354-405
Inner product (see Scalar product)
Instability, 15-17, 117,376,385,389-394,
402
Integral part of a number, 4
Integral remainder for Taylor’s formula,
27
Integration, 303 – 345
composite rules, 309, 319ff.
corrected trapezoid rule, 309, 321
Gaussian rules, 311 – 318
program for weights and nodes, 316
midpoint rule, 305, 321
rectangle rule, 305, 320
Romberg rule, 340-345
Simpson’s rule, 307, 321, 385
trapezoid rule, 305, 321
Intermediate-value theorem for continuous
functions, 25, 74, 89
Interpolating polynomial, 38-71, 295
difference formula, 55 – 62
error, 51ff.
Lagrange formula, 38, 39-41
Newton formula, 40,41
uniqueness of, 38
Interpolation:
broken-line, 284-285
in a function table, 46-50, 55-61
global,293
iterated linear, 50
by polynomials, 31ff.
by trigonometric polynomials,
275-276
linear, 39
local,293
optimal, 276
osculatory, 63, 67, 68, 286
quadratic, 120, 202, 213-214, 416
Interval arithmetic, 18
Inverse of a matrix, 133, 166
approximate, 225
calculation of, 166-168
program, 167
Inverse interpolation, 51
Inverse iteration. 193- 195
Iterated linear interpolation, 50
Iteration function for fixed-point iteration, 88,
223
Iteration methods for solving linear systems,
144, 209, 223ff.
Iterative improvement, 183-184, 229
algorithm, 183454 INDEX
Jacobi iteration, 226, 229, 234
Jacobi polynomials, 317
Jacobian (matrix), 214, 216, 404
Kronecker symbol 8;j, 201
Lagrange form, 38
Lagrange formula for interpolating polynomial,
39,295,312
Lagrange polynomials, 38, 147, 259, 275, 295
Laguerre polynomials, 256, 318
Least-squares approximation, 166, 215,
247-25C 259-267
by polynomials, 259ff., 302
program, 263-264
by trigonometric polynomials, 275
Lebesque function, 243, 244
Legendre polynomials, 255, 259, 260, 315
Leibniz formula for divided difference of a
product, 71
Level line, 212
Linear combination, 134, 347
Linear convergence, 95, 98
Linear independence, 140, 347, 417
Linear operation, 294
Linear system, 128, 136, 144
numerical solution of, I47ff.
Line search, 213-214, 215
LINPACK,422
Local discretization error, 355, 359
Loss of significance, 12-14,32, 116, 121, 265,
300
Lower bound for dist 00 (j, 1TnJ, 236 – 237, 245
Lower-triangular, 131
Maehly’s method, 119
Mantissa of a floating-point number, 7
Matrix, 129ff.
addition, 133
approximate inverse, 225
bandtype of banded, 350
conjugate transposed, 142
dense, 145
diagonal, 131
diagonally dominant, 184, 201, 217, 225,
230,231,234,250,289
equality, 129
general properties, 128- 144
Hermitian, 142, 206
Hessenberg , 197
Householder reflection, 197
Matrix:
identity, 132
inverse, 133, 166-168
invertible, 132, 152, 168, 178, 185, 188 t 229
multiplication, 130
norm, 172
null, 134
permutation, 143, 186
positive definite, 159, 169, 231
similar t 196
sparse, 145, 231
square, 129, 135
symmetric, 141, 198, 206
trace, 146
transpose, 141
triangular, 131, 147, 168, 178, 186,234
triangular factorization, 160- 166
tridiagonal, 153-156, 168, 188, 198,
204-206,217,230
unitary, 197
Matrix-updating methods for solving systems of
equations, 221 – 222
Mean-value theorem:
for derivatives, 26, 52,79,92,96,102,298,
360
for integrals, 26, 304, 314, 320
Midpoint rule, 305
composite, 321, 341
Milne’s method, 378, 385, 389
Minimax approximation (see Approximation,
uniform)
Minor of a matrix, 188
Modified regula falsi, 77,78, 84-86, 205
algorithm, 77
program, 84 – 86
Muller’s method, 12Off., 202-204
Multiplicity of a zero, 36
Multistep methods, 373ff.
Murnaghan-Wrench algorithm, 241
Nested form of a polynomial, 33
Nested multiplication, 112
for Chebyshev polynomials, 258
in fast Fourier transform, 279
for Newton form, 33, 112
for orthogonal polynomials, 257
for series, 37
Neville’s algorithm, 50
Newton backward-difference formula, 62, 373,
382
Newton form of a polynomial, 32ff.
Newton formula for the interpolating
polynomial, 40-41Newton formula for the interpolating
polynomial:
algorithm for calculation of coefficients, 44
program, 45, 68-69
Newton forward-difference formula, 57
Newton’s method, 79, 100-102, 104-106,
108, 113ff., 241, 244, 404
algorithm, 79
for finding real zeros of polynomials, 113
program, 115
for systems, 216-222, 223, 224
algorithm, 217
damped, 218-220
modified, 221
quasi-, 223
Node of a rule, 295
Noise, 295
Norm, 17Off.
Euclidean, 171
function, 235
matrix, 172
max, 171
vector, 171
Normal equations for least-squares problem,
215,248-251, 260
Normalized floating-point number, 7
Numerical differentiation, 290, 295- 303
Numerical instability (see Instability)
Numerical integration (see Integration)
Numerical quadrature (see Integration)
Octal system, 3
One-step methods, 355
Optimization, 209ff.
Optimum step size:
in differentiation, 301
in solving differential equations, 366-372,
385,396
Order:
of convergence, 20-24, 102
of a root, 36, 109, 110
symbol (I) ( ),20-24, 163, 192,202,221,
337ff., 353ff., 361,363-365, 367,390,
393
symbolo( ), 20-24, 98, 334ff.
of a trigonometric polynomial, 268
Orthogonal functions, 250, 252, 270, 418
Orthogonal polynomials, 251ft., 313
generation of, 261- 265
Orthogonal projection, 248
Osculatory interpolation, 62ff., 308
program, 68-69
Overflow, 8
INDEX 455
Parseval’s relation, 270
Partial double precision accumulation t 396
Partial pivoting, 159
Permutation, 143
Piecewise-cubic interpolation, 285ff.
programs, 285 t 287, 290
Piecewise-parabolic, 293
Piecewise-polynomial functions, 284ff., 319,
418
Piecewise-polynomial interpolation, 284ff.
Pivotal equation in elimination, 151
Pivoting strategy in elimination, 157, 180
. Polar form of a complex number, 270, 277,
351
Polynomial equations, 11Off.
complex roots, 12Off.
real roots t 11Off.
Polynomial forms:
Lagrange, 38
nested, 33
Newton, 32ff.
power, 32
shifted power, 32
Polynomial interpolation (see Interpolating
polynomial)
Polynomials:
algebraic, 31ff.
trigonometric, 268ff.
PORT, 421
Power form of a polynomial, 32
Power method, 192-196
Power spectrum, 271
Predictor-corrector methods, 379ff.
Propagation of errors, 14, 395
Quadratic convergence, l00ff.
Quadratic formula, 13-14
Quotient polynomial, 35
QR method, 199-200
Rayleigh quotient, 201
Real numbers, 24
Rectangle rule, 305
composite, 320
Reduced or deflated polynomial, 117
Regula falsi, 76
modified (see Modified regula falsi)
Relative error, 12
Relaxation, 232-233
Remez algorithm, 241
Residual, 169
Rolle’s theorem, 26, 52, 74456 INDEX
Romberg integration, 340-345
program, 343-344
Round-off error, 8
in differentiation, 300-302
in integration, 322
propagation of, 9ff., 12ff., 395ff.
in solving differential equations, 395-398
in solving equations, 83, 87, 116-117
in solving linear systems, 157, 178- 185
Rounding, 8
Rule, 295
Runge-Kutta methods, 362ff.
Fehlberg, 369- 370
order 2, 363-364
order 4, 364
Verner, 370
Sampling frequency, 272
Scalar (or inner) product, 142, 143
of functions, 251, 270, 273
Schur’s theorem, 197, 234
Secant method, 78-79, 102-104, 106-109,
412
algorithm, 78
Self-starting, 365, 376
Sequence, 20
Series summation, 37
Shooting methods, 412ff.
Significant-digit arithmetic, 18
Significant digits, 12
Similarity transformation, 196ff.
into upper Hessenberg form, 197- 199
algorithm, 199
Simpson’s rule, 307, 317, 318, 329-332, 385
composite, 320
program, 325
Simultaneous displacement (see Jacobi iteration)
Single precision, 7
Smoothing, 271
SOR, 231
Spectral radius, 228
Spectrum:
of a matrix (see Eigenvalues)
of a periodic function, 271
Spline, 289-293
Stability (see Instability)
Stable:
absolutely, 394
relatively, 394
strongly, 391, 392
weakly, 393
Steepest descent, 2 IOff.
algorithm, 211
Steffensen iteration, 98, 108
algorithm, 98
Step-size control, 366, 384, 394
Sturm sequence, 205
Successive displacement (see Gauss-Seidel
iteration)
Successive overrelaxation (SOR), 231
Synthetic division by a linear polynomial, 35
Tabulated function, 55
Taylor polynomial, 37,63,64
Taylor series, truncated, 27, 32, 100, 336, 353,
354, 357, 359, 390
for functions of several variables, 29, 216~
363,414
Taylor’s algorithm, 354ff., 362, 366
Taylor’s formula with (integral) remainder, 27
(See also Taylor series, truncated)
Termination criterion, 81, 85, 122, 194, 227
Three-term recurrence relation, 254
Total pivoting, 159
Trace of a matrix, 146
Trapezoid rule, 272, 305, 317, 340
composite, 321
corrected (see Corrected trapezoid rule)
program, 323
Triangle inequality, 171, 176
Triangular factorization, l6Off.
program, 165- 166
Tridiagonal matrix (see Matrix, tridiagonal)
Trigonometric polynomial. 268ff.
Truncation error (see Discretization error)
Two-point boundary value problems, 406ff.
Underflow, 8
Unit roundoff, 9
Unit vector, 135
Unstable (see Instability)
Upper-triangular, 131, 147- 149
Vandermonde matrix, 147
Vector, 129
Wagon wheels, 274
Waltz, 106
Wavelength, 271
Wronskian, 347
Zeitgeist, 432
كلمة سر فك الضغط : books-world.net
The Unzip Password : books-world.net
تحميل
يجب عليك التسجيل في الموقع لكي تتمكن من التحميل
تسجيل | تسجيل الدخول