A basic family of iteration functions for polynomial root finding and its characterizations

Bahman Kalantari, Iraj Kalantari, Rahim Zaare-Nahandi

Research output: Contribution to journalArticlepeer-review

35 Scopus citations


Let p(x) be a polynomial of degree n >2 with coefficients in a subfield K of the complex numbers. For each natural number m2, let £OT{,x) be the /H xm lower triangular matrix whose diagonal entries are p(x) and for each j=\,...,m-l, its yth subdiagonal entries are p(J)(x)/j\. For / = 1,2, let L(X) be the matrix obtained from Lm(x) by deleting its first i rows and its last / columns. L\l\x)=l. Then, the function Bm(x) = x- p(x) det(L(_}(x))/det(L\x)) defines a fixed-point iteration function having mth order convergence rate for simple roots of p(x). For m -1 and 3, Bm(x) coincides with Newton's and Halley's, respectively. The function Bm(x) is a member of S(wi,w + /i-2), where for any Mm, S(m,M) is the set of all rational iteration functions g(x) E K(X) such that for all roots 9 of p(x), then g(x)=&+Y=m >'''(* )(#-*)'» witn }',{*)£ (*) and well-defined at any simple root O. Given gc.S(m,M), and a simple root O of p(x), g(l](8) = Q, i= 1,..., m- 1, and the asymptotic constant of convergence of the corresponding fixed-point iteration is ym(0) = (-l)mg(m\0)/m\. For 5ffl(j) we obtain ym(d) = (~\)mfet(L%)+l(6))/det(Lt£\0)'). If all roots of /J(A:) are simple, £.,(*) is the unique member of S(m,m + n- 2). By making use of the identity O = =0[/jfi|(;c)/V!](fl - x)', we arrive at two recursive formulas for constructing iteration functions within the S(m,M) family. In particular, the family of Bm(x) can be generated using one of these formulas. Moreover, the other formula gives a simple scheme for constructing a family of iteration functions credited to Euler as well as Schröder, whose mth order member belongs to S(m,mn), m>2. The iteration functions within S(m,M) can be extended to any arbitrary smooth function /, with the uniform replacement of p(J) with /('} in g as well as in ym(S).

Original languageEnglish (US)
Pages (from-to)209-226
Number of pages18
JournalJournal of Computational and Applied Mathematics
Issue number2
StatePublished - May 5 1997

All Science Journal Classification (ASJC) codes

  • Computational Mathematics
  • Applied Mathematics


  • Iteration functions
  • Newton's method
  • Roots


Dive into the research topics of 'A basic family of iteration functions for polynomial root finding and its characterizations'. Together they form a unique fingerprint.

Cite this