Algorithms for quaternion polynomial root-finding

Research output: Contribution to journalArticle

16 Citations (Scopus)

Abstract

In 1941 Niven pioneered root-finding for a quaternion polynomial P(x), proving the fundamental theorem of algebra (FTA) and proposing an algorithm, practical if the norm and trace of a solution are known. We present novel results on theory, algorithms and applications of quaternion root-finding. Firstly, we give a new proof of the FTA resulting in explicit formulas for both exact and approximate quaternion roots of P(x) in terms of exact and approximate complex roots of the real polynomial F(x)=P(x)P̄(x), where P̄(x) is the conjugate polynomial. In particular, if |F(c)|≤Ïμ, then for a computable quaternion conjugate q of c, |P(q)|≤Ïμ. Consequences of these include relevance of root-finding methods for complex polynomials, computation of bounds on zeros, and algebraic solution of special quaternion equations. Secondly, working directly in the quaternion space, we develop Newton and Halley methods and analyze their local behavior. Surprisingly, even for a quadratic quaternion polynomial Newton's method may not converge locally. Finally, we derive an analogue of the Bernoulli method in the quaternion space for computing the dominant root in certain cases. This requires the development of an independent theory for the solution of quaternion homogeneous linear recurrence relations. These results also lay a foundation for quaternion polynomiography.

Original languageEnglish (US)
Pages (from-to)302-322
Number of pages21
JournalJournal of Complexity
Volume29
Issue number3-4
DOIs
StatePublished - Jan 1 2013

Fingerprint

Polynomial Roots
Root-finding
Quaternion
Polynomials
Algebra
Fundamental theorem of algebra
Roots
Newton-Raphson method
Newton Methods
Polynomial
Linear Recurrence Relation
Halley's Method
Polynomial Methods
Complex Polynomials
Bernoulli
Explicit Formula
Trace

All Science Journal Classification (ASJC) codes

  • Algebra and Number Theory
  • Statistics and Probability
  • Numerical Analysis
  • Control and Optimization
  • Applied Mathematics

Cite this

@article{c9e77527d6a24b44a2db13b59ea0b040,
title = "Algorithms for quaternion polynomial root-finding",
abstract = "In 1941 Niven pioneered root-finding for a quaternion polynomial P(x), proving the fundamental theorem of algebra (FTA) and proposing an algorithm, practical if the norm and trace of a solution are known. We present novel results on theory, algorithms and applications of quaternion root-finding. Firstly, we give a new proof of the FTA resulting in explicit formulas for both exact and approximate quaternion roots of P(x) in terms of exact and approximate complex roots of the real polynomial F(x)=P(x)P̄(x), where P̄(x) is the conjugate polynomial. In particular, if |F(c)|≤{\"I}μ, then for a computable quaternion conjugate q of c, |P(q)|≤{\"I}μ. Consequences of these include relevance of root-finding methods for complex polynomials, computation of bounds on zeros, and algebraic solution of special quaternion equations. Secondly, working directly in the quaternion space, we develop Newton and Halley methods and analyze their local behavior. Surprisingly, even for a quadratic quaternion polynomial Newton's method may not converge locally. Finally, we derive an analogue of the Bernoulli method in the quaternion space for computing the dominant root in certain cases. This requires the development of an independent theory for the solution of quaternion homogeneous linear recurrence relations. These results also lay a foundation for quaternion polynomiography.",
author = "Bahman Kalantari",
year = "2013",
month = "1",
day = "1",
doi = "10.1016/j.jco.2013.03.001",
language = "English (US)",
volume = "29",
pages = "302--322",
journal = "Journal of Complexity",
issn = "0885-064X",
publisher = "Academic Press Inc.",
number = "3-4",

}

Algorithms for quaternion polynomial root-finding. / Kalantari, Bahman.

In: Journal of Complexity, Vol. 29, No. 3-4, 01.01.2013, p. 302-322.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Algorithms for quaternion polynomial root-finding

AU - Kalantari, Bahman

PY - 2013/1/1

Y1 - 2013/1/1

N2 - In 1941 Niven pioneered root-finding for a quaternion polynomial P(x), proving the fundamental theorem of algebra (FTA) and proposing an algorithm, practical if the norm and trace of a solution are known. We present novel results on theory, algorithms and applications of quaternion root-finding. Firstly, we give a new proof of the FTA resulting in explicit formulas for both exact and approximate quaternion roots of P(x) in terms of exact and approximate complex roots of the real polynomial F(x)=P(x)P̄(x), where P̄(x) is the conjugate polynomial. In particular, if |F(c)|≤Ïμ, then for a computable quaternion conjugate q of c, |P(q)|≤Ïμ. Consequences of these include relevance of root-finding methods for complex polynomials, computation of bounds on zeros, and algebraic solution of special quaternion equations. Secondly, working directly in the quaternion space, we develop Newton and Halley methods and analyze their local behavior. Surprisingly, even for a quadratic quaternion polynomial Newton's method may not converge locally. Finally, we derive an analogue of the Bernoulli method in the quaternion space for computing the dominant root in certain cases. This requires the development of an independent theory for the solution of quaternion homogeneous linear recurrence relations. These results also lay a foundation for quaternion polynomiography.

AB - In 1941 Niven pioneered root-finding for a quaternion polynomial P(x), proving the fundamental theorem of algebra (FTA) and proposing an algorithm, practical if the norm and trace of a solution are known. We present novel results on theory, algorithms and applications of quaternion root-finding. Firstly, we give a new proof of the FTA resulting in explicit formulas for both exact and approximate quaternion roots of P(x) in terms of exact and approximate complex roots of the real polynomial F(x)=P(x)P̄(x), where P̄(x) is the conjugate polynomial. In particular, if |F(c)|≤Ïμ, then for a computable quaternion conjugate q of c, |P(q)|≤Ïμ. Consequences of these include relevance of root-finding methods for complex polynomials, computation of bounds on zeros, and algebraic solution of special quaternion equations. Secondly, working directly in the quaternion space, we develop Newton and Halley methods and analyze their local behavior. Surprisingly, even for a quadratic quaternion polynomial Newton's method may not converge locally. Finally, we derive an analogue of the Bernoulli method in the quaternion space for computing the dominant root in certain cases. This requires the development of an independent theory for the solution of quaternion homogeneous linear recurrence relations. These results also lay a foundation for quaternion polynomiography.

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

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

U2 - 10.1016/j.jco.2013.03.001

DO - 10.1016/j.jco.2013.03.001

M3 - Article

VL - 29

SP - 302

EP - 322

JO - Journal of Complexity

JF - Journal of Complexity

SN - 0885-064X

IS - 3-4

ER -