NUMERICAL ANALYSIS

By V. LAANI

CONTENTS PART I GETTING STARTED FOUNDATIONS OF MATRIX ANALYSIS VECTOR SPACES MATRICES OPERATIONS WITH MATRICES INVERSE OF A MATRIX MATRICES AND LINEAR MAPPINGS OPERATIONS WITH BLOCK-PARTITIONED MATRICES TRACE AND DETERMINANT OF A MATRIX RANK AND KERNEL OF A MATRIX SPECIAL MATRICES BLOCK DIAGONAL MATRICES TRAPEZOIDAL AND TRIANGULAR MATRICES BANDED MATRICES EIGENVALUES AND EIGENVECTORS SIMILARITY TRANSFORMATIONS THE SINGULAR VALUE DECOMPOSITION (SVD) SCALAR PRODUCT AND NORMS IN VECTOR SPACES MATRIX NORMS RELATION BETWEEN NORMS AND THE SPECTRAL RADIUS OF A MATRIX SEQUENCES AND SERIES OF MATRICES POSITIVE DE?NITE, DIAGONALLY DOMINANT AND M-MATRICES EXERCISES PRINCIPLES OF NUMERICAL MATHEMATICS WELL-POSEDNESS AND CONDITION NUMBER OF A PROBLEM STABILITY OF NUMERICAL METHODS RELATIONS BETWEEN STABILITY AND CONVERGENCE A PRIORI AND A POSTERIORI ANALYSIS SOURCES OF ERROR IN COMPUTATIONAL MODELS MACHINE REPRESENTATION OF NUMBERS THE POSITIONAL SYSTEM THE FLOATING-POINT NUMBER SYSTEM DISTRIBUTION OF FLOATING-POINT NUMBERS IEC/IEEE ARITHMETIC ROUNDING OF A REAL NUMBER IN ITS MACHINE REPRESENTATION MACHINE FLOATING-POINT OPERATIONS PART II NUMERICAL LINEAR ALGEBRA DIRECT METHODS FOR THE SOLUTION OF LINEAR SYSTEMS STABILITY ANALYSIS OF LINEAR SYSTEMS THE CONDITION NUMBER OF A MATRIX FORWARD A PRIORI ANALYSIS BACKWARD A PRIORI ANALYSIS A POSTERIORI ANALYSIS SOLUTION OF TRIANGULAR SYSTEMS IMPLEMENTATION OF SUBSTITUTION METHODS ROUNDING ERROR ANALYSIS INVERSE OF A TRIANGULAR MATRIX THE GAUSSIAN ELIMINATION METHOD (GEM) AND LU FACTORIZATION GEM AS A FACTORIZATION METHOD THE E?ECT OF ROUNDING ERRORS IMPLEMENTATION OF LU FACTORIZATION COMPACT FORMS OF FACTORIZATION OTHER TYPES OF FACTORIZATION LDMT FACTORIZATION SYMMETRIC AND POSITIVE DE?NITE MATRICES: THE CHOLESKY FACTORIZATION RECTANGULAR MATRICES: THE QR FACTORIZATION PIVOTING COMPUTING THE INVERSE OF A MATRIX BANDED SYSTEMS TRIDIAGONAL MATRICES IMPLEMENTATION ISSUES BLOCK SYSTEMS BLOCK LU FACTORIZATION INVERSE OF A BLOCK-PARTITIONED MATRIX BLOCK TRIDIAGONAL SYSTEMS SPARSE MATRICES THE CUTHILL-MCKEE ALGORITHM DECOMPOSITION INTO SUBSTRUCTURES NESTED DISSECTION ACCURACY OF THE SOLUTION ACHIEVED USING GEM AN APPROXIMATE COMPUTATION OF K(A) IMPROVING THE ACCURACY OF GEM SCALING ITERATIVE RE?NEMENT UNDETERMINED SYSTEMS APPLICATIONS NODAL ANALYSIS OF A STRUCTURED FRAME REGULARIZATION OF A TRIANGULAR GRID ITERATIVE METHODS FOR SOLVING LINEAR SYSTEMS ON THE CONVERGENCE OF ITERATIVE METHODS LINEAR ITERATIVE METHODS JACOBI, GAUSS-SEIDEL AND RELAXATION METHODS CONVERGENCE RESULTS FOR JACOBI AND GAUSS-SEIDEL METHODS CONVERGENCE RESULTS FOR THE RELAXATION METHOD A PRIORI FORWARD ANALYSIS BLOCK MATRICES SYMMETRIC FORM OF THE GAUSS-SEIDEL AND SOR METHODS STATIONARY AND NONSTATIONARY ITERATIVE METHODS CONVERGENCE ANALYSIS OF THE RICHARDSON METHOD PRECONDITIONING MATRICES THE GRADIENT METHOD THE CONJUGATE GRADIENT METHOD THE PRECONDITIONED CONJUGATE GRADIENT METHOD THE ALTERNATING-DIRECTION METHOD METHODS BASED ON KRYLOV SUBSPACE ITERATIONS THE ARNOLDI METHOD FOR LINEAR SYSTEMS THE GMRES METHOD THE LANCZOS METHOD FOR SYMMETRIC SYSTEMS THE LANCZOS METHOD FOR UNSYMMETRIC SYSTEMS STOPPING CRITERIA A STOPPING TEST BASED ON THE INCREMENT A STOPPING TEST BASED ON THE RESIDUAL ANALYSIS OF AN ELECTRIC NETWORK FINITE DI?ERENCE ANALYSIS OF BEAM BENDING APPROXIMATION OF EIGENVALUES AND EIGENVECTORS GEOMETRICAL LOCATION OF THE EIGENVALUES STABILITY AND CONDITIONING ANALYSIS A PRIORI ESTIMATES A POSTERIORI ESTIMATES THE POWER METHOD APPROXIMATION OF THE EIGENVALUE OF LARGEST MODULE INVERSE ITERATION THE QR ITERATION THE BASIC QR ITERATION THE QR METHOD FOR MATRICES IN HESSENBERG FORM HOUSEHOLDER AND GIVENS TRANSFORMATION MATRICES REDUCING A MATRIX IN HESSENBERG FORM QR FACTORIZATION OF A MATRIX IN HESSENBERG FORM THE BASIC QR ITERATION STARTING FROM UPPER HESSENBERG FORM IMPLEMENTATION OF TRANSFORMATION MATRICES THE QR ITERATION WITH SHIFTING TECHNIQUES THE QR METHOD WITH SINGLE SHIFT THE QR METHOD WITH DOUBLE SHIFT COMPUTING THE EIGENVECTORS AND THE SVD OF A MATRIX THE HESSENBERG INVERSE ITERATION COMPUTING THE EIGENVECTORS FROM THE SCHUR FORM OF A MATRIX APPROXIMATE COMPUTATION OF THE SVD OF A MATRIX THE GENERALIZED EIGENVALUE PROBLEM COMPUTING THE GENERALIZED REAL SCHUR FORM GENERALIZED REAL SCHUR FORM OF SYMMETRIC-DE?NITE PENCILS METHODS FOR EIGENVALUES OF SYMMETRIC MATRICES THE JACOBI METHOD THE METHOD OF STURM SEQUENCES THE LANCZOS METHOD ANALYSIS OF THE BUCKLING OF A BEAM FREE DYNAMIC VIBRATION OF A BRIDGE PART III AROUND FUNCTIONS AND FUNCTIONALS ROOT?NDING FOR NONLINEAR EQUATIONS CONDITIONING OF A NONLINEAR EQUATION A GEOMETRIC APPROACH TO ROOT?NDING THE BISECTION METHOD THE METHODS OF CHORD, SECANT AND REGULA FALSI AND NEWTON’S METHOD THE DEKKER-BRENT METHOD FIXED-POINT ITERATIONS FOR NONLINEAR EQUATIONS CONVERGENCE RESULTS FOR SOME FIXED-POINT METHODS ZEROS OF ALGEBRAIC EQUATIONS THE HORNER METHOD AND DE?ATION THE NEWTON-HORNER METHOD THE MULLER METHOD POST-PROCESSING TECHNIQUES FOR ITERATIVE METHODS AITKEN’S ACCELERATION TECHNIQUES FOR MULTIPLE ROOTS ANALYSIS OF THE STATE EQUATION FOR A REAL GAS ANALYSIS OF A NONLINEAR ELECTRICAL CIRCUIT NONLINEAR SYSTEMS AND NUMERICAL OPTIMIZATION SOLUTION OF SYSTEMS OF NONLINEAR EQUATIONS NEWTON’S METHOD AND ITS VARIANTS MODI?ED NEWTON’S METHODS QUASI-NEWTON METHODS SECANT-LIKE METHODS FIXED-POINT METHODS UNCONSTRAINED OPTIMIZATION DIRECT SEARCH METHODS DESCENT METHODS LINE SEARCH TECHNIQUES DESCENT METHODS FOR QUADRATIC FUNCTIONS NEWTON-LIKE METHODS FOR FUNCTION MINIMIZATION SECANT-LIKE METHODS CONSTRAINED OPTIMIZATION KUHN-TUCKER NECESSARY CONDITIONS FOR NONLINEAR PROGRAMMING THE PENALTY METHOD THE METHOD OF LAGRANGE MULTIPLIERS SOLUTION OF A NONLINEAR SYSTEM ARISING FROM SEMICONDUCTOR DEVICE SIMULATION NONLINEAR REGULARIZATION OF A DISCRETIZATION GRID POLYNOMIAL INTERPOLATION THE INTERPOLATION ERROR DRAWBACKS OF POLYNOMIAL INTERPOLATION ON EQUALLY SPACED NODES AND RUNGE’S COUNTEREXAMPLE STABILITY OF POLYNOMIAL INTERPOLATION NEWTON FORM OF THE INTERPOLATING POLYNOMIAL SOME PROPERTIES OF NEWTON DIVIDED DI?ERENCES THE INTERPOLATION ERROR USING DIVIDED DI?ERENCES BARYCENTRIC LAGRANGE INTERPOLATION PIECEWISE LAGRANGE INTERPOLATION HERMITE-BIRKO?INTERPOLATION EXTENSION TO THE TWO-DIMENSIONAL CASE PIECEWISE POLYNOMIAL INTERPOLATION APPROXIMATION BY SPLINES INTERPOLATORY CUBIC SPLINES B-SPLINES SPLINES IN PARAMETRIC FORM B´EZIER CURVES AND PARAMETRIC B-SPLINES FINITE ELEMENT ANALYSIS OF A CLAMPED BEAM GEOMETRIC RECONSTRUCTION BASED ON COMPUTER TOMOGRAPHIES NUMERICAL INTEGRATION QUADRATURE FORMULAE INTERPOLATORY QUADRATURES THE MIDPOINT OR RECTANGLE FORMULA THE TRAPEZOIDAL FORMULA THE CAVALIERI-SIMPSON FORMULA NEWTON-COTES FORMULAE COMPOSITE NEWTON-COTES FORMULAE HERMITE QUADRATURE FORMULAE RICHARDSON EXTRAPOLATION ROMBERG INTEGRATION AUTOMATIC INTEGRATION NONADAPTIVE INTEGRATION ALGORITHMS ADAPTIVE INTEGRATION ALGORITHMS SINGULAR INTEGRALS INTEGRALS OF FUNCTIONS WITH FINITE JUMP DISCONTINUITIES INTEGRALS OF IN?NITE FUNCTIONS INTEGRALS OVER UNBOUNDED INTERVALS MULTIDIMENSIONAL NUMERICAL INTEGRATION THE METHOD OF REDUCTION FORMULA TWO-DIMENSIONAL COMPOSITE QUADRATURES MONTE CARLO METHODS FOR NUMERICAL INTEGRATION COMPUTATION OF AN ELLIPSOID SURFACE COMPUTATION OF THE WIND ACTION ON A SAILBOAT MAST PART IV TRANSFORMS, DI?ERENTIATION AND PROBLEM DISCRETIZATION ORTHOGONAL POLYNOMIALS IN APPROXIMATION THEORY APPROXIMATION OF FUNCTIONS BY GENERALIZED FOURIER SERIES THE CHEBYSHEV POLYNOMIALS THE LEGENDRE POLYNOMIALS GAUSSIAN INTEGRATION AND INTERPOLATION CHEBYSHEV INTEGRATION AND INTERPOLATION LEGENDRE INTEGRATION AND INTERPOLATION GAUSSIAN INTEGRATION OVER UNBOUNDED INTERVALS PROGRAMS FOR THE IMPLEMENTATION OF GAUSSIAN QUADRATURES APPROXIMATION OF A FUNCTION IN THE LEAST-SQUARES SENSE DISCRETE LEAST-SQUARES APPROXIMATION THE POLYNOMIAL OF BEST APPROXIMATION FOURIER TRIGONOMETRIC POLYNOMIALS THE GIBBS PHENOMENON THE FAST FOURIER TRANSFORM 10 10 APPROXIMATION OF FUNCTION DERIVATIVES 10 10 1 CLASSICAL FINITE DI?ERENCE METHODS 10 10 2 COMPACT FINITE DI?ERENCES 10 10 3 PSEUDO-SPECTRAL DERIVATIVE 10 11 TRANSFORMS AND THEIR APPLICATIONS 10 11 1 THE FOURIER TRANSFORM 10 11 2 (PHYSICAL) LINEAR SYSTEMS AND FOURIER TRANSFORM 10 11 3 THE LAPLACE TRANSFORM 10 11 4 THE Z-TRANSFORM 10 12 THE WAVELET TRANSFORM 10 12 1 THE CONTINUOUS WAVELET TRANSFORM 10 12 2 DISCRETE AND ORTHONORMAL WAVELETS 10 13 APPLICATIONS 10 13 1 NUMERICAL COMPUTATION OF BLACKBODY RADIATION 10 13 2 NUMERICAL SOLUTION OF SCHR¨ODINGER EQUATION 10 14 EXERCISES NUMERICAL SOLUTION OF ORDINARY DI?ERENTIAL EQUATIONS THE CAUCHY PROBLEM ONE-STEP NUMERICAL METHODS ANALYSIS OF ONE-STEP METHODS THE ZERO-STABILITY CONVERGENCE ANALYSIS THE ABSOLUTE STABILITY DI?ERENCE EQUATIONS MULTISTEP METHODS ADAMS METHODS BDF METHODS ANALYSIS OF MULTISTEP METHODS CONSISTENCY THE ROOT CONDITIONS STABILITY AND CONVERGENCE ANALYSIS FOR MULTISTEP METHODS ABSOLUTE STABILITY OF MULTISTEP METHODS PREDICTOR-CORRECTOR METHODS RUNGE-KUTTA (RK) METHODS DERIVATION OF AN EXPLICIT RK METHOD STEPSIZE ADAPTIVITY FOR RK METHODS IMPLICIT RK METHODS REGIONS OF ABSOLUTE STABILITY FOR RK METHODS SYSTEMS OF ODES 11 10 STI?PROBLEMS 11 11 APPLICATIONS 11 11 1 ANALYSIS OF THE MOTION OF A FRICTIONLESS PENDULUM 11 11 2 COMPLIANCE OF ARTERIAL WALLS 11 12 EXERCISES TWO-POINT BOUNDARY VALUE PROBLEMS A MODEL PROBLEM FINITE DI?ERENCE APPROXIMATION STABILITY ANALYSIS BY THE ENERGY METHOD FINITE DI?ERENCES FOR TWO-POINT BOUNDARY VALUE PROBLEMS WITH VARIABLE COE?CIENTS THE SPECTRAL COLLOCATION METHOD THE GALERKIN METHOD INTEGRAL FORMULATION OF BOUNDARY VALUE PROBLEMS A QUICK INTRODUCTION TO DISTRIBUTIONS FORMULATION AND PROPERTIES OF THE GALERKIN METHOD ANALYSIS OF THE GALERKIN METHOD THE FINITE ELEMENT METHOD SPECTRAL METHODS ADVECTION-DI?USION EQUATIONS GALERKIN FINITE ELEMENT APPROXIMATION THE RELATIONSHIP BETWEEN FINITE ELEMENTS AND FINITE DI?ERENCES; THE NUMERICAL VISCOSITY STABILIZED FINITE ELEMENT METHODS A QUICK GLANCE AT THE TWO-DIMENSIONAL CASE LUBRICATION OF A SLIDER VERTICAL DISTRIBUTION OF SPORE CONCENTRATION OVER WIDE REGIONS PARABOLIC AND HYPERBOLIC INITIAL BOUNDARY VALUE PROBLEMS THE HEAT EQUATION FINITE DI?ERENCE APPROXIMATION OF THE HEAT EQUATION FINITE ELEMENT APPROXIMATION OF THE HEAT EQUATION STABILITY ANALYSIS OF THE ?-METHOD SPACE-TIME FINITE ELEMENT METHODS FOR THE HEAT EQUATION HYPERBOLIC EQUATIONS: A SCALAR TRANSPORT PROBLEM SYSTEMS OF LINEAR HYPERBOLIC EQUATIONS THE WAVE EQUATION THE FINITE DI?ERENCE METHOD FOR HYPERBOLIC EQUATIONS DISCRETIZATION OF THE SCALAR EQUATION ANALYSIS OF FINITE DI?ERENCE METHODS STABILITY THE CFL CONDITION VON NEUMANN STABILITY ANALYSIS DISSIPATION AND DISPERSION EQUIVALENT EQUATIONS 13 10 FINITE ELEMENT APPROXIMATION OF HYPERBOLIC EQUATIONS 13 10 1 SPACE DISCRETIZATION WITH CONTINUOUS AND DISCONTINUOUS FINITE ELEMENTS 13 10 2 TIME DISCRETIZATION 13 11 APPLICATIONS 13 11 1 HEAT CONDUCTION IN A BAR 13 11 2 A HYPERBOLIC MODEL FOR BLOOD FLOW INTERACTION WITH ARTERIAL WALLS 13 12 EXERCISES REFERENCES