Affordable Access

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

Publication Date
  • Computer Science
  • Mathematics


PII: S0304-3975(00)00426-6 Theoretical Computer Science 279 (2002) 51–64 A constructive algorithm for $nding the exact roots of polynomials with computable real coe)cients David Lester ∗, Scott Chambers, Heoi Lee Lu Department of Computer Science, Manchester University, Oxford Road, Manchester M13 9PL, UK Abstract In this paper we will show that it is possible to generate the roots of monic polynomials with computable real coe)cients as computable complex numbers. A result from constructive analysis has already shown that the roots are computable numbers; however, because the proof is non-constructive it does not provide an e1ective method for $nding the roots. In this work we combine two extra stages to a standard numerical algorithm: an exact error analysis, and a method for aligning sets of complex rational numbers so that the result is a set of computable complex numbers. The method of e1ectivization is of interest as it can be used in other situations where an algorithm will work with rational approximations, but comparison operations prevent its use with computable numbers. c© 2002 Elsevier Science B.V. All rights reserved. Keywords: Computable arithmetic; Polynomial roots 1. Introduction Finding the roots of polynomials with rational coe)cients (the algebraic eigenvalue problem) has already been well studied [4, 10, 11]; what we seek to demonstrate in this paper is that one can $nd the roots of the more general polynomial with computable real coe)cients. That the roots are computable numbers is a result from constructive analysis [1] and is demonstrated (non-constructively) by the computable analogue to the intermediate value theorem, see [9, Theorem 8, p. 41]. Although we know that the roots are computable numbers, because the proof is non-constructive we do not have a method for $nding them. This paper describes a method for $nding the roots by providing a constructive proof that they are computable numbers. In Sections 2 and 3 we outline some b

There are no comments yet on this publication. Be the first to share your thoughts.