Solution of Equations & Differentiation(Numerical Method)

Bisection Method

$$e^{-x}=x$$

Use bisection method to find a root on the interval $[0,1]$

Solution:

Let $f(x)=e^{-x}-x, x\in [0,1]$

$f$ is continuos and since $f(0)=1$ and $f(1)=-0.6321$, by the Intermediate Value Theorem, there exists a root in $[0,1]$

Let $a^{(0)} = 0$ and $b^{(0)}=1$

$$\begin{array}{c|c|c|c|c|c|c}k&a^{(k)}&f(a^{(k)})&b^{(k)}&f(b^{(k)})&\frac{a^{(k)}+b^{(k)}}{2}&f(\frac{a^{(k)}+b^{(k)}}{2})\\\hline 0&0 &1&1&-0.6321&0.5&0.1065\\\end{array}$$

Compare $f(a^{(k)})|f(\frac{a^{(k)}+b^{(k)}}{2})|f(b^{(k)})$ and choose the two value with opposite sign and insert into the next row

$$\Rightarrow 1|\underbrace{0.1065|-0.6321}_\text{ opposite sign }$$

Let $a^{(1)} = 0.5$ and $b^{(1)}=1$

$$\begin{array}{c|c|c|c|c|c|c}k&a^{(k)}&f(a^{(k)})&b^{(k)}&f(b^{(k)})&\frac{a^{(k)}+b^{(k)}}{2}&f(\frac{a^{(k)}+b^{(k)}}{2})\\\hline 1&0.5 &0.1065&1&-0.6321&0.75&-0.2776\\\end{array}$$

Compare $f(a^{(k)})|f(\frac{a^{(k)}+b^{(k)}}{2})|f(b^{(k)})$
$$\Rightarrow \underbrace{0.1065|-0.2776}_\text{opposite sign}|-0.6321$$

Let $a^{(2)} = 0.5$ and $b^{(2)}=0.75$

$$\begin{array}{c|c|c|c|c|c|c}k&a^{(k)}&f(a^{(k)})&b^{(k)}&f(b^{(k)})&\frac{a^{(k)}+b^{(k)}}{2}&f(\frac{a^{(k)}+b^{(k)}}{2})\\\hline 2&0.5 &0.1065&0.75&-0.2776&0.625&-0.0897\\\end{array}$$

Compare $f(a^{(k)})|f(\frac{a^{(k)}+b^{(k)}}{2})|f(b^{(k)})$
$$\Rightarrow \underbrace{0.1065|-0.0897}_\text{opposite sign}|-0.2776$$

Let $a^{(3)} = 0.5$ and $b^{(3)}=0.625$

$$\begin{array}{c|c|c|c|c|c|c}k&a^{(k)}&f(a^{(k)})&b^{(k)}&f(b^{(k)})&\frac{a^{(k)}+b^{(k)}}{2}&f(\frac{a^{(k)}+b^{(k)}}{2})\\\hline 3&0.5 &0.1065&0.625&-0.0897&\cdots&\cdots\\\end{array}$$

**To approximate how many iterations will bisection method get to a certain accuracy**
 Use the formula :$\frac{b-a}{2^n}>\varepsilon$(accuracy) 

Assume $\varepsilon=10^{-4},x\in[0,1]$, $a=0,b=1$

By applying the formula:

$$\begin{matrix}\frac{1-0}{2^n}>10^{-4}\\n \log{2}>log{\frac{1}{10^{-4}}}\\n>13.2877\\n\approx 14\end{matrix}$$

$\therefore$ Approximately, 14 iterations will get an accuracy of $10^{-4}$

---

Newton's Method

$$f(x)=-x^{3}-\cos{x}$$

Use Newton's method to find $x_2$, with $x_0=-1$

Solution:

General Formula: $$x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}$$

Step 1: Find the derivative of $f(x)$

$$f'(x)=-3x^{2}+\sin{x}$$

Step 2: Apply the general formula with $k=0,1,2,3,...$

When k=0,

$$\begin{align}x_1 &=x_0 - \frac{-(x_0)^{3}-\cos(x_0)}{-3(x_0)^{2}+\sin(x_0)}\\&=(-1)-\frac{-(-1)^{3}-\cos(-1)}{-3(-1)^{2}+\sin(-1)}\\&=-0.88033290\\\end{align}$$

