TY - JOUR

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

AU - Kalantari, Bahman

AU - Kalantari, Iraj

AU - Zaare-Nahandi, Rahim

N1 - Funding Information:
author. E-mail: kalantar@cs.rutgers.edu. is supported in part by the National Science Foundation under Grant No. CCR-9208371. is supported in part by a grant from University of Tehran.

PY - 1997/5/5

Y1 - 1997/5/5

N2 - 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).

AB - 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).

KW - Iteration functions

KW - Newton's method

KW - Roots

UR - http://www.scopus.com/inward/record.url?scp=0031554218&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0031554218&partnerID=8YFLogxK

U2 - 10.1016/S0377-0427(97)00014-9

DO - 10.1016/S0377-0427(97)00014-9

M3 - Article

AN - SCOPUS:0031554218

SN - 0377-0427

VL - 80

SP - 209

EP - 226

JO - Journal of Computational and Applied Mathematics

JF - Journal of Computational and Applied Mathematics

IS - 2

ER -