Interested in search algorithms for all roots of a polynomial (including complex).

I know that there is a method of 2D-approximations. Are there any more efficient algorithms?

1 answer 1

You can generalize Newton's method to the case of complex roots, but there is a danger of drowning in its pools :)

The polyroots function in MathCAD uses the default Laguerre method, optionally the accompanying matrix method. Implementations of these methods met on the net.

Serious math libraries implement the Jenkins-Traub method for equations of general form. The method has good convergence (not worse than the method of the accompanying matrix). And here you can get hold of implementation.

The Lobachevsky-Greffe method is very interesting (Western science traditionally underestimates the merits of our compatriots, so you should look in English by the names of Greffe and Dundelen), which allows you to find all the roots simultaneously. Only the computational scheme for complex roots is rather confusing; I have not seen any realizations.

A couple of links to sources:
1. Tarasevich Yu. Yu. Numerical methods at Mathcad
2. J. Traub. Iterative methods for solving equations