### 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 language | English (US) |
---|---|

Pages (from-to) | 302-322 |

Number of pages | 21 |

Journal | Journal of Complexity |

Volume | 29 |

Issue number | 3-4 |

DOIs | |

State | Published - Jan 1 2013 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

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

### Cite this

*Journal of Complexity*,

*29*(3-4), 302-322. https://doi.org/10.1016/j.jco.2013.03.001

}

*Journal of Complexity*, vol. 29, no. 3-4, pp. 302-322. https://doi.org/10.1016/j.jco.2013.03.001

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

Research output: Contribution to journal › Article

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

AN - SCOPUS:84878533047

VL - 29

SP - 302

EP - 322

JO - Journal of Complexity

JF - Journal of Complexity

SN - 0885-064X

IS - 3-4

ER -