\begin{enumerate}
\item
Consider the following recursive equation
$p_0 = 1, \quad p_1 = a_1, \quad p_n = {10\over 3} p_{n-1} - p_{n-2}.$
For what values of $a_1$ is it stable in relative error? Explain.

\noindent{\bf Ans}: {\bf(25 pts + extra 15 pts)} 

{\bf (a)}: Exact solution is given by
$$
p_n^{\rm exact} = c_1\left(\frac{1}{3}\right)^n + c_2 3^n
$$
where $c_1 = {9- 3 a_1 \over 8}$, $c_2 = {3 a_1 -1 \over 8}$ ( {\bf 10 pts})
    
{\bf (b)}: Relative error $ = \left| {e_n \over p_n^{\rm exact}} \right |$. 
 ( {\bf 8 pts})

Note that 
$$
e_n \approx d_1\left(\frac{1}{3}\right)^n + d_2 3^n  
$$
Both $d_1$, $d_2$ are of $O(\delta)$ {\bf (7 pts)}.

Therefore, relative error
$ = 
{ O(\delta) \left(\frac{1}{3}\right)^n + O(\delta) 3^n
\over
c_1\left(\frac{1}{3}\right)^n + c_2 3^n
}.
$ 
It is 
stable if and only if $c_2 \neq 0$, or $a_1 \neq 1/3$. ( {\bf extra 15 pts})

\item
The file an.txt contains a sequence stored as '$n, a_n$' at $n$th line. 
Find its rate of convergence. Express your answer as $O(\beta_n)$ and
find $\beta_n$ explicitly. Show details. 

\noindent{\bf Ans}: { \bf(0 pts + extra 20 pts)}:

Standard procedure:

{\bf step 1}:
try semilogy and loglog plot of $ |a_n -L|$ vs $n$ (where $L= \lim a_n$)
to determine whether 
$a_n - L \approx C n^{-p}$ or
$a_n - L \approx C \alpha^{-n}$ or something else.

{\bf step 2}:

Proceed to find out the constants $C, p$ or $C, \alpha$.

{\bf Here I forgot to put the limit $L$ in the problem}, therefore one 
can not perform step 1 easily (one could, but not straightforwardly).

{\bf Extra 20 pts}:

Directly try $a_n - L \approx C n^{-p}$ and find $p$ through
$$
p \approx \log_2 { a_N - a_{2N} \over a_{2N} - a_{4N} } 
$$
Different choices of $N = 30, 50, \cdots, 100, 125$
all give consistent answer $p \approx 1$ {\bf (15 pts)}.

{\bf Ans}: $a_n -L = O({1 \over n})$ {\bf (5 pts)}.

\item
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.

\noindent{\bf Ans}: {\bf(25 pts)} 


Correct formula: {\bf(15 pts)}, % (2) {\bf(5 pts)} 
correct answer $x^* \approx 1.029866529$ {\bf(10 pts)}

\item
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 \geq N$.

\noindent{\bf Ans}: {\bf(25 pts)} 
Existence proof: {\bf 5 pts};
Correct estimation: {\bf(15 pts)}; Correct $N$ resulting from the 
estimate: {\bf(5 pts)}.

Possible estimate include

{\noindent \bf Fixed point iteration}: 
Let $g(x) = 1 + \frac{\cos x}{2}$. 
Then $|g'(x)| = |-\frac{\sin x}{2}| \leq \frac{1}{2} =: k$.

\underline{Estimate 1}:\\
$$
|x_n-x^*| \leq k^n \max\{x_0-a,b-x_0\} = \frac{1}{2^{n+2}} < 10^{-5}
$$
$$
\Rightarrow n \geq 14.60... \Rightarrow N = 15.
$$
or

\underline{Estimate 2}:\\
$$
|x_n-x^*| \leq \frac{k^n}{1-k} |x_1-x_0| = \frac{1}{2^{n+1}}|2\cos(1.25)-1| < 10^{-5}
$$
$$
\Rightarrow n \geq 14.17... \Rightarrow N = 15.
$$

{\noindent \bf Bisection}: 
Use Theorem 2.1 to estimate $ |x_n - x^* |$.

{\noindent \bf Newton's Method}: 
Use $x_{n+1}-x^* = {g''(\xi_n) \over 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$.

\item
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.

\noindent{\bf Ans}: {\bf(25 pts)} 

$$f(p_1)f(p_0)<0 \Rightarrow a=p_0,\; b=p_1\;$$
$$f(p_2)f(p_1)<0 \Rightarrow a=p_1,\; b=p_2\;$$  
$$f(p_3)f(p_2)>0 \Rightarrow a=p_1,\; b=p_3\;$$
{\bf(up to here = 10 pts)}
$$
\Rightarrow p_4 = p_3-f(p_3)\frac{p_3-p_1}{f(p_3)-f(p_1)}\;\textrm{{\bf(10 pts)}}\; \approx 0.8421\;\textrm{{\bf(5 pts)}}.
$$
\end{enumerate}