2

At each iteration in the bisection method the absolute error becomes half of the previous iteration. Thus if we approximate the root $x$ of some equation in some interval $[a,b]$ (say) by means of a sequence $\{x_n\}$ converging to $x$ in the bisection method then we should have $|x_n-x| \le \frac {b-a} {2^n}$ If we want to approximate $x$ in such a way that the absolute error $\le \epsilon$ for some given $\epsilon >0$ then we first calculate the maximum probable iterations for which $|x_n-x|>\epsilon$ or in other words the maximum probable iterations for which $\frac {b-a} {2^n} > \epsilon$. This would yield the maximum possible value of $n$ is $\frac {\ln (b-a) - \ln \epsilon} {\ln 2}$ i.e. for all $n \ge \frac {\ln (b-a) - \ln \epsilon} {\ln 2}$ we have $|x_n-x| \le \epsilon$. Now my question is $:$

Can I say that the least $n$ for which it just exceeds the quantity $\frac {\ln (b-a) - \ln \epsilon} {\ln 2}$ is the least value of $n$ for which $|x_n-x| \le \epsilon$? This question immediately came to my mind when I was trying to solve the following problem $:$

Find the minimum number iterations needed to approximate the root of the equation $e^x-3x^2=0$ in $(3,4)$ such that the absolute error $\le 10^{-3}$.

Now if the answer to my last question is "yes" then I find the answer to the above problem which is $10$ but if it isn't then I don't find any clue to find such $n$.

Please help me to overcome my confusion.

Glorfindel
  • 3,955
Arnab Chattopadhyay.
  • 2,570
  • Could you just compute the bisection sequence and present it as a table (with function values)? – Lutz Lehmann Jun 24 '17 at 17:28
  • No I use the above rule to compute the minimum possible value of $n$. – Arnab Chattopadhyay. Jun 24 '17 at 17:29
  • This question is a duplicate. See here, https://math.stackexchange.com/questions/1057651/minimum-number-of-iteration-in-bisection-method – MasterYoda Jun 24 '17 at 17:32
  • No I have already visited that link before asking this question but I dont find any reason there that can fulfill my requirement. – Arnab Chattopadhyay. Jun 24 '17 at 17:34
  • What is missing from the answer to the other question? It says to apply your formula (so the answer is "yes") and it applies the formula and gets the answer $10$ (the same as you did). – David K Jun 24 '17 at 18:22
  • But this formula does not guarantee that the least $n$ for which $n$ just exceeds the quantity $\frac {\ln(b-a)-\ln \epsilon} {\ln 2}$ is the least $n$ for which $|x_n - x|$ just reach at the desired accuracy which is my requirement and I want to know it clearly. So it cannot be considered as a duplicate of that link. – Arnab Chattopadhyay. Jun 25 '17 at 02:16
  • Even if you reached the precision in an earlier step, you would have no certificate of that fact. One could do something with function values and derivatives, but then you leave the domain of the bisection method. – Lutz Lehmann Jun 25 '17 at 11:08

1 Answers1

1

The bisection method bases all decisions purely on the sign of the function value. There is no size information used, even less slope information.

Thus even if the root were $3.500001$ so that the best approximation could be found in the first step, there is no way to detect this, the result of the first step is only that the root is somewhere in $[3.5,4]$.

It is really only the length of the bracketing interval that gives any information on the quality of the root approximation by endpoint or midpoint.

What you can do is to always return the midpoint (without a final function evaluation there), so that for an error of $10^{-3}$ you need an interval length smaller than $2·10^{-3}$ which is reached after $9$ steps with $b_9-a_9=\frac1{512}$ or $11$ function evaluations.

Lutz Lehmann
  • 126,666