$$該死的數值作業1$$
### Q1

Find the rate of convergence of the following sequence as $n\rightarrow\infty$

$\mbox{(a)}$ $\displaystyle \sin\frac{1}{n}$$,$ $\mbox{(b)}$ $\displaystyle\sin\frac{1}{n^2}$$,$ $\mbox{(c)}$ $\displaystyle \left(\sin\frac{1}{n}\right)^2$

#### Sol
We know that
$$\sin(x)\leq {x}，\text{for} \mbox{ 0 } \leq x<1$$
$\mbox{(a)}$
$$\lim_{n \rightarrow \infty }\sin(\frac{1}{n})=0$$
we have
$$|\sin\left(\frac{1}{n}\right)|<\frac{1}{n}$$
so,
$$\sin(\frac{1}{n})=O(\frac{1}{n})$$
$\mbox{(b)}$
$$\lim_{n \rightarrow \infty }\sin(\frac{1}{n^2})=0$$
we have
$$|\sin(\frac{1}{n^2})|<\frac{1}{n^2}$$
so,
$$\sin(\frac{1}{n^2})=O(\frac{1}{n^2})$$
$\mbox{(c)}$
By$\mbox{(a)}$
$$|\sin(\frac{1}{n})|<(\frac{1}{n})$$
we can get
$$|\sin(\frac{1}{n})|^2<(\frac{1}{n})^2$$
so,
$$(\sin(\frac{1}{n}))^2=O(\frac{1}{n^2})$$

------

### Q2

* Find the number of multiplication and additions are required to determine a sum of the form
$$
\displaystyle\sum_{i=1}^n\sum_{j=1}^ia_ib_j
$$
* Give an algorithm to reduce the number of computations

#### Sol
* There are $(\frac{n^2+n}{2}-1)$ additions and $(\frac{n^2+n}{2})$ multiplications

* int n;
int i;
int j;
int k;
for(i=1;i<n+1;i++)
{
for(j=1;j<i+1;j++)
{
k+="+b_%d",j; //沒試過能不能+=字串><，只是想要最後print出我的結果
}
print("a_%d*(%d)");
k="";
}

------

### Q3

* The following methods are proposed to compute $21^{1/3}$, rank them in order, bases on there apparent speed of convergence, with $p_0=1$, and show your numerical result of convergence with $\displaystyle\frac{|p_n-21^{1/3}|}{21^{1/3}}<1e-2$.

1. $p_n = \displaystyle\frac{20p_{n-1}+21/p_{n-1}^2}{21}$

2. $p_n = p_{n-1}-\displaystyle\frac{p_{n-1}^3-21}{3p_{n-1}^2}$

3. $p_n = p_{n-1}-\displaystyle\frac{p_{n-1}^4-21p_{n-1}}{p_{n-1}^2-21}$

4. $p_n = \left(\displaystyle\frac{21}{p_{n-1}}\right)^{1/2}$

#### Sol
$$b>d>a>c$$

$\quad\quad\quad\qquad\qquad\qquad\qquad By\quad excel$

