Numerical Analysis I, Fall 2017 (http://www.math.nthu.edu.tw/˜ wangwc/)

Midterm 01

Oct 24, 2017.

1. (10 pts) The half precision format uses 16 bits to store a binary floating point number of the form ±1.a_{1}a_{2} ⋯ a_{t} × 2^{e} where a_{j} ∈ \{0, 1\}, −14 ≤ e ≤ 15. Find t and \underline{derive} an upper bound for relative error caused by \underline{rounding}. Express your final answer as a real number, but need not convert it to decimal expression.

Ans:

There are total 30 different exponents (−14 ≤ e ≤ 15). It takes 5 bits to give 30 or more different exponents (2^{5} = 32). (2 pts) Total bits = 1 + t + 5 = 16 ⇒ t = 10 (2 pts).

Let x = ±1.a_{1}a_{2} ⋯ a_{t} … × 2^{e}. If a_{t+1} = 0, then fl_{round}(x) = ±1.a_{1}a_{2} ⋯ a_{t} × 2^{e}. A bound for the relative error is

\frac{|x − fl_{round}(x)|}{|x|} = \frac{|0.a_{t+1}a_{t+2} … |}{|1.a_{1}a_{2} … a_{t}a_{t+1} … |} × 2^{−t} ≤ 2^{−(t+1)}. (2 pts)

If a_{t+1} = 1, then fl_{round}(x) = ±(1.a_{1}a_{2} ⋯ a_{t} + 2^{−t}) × 2^{e}. The upper bound for relative error becomes

\frac{|x − fl_{round}(x)|}{|x|} = \frac{|1 − 0.a_{t+1}a_{t+2} … |}{|1.a_{1}a_{2} … a_{t}a_{t+1} … |} × 2^{−t} ≤ 2^{−(t+1)}. (2 pts)

Therefore, an upper bound for relative error caused by rounding is 2^{−11} (2 pts).

2. (10 pts) Given p_{0}, p_{1} and p_{2}, the general solution to the recursion formula p_{n} = \frac{10}{3}p_{n−1} − 3p_{n−2} + \frac{2}{3}p_{n−3} is p_{n} = c_{1}1^{n} + c_{2}2^{n} + c_{3}(\frac{1}{3})^{n} (need not show this). Find all (c_{1}, c_{2}, c_{3}) ≠ (0, 0, 0) such that the above iteration is unstable in relative error. \underline{Explain}.

Ans: Relative error = |\frac{e_{n}}{p_{n}^{exact}} |. (3 pts)

Note that

e_{n} ≈= d_{1}1^{n} + d_{2}2^{n} + d_{3}(\frac{1}{3})^{n}

d_{1}, d_{2} and d_{3} are of O(δ) (4 pts).

Therefore, relative error = \frac{O(δ)1^{n}+O(δ)2^{n}+O(δ)( \frac{1}{3} )^{n}}{c_{1}1^{n}+c_{2}2^{n}+c_{3}( \frac{1}{3} )^{n}} . It is stable if and only if c_{2} ≠ 0. (3 pts)

3. (10 pts) The first few iteration (p_{i}, f(p_{i})), i = 0, 1, 2, 3, 4 of method of false position for some equation f(x) = 0 is given by

(0, −2), (3, 1), (2, 2), (1, 1), (\frac{2}{3}, \frac{2}{9})

Find p_{5} (4 digits will do). \underline{Explain}.

Ans:

f(p_{1})f(p_{0}) < 0 ⇒ a = p_{0}, b = p_{1}
f(p_{2})f(p_{0}) < 0 ⇒ a = p_{0}, b = p_{2}
f(p_{3})f(p_{0}) < 0 ⇒ a = p_{0}, b = p_{3}
f(p_{4})f(p_{0}) < 0 ⇒ a = p_{0}, b = p_{4}

(up to here = 4 pts)

⇒ p_{5} = p_{4} − f(p_{4})\frac{p_{4} − p_{0}}{f(p_{4}) − f(p_{0})} (4 pts) = 0.6 (2 pts).

4. (15 pts) Use any method to find a solution of \sqrt{1 + 0.9x} − \sqrt{1 − 0.8x} = 1.0 × 10^{−10} to 15 correct digits. You need to prevent loss of accuracy. Standard methods only gives you about 5 correct digits (and 1/3 partial credits).

Ans:

Apply the following identity

a^{2} − b^{2} = (a + b)(a − b)

that avoids the subtraction of two nearly identical numbers and gives

f(x) = \frac{1.7x}{\sqrt{1 + 0.9x} + \sqrt{1 − 0.8x}} − 10^{−10}. (7 pts)

Then solve f(x) = 0 by any numerical method to find the solution

x_{∗} ≈ 1.17647058823875 × 10^{−10}. (8 pts)

5. (10+5 pts) It is known that the unique solution to f(x) = x + 3 sin(x) − 0.01 = 0 is located near x = 0.

(a) Find a fixed point iteration that will converge for any x_{0} ∈ [−\frac{1}{2}, \frac{1}{2}]. Show that your method satisfies the assumptions of a relevant Theorem, but need not prove the Theorem again. You can use the numerical values of sin(\frac{1}{2}), cos(\frac{1}{2}), exp(\frac{1}{2}), etc. in your proof.

(b) Find an N (need not be optimal) such that |x_{n} − x^{∗}| < 10^{−30} for all n ≥ N with x_{0} = 0 (assuming a higher precision floating point arithmetic is used).

Ans:

(a) Direct xed point iteration with g(x) = g_{0}(x) = 0.01 − 3 sin(x) does not converge. Instead, a proper choice of β and g(x) = βx + (1β)g_{0}(x) will result in local convergence (2 pts). One could choose

β = \frac{g′_{0}(ξ)}{g′_{0}(ξ) − 1}

for some ξ near 0. If ξ = 0, then β = \frac{3}{4}. (2 pts) First check g([−\frac{1}{2}, \frac{1}{2}]) ⊂ [−\frac{1}{2}, \frac{1}{2}].

−\frac{1}{2} < −0.012931... = g(−\frac{1}{2}) ≤ g(x) ≤ g(\frac{1}{2}) = 0.017931... < \frac{1}{2} (3 pts)

Second check |g′(x)| ≤ k for some k ∈ (0, 1), ∀ x ∈ (−\frac{1}{2}, \frac{1}{2}).

|g′(x)| = |\frac{3}{4}(1 − cos(x))| ≤ \frac{3}{4} < 1 ∀ x ∈ (−\frac{1}{2}, \frac{1}{2}) (3 pts)

(b) Estimation (3 pts) Result N (2 pts) [Method 1]

|x_{n}−x_{∗}| ≤ k^{n} max\{x_{0}−a, b−x_{0}\} = (\frac{3}{4})^{n} max \{0 − (−\frac{1}{2}) , \frac{1}{2} − 0\} = (\frac{3}{4})^{n} \frac{1}{2} < 10^{−30}

⇒ n > \frac{log_{10} 2 − 30}{log_{10} \frac{3}{4}} = 237.71... ⇒ N = 238.

[Method 2]

|x_{n} − x_{∗}| ≤ \frac{k^{n}}{1 − k} |x_{1} − x_{0}| = 4 (\frac{3}{4})^{n} |g(0) − 0| = (\frac{3}{4})^{n} 0.01 < 10^{−30}

⇒ n > \frac{28}{log_{10} \frac{4}{3}} = 224.11... ⇒ N = 225.

6. (15 pts) Give a cubically convergent method to solve for e^{x} − 1 = 0. Give the formula and prove that it is cubically convergent (locally). If you cannot do it, do the same for a locally quadratically convergent method for partial credit.

Answer:

[Cubic]

One solution is given by (there may be others)

x_{n+1} = g(x_{n}), g(x) = x − \frac{f(x)}{f′(x)} − \frac{f′′(x)}{2f′(x)} [\frac{f(x)}{f′(x)}]^{2} . (5 pts)

Check that g′(p) = g′′(p) = 0 and g^{(3)}(p) ≠ 0, and then compute

lim_{n→∞} \frac{|p_{n+1} − p|}{|p_{n} − p|^{3}} = \frac{|g^{(3)}(p)|}{3!}. (10 pts)

[Quadratic]

x_{n+1} = g(x_{n}), g(x) = x − \frac{f(x)}{f′(x)}. (2 pts)

Check that g′(p) = 0 and g′′(p) ≠ 0, and then compute

lim_{n→∞} \frac{|p_{n+1} − p|}{|p_{n} − p|^{2}} = \frac{|g′′(p)|}{2!}. (5 pts)

7. (10 pts) Derive Aitken’s Δ^{2} acceleration method.

Hint: the starting point is to assume p_{n} converges to p linearly. Ans: Start from the assumption

\frac{p_{n+1} − p}{p_{n} − p} ≈ \frac{p_{n+2} − p}{p_{n+1} − p}.

See derivation in the textbook. Partial credits for partial results.

8. (15 pts) Use any method to solve the nonlinear system of equations

sin(x) + \frac{2y}{1 + x} = 0.01, 5x + sin(\frac{6y}{1 + y^{2}} ) = 0.02.

Write your answer in the format of ’format long e’. Hint: the solution is near (0, 0) where sin x ≈ x, \frac{y}{1+x} ≈ y, etc. to leading orders. Ans: Let

g_{1}(x) = \frac{1}{5} (0.02 − sin (\frac{6y}{1 + y^{2}} ))

g_{2}(x) = \frac{1}{2}(0.01 − sin(x))(1 + x)

and

G(x) = (g_{1}(x), g_{2}(x))^{t}
Ḡ(x) = αx + (I − α)G(x)

where α is a 2 × 2 matrix and I is the identity matrix. One could choose

α = (DG(x_{0}) − I)^{−1}DG(x_{0}).

(up to here = 5 pts) If x_{0} = (0, 0)^{t}, then the iteration gives

x_{∗} ≈ (−4.882452175e − 03, 7.404885005e − 03)^{t}. (10 pts)