A COMBINATORIAL CONSTRUCTION OF HIGH ORDER ALGORITHMS FOR FINDING POLYNOMIAL ROOTS OF KNOWN MULTIPLICITY

We construct a family of high order iteration functions for finding polynomial roots of a known multiplicity s. This family is a generalization of a fundamental family of high order algorithms for simple roots that dates back to Schroder's 1870 paper. It starts with the well known variant of Newton's method (B) over cap (2)(x) = x - s . p(x)/p' (x) and the multiple root counterpart of Halley's method derived by Hansen and Patrick. Our approach demonstrates the relevance and power of algebraic combinatorial techniques in studying rational root-finding iteration functions.