A constructive algorithm for finding the exact roots of polynomials with computable real coefficients.

DOI10.1016/S0304-3975(00)00426-6MaRDI QIDQ1603892zbMATH OpenFDO

Authors Scott Chambers, Heoi Lee Lu, David R. Lester

Publication date 15 July 2002

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0304-3975(00)00426-6

zbMATH Keywords

computable arithmeticerror analysisJenkins' and Traub's algorithmpolynomial roots

Mathematics Subject Classification ID

Real polynomials: location of zeros (26C10) Numerical computation of solutions to single equations (65H05)

Review text

A constructive algorithm for finding the exact roots of polynomials with computable real coefficients is given. After a short introduction to computability and arithmetic and the properties of the roots of polynomials, an error analysis is presented. As the main result the authors prove the dependence of the roots with respect to perturbations of the coefficients. After a discussion of how to align the roots, the complete algorithm, which is based on the algorithms by \textit{M. A. Jenkins} and \textit{J. F. Traub} [SIAM J. Numer. Anal. 7, 545--566 (1970; Zbl 0237.65034)], is described.

Recommendations

• Design, analysis, and implementation of a multiprecision polynomial rootfinder
• Algorithms and Computation
• scientific article; zbMATH DE number 1500715
• Exact computation of polynomial zeros expressible by square roots
• Computing the real roots of a polynomial by the exclusion algorithm

Cites work

• A Three-Stage Algorithm for Real Polynomials Using Quadratic Iteration
• A three-stage variable-shift iteration for polynomial zeros and its relation to generalized Rayleigh iteration
• scientific article; zbMATH DE number 432500 (Why is no real title available?)
• scientific article; zbMATH DE number 3886959 (Why is no real title available?)
• scientific article; zbMATH DE number 3970003 (Why is no real title available?)
• scientific article; zbMATH DE number 4070894 (Why is no real title available?)
• scientific article; zbMATH DE number 42077 (Why is no real title available?)
• scientific article; zbMATH DE number 846277 (Why is no real title available?)
• scientific article; zbMATH DE number 3408799 (Why is no real title available?)

Cited in

(8)

• Computing the real roots of a polynomial by the exclusion algorithm
• Comparing representations for function spaces in computable analysis
• Intersection of a ruled surface with a free-form surface
• A combinatorial construction of high order algorithms for finding polynomial roots of known multiplicity
• Finding polynomial roots: A fast algorithm convergent on the complex plane
• A fitting algorithm for real coefficient polynomial rooting
• A complete algorithm to find exact minimal polynomial by approximations
• Coefficient-free adaptations of polynomial root-finders

Describes a project that uses

Uses Software

• Haskell
• mctoolbox

This page was built for publication: A constructive algorithm for finding the exact roots of polynomials with computable real coefficients.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1603892)