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

David Lester, Scott Chambers, Heoi Lee Lu

    Research output: Contribution to journalArticlepeer-review

    Abstract

    In this paper we will show that it is possible to generate the roots of monic polynomials with computable real coefficients 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 effective method for finding 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 effectivization 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. © 2002 Elsevier Science B.V. All rights reserved.
    Original languageEnglish
    Pages (from-to)51-64
    Number of pages13
    JournalTheoretical Computer Science
    Volume279
    Issue number1-2
    DOIs
    Publication statusPublished - 28 May 2002

    Keywords

    • Computable arithmetic
    • Polynomial roots

    Fingerprint

    Dive into the research topics of 'A constructive algorithm for finding the exact roots of polynomials with computable real coefficients'. Together they form a unique fingerprint.

    Cite this