I am writing a program to determine the roots of polynomial functions.
I will be using the secant method to determine the roots.
The problem I am facing is that I have to know at least a bit of information about the function before I apply the secant method, namely:
- How many roots are there so I can know once Ive solved for all of them
- Where, approximately, are these roots so I can apply appropriate root finding intervals to the secant method
To address point 1, I am using the Fundamental Theorem of Algebra which tells me how many real and how many non-real, complex roots there are
To address point 2, I am using Descartes Rule of Signs which tells me all the possibilities on which side of x axis are the real and complex roots (which, coupled with point 1 above, should tell me exactly how many there are real and non-real, complex).
The problem I am facing is that this is still not enough for me to start guessing where to choose my root finding intervals. The only thing I can possibly think of is to randomly substitute pairs of x values in my f(x) function until I hit a pair of x values that change the sign of f(x). (Recall that if x1 and x2 yield opposite f(x1) and f(x2) values, there must be at least one root in between those values.)
Random sampling (even being complemented with fundamental theorem of algebra and Descartes rule of signs) seems very much like a brute force inefficient method which seems to cancel the benefits of the actual efficient root finding methods.
Are there any other ways I can get around random sampling? How do the proprietary mathematics software achieve finding appropriate intervals for roots?