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

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

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

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

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

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

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

Полином Уилкинсона показывает, что очень небольшая модификация одного коэффициента многочлена может кардинально изменить не только значение корней, но и их природу (действительную или комплексную). Кроме того, даже при хорошей аппроксимации, когда вычисляется полином с приближенным корнем, можно получить результат, который далеко близок к нулю. Например, если многочлен степени 20 (степень многочлена Уилкинсона) имеет корень, близкий к 10, производная многочлена в корне может быть порядка $10^{20};$ это означает, что ошибка $10^{-10}$ от значения корня может дать значение многочлена в приближенном корне, которое имеет порядок $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] предоставляет метод изоляции реального корня, который лежит в основе наиболее эффективных алгоритмов изоляции реального корня. Речь идет о положительных действительных корнях многочлена без квадратов (то есть многочлена без кратных корней). Если $a_{1},a_{2},\ldots ,$ – последовательность положительных действительных чисел, пусть

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

я подходящая $— k$ - дробь цепной дроби

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

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

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

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

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

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

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

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]

Теорема (Обрешкоффа – Островского) . Вывод вспомогательного результата Винсента верен, если многочлен $p (x)$ имеет не более одного корня $α + 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]

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

\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 }},

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

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

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

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

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

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

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

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

function continued fraction is
    input: P(x), a square-free polynomial,
    output: a list of pairs of rational numbers defining isolating intervals
    /* Initialization */
        L := [(P(x), x), (P(–x), –x)]                /* two starting intervals */
        Isol := [ ]
    /* Computation */
    while L  $\neq$  [ ] do
        Choose (A(x), M(x)) in L, and remove it from L
        v := var(A)
        if v = 0 then exit                /* no root in the interval */
        if v = 1 then                     /* isolating interval found */
            add (M(0), M(∞)) to Isol
            exit
        b := some positive integer
        B(x) = A(x + b)
        w := v – var(B)
        if B(0) = 0 then                         /* rational root found */
            add (M(b), M(b)) to Isol
            B(x) := B(x)/x
        add (B(x),  M(b + x)) to L           /* roots in (M(b), M(+∞)) */
        if w = 0 then exit                  /* Budan's theorem */ 
        if w = 1 then                       /* Budan's theorem again */ 
            add (M(0), M(b)) to Isol
        if w > 1 then
            add ( A(b/(1 + x)),  M(b/(1 + x)) )to L      /* roots in (M(0), M(b)) */

Различные варианты алгоритма существенно зависят от выбора $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 году Акритасом и Коллинзом под названием « Модифицированный алгоритм Успенского» . ^[3] и назывался алгоритмом Успенского , алгоритмом Винсента-Акритаса-Коллинза или методом Декарта , хотя Декарт, Винсент и Успенский никогда его не описывали.

Способ работает следующим образом. Для поиска корней в некотором интервале сначала меняют переменную для отображения интервала на $[0, 1],$ давая новый полином $q (x)$ . Для поиска корней $q$ в $[0, 1]$ интервал $[0, 1]$ отображается на $[0, +\infty])$ путем замены переменной $x\to {\frac {1}{x+1}},$ давая многочлен $r (x)$ . Правило знаков Декарта, примененное к многочлену $r,$ дает указания о количестве действительных корней $q$ в интервале $[0, 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 к$ , которые представляют собой интервал $\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$ )

