Система полиномиальных уравнений

Система полиномиальных уравнений (иногда просто полиномиальная система ) — это совокупность одновременных уравнений $f 1 = 0, ..., f h = 0$ , где $f i$ являются полиномами от нескольких переменных, скажем $x 1, ..., x n$ над некоторым полем $k$ .

Решением k полиномиальной системы является набор значений $x i$ s, которые принадлежат некоторому алгебраически замкнутому расширению поля $K$ поля $и$ делают все уравнения истинными. Когда $k$ поле рациональных чисел , $K$ обычно считается полем комплексных чисел , поскольку каждое решение принадлежит расширению поля k $—$ , которое изоморфно подполю комплексных чисел.

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

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

Определение

Многочисленные особые точки секстика Барта являются решениями полиномиальной системы

Простой пример системы полиномиальных уравнений:

{\begin{aligned}x^{2}+y^{2}-5&=0\\xy-2&=0.\end{aligned}}

Его решениями являются четыре пары $(x, y) = (1, 2), (2, 1), (-1, -2), (-2, -1)$ . Эти решения легко проверить заменой, но для доказательства отсутствия других решений требуется дополнительная работа.

Предметом данной статьи является исследование обобщений таких примеров и описание методов, используемых для вычисления решений.

Система полиномиальных уравнений, или полиномиальная система – это совокупность уравнений

{\begin{aligned}f_{1}\left(x_{1},\ldots ,x_{m}\right)&=0\\&\;\;\vdots \\f_{n}\left(x_{1},\ldots ,x_{m}\right)&=0,\end{aligned}}

где каждый $f h$ представляет собой многочлен от неопределенных $x 1, ..., x m$ с целыми коэффициентами или коэффициентами в некотором фиксированном поле , часто поле рациональных чисел или конечном поле . ^[1] Другие поля коэффициентов, например действительные числа , используются реже, так как их элементы невозможно представить в компьютере (в вычислениях можно использовать только приближения действительных чисел, и эти приближения всегда являются рациональными числами).

Решением , который полиномиальной системы является кортеж значений $(x 1, ..., x m)$ удовлетворяет всем уравнениям полиномиальной системы. Решения ищутся в комплексных числах или, в более общем смысле, в алгебраически замкнутом поле, содержащем коэффициенты. В частности, в нулевой характеристике все комплексные ищутся решения. Поиск реального или рационального решения – это гораздо более сложная задача, не рассматриваемая в данной статье.

Множество решений не всегда конечно; например, решения системы

{\begin{aligned}x(x-1)&=0\\x(y-1)&=0\end{aligned}}

являются точкой $(x, y) = (1,1)$ и линией $x = 0$ . ^[2] Даже если множество решений конечно, вообще говоря, не существует выражения решений в замкнутой форме (в случае одного уравнения это теорема Абеля–Руффини ).

Поверхность Барта , изображенная на рисунке, является геометрическим представлением решений полиномиальной системы, сведенной к одному уравнению 6-й степени с 3-мя переменными. некоторые из его многочисленных особых точек На изображении видны . Они являются решениями системы четырех уравнений пятой степени с тремя переменными. Такая переопределенная система вообще не имеет решения (т. е. если коэффициенты не являются конкретными). Если она имеет конечное число решений, то это число не превосходит $5. 3 = 125$ по теореме Безу . Однако было показано, что для случая особых точек поверхности степени 6 максимальное число решений равно 65 и достигается поверхностью Барта.

Основные свойства и определения

Система считается переопределенной , если количество уравнений превышает количество переменных. Система несовместна , если она не имеет комплексного решения (или, если коэффициенты не являются комплексными числами, нет решения в алгебраически замкнутом поле, содержащем эти коэффициенты). Согласно Nullstellensatz Гильберта это означает, что 1 представляет собой линейную комбинацию (с полиномами в качестве коэффициентов) первых членов уравнений. Большинство, но не все, переопределенные системы, построенные со случайными коэффициентами, несовместимы. Например, система $x 3 - 1 = 0, х 2 - 1 = 0$ переопределено (имеет два уравнения, но только одно неизвестное), но оно не противоречиво, поскольку имеет решение $x = 1$ .

