01:198:107 Lecture Notes - Lecture 16: Approximation Error, Condition Number, Square Root
CS 107: Lecture 16: solving f(x)=0
● Approximation
○ How does this solve the problem?
■ Problem: infinite numbers, finie # bits
■ Solution:
● Use the bits to represent a finite number of numbers exactly
● When you want to represent any other number, use the
closest number you can represent
○ Eg. suppose you want to represent ⅓
○ Represent it as +.333e+00
● Relative error
○ Often what you are more concerned with
■ Eg error of 1 ft in measuring this room for a carpet is a big deal, but
error of 1 ft in measuring distance from here to GW Bridge is not a
big deal
■ Note that this representation gives roughly constant relative error,
as long as number is not too close to 0 or too far from 0
● Sources of round off
○ Irrationals
○ Repeating decimals
○ Operations not closed
■ Division
■ Addition
● Sources of large relative error
○ Overflow: number too big
○ Underflow: number too close to 0
○ Cancellation
○ Poor conditioning
● Poor conditioning
○ Condition number = d result / d input
● Consequences
Document Summary
Use the bits to represent a finite number of numbers exactly. When you want to represent any other number, use the closest number you can represent. Eg. suppose you want to represent . Often what you are more concerned with. Eg error of 1 ft in measuring this room for a carpet is a big deal, but error of 1 ft in measuring distance from here to gw bridge is not a big deal. Note that this representation gives roughly constant relative error, as long as number is not too close to 0 or too far from 0. Condition number = d result / d input. Given values for all but one variable. An expression whose value is 0 when the original relationship holds. So solving an equation reduces to finding the zeros of a function. Look in the middle of the bracket. Assume f(x) is a straight line from (x-,f(x-)) to (x+,f(x+))