Изоляция реального корня

Методы нахождения действительных корней многочлена

В математике , а точнее в численном анализе и компьютерной алгебре , изоляция действительных корней многочлена заключается в создании непересекающихся интервалов действительной прямой , которые содержат каждый (и только один) действительный корень многочлена, и, вместе, содержат все действительные корни многочлена.

Изоляция действительных корней полезна, поскольку обычные алгоритмы поиска корней для вычисления действительных корней многочлена могут выдавать некоторые действительные корни, но, как правило, не могут гарантировать нахождение всех действительных корней. В частности, если такой алгоритм не находит ни одного корня, неизвестно, является ли это следствием отсутствия действительного корня. Некоторые алгоритмы вычисляют все комплексные корни, но, поскольку действительных корней, как правило, гораздо меньше, чем комплексных, большая часть времени их вычислений обычно тратится на вычисление недействительных корней (в среднем, многочлен степени n имеет n комплексных корней и только log n действительных корней; см. Геометрические свойства корней многочлена § Действительные корни ). Более того, может быть трудно отличить действительные корни от недействительных корней с малой мнимой частью (см. пример многочлена Уилкинсона в следующем разделе).

Первый полный алгоритм изоляции действительных корней вытекает из теоремы Штурма (1829). Однако, когда алгоритмы изоляции действительных корней начали внедряться на компьютерах, оказалось, что алгоритмы, полученные из теоремы Штурма, менее эффективны, чем те, которые получены из правила знаков Декарта (1637).

С начала 20-го века ведется активная исследовательская деятельность по улучшению алгоритмов, полученных из правила знаков Декарта, получению очень эффективных реализаций и вычислению их вычислительной сложности . Лучшие реализации могут регулярно выделять действительные корни многочленов степени более 1000. ^{[1] [2]}

Технические характеристики и общая стратегия

Для нахождения действительных корней многочлена общая стратегия заключается в том, чтобы разделить действительную линию (или ее интервал, где ищутся корни) на непересекающиеся интервалы до тех пор, пока в каждом интервале не останется не более одного корня. Такая процедура называется изоляцией корня , а полученный интервал, содержащий ровно один корень, является изолирующим интервалом для этого корня.

Полином Уилкинсона показывает, что очень небольшое изменение одного коэффициента полинома может кардинально изменить не только значение корней, но и их природу (действительную или комплексную). Кроме того, даже при хорошем приближении, когда оценивается полином в приближенном корне, можно получить результат, далекий от нуля. Например, если полином степени 20 (степень полинома Уилкинсона) имеет корень, близкий к 10, производная полинома в корне может быть порядка это означает, что ошибка в значении корня может привести к значению полинома в приближенном корне, которое будет иметь порядок Из этого следует, что, за исключением, может быть, очень низких степеней, процедура изоляции корня не может дать надежных результатов без использования точной арифметики. Поэтому, если требуется выделить корни многочлена с коэффициентами с плавающей точкой , часто бывает лучше преобразовать их в рациональные числа , а затем взять примитивную часть полученного многочлена, чтобы получить многочлен с целыми коэффициентами. ${\displaystyle 10^{20};}$ ${\displaystyle 10^{-10}}$ ${\displaystyle 10^{10}.}$

По этой причине, хотя методы, описанные ниже, теоретически работают с действительными числами, на практике они обычно используются с многочленами с целыми коэффициентами и интервалами, заканчивающимися рациональными числами. Кроме того, многочлены всегда должны быть свободны от квадратов . Для этого есть две причины. Во-первых, алгоритм Юня для вычисления факторизации без квадратов менее затратен, чем удвоенная стоимость вычисления наибольшего общего делителя многочлена и его производной. Поскольку это может привести к получению множителей более низких степеней, обычно выгодно применять алгоритмы изоляции корней только к многочленам без кратных корней, даже если это не требуется алгоритмом. Вторая причина рассмотрения только многочленов без квадратов заключается в том, что самые быстрые алгоритмы изоляции корней не работают в случае кратных корней.

