Root Finding Tutorial Sheet, #14
Learning targets
- To understand the process of the 3 root finding methods (Newton-Raphson, Bisection, Secant)
- Iterate multiple times to find a root to a desired level of accuracy (could use code)
- Understand some constraints and disadvantages associated with the methods/use of computers
Additional Resources
Tutorials
- Newton-Raphson : Extra video by Sam recapping the Newton Raphson method from the lecture.
- Bisection : Extra video by Sam recapping the bisection method from the lecture.
- Calculus Playlist : Some nice comparisons of the methods.
Software
- Bisection Calculator : Pretty cool bisection calculator that includes the accuracy and each stage.
- Newton-Raphson Calculator : Newton-Raphson calculator that includes the accuracy and each stage.
- WolframAlpha : N-R interactive visualisation tool.
Problem sheet
Skill Building Questions
Problem 1.
Find the positive root of $f(x)=x^3-6x^2+11x-6=0$ using the bisection method from the interval [2.5, 4].
Using a table, the highlighted cells (red = negative, green = positive) show the $a$ and $b$ values used for the interval of the next iteration, where $\frac{a + b}{2} = c$. These numbers are chosen for the interval of the following iteration since they have the smallest difference in values and have a negative product.
It is clear that the iterations are converging towards the root $\boxed{x=3}.$
Alternative Method:
Finding the interval $[a, b]$ bracketing the root. Since the bisection method finds a root in a given interval $[2.5, 4]$ \begin{aligned} & (\mathrm{i})\quad f(x) = x^3-6x^2+11x-6\newline & (\mathrm{ii})\quad a_0=2.5,\quad b_0=4 \end{aligned} Iteration 1 $(k = 0)$: \begin{equation*} c_0 = \frac{a_0+b_0}{2}=\frac{4+2.5}{2}=\frac{6.5}{2}=3.25 \end{equation*} Since $f(c_0)f(a_0)=f(3.25)f(2.5) < 0$ and $|f(c_0)f(a_0)| < |f(b_0)f(a_0)|$ , set $b_1=c_0=3.25,a_1=a_0=2.5$ Iteration 2 $(k = 1)$: \begin{equation*} c_1 = \frac{3.25+2.5}{2}=2.8750 \end{equation*} Since $f(c_1)f(a_1)=f(2.875)f(2.5)>0$ and $|f(c_1)f(b_1)| < |f(b_1)f(a_1)|$, set $ b_2=b_1=3.25, a_2 = c_1=2.875$ Iteration 3 $(k = 2)$: \begin{equation*} c_2=\frac{a_2+b_2}{2}=\frac{2.875+3.25}{2}=3.0625 \end{equation*} Since $f(c_2)f(a_2)=f(3.0625)f(2.875) < 0$ and $|f(c_2)f(a_2)| < |f(b_2)f(a_2)|$, set $b_3=c_2=3.0625,a_3=a_2=2.875$ Iteration 4 $(k = 3)$: \begin{equation*} c_3=\frac{a_3+b_3}{2}=\frac{2.875+3.0625}{2}=2.9688 \end{equation*} It is clear that the iterations are converging towards the root $\boxed{x=3}.$
Problem 2.
The equation $x^3-7x^2+14x-6=0$ has at least one root between $x=0$ and $ x=1$. Use the method of interval bisection to locate this root accurate to $10^{-2}$.
This yields the following results for $p_n$ and $f(p_n)$: \begin{align*} & n& \quad &c_n& \quad &f(c_n) \newline \hline & 1& &0.5000000& &-0.6250000000 \newline & 2& &0.7500000& &+0.9843750000 \newline & 3& &0.6250000& &+0.2597656250 \newline & 4& &0.5625000& &-0.1618652344 \newline & 5& &0.5937500& &+0.0540466309 \newline & 6& &0.5781250& &-0.0526237488 \newline & 7& &0.5859375& &+0.0010313988 \newline \hline \end{align*} Therefore, the root is $\boxed{x = 0.59}$ to 2dp.
Alternative method:
We can also use the same method as in problem 1 and use a table to find the root.
Therefore, the root is $\boxed{x = 0.59}$ to 2dp.
Problem 3.
Find the only real root of $x^3-3x-4=0$ using NR method correct to 9 decimal places.
Link to Wolfram Alpha
The root is $\boxed{x = 2.195823345}$ correct to 9dp.
Tip: a sensible starting point would have been $ \ x=3 \ $ as well as some of the points mentioned earlier.
Problem 4.
Find the real root of $x^3-6x^2+9x+1=0$ using;
(a) the Newton-Raphson method.
To check this, we can substitute this back into the original equation: \begin{equation*} (-0.1038)^{3}-6(-0.1038)^2+9(-0.1038)+1 =0.0000349 \approx 0 \end{equation*} Alternatively this could be solved using code (e.g. Matlab).
(b) the Secant method
$\therefore$ the root of the equation is $\boxed{x = -0.1038}$ to 4 dp.
Alternatively this could be solved using code (e.g. Matlab). An example of the Matlab script is given below (it requires user input rather than editing the script, but you could do it either way).
% Secant Method Example Code in MATLAB
a=input('Enter function:','s'); %Prompts you to type in equation
f=inline(a)
x(1)=input('Enter first point of guess interval: '); %Prompts you to enter 2 points (x-values)
x(2)=input('Enter second point of guess interval: ');
n=input('Enter allowed Error in calculation: '); %Prompts you to enter the allowed error
iteration=0;
for i=3:1000
x(i) = x(i-1) - (f(x(i-1)))*((x(i-1) - x(i-2))/(f(x(i-1)) - f(x(i-2)))); %Secant Equation
iteration=iteration+1;
if abs((x(i)-x(i-1))/x(i))*100<n
root=x(i)
iteration=iteration
break
end
end
The root found by these start points will then be returned. (for this question $\boxed{x = -0.1038}$ to 4 dp.)
Problem 5
Find a positive real root of $\cos(x)-x^3=0$ using;
(a) the NR (Newton-Raphson) method.
Input Data: \begin{aligned} & (\mathrm{i})\quad f(x) = \mathrm{cos}x-x^3\newline & (\mathrm{ii})\quad x_0 = 0.5 \end{aligned} Formula to be used: $$x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}$$ Compute $f'(x)=-\mathrm{sin}x-3x^2$ Iteration 1: $ \ k=0$ $$ x_1=x_0-\frac{f(x_0)}{f'(x_0)}=0.5-\frac{\mathrm{cos}(0.5)-(0.5)^3}{-sin(0.5)-3(0.5)^2}=1.1121 $$ Iteration 2: $ \ k=1$ $$ x_2=x_1-\frac{f(x_1)}{f'(x_1)}=0.9097 $$ Iteration 3: $ \ k=2$ $$ x_3=x_2-\frac{f(x_2)}{f'(x_2)}=0.8444 $$ Iteration 4: $ \ k=3$ $$ x_4=x_3-\frac{f(x_3)}{f'(x_3)}=0.8659 $$ Iteration 5: $ \ k=4$ $$ x_5=x_4-\frac{f(x_4)}{f'(x_4)}=0.8655 $$ Iteration 6: $ \ k=5$ $$ x_6=x_5-\frac{f(x_5)}{f'(x_5)}=0.8654 $$ Iteration 7: $ \ k=6$ $$ x_7=x_6-\frac{f(x_6)}{f'(x_6)}=0.8654 $$ $\therefore$ the root is $\boxed{x=0.8654}$ to 4 dp.
(b) the Secant method.
$\therefore$ the root of the equation is $\boxed{x=0.8654}$ to 4 dp.
Exam Style Questions
Problem 6.
(i) Use the Newton Raphson method to investigate the function: $ \ f(x) = \frac{1+4x - x^3}{x} \ $ by starting from the point $ \ x = -1.0$. Find a root accurate to 2 decimal places.
Alternatively you could use Matlab or Python code to solve this.
(ii) Sketch the function as well as the path travelled by your NR approximation from the starting location and along each of the subsequent tangents, finishing at the root you have found.
Extension Questions
Problem 7.
For those who’d like an extra method, look up the “Fixed point method” to find the roots for the following function:
$x-\mathrm{cos}x = 0$ starting from the intervals $0 < x < \frac{\pi}{2}$
Thus, if we take $g(x)=\mathrm{cos}(x)$, then:
(1) For all $x$ in $[ 0,\frac{\pi}{2} ]$, $0\leq g(x)\leq 1$
(2) $g^{'}(x)=-\mathrm{sin}x$. Thus,$\rvert g^{'}(x)\rvert<1$ in $[ 0,\frac{\pi}{2} ]$
According to the Fixed-Point Iteration Theorem, the iterations must converge with any choice of $x_0$ in $[ 0,\frac{\pi}{2} ]$. This is verified from the following computations. \begin{equation*} \begin{aligned} x_0&=0 \newline x_1&=\mathrm{cos}x_0=1 \newline x_2&=\mathrm{cos}x_2=0.5403 \newline x_3&=\mathrm{cos}x_3=0.8576 \newline .& \newline .& \newline .& \newline x_{17}&=\mathrm{cos}x_4=0.73956 \newline x_{18}&=\mathrm{cos}x_1=0.73956 \end{aligned} \end{equation*} The sequence is clearly converging to the root $\boxed{x\approx 0.74}$
Problem 8 (optional).
This is an optional question (requires Matlab and it’s symbolic toolbox).
The image below shows Matlab script to find a root to the equation $\frac{1}{x} +4 -x^2$ using the Newton Raphson method. Copy the code into Matlab and fill in the code hidden by ‘*’ so that the code works. Use it to find the root (and use the starting point of 1).
function Newton_Raphson_Method
%Implementation of Newton-Raphson method to determine a solution.
i = 1;
********** %initial conditions (start point)
N = 5; %maximum number of iterations
error = 0.01; %precision required
syms 'x'
f(x) = ********** %function we are solving
df = diff(f); %differential of f(x)
while i <= N
********** %Newton-Raphson equation
if (abs(p - p0)/abs(p)) < error %stopping criterion when difference between iterations is below tolerance
fprintf('Solution is %f \n', double(p))
return
end
i = i + 1;
p0 = p; %update p0
end
fprintf('Solution did not converge within %d iterations at a required precision of %d \n', N, error) %error for non-convergence within N iterations
end
function Newton_Raphson_Method
%Implementation of Newton-Raphson method to determine a solution.
i = 1;
p0 = 1; %initial conditions (start point)
N = 5; %maximum number of iterations
error = 0.01; %precision required
syms 'x'
f(x) = (1/x) + 4 -x.^2 ; %function we are solving
df = diff(f); %differential of f(x)
while i <= N
p = p0 - (f(p0)/df(p0)); %Newton-Raphson equation
if (abs(p - p0)/abs(p)) < error %stopping criterion when difference between iterations is below tolerance
fprintf('Solution is %f \n', double(p))
return
end
i = i + 1;
p0 = p; %update p0
end
fprintf('Solution did not converge within %d iterations at a required precision of %d \n', N, error) %error for non-convergence within N iterations
end
The root found was $\boxed{x=2.11}$ to 2dp.
See if you can write the code yourself for the other root finding methods!
Answers
For Printing
Revision Questions
The questions included are optional, but here if you want some extra practice.
- Engineering Mathematics 7th edition, Stroud and Dexter : Pages 344-352
- Advanced Engineering Mathematics 5th edition, Stroud and Dexter : Pages 10-17
- A-Level Questions : Baseline A-Level questions, helps with learning by ‘rote’.