Newton iteration towards a cluster of polynomial zeros (Q4336101)

This paper presents and analyzes a numerical algorithm based on the following idea. The algorithm uses only polynomial multiplication and division. Let \(P \in \mathbb{C} [z] \) be a polynomial which has a cluster of \(k\) zeros near \(v_{0} \in \mathbb{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 \(\mathbb{C}^{k}\), applied to the mapping \(F\to P \bmod F\). In particular, there is no need to solve linear systems. The analysis results in an explicit quantitative condition for the coefficients of \(P\) which guarantees the algorithm to converge when started with \(F_{0} = (z-v_{0})^{k} \). Efficient test procedures for this condition are described. Finally, another starting value condition in terms of root sizes is proved and illustrated with the same examples. For the entire collection see [Zbl 0857.00037].