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

Brief Answers to Quiz 02

1:20-2:10PM, Oct 16, 2020.

1. Find the smallest N so that |∑_{i=0}^{N} \frac{3^{i}}{i!} − exp(1)^{3}| < 10^{−5}. Let your code print the answer

N and |∑_{i=0}^{N} \frac{3^{i}}{i!} − exp(1)^{3}| on screen, and also write them down on the answer sheet.

Type the error bound 10^{−5} directly in your code, and do not use it as an input. Extra credits for more efficient method(s).

Name your code using your student ID number, quiz number and problem number, such as m107000001 q2p1.m or m108000002 q2p1.c. Extra credits using C, C++, etc.

Ans:

N = 15 (5 pts) absolute error = 2.492E-06 (5 pts) Code (10 pts) Extra points by using C (3 pts) Extra points by nested summation (5 pts)

2. Consider the following recursive formula p_{1} = 1, p_{2} = a, p_{n} = \frac{10}{3}p_{n−1} − p_{n−2}, used as an algorithm to compute p_{N} for a given N. For what values of a is this algorithm stable in relative error? Explain.

Ans:

(a): Exact solution is given by

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

where c_{1} = \frac{81−27a}{24}, c_{2} = \frac{3a−1}{24} ( 10 pts)

(b): Relative error = |\frac{e_{N}}{p_{N}^{exact}} |.

Note that

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

Both d_{1}, d_{2} are of O(ε_{M})

Therefore, relative error = \frac{O(ε_{M})(\frac{1}{3})^{n}+O(ε_{M})3^{n}}{c_{1}(\frac{1}{3})^{n}+c_{2}3^{n}} . ( 5 pts)

It is stable if and only if c_{2} ≠ 0, or a ≠ 1/3. ( 5 pts)

3. The file an.txt contains a sequence stored as ’n, a_{n}’ at nth line and its limit L = lim a_{n} in the comment line. Find its rate of convergence. Express your answer as O(β_{n}) and find β_{n} explicitly. Extra credits for finding the rate without knowing L. Explain how you get the answer and hand in your code.

Ans:

Method 1: Try semilogy or 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. Method 2 (Full credit + extra 10 pts): Proceed to find out the constants C, p or C, α. 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. Ans: a_{n} − L = O(\frac{1}{n})

4. Find a root of x = 2 cos x with 10 correct decimal digits using any numerical method of your choice. Write down (1): the detail formula of your method, (2): x_{0}, x_{1} and (3): the answer x^{∗}, on the answer sheet. Double check that your answer indeed satisfies the equation before you write them down. Need not hand in the code if you are sure about your answer. Ans: Correct formula of the chosen method: (5 pts) Correct answer x^{∗} ≈ 1.029866529 (15 pts)

5. Show that the nonlinear equation x = 1 + \frac{1}{2} cos(x) 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. You can use any theorem(s) on the textbook directly and need not prove the theorem(s) in advance, as long as you state the theorem(s) correctly. Ans: Existence proof: Show that g[1, 1.5] ⊂ [1.1/5] and |g′(x)| ≤ k < 1 on [1.1/5]. (5 pts); Correct error estimation: (10 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 credits for estimate. Direct simulation to give N will get no credits for estimate and no credits for N.