When k=1,

$$\begin{align}x_2 &=x_1 - \frac{-(x_1)^{3}-\cos(x_1)}{-3(x_1)^{2}+\sin(x_1)}\\&=(-0.88033290)-\frac{-(-0.88033290)^{3}-\cos(-0.88033290)}{-3(-0.88033290)^{2}+\sin(-0.88033290)}\\&=-0.865684\\\end{align}$$

---

Secant Method

$$f(x)=x^{2}-6,x_0=3,x_1=2$$

Use Secant method to find $x_3$

Solution:

General Formula: $$x_{k+1} = x_k - \frac{x_k - x_{k-1}}{f(x_k)-f(x_{k-1})}f(x_k)$$

Apply the general formula with $k=1,2,3,...$

When k=1,

$$\begin{align}x_2&=x_1-\frac{x_1 - x_0}{f(x_1)-f(x_0)}f(x_1)\\&=2-\frac{2-3}{-2-(3)}(-2)\\&=2.4\end{align}$$

When k=2,

$$\begin{align}x_3&=x_2-\frac{x_2 - x_1}{f(x_2)-f(x_1)}f(x_2)\\&=2.4-\frac{2.4-2}{-0.24-(-2)}(-0.24)\\&=2.454545\end{align}$$

---

Richardson's Extrapolation

$$f(x)=x^2 \cos x$$

Find an approximation to $f'(1.0)$ with Richardson's extrapolation with $h=0.1$ to an order $O(h^8)$

Solution:

$$\begin{array}{c|cccc}h & N_1(h)=\frac{f(1.0+h)-f(1.0-h)}{2h},O(h^2)&N_2(h)=\frac{2^2 N_1(\frac{h}{2})-N_1(h)}{2^2 -1},O(h^4) &N_3(h)=\frac{2^4 N_2(\frac{h}{2})-N_2(h)}{2^4 -1},O(h^6)&N_4(h)=\frac{2^6 N_3(\frac{h}{2})-N_3(h)}{2^6 -1},O(h^8)\\\hline 0.1 &N_1(0.1)=\frac{f(1.0+0.1)-f(1.0-0.1)}{2(0.1)} \\ 0.05 &N_1(0.05)=\frac{f(1.0+0.05)-f(1.0-0.05)}{2(0.05)}&N_2(0.1)=\frac{2^2 (N_1(0.05))-(N_1(0.1))}{2^2 -1}\\0.025 & N_1(0.025)=\frac{f(1.0+0.025)-f(1.0-0.025)}{2(0.025)} & N_2(0.05)=\frac{2^2 (N_1(0.025))-N_1(0.05)}{2^2 -1} & N_3(0.1)=\frac{2^4 (N_2(0.05))-N_2(0.1)}{2^4 -1}\\ 0.0125 & N_1(0.0125)=\frac{f(1.0+0.0125)-f(1.0-0.0125)}{2(0.0125)} & N_2(0.025)=\frac{2^2 (N_1(0.0125))-N_1(0.025)}{2^2 -1} & N_3(0.05)=\frac{2^4 (N_2(0.025))-N_2(0.05)}{2^4 -1} & N_4(0.1)=\frac{2^6 (N_3(0.05))-N_3(0.1)}{2^6 -1}\\\end{array}$$


$$\begin{array}{c|cccc}h & N_1(h)=\frac{f(1.0+h)-f(1.0-h)}{2h},O(h^2)&N_2(h)=\frac{2^2 N_1(\frac{h}{2})-N_1(h)}{2^2 -1},O(h^4) &N_3(h)=\frac{2^4 N_2(\frac{h}{2})-N_2(h)}{2^4 -1},O(h^6)&N_4(h)=\frac{2^6 N_3(\frac{h}{2})-N_3(h)}{2^6 -1},O(h^8)\\\hline 0.1 & N_1(0.1)=0.226736\\0.05 & N_1(0.05)=0.236031 & N_2(0.1)=0.239129\\0.025 & N_1(0.025)=0.238358 & N_2(0.05)=0.239134&N_3(0.1)=0.239134\\0.0125 & N_1(0.0125)=0.238940&N_2(0.025)=0.239134&N_3(0.05)=0.239134&N_4(0.1)=0.239134\end{array}$$


$\therefore f'(1.0) \approx 0.239134$