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
Additional Information
- Yi Jin
- Affiliation: Quantitative Research, Interest Rate Derivatives, J.P. Morgan, 270 Park Avenue, New York, New York 10017
- Email: yi.x.jin@jpmorgan.com
- Bahman Kalantari
- Affiliation: Department of Computer Science, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Road, Piscataway, New Jersey 08854
- Email: kalantar@cs.rutgers.edu
- Received by editor(s): December 4, 2007
- Published electronically: February 5, 2010
- Additional Notes: The main idea of this article was developed in the first author’s Ph.D. dissertation [5], supervised by the second author.
- Communicated by: Peter A. Clarkson
- © Copyright 2010 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 138 (2010), 1897-1906
- MSC (2010): Primary 05E05, 05A15, 65D15; Secondary 65Q05, 65H05
- DOI: https://doi.org/10.1090/S0002-9939-10-10309-8
- MathSciNet review: 2596023