Find all roots of a polynomial using secant method

Question

I am writing a program that will find all zeros of a polynomial using secant method. But this method despite my best efforts doesn't always converge.

How to find the initial value for the secant method such that it will converge?

Answer 1

Unfortunately, there's little help: You are facing a fundamental problem there. Finding points from which the secant method will converge towards the roots (even ignoring the degenerate case of multiple roots) is the hard part of root finding. Or put differently, the state of the art is that you can only guarantee that the secant method (or Newton's method, or Aberth-Ehrlich/Börsch-Supan's method, or Durand-Weierstraß-Kerner, or...) converges for approximations which are chosen close enough to the roots that the problem is essentially already solved.

If you want a complete algorithm, go for subdivision approaches (e.g., methods based on Descartes' rule of signs); if you are happy with an easy-to-implement and fast algorithm that always works in practice, use Aberth-Ehrlich for all complex roots and filter out the real ones. Or just use the already existing libraries such as Fabrice Rouillier's RS (real roots) or Bini and Robol's MPSolve (complex).

IIRC, there are results which guarantee the convergence of individual Newton-like methods towards all roots if "enough" starting points are chosen (where "enough" is polynomial in the degree of your input) according to a certain distribution. But again, it is non-trivial to implement that, and AFAIK it only works for complex roots where you know in advance that there are exactly degree many roots. This serves as a criterion to know when to stop iterating over the remaining guesses.