Newton Iteration Towards a Cluster of Polynomial Zeros

Let P ∈ C[z] be a polynomial which has a cluster of k zeros near v₀ ∈ C. The coefficients of the factor F of P corresponding to this root cluster can be computed from the coefficients of P by Newton iteration in Ck, applied to the mapping F ↦ P mod F.This paper presents and analyzes a numerical algorithm based on this idea. The algorithm uses only polynomial multiplication and division. In particular, there is no need to solve linear systems.The analysis results in an explicit quantitative condition for the coeficcients of P which guarantees the algorithm to converge when started with P₀ = (z — v₀)k. Efficient test procedures for this condition are described. Finally, another starting value condition in terms of root sizes is proved and illustrated with some examples.