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

Quiz 02

Oct 13, 2017.

1. Consider the following recursive equation p_{0} = 1, p_{1} = a_{1}, p_{n} = \frac{10}{3}p_{n−1} − p_{n−2}. For what values of a_{1} is it stable in relative error? Explain. Ans: (25 pts + extra 15 pts) (a): Exact solution is given by

p_{n}^{exact} = c_{1} (\frac{1}{3})^{n} + c_{2}3^{n}

where c_{1} = \frac{9−3a_{1}}{8} , c_{2} = \frac{3a_{1}−1}{8} ( 10 pts) (b): Relative error = |\frac{e_{n}}{p_{n}^{exact}} |. ( 8 pts) Note that

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

Both d_{1}, d_{2} are of O(δ) (7 pts). Therefore, relative error = \frac{O(δ)(\frac{1}{3})^{n}+O(δ)3^{n}}{c_{1}(\frac{1}{3})^{n}+c_{2}3^{n}} . It is stable if and only if c_{2} ≠ 0, or a_{1} ≠ 1/3. ( extra 15 pts)

2. The file an.txt contains a sequence stored as ’n, a_{n}’ at nth line. Find its rate of convergence. Express your answer as O(β_{n}) and find β_{n} explicitly. Show details. Ans: (0 pts + extra 20 pts): Standard procedure: step 1: try semilogy and loglog plot of |a_{n} − L| vs n (where L = lim a_{n}) to determine whether a_{n} − L ≈ Cn^{−p} or a_{n} − L ≈ Cα^{−n} or something else. step 2: Proceed to find out the constants C, p or C, α. Here I forgot to put the limit L in the problem, therefore one can not perform step 1 easily (one could, but not straightforwardly). Extra 20 pts: Directly try a_{n} − L ≈ Cn^{−p} and find p through

p ≈ log_{2} \frac{a_{N} − a_{2N}}{a_{2N} − a_{4N}}

Different choices of N = 30, 50, ⋯, 100, 125 all give consistent answer p ≈ 1 (15 pts). Ans: a_{n} − L = O(\frac{1}{n}) (5 pts).

3. Find a root of x = 2 cos x with 10 correct decimal digits using any numerical method of your choice. Put (1): the detail formula, (2): x_{0}, x_{1} and (3): the answer x^{∗}, on the answer sheet, but need not hand in the code. Ans: (25 pts) Correct formula: (15 pts), correct answer x^{∗} ≈ 1.029866529 (10 pts)

4. Show that the nonlinear equation x = 1 + cos(x)/2 has a solution in [1, 1.5]. Let x_{0} = 1.25, give an estimate on N (need not be optimal) such that |x_{n} − x^{∗}| < 10^{−5} for all n ≥ N. Ans: (25 pts) Existence proof: 5 pts; Correct estimation: (15 pts); Correct N resulting from the estimate: (5 pts). Possible estimate include Fixed point iteration: Let g(x) = 1 + \frac{cos x}{2}. Then |g′(x)| = | − \frac{sin x}{2}| ≤ \frac{1}{2} =: k. \underline{Estimate 1}:

|x_{n} − x^{∗}| ≤ k^{n} max\{x_{0} − a, b − x_{0}\} = \frac{1}{2^{n+2}} < 10^{−5}

⇒ n ≥ 14.60... ⇒ N = 15.

or \underline{Estimate 2}:

|x_{n} − x^{∗}| ≤ \frac{k^{n}}{1 − k} |x_{1} − x_{0}| = \frac{1}{2^{n+1}} |2 cos(1.25) − 1| < 10^{−5}

⇒ n ≥ 14.17... ⇒ N = 15.

Bisection: Use Theorem 2.1 to estimate |x_{n} − x^{∗}|. Newton’s Method: Use x_{n+1}−x^{∗} = \frac{g′′(ξ_{n})}{2}(x_{n}−x^{∗})^{2} (section 2.4) to give an estimate. Any method with correct estimate will receive full 15 pts for estimate. Direct simulation to give N will get no credits for estimate and no credits for N.

5. The first few iteration (p_{i}, f(p_{i})), i = 0, 1, 2, 3 of method of false position for some equation f(x) = 0 is given in q2p5.txt. Find p_{4} (4 digits will do). Also give your formula for finding p_{4} and explain. Ans: (25 pts)

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

(up to here = 10 pts)

⇒ p_{4} = p_{3} − f(p_{3})\frac{p_{3} − p_{1}}{f(p_{3}) − f(p_{1})} (10 pts) ≈ 0.8421 (5 pts).