I am a software developer and I have made a Java class that solves general equations. I thought that I could use the Newton's method which is pretty good but of course I have to set up the bounds. Let me explain better.
- The user inputs a function such as
f(x) = x^3 - x/(x+2) + cos(x). The plot of this function is this - The user must input the bounds in which he thinks that there will be a root (where the function intersects with the x axis). Let's say that we have chosen the interval
[-3, 0] - Now I am going to start a loop in which I create a lot of sub-intervals for example
[-3 ; -2.8],[-2.8 ; -2.6],[-2.6 ; -2.4]and so on. In this way I am able to find the interval in which I have a solution because I just have to check where the sign of the function changes (Bolzano's theorem for roots).- I apply Newton's method in the chosen interval and I get an approx. value of the roots.
The implementation you have seen above is the best that I could imagine. Basically first I need to generate a lot of intervals and then where I am sure that I have a solution, I apply the method.
We assume that the function in each interval is continuous
Question. Newton's method is fast and pretty good, but my program is slow due to the generation of intervals. What I am asking: is there a better method?
Note that I am not asking suggestions about the code. I would like to know if there is a best approach that I could use to solve equations in general, not only polynomials.
In particular I have made a lot of researches on this topic because my goal is to be able to solve equations without putting the bounds. In the case above I was forces to set an interval in which I had to look for the solutions. Is there something that could help me?
The Wikipedia article is very good for talking about the mathematical reasons why newton's method fails. I would check for multiple roots and your implementation if you feel that your code is not very fast. You should try finding the roots of $$f(x)= 2 \log(x) + \sqrt{x} -2 $$ and $$g(x)=(x-1)^6 .$$ Because of the multiple roots convergence should be much faster for $f$ than $g$. If you don't want your users to provide a interval what you should do is try a random number of initial points (in the domain of the given function). After a sufficient number of random initial points there is a high likely hood that all roots have been found.
Of course you should also tell you users to only input continuous functions as well.
If you need a method that will always find a root for an interval see the BiSection Method (you may still need to find multiple intervals if there are multiple roots to your equation, but bisection always gives at least one root if it exists).