×

Algorithms for quaternion polynomial root-finding. (English) Zbl 1326.65060

Summary: In [Am. Math. Mon. 48, 654–661 (1941; Zbl 0060.08002)], I. 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)\overline P(x)\), where \(\overline P(x)\) is the conjugate polynomial. In particular, if \(|F(c)|\leq \epsilon\), then for a computable quaternion conjugate \(q\) of \(c\), \(|P(q)|\leq \sqrt {\epsilon}\). 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.

MSC:

65H04 Numerical computation of roots of polynomial equations
68W30 Symbolic computation and algebraic computation
16Z05 Computational aspects of associative rings (general theory)

Citations:

Zbl 0060.08002
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adler, S., Quaternionic Quantum Mechanics and Quantum Fields (1995), Oxford University Press: Oxford University Press New York · Zbl 0885.00019
[2] Beardon, A. F., Iteration of Rational Functions: Complex Analytic Dynamical Systems (1991), Springer-Verlag: Springer-Verlag New York · Zbl 0742.30002
[3] Beck, B., Sur les équations polynomiales dans les quaternions, Enseign. Math., 25, 193-201 (1979) · Zbl 0452.12008
[4] Bedding, S.; Briggs, K., Iteration of quaternion functions, Amer. Math. Monthly, 103, 654-664 (1996) · Zbl 0947.30017
[5] Brand, L., The roots of a quaternion, Amer. Math. Monthly, 48, 519-520 (1942) · Zbl 0061.01408
[6] Bray, U.; Whaples, G., Polynomials with coefficients from a division ring, Canad. J. Math., 35, 509-515 (1983) · Zbl 0496.16022
[7] Cho, E., De Moivre’s formula for quaternions, Appl. Math. Lett., 11, 33-35 (1998) · Zbl 0938.11055
[8] De Leo, S.; Ducati, G.; Leonardi, V., Zeros of unilateral quaternionic polynomials, Electron. J. Linear Algebra, 15, 297-313 (2006) · Zbl 1151.15303
[9] Eilenberg, S.; Niven, I., The “Fundamental Theorem of Algebra” for quaternions, Bull. Amer. Math. Soc., 50, 246-248 (1944) · Zbl 0063.01228
[10] Gordon, B.; Motzkin, T. S., On the zeros of polynomials over division rings, Trans. Amer. Math. Soc., 116, 218-226 (1965) · Zbl 0141.03002
[11] Heidrich, R.; Jank, G., On the iteration of quaternionic Möbius transformations, Complex Var., 29, 313-318 (1996) · Zbl 0860.30041
[12] Henrici, P., Applied and Computational Complex Analysis, Volume I (1974), Wiley: Wiley New York
[13] Hildebrand, F. B., Introduction to Numerical Analysis (1974), McGraw-Hill: McGraw-Hill New York · Zbl 0279.65001
[14] Householder, A. S., The Numerical Treatment of a Single Nonlinear Equation (1970), McGraw-Hill: McGraw-Hill New York · Zbl 0242.65047
[15] Huang, L.; So, W., On left eigenvalues of quaternionic equations, Linear Algebra Appl., 323, 105-116 (2001) · Zbl 0976.15014
[16] Huang, L.; So, W., Quadratic formulas for quaternions, Appl. Math. Lett., 15, 533-540 (2002) · Zbl 1011.15010
[17] Janovska, D.; Opfer, G., Computing quaternionic roots by Newton’s method, Electron. Trans. Numer. Anal., 26, 82-102 (2007) · Zbl 1160.65016
[18] Jenkins, M. A.; Traub, J. F., A three-stage variable-shift iteration for polynomial zeros and its relation to generalized Rayleigh iteration, Numer. Math., 14, 252-263 (1970) · Zbl 0176.13701
[19] Jia, Z.; Cheng, X.; Zhao, M., A new method for roots of monic quaternionic quadratic polynomial, Comput. Math. Appl., 58, 1852-1858 (2007) · Zbl 1189.65090
[20] Jin, Y., On efficient computation and asymptotic sharpness of Kalantari’s bounds for zeros of polynomials, Math. Comp., 75, 1905-1912 (2006) · Zbl 1171.65397
[21] Kalantari, B., Generalization of Taylor’s theorem and Newton’s method via a new family of determinantal interpolation formulas and its applications, J. Comput. Appl. Math., 126, 287-318 (2000) · Zbl 0971.65040
[22] Kalantari, B., A new visual art medium: polynomiography, ACM SIGGRAPH Comput. Graph. Q., 38, 21-23 (2004)
[23] Kalantari, B., On homogeneous linear recurrence relations and approximation of zeros of complex polynomials, (Unusual Applications in Number Theory. Unusual Applications in Number Theory, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 64 (2004)), 125-143 · Zbl 1083.12001
[24] Kalantari, B., Polynomiography and applications in art, education, and science, Comput. Graph., 28, 417-430 (2004)
[25] Kalantari, B., An infinite family of bounds on zeros of analytic functions and relationship to Smale’s bound, Math. Comp., 74, 841-852 (2005) · Zbl 1137.65348
[26] Kalantari, B., Polynomiography: from the fundamental theorem of algebra to art, Leonardo, 38, 233-238 (2005)
[27] Kalantari, B., Polynomial Root-Finding and Polynomiography (2008), World Scientific: World Scientific New Jersey · Zbl 1218.37003
[28] Kalantari, B., Voronoi diagrams and polynomial root-finding, (Proceedings of the Sixth Annual International Symposium on Voronoi Diagrams in Science and Engineering (2009), IEEE: IEEE Copenhagen, Denmark), 31-40
[29] Kalantari, B., Polynomial root-finding methods whose basins of attraction approximate Voronoi diagram, Discrete Comput. Geom., 46, 187-203 (2011) · Zbl 1221.65111
[30] Kalantari, B.; Kalantari, I.; Zaare-Nahandi, R., A basic family of iteration functions for polynomial root finding and its characterizations, J. Comput. Appl. Math., 80, 209-226 (1997) · Zbl 0874.65037
[31] Lam, T. Y., A First Course in Noncommutative Rings (1991), Springer-Verlag: Springer-Verlag New York · Zbl 0728.16001
[32] Mandelbrot, B. B., The Fractal Geometry of Nature (1982), Freeman: Freeman San Francisco · Zbl 0504.28001
[33] McNamee, J. M., Numerical Methods for Roots of Polynomials: Part I, Volume 14 (2007), Elsevier: Elsevier Amsterdam · Zbl 1143.65002
[34] Milnor, J., Dynamics in One Complex Variable: Introductory Lectures, vol. 160 (2006), Princeton University Press: Princeton University Press New Jersey
[35] Neff, C. A.; Reif, J. H., An efficient algorithm for the complex roots problem, J. Complexity, 12, 81-115 (1996) · Zbl 0888.12005
[36] Niven, I., Equations in quaternions, Amer. Math. Monthly, 48, 654-661 (1941) · Zbl 0060.08002
[37] Niven, I., The roots of a quaternion, Amer. Math. Monthly, 49, 386-388 (1942) · Zbl 0061.01407
[38] Norton, A., Julia sets in the quaternions, Comput. Graph., 13, 267-278 (1989)
[39] Opfer, G., Polynomials and Vandermonde matrices over the field of quaternions, Electron. Trans. Numer. Anal., 36, 9-16 (2009) · Zbl 1196.11154
[40] Pan, V. Y., Solving a polynomial equation: some history and recent progress, SIAM Rev., 39, 187-220 (1997) · Zbl 0873.65050
[41] Pogorui, A.; Shapiro, M., On the structure of the set of zeros of quaternion polynomials, Complex Var., 49, 379-389 (2004) · Zbl 1160.30353
[42] Porter, M., Quaternionic linear and quadratic equations, J. Natur. Geom., 11, 101-106 (1997) · Zbl 0869.11024
[43] Renmin, H.; Xuqiang, Z.; Linagtao, W., The double determinant of Vandermonde’s type over quaternion field, Appl. Math. Mech., 20, 1046-1053 (1999) · Zbl 0953.15011
[44] Schröder, E., On infinitely many algorithms for solving equations, Math. Ann., 2, 317-365 (1870), (in German), English translation by G.W. Stewart, TR-92-121, Institute for Advanced Computer Studies, University of Maryland, College Park, MD, 1992
[45] Serodio, R.; Pereira, E.; Vitoria, J., Computing the zeros of quaternion polynomials, Comput. Math. Appl., 42, 1229-1237 (2001) · Zbl 1050.30037
[46] Serodio, R.; Siu, L., Zeros of quaternion polynomials, Appl. Math. Lett., 14, 237-239 (2001) · Zbl 0979.30030
[47] Traub, J. F., Iterative Methods for the Solution of Equations (1964), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0121.11204
[48] Zhang, F., Quaternions and matrices of quaternions, Linear Algebra Appl., 251, 21-57 (1997) · Zbl 0873.15008
[49] Zhang, F.; Mu, D. L., Quadratic equations over noncommutative rings, J. Math. Res. Exposition, 14, 260-264 (1994) · Zbl 0815.16007
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.