Numerical-Computation-As-2

Question 1.

(a) Use the Intermediate Value Theorem to find an interval of length one that contains a root of the equation:

$$(1)x^3=9,(2)3x^3+x^2=x+5,(3){\cos }^{2}x+6=x$$

We need to find an interval of length one, $[a,b]$ where $b-a=1$, such that $f(a)$ and $f(b)$ have opposite signs.

(1) let $f(x)=x^3-9$ and $a=2,b=3$

• $f(a)=-1<0$
• $f(b)=18>0$

Therefore, the interval is $[2,3]$.

(2) let $g(x)=3x^3+x^2-x-5$ and $a=1,b=2$

• $g(a)=-2$
• $g(b)=24+4-2-5=21$

Therefore, the interval is $[1,2]$.

(3) let $h(x)=co{s}^{2}x-x+6$ and $a=6,b=7$

• $h(a)=co{s}^{2}6\approx 0.9219$
• $h(b)=co{s}^{2}7-1\approx -0.4316<0$

Therefore, the interval is $[6,7]$.

(b) By the Bisection Method, how many steps are needed to have an approximate root within $\frac{1}{8}$ of the true root using the interval you found in (a), and why?

The error Formula:

$$|p-c_n|\le \frac{b-a}{2^{n+1}}$$

Since $b-a=1$ Therefore $\frac{1}{2^{n+1}}<\frac{1}{8}$ Then $n>2$ so $n=3$

3 steps are needed to guarantee that the approximate root is within $\frac{1}{8}$ of the true root for all three cases. This is because with an initial interval of length 1, four iterations will reduce the error bound to $\frac{1}{2^4}=\frac{1}{16}$, which is less than $\frac{1}{8}$​. Three steps would only guarantee an error within $\frac{1}{2^3}=\frac{1}{8}$​, which is not strictly within $\frac{1}{8}$.

(c) Consider three equations. Apply two steps of the Bisection Method to find an approximate root.

(1) Equation: $x^3=9$

Let $f(x)=x^3-9$. The initial interval is $[a_0,b_0]=[2,3]$.

Step 1:

$$f(2)=-1,f(3)=18>0$$$$f(2)f(3)<0$$$$c=\frac{2+3}{2}=2.5>0$$

Therefore $a_1=2,b_1=2.5$ $$f(2)=-1<0, f(2.5)=\frac{53}{8}>0$$

Step 2:

$$c=2.25$$$$f(2.25)>0$$

Therefore $$a_2=2, b_2=2.25$$ $$x_a=\frac{2+2.25}{2}=2.125$$

(2) Equation: $3x^3+x^2=x+5$

Let $g(x)=3x^3+x^2-x-5$. The initial interval is $[a_0,b_0]=[1,2]$.

Step 1:

$$f(1)=3(1{)}^3+(1{)}^2-1-5=-2<0$$$$f(2)=3(2{)}^3+(2{)}^2-2-5=21>0$$$$f(1)f(2)<0$$$$c=\frac{1+2}{2}=1.5$$$$f(1.5)=3(1.5{)}^3+(1.5{)}^2-1.5-5=5.875>0$$

$[a_1,b_1]=[1,1.5]$.

Step 2:

$$c=\frac{1+1.5}{2}=1.25$$$$f(1.25)=3(1.25{)}^3+(1.25{)}^2-1.25-5=1.171875>0$$

$[a_2,b_2]=[1,1.25]$.

$$x_a=\frac{1+1.25}{2}=1.125$$

(3) Equation: ${\cos }^{2}x+6=x$

Let $h(x)={\cos }^{2}x+6-x$. The initial interval is $[a_0,b_0]=[6,7]$.

Step 1:

$$f(6)={\cos }^2(6)+6-6={\cos }^2(6)\approx 0.9219>0$$$$f(7)={\cos }^2(7)+6-7={\cos }^2(7)-1\approx -0.4317<0$$$$c=\frac{6+7}{2}=6.5$$$$f(6.5)={\cos }^2(6.5)+6-6.5\approx 0.4777>0$$

$[a_1,b_1]=[6.5,7]$.

Step 2:

$$c=\frac{6.5+7}{2}=6.75$$$$f(6.75)={\cos }^2(6.75)+6-6.75\approx 0.0254>0$$

$[a_2,b_2]=[6.75,7]$.

$$x_a=\frac{6.75+7}{2}=6.875$$

Question 2.

Which of the following three Fixed-Point Iterations converge to the cube root of 4? Rank the ones that converge from fastest to slowest.

(A) $g(x)=\frac{2}{\sqrt{x}}$

1. Fixed Point:: $g(\sqrt[3]{4})=\frac{2}{\sqrt{\sqrt[3]{4}}}=\frac{2}{(4^{1/3}{)}^{1/2}}=\frac{2}{4^{1/6}}$. Since $2=\sqrt{4}=4^{1/2}$, we have: $g(p)=\frac{4^{1/2}}{4^{1/6}}=4^{(1/2-1/6)}=4^{(3/6-1/6)}=4^{2/6}=4^{1/3}=p$.

