Q. Use the Bisection Method to find an approximation with accuracy $10^{-4}$ to the solution of $x^3-x-1=0$ lying in the interval [1,2]
What should be the correct stopping criteria for this problem? If I choose $|b_n-a_n|$$<$Tolerence, the approximate value is 1.324707 (iter 11). If I decide $|P_n-P_{n-1}|/|P_n|$ $<$ Tolerance then I got approximate value 1.324829. I'm a little bit confused. Did I make any mistakes? What criteria should I use to answer this question?
Similar solved problem..
Let $x \in \mathbb{R}$ denote the unknown value which we seek to approximate. The most useful measure of the accuracy of an approximation $\hat{x}$, is the absolute error $$e = x - \hat{x}$$ and the relative error $$r = \frac{x - \hat{x}}{x}$$ which is only defined when $x \not = 0$.
Now, the phrasing of the original problem is weak and we cannot determine the author's intention with any certainty. However, the bisection algorithm affords us the opportunity to bound both the error and the relative error in terms of the brackets, i.e., the intervals $(a,b)$ which are produced.
Specifically, let $(a_j,b_j)$ denote the $j$th bracket and let $f$ denote our continuous function. We seek to solve $f(x) = 0$. We have different signs for $f(a_j)$ and $f(b_j)$. It follows that there exist a zero $x$ of $f$ in the interval $(a_j,b_j)$. Without additional information, the best approximation of $x$ is the midpoint $$x_j = \frac{a_j + b_j}{2}.$$ For the error we have $$|e| = |x - x_j| \leq \frac{1}{2}|b_j - a_j|.$$ If $a_j$ and $b_j$ have the same sign, then $x = 0$ is impossible and the relative error $r$ is defined. In this case, we have the bound $$|r| = \frac{|x-x_j|}{|x|} \leq \frac{\frac{1}{2}|b_j-a_j|}{\min\{|a_j|,|b_j|\}}.$$ Your objective should be to ensure that either $$ \frac{1}{2}|b_j - a_j| \leq \tau $$ or $$ \frac{\frac{1}{2}|b_j-a_j|}{\min\{|a_j|,|b_j|\}} \leq \tau$$ where $\tau$ is the tolerance specified by the user.
Your own suggestion is to terminate the iteration when $$ \left | \frac{x_j - x_{j-1}}{x_j} \right| \leq \tau$$ In general, this is not a bad choice, it simply that we can do better because the bisection method delivers more than just an approximation, it delivers an interval which contains the root.
If a choice must be made, then I would choose to bound the relative error. I would make this choice because I am using floating point arithmetic. Here, every number in the representational range can be approximated with a small relative error. In the absence of any additional information bounding the relative error is the "natural" choice.