Система называется недоопределенной , если количество уравнений меньше числа переменных. Недоопределенная система либо несовместна, либо имеет бесконечное число комплексных решений (или решений в алгебраически замкнутом поле , содержащем коэффициенты уравнений). Это нетривиальный результат коммутативной алгебры , который включает, в частности, теорему Гильберта о Nullstellensatz и теорему Крулла о главном идеале .

Система называется нульмерной, если она имеет конечное число комплексных решений (или решений в алгебраически замкнутом поле). Эта терминология исходит из того факта, что алгебраическое многообразие решений имеет нулевую размерность . Система с бесконечным числом решений называется положительномерной .

Нульмерную систему с таким же количеством уравнений, как и переменных, иногда называют « хорошей» . ^[3]Теорема Безу утверждает, что корректная система, уравнения которой имеют степени $d 1, ..., d n,$ имеет не более $d 1 \cdot\cdot\cdot d n$ решений. Эта граница является резкой. Если все степени равны $d$ , эта граница становится $d н$ и экспоненциально зависит от числа переменных. ( Основная теорема алгебры — это частный случай $n = 1.$ )

Такое экспоненциальное поведение затрудняет решение полиномиальных систем и объясняет, почему мало решателей, которые способны автоматически решать системы с границей Безу выше, скажем, 25 (три уравнения степени 3 или пять уравнений степени 2 выходят за эту границу). ^{[ нужна ссылка ]}

Что решает?

Первое, что нужно сделать для решения полиномиальной системы, — это решить, является ли она несовместной, нульмерной или положительной размерностью. Это можно сделать путем вычисления базиса Грёбнера левых частей уравнений. Система несовместна , если этот базис Грёбнера приведен к 1. Система является нульмерной , если для каждой переменной существует старший моном некоторого элемента базиса Грёбнера, который является чистой степенью этой переменной. Для этого теста лучшим мономиальным порядком (то есть тем, который обычно приводит к самым быстрым вычислениям) обычно является градуированный обратный лексикографический порядок (grevlex).

Если система положительномерна , то она имеет бесконечно много решений. Поэтому перечислить их невозможно. Отсюда следует, что в этом случае решение может означать только «нахождение описания решений, из которого легко извлечь соответствующие свойства решений». Общепринятого такого описания не существует. На самом деле существует множество различных «релевантных свойств», которые включают почти все подполя алгебраической геометрии .

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

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

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

Расширения

Тригонометрические уравнения

Тригонометрическое уравнение — это уравнение $g = 0$ , где $g$ — тригонометрический полином . Такое уравнение можно преобразовать в полиномиальную систему, разложив в нем синусы и косинусы (используя формулы суммы и разности ), заменив $sin(x)$ и $cos(x)$ двумя новыми переменными $s$ и $c$ и добавив новое уравнение $s 2 + с 2 - 1 = 0$ .

Например, из-за тождества

\cos(3x)=4\cos ^{3}(x)-3\cos(x),

решение уравнения

\sin ^{3}(x)+\cos(3x)=0

эквивалентно решению полиномиальной системы

{\begin{cases}s^{3}+4c^{3}-3c&=0\\s^{2}+c^{2}-1&=0.\end{cases}}

Для каждого решения $(c 0, s 0)$ этой системы существует единственное решение $x$ уравнения такое, что $0 \leq x < 2 π$ .

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

Решения в конечном поле

При решении системы над конечным полем $k$ с $q$ элементами нас в первую очередь интересуют решения в $k$ . Поскольку элементы $k$ являются в точности решениями уравнения $x д - x = 0$ , то для ограничения решений на $k$ достаточно добавить уравнение $x i д - x i = 0$ для каждой переменной $x i$ .

Коэффициенты в числовом поле или в конечном поле непростого порядка

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

