INTRODUCTION TO SCIENTIFIC COMPUTING

By STEVEN BROWN

CONTENTS SCIENTI?C COMPUTING INTRODUCTION GENERAL STRATEGY APPROXIMATIONS IN SCIENTI?C COMPUTATION SOURCES OF APPROXIMATION DATA ERROR AND COMPUTATIONAL ERROR TRUNCATION ERROR AND ROUNDING ERROR ABSOLUTE ERROR AND RELATIVE ERROR SENSITIVITY AND CONDITIONING BACKWARD ERROR ANALYSIS STABILITY AND ACCURACY COMPUTER ARITHMETIC FLOATING-POINT NUMBERS NORMALIZATION PROPERTIES OF FLOATING-POINT SYSTEMS ROUNDING MACHINE PRECISION SUBNORMALS AND GRADUAL UNDER?OW EXCEPTIONAL VALUES FLOATING-POINT ARITHMETIC CANCELLATION MATHEMATICAL SOFTWARE MATHEMATICAL SOFTWARE LIBRARIES SCIENTI?C COMPUTING ENVIRONMENTS PRACTICAL ADVICE ON SOFTWARE HISTORICAL NOTES AND FURTHER READING SYSTEMS OF LINEAR EQUATIONS LINEAR SYSTEMS SINGULARITY AND NONSINGULARITY SOLVING LINEAR SYSTEMS TRIANGULAR LINEAR SYSTEMS ELEMENTARY ELIMINATION MATRICES GAUSSIAN ELIMINATION AND LU FACTORIZATION PIVOTING IMPLEMENTATION OF GAUSSIAN ELIMINATION COMPLEXITY OF SOLVING LINEAR SYSTEMS GAUSS-JORDAN ELIMINATION SOLVING MODI?ED PROBLEMS NORMS AND CONDITION NUMBERS VECTOR NORMS MATRIX NORMS CONDITION NUMBER OF A MATRIX ACCURACY OF SOLUTIONS RESIDUAL OF A SOLUTION ESTIMATING ACCURACY IMPROVING ACCURACY SPECIAL TYPES OF LINEAR SYSTEMS SYMMETRIC POSITIVE DE?NITE SYSTEMS SYMMETRIC INDE?NITE SYSTEMS BAND SYSTEMS ITERATIVE METHODS FOR LINEAR SYSTEMS SOFTWARE FOR LINEAR SYSTEMS LINPACK AND LAPACK BASIC LINEAR ALGEBRA SUBPROGRAMS LINEAR LEAST SQUARES DATA FITTING NORMAL EQUATIONS METHOD ORTHOGONALITY AUGMENTED SYSTEM METHOD ORTHOGONALIZATION METHODS TRIANGULAR LEAST SQUARES PROBLEMS ORTHOGONAL TRANSFORMATIONS QR FACTORIZATION HOUSEHOLDER TRANSFORMATIONS GIVENS ROTATIONS GRAM-SCHMIDT ORTHOGONALIZATION RANK DE?CIENCY COLUMN PIVOTING COMPARISON OF METHODS SOFTWARE FOR LINEAR LEAST SQUARES EIGENVALUES AND SINGULAR VALUES EIGENVALUES AND EIGENVECTORS NONUNIQUENESS CHARACTERISTIC POLYNOMIAL PROPERTIES OF EIGENVALUE PROBLEMS SIMILARITY TRANSFORMATIONS CONDITIONING OF EIGENVALUE PROBLEMS METHODS FOR COMPUTING ALL EIGENVALUES JACOBI METHOD FOR SYMMETRIC MATRICES QR ITERATION PRELIMINARY REDUCTION METHODS FOR COMPUTING SELECTED EIGENVALUES POWER METHOD GEOMETRIC INTERPRETATION SHIFTS DE?ATION INVERSE ITERATION RAYLEIGH QUOTIENT RAYLEIGH QUOTIENT ITERATION LANCZOS METHOD FOR SYMMETRIC MATRICES 4 3 10 SPECTRUM-SLICING METHODS FOR SYMMETRIC MATRICES GENERALIZED EIGENVALUE PROBLEMS SINGULAR VALUES SINGULAR VALUE DECOMPOSITION APPLICATIONS OF SVD SOFTWARE FOR EIGENVALUES AND SINGULAR VALUES NONLINEAR EQUATIONS SOLUTIONS OF NONLINEAR EQUATIONS CONVERGENCE RATES OF ITERATIVE METHODS NONLINEAR EQUATIONS IN ONE DIMENSION BISECTION METHOD FIXED-POINT ITERATION NEWTON’S METHOD SECANT METHOD INVERSE INTERPOLATION LINEAR FRACTIONAL INTERPOLATION SAFEGUARDED METHODS ZEROS OF POLYNOMIALS SYSTEMS OF NONLINEAR EQUATIONS SECANT UPDATING METHODS BROYDEN’S METHOD ROBUST NEWTON-LIKE METHODS SOFTWARE FOR NONLINEAR EQUATIONS OPTIMIZATION OPTIMIZATION PROBLEMS LOCAL VERSUS GLOBAL OPTIMIZATION RELATIONSHIP TO NONLINEAR EQUATIONS ONE-DIMENSIONAL OPTIMIZATION GOLDEN SECTION SEARCH SUCCESSIVE PARABOLIC INTERPOLATION MULTIDIMENSIONAL UNCONSTRAINED OPTIMIZATION DIRECT SEARCH METHODS STEEPEST DESCENT METHOD QUASI-NEWTON METHODS CONJUGATE GRADIENT METHOD TRUNCATED NEWTON METHODS NONLINEAR LEAST SQUARES GAUSS-NEWTON METHOD LEVENBERG-MARQUARDT METHOD CONSTRAINED OPTIMIZATION LINEAR PROGRAMMING SOFTWARE FOR OPTIMIZATION INTERPOLATION PURPOSES FOR INTERPOLATION INTERPOLATION VERSUS APPROXIMATION CHOICE OF INTERPOLATING FUNCTION BASIS FUNCTIONS POLYNOMIAL INTERPOLATION EVALUATING POLYNOMIALS LAGRANGE INTERPOLATION NEWTON INTERPOLATION ORTHOGONAL POLYNOMIALS INTERPOLATING A FUNCTION HIGH-DEGREE POLYNOMIAL INTERPOLATION PLACEMENT OF INTERPOLATION POINTS PIECEWISE POLYNOMIAL INTERPOLATION HERMITE CUBIC INTERPOLATION CUBIC SPLINE INTERPOLATION HERMITE CUBIC VERSUS CUBIC SPLINE INTERPOLATION B-SPLINES SOFTWARE FOR INTERPOLATION SOFTWARE FOR SPECIAL FUNCTIONS NUMERICAL INTEGRATION AND DI?ERENTIATION NUMERICAL QUADRATURE QUADRATURE RULES NEWTON-COTES QUADRATURE NEWTON-COTES QUADRATURE RULES METHOD OF UNDETERMINED COE?CIENTS ERROR ESTIMATION POLYNOMIAL DEGREE GAUSSIAN QUADRATURE GAUSSIAN QUADRATURE RULES CHANGE OF INTERVAL GAUSS-KRONROD QUADRATURE RULES COMPOSITE AND ADAPTIVE QUADRATURE COMPOSITE QUADRATURE RULES AUTOMATIC AND ADAPTIVE QUADRATURE OTHER INTEGRATION PROBLEMS INTEGRATING TABULAR DATA IN?NITE INTERVALS DOUBLE INTEGRALS MULTIPLE INTEGRALS INTEGRAL EQUATIONS NUMERICAL DI?ERENTIATION FINITE DI?ERENCE APPROXIMATIONS AUTOMATIC DI?ERENTIATION RICHARDSON EXTRAPOLATION SOFTWARE FOR NUMERICAL INTEGRATION AND DI?ERENTIATION 8 10 HISTORICAL NOTES AND FURTHER READING INITIAL VALUE PROBLEMS FOR ODES ORDINARY DI?ERENTIAL EQUATIONS INITIAL VALUE PROBLEMS HIGHER-ORDER ODES STABLE AND UNSTABLE ODES NUMERICAL SOLUTION OF ODES EULER’S METHOD ACCURACY AND STABILITY ORDER OF ACCURACY STABILITY OF A NUMERICAL METHOD STEPSIZE CONTROL IMPLICIT METHODS STI?DI?ERENTIAL EQUATIONS SURVEY OF NUMERICAL METHODS FOR ODES TAYLOR SERIES METHODS RUNGE-KUTTA METHODS EXTRAPOLATION METHODS MULTISTEP METHODS MULTIVALUE METHODS SOFTWARE FOR ODE INITIAL VALUE PROBLEMS 10 BOUNDARY VALUE PROBLEMS FOR ODES 10 1 BOUNDARY VALUE PROBLEMS 10 2 SHOOTING METHOD 10 3 SUPERPOSITION METHOD 10 4 FINITE DI?ERENCE METHOD 10 5 FINITE ELEMENT METHOD 10 6 EIGENVALUE PROBLEMS 10 7 SOFTWARE FOR ODE BOUNDARY VALUE PROBLEMS 10 8 HISTORICAL NOTES AND FURTHER READING 11 PARTIAL DI?ERENTIAL EQUATIONS 11 1 PARTIAL DI?ERENTIAL EQUATIONS 11 1 1 CLASSI?CATION OF PARTIAL DI?ERENTIAL EQUATIONS 11 2 TIME-DEPENDENT PROBLEMS 11 2 1 SEMIDISCRETE METHODS USING FINITE DI?ERENCES 11 2 2 SEMIDISCRETE METHODS USING FINITE ELEMENTS 11 2 3 FULLY DISCRETE METHODS 11 2 4 IMPLICIT FINITE DI?ERENCE METHODS 11 2 5 HYPERBOLIC VERSUS PARABOLIC PROBLEMS 11 3 TIME-INDEPENDENT PROBLEMS 11 3 1 FINITE DI?ERENCE METHODS 11 3 2 FINITE ELEMENT METHODS 11 4 DIRECT METHODS FOR SPARSE LINEAR SYSTEMS 11 4 1 SPARSE FACTORIZATION METHODS 11 4 2 FAST DIRECT METHODS 11 5 ITERATIVE METHODS FOR LINEAR SYSTEMS 11 5 1 STATIONARY ITERATIVE METHODS 11 5 2 JACOBI METHOD 11 5 3 GAUSS-SEIDEL METHOD 11 5 4 SUCCESSIVE OVER-RELAXATION 11 5 5 CONJUGATE GRADIENT METHOD 11 5 6 RATE OF CONVERGENCE 11 5 7 MULTIGRID METHODS 11 6 COMPARISON OF METHODS 11 7 SOFTWARE FOR PARTIAL DI?ERENTIAL EQUATIONS 11 7 1 SOFTWARE FOR INITIAL VALUE PROBLEMS 11 7 2 SOFTWARE FOR BOUNDARY VALUE PROBLEMS 11 7 3 SOFTWARE FOR SPARSE LINEAR SYSTEMS 11 8 HISTORICAL NOTES AND FURTHER READING 12 FAST FOURIER TRANSFORM 12 1 TRIGONOMETRIC INTERPOLATION 12 1 1 CONTINUOUS FOURIER TRANSFORM 12 1 2 FOURIER SERIES 12 1 3 DISCRETE FOURIER TRANSFORM 12 2 FFT ALGORITHM 12 2 1 LIMITATIONS OF THE FFT 12 3 APPLICATIONS OF DFT 12 3 1 FAST POLYNOMIAL MULTIPLICATION 12 4 WAVELETS 12 5 SOFTWARE FOR FFT 12 6 HISTORICAL NOTES AND FURTHER READING 13 RANDOM NUMBERS AND SIMULATION 13 1 STOCHASTIC SIMULATION 13 2 RANDOMNESS AND RANDOM NUMBERS 13 3 RANDOM NUMBER GENERATORS 13 3 1 CONGRUENTIAL GENERATORS 13 3 2 FIBONACCI GENERATORS 13 3 3 NONUNIFORM DISTRIBUTIONS 13 4 QUASI-RANDOM SEQUENCES 13 5 SOFTWARE FOR GENERATING RANDOM NUMBERS 13 6 HISTORICAL NOTES AND FURTHER READING