Для изоляции корней требуется процедура подсчета действительных корней многочлена в интервале без необходимости их вычисления или, по крайней мере, процедура принятия решения о том, содержит ли интервал ноль, один или несколько корней. С такой процедурой принятия решения можно работать с рабочим списком интервалов, которые могут содержать действительные корни. В начале список содержит один интервал, содержащий все интересующие корни, как правило, всю действительную линию или ее положительную часть. Затем каждый интервал списка делится на два меньших интервала. Если один из новых интервалов не содержит ни одного корня, он удаляется из списка. Если он содержит один корень, он помещается в выходной список изолирующих интервалов. В противном случае он сохраняется в рабочем списке для дальнейших делений, и процесс может продолжаться до тех пор, пока все корни в конечном итоге не будут изолированы

Теорема Штурма

Первая полная процедура изоляции корней является результатом теоремы Штурма (1829), которая выражает число действительных корней в интервале через число вариаций знаков значений последовательности многочленов, называемой последовательностью Штурма , на концах интервала. Последовательность Штурма — это последовательность остатков, которые встречаются в варианте евклидова алгоритма, примененного к многочлену и его производным. При реализации на компьютерах оказалось, что изоляция корней с помощью теоремы Штурма менее эффективна, чем другие методы, описанные ниже. ^[3] Следовательно, теорема Штурма редко используется для эффективных вычислений, хотя она остается полезной для теоретических целей.

Правило знаков Декарта и его обобщения

Правило знаков Декарта утверждает, что разность между числом вариаций знаков в последовательности коэффициентов многочлена и числом его положительных действительных корней является неотрицательным четным целым числом. Из этого следует, что если это число вариаций знаков равно нулю, то многочлен не имеет положительных действительных корней, а если это число равно единице, то многочлен имеет единственный положительный действительный корень, который является единственным корнем. К сожалению, обратное неверно, то есть многочлен, который либо не имеет положительных действительных корней, либо имеет единственный положительный простой корень, может иметь число вариаций знаков больше 1.

Это было обобщено теоремой Будана (1807) в аналогичный результат для действительных корней в полуоткрытом интервале ( a , b ]) : если f ( x ) — многочлен, а v — разность между числами изменений знаков последовательностей коэффициентов f ( x + a ) и f ( x + b ) , то v за вычетом числа действительных корней в интервале, подсчитанного с их кратностями, является неотрицательным четным целым числом. Это обобщение правила знаков Декарта, поскольку при достаточно большом b нет изменения знака в коэффициентах f ( x + b ) , и все действительные корни меньше b .

Будан может предоставить алгоритм изоляции действительных корней для бесквадратного многочлена (многочлена без кратных корней): из коэффициентов многочлена можно вычислить верхнюю границу M абсолютных значений корней и нижнюю границу m абсолютных значений разностей двух корней (см. Свойства корней многочлена ). Затем, если разделить интервал [– M , M ] на интервалы длины меньше m , то каждый действительный корень содержится в некотором интервале, и ни один интервал не содержит двух корней. Таким образом, изолирующие интервалы являются интервалами, для которых теорема Будана утверждает нечетное число корней.

Однако этот алгоритм очень неэффективен, так как нельзя использовать более грубое разбиение интервала [– M , M ] , поскольку, если теорема Будана дает результат больше 1 для интервала большего размера, нет способа гарантировать, что он не содержит нескольких корней.

Теоремы Винсента и родственные им теоремы

Теорема Винсента (1834)^[4]дает метод изоляции действительных корней, который лежит в основе наиболее эффективных алгоритмов изоляции действительных корней. Она касается положительных действительных корнейбесквадратного многочлена(то есть многочлена без кратных корней). Если— последовательность положительных действительных чисел, то пусть ${\displaystyle a_{1},a_{2},\ldots ,}$

${\displaystyle c_{k}=a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{a_{3}+{\cfrac {1}{\ddots +{\cfrac {1}{a_{k}}}}}}}}}}$

быть k- й подходящей дробью цепной дроби

${\displaystyle a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{a_{3}+{\cfrac {1}{\ddots }}}}}}.}$

Теорема Винсента  —  Пусть — свободный от квадратов многочлен степени n , а — последовательность действительных чисел. Для i = 1, 2,... рассмотрим многочлен ${\displaystyle p_{0}(x)}$ ${\displaystyle a_{1},a_{2},\ldots ,}$

