# Halving the Interval Method with Relative Accuracy

## Find the smallest positive root of $x^3 – 2x + 1 = 0$ with relative accuracy of $0.5 \%$ by finding good starting value from its graph.

According to the graph above, there are three roots, one negative and two positive.

Let’s give $f(x) = x^3-2x+1$, then $f(1) = 1^3 – 2 \times 1 + 1 = 0$.
Therefore $x = 1$ is the largest positive root as well as shown in the graph.

So the smallest positive root lies in between $x=0$ and $x=1$.
Though this interval is good enough to start applying “halving the interval method”, it could be better to make the working more effective and efficient, say $0.5 < x < 0.9$.

To find the rate of accuracy by taking the relative accuracy method, we need two values, the error and the “believed” true value.
In this case, the true value is $\displaystyle \frac{0.5+0.9}{2} = 0.7$ as we believe $0.7$ is more accurate than both $0.5$ and $0.9$ and the error is $\left| 0.5 – 0.7 \right| = 0.2$ or $\left| 0.7 – 0.9 \right| = 0.2$.

Thus the relative accuracy is $\displaystyle \frac{ \left| 0.5-0.7 \right| }{0.7} \times 100 \% =28.57 \%$.

Let’s start to find the smallest positive root!

$f(0.5) = 0.125 > 0$
$f(0.9) = -0.057 < 0$
The interval is $0.5 < x < 0.9$ as the closer value of $x$ lies between opposite sign of its function values.
The midpoint is $\displaystyle \frac{0.5+0.9}{2} = 0.7$.
Its relative accuracy is $\displaystyle \frac{|0.5 – 0.7|}{0.7} \times 100 \% = 28.57 \%$.

$f(0.7) = -0.057 < 0$
The refined interval is $0.5 < x < 0.7$.
The midpoint is $\displaystyle \frac{0.5+0.7}{2} = 0.6$.
Its relative accuracy is $\displaystyle \frac{|0.5 – 0.6|}{0.6} \times 100 \% = 16.67 \%$.

$f(0.6) = 0.016 > 0$
The refined interval is $0.6 < x < 0.7$.
The midpoint is $\displaystyle \frac{0.6+0.7}{2} = 0.65$.
Its relative accuracy is $\displaystyle \frac{|0.6 – 0.65|}{0.65} \times 100 \% = 7.69 \%$.

$f(0.65) = -0.0253 \cdots < 0$
The refined interval is $0.6 < x < 0.65$.
The midpoint is $\displaystyle \frac{0.6+0.65}{2} = 0.625$.
Its relative accuracy is $\displaystyle \frac{|0.6 – 0.625|}{0.625} \times 100 \% = 4 \%$.

$f(0.625) = -0.0058 \cdots < 0$
The refined interval is $0.6 < x < 0.625$.
The midpoint is $\displaystyle \frac{0.6+0.625}{2} = 0.6125$.
Its relative accuracy is $\displaystyle \frac{|0.6 – 0.6125|}{0.6125} \times 100 \% = 2.04 \%$.

$f(0.6125) = 0.0047 \cdots > 0$
The refined interval is $0.6125 < x < 0.625$.
The midpoint is $\displaystyle \frac{0.6125+0.625}{2} = 0.61875$.
Its relative accuracy is $\displaystyle \frac{|0.6125 – 0.61875|}{0.61875} \times 100 \% = 1.01 \%$.

$f(0.61875) = -0.0006 \cdots < 0$
The refined interval is $0.6125 < x < 0.61875$.
The midpoint is $\displaystyle \frac{0.6125+0.61875}{2} = 0.615625$.
Its relative accuracy is $\displaystyle \frac{|0.6125 – 0.615625|}{0.615625} \times 100 \% = 0.51 \% \$So close!

$f(0.615625) = 0.002 \cdots > 0$
The refined interval is $0.615625< x < 0.61875$.
The midpoint is $\displaystyle \frac{0.615625+0.61875}{2} = 0.6171875$.
Its relative accuracy is $\displaystyle \frac{|0.615625- 0.6171875|}{0.6171875} \times 100 \% = \color{green}{0.25 \%}$.

As this $\color{green}{0.25 \%}$ meets the minimum relative accuracy level of $0.5 \%$, the smallest positive root is $\color{green}{0.6171875}$!