Например, если система содержит ${\sqrt {2}}$ , система над рациональными числами получается сложением уравнения $r 22 - 2 = 0$ и замена ${\sqrt {2}}$ на $r 2$ в остальных уравнениях.

В случае конечного поля одно и то же преобразование позволяет всегда предполагать, что поле $k$ имеет простой порядок.

Алгебраическое представление решений

Обычные цепи

Обычный способ представления решений — через нульмерные регулярные цепочки. Такая цепочка состоит из последовательности многочленов $f 1 (x 1)$ , $f 2 (x 1, x 2)$ , ..., $f n (x 1, ..., x n)$ таких, что для каждого $i$ такого что $1 \leq я \leq n$

$f i$ — многочлен только от $x 1, ..., x i$ , который имеет степень $d i > 0$ по $x i$ ;
коэффициент при $x i d Из$ in $f i$ — многочлен от $x 1, ..., x i -1,$ который не имеет общего нуля с $f 1$ , ..., $f i - 1$ .

Такой регулярной цепочке соответствует треугольная система уравнений

{\begin{cases}f_{1}(x_{1})=0\\f_{2}(x_{1},x_{2})=0\\\quad \vdots \\f_{n}(x_{1},x_{2},\ldots ,x_{n})=0.\end{cases}}

Решения этой системы получаются путем решения первого одномерного уравнения, подстановки решений в другие уравнения, затем решения второго уравнения, которое теперь является одномерным, и так далее. Определение регулярных цепей подразумевает, что одномерное уравнение, полученное из $f i,$ имеет степень $d i$ и, таким образом, система имеет $d 1 ... d n$ решений, при условии, что в этом процессе разрешения нет кратного корня ( фундаментальная теорема алгебры ). .

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

{\begin{cases}x^{2}-1=0\\(x-1)(y-1)=0\\y^{2}-1=0.\end{cases}}

Существует несколько алгоритмов вычисления треугольного разложения произвольной полиномиальной системы (не обязательно нульмерной). ^[4] на регулярные цепи (или регулярные полуалгебраические системы ).

Существует также алгоритм, специфичный для нульмерного случая и в данном случае конкурирующий с прямыми алгоритмами. Он заключается в вычислении сначала базиса Грёбнера для градуированного обратного лексикографического порядка (grevlex) , а затем выведении лексикографического базиса Грёбнера с помощью алгоритма FGLM. ^[5] и, наконец, применение лекстриангулярного алгоритма. ^[6]

Такое представление решений вполне удобно для коэффициентов в конечном поле. Однако для рациональных коэффициентов необходимо учитывать два аспекта:

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

Первую проблему решили Дахан и Шост: ^[7]^[8] Среди наборов регулярных цепей, представляющих заданный набор решений, существует набор, для которого коэффициенты явно ограничены с точки зрения размера входной системы с почти оптимальной оценкой. Это множество, называемое эквипроектируемым разложением , зависит только от выбора координат. Это позволяет использовать модульные методы для эффективного расчета эквипроектируемого разложения. ^[9]

Вторая проблема обычно решается путем вывода регулярных цепочек специального вида, иногда называемых леммами формы , для которых все $d i,$ кроме первого, равны $1$ . Для получения таких регулярных цепочек, возможно, придется добавить дополнительную переменную, называемую разделяющей переменной , которой присвоен индекс $0$ . Рациональное одномерное представление , описанное ниже, позволяет вычислить такую специальную регулярную цепь, удовлетворяющую границе Дахана – Шоста, начиная либо с регулярной цепи, либо с базиса Грёбнера.

Рациональное одномерное представление

Рациональное одномерное представление или RUR — это представление решений нульмерной полиномиальной системы над рациональными числами, введенное Ф. Руйе. ^[10]

РУР нульмерной системы состоит из линейной комбинации $x 0$ переменных, называемой разделяющей переменной , и системы уравнений ^[11]

{\begin{cases}h(x_{0})=0\\x_{1}=g_{1}(x_{0})/g_{0}(x_{0})\\\quad \vdots \\x_{n}=g_{n}(x_{0})/g_{0}(x_{0}),\end{cases}}

