2 6 2012 Computational Methods CMSC AMSC MAPL 460 Representing numbers in floating point Ramani Duraiswami Dept of Computer Science Effects of floating point errors Singular equations will only be nearly singular Severe cancellation errors can occur x 0 988 0001 1 012 y x 7 7 x 6 21 x 5 35 x 4 35 x 3 21 x 2 7 x 1 plot x y 1 2 6 2012 Class Outline Computations should be as accurate and as error free as possible Sources of error Poor models of a physical situation Ill posed problems Errors due to representation of numbers on a computer successive operations with these How do we analyze an algorithm for correctness Forward error analysis Backward error analysis Well posedness Error What we need to know about error how does error arise how machines do arithmetic fixed point arithmetic floating point arithmetic how errors are propagated in calculations how to measure error 2 2 6 2012 Typical task that uses scientific computing Evaluate safety of a machine part Tasks 1 Measure the parts dimensions shape etc and discretize it e g via finite elements 2 Determine the material it is made of 3 Find the mathematical models equations that determine how the part will deform according to loads 4 Discretize the equations e g via finite elements 5 Solve it on the computer Errors 1 2 3 4 Each step is characterized by some error Measurement errors Errors in properties Inexact mathematical models Discretization errors something continuous is represented discretely 5 Errors in the solution to discrete representations of numbers 3 2 6 2012 Errors are inevitable Everybody did the best they could No one made any mistakes yet answer could be wrong Goal of error analysis is to determine when the answer can be relied upon Which algorithms can be trusted for which data Last class we focused on errors due to the finite representation of numbers Modeling Original mathematical models may be poorly specified or unavailable E g Newton s laws work for non relativistic dynamics Turbulence Computing with a poor model will lead to inevitable errors Quantities that are measured may be done so with error and bias Using them in computation will lead to errors Approaches to fix these errors are in the domain of statistics Will not be much discussed in this course 4 2 6 2012 Numerical Modeling and Measurement Errors Continuous mathematical models have to be represented in discrete form on the computer Finite difference or finite element discretization Continuous quantities may be represented using linear interpolants Model may only reach accurate answer in the limit Round off errors continuous numbers represented with discrete representations on the computer Error definition Computation should have result c Actual result is x abs err x c rel err x c x for x 0 x c 1 rel err Usually we do not know c No need to solve the problem if we already knew it Error analysis tries to estimate abs err and rel err using computed result x and knowledge of the algorithm and data 5 2 6 2012 Two issues Can we design algorithms to minimize errors Can we estimate errors based on knowledge of algorithm Error Analysis forward and backward Errors due to round off in addition Errors can be magnified during computation Example 2 003 x 100 suppose 001 or 05 error 2 000 x 100 suppose 001 or 05 error Result of subtraction 0 003 x 100 but true answer could be as small as 2 002 2 001 0 001 or as large as 2 004 1 999 0 005 So error in the answer is as much as 002 or 200 error if true answer is 0 001 Called Catastrophic cancellation or loss of significance 6 2 6 2012 Addition We could generalize this example to prove a theorem When adding or subtracting the bounds on absolute errors add Multiplication Division What if we multiply or divide Suppose x and y are the true values and X and Y are our approximations to them If X x 1 r and Y y 1 s then r is the relative error in x and s is the relative error in y Can show that If r and s are small then we can ignore rs term 7 2 6 2012 Rules of thumb Addition subtraction Bounds on absolute errors add Multiplication Division Bounds on relative errors add One way to analyze the algorithm is to assume this error occurs in each arithmetic operation Worst case analysis Such error bounds forward error bounds are often pessimistic Error Analysis Two primary techniques of error analysis Forward Error Analysis Floating point representation of the error is subjected to the same mathematical operations as the data itself Equation for the error itself Backward Error Analysis Attempt to regenerate the original mathematical problem from previously computed solutions Minimizes error generation and propagation 8 2 6 2012 Error Analysis Forward and Backward error analysis Forward error analysis Assume that the problem we are solving is exactly specified Produce an approximate answer using the algorithm considered True problem True solution unknown Computed solution known Goal of forward error analysis produce region guaranteed to contain true soln Report region and computed solution Backward error analysis We know that our problem specification itself has error error in initial data So while we think we are solving one problem we are actually solving another Unknown problem the one actually solved True problem known Region containing true problem and solved problem True Solution Unknown Computed solution Given an answer determine how close the problem actually solved is to the given problem Report solution and input region 9 2 6 2012 Testing for Error Propagation Use the computed solution in the original problem and check if it satisfies it Use Double or Extended Precision rather than Single Precision Rerun the problem with slightly modified incorrect data and look at the results Well posed problems Hadamard postulated that for a problem to be well posed 1 Solution must exist 2 It must be unique 3 Small changes to input data should cause small changes to solution Essentially this means the regions in the problem space and solution space must be small 10