Finding complex roots of integer polynomials

Question

How would one find approximates for complex root of polynomial with integer coefficients,I know for example the Newton's method $$x_n=x_{n-1}-\frac{f(x_{n-1})}{f'(x_{n-1})}$$ Anyway is it possible to do such when you're finding complex roots(for example $3z^3+z^2+z+1$)?Or are there any other methods for doing such?

Answer 1

There are two improvements of Newton-Raphson iteration that work particularly well for polynomials since they find all roots simultaneously. (Newton-Raphson finds only one at a time.) The first one is the Durand-Kerner method that was actually already known to Weierstrass (and re-invented again by me when I was a student). The second one is the Aberth-Ehrlich method. It's been quite a while since I used those methods but if I remember correctly the latter is superior in terms of convergence rate.

Oh, and as stated in the comments, do not pick all initial candidate roots real since iteration will never "come off" the real line in that case. Just some random complex initial values will do for both methods.