2. Convergence: We find the derivative $g^{\prime }(x)$. $g(x)=2x^{-1/2}$$g^{\prime }(x)=2\cdot (-\frac{1}{2})x^{-3/2}=-x^{-3/2}=-\frac{1}{x\sqrt{x}}$. Now, we evaluate $|g^{\prime }(p)|$: $|g^{\prime }(p)|=|-\frac{1}{p\sqrt{p}}|=\frac{1}{(4^{1/3}{)}^{3/2}}=\frac{1}{4^{(1/3\cdot 3/2)}}=\frac{1}{4^{1/2}}=\frac{1}{2}$. Since $|g^{\prime }(p)|=\frac{1}{2}<1$, iteration converges.

(B) $g(x)=\frac{3x}{4}+\frac{1}{x^2}$

1. Fixed Point:: $g(p)=\frac{3p}{4}+\frac{1}{p^2}$. Since $p^3=4$, we can write $\frac{1}{p^2}$ as $\frac{p}{p^3}=\frac{p}{4}$. $g(p)=\frac{3p}{4}+\frac{p}{4}=\frac{4p}{4}=p$. Yes, it has the correct fixed point.

2. Convergence: We find the derivative $g^{\prime }(x)$. $g(x)=\frac{3}{4}x+x^{-2}$$g^{\prime }(x)=\frac{3}{4}-2x^{-3}=\frac{3}{4}-\frac{2}{x^3}$. Now, we evaluate $|g^{\prime }(p)|$: $|g^{\prime }(p)|=|\frac{3}{4}-\frac{2}{p^3}|=|\frac{3}{4}-\frac{2}{4}|=|\frac{3}{4}-\frac{1}{2}|=\left|\frac{1}{4}\right|=\frac{1}{4}$. Since $|g^{\prime }(p)|=1/4<1$, iteration converges.

(C) $g(x)=\frac{2}{3}x+\frac{4}{3x^2}$

1. Fixed Point:: $g(p)=\frac{2}{3}p+\frac{4}{3p^2}$. Since $p^3=4$, we can write $\frac{4}{p^2}$ as $\frac{p^3}{p^2}=p$. $g(p)=\frac{2}{3}p+\frac{p}{3}=\frac{3p}{3}=p$. Yes, it has the correct fixed point.

2. Convergence: We find the derivative $g^{\prime }(x)$. $g(x)=\frac{2}{3}x+\frac{4}{3}{x}^{-2}$$g^{\prime }(x)=\frac{2}{3}+\frac{4}{3}(-2x^{-3})=\frac{2}{3}-\frac{8}{3x^3}$. Now, we evaluate $|g^{\prime }(p)|$: $|g^{\prime }(p)|=|\frac{2}{3}-\frac{8}{3p^3}|=|\frac{2}{3}-\frac{8}{3(4)}|=|\frac{2}{3}-\frac{8}{12}|=|\frac{2}{3}-\frac{2}{3}|=0$.

Since $|g^{\prime }(p)|=0<1$, iteration (C) converges. $\therefore$, the speed of converge from quick to slow is $C>B>A$

Question 3.

Apply two steps of Newton's Method with initial guess $x_0=1$ on the equation $x^2+\frac{1}{x+1}-3x=0$.

let $f(x)=x^2-3x+\frac{1}{x+1}$

$$f^{\prime }(x)=2x-3-1(x+1{)}^{-2}$$

The formula for Newton's Method is:

$$x_{k+1}=x_k-\frac{f(x_k)}{f^{\prime }(x_k)}$$

The initial guess $x_0=1$.

Step 1: Calculate $x_1$

We start with $x_0=1$. We need to calculate $f(x_0)$ and $f^{\prime }(x_0)$.

$$f(1)=1-3+\frac{1}{2}=\mathbf{-}\mathbf{1.5}\$\$\$\$f^{\prime }(1)=2-3-\frac{1}{4}=\mathbf{-}\mathbf{1.25}$$

Apply the formula to find $x_1$:

$$x_1=x_0-\frac{f(x_0)}{f^{\prime }(x_0)}=1-\frac{-1.5}{-1.25}$$$$x_1=1-1.2$$$${\mathit{x}}_{\mathbf{1}}\mathbf{=}\mathbf{-}\mathbf{0.2}$$

Step 2: Calculate $x_2$

Now we use $x_1=-0.2$ as our new guess. We need to calculate $f(x_1)$ and $f^{\prime }(x_1)$.

$$f(-0.2)=0.04+0.6+\frac{1}{0.8}=0.64+1.25=\mathbf{1.89}$$$$f^{\prime }(-0.2)=-3.4-\frac{1}{0.64}=-3.4-1.5625=\mathbf{-}\mathbf{4.9625}$$

Apply the formula to find $x_2$:

$$x_2=x_1-\frac{f(x_1)}{f^{\prime }(x_1)}=-0.2-\frac{1.89}{-4.9625}\approx 0.180856$$

After two steps of Newton's Method, the approximate root is $x_2\approx 0.180856$.

Question 4.

