Sorry if I misused/mixed up some maths terms. I barely know any maths lingo, especially not in English.
I was thinking about programmatically solving equations (or rather, approximating their roots), and was wondering about how to guarantee an arbirtarily close approximation of every root of a function has been found. I'm only considering real numbers here, as well as only equations of the form $y=f(x)$ Here's some observations I've made:
- This can always be guaranteed as long as the number of roots of a function can be calculated/counted and is finite (though it can take aribtrarily long to find them, once you have, you can guarantee you have all of them).
- Inversely, the number of roots of a function can always be calculated/counted if you can approximate all of its roots and guarantee there are no other roots.
- If this condition holds true for the continuous function $f(x)$, it also always holds true for $F(x)$
I know this condition holds true for all non-zero polinomials, since it holds true for $f(x)=ax$ where a is nonzero (see number 3 of my observations). I wonder if there are other (categories of) functions this applies to, if there's other observations to be made about this condition, and if there's maybe even a way to guarantee this condition holds true or false for an arbitrary function.
My apologies if my question is either too vague/too broad/etc.
Unfortuantely, there are several challenges that make these claims insufficient.
If the function is discontinuous, it may appear to have a root when in fact it does not. For instance, consider a function f(x) = 1 for $x \gt 0$, and f(x) = -1 otherwise. This function would appear to cross the x axis and therefore would be a candidate for a function that has a root, but no such root could be found. In fact, any approximation method that relies on limit behaviour around the root will fail, since in the limit it always appears as though this function has a root around $x = 0$ when in fact it does not.
If you're talking about root finding in principle, then yes, for some class of functions arbitrary approximations of their roots can be found. If you're talking about doing it using a practical computer then no, this is not possible. For instance, a function with a horizontal asymptote at $y = 0$ will appear to approach 0 but never reach it.
This relies heavily on root counting, which is hard. For polynomials it's simple enough - the number of roots (not necessarily real) is equal to the degree. But there are many other functions than polynomials and therefore to count their roots may be impossible. Furthermore, you'd need some initial estimate of where the roots are, because if you just search along the x axis you might miss some if you're stepping too far.
I assume by $F(x)$ you mean $f(x)$'s integral. If the function is not integrable then this is already a nonstarter.
I should also mention that many root finding algorithms rely on the function giving information about the fact that there is a root there. For example, it changes sign from positive to negative and is continuous, so it must have a root. But consider even relatively simple functions $y = sin(x) + 1, x\in[1,\pi]$. This function has no sign changes but has a finite number of roots in the domain I provided. It in fact only has roots at a very unfortunate place - the irrational $\pi$! Approximating a root of this function would be very hard indeed, and this function is nicely continuous. If I made it even worse, say $f(x) = 1$ except at $x = \pi$ where $f(\pi) = 0$, then this function gives absolutely no information about where its root is that an algorithm could use without knowing exactly what the function was in the first place. Since I presume you want a general purpose algorithm, not a specific one to the function, it appears that such a thing is not possible.
For what it's worth, equation solving and root finding are the same problem. If $y = f(x)$ and we are looking for when $y = 3$, say, then we are finding the roots of the equation $f(x) - 3 = 0$.