On the worst-case arithmetic complexity of approximating zeros of polynomials
For complex polynomials \(P_ d(R)\) of degree \(d\geq 2\) with all zeros \(z_ i\) satisfying \(| z_ i| \leq R\) it is shown that the worst- case computational complexity of obtaining an \(\epsilon\)-approximation for the zeros of \(P_ d(R)\) is O(log log(R/\(\epsilon)\)). Further a new algorithm, based on Newton's method, and using the Schur-Cohn algorithm, giving upper bounds is derived.
scientific article; zbMATH DE number 4046964
scientific article