------
### Q5
* Let $p$ be the root of $f(x) = 0$, with $f$ is at least $C^2$, please show that the Newton Method for finding the root of $f$ is at least quadratic.
* Show that the rate of convergence of secent method is $\displaystyle\frac{1+\sqrt{5}}{2}$
#### Sol
* By Taylor's theorem and Lagrange form of the Taylor series expansion remainder,then the expansion of $f (p)$ about $x_n$ is
$$0=f(p)=f(x_n)+f'(x_n)(p-x_n)+\frac{1}{2} f''(ξn)(p-x_n)^2$$
$$\text{Dividing by }f'(x_n),$$
$$\frac{f(x_n)}{f'(x_n)}+(p-x_n)=\frac{-f''(ξn)}{2f(x_n)}(p-x_n)^2$$
$$x_\text{n+1} \text{ is defined by}$$
$$x_\text{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}$$
Then,
$$p-x_\text{n+1}=\frac{-f''(ξn)}{2f(x_n)}(p-x_n)^2$$
That is,
$$ε_\text{n+1}=\frac{-f''(ξn)}{2f(x_n)}ε_n ^\text{ 2}$$
$$|ε_\text{n+1}|=\frac{|f''(ξn)|}{2|f(x_n)|}ε_n ^\text{ 2}$$
the root of $f$ is at least quadratic.

* The secant method is defined by the recurrence relation
$$x_\text{n+1}=\frac{f(x_n)x_\text{n-1}-f(x_\text{n-1})x_n}{f(x_n)-x_\text{n-1}}$$
Say $f(ξ)=0$ and $e_n=(ξ-x_n)$ i.e the error in the n$^{th}$ iteration in estimating ξ.
$$x_\text{n+1}=e_\text{n+1}+ξ$$$$x_n=e_n+ξ$$$$x_\text{n-1}=e_\text{n-1}+ξ$$
By above,we get
$$e_\text{n+1}=\frac{e_\text{n-1}f(x_n)-f(e_\text{n-1})e_n}{f(x_n)-f(x_\text{n-1})}$$
By Mean value Theorem, $\exists \quad a,\eta_{n}$ in the interval $x_{n}$ and $ξ$ s.t
$$f'(\eta_{n})=\frac{f(x_n)-f(ξ)}{x_n-ξ}$$
$$\text{because }f(ξ)=0,x_n-ξ=e_n$$
we get
$$f'(\eta_{n})=\frac{f(x_n)}{e_n}$$
i.e.
$$f(x_n)=e_nf'(\eta_{n})$$
Using above, we get
$$f(x_\text{n-1})=e_\text{n-1}f'(\eta_{n-1})$$
so,
$$e_{n+1}=e_ne_{n-1}\frac{f'(\eta_{n})-f'(\eta_{n-1})}{f(x_n)-f(x_{n-1})}$$
i.e.
$$e_{n+1}\propto e_ne_{n-1}$$
By def of rate of convergence , the method is of order p if
$$e_n\propto e_{n-1}^ p$$
i.e.
$$e_{n+1}\propto e_n^p$$
Then,we get
$$p=\frac{(p+1)}{p}$$
i.e.
$$p^2-p-1=0$$
$\displaystyle \Rightarrow
p=\frac{1\pm\sqrt{5}}{2}$

------
### Q6
Please use Newton method for finding the root of $f(x) = x(x-1)^2$ where $p_0 = 1.5$.
#### Sol
$f(x)=x(x-1)^2=0$ $\Rightarrow f'(x)=3x^2-4x+1$
From $p_0$=1.5
$$p_1=p_0-\frac{f(p_0)}{f'(p_0)}$$
$$p_2=p_1-\frac{f(p_1)}{f'(p_1)}$$
$$p_3=p_2-\frac{f(p_2)}{f'(p_2)}$$
$$p_4=p_3-\frac{f(p_3)}{f'(p_3)}$$
$$p_5=p_4-\frac{f(p_4)}{f'(p_4)}$$
$$p_6=p_5-\frac{f(p_5)}{f'(p_5)}$$
$$....$$
$$....$$

$\quad\quad By\quad excel$

we can observe the drawing, $i\rightarrow \infty$ then $p_i\rightarrow 1$.
$$\text{The answer is } 1.$$

------

### Q7
A sequence $\left\{p_n\right\}$ is said to be superlinear convergent to $p$ if
$$
\lim_{n\rightarrow\infty} \displaystyle\frac{|p_{n+1}-p|}{|p_n-p|}=0
$$
* Show that if $p_n\rightarrow p$ in order $\alpha>1$, then $\left\{p_n\right\}$ is superlinear convergent to $p$.
* Show that $p_n = \frac{1}{n^n}$ is super linear convergent to 0 but doesn't convergent to 0 of order $\alpha>1$.

#### Sol
* $$\displaystyle\lim_{n\rightarrow\infty}\frac{|p_{n+1}-p|}{|p_n-p|}=\lim_{n\rightarrow\infty}\left(\frac{|p_{n+1}-p|}{|p_n-p|^\alpha}\frac{1}{|p_n-p|^{\alpha-1}}\right)$$
$$\displaystyle=c\lim_{n\rightarrow\infty}\frac{1}{|p_n-p|^{\alpha-1}}
\displaystyle=c\lim_{n\rightarrow\infty}|p_n-p|^{1-\alpha}
=0$$
Therefore, if $p_n\rightarrow p$ in order $\alpha>1$, then $\left\{p_n\right\}$ is superlinear convergent to $p$.

* We know$$\displaystyle\frac{|p_{n+1}|}{|p_n|^\alpha}=\frac{\left(n+1\right)^{-\left(n+1\right)}}{n^{-\alpha{n}}}=\frac{n^{\alpha{n}}}{\left(n+1\right)^{\left(n+1\right)}}=\frac{\frac{n^{\alpha{n}}}{n^{\left(n+1\right)}}}{1+\frac{\left(n+1\right)^{\left(n+1\right)}-n^{\left(n+1\right)}}{n^{\left(n+1\right)}}}$$
Then
$$\displaystyle\lim_{n\rightarrow\infty}\frac{|p_{n+1}|}{|p_n|^\alpha}=\lim_{n\rightarrow\infty}\frac{n^{\alpha{n}}}{n^{\left(n+1\right)}}=\lim_{n\rightarrow\infty}n^{\left(\alpha-1\right)n-1}\rightarrow\infty \text{ , if } \displaystyle\alpha>1$$
$$\displaystyle\lim_{n\rightarrow\infty}\frac{|p_{n+1}|}{|p_n|}=\lim_{n\rightarrow\infty}\frac{n^n}{n^{\left(n+1\right)}}=\lim_{n\rightarrow\infty}n^{-1}=0\text{ , if } \displaystyle\alpha=1$$
Therefore, $p_n = \frac{1}{n^n}$ is super linear convergent to 0 but doesn't convergent to 0 of order $\alpha>1$.

------

### Q8 (程式題)
In this problem, you should write functions(Code) for Newton method and secent method and paste in here.

Use Newton method and Secant to find solution accurate to within TOL = $10^{-5}$ for the following problems.
On the other hand,
* $2x\cos(2x)-(x-2)^2=0 \mbox{ for } x\in \left[2,3\right]\mbox{ and }\left[3,4\right]$
* $e^x-3x^2 = 0 \mbox{ for } x\in \left[0,1\right], \left[3,4\right]\mbox{ and }\left[6,7\right]$

#### Sol

$$Newton\quad method$$

*
from math import sin, cos
def new_func(x):
temp = 2*x*cos(2*x) - (x - 2)**2
return temp
def diff_func(x):
temp = -4*x*sin(2*x) - 2*x + 2*cos(2*x) + 4
return temp
def newton(p0, tol):
n=0
while(1):
p = p0 - new_func(p0) / diff_func(p0)
n+=1
if n==30:
break
print ('p0 = ' + str(p0))
p0 = p
print('p = ' + str(p))
newton(2.5, 1) <--有其他區間就把2.5改成那個區間的中點(其實也不一定要中點)

$$Secant\quad method$$
*
from math import exp
def new_func(x):
temp = exp(x)-3*x**2
return temp
def newton(p0, p1, tol):
n=0
while(1):
p = p1 - (p1 - p0)*new_func(p1) / (new_func(p1) - new_func(p0))
n+=1
if n==30:
break
print('p0 = ' + str(p0))
p0 = p1
print('p1 = ' + str(p1))
p1=p
print('p = ' + str(p))
newton(3.5, 3.6, 1)<--有其他區間就把3.5和3.6改成在那個區間任取兩點