×

Choosing improved initial values for polynomial zerofinding in extended Newbery method to obtain convergence. (English) Zbl 1251.65070

Summary: In all polynomial zerofinding algorithms, a good convergence requires a very good initial approximation of the exact roots. The objective of the work is to study the conditions for determining the initial approximations for an iterative matrix zerofinding method. The investigation is based on the Newbery’s matrix construction which is similar to Fiedler’s construction associated with a characteristic polynomial. To ensure that convergence to both the real and complex roots of polynomials can be attained, three methods are employed. It is found that the initial values for the Fiedler’s companion matrix which is supplied by the Schmeisser’s method give a better approximation to the solution in comparison to when working on these values using the Schmeisser’s construction towards finding the solutions. In addition, empirical results suggest that a good convergence can still be attained when an initial approximation for the polynomial root is selected away from its real value while other approximations should be sufficiently close to their real values. Tables and figures on the errors that resulted from the implementation of the method are also given.

MSC:

65H05 Numerical computation of solutions to single equations

Software:

MultRoot
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] J. H. Wilkinson, Rounding Errors in Algebraic Processes, Prentice-Hall, Englewood Cliffs, NJ, USA, 1963. · Zbl 1041.65502
[2] J. H. Wilkinson, The Algebraic Eigenvalue Problem, Clarendon Press, Oxford, UK, 1965. · Zbl 0258.65037
[3] L. V. Foster, “Generalizations of laguerre’s method: higher order methods,” SIAM Journal on Numerical Analysis, vol. 18, no. 6, pp. 1004-1018, 1981. · Zbl 0554.65036
[4] M. A. Jenkins and J. F. Traub, “A three-stage variable-shift iteration for polynomial zeros and its relation to generalized rayleigh iteration,” Numerische Mathematik, vol. 14, pp. 252-263, 1969/1970. · Zbl 0176.13701
[5] M. A. Jenkins and J. F. Traub, “Algorithm 419-zeros of a complex polynomial,” Communications of the ACM, vol. 15, no. 2, pp. 97-99, 1972.
[6] E. Hansen, M. Patrick, and J. Rusnak, “Some modificiations of laguerre’s method,” BIT Numerical Mathematics, vol. 17, no. 4, pp. 409-417, 1977. · Zbl 0386.65013
[7] K. C. Toh and L. N. Trefethen, “Pseudozeros of Polynomial and Pseudo spectra of companion matrices,” Technical Report TR 93-1360, Department of Computer Science, Cornell University, Ithaca, NY, USA, 1993.
[8] K. Madsen and J. Reid, “Fortran subroutines for finding polynomial zeros,” Tech. Rep. HL.75/1172(C.13), Computer Science and Systems Division, A.E.R.E., Harwell, UK, 1975.
[9] T. E. Hull and R. Mathon, The Mathematical Basis for a New Polynomial Rootfinder with Quadratic Convergence, Department of Computer Science, University of Toronto, Ontario, Canada, 1993. · Zbl 0884.65042
[10] C. D. Yan and W. H. Chieng, “Method for finding multiple roots of polynomials,” Computers & Mathematics with Applications, vol. 51, no. 3-4, pp. 605-620, 2006. · Zbl 1100.65045
[11] J. R. Winkler, Polynomial Roots and Approximate Greatest Common Divisors, Lecture Notes for a Summer School, The Computer Laboratory the University of Oxford, 2007.
[12] Z. Zeng, “Computing multiple roots of inexact polynomials,” Mathematics of Computation, vol. 74, no. 250, pp. 869-903, 2005. · Zbl 1079.12007
[13] F. Malek and R. Vaillancourt, “Polynomial zerofinding iterative matrix algorithms,” Computers & Mathematics with Applications, vol. 29, no. 1, pp. 1-13, 1995. · Zbl 0812.65039
[14] A. C. R. Newbery, “A family of test matrices,” Communications of the Association for Computing Machinery, vol. 7, p. 724, 1964. · Zbl 0126.32104
[15] M. Fiedler, “Expressing a polynomial as the characteristic polynomial of a symmetric matrix,” Linear Algebra and its Applications, vol. 141, pp. 265-270, 1990. · Zbl 0721.15005
[16] G. Schmeisser, “A real symmetric tridiagonal matrix with a given characteristic polynomial,” Linear Algebra and its Applications, vol. 193, pp. 11-18, 1993. · Zbl 0793.15009
[17] M. Fiedler, “Numerical solution of algebraic equations which have roots with almost the same modulus,” Aplikace Matematiky, vol. 1, pp. 4-22, 1956.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.