function bisection is
    input:  $p (x)$ , a square-free polynomial, such that  $p (0) p (1) \neq 0$ , 
                      for which the roots in the interval  $[0, 1]$  are searched
    output: a list of triples  $(c, k, h)$ , 
                      representing isolating intervals of the form  $\left[{\frac {c}{2^{k}}},{\frac {c+h}{2^{k}}}\right]$ 
    /* Initialization */
    L := [(0, 0, p(x))] /* a single element in the working list L */
    Isol := [ ]
    n := degree(p)
    /* Computation */
    while L  $\neq$  [ ] do
        Choose (c, k,  $q (x))$  in L, and remove it from L
        if  $q (0) = 0$  then
             $q (x) := q (x)/ x$ 
            n := n – 1                /* A rational root found */
            add (c, k, 0) to Isol
        v :=  $\operatorname {var} ((x+1)^{n}q(1/(x+1)))$ 
        if v = 1 then                /* An isolating interval found */
            add (c, k, 1) to Isol
        if v > 1 then                /* Bisecting */
            add (2c, k + 1,  $2^{n}q(x/2)$   to L
            add (2c + 1, k + 1,  $2^{n}q((x+1)/2)$   to L
    end

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

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

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

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

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

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

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

Ссылки

Источники

Алесина, Альберто; Массимо Галуцци (1998). «Новое доказательство теоремы Винсента» . L'Enseignement Mathématique . 44 (3–4): 219–256. Архивировано из оригинала 14 июля 2014 г. Проверено 16 декабря 2018 г.
Акритас, Алкивиадис Г. (1986). Никакого «Метода Успенского» не существует . Материалы пятого симпозиума ACM по символьным и алгебраическим вычислениям (SYMSAC '86). Ватерлоо, Онтарио, Канада. стр. 88–90.
Акритас, Алкивиадис Г.; Стшебонский, AW; Виглас, П.С. (2008). «Улучшение производительности метода цепных дробей с использованием новых границ положительных корней» (PDF) . Нелинейный анализ: моделирование и управление . 13 (3): 265–279. дои : 10.15388/NA.2008.13.3.14557 .
Акритас, Алкивиадис Г.; Стржебонский, Адам В. (2005). «Сравнительное исследование двух реальных методов изоляции корней» (PDF) . Нелинейный анализ: моделирование и управление . 10 (4): 297–304. дои : 10.15388/NA.2005.10.4.15110 .
Коллинз, Джордж Э .; Акритас, Алкивиадис Г. (1976). Полиномиальная изоляция действительного корня с использованием правила знаков Декарта . SYMSAC '76, Материалы третьего симпозиума ACM по символьным и алгебраическим вычислениям. Йорктаун-Хайтс, штат Нью-Йорк, США: ACM. стр. 272–275. дои : 10.1145/800205.806346 .
Кобель, Александр; Руйе, Фабрис; Сагралов, Майкл (2016). «Вычисление действительных корней действительных многочленов… и теперь по-настоящему!». ISSAC '16, Труды ACM Международного симпозиума по символьным и алгебраическим вычислениям . Ватерлоо, Канада. arXiv : 1605.00410 . дои : 10.1145/2930889.2930937 .
Обрешков, Никола (1963). Распределение и вычисление корней действительных многочленов (на немецком языке). Берлин: Немецкое научное издательство VEB . п. 81.
Островский, AM (1950). «Примечание к теореме Винсента». Анналы математики . Вторая серия. 52 (3): 702–707. дои : 10.2307/1969443 . JSTOR 1969443 .
Рулье, Ф.; Циммерман, П. (2004). «Эффективное выделение действительных корней полинома» . Журнал вычислительной и прикладной математики . 162 (1): 33–50. Бибкод : 2004JCoAM.162...33R . дои : 10.1016/j.cam.2003.08.015 .
Сагралов, М.; Мельхорн, К. (2016). «Вычисление действительных корней действительных многочленов». Журнал символических вычислений . 73 : 46–86. arXiv : 1308.4088 . дои : 10.1016/j.jsc.2015.03.004 .
Цигаридас, Элиас П.; Эмирис, Иоаннис З. (2006). «Изоляция действительного корня одномерного полинома: новый взгляд на непрерывные дроби». В Азаре, Йоси; Эрлебах, Томас (ред.). Алгоритмы – ESA 2006, 14-й ежегодный европейский симпозиум, Цюрих, Швейцария, 11–13 сентября 2006 г., Труды . Конспекты лекций по информатике. Том. 4168. Спрингер. стр. 817–828. arXiv : cs/0604066 . дои : 10.1007/11841036_72 .
Успенский, Джеймс Виктор (1948). Теория уравнений . Нью-Йорк: Книжная компания McGraw – Hill.
Винсент, Александр Жозеф Идульф (1834). «Память при решении числовых уравнений» . Мемуары Королевского общества наук, сельского хозяйства и искусств Лилля (на французском языке): 1–34.
Винсент, Александр Жозеф Идульф (1836). «Примечание по решению числовых уравнений» (PDF) . Журнал чистой и прикладной математики . 1 :341–372.
Винсент, Александр Жозеф Идульф (1838). «Дополнение к предыдущему примечанию, касающемуся разрешения числовых уравнений» (PDF) . Журнал чистой и прикладной математики . 3 : 235–243. Архивировано из оригинала (PDF) 29 октября 2013 г. Проверено 16 декабря 2018 г.

[TE-1] Перейти обратно: Перейти обратно: ^а ^б ^с Цигаридас и Эмирис 2006

[KRS-2] Перейти обратно: Перейти обратно: ^а ^б Kobel, Rouillier & Sagraloff 2016

[CA-3] Перейти обратно: Перейти обратно: ^а ^б ^с Коллинз и Акритас, 1976 г.

[Vincent-memoire-4] Перейти обратно: Перейти обратно: ^а ^б ^с Винсент 1834 г.

[Obr_1920-5] Обрешков 1963 г.

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

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

[8] Акритас и Стржебоньский 2005 г.

[RZ-9] Перейти обратно: Перейти обратно: ^а ^б ^с Рулье и Циммерман, 2004 г.

[SM-10] Перейти обратно: Перейти обратно: ^а ^б ^с ^д Сагралофф и Мельхорн, 2016 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]