numerical analysis

Name:

Student ID:

MATH 148 - Spring 2020 - HW1 - due Monday 4/6 at 2:40 PCT

Reading: §1.1, 1.2, 1.6, 1.7 (Scientific Computing with Matlab and Octave, by Quarteroni, Saleri & Gervasio, 4th ed)

1. (a) Let a = 0.00456, b = 0.123, c = −0.128. Using 3-digit rounding, compute (a + b) + c and a + (b + c). Conclusion?

(b) Let a = 2, b = −0.6, c = 0.602. Using 3-digit rounding, compute a×(b+c) and (a×b) + (a×c). Conclusion?

2. (a) Let x, y and z be real numbers whose floating point approximations in a computing device coincide with x, y and z respectively. Show that the relative error in computing x(y + z) equals �1 + �2 − �1�2 where �1 = Er(fl(y + z)) and �2 = Er(fl(x×fl(y + z))).(given a number x and its approximation x̂, we denote Er(x̂) =

|x−x̂| |x| )

1

(b) If fl(x) is the approximation of a real number x is a computing device, and � is the corresponding relative error, then show that fl(x) = (1 − �)x.

3. (a) How many numbers belong to the set F(2, 2,−2, 2). What is the value of �M for such a set ?

(b) Show that the set F(β,t,L,U) contains precisely 2(β − 1)βt−1(U −L + 1) elements.

(c) (Matlab) Write a script that visualizes the set F(β,t,L,U) on the real line (there may be three nested for loops), and plot the set F(2, 2,−2, 2) (witness how this set is “denser” near zero). Does the spacing look more uniform when plotting with a log-rescaling on x ? (command: semilogx)

2

4. The Fibonacci sequence is defined as

u0 = u1 = 1, un+2 = un+1 + un (n ≥ 0). (1)

(a) Find r1,r2 the two roots of the polynomial equation r 2 − r − 1 = 0 with r1 > 1 (r1 is the

“golden ratio”). Find constants c1,c2 such that u0 = c1 + c2 and u1 = c1r1 + c2r2, and prove by induction that un = c1r

n 1 + c2r

n 2 for every n ≥ 0.

(b) Deduce that r1 = limn→∞ un+1 un

and if en = 1 r1

∣∣∣un+1un −r1∣∣∣ is the relative error at step n, show that |en| ≤ C

( r2 r1

)n for some fixed constant C.

(c) (Matlab) Write a script that computes the nth Fibonacci number based on (1) (one for loop). At every iteration, compute r̂1 =

un+1 un

and store en = Er(r̂1) (as ’true’ value, you may use

Matlab’s value for r1 = 1+ √ 5

2 ). Provide a plot of log en versus n, explain the different regimes

(the error should first decrease linearly, how much is the slope ?)

3