${\displaystyle p_{i}(x)=x^{n}p_{i-1}\left(a_{i}+1/x\right).}$

Тогда существует целое число k такое, что либо , либо последовательность коэффициентов имеет не более одного изменения знака. ${\displaystyle p_{k}(0)=0,}$ ${\displaystyle p_{k}}$

В первом случае сходящийся c _k является положительным корнем В противном случае это число изменений знака (либо 0, либо 1) является числом действительных корней в интервале, определяемом и ${\displaystyle p_{0}.}$ ${\displaystyle p_{0}}$ ${\displaystyle c_{k-1}}$ ${\displaystyle c_{k}.}$

Для доказательства своей теоремы Винсент доказал результат, который полезен сам по себе: ^[4]

Вспомогательная теорема Винсента  —  Если p ( x ) — свободный от квадратов многочлен степени n , а a , b , c , d — неотрицательные действительные числа, такие, что достаточно мало (но не равно 0), то существует не более одного изменения знака в коэффициентах многочлена ${\displaystyle \left|{\frac {a}{c}}-{\frac {b}{d}}\right|}$

${\displaystyle q(x)=(cx+d)^{n}p\left({\frac {ax+b}{cx+d}}\right),}$

и это число изменений знака является числом действительных корней p ( x ) в открытом интервале, определяемом и ${\displaystyle {\frac {a}{c}}}$ ${\displaystyle {\frac {b}{d}}.}$

Для работы с действительными числами всегда можно выбрать c = d = 1 , но, поскольку эффективные вычисления выполняются с рациональными числами , обычно удобно предполагать, что a , b , c , d являются целыми числами.

Условие «достаточно малого» было количественно определено независимо Николой Обрешковым ^[5] и Александром Островским : ^[6]

Теорема Обрешкова–Островского: синим и желтым цветом обозначены области комплексной плоскости, где не должно быть корней, имеющих 0 или 1 изменение знака; слева — области, исключенные для корней p , справа — области, исключенные для корней преобразованного многочлена q ; синим цветом обозначены области, которые исключены из-за наличия одного изменения знака, но разрешены для нулевых изменений знака.

Теорема  (Обрешков–Островский)  —  Заключение вспомогательного результата Винсента справедливо, если многочлен p ( x ) имеет не более одного корня α + iβ такого, что

${\displaystyle \left(\alpha -{\frac {a}{c}}\right)\left(\alpha -{\frac {b}{d}}\right)+\beta ^{2}\leq {\frac {1}{\sqrt {3}}}\left|\beta \left({\frac {a}{c}}-{\frac {b}{d}}\right)\right|.}$

В частности, вывод справедлив, если

${\displaystyle \left|{\frac {a}{c}}-{\frac {b}{d}}\right|<{\frac {\operatorname {sep} (p)}{2{\sqrt {3}}}},}$

где sep( p ) — минимальное расстояние между двумя корнями p .

Для полиномов с целыми коэффициентами минимальное расстояние sep( p ) может быть ограничено снизу через степень полинома и максимальное абсолютное значение его коэффициентов; см. Свойства корней полинома § Разделение корней . Это позволяет анализировать сложность алгоритмов в худшем случае, основанных на теоремах Винсента. Однако теорема Обрешкова–Островского показывает, что число итераций этих алгоритмов зависит от расстояний между корнями в окрестности рабочего интервала; поэтому число итераций может существенно различаться для разных корней одного и того же полинома.

Джеймс В. Успенский дал оценку длины цепной дроби (целое число k в теореме Винсента) для получения нулевых или однознаковых вариаций: ^{[1] [7]}

Теорема  (Успенский)  —  Пусть p ( x ) — многочлен степени n , а sep( p ) — минимальное расстояние между двумя корнями p . Пусть

${\displaystyle \varepsilon =\left(n+{\frac {1}{n}}\right)^{\frac {1}{n-1}}-1.}$

Тогда целое число k , существование которого утверждается в теореме Винсента, не больше наименьшего целого числа h такого, что