где $h$ — одномерный полином по $x 0$ степени $D$ , а $g 0, ..., g n$ — одномерные многочлены по $x 0$ степени меньше $D$ .

Учитывая нульмерную полиномиальную систему над рациональными числами, RUR обладает следующими свойствами.

Все линейные комбинации переменных, кроме конечного числа, являются разделяющими переменными.
Если выбрана разделяющая переменная, RUR существует и уникален. В частности, $h$ и $g i$ определяются независимо от какого-либо алгоритма их вычисления.
Решения системы находятся во взаимно однозначном соответствии с корнями $h$ , а кратность каждого корня $h$ равна кратности соответствующего решения.
Решения системы получаются подстановкой корней $h$ в остальные уравнения.
Если $h$ не имеет кратного корня $g0,$ является производной h $.$ то

Например, для системы из предыдущего раздела каждая линейная комбинация переменных, за исключением кратных $x$ , $y$ и $x + y$ , является разделяющей переменной. Если выбрать $t = .mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠ x – y / 2 ⁠$ как разделяющая переменная, то рубль равен

{\begin{cases}t^{3}-t=0\\x={\frac {t^{2}+2t-1}{3t^{2}-1}}\\y={\frac {t^{2}-2t-1}{3t^{2}-1}}.\\\end{cases}}

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

Для нульмерных систем RUR позволяет извлекать числовые значения решений путем решения одного одномерного многочлена и подстановки его в рациональные функции. Это позволяет производить сертифицированные аппроксимации решений с любой заданной точностью.

Более того, одномерный полином $h (x 0)$ RUR может быть факторизован, и это дает RUR для каждого неприводимого фактора. Тем самым обеспечивается простое разложение данного идеала (т. е. разложение радикала первичное идеала). На практике это обеспечивает выход с гораздо меньшими коэффициентами, особенно в случае систем с высокой кратностью.

В отличие от треугольных разложений и равнопроектируемых разложений, RUR не определен в положительной размерности.

Численное решение

Общие алгоритмы решения

Общие численные алгоритмы, разработанные для любой системы нелинейных уравнений, работают и для полиномиальных систем. Однако обычно предпочтение отдается конкретным методам, поскольку общие методы обычно не позволяют найти все решения. В частности, если общий метод не находит решения, это обычно не означает, что решения нет.

Тем не менее, здесь следует упомянуть два метода.

Метод Ньютона можно использовать, если количество уравнений равно числу переменных. Он не позволяет ни найти все решения, ни доказать отсутствие решения. Но это очень быстро, если начинать с точки, близкой к решению. Таким образом, это основной инструмент для метода продолжения гомотопии, описанного ниже.
Оптимизация редко используется для решения полиномиальных систем, но примерно в 1970 году ей удалось показать, что система из 81 квадратного уравнения с 56 переменными не является противоречивой. ^[12] С другими известными методами это остается за пределами возможностей современных технологий по состоянию на 2022 год. ^[update]. Этот метод заключается просто в минимизации суммы квадратов уравнений. Если ноль найден как локальный минимум, то он достигается при решении. Этот метод работает для переопределенных систем, но выводит пустую информацию, если все найденные локальные минимумы положительны.

Метод продолжения гомотопии

Это получисловой метод, который предполагает, что количество уравнений равно количеству переменных. Этот метод относительно старый, но за последние десятилетия он был значительно усовершенствован. ^[13]

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

На втором этапе система $g_{1}=0,\,\ldots ,\,g_{n}=0$ полиномиальных уравнений, которое имеет в точности $N$ решения, которые легко вычислить. Эта новая система имеет тот же номер $n$ переменных и столько же $n$ уравнений и той же общей структуры, что и решаемая система, $f_{1}=0,\,\ldots ,\,f_{n}=0$ .

Затем гомотопия рассматривается между двумя системами. Он состоит, например, из прямой линии между двумя системами, но можно рассматривать и другие пути, в частности, во избежание некоторых сингулярностей в системе