Considering the equation $x^3-x^2-5x-3=0$, with roots $r=-1$, $r=3$. Estimate the error $e_{i+1}$ in terms of the previous error $e_i$ as Newton's Method converges to the given roots.
Is the convergence linear or quadratic?

The formula for Newton's Method is $x_{n+1}=g(x_n)$ where $g(x)=x-\frac{f(x)}{f^{\prime }(x)}$. The error after step $i$ is $e_i=x_i-r$. The relationship between consecutive errors is given by:

• If $f^{\prime }(r)\ne 0$ (simple root), convergence is quadratic, and $e_{i+1}\approx \frac{f^{″}(r)}{2f^{\prime }(r)}{e}_i^2$.

• If $f^{\prime }(r)=0$ (multiple root), convergence is linear, and $e_{i+1}\approx (1-\frac{1}{m})e_i$, where $m$ is the multiplicity of the root.

• $f(x)=x^3-x^2-5x-3$

• $f^{\prime }(x)=3x^2-2x-5$

• $f^{″}(x)=6x-2$

Case 1: Root $r=3$

1. Check for Multiplicity: We evaluate $f^{\prime }(x)$ at the root $r=3$. $f^{\prime }(3)=3(3{)}^2-2(3)-5=27-6-5=16$. Since $f^{\prime }(3)=16\ne 0$, the root $r=3$ is a simple root (multiplicity 1).

2. Determine Convergence Rate: Because it is a simple root, the convergence is quadratic.

3. Estimate the Error Relationship: We use the formula for quadratic convergence: $e_{i+1}\approx \frac{f^{″}(r)}{2f^{\prime }(r)}{e}_i^2$. We need to calculate $f^{″}(3)$: $f^{″}(3)=6(3)-2=18-2=16$.

   $$e_{i+1}\approx \frac{16}{2\cdot 16}{e}_i^2=\frac{16}{32}{e}_i^2$$

   Therefore, for the root $r=3$, the error relationship is:

   $${\mathit{e}}_{\mathit{i}\mathbf{+}\mathbf{1}}\mathbf{\approx }\frac{\mathbf{1}}{\mathbf{2}}{\mathit{e}}_{\mathit{i}}^{\mathbf{2}}$$

Case 2: Root $r=-1$

1. Check for Multiplicity: We evaluate $f^{\prime }(x)$ at the root $r=-1$. $f^{\prime }(-1)=3(-1{)}^2-2(-1)-5=3+2-5=0$. Since $f^{\prime }(-1)=0$, this is a multiple root. We need to find its multiplicity. Let's check the next derivative: $f^{″}(-1)=6(-1)-2=-8$. Since $f^{\prime }(-1)=0$ but $f^{″}(-1)\ne 0$, the multiplicity of the root $r=-1$ is m = 2 (a double root).

2. Determine Convergence Rate: Because it is a multiple root, the convergence is linear.

3. Estimate the Error Relationship: We use the formula for linear convergence for a root of multiplicity $m=2$: $e_{i+1}\approx (1-\frac{1}{m})e_i$.

   $$e_{i+1}\approx (1-\frac{1}{2})e_i$$

   Therefore, for the root $r=-1$, the error relationship is:

   $${\mathit{e}}_{\mathit{i}\mathbf{+}\mathbf{1}}\mathbf{\approx }\frac{\mathbf{1}}{\mathbf{2}}{\mathit{e}}_{\mathit{i}}$$

Question 5.

Apply two steps of the Secant Method on the interval with initial guesses $x_0=1$ and $x_1=2$ to find the approximate root of $e^x+x=7$.

First, we define our function $f(x)$ by setting the equation to zero:

$$f(x)=e^x+x-7$$

The formula for the Secant Method is:

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

We are given the initial guesses $x_0=1$ and $x_1=2$.

Step 1: Calculate $x_2$

We start by calculating the function values at our initial guesses, $f(x_0)$ and $f(x_1)$.

• Calculate $f(x_0)$:

  $$f(x_0)=f(1)=e^1+1-7=e-6\approx 2.71828-6=\mathbf{-}\mathbf{3.28172}$$

• Calculate $f(x_1)$:

  $$f(x_1)=f(2)=e^2+2-7=e^2-5\approx 7.38906-5=\mathbf{2.38906}$$

• Apply the formula to find $x_2$:

  $$x_2=x_1-\frac{f(x_1)(x_1-x_0)}{f(x_1)-f(x_0)}$$$$x_2=2-\frac{(2.38906)(2-1)}{(2.38906)-(-3.28172)}\approx 1.57871$$

Step 2: Calculate $x_3$

• Calculate $f(x_2)$:

  $$f(x_2)=f(1.57871)=e^{1.57871}+1.57871-7=\mathbf{-}\mathbf{0.57274}$$

• Apply the formula to find $x_3$:

  $$x_3=x_2-\frac{f(x_2)(x_2-x_1)}{f(x_2)-f(x_1)}$$$$x_3=1.57871-\frac{(-0.57274)(1.57871-2)}{(-0.57274)-(2.38906)}\approx 1.66019$$

After two steps of the Secant Method, the approximate root is $x_3\approx 1.6602$.