2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Could you just compute the bisection sequence and present it as a table (with function values)? $\endgroup$ – LutzL Jun 24 '17 at 17:28
  • $\begingroup$ No I use the above rule to compute the minimum possible value of $n$. $\endgroup$ – Arnab Chatterjee. Jun 24 '17 at 17:29
  • $\begingroup$ This question is a duplicate. See here, math.stackexchange.com/questions/1057651/… $\endgroup$ – MasterYoda Jun 24 '17 at 17:32
  • $\begingroup$ No I have already visited that link before asking this question but I dont find any reason there that can fulfill my requirement. $\endgroup$ – Arnab Chatterjee. Jun 24 '17 at 17:34
  • $\begingroup$ 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). $\endgroup$ – David K Jun 24 '17 at 18:22
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.