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$
$$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$
Comments
Post a Comment