Please enable JavaScript.

Coggle requires JavaScript to display documents.

cs417 hw2, double z = x + y, hw2, x(star) * y(star) -> relative error…

- - - - (absolutevalue(known correct - actual value))/ (absolutevalue(known correct))
        
        absolute error/known correct value
      - one we care about
      - order of magnitude of how off we are
      - relative error = absolute value[x-x(star)] / absolutevalue[x]
        
        meaning
        
        known correct - actual value / known correct value
        
        aka
        
        infinite precision - finite precision / infinite precision
        
        the smaller the value we have in the denominator, the larger the bound.
        the larger the denominator, the smaller the bound
        
        <=2^-k x 2^e / absolute value[x]
        
        lim as x->0, sum(1/x) approaches infinity
        
        smallest possible value a finite value(x, as opposed to x(star)), can be
        
        0
        
        if both x = 0 and x(star) = 0, then
        
        error = 0
        
        1 more item...
        
        smallest possible value a finite value(x(star)), can be
        
        0
        
        <={ 2^-k x 2^e} / {(2^-1) x 2^e}
        
        simplify
        
        upper bound for relative error
        2^-k / 2^-1
        or
        2^-k x 2^1
        or
        2^(-k+1)
        
        relative error = absolute value[x-x(star)] / absolutevalue[x]
        <= 2^-k/2^-1
        
        largest possible error we can have for a finite precision number that we can store
        
        1 more item...
        
        in what cases is this upper bound useful?
        
        2 more items...
        
        later generalizes to
        
        1 more item...
    - - ex
        
        someone says its 90 degrees outside
        phone says its 87
        the absolute error is
        
        absolute value(90-87) = 3
        
        it takes 40 minutes to get somewhere but someone says it takes45 minutes
        
        abs error =
        
        5
        
        supposed to change oil at 3000 miles
        change it at 3100
        
        abs(3000-3100)=100
      - absolutevalue(known correct - actual value)
      - absolute error formula
        
        absolute value((+-infiniteprecision) - (+-finiteprecision))
        
        ( +- summation(b
        (star)(-i) x B^(-i))
        from i=1 to k ) x B^e(star)
        
        (+-summation(b(-i)xB^(-i)) from i =1 to infinity) x B^(e))
        
        -
        
        abs[B^e(summation(b(-i)^starxB^(-i)) from i =1 to infinity) - summation(b(star)(-i)) x B^(-i)) from i=1 to k]
        
        e = e(star)
        
        why?
        
        2 more items...
        
        +- signs will match,
        absolute value nullifies them
        
        sums can be split:
        
        from i=1 to k:
        
        2 more items...
        
        from i=k+1 to infinity:
        
        1 more item...
        
        absolute value(
        
        )
  - - - f= ( +- summation(b(star)(-i) x B^(-i))
        from i=1 to k ) x B^e(star)
        
        ex
        
        0.1010
        
        b(-1) = 1
        b(-2) = 0
        b(-3) = 1
        b(-4) = 0
        
        each individual digit = b(-i)
        each position = B^(-i)
        
        where e = +-summation ( s(i) x B^i)
        from i = 0 to s-1
        
        b(-i) = either 0 or 1
    - - base 2 -> B =2
      - f - mantissa(always normalized)
        e - exponent
        b - base
  - - - star means
        
        may be different from its finite precision equivalent
      - e = +-(summation(s(i)^starxB^(i)) from i =0 to infinity) x B^e(star)