${\displaystyle F_{h-1}\operatorname {sep} (p)>2\quad {\text{and}}\quad F_{h-1}F_{k}\operatorname {sep} (p)>{\frac {1}{\varepsilon }},}$

где - h- е число Фибоначчи . ${\displaystyle F_{h}}$

Метод непрерывной дроби

Использование непрерывных дробей для изоляции действительных корней было введено Винсентом, хотя он приписал эту идею Жозефу-Луи Лагранжу , не указав при этом ссылку. ^[4] Для создания алгоритма теоремы Винсента необходимо предоставить критерий выбора , которые встречаются в его теореме. Сам Винсент предоставил некоторый выбор (см. ниже). Возможны и некоторые другие варианты, и эффективность алгоритма может существенно зависеть от этих выборов. Ниже представлен алгоритм, в котором эти выборы являются результатом вспомогательной функции, которая будет обсуждаться позже. ${\displaystyle a_{i}}$

Для запуска этого алгоритма необходимо работать со списком интервалов, представленных определенной структурой данных. Алгоритм работает, выбирая интервал, удаляя его из списка, добавляя ноль, один или два меньших интервала в список и, возможно, выводит интервал изоляции.

Для выделения действительных корней многочлена p ( x ) степени n каждый интервал представляется парой , где A ( x ) — многочлен степени n , а — преобразование Мёбиуса с целыми коэффициентами. Имеем ${\displaystyle (A(x),M(x)),}$ ${\displaystyle M(x)={\frac {px+r}{qx+s}}}$

${\displaystyle A(x)=p(M(x)),}$

и интервал, представленный этой структурой данных, является интервалом, имеющим и в качестве конечных точек. Преобразование Мёбиуса отображает корни p в этом интервале в корни A в (0, +∞) . ${\displaystyle M(\infty )={\frac {p}{q}}}$ ${\displaystyle M(0)={\frac {r}{s}}}$

Алгоритм работает со списком интервалов, который в начале содержит два интервала и соответствующие разбиению действительных чисел на положительные и отрицательные (можно предположить, что ноль не является корнем, поскольку, если бы это было так, достаточно применить алгоритм к p ( x )/ x ). Затем для каждого интервала ( A ( x ), M ( x )) в списке алгоритм удаляет его из списка; если число вариаций знака коэффициентов A равно нулю, в интервале нет корня, и осуществляется переход к следующему интервалу. Если число вариаций знака равно единице, интервал, определяемый и , является изолирующим интервалом. В противном случае выбирается положительное действительное число b для деления интервала (0, +∞) на (0, b) и (b, +∞) , и для каждого подинтервала составляется M с преобразованием Мёбиуса, которое отображает интервал на (0, +∞) , для получения двух новых интервалов для добавления в список. В псевдокоде это дает следующее, где var( A ) обозначает число вариаций знака коэффициентов многочлена A . ${\displaystyle (A(x)=p(x),M(x)=x)}$ ${\displaystyle (A(x)=p(-x),M(x)=-x),}$ ${\displaystyle M(0)}$ ${\displaystyle M(\infty )}$

Функция непрерывной дроби имеет  входные данные : P(x), многочлен, свободный от квадратов , выходные данные : список пар рациональных чисел, определяющих изолирующие интервалы. /* Инициализация */ L := [(P(x), x), (P(–x), –x)] /* два начальных интервала */ Изол := [ ] /* Вычисление */ while L ≠ [ ] do  Выбрать (A(x), M(x)) в L и удалить его из L v := var( A ) if v = 0 then exit /* нет корня в интервале */ if v = 1 then /* найден изолирующий интервал */ add (M(0), M(∞)) to Isol exit b := некоторое положительное целое число В(х) = А(х + Ь) w := v – var(B) если B(0) = 0, то /* найден рациональный корень */ добавить (M(b), M(b)) к Isol В(х) := В(х)/х добавить (B(x), M(b + x)) к L /* корни в (M(b), M(+∞)) */ если w = 0 , то выход /* теорема Будана */ если w = 1, то /* теорема Будана снова */ добавить (M(0), M(b)) к Isol если w > 1, то  добавить ( A(b/(1 + x)), M(b/(1 + x)) ) к L /* корни в (M(0), M(b)) */

