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

Bahman Kalantari, Iraj Kalantari, Rahim Zaare-Nahandi

Research output: Contribution to journalArticle

35 Citations (Scopus)

Abstract

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
Volume80
Issue number2
DOIs
StatePublished - May 5 1997

Fingerprint

Iteration Function
Polynomial Roots
Root-finding
Polynomials
Roots
Fixed Point Iteration
Lower triangular matrix
Order of a polynomial
Recursive Formula
Subfield
Complex number
Natural number
Smooth function
Rational function
Replacement
Convergence Rate
Euler
Well-defined
Rational functions
Family

All Science Journal Classification (ASJC) codes

  • Computational Mathematics
  • Applied Mathematics

Cite this

@article{37276436deac4040a016a0bf39c3f822,
title = "A basic family of iteration functions for polynomial root finding and its characterizations",
abstract = "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{\"o}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).",
author = "Bahman Kalantari and Iraj Kalantari and Rahim Zaare-Nahandi",
year = "1997",
month = "5",
day = "5",
doi = "10.1016/S0377-0427(97)00014-9",
language = "English (US)",
volume = "80",
pages = "209--226",
journal = "Journal of Computational and Applied Mathematics",
issn = "0377-0427",
publisher = "Elsevier",
number = "2",

}

A basic family of iteration functions for polynomial root finding and its characterizations. / Kalantari, Bahman; Kalantari, Iraj; Zaare-Nahandi, Rahim.

In: Journal of Computational and Applied Mathematics, Vol. 80, No. 2, 05.05.1997, p. 209-226.

Research output: Contribution to journalArticle

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

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

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

VL - 80

SP - 209

EP - 226

JO - Journal of Computational and Applied Mathematics

JF - Journal of Computational and Applied Mathematics

SN - 0377-0427

IS - 2

ER -