"Записки научных семинаров ПОМИ"

Том 373, стр. 5-33

Department of Computer and Communication Engineering University of Thessaly Greece

akritas@uth.gr

Аннотация: В этой статье мы представляем две различные версии теоремы Винсента (1836) и обсуждаем основанные на ней методы отделения корней полиномов: один, использующий технику цепных дробей , и второй, использующий бисекции -- еще недавно являвшийся самым быстрым. Мы показываем, что, используя новые алгоритмы квадратичной сложности получения оценок положительных корней полиномов, эффективность метода, основанного на цепных дробях, может быть увеличена в среднем на 40% по сравнению с первоначальной реализацией. Обсуждаются также некоторые возможные направления дальнейших исследований в этой области. Библ. -- 45 назв.
Ключевые слова: отделение корней, цепные дроби, сложность, теорема Винсента [root isolation, continuous fractions, complexity, Vincent's theorem]