Is it possible for the bisection method to provide "fake" zeros

The bisection method only cares if the function changes sign, so it goes straight past the 'fake' root without noticing.

If the coefficients have a slight error in them, then perhaps the 'fake' root should have been a root.


You have to be aware that the bisection method finds a point with a sign change in the values of the numerical evaluation of your function. Due to catastrophic cancellation that are unavoidable to get small values close to a root, this can give wide errors even for simple roots. Take for instance the rescaled Wilkinson polynomial $p(x)=\prod_{k=1}^{20}(x-k/10)$ in double floating point precision, after multiplying it out as $x^{20}-21x^{19}+a_{18}x^{18}+...+a_1x+a_0$. Around the root $x=1.9$ the numerical evaluation of a larger sampling of points gives this image

enter image description here

so that depending on the initial interval the bisection method might end at any point between $1.8999$ and $1.9003$

To put this into perspective, the scale $\bar p(x)=|x|^n+|a_{n-1}|\,|x|^{n-1}+..+|a_1|\,|x|+|a_0|$ for this situation, polynomial evaluation for $|x|\le 2$, is provided by the bound $\bar p(2)=p(-2)=3.35367..\cdot 10^9$, so that the expected accuracy bound $\bar p(1.9)\mu$ using a machine constant $\mu=2⋅10^{-16}$ is indeed about $7⋅10^{-7}$, the observed errors are a little smaller.


As long as you evaluate $f\left(\frac {a+b}2\right)$ to something greater than zero, the method will work fine. It will replace $a$ with $\frac {a+b}2$ as the left end of the interval. The usual termination criterion for bisection and other bracketing approaches is the length of the interval, not the function value. It would keep going, knowing that there is a root somewhere in the interval because the function values at the endpoints have opposite signs.

Tags:

Numerical Methods

Analysis

Real Analysis

Roots

Related

On $\int_0^{2\pi}e^{\cos2x}\cos(\sin2x)\ \mathrm{d}x=2\pi$ Lattice Paths that Avoid a Point How to calculate mutual information Geometrical interpretation for the sum of factorial numbers Showing a function is Frechet Differentiable？ Suppose $f: [0,1] \rightarrow [0,1] $ and $f(x) \leq \int_0^x \sqrt{f(t)}dt$. Show that $f(x) \leq x^2$ for all $x \in [0,1]$. Prove that $\prod_{i=1}^n (1+x_i/n) \sim \exp (\sum_{i=1}^n x_i/n)$ as $n\rightarrow\infty$? Is there a function $f(x)$ such that $\lim_{x\rightarrow x_0}f(x)=\infty$ for all $x_0$ in some interval? Prove that $\Vert\cdot \Vert^2:X\to \Bbb{R},$ where $X$ is a vector space, is convex Derivative of inner product Proof verification for Identity matrices Prove $\sum_{n=1}^\infty\frac{\cot(\pi n\sqrt{61})}{n^3}=-\frac{16793\pi^3}{45660\sqrt{61}}$

Recent Posts