TITLE: Is it possible for the bisection method to provide "fake" zeros
QUESTION [7 upvotes]: I've read about the bisection method for finding roots of a function in my numerical analysis textbook and one question came to my mind.
Given a relatively complicated function, the chances of finding the exact root (that is, a root that is completely represented in the computer's memory, with all significant figures) are very low. This means that most of the time, we will have a value for which the function is very close to, but not exactly equal to zero.
So what would happen if the function had one root, and another value at which the function gets extremely close to zero, without actually getting there? Would the algorithm fail? And what is the meaning of that eventual "fake" root; is it worth anything?
Thank you.
EDIT: here is a picture showing what I meant

REPLY [3 votes]: Suppose we are utilizing a computer that has $N$-bit precision ($N\geq4$). If we take any integer $n > N$ and we apply the bisection algorithm to the function $f$ defined on $[0,1]$ by $f(x)=\left(x-\frac12\right)^2\left(x-\frac34\right)-2^{-n}$, then the algorithm will output $x=\frac12$ as the point where $f$ has a root. This is because $f(0)=-\frac3{16}-2^{-n}<0$, $f(1)=\frac1{16}-2^{-n}>0$, and our computer isn't capable of distinguishing $\,f\left(\frac12\right)=-2^{-n}$ from zero. 
Here is a plot of our function $f$ if we took $n=10$:
Notwithstanding the output from applying the bisection algorithm to $f$ on $[0,1]$, we can see that the only zero of $f$ in $[0,1]$ lies somewhere between $\frac34$ and $1$.

As for the meaning of such a "fake" root, I would say it alludes to the fact that the Intermediate Value Theorem is equivalent to the nonconstructive proposition known as the lesser limited principle of omniscience.
Define a binary sequence $\{a_n\}_{n=1}^\infty$ by
\begin{equation}a_n=\begin{cases}0 &\text{ iff either } 2k+3 \text{ is the sum of 3 primes for all } k\leq n \text{ or there exists } k<n \text{ s.t. } a_k=1 \\1&\text{ otherwise.}\end{cases} \end{equation}
Define $a=\sum_{n=1}^\infty a_n2^{-n}$, and apply the bisection algorithm to the function $f$ defined on $[0,1]$ by $f(x)=\left(x-\frac12\right)^2\left(x-\frac34\right)-a$. As long as our computation is limited to some finite precision, the algorithm will output $x=\frac12$ as a root of $f$. This output is correct (which I take to mean that it is either identical to or approximately close to a root) if and only if the odd Goldbach conjecture is true.
The way that the binary sequence $\{a_n\}_{n=1}^\infty$ is defined is meant to invoke the limited principle of omniscience, a nonconstructive principle which implies the lesser limited principle of omniscience.

Disclaimer (in response to the valid concerns raised by Euro Micelli): My "answer" is not trying to provide affirmation of the question in the title as I would say the answer to the question posed in the title is "not yes". I will note that even arbitrary precision is still subject to available memory and computation time (as far as I know). I figure we have two sides of the same coin, the bisection method is not constructive and so is the definition of the function $f$ on $[0,1]$. Indeed there are ways to preclude such a false output, and my response has only considered the algorithm underlying the proof of the Intermediate Value Theorem in the most classical and basic setting. I respond to questions on this forum by trying to provide the question asker with some insight and perspective to the best of my knowledge given the contents of their initial post.
{"set_name": "stack_exchange", "score": 7, "question_id": 3021532}