(1-t)g_{1}+tf_{1}=0,\,\ldots ,\,(1-t)g_{n}+tf_{n}=0

.

Продолжение гомотопии заключается в деформации параметра $t$ от 0 до 1 следуя и $N$ решения во время этой деформации. Это дает желаемые решения для $t=1$ . Следующее означает, что если $t_{1}<t_{2}$ , решения для $t=t_{2}$ выводятся из решений $t=t_{1}$ по методу Ньютона. Трудность здесь состоит в том, чтобы правильно подобрать значение $t_{2}-t_{1}:$ Слишком большая сходимость Ньютона может быть медленной и даже может перейти от одного пути решения к другому. Слишком маленькое количество шагов замедляет метод.

Численное решение из рационального одномерного представления

Вывести числовые значения решений из RUR кажется несложным: достаточно вычислить корни одномерного многочлена и подставить их в другие уравнения. Это не так просто, поскольку вычисление многочлена по корням другого многочлена крайне нестабильно.

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

Метод Аберта , реализованный в MPSolve, вычисляет все комплексные корни с любой точностью.
Алгоритм Успенского Коллинза и Акритаса, ^[14] улучшен Рулье и Циммерманном ^[15] и основано на правиле знаков Декарта . Этот алгоритм вычисляет действительные корни, изолированные в интервалах произвольной малой ширины. Он реализован в Maple (функции fsolve и RootFinding[Isolate] ).

Пакеты программного обеспечения

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

Функция Maple числами с RootFinding[Isolate] принимает на вход любую полиномиальную систему рациональных чисел (если некоторые коэффициенты являются плавающей запятой , они преобразуются в рациональные числа) и выводит действительные решения, представленные либо (необязательно) как интервалы рациональных чисел, либо как аппроксимации с плавающей запятой произвольной точности. Если система не является нульмерной, это сигнализируется как ошибка.

Внутри этот решатель, разработанный Ф. Рулье, сначала вычисляет базис Грёбнера, а затем рациональное одномерное представление, из которого выводятся необходимые аппроксимации решений. Он обычно работает для систем, имеющих до нескольких сотен сложных решений.

Рациональное одномерное представление можно вычислить с помощью Maple функции Groebner[RationalUnivariateRepresentation] .

Чтобы извлечь все комплексные решения из рационального одномерного представления, можно использовать MPSolve , который вычисляет комплексные корни одномерных полиномов с любой точностью. Рекомендуется запускать MPsolve несколько раз, каждый раз удваивая точность, пока решения не останутся устойчивыми, так как подстановка корней в уравнениях входных переменных может быть крайне нестабильной.

Второй решатель — PHCpack, ^[13]^[16] написано под руководством Дж. Вершельде. PHCpack реализует метод продолжения гомотопии. Этот решатель вычисляет изолированные комплексные решения полиномиальных систем, имеющих столько же уравнений, сколько переменных.

Третий решатель — Бертини, ^[17]^[18] авторы: DJ Bates, JD Hauenstein, AJ Sommese и CW Wampler. Бертини использует числовое продолжение гомотопии с адаптивной точностью. Помимо вычисления нульмерных наборов решений, PHCpack и Bertini способны работать с положительномерными наборами решений.

Четвертый решатель — это Maple библиотека RegularChains , написанная Марком Морено-Маза и соавторами. Содержит различные функции для решения полиномиальных систем с помощью регулярных цепей .

См. также

Ссылки

