Symmetric functions and root-finding algorithms

Research output: Contribution to journalArticle

5 Citations (Scopus)

Abstract

We study a fundamental family of root-finding iteration functions in the context of symmetric functions. This family, which we refer to as the Basic Family, goes back to Schröder's 1870 paper, and admits numerous different representations. In one representation, it is known as König's family. A purely algebraic derivation by Kalantari et al. leads to the discovery of many minimality and uniqueness properties of this family. Our new perspective reveals a symmetric algebraic structure of the Basic Family, which gives rise to simple combinatorial proofs of many important properties of this family and two of its variants. The first variant maintains high order of convergence for multiple roots. The second variant, called the Truncated Basic Family, is an infinite family of mth order methods for every m ≥ 3, using only the first m - 1 derivatives. Our result extends Kalantari's analysis of Halley's family, the special case of the Truncated Basic Family where m = 3. Finally, we give a recipe for constructing new high order root-finding algorithms, and use it to derive an interesting family of iteration functions that have higher orders of convergence for multiple roots than for simple roots.

Original languageEnglish (US)
Pages (from-to)156-174
Number of pages19
JournalAdvances in Applied Mathematics
Volume34
Issue number1
DOIs
StatePublished - Jan 1 2005

Fingerprint

Root-finding
Symmetric Functions
Iteration Function
Derivatives
Multiple Roots
Order of Convergence
Higher Order
Family
Minimality
Algebraic Structure
Uniqueness

All Science Journal Classification (ASJC) codes

  • Applied Mathematics

Cite this

@article{c252023299534f4d8ebfa9b734221286,
title = "Symmetric functions and root-finding algorithms",
abstract = "We study a fundamental family of root-finding iteration functions in the context of symmetric functions. This family, which we refer to as the Basic Family, goes back to Schr{\"o}der's 1870 paper, and admits numerous different representations. In one representation, it is known as K{\"o}nig's family. A purely algebraic derivation by Kalantari et al. leads to the discovery of many minimality and uniqueness properties of this family. Our new perspective reveals a symmetric algebraic structure of the Basic Family, which gives rise to simple combinatorial proofs of many important properties of this family and two of its variants. The first variant maintains high order of convergence for multiple roots. The second variant, called the Truncated Basic Family, is an infinite family of mth order methods for every m ≥ 3, using only the first m - 1 derivatives. Our result extends Kalantari's analysis of Halley's family, the special case of the Truncated Basic Family where m = 3. Finally, we give a recipe for constructing new high order root-finding algorithms, and use it to derive an interesting family of iteration functions that have higher orders of convergence for multiple roots than for simple roots.",
author = "Yi Jin and Bahman Kalantari",
year = "2005",
month = "1",
day = "1",
doi = "10.1016/j.aam.2004.05.005",
language = "English (US)",
volume = "34",
pages = "156--174",
journal = "Advances in Applied Mathematics",
issn = "0196-8858",
publisher = "Academic Press Inc.",
number = "1",

}

Symmetric functions and root-finding algorithms. / Jin, Yi; Kalantari, Bahman.

In: Advances in Applied Mathematics, Vol. 34, No. 1, 01.01.2005, p. 156-174.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Symmetric functions and root-finding algorithms

AU - Jin, Yi

AU - Kalantari, Bahman

PY - 2005/1/1

Y1 - 2005/1/1

N2 - We study a fundamental family of root-finding iteration functions in the context of symmetric functions. This family, which we refer to as the Basic Family, goes back to Schröder's 1870 paper, and admits numerous different representations. In one representation, it is known as König's family. A purely algebraic derivation by Kalantari et al. leads to the discovery of many minimality and uniqueness properties of this family. Our new perspective reveals a symmetric algebraic structure of the Basic Family, which gives rise to simple combinatorial proofs of many important properties of this family and two of its variants. The first variant maintains high order of convergence for multiple roots. The second variant, called the Truncated Basic Family, is an infinite family of mth order methods for every m ≥ 3, using only the first m - 1 derivatives. Our result extends Kalantari's analysis of Halley's family, the special case of the Truncated Basic Family where m = 3. Finally, we give a recipe for constructing new high order root-finding algorithms, and use it to derive an interesting family of iteration functions that have higher orders of convergence for multiple roots than for simple roots.

AB - We study a fundamental family of root-finding iteration functions in the context of symmetric functions. This family, which we refer to as the Basic Family, goes back to Schröder's 1870 paper, and admits numerous different representations. In one representation, it is known as König's family. A purely algebraic derivation by Kalantari et al. leads to the discovery of many minimality and uniqueness properties of this family. Our new perspective reveals a symmetric algebraic structure of the Basic Family, which gives rise to simple combinatorial proofs of many important properties of this family and two of its variants. The first variant maintains high order of convergence for multiple roots. The second variant, called the Truncated Basic Family, is an infinite family of mth order methods for every m ≥ 3, using only the first m - 1 derivatives. Our result extends Kalantari's analysis of Halley's family, the special case of the Truncated Basic Family where m = 3. Finally, we give a recipe for constructing new high order root-finding algorithms, and use it to derive an interesting family of iteration functions that have higher orders of convergence for multiple roots than for simple roots.

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

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

U2 - 10.1016/j.aam.2004.05.005

DO - 10.1016/j.aam.2004.05.005

M3 - Article

VL - 34

SP - 156

EP - 174

JO - Advances in Applied Mathematics

JF - Advances in Applied Mathematics

SN - 0196-8858

IS - 1

ER -