CS590 homework 1 Solved

1.      The function 𝑓1(𝑥0, ℎ) = sin(𝑥0 + ℎ) − sin⁡(𝑥0) can be transformed into another form, 𝑓2(𝑥0, ℎ) using the trigonometric formula given below:

                                                                                                               𝜙 + 𝜓           𝜙 − 𝜓

sin(𝜙) − sin(𝜓) = 2 cos ( ) sin ( )

                                                                                                                     2                   2

Thus, 𝑓1and 𝑓2 have the same values, in exact arithmetic, for any given argument values 𝑥0 and ℎ.

a.      Derive 𝑓2(𝑥0, ℎ).

b.      Suggest a formula that avoids cancellation errors for computing the approximation (𝑓(𝑥0 + ℎ) − 𝑓(𝑥0))/ℎ to the derivative of 𝑓(𝑥) = sin(𝑥) at 𝑥 = 𝑥0. Write a Python program that implements your formula and computes an approximation of 𝑓′(1.2), for ℎ =⁡1e-20, 1e-19, …, 1.

 

2.      Consider the linear system  

                                                                                      𝑎    𝑏     𝑥         1

                                                                                    (𝑏     𝑎) (𝑦) = (0)

with 𝑎, 𝑏 0.  

a.      If 𝑎 ≈ 𝑏, what is the numerical difficulty in solving this linear system?

b.      Suggest a numerically stable formula for computing 𝑧 = 𝑥 + 𝑦 given 𝑎 and 𝑏.

c.       Determine whether the following statement is true or false, and explain why:

“When 𝑎 ≈ 𝑏, the problem of solving the linear system is ill-conditioned but the problem of computing 𝑥 + 𝑦 is not ill-conditioned.”

3.      With exact rounding, we know that each elementary operation has a relative error which is bounded in terms of the rounding unit 𝜂; e.g., for two floating point numbers 𝑥 and 𝑦, 𝑓𝑙(𝑥 + 𝑦) = (𝑥 + 𝑦)(1 + 𝜖), |𝜖| ≤ 𝜂. But is this true also for elementary functions such as sin, ln, and exponentiation?  

Consider exponentiation, which is performed according to the formula below.

𝑥𝑦 = 𝑒𝑦𝑙𝑛(𝑥)⁡(𝑎𝑠𝑠𝑢𝑚𝑖𝑛𝑔⁡𝑥 0)

Estimate the relative error in calculating 𝑥𝑦 in floating point, assuming 𝑓𝑙(𝑙𝑛𝑧) = (𝑙𝑛𝑧)(1 + 𝜖), |𝜖| ≤ 𝜂, and that everything else is exact. Show that the sort of bound we have for elementary operations and for ln does not hold for exponentiation when 𝑥𝑦 is very large.  

4.      You are required by a computer manufacturer to write a library function for a given floating point system to find the cube root 𝑦1/3 of any given positive number 𝑦. Any such relevant floating-point number can be represented as 𝑦 = 𝑎 ∗ 2𝑒, where 𝑎 normalized fraction (0.5 ≤ 𝑎 < 1) and 𝑒 is an integer exponent. This library function must be very efficient and it should always work. For efficiency purposes it makes sense to store some useful constants ahead of computation time, e.g., the constants 21/3, 2/3 and 𝑎/3, and should these prove useful.

a.      Show how 𝑦1/3 can be obtained, once 𝑎1/3 has been calculated for the corresponding fraction, in at most five additional flops.  

b.      Derive the corresponding Newton iteration. What is the flop count per iteration?  

c.       How would you choose an initial approximation? Roughly how many iterations are needed? (The machine rounding unit is 2−52.)