A combinatorial construction of high order algorithms for finding polynomial roots of known multiplicity

TY - JOUR

T1 - A combinatorial construction of high order algorithms for finding polynomial roots of known multiplicity

AU - Jin, Yi

AU - Kalantari, Bahman

PY - 2010/6

Y1 - 2010/6

N2 - 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 Schröder's 1870 paper. It starts with the well known variant of Newton's method B̂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.

AB - 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 Schröder's 1870 paper. It starts with the well known variant of Newton's method B̂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.

KW - Generating functions

KW - Iteration functions

KW - Multiple roots

KW - Recurrence relation

KW - Root-finding

KW - Symmetric functions

UR - https://www.scopus.com/pages/publications/77951177786

UR - https://www.scopus.com/pages/publications/77951177786#tab=citedBy

U2 - 10.1090/S0002-9939-10-10309-8

DO - 10.1090/S0002-9939-10-10309-8

M3 - Article

SN - 0002-9939

VL - 138

SP - 1897

EP - 1906

JO - Proceedings of the American Mathematical Society

JF - Proceedings of the American Mathematical Society

IS - 6

ER -