^ Бейтс и др. 2013 , с. 4
^ Бейтс и др. 2013 , с. 8
^ Сонгсин Лян, Дж. Герхард, DJ Джеффри, Г. Мороз, Пакет для решения параметрических полиномиальных систем . Коммуникации в компьютерной алгебре (2009)
^ Обри, П.; Маза, М. Морено (1999). «Треугольные множества для решения полиномиальных систем: сравнительная реализация четырех методов» . Дж. Симб. Вычислить . 28 (1–2): 125–154. дои : 10.1006/jsco.1999.0270 .
^ Фожер, Дж. К.; Джанни, П .; Лазард, Д.; Мора, Т. (1993). «Эффективное вычисление нульмерного базиса Грёбнера путем изменения порядка» . Журнал символических вычислений . 16 (4): 329–344. дои : 10.1006/jsco.1993.1051 .
^ Лазард, Д. (1992). «Решение нульмерных алгебраических систем». Журнал символических вычислений . 13 (2): 117–131. дои : 10.1016/S0747-7171(08)80086-7 .
^ Ксавье Дахан и Эрик Шост. Точные оценки треугольных множеств . Более того, недавние алгоритмы разложения полиномиальных систем на треугольные разложения создают регулярные цепочки с коэффициентами, соответствующими результатам Дахана и Шоста. В проце. ISSAC'04, страницы 103–110, ACM Press, 2004 г.
^ Дахан, Ксавьер; Морено Маза, Марк; Шост, Эрик; У, Вэньюань; Се, Южен (2005). «Техника подъема треугольных разложений» (PDF) . Труды ISAAC 2005 . АКМ Пресс. стр. 108–105.
^ Чанбо Чен и Марк Морено-Маза. Алгоритмы вычисления треугольного разложения полиномиальных систем.В учеб. ISSAC'2011, страницы 83-90, ACM Press, 2011 и Journal of Символические вычисления (будет опубликовано)
^ Руйе, Фабрис (1999). «Решение нульмерных систем посредством рационального одномерного представления». Прил. Алгебра англ. Коммун. Вычислить . 9 (9): 433–461. дои : 10.1007/s002000050114 . S2CID 25579305 .
^ Саугата Басу; Ричард Поллак; Мари-Франсуаза Рой (2006). Алгоритмы реальной алгебраической геометрии, глава 12.4 . Спрингер-Верлаг .
^ Лазард, Дэниел (2009). «Тридцать лет решения полиномиальных систем, а сейчас?» . Дж. Симб. Вычислить . 44 (3): 2009. doi : 10.1016/j.jsc.2008.03.004 .
^ Jump up to: Перейти обратно: ^а ^б Вершельде, Январь (1999). «Алгоритм 795: PHCpack: универсальный решатель для полиномиальных систем путем продолжения гомотопии» (PDF) . Транзакции ACM в математическом программном обеспечении . 25 (2): 251–276. дои : 10.1145/317275.317286 . S2CID 15485257 .
^ Джордж Э. Коллинз и Алкивиадис Г. Акритас, Полиномиальная изоляция действительного корня с использованием правила знаков Декарта . Материалы симпозиума ACM 1976 года по символьным и алгебраическим вычислениям.
^ Рулье, Ф.; Циммерман, П. (2004). «Эффективное выделение действительных корней полинома» . Журнал вычислительной и прикладной математики . 162 (1): 33–50. Бибкод : 2004JCoAM.162...33R . дои : 10.1016/j.cam.2003.08.015 .
^ Выпуск 2.3.86 PHCpack
^ Бейтс и др. 2013 год
^ Бертини: Программное обеспечение для числовой алгебраической геометрии

Бейтс, Дэниел Дж.; Соммесе, Эндрю Дж.; Хауэнштайн, Джонатан Д.; Уэмплер, Чарльз В. (2013). Численное решение полиномиальных систем с помощью Бертини . Филадельфия: Общество промышленной и прикладной математики. ISBN 978-1-61197-269-6 .
Кокс, Дэвид; Литтл, Джон; О'Ши, Донал (1997). Идеалы, разновидности и алгоритмы: введение в вычислительную алгебраическую геометрию и коммутативную алгебру (2-е изд.). Нью-Йорк: Спрингер. ISBN 978-0387946801 .
Морган, Александр (1987). Решение полиномиальных систем с использованием продолжения для инженерных и научных задач (изд. SIAM). Общество промышленной и прикладной математики (SIAM, 3600 Market Street, этаж 6, Филадельфия, Пенсильвания, 19104). ISBN 9780898719031 .
Штурмфельс, Бернд (2002). Решение систем полиномиальных уравнений . Провиденс, Род-Айленд: Американское математическое соц. ISBN 0821832514 .

