INTRODUCTION TO COMPUTATIONAL MATHEMATICS

1 INTRODUCTION TOCOMPUTATIONALMATHEMATICSC ourse Notes forCM 271 / AM 341 / CS 371H. De SterckP. UllrichDepartment of Applied MathematicsUniversity of WaterlooMarch 20th, 2006 These notes have been funded by2 Contents1 Errors and Error Sources of Error .. Floating Point Numbers and Operations .. A Binary Computer .. Standard floating point systems .. Machine Precision .. Floating Point Operations .. Condition of a Mathematical Problem .. Stability of a Numerical Algorithm .. 232 Root INTRODUCTION .. Four Algorithms for Root Finding.

2 Bisection Method .. Fixed Point Iteration .. Newton s Method .. Secant Method .. Stopping Criteria for Iterative Functions .. Rate of Convergence .. Convergence Theory .. Fixed Point Iteration .. Newton s Method .. Secant Method .. Overview .. 443 Polynomial Interpolation .. The Vandermonde Matrix .. Lagrange Form .. Hermite Interpolation .. Piecewise Polynomial Interpolation .. Piecewise Linear Interpolation .. Spline Interpolation .. Further Generalizations .. 5534 CONTENTS4 Integration of an Interpolating Polynomial.

3 Midpoint Rule:y(x) degree 0 .. Trapezoid Rule:y(x) degree 1 .. Simpson Rule:y(x) degree 2 .. Accuracy, Truncation Error and Degree of Precision .. Composite Integration .. Composite Trapezoid Rule .. Composite Simpson Rule .. Gaussian Integration .. 645 Discrete Fourier INTRODUCTION .. Fourier Series .. Real form of the Fourier Series .. Complex form of the Fourier Series .. Fourier Series and Orthogonal Basis .. Discrete Fourier Transform .. Aliasing and the Sample Theorem .. Fast Fourier Transform.

4 DFT and Orthogonal Basis .. Power Spectrum and Parseval s Theorem .. 906 Numerical Linear INTRODUCTION .. Gaussian Elimination .. LU Factorization .. Pivoting .. Algorithm and COMPUTATIONAL Cost .. Determinants .. Condition and Stability .. The Matrix Norm .. Condition of the problemA~x=~b.. Stability of the LU Decomposition Algorithm .. Iterative Methods for solvingA~x=~b.. Jacobi and Gauss-Seidel Methods .. Convergence of Iterative Methods .. 115 INTRODUCTION toComputationalMathematicsThe goal of COMPUTATIONAL MATHEMATICS , put simply, is to find or develop algo-rithms that solve mathematical problems computationally (ie.)

5 Using comput-ers). In particular, we desire that any algorithm we develop fulfills four primaryproperties: accurate algorithm is able to return a result that is nu-merically very close to the correct, or analytical, result. efficient algorithm is able to quickly solve the mathemat-ical problem with reasonable COMPUTATIONAL resources. robust algorithm works for a wide variety of inputsx. stable algorithm is not sensitive to small changes in notes have been funded 1 Errors and ErrorPropagationIn examining COMPUTATIONAL MATHEMATICS problems, we shall generally considera problem of the following form:ProblemConsider an arbitrary problemPwith inputx.

6 We must computethe desired outputz=fP(x).In general our only tools for solving such problems are primitive mathemati-cal operations (for example, addition, subtraction, multiplication and division)combined with flow constructs (if statements and loops). As such, even simpleproblems such as evaluating the exponential function may be difficult the problemPdefined by the evaluation of the exponen-tial functionz= exp(x). We wish to find the approximation zforz= exp(x) from calculus that the Taylor series expansion of theexponential function is given byexp(x) = 1 +x+x22!

7 +x33!+..= Xi=0xii!.( )Since we obviously cannot compute an infinite sum computationally withoutalso using infinite resources, consider the truncated series constructed by onlysumming the firstnterms. This yields the expansion z=nXi=0xii!( )78 CHAPTER 1. ERRORS AND ERROR PROPAGATIONAs we will later see, this is actually a poor algorithm for computing theexponential - although the reason for this may not be immediately Sources of ErrorComputational error can originate from several sources, although the mostprominent forms of error (and the ones that we will worry about in this text)come from two main sources:1.

8 Errors introduced in the inputx. In particular, this form of error can begenerally classified to be from one of two sources:a) Measurement error, caused by a difference between the exact valuexand the measured value x. The measurement error is computedas x=|x x|.b) Rounding error, caused by a difference between the exact valuexand the COMPUTATIONAL or floating-point representation x=f l(x).Since infinite precision cannot be achieved with finite resources, thecomputational representation is a finite precision approximation ofthe exact , for example, the decimal numberx= order to standardize the representation of these numbers we per-form normalization (such that the number to the left of the decimalpoint is 0 and the first digit right of the decimal point is nonzero).

9 The number xis thus normalized as follows:x= |{z}mantissa 10 3.( )However, a computer can only represent finite precision, so we arenot guaranteed to retain all digits from the initial number. Let sconsider a hypothetical decimal computer with at most 5 digits inthe mantissa. The floating-point representation ofxobtained on thiscomputer, after rounding, is given by x=fl(x) = 10 3.( )The process of conversion to a floating point number gives us a round-ing error equal to x=x x= Errors as a result of the calculation, approximation or algorithm. Thisform of error can again be generally classified to be from one of two sources:a) Truncation error.

10 When truncating an infinite series to provide afinite approximation, the method inherently introduces an error. SOURCES OF ERROR9example we first considered truncating the infinite expansion asfollows:z= exp(x) = Xi=0xii!=nXi=0xii!+ Xi=n+1xii!= z+ Xi=n+1xii!( )In this case, the truncation error is given byT=z z= Xi=n+1xii!( )b) Rounding errors in elementary steps of the algorithm. For example,consider the addition of 107and 103in a floating pointnumber system where we only maintain 4 digit accuracy (in base 10).The exact result should be 107but due to rounding weinstead calculate the result to be analyzing sources of error, it is often useful to provide a mathematical basisfor the error analysis.