Numerical Analysis HW1 (Due 10/6)

# Numerical Analysis HW1 (Due 10/6) ###### tags: `Numerical Analysis` ### 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 **p.34** ------ ### 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 * * 請寫下演算法 ``` For i=1...n : do ... end for... ``` ------ ### 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 Let $f(x) = (20x+21/x^2)/21, x-(x^3-21)/3x^2 \cdots$ 然後比較微分在區間內的大小 ------  ### 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 atleast quadratic. * Show that the rate of convergence of secent method is $\displaystyle\frac{1+\sqrt{5}}{2}$ #### Sol **p.80** ------ ### Q6 Please use Newton method for finding the root of $f(x) = x(x-1)^2$ where $p_0 = 1.5$. #### Sol **p.83** ------ ### 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 Since $\alpha>1$, leads $|p_n-p|^{\alpha-1}\rightarrow 0$ ------ ### 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 ##### Code requirement Please write a function named as newton, with input (p0, TOL) and output solution Please write a function named as secant, with input (p0, p1, TOL) and output solution For example： ```[python] def newton(p_0, TOL): for i in range(100): p = p_0*i+TOL p_0 = p return p_0 ``` ------