- - - - x(star) = +/- [sum of (b(-i) x B^-i ) from i=1 to k ] x B^e
        
        ?<= absoluteValue[x(star)]<=?
        
        upper/lower bound for finite precision
        
        mantissa
        
        largest/smallest possible mantissa i can store
        
        sum of (b(-i) x B^-i ) from i=1 to k
        
        +/- ommitted because were only interested in teh magnitude(cant have negative amount of storage space)
        
        smallest possible nonzero mantissa we can store
        
        0.1 ( both in base 2 and base 10)
        
        1 more item...
        
        largest possible
        
        0.11.. Base 2
        0.99.. Base 10
        
        1 more item...
        
        final: B^-1 <=mantissa <= 1-B^-k
        
        exponent
        
        largest/smallest possible magnitude for the exponent
        
        B^e
        
        e = +- sum{s(i)B^i} from 0 to s
        
        to get the largest number possible what kind of exponent do we need?
        
        1 more item...
        
        to get the smallest number possible what kind of exponent do we need?
        
        1 more item...
        
        final: |e| <= B^s -1
        
        largest possible: B^(s) -1
        smallest possible: -(B^(-s) - 1
        
        final: smallest/largest possible finite precision number: B^(-1) x B ^{ B^[s] -1} <= absoluteValue(x(star) <= 1 - B^(-k) x B^{ B^[s] -1}
- - - - z(star) = x(1+epsilonx) + y(1+epsilony)
        
        z(star) = x+y +(x(epsionx) y(epsilony))
        
        x+y = z
        
        absolute error: abs[z(star) -z]
        abs[x+y + xepsilonx + yepsilony - x+y]
        =abs[xepsilonx+yepsilony]
        
        relative error:
        abs[xepsilonx+yepsilony] / abs[x+y]
        
        absolute value property
        
        relative error:
        abs[xepsilonx+yepsilony] / abs[x+y]<=abs[xepslionx]/abs[x+y] + abs[yepsilony]/abs[x+y]
        
        2 more items...
  - - - x(1+epsilon(x)) / y(1+epsilon(y))
        
        [x(1+epsilon(x)) / y(1+epsilon(y)) ]
        
        x
        
        (1-epsilony / 1-epsilony)
        
        multiply by conjugate(1)
        
        x(1+epsilonx) (1-epsilony) / y(1+epsilony)(1-epsilony)
        
        x(1+epsilonx) (1-epsilony) /y(1-epsilony^2)
        
        x(1+epsilonx - epsilony) /y(1)
        
        (x/y) ( 1+ epsilonx - epsilony)
        
        1 more item...
        
        (1+e(i)) x (1-e(i))
        = 1+e(i)-e(i)-e(i)^2
        
        1-e(i)^2
        
        epsilon^n = 0
        
        1
        
        as long as epsilon subscript matches(ex:epsilonx)
  - - - aka
        
        repeated multiplication
    - - z = x(y)
        
        z = x(y) -> z(star) = x(star) y(star)
        
        abs[z(star) - z]
        
        z(star) = x(star) y(star)
        
        =
        
        z(star)=x(1+epsilon(x)) y(1+epsilon(y))
        
        z(star)=xy(1+epsilonx + epsilony + epsilionxy)
        
        3 more items...
        
        abs[z(star) - z]=abs[xy+(xy)(epsilonx +epsilony) - z]
        
        abs[z(star) - z]=abs[xy+(xy)(epsilonx +epsilony) - xy]
        
        abs[z(star) - z]=abs[(xy)(epsilonx +epsilony)]
        
        meaning
        
        1 more item...
- - - - which leads us to
        
        x(star) = x(1+epsilon)
        =
        x+ (x(epsilon))
        =
        x +- how far off i am
        
        x(star) also = fl(x)
        
        meaning floating point of x
- - - - aka
        
        triangle inequality
      - meaning
        
        the absolute value of the sum of two numbers is no greater than the absolute values of each of those numbers added together,
        this applies no matter how many numbers youre adding
        
        useful for hw2,
        hw3,
        exam question on condition numbers
      - by extension,
        
        abs[a-b] <= abs[a] + abs[b]
- - - - (x+y)(1+e1+e2)+z(1+e2)
        (x+y)+(x+y)(e1+e2) + z(1+e2)
        (x+y+z)+(x+y)(e1)+(x+y+z)(e2)
        
        absolute error:
        absolutevalue[(x+y+z)+(x+y)(e1)+(x+y+z)(e2) - (x+y+z)]
        terms cancel out
        abs[(x+y)(e1)+(x+y+z)(e2)]
        
        absolute error:
        abs[(x+y)(e1)+(x+y+z)(e2)] <= abs[x+y] (abs[e1]) + abs[x+y+z] (abs[e2])
        
        relative error:
        abs[(x+y)(e1)+(x+y+z)(e2)] / abs[x+y+z]
        <= {abs[x+y] (abs[e1]) } / {abs[x+y+z]} +{abs[x+y+z] (abs[e2])} / abs[x+y+z]
        
        epsilon 1,2,3,4 are all really close to one another in terms of magnitude
        
        E = max(e1,e2,e3,e4}
        
        pullout E from both terms
        <={abs[x+y] / {abs[x+y+z]} + abs[x+y+z] / abs[x+y+z] } {E}
        second term cancels out
        <= { (abs[x+y] / abs[x+y+z]) + 1 } E = bound for eq 1
        
        vs
        
        2 more items...
- - - - number line method
        
        0 x y z
        
        abs[x+y] < abs[y+z]
        fl(fl(x+y)+z)) is more accurate(has less relative error)
      - abs[x+y] vs abs[y+z]
- - - - fl(fl(x) * fl(y))
    - - epsilon m is the error for multiplication
      - xy(1+epslionx+epsliony)(1+epsilonm)
        
        absolute error: abs[xy(1+ex+ey+em) - (xy)]
        
        relative error;
        abs[xy(1+ex+ey+em) - (xy)/ abs[xy]
        =abs[[xy[ex+ey+em)]/abs[xy]
        =abs[ex+ey+em]
        
        doing this for division, repeated multiplication, subtaction, addition up to you, will be on exam
        9/14 38 minutes in