Изоляция реального корня - Real-root isolation

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

{ 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$ положительный корень ${ displaystyle p_ {0}.}$ В противном случае это количество вариаций знака (0 или 1) равно количеству действительных корней ${ displaystyle p_ {0}}$ в интервале, определяемом ${ displaystyle c_ {k-1}}$ и ${ displaystyle c_ {k}.}$

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

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

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

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

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

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

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

п

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

q

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

Теорема (Обрещкофф – Островский) — Заключение вспомогательного результата Винсента справедливо, если многочлен $п (Икс)$ имеет не более одного корня $α + 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}}}},}

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

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

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

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

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

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

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

куда ${ displaystyle F_ {h}}$ это $час$ th Число Фибоначчи.

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

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

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

Для выделения действительных корней многочлена $п (Икс)$ степени $п$ , каждый интервал представлен парой ${ Displaystyle (А (х), М (х)),}$ куда $А (Икс)$ является многочленом степени $п$ и ${ Displaystyle М (х) = { гидроразрыва {px + r} {qx + s}}}$ это Преобразование Мёбиуса с целыми коэффициентами. Надо

{ Displaystyle А (х) = п (М (х)),}

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

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

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

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

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

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

Метод бисекции

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

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

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

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

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

Псевдокод

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

$п (Икс)$ - многочлен, действительные корни которого из интервала $[0, 1]$ должны быть изолированы
$var (q (Икс))$ обозначает количество вариации знаков в последовательности коэффициентов многочлена $q$
Элементы рабочего списка имеют вид (c, k, q(Икс)), куда
- $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),}$ куда $п$ степень $п$ (полином $q$ может быть вычислен непосредственно из $п$ , $c$ и $k$ , но его инкрементное вычисление обходится дешевле, поскольку это будет сделано в алгоритме; если $п$ имеет целые коэффициенты, то же верно и для $q$ )

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

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

Последние улучшения

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

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

{ Displaystyle { тильда {O}} (п ^ {2} (к + т)),}

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

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

Источники

Алезина, Альберто; Массимо Галуцци (1998). «Новое доказательство теоремы Винсента». L'Enseignement Mathématique. 44 (3–4): 219–256. Архивировано из оригинал на 2014-07-14. Получено 2018-12-16.
Акритас, Алкивиадис Г. (1986). Нет "метода Успенского". Труды пятого симпозиума ACM по символическим и алгебраическим вычислениям (SYMSAC '86). Ватерлоо, Онтарио, Канада. С. 88–90.
Akritas, Alkiviadis G .; Strzeboński, A. W .; Вигклас, П. С. (2008). «Повышение эффективности метода непрерывных дробей с использованием новых оценок положительных корней» (PDF). Нелинейный анализ: моделирование и управление. 13 (3): 265–279. Дои:10.15388 / NA.2008.13.3.14557.
Akritas, Alkiviadis G .; Стшебоньский, Адам В. (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, Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computing. Ватерлоо, Канада. arXiv:1605.00410. Дои:10.1145/2930889.2930937.
Обрещков, Никола (1963). Verteilung und Berechnung der Nullstellen reeller Polynome (на немецком). Берлин: VEB Deutscher Verlag der Wissenschaften. п. 81.
Островский, А.М. (1950). «Замечание о теореме Винсента». Анналы математики. Вторая серия. 52 (3): 702–707. Дои:10.2307/1969443. JSTOR 1969443.
Rouillier, F .; Циммерман, П. (2004). «Эффективная изоляция действительных корней многочлена». Журнал вычислительной и прикладной математики. 162: 33–50. Дои:10.1016 / j.cam.2003.08.015.
Сагралов, М .; Мельхорн, К. (2016). «Вычисление действительных корней действительных многочленов». Журнал символических вычислений. 73: 46–86. arXiv:1308.4088. Дои:10.1016 / j.jsc.2015.03.004.
Цигаридас, П. Э .; Эмирис, И. З. (2006). «Изоляция одномерного полинома действительного корня: еще раз о непрерывных дробях». LNCS. Конспект лекций по информатике. 4168: 817–828. arXiv:cs / 0604066. Bibcode:2006cs ........ 4066T. Дои: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). "Note sur la résolution des équations numériques" (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) в 2013-10-29. Получено 2018-12-16.

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

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

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

[Vincent-memoire-4] а ^б ^c Винсент 1834

[Obr_1920-5] Обрещков 1963

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

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

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

[RZ-9] а ^б ^c Руйе и Циммерман 2004

[SM-10] а ^б ^c ^d Сагралов и Мельхорн 2016

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]