Week 2 - Error and Asymptotics, Rounding, Chopping, Computer Arithmetic, FYTT PDF

Preview

Summary

Download Week 2 - Error and Asymptotics, Rounding, Chopping, Computer Arithmetic, FYTT PDF

Description

2 2.1

Error, Asymptotics, and Computer Arithmetic Expressing Error in Different Ways

We have already talked about error in the context of T T

. Finding or bounding error associated with a

— as well as how quickly that error may d

or i

as parameters change — will be important in this course. There are different ways we can do this.

For the following, suppose we have a “true” quantity p that we wish to approximate using p∗ . Absolute Error Absolute error simply gives the m between the two, i.e.: Absolute Error = |p − p∗ |.

of the difference

Relative Error Relative error scales the difference between the two instead, which is especially useful if the quantities involved are v v

s

l

or

. Relative error is given by:    p − p∗  . Relative Error =  p 

Example 1. Find the absolute and relative errors for estimating: a) The quantity 71 by the approximation 75;

b) The quantity 6.5 × 1017 by the approximation 1.0 × 1018 .

2

Example 2. Find the largest interval in which an estimate of 22 must lie to produce relative error of at most 1%.

2.2

Asymptotic Order and Big-O Notation

We will find it useful throughout the course to express how error changes depending on a parameter, and asymptotic order will give us an important way to measure this.

3

2.3

Big-O Notation

Let f (n) and g(n) be functions depending on a “l

” param-

eter n, and suppose that |f (n)| and |g(n)| both → ∞ as n → ∞. Then, we say that: f (n) ∈ O(g(n)) or f ∈ O(g) if there exists an N such that for some n > N , we have that |f (n)| ≤ k|g(n)| for some finite constant k .

We can check to see if f ∈ O(g) by evaluating the limit f (n) . n→∞ g(n) lim

If that limit evaluates to a f

c

, then f satisfies

the criteria above, and roughly, we can think of f as growing at about the same pace as g. We say “f is on the order of g as n → ∞”, or “f is Big-O of g as n → ∞”. 4

✍ Some sources might write this notation using an equals sign; i.e. f = O(g). However, this is a bit of an abuse of notation since many different functions f may be on the order of g . ✍ In the event that the limit on the previous page gives 0, then f grows m

l

than g. In that case, some

q

sources may use the notation f ∈ o(g), or “f is little-o of g”. Note that if f ∈ o(g), then f is always ∈

automatically as well,

by definition. For this course, it will be usually be fine to just work with Big-O notation.

Big-O notation helps us to compare different kinds of growth. For √ example, we know that ln(n), n, n2, and 2n all grow w b

as n gets large. But they all do so at different rates, with

some growing only extremely slowly, and others starting gradually but then exploding in growth as n increases.

5

Example 3. Let f (n) = n3 + n + 7. Show that f ∈ O(n3).

Example 4. Which is true: ln(x) ∈ O (ln(ln(x))),

or

ln(ln(x)) ∈ O (ln(x))?

6

We can also use this notation to describe i ; that is, where the parameter involved is very

a s

instead.

That is, suppose that f (h) and g(h) both → 0 as h → 0. We can write: f (h) ∈ O(g(h)) if there exists some δ > 0 such that whenever |h| < δ, we have that |f (h)| ≤ k |g(h)| for some positive constant k. Similarly to above, we can determine if this is true by determining if the following limit yields a finite constant: f (h) h→0 g(h) lim

Example 5. Show that the infinite polynomial

∞ X n=2

an hn , where

each of the an are positive constants, is on the order of h2 as h → 0.

7

This gives us an interesting and useful way of expressing the error associated with our T

from earlier:

a

Recall that the Taylor polynomial for ex about x = 0 is given by x2 xn f (n+1)(c) n+1 e = 1 +x + +...+ x , + (n + 1)! n! 2 x

for some c in between 0 and x (a value that was difficult or impossible to calculate). Now, using our knowledge from our new concept, let’s recognize that whatever c might be,

f (n+1) (c) (n+1)!

is just some c

coefficient of xn+1 . Therefore, the whole error is simply a term that is on the order of xn+1 as x → 0. As a slight abuse of notation, it is very common to write: ex = One thing is for certain: This is d w

d

!

8

e

to

2.4

Floating Point Math

We often take for granted that computers can do math, given the correct input. But how are numbers s ? Consider the number 1 . We know from experience that the decimal expansion of this 3 rational expression is:

But, a device with f

storage capabilities might have trouble

storing a number with an i

number of decimal places.

The situation might be even worse for an irrational number (like or

), where a decimal expansion generally doesn’t follow any kind

of pattern.

Computers typically use “floating-points” to deal with numbers of all kinds. This is a structure that can store any base-10 number that is of a particular size and to a certain precision.

9

A floating-point number system is one that stores any nonzero number x in the following way: f l(x) = (sign(x))0.d1d2 . . . dn × 10p where p is a whole number between certain minimum and maximum values, and di ∈ {0, 1 . . . , 9}. The function sign(x) simply returns −1 if x is negative, and 1 if x is positive. The string of digits .d1d2 . . . dn is called the mantissa, and n is a whole number that determines the p

of this representa-

tion. ✍ For this course, we will work exclusively with a decimal (base-10) number system, but the same definitions may be extended to other representations, such as octal (base

) or hexadecimal (base

in truth, the mantissa is typically stored in binary form.

10

);

