MATH565-Homework 2 Solved

1.   Find the rate of convergence of the sequence

                                                                                                                                                    (1)

as n → ∞.

2.   Show that the sequence

                                                                                                                                                           (2)

converges linearly.

3.   Compute the limit and determine the corresponding rate of convergence for the function

                                                                                                                                        (3)

4.   The following Matlab code produces the output shown below

x = 1; for k = 1:1074 x = x/2;

fprintf(’%-7d %20.16e\n’,k, x); end fprintf(’\n’); fprintf(’%10s %16.8e\n’,’realmin’,realmin); fprintf(’%10s %16.8e\n’,’x’,x);

Output

1                     5.0000000000000000e-01

2                     2.5000000000000000e-01

3                     1.2500000000000000e-01

4                     6.2500000000000000e-02

...............................

1071            3.9525251667299724e-323

1072            1.9762625833649862e-323

1073            9.8813129168249309e-324

1074            4.9406564584124654e-324

realmin 2.22507386e-308 x 4.94065646e-324

For the following, you are asked to show both the binary and 64-bit representation of the requested values. The binary representation should be of the form

                                                                    (1 + b12−1 + b22−2 + b32−3 + ...) × 2β                                                                                  (4)

where bi = 0 or 1, and β is an integer exponent. The 64-bit representation is a string of 64 0s and 1s.

(a)   What is the value of iterate 52? Show the binary and 64-bit representations of this iterate. Whatis the name we often give to this number?

(b)   Which iterate produces the value realmin? Show the binary and 64-bit representation of this number.

(c)    Show the binary and 64-bit representations for the last value of x shown, and be sure to mention any IEEE floating point conventions that are involved. What is the name we give to these values smaller than realmin?

(d)   Had the loop continued one more iteration, what would the resulting value of x be? Explain why.

(e)   Using the Float-Toy (http://evanw.github.io/float-toy/)), give an example of a number less realmin that is not generated by the iterations above.

5.   In class, we showed that

                                                                                                                                  (5)

as x → 0. We then argued that

                                                                                                                                          (6)

for x close to 0, and concluced that the ”rate of convergence” of f(x) is O(x2). To get to this conclusion, however, we simply disregarded all higher order terms in the Taylor Series expansion of f(x), without justification.

Do the following to convince yourself, using graphic and analytic means, that the conclusion is justified.

(a)   Provide convincing graphical evidence that f(x) converges like O(x2) as x → 0.

•   Plot |f(x) − 1/2| and x2/8 on the same graph to see the convergence behavior of f(x).

•   Use small enough values of x to really see the behavior near 0. In Matlab, for example, use

x = logspace(-3,-1,500)

This creates a sequence of values xi that are equally spaced in a logarithmic scale. That is, xi = 10pi, where the p1 = −3, p500 = −1 and the remaining pi are equally spaced values between −3 and −1.

•   To see the behavior clearly, use a log scale for the y-axis. In Matlab, you can set the scale of the y-axis using set(gca,’yscale’,’log’)

(b)   (Math 565.) Use the Remainder Theorem to show formally that we are justified in claiming that the rate of convergence of f(x) is O(x2). Is our choice of λ = 1/8 reasonable?

6.   Recreate the plot you created for Problem 5, but this time use very small values of x, i.e.

x = logspace(-6,-3,500)

You should see very strange behavior for x less than about 10−4. This behavior is the result of ”catastrophic cancellation”. To understand this, consider the following expression

                                                                           1                                               (7)

(a)   Show in finite precision arithmetic (roughly 16 decimal digits), we are justified in approximatingg(ε) as

                                                                                                                                              (8)

for ε . 10−4. Hint: What is the size of the next term in the Taylor Series for g(ε)?

(b)   Show the result of each operation needed to evaluate f(ε), given by

                                                                                                                                    (9)

in finite precision arithmetic, for ε = 10−4. Explain how ”garbage” digits can appear in the calculation, resulting in the strange behavior you see in your plot of f(x).

(c)    For what value of ε do you expect to see almost no digits of accuracy in your evaluation of f(ε)?

(d)   Recreate the plot from Problem 5 for these very small values, but this time use the Taylor Seriesapproximation to f(x). Include terms up to x6. 7. (Math 565). Consider the sequence of partial sums

n

Sn(x) = 1 − x + x2 − x3 + ... + (−1)nxn = X(−1)kxk

k=0

for |x| < 1.

(a) Numerically generate values of Sn(x) for x = 1/π. Show that the error sequence
(10)
                                                                                                                           (11)

converges linearly with asymptotic error constant x. Turn in your numerically generated sequence of values, and convincing numerical evidence that the sequence converges linearly.

(b) Show analytically that the sequence Sn(x) converges linearly.