Различные варианты алгоритма существенно зависят от выбора b . В работах Винсента и в книге Успенского всегда b = 1 , с той разницей, что Успенский не использовал теорему Будана для избежания дальнейших делений пополам интервала, связанного с (0, b)

Недостатком выбора b = 1 всегда является необходимость делать много последовательных замен переменных вида x → 1 + x . Их можно заменить одной заменой переменной x → n + x , но, тем не менее, необходимо делать промежуточные замены переменных для применения теоремы Будана.

Способом повышения эффективности алгоритма является взятие в качестве b нижней границы положительных действительных корней, вычисленной из коэффициентов полинома (см. Свойства полиномиальных корней для получения таких границ). ^{[8] [1]}

Метод деления пополам

Метод бисекции грубо говоря состоит из начала с интервала, содержащего все действительные корни многочлена, и рекурсивного деления его на две части до тех пор, пока в конечном итоге не будут получены интервалы, содержащие либо ноль, либо один корень. Начальный интервал может иметь вид (- B , B ) , где B — верхняя граница абсолютных значений корней, например, приведенная в Свойствах корней многочлена § Границы (комплексных) корней многочлена . По техническим причинам (более простые изменения переменной, более простой анализ сложности , возможность использования двоичного анализа компьютеров) алгоритмы обычно представляются как начинающиеся с интервала [0, 1] . Нет потери общности, так как изменения переменных x = By и x = – By перемещают соответственно положительные и отрицательные корни в интервале [0, 1] . ( Также может использоваться одиночная переменная изменения x = (2 By – B ) .)

Метод требует алгоритма для проверки того, имеет ли интервал ноль, один или, возможно, несколько корней, и для гарантии завершения, этот алгоритм проверки должен исключить возможность получения бесконечно много раз вывода «возможность нескольких корней». Теорема Штурма и вспомогательная теорема Винсента предоставляют такие удобные тесты. Поскольку использование правила знаков Декарта и вспомогательной теоремы Винсента гораздо более эффективно с вычислительной точки зрения, чем использование теоремы Штурма, в этом разделе описывается только первое.

Метод деления пополам, основанный на правилах знаков Декарта и вспомогательной теореме Винсента, был предложен в 1976 году Акритасом и Коллинзом под названием « Модифицированный алгоритм Успенского » ^[3] и назывался алгоритмом Успенского , алгоритмом Винсента–Акритаса–Коллинза или методом Декарта , хотя Декарт, Винсент и Успенский никогда его не описывали.

Метод работает следующим образом. Для поиска корней в некотором интервале сначала меняют переменную для отображения интервала на [0, 1], получая новый многочлен q ( x ) . Для поиска корней q в [0, 1] , отображают интервал [0, 1] на [0, +∞]) заменой переменной, получая многочлен r ( x ) . Правило знаков Декарта, примененное к многочлену r , дает указания на количество действительных корней q в интервале [0, 1] , и, таким образом, на количество корней исходного многочлена в интервале, который был отображен на [0, 1] . Если нет изменения знака в последовательности коэффициентов r , то нет действительного корня в рассматриваемых интервалах. Если есть одно изменение знака, то есть интервал изоляции. В противном случае интервал [0, 1] разбивается на [0, 1/2] и [1/2, 1] , которые отображаются на [0, 1] с помощью замен переменных x = y /2 и x = ( y + 1)/2 . Вспомогательная теорема Винсента обеспечивает завершение этой процедуры. ${\displaystyle x\to {\frac {1}{x+1}},}$

За исключением инициализации, все эти изменения переменной состоят из композиции максимум двух очень простых изменений переменной, которые являются масштабированием на два x → x /2 , переносом x → x + 1 и инверсией x → 1/ x , последняя состоит просто из изменения порядка коэффициентов полинома. Поскольку большая часть времени вычислений посвящена изменениям переменной, метод, состоящий в отображении каждого интервала на [0, 1], является основополагающим для обеспечения хорошей эффективности.

Псевдокод

В приведенном ниже псевдокоде используются следующие обозначения.

• p ( x ) — многочлен, для которого действительные корни в интервале [0, 1] должны быть изолированы
• var( q ( x )) обозначает число изменений знака в последовательности коэффициентов полинома q
• Элементы рабочего списка имеют вид ( c , k , q ( x )) , где
  • c и k — два неотрицательных целых числа, такие, что c < 2 ^k , которые представляют интервал ${\displaystyle \left[{\frac {c}{2^{k}}},{\frac {c+1}{2^{k}}}\right],}$
  • ${\displaystyle q(x)=2^{kn}p\left({\frac {x+c}{2^{k}}}\right),}$где n — степень p (многочлен q может быть вычислен непосредственно из p , c и k , но его менее затратно вычислять пошагово, как это будет сделано в алгоритме; если p имеет целые коэффициенты, то же самое верно и для q )

Входными данными функции деления пополам являются : p ( x ) , бесквадратный многочлен , такой, что p (0) p (1) ≠ 0 ,для которого ищутся корни в интервале [0, 1] вывод : список троек ( c , k , h ) , представляющие изолирующие интервалы формы /* Инициализация */ ${\displaystyle \left[{\frac {c}{2^{k}}},{\frac {c+h}{2^{k}}}\right]}$ L := [(0, 0, p ( x ))] /* один элемент в рабочем списке L */ Изол := [ ] n := степень( p ) /* Вычисление */ while L ≠ [ ] do  Выбрать (c, k, q ( x ))  в L и удалить его из L if  q (0) = 0  then  q ( x ) := q ( x )/ x n := n – 1 /* Найден рациональный корень */ добавить (c, k, 0) к Isol v := if v = 1 then /* Найден изолирующий интервал */ add (c, k, 1) to Isol if v > 1 then /* Деление пополам */ add (2c, k + 1, to L add (2c + 1, k + 1, to L end ${\displaystyle \operatorname {var} ((x+1)^{n}q(1/(x+1)))}$  ${\displaystyle 2^{n}q(x/2)}$  ${\displaystyle 2^{n}q((x+1)/2)}$ 

Эта процедура по сути та, что была описана Коллинзом и Акритасом. ^[3] Время выполнения зависит в основном от количества интервалов, которые необходимо рассмотреть, и от изменений переменных. Существуют способы повышения эффективности, которые были активным предметом исследований с момента публикации алгоритма, и в основном с начала 21-го века.

Недавние улучшения

Были предложены различные способы улучшения алгоритма деления пополам Акритаса–Коллинза. Они включают метод, позволяющий избежать хранения длинного списка полиномов без потери простоты замены переменных, ^[9] использование приближенной арифметики ( плавающей точки и интервальной арифметики ), когда это позволяет получить правильное значение для числа вариаций знака, ^[9] использование метода Ньютона , когда это возможно, ^[9] использование быстрой полиномиальной арифметики, ^[10] сокращения для длинных цепочек делений пополам в случае кластеров близких корней, ^[10] деления пополам неравными частями для ограничения проблем неустойчивости при оценке полиномов. ^[10]

Все эти улучшения приводят к алгоритму выделения всех действительных корней многочлена с целыми коэффициентами, который имеет сложность (используя мягкую нотацию O , Õ , для исключения логарифмических множителей)

${\displaystyle {\tilde {O}}(n^{2}(k+t)),}$

где n — степень полинома, k — число ненулевых членов, t — максимальное число цифр коэффициентов. ^[10]

Реализация этого алгоритма представляется более эффективной, чем любой другой реализованный метод вычисления действительных корней многочлена, даже в случае многочленов, имеющих очень близкие корни (случай, который ранее был самым сложным для метода бисекции). ^[2]

Ссылки

1. Цигаридас и Эмирис 2006
2. Кобель, Рулье и Сагралов, 2016 г.
3. Коллинз и Акритас 1976
4. Винсент 1834
5. Обрешков 1963
6. Островский 1950
7. Успенский 1948
8. Акритас и Стржебонский 2005
9. Рулье и Циммерман, 2004 г.
10. Сагралофф и Мельхорн 2016

Источники

• Алесина, Альберто; Массимо Галуцци (1998). «Новое доказательство теоремы Винсента». L'Enseignement Mathématique . 44 (3–4): 219–256. Архивировано из оригинала 2014-07-14 . Получено 2018-12-16 .
• Акритас, Алкивиадис Г. (1986). «Метода Успенского» не существует. Труды пятого симпозиума ACM по символическим и алгебраическим вычислениям (SYMSAC '86). Ватерлоо, Онтарио, Канада. С. 88–90.
• Акритас, Алкивиадис Г.; Стржебонский, А.В.; Вигклас, П.С. (2008). "Улучшение производительности метода непрерывных дробей с использованием новых границ положительных корней" (PDF) . Нелинейный анализ: моделирование и управление . 13 (3): 265–279. doi : 10.15388/NA.2008.13.3.14557 .
• Акритас, Алкивиадис Г.; Стржебонский, Адам В. (2005). "Сравнительное исследование двух методов изоляции реальных корней" (PDF) . Нелинейный анализ: моделирование и управление . 10 (4): 297–304. doi :10.15388/NA.2005.10.4.15110.
• Коллинз, Джордж Э .; Акритас, Алкивиадис Г. (1976). Изоляция полиномиальных действительных корней с использованием правила знаков Декарта . SYMSAC '76, Труды третьего симпозиума ACM по символическим и алгебраическим вычислениям. Yorktown Heights, NY, USA: ACM. стр. 272–275. doi : 10.1145/800205.806346 .
• Кобель, Александр; Руйе, Фабрис; Сагралофф, Майкл (2016). «Вычисление действительных корней действительных многочленов... и теперь для действительных!». ISSAC '16, Труды ACM на Международном симпозиуме по символическим и алгебраическим вычислениям . Ватерлоо, Канада. arXiv : 1605.00410 . doi :10.1145/2930889.2930937.
• Обрешков, Никола (1963). Verteilung und Berechnung der Nullstellen Reeller Polynome (на немецком языке). Берлин: VEB Deutscher Verlag der Wissenschaften . п. 81.
• Островский, AM (1950). «Заметка о теореме Винсента». Annals of Mathematics . Вторая серия. 52 (3): 702–707. doi :10.2307/1969443. JSTOR  1969443.
• Руйе, Ф.; Циммерман, П. (2004). «Эффективная изоляция действительных корней многочлена». Журнал вычислительной и прикладной математики . 162 (1): 33–50. Bibcode : 2004JCoAM.162...33R. doi : 10.1016/j.cam.2003.08.015 .
• Сагралофф, М.; Мельхорн, К. (2016). «Вычисление действительных корней действительных многочленов». Журнал символических вычислений . 73 : 46–86. arXiv : 1308.4088 . doi : 10.1016/j.jsc.2015.03.004.
• Tsigaridas, Elias P.; Emiris, Ioannis Z. (2006). "Изоляция действительных корней одномерных полиномов: пересмотр непрерывных дробей". В Azar, Yossi; Erlebach, Thomas (ред.). Алгоритмы - ESA 2006, 14-й ежегодный европейский симпозиум, Цюрих, Швейцария, 11-13 сентября 2006 г., Труды . Заметки лекций по информатике. Том 4168. Springer. стр. 817–828. arXiv : cs/0604066 . doi :10.1007/11841036_72. ISBN 978-3-540-38875-3.
• Успенский, Джеймс Виктор (1948). Теория уравнений. Нью-Йорк: McGraw–Hill Book Company.
• Винсент, Александр Жозеф Идульф (1834). «Мемуар о разрешении числовых уравнений». Mémoires de la Société Royale des Sciences, de L' Agriculture et des Arts, de Lille (на французском языке): 1–34.
• Винсент, Александр Жозеф Идульф (1836). «Примечание к решению числовых уравнений» (PDF) . Journal de Mathématiques Pures et Appliquées . 1 : 341–372.
• Винсент, Александр Жозеф Идульф (1838). «Дополнение к предыдущему примечанию относительно разрешения числовых уравнений» (PDF) . Journal de Mathématiques Pures et Appliquées . 3 : 235–243. Архивировано из оригинала (PDF) 29 октября 2013 г. Проверено 16 декабря 2018 г.