Example 6. Write the following numbers in 4-digit (decimal) floating point representation: a) −39.2

b) 5

c) 1001

While computer programming, you may have encountered terms like “float” and “double” when defining variables. Typically: • a float refers to a number that uses this format and 32 bits (a bit is just a d

, 0 or 1) of information: 1 bit is used for the

sign, 8 bits are used for the exponent, with the remaining used for the mantissa; • a double precision number uses this format and 64 bits: 1 for the sign, 11 for the exponent, and the remaining

for the

mantissa. Double-precision floating point numbers require double the , but are much more precise when it comes to storing

s v

l

or v

numbers.

s 11

Example 7. Write the number 20.006 in 4-digit floating point representation. Well, this is t

. If we try to use the strategy from the previous

example, we end up with 0.20006 × 102, except that this requires digits of precision! In these cases, there are a couple of options:

Chopping to n digits of precision: That is, the mantissa is t

after n digits. In the case of our previous example, we

would obtain a result of

.

In general, the absolute error associated with chopping is |error| < 10−n+p , where p is the power of 10 in the floating-point representation. For example, the act of chopping any number ×102 to four decimal places will produce error of no more than 10−4+2 = 10−2. ✍ Chopping is “quick and dirty” and computationally i

, but just fine if all you might need is a rough approxi-

mation or simple estimate. 12

Rounding to n digits precision requires a little bit of extra computation but in general cuts the potential for error i

h

.

To round a number to the nearest given power of 10, a simple scheme look to the digit to the right of the one in question; if it is 5 or greater, round up; if not, round down. In this case, the absolute error is given 1 by |error| ≤ 10−n+p . 2 In our example, of course, rounding 20.006 for four-digit arithmetic would yield a result of

.

✍ Depending on the application, a rounding scheme may make different choices if the “number to the right” is a 5, such as rounding so that the result ends with an e

digit. For this course, you

are safe to assume that 5 will always round u

13

!

Computers will tackle mathematical expressions using the usual order of operations, storing numbers to a particular precision at each step. It is easy to see through some simplified number systems how error can quickly a

in this way!

Example 8. Calculate the following expressions “acting like a computer” using 4-digit (decimal) arithmetic using the method described. a) Using chopping: 30.009 − 10.001 − 10.0025 − 10.0031

√ √ √3 3 b) Using rounding: ( 10)( 10)( 3 10)

c) Using chopping: tan

 π 2

14

FYTT 2: 1. a) A “true” value is given as p = 10−3 . For what range of values must an estimate of p be to produce a relative error of less than 1? b) A “true” value is given as p = 471. For what range of values must an estimate of p be to produce a relative error of less than 3.3%? Final Answers: a) An estimate p∗ must be between 0 and 0.002. b) An estimate p∗ must be between 455.457 and 486.543.

2. Suppose you are estimating a third-degree Taylor polynomial centered at t = 0 for e−t in order to estimate the value of e−1 . What is the absolute and relative error in doing so? Final Answers: The absolute error in the estimate is about 0.03458. The relative error is then 9.4%.

3. Suppose you are estimating a “true” value p by a value p∗ . Under what circumstances is: a) the absolute error equal to the relative error? b) it completely nonsensical to use the relative error? Final Answers: a) The absolute error is equal to the relative error whenever p is equal to 1 OR whenever the estimate is exact (i.e. p = p∗ ). b) If the true value is 0, then the relative error remains undefined, and therefore it does not make any sense to try and define it.

15

2

4. a) Show that ex ∈ O(ex ) as x → ∞. b) Show that tan2 (h) ∈ O(h2 ), where h is a small parameter. c) Show that xa ∈ O(xb ) if a ≤ b, where x is large. d) Show, given a function f (x), that any real constant times f (x) must be on the order of f (x) as x → ∞.

5. For each of the following, use the basic definition of “Big-O” notation to show the following, rather than calculate a limit.   1 ∈ O(h), where h is a small positive parameter. a) Show that h sin h b) Show that

√

√ x + 1 ∈ O( x), where x is a large positive parameter.

6. Calculate the following expressions “acting like a computer” using 4-digit arithmetic using the method described. √

1 a) Using rounding: √ 2

b) Using rounding:

c) Using chopping: eln(40)

d) Using chopping: ln(e40)

e) Using rounding: 10! − 5!

f) Using chopping:

2 2

3−

√

10

2

Final Answers: a) 0.7072 d) 39.99

b) 0.7070

c) 39.94

e) 3629000 (a number larger than 10!, believe it or not)

16

f) −0.081

7. Go through each of the approximations in Question 6 and find the absolute and relative errors from the true values. Final Answers: a) Absolute: About 9.32188 × 10−5

Relative: About 0.0131831%

b) Absolute: About 1.06781 × 10−4

Relative: About 0.0151011%

c) Absolute: 0.06

Relative: 0.15%

d) Absolute: 0.01

Relative: 0.025%

e) Absolute: 320

Relative: About 0.00881863%

f) Absolute: About 1.3883 × 10−4

Relative: About 0.1711%

8. What is the minimum number of digits that would need to be included in the arithmetic for a computer to produce the result of the following with zero error? a)

1 + 2.5 + 5.05 10

b) 0.0002(0.00005)

c) π − 3.14

d) cos(0)

Final Answers: a) 3

b) 1

c) There will always be nonzero error with any number of digits.

17

d) 1...