PRINCIPLES OF NUMERICAL ANALYSIS
CONTENTS INTRODUCTION TO NUMERICAL ANALYSIS NUMERICAL ANALYSIS THE GOALS OF NUMERICAL ANALYSIS NUMERICAL ANALYSIS IN R E?CIENCY DATA TYPES IN R DATA TYPES DATA STRUCTURES ELEMENTARY PROBLEMS SUMMATION ALGORITHMS EVALUATING POLYNOMIALS THE NTH ROOT ALGORITHM COMMENTS EXERCISES ERROR ANALYSIS TRUE VALUES ACCURACY PRECISION INTERNAL DATA STORAGE BINARY NUMBERS FLOATING POINT NUMBERS NUMERICAL ERROR ROUND-O?ERROR AND MACHINE ? LOSS OF SIGNI?CANCE OVER?OW AND UNDER?OW ERROR PROPAGATION AND STABILITY APPLICATIONS SIMPLE DIVISION ALGORITHMS BINARY LONG DIVISION LINEAR ALGEBRA VECTORS AND MATRICES VECTOR AND MATRIX OPERATIONS ELEMENTARY ROW OPERATIONS GAUSSIAN ELIMINATION ROW ECHELON FORM TRIDIAGONAL MATRICES MATRIX DECOMPOSITION LU DECOMPOSITION CHOLESKY DECOMPOSITION ITERATIVE METHODS JACOBI ITERATION GAUSS–SEIDEL ITERATION LEAST SQUARES INTERPOLATION AND EXTRAPOLATION POLYNOMIAL INTERPOLATION LINEAR INTERPOLATION HIGHER-ORDER POLYNOMIAL INTERPOLATION PIECEWISE INTERPOLATION PIECEWISE LINEAR INTERPOLATION CUBIC SPLINE INTERPOLATION B´EZIER CURVES MULTIDIMENSIONAL INTERPOLATION BILINEAR INTERPOLATION NEAREST NEIGHBOR INTERPOLATION TIME SERIES INTERPOLATION COMPUTER GRAPHICS DI?ERENTIATION AND INTEGRATION NUMERICAL DI?ERENTIATION FINITE DI?ERENCES THE SECOND DERIVATIVE NEWTON–COTES INTEGRATION MULTIPANEL INTERPOLATION RULES NEWTON–COTES ERRORS NEWTON–COTES FORMS, GENERALLY GAUSSIAN INTEGRATION THE GAUSSIAN METHOD IMPLEMENTATION DETAILS MORE TECHNIQUES ADAPTIVE INTEGRATORS ROMBERG’S METHOD MONTE CARLO METHODS REVOLVED VOLUMES GINI COE?CIENTS ROOT FINDING AND OPTIMIZATION ONE-DIMENSIONAL ROOT FINDING BISECTION METHOD NEWTON–RAPHSON METHOD SECANT METHOD MINIMIZATION AND MAXIMIZATION GOLDEN SECTION SEARCH GRADIENT DESCENT MULTIDIMENSIONAL OPTIMIZATION MULTIDIMENSIONAL GRADIENT DESCENT HILL CLIMBING SIMULATED ANNEALING THE TRAVELING SALESPERSON DI?ERENTIAL EQUATIONS INITIAL VALUE PROBLEMS EULER METHOD RUNGE–KUTTA METHODS, GENERALLY LINEAR MULTISTEP METHODS SYSTEMS OF ORDINARY DI?ERENTIAL EQUATIONS SOLUTION SYSTEMS AND INITIAL VALUE PROBLEMS BOUNDARY VALUE PROBLEMS PARTIAL DI?ERENTIAL EQUATIONS THE HEAT EQUATION THE WAVE EQUATION CARBON DATING LOTKA–VOLTERRA EQUATIONS SUGGESTED READING THE GOALS OF NUMERICAL ANALYSIS NUMERICAL ANALYSIS IS AN APPLIED BRANCH OF MATHEMATICS IT SEEKS OUT SOLUTIONS TO PRACTICAL PROBLEMS THAT CAN BE PUT INTO PRACTICE THE PRACTICAL ASPECT OF IT LEADS TO A DESIRE FOR SOLUTIONS THAT ARE “GOOD ENOUGH ” BUT GOOD ENOUGH IS HARDER TO DE?NE THE VALUE AND SUITABILITY OF NUMERICAL SOLUTIONS ARE CON- STRAINED BY THREE CONCEPTS FIRST, WE ARE CONCERNED WITH THE E?CIENCY, OR HOW MUCH WORK IS NECESSARY TO REACH A SOLUTION SECOND, WE ARE CONCERNED WITH THE ACCURACY OF OUR SOLUTION, OR HOW CLOSE WE ARE TO THE TRUE VALUE FINALLY, WE ARE CONCERNED WITH PRECISION, OR THE LEVEL OF DETAIL IN OUR SOLUTION WE WILL EXAMINE EACH OF THESE CONCEPTS IN TURN AND LEARN HOW TO APPLY THEM TO NUMERICAL ANALYSIS BUT GOOD ENOUGH IS ENTIRELY DEPENDENT ON THE APPLICATION SPACE NUMERICAL ANALYSIS UNDERLIES MANY ?ELDS WHICH REQUIRE NUMERICAL ANSWERS TO MATHEMATICAL QUESTIONS FROM VIDEO GAMES TO CLIMATE SCIENCE, AND PHYSICS TO PSYCHOLOGY, NUMERICAL ANALYSIS PERFORMS THE CALCULATIONS WE USE DAILY EN- GINEERS NEED TO KNOW THE TOLERANCES FOR LOAD BEARING CAPACITIES FOR A BUILDING FINANCIERS NEED TO CALCULATE THE EXPECTED MARKET RETURN ON AN INVESTMENT