[Bates_p4-1] Бейтс и др. 2013 , с. 4

[2] Бейтс и др. 2013 , с. 8

[3] Сонгсин Лян, Дж. Герхард, DJ Джеффри, Г. Мороз, Пакет для решения параметрических полиномиальных систем . Коммуникации в компьютерной алгебре (2009)

[4] Обри, П.; Маза, М. Морено (1999). «Треугольные множества для решения полиномиальных систем: сравнительная реализация четырех методов» . Дж. Симб. Вычислить . 28 (1–2): 125–154. дои : 10.1006/jsco.1999.0270 .

[5] Фожер, Дж. К.; Джанни, П .; Лазард, Д.; Мора, Т. (1993). «Эффективное вычисление нульмерного базиса Грёбнера путем изменения порядка» . Журнал символических вычислений . 16 (4): 329–344. дои : 10.1006/jsco.1993.1051 .

[6] Лазард, Д. (1992). «Решение нульмерных алгебраических систем». Журнал символических вычислений . 13 (2): 117–131. дои : 10.1016/S0747-7171(08)80086-7 .

[7] Ксавье Дахан и Эрик Шост. Точные оценки треугольных множеств . Более того, недавние алгоритмы разложения полиномиальных систем на треугольные разложения создают регулярные цепочки с коэффициентами, соответствующими результатам Дахана и Шоста. В проце. ISSAC'04, страницы 103–110, ACM Press, 2004 г.

[8] Дахан, Ксавьер; Морено Маза, Марк; Шост, Эрик; У, Вэньюань; Се, Южен (2005). «Техника подъема треугольных разложений» (PDF) . Труды ISAAC 2005 . АКМ Пресс. стр. 108–105.

[9] Чанбо Чен и Марк Морено-Маза. Алгоритмы вычисления треугольного разложения полиномиальных систем.В учеб. ISSAC'2011, страницы 83-90, ACM Press, 2011 и Journal of Символические вычисления (будет опубликовано)

[10] Руйе, Фабрис (1999). «Решение нульмерных систем посредством рационального одномерного представления». Прил. Алгебра англ. Коммун. Вычислить . 9 (9): 433–461. дои : 10.1007/s002000050114 . S2CID 25579305 .

[11] Саугата Басу; Ричард Поллак; Мари-Франсуаза Рой (2006). Алгоритмы реальной алгебраической геометрии, глава 12.4 . Спрингер-Верлаг .

[12] Лазард, Дэниел (2009). «Тридцать лет решения полиномиальных систем, а сейчас?» . Дж. Симб. Вычислить . 44 (3): 2009. doi : 10.1016/j.jsc.2008.03.004 .

[Vers99-13] Jump up to: Перейти обратно: ^а ^б Вершельде, Январь (1999). «Алгоритм 795: PHCpack: универсальный решатель для полиномиальных систем путем продолжения гомотопии» (PDF) . Транзакции ACM в математическом программном обеспечении . 25 (2): 251–276. дои : 10.1145/317275.317286 . S2CID 15485257 .

[14] Джордж Э. Коллинз и Алкивиадис Г. Акритас, Полиномиальная изоляция действительного корня с использованием правила знаков Декарта . Материалы симпозиума ACM 1976 года по символьным и алгебраическим вычислениям.

[15] Рулье, Ф.; Циммерман, П. (2004). «Эффективное выделение действительных корней полинома» . Журнал вычислительной и прикладной математики . 162 (1): 33–50. Бибкод : 2004JCoAM.162...33R . дои : 10.1016/j.cam.2003.08.015 .

[16] Выпуск 2.3.86 PHCpack

[17] Бейтс и др. 2013 год

[18] Бертини: Программное обеспечение для числовой алгебраической геометрии

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]