2

I am using the Bisection Method to find a root for:

$$\frac{1.52}{(1+x)^2}-0.5\tan^{-1}\left(\frac{1}{x}+\frac{0.65x}{1+x^2}\right)$$

At $[0.1,2]$ and for $\varepsilon=0.01$

Using $\log_2(\frac{b-a}{\varepsilon})\leq n$ I get that $7.56\leq n$

But applying the method I get $|f(1.7625)|\leq 0.01$ after just $3$ iterations

Is it due to a numerical issue with $\log_2(\frac{b-a}{\varepsilon})$ as it is a division by a small number?

Lutz Lehmann
  • 126,666
newhere
  • 3,115
  • How many iterations did you expect? and why? Also I recommend that you add some context why the term $\log_2(\frac{b-a}{\varepsilon})$ is important for you. – harfe Aug 27 '19 at 11:51
  • @harfe at least 8 iterations due to the formula, I linked where it came from – newhere Aug 27 '19 at 11:53
  • 1
    If you use $|f(x)| \leq \epsilon$ (which is very wrong), just multiply any function by $10^{-9999999}$ and the solution is reached in one single iteration. – Claude Leibovici Aug 28 '19 at 08:07
  • @ClaudeLeibovici why using $|f(x)|\leq \varepsilon$ for a given $\varepsilon$ is wrong if we want to bound the error? – newhere Aug 28 '19 at 08:37
  • 1
    Just what I wrote. Your result must not be sensitive to muliplication or division of the function by any number. What you want is that $|x_n-x_{n-1}| \leq \epsilon$ as explained in comments and answers. – Claude Leibovici Aug 28 '19 at 08:42

1 Answers1

2

You are looking at the wrong error. In the wikipedia section that you linked, the error concerns the $x$-values $$ |x - x_n| $$ where $x$ is a solution with $f(x)=0$ and $x_n$ is the midpoint in the $n$th iteration. This is very different from the error of the function values $$ |f(x_n)|. $$

A second point that should be mentioned that such a formula usually refers to the maximum number of iterations needed, not the minimum number of iterations: If you are lucky, your algorithm can come close to the solution in earlier iterations.

harfe
  • 1,588
  • 5
  • 9
  • Wikipedia writes: "$\varepsilon_0$ = initial backet size = $b-a$ – newhere Aug 27 '19 at 12:19
  • 1
    @newhere : You need to use the exact definitions of each symbol. If $ε_k$ is the length of the bracketing interval after $k$ steps, then $ε_0=b-a$ and you want $ε_n=2^{-n}ε_0\le 0.01$. The size of the function values does not occur in this computation. – Lutz Lehmann Aug 27 '19 at 17:17
  • @LutzL so in the function $\log_2(\frac{b-a}{\varepsilon})\leq n$ , $\varepsilon$ is a stopping condition on the interval in which the root need to be found? – newhere Aug 28 '19 at 08:40
  • 1
    Yes. This inequality determines with full control how many steps it takes to reduce the error of $x_n$ to less than $ε/2$, if $x_n$ is the midpoint of the interval. – Lutz Lehmann Aug 28 '19 at 09:13