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

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

Изоляция действительного корня полезна, потому что обычные алгоритмы поиска корня для вычисления действительных корней многочлена могут давать некоторые действительные корни, но, как правило, не могут подтвердить обнаружение всех действительных корней. В частности, если такой алгоритм не находит никакого корня, неизвестно, так ли это, потому что настоящего корня нет. Некоторые алгоритмы вычисляют все комплексные корни, но, поскольку реальных корней, как правило, намного меньше, чем комплексных корней, большая часть времени их вычислений обычно тратится на вычисление нереальных корней (в среднем многочлен степени $n$ имеет $n$ комплексных корней, и $регистрируют$ только $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$ .

Budan's может предоставить алгоритм изоляции действительного корня для полинома без квадратов (полином без кратного корня): из коэффициентов полинома можно вычислить верхнюю границу $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}}}}}}}}}}

быть $к$ - й сходится в непрерывную дробь

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

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

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

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

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

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

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

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

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

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

«Достаточно маленький» условие было количественно независимо от Никола Обрешкав , ^[5] и А. Островским : ^[6]

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

p

, справа области, исключенные для корней преобразованного многочлена

q

; синим цветом обозначены области, которые исключены из-за наличия вариации одного знака, но допускаются без вариации знака.

Теорема (Obreschkoff-Ostrowski) - Вывод вспомогательного результата Винсент имеет место , если многочлен $р (х)$ имеет не более одного корня $α + iβ$ такое , что

\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|.

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

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

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

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

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

Теорема (Успенский) - Пусть $р (х)$ многочлен степени $п$ , а $сентябрь (р)$ минимальное расстояние между двумя корнями $р$ . Позволять

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

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

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

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

Метод непрерывной дроби [ править ]

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

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

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

A(x)=p(M(x)),

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

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

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

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

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

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

Метод деления пополам [ править ]

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

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

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

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

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

Псевдокод [ править ]

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

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

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

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

Последние улучшения [ править ]

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

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

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

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

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

Ссылки [ править ]

^ a b c Цигаридас и Эмирис 2006
^ а б Кобель, Руйе и Сагралофф 2016
^ a b c Коллинз и Акритас 1976
^ a b c Винсент 1834
^ Obreschkoff 1963
^ Островский 1950
^ Успенский 1948
^ Akritas & Strzeboński 2005
^ a b c Rouillier & Zimmerman 2004
^ a b c d Sagraloff & Mehlhorn 2016 г.

Источники [ править ]

Алезина, Альберто; Массимо Галуцци (1998). «Новое доказательство теоремы Винсента» . L'Enseignement Mathématique . 44 (3–4): 219–256. Архивировано из оригинала на 2014-07-14 . Проверено 16 декабря 2018 .
Акритас, Алькивиадис Г. (1986). Нет «метода Успенского» . Труды пятого симпозиума ACM по символьным и алгебраическим вычислениям (SYMSAC '86). Ватерлоо, Онтарио, Канада. С. 88–90.
Akritas, Alkiviadis G .; Strzeboński, AW; Вигклас, ПС (2008). «Повышение эффективности метода непрерывных дробей с использованием новых оценок положительных корней» (PDF) . Нелинейный анализ: моделирование и управление . 13 (3): 265–279. DOI : 10,15388 / NA.2008.13.3.14557 .
Akritas, Alkiviadis G .; Стшебоньский, Адам В. (2005). «Сравнительное исследование двух реальных методов изоляции корней» (PDF) . Нелинейный анализ: моделирование и управление . 10 (4): 297–304. DOI : 10,15388 / NA.2005.10.4.15110 .
Коллинз, Джордж Э .; Акритас, Алькивиадис Г. (1976). Выделение полиномиального действительного корня с помощью правила знаков Декарта . SYMSAC '76, Труды третьего симпозиума ACM по символьным и алгебраическим вычислениям. Йорктаун-Хайтс, Нью-Йорк, США: 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). «Примечание к теореме Винсента». Анналы математики . Вторая серия. 52 (3): 702–707. DOI : 10.2307 / 1969443 . JSTOR 1969 443 .
Rouillier, F .; Циммерман, П. (2004). «Эффективная изоляция действительных корней многочлена» . Журнал вычислительной и прикладной математики . 162 : 33–50. DOI : 10.1016 / j.cam.2003.08.015 .
Сагралов, М .; Мельхорн, К. (2016). «Вычисление действительных корней действительных многочленов». Журнал символических вычислений . 73 : 46–86. arXiv : 1308,4088 . DOI : 10.1016 / j.jsc.2015.03.004 .
Цигаридас, ЧП; Эмирис, ИЗ (2006). «Изоляция одномерного полинома действительного корня: еще раз о непрерывных дробях». LNCS . Конспект лекций по информатике. 4168 : 817–828. arXiv : cs / 0604066 . Bibcode : 2006cs ........ 4066T . DOI : 10.1007 / 11841036_72 . ISBN 978-3-540-38875-3.
Успенский, Джеймс Виктор (1948). Теория уравнений . Нью-Йорк: Книжная компания Макгроу-Хилла.
Винсент, Александр Жозеф Хидулф (1834). "Mémoire sur la résolution des équations numériques" . Mémoires de la Société Royale des Sciences, de L 'Agriculture et des Arts, де Лилль (на французском языке): 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 .

[TE-1] Цигаридас и Эмирис 2006

[KRS-2] а б Кобель, Руйе и Сагралофф 2016

[CA-3] Коллинз и Акритас 1976

[Vincent-memoire-4] Винсент 1834

[Obr_1920-5] Obreschkoff 1963

[O_1950-6] Островский 1950

[Uspensky-7] Успенский 1948

[8] Akritas & Strzeboński 2005

[RZ-9] Rouillier & Zimmerman 2004

[SM-10] Sagraloff & Mehlhorn 2016 г.

[1]