A combinatorial construction of high order algorithms for finding polynomial roots of known multiplicity

Research output: Contribution to journalArticle

1 Citation (Scopus)

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 B̂2(x) = x - s • 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.

Original languageEnglish (US)
Pages (from-to)1897-1906
Number of pages10
JournalProceedings of the American Mathematical Society
Volume138
Issue number6
DOIs
StatePublished - Jun 1 2010

Fingerprint

Polynomial Roots
Iteration Function
Multiplicity
Polynomials
Higher Order
Newton-Raphson method
Halley's Method
Root of a polynomial
Multiple Roots
Root-finding
Date
Newton Methods
Roots
Demonstrate
Family

All Science Journal Classification (ASJC) codes

  • Mathematics(all)
  • Applied Mathematics

Keywords

  • Generating functions
  • Iteration functions
  • Multiple roots
  • Recurrence relation
  • Root-finding
  • Symmetric functions

Cite this

@article{fe1a311200274292b35cd72bdffd50d5,
title = "A combinatorial construction of high order algorithms for finding polynomial roots of known multiplicity",
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{\"o}der's 1870 paper. It starts with the well known variant of Newton's method B̂2(x) = x - s • 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.",
keywords = "Generating functions, Iteration functions, Multiple roots, Recurrence relation, Root-finding, Symmetric functions",
author = "Yi Jin and Bahman Kalantari",
year = "2010",
month = "6",
day = "1",
doi = "10.1090/S0002-9939-10-10309-8",
language = "English (US)",
volume = "138",
pages = "1897--1906",
journal = "Proceedings of the American Mathematical Society",
issn = "0002-9939",
publisher = "American Mathematical Society",
number = "6",

}

TY - JOUR

T1 - A combinatorial construction of high order algorithms for finding polynomial roots of known multiplicity

AU - Jin, Yi

AU - Kalantari, Bahman

PY - 2010/6/1

Y1 - 2010/6/1

N2 - 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 B̂2(x) = x - s • 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.

AB - 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 B̂2(x) = x - s • 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.

KW - Generating functions

KW - Iteration functions

KW - Multiple roots

KW - Recurrence relation

KW - Root-finding

KW - Symmetric functions

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

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

U2 - 10.1090/S0002-9939-10-10309-8

DO - 10.1090/S0002-9939-10-10309-8

M3 - Article

VL - 138

SP - 1897

EP - 1906

JO - Proceedings of the American Mathematical Society

JF - Proceedings of the American Mathematical Society

SN - 0002-9939

IS - 6

ER -