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

Jin, Yi; Kalantari, Bahman

doi:10.1090/S0002-9939-10-10309-8

A combinatorial construction of high order algorithms for finding polynomial roots of known multiplicity
HTML articles powered by AMS MathViewer

by Yi Jin and Bahman Kalantari PDF

Proc. Amer. Math. Soc. 138 (2010), 1897-1906 Request permission

Abstract:

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 $\hat {B}_{2}(x) = x-s \cdot 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.

References

Xavier Buff and Christian Henriksen, On König’s root-finding algorithms, Nonlinearity 16 (2003), no. 3, 989–1015. MR 1975793, DOI 10.1088/0951-7715/16/3/312
Charles M. Fiduccia, An efficient formula for linear recurrences, SIAM J. Comput. 14 (1985), no. 1, 106–112. MR 774930, DOI 10.1137/0214007
Eldon Hansen and Merrell Patrick, A family of root finding methods, Numer. Math. 27 (1976/77), no. 3, 257–269. MR 433858, DOI 10.1007/BF01396176
Yi Jin and Bahman Kalantari, Symmetric functions and root-finding algorithms, Adv. in Appl. Math. 34 (2005), no. 1, 156–174. MR 2102280, DOI 10.1016/j.aam.2004.05.005
Y. Jin, Combinatorics of polynomial root-finding algorithms, Ph.D. dissertation, Dept. of Computer Science, Rutgers University, New Brunswick, NJ, October 2005.
Yi Jin, On efficient computation and asymptotic sharpness of Kalantari’s bounds for zeros of polynomials, Math. Comp. 75 (2006), no. 256, 1905–1912. MR 2240641, DOI 10.1090/S0025-5718-06-01868-0
Bahman Kalantari, Iraj Kalantari, and Rahim Zaare-Nahandi, A basic family of iteration functions for polynomial root finding and its characterizations, J. Comput. Appl. Math. 80 (1997), no. 2, 209–226. MR 1455244, DOI 10.1016/S0377-0427(97)00014-9
Bahman Kalantari, Generalization of Taylor’s theorem and Newton’s method via a new family of determinantal interpolation formulas and its applications, J. Comput. Appl. Math. 126 (2000), no. 1-2, 287–318. MR 1806762, DOI 10.1016/S0377-0427(99)00360-X
B. Kalantari and Y. Jin, On extraneous fixed-points of the basic family of iteration functions, BIT 43 (2003), no. 2, 453–458. MR 2010487, DOI 10.1023/A:1026095904985
Bahman Kalantari, On homogeneous linear recurrence relations and approximation of zeros of complex polynomials, Unusual applications of number theory, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 64, Amer. Math. Soc., Providence, RI, 2004, pp. 125–143. MR 2063208
Bahman Kalantari, An infinite family of bounds on zeros of analytic functions and relationship to Smale’s bound, Math. Comp. 74 (2005), no. 250, 841–852. MR 2114651, DOI 10.1090/S0025-5718-04-01686-2
H. T. Kung, A new upper bound on the complexity of derivative evaluation, Information Processing Lett. 2 (1973), 146–147. MR 347135, DOI 10.1016/0020-0190(74)90053-2
I. G. Macdonald, Symmetric functions and Hall polynomials, 2nd ed., Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1995. With contributions by A. Zelevinsky; Oxford Science Publications. MR 1354144
E. Schröder, Ueber unendlich viele Algorithmen zur Auflösung der Gleichungen, Math. Ann. 2 (1870), no. 2, 317–365 (German). MR 1509664, DOI 10.1007/BF01444024