7
$\begingroup$

Let's say I have a continuous function $f : I \to \mathbb R$ for $I = [a,b]$ and I want to decide if it has a root or not in $I$. Pretend that I can evaluate it anywhere but cannot use analytical methods to learn anything more about it.

I could obtain a grid of points $a = p_1 < \dots < p_n = b$, evaluate $f$ on each point, and make a scatterplot with some kind of interpolation. From this I may find a root, but if I don't see a root can I ever be confident that one actually does not exist? Can I know that there isn't wild behavior between some pair of points that I missed? Eg maybe for some $i$ the function dips down below $0$ really rapidly right after $p_i$ and returns right before $p_{i+1}$, so it looks flat but just because I've missed something.

My question: what are the circumstances under which we can use a finite number of finite precision function evaluations to prove a root does not exist?

My current guess is that if $f$ is Lipschitz then we could use its Lipschitz constant $K$ to make our grid fine enough that there's no way that $f$ could have a root between pairs of grid points if it doesn't visibly have one in the interpolated scatterplot. But if $K$ is large or $f$ is really close to $0$ then we may have a situation where the grid is required to be finer than finite precision can do.

I also wonder if convexity would do the trick (which since it's stronger than Lipschitz on $I$ seems like a natural thing to try next).

$\endgroup$
  • 1
    $\begingroup$ Typically you would think first in terms of exact evaluations. For that, you need some quantitative regularity (i.e. a modulus of continuity) to ensure that nothing crazy happens in between the points you checked. The finite precision issue is not so complicated once you understand the exact case. $\endgroup$ – Ian Mar 29 '18 at 17:47
  • $\begingroup$ For a polynomial $f(x)=\sum_{j=0}^n A_jx^j$ with $n>0$ and $A_n\ne 0$ . let $M=\max_{j<n}|A_j/A_n|.$ Elementary algebra shows that $|x|\geq 1+M\implies |A_nx^n|>\sum_{j=0}^{n-1} |A_jx^j| \implies f(x)\ne 0. $....Similarly, if also $A_0\ne 0$, let $f^*(x)=x^n f(1/x)$ for $x\ne 0$ and let $M^*=\max_{j>0}|A_j/A_0|.$ Then $0<|x|\leq 1/(1+M^*)\implies g(x)\ne 0 \implies f(x)\ne 0.$ $\endgroup$ – DanielWainfleet Mar 30 '18 at 3:22
  • $\begingroup$ @Ian: I think you can make the modulus of continuity arbitrarily low and still break the algorithm. Take $f(x) = \epsilon >0$ everywhere, except between two evaluation points, then place a tiny inverted bump function to construct a zero. $\endgroup$ – user14717 Mar 31 '18 at 2:12
  • $\begingroup$ @user14717 I mean that with a good modulus of continuity control and also suitable values at evaluation points then you can get a proof like this. $\endgroup$ – Ian Mar 31 '18 at 3:04
  • $\begingroup$ @Ian: Ah, I see. $\endgroup$ – user14717 Mar 31 '18 at 3:35
2
$\begingroup$

In exact arithmetic, one way to do this is to obtain a modulus of continuity $\omega_f$. This is (non-uniquely) defined by the property that if $|x-y|<\omega_f(x,\epsilon)$ then $|f(x)-f(y)|<\epsilon$. (There is of course a maximal $\omega_f$, but we rarely have it in hand.)

Suppose you have such a $\omega_f$ and you evaluate $f$ at some points $x_i$. If $|x_i-x_{i+1}|<\omega_f(x_i,|f(x_i)|)$ for all $i$, then $f$ has no zero in the interval.

In inexact arithmetic, you can do something similar, you just need to require your approximate values of $f$ to be bounded a bit further away from zero, depending on your precision level.

$\endgroup$
  • $\begingroup$ I feel like . . . maybe determination of the modulus of continuity is harder that determination of root existence. Not that this makes your answer wrong, but as a practical consideration, I don't see how this could be a piece of deployed code. $\endgroup$ – user14717 Apr 3 '18 at 3:18
  • $\begingroup$ thank you for the answer. Would it be fair to say that this is very similar to my idea of finding a Lipschitz constant (assuming it exists), and then hoping that things aren't either too small or too big for my computer to handle? $\endgroup$ – alfalfa Apr 3 '18 at 15:28
  • $\begingroup$ @alfalfa A Lipschitz constant corresponds to a modulus of continuity which is linear in $\epsilon$. $\endgroup$ – Ian Apr 3 '18 at 15:33
  • $\begingroup$ ok, thanks. My intuition on this is that the only way to guarantee that $f$ cannot have a sneaky root is to limit the amount it can vary between grid points, so something like the modulus of continuity is unavoidable. Do you think it's justified to claim that if $\omega_f$ is sufficiently large then we can't guarantee that a root doesn't exist? $\endgroup$ – alfalfa Apr 3 '18 at 16:12
  • $\begingroup$ @alfalfa A bad $\omega_f$ is small, not large. But basically yes: if the largest $\omega_f$ evaluated as I said is still less than the grid spacing then you cannot say anything. $\endgroup$ – Ian Apr 3 '18 at 16:17
4
$\begingroup$

This reminds me of Kahan's spy function, which proves that there is no deterministic algorithm which can integrate all functions numerically. We can apply the same idea to your root existence routine. Consider a function spy, which simply records its input. Pass it to your routine. Now use the record produced by spy to create a continuous function malicious which uses those points to (say) always evaluate to 1 at the grid, yet still has a root. A $C^{\infty}[a, b]$ example would be an inverted bump function scaled to fit between each pair of grid nodes and dip down under $0$ at the peak. I'm sure you could also construct a power series that functions as a suitable malicious as well.

Now let's say you use a random set of nodes. Use any one of the divergent sequences which approximate the Dirac delta function (delta sequence), truncate the series (so it meets whatever regularity criterion you want) and place the peak at a random point. Now you have some very low probability that your root existence routine will find a positive and negative value of your function, meaning of course that it can't prove anything.

$\endgroup$
  • $\begingroup$ thank you, this is a very helpful formalization. I guess in some ways my question is almost a rephrasing of the difference between proving $\exists n : P(n)$ versus $\forall n \, P(n)$ $\endgroup$ – alfalfa Apr 3 '18 at 15:25

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.