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

Система полиномиальных уравнений (иногда просто полиномиальная система) представляет собой совокупность одновременных уравнений F 1 = 0,..., е ч = 0 где в е я являюсь многочленами от нескольких переменных, скажем, х 1,..., х n, над некоторым полем k.

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

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

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

• 1 Определение
• 2 Основные свойства и определения
• 3 Что решает?
• 4 расширения
  • 4.1 Тригонометрические уравнения
  • 4.2 Решения в конечном поле
  • 4.3 Коэффициенты в числовом поле или в конечном поле непростого порядка
• 5 Алгебраическое представление решений
  • 5.1 Обычные цепи
  • 5.2 Рациональное одномерное представление
• 6 Численное решение
  • 6.1 Общие алгоритмы решения
  • 6.2 Метод продолжения гомотопии
  • 6.3 Численное решение из рационального одномерного представления
• 7 пакетов программного обеспечения
• 8 См. Также
• 9 ссылки

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

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

${\ displaystyle {\ begin {align} x ^ {2} -1 amp; = 0 \\ y ^ {2} -4 amp; = 0. \ end {align}}}$

Его решениями являются четыре пары ( x, y) = (1, 2), (−1, 2), (1, −2), (−1, −2).

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

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

${\ displaystyle {\ begin {align} f_ {1} \ left (x_ {1}, \ ldots, x_ {m} \ right) amp; = 0 \\ amp; \; \; \ vdots \\ f_ {n} \ left (x_ {1}, \ ldots, x_ {m} \ right) amp; = 0, \ end {align}}}$

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

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

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

${\ Displaystyle {\ begin {выровнено} х (х-1) amp; = 0 \\ х (у-1) amp; = 0 \ конец {выровнено}}}$

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

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

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

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

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

Нульмерную систему с таким количеством уравнений, сколько переменных, иногда говорят, что она ведет себя хорошо. Теорема Безу утверждает, что система с хорошим поведением, уравнения которой имеют степени d 1,..., d n, имеет не более d 1 ⋅⋅⋅ d n решений. Эта оценка точна. Если все степени равны d, эта граница становится d ⁿ и экспоненциальна по количеству переменных. ( Основная теорема алгебры - это частный случай n = 1.)

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

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

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

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

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

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

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

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

Например, из-за личности

${\ Displaystyle \ соз (3x) = 4 \ соз ^ {3} (х) -3 \ соз (х),}$

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

${\ Displaystyle \ грех ^ {3} (х) + \ соз (3х) = 0}$

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

${\ displaystyle {\ begin {cases} s ^ {3} + 4c ^ {3} -3c amp; = 0 \\ s ^ {2} + c ^ {2} -1 amp; = 0. \ end {cases}}}$

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

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

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

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

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

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

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

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

Обычные цепочки

Основная статья: Обычная цепочка

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

• f i - многочлен только от x 1,..., x i, который имеет степень d i gt; 0 по x i ;
• коэффициент при x i ^{d i} в f i является многочленом от x 1,..., x i −1, который не имеет общего нуля с f 1,..., f i - 1.

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

${\ displaystyle {\ 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 {ases}}}$

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

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

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

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

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

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

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

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

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

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

Рациональное одномерное представление или рубли является представлением решений нульмерной полиномиальной системы над рациональными числами, которые были введены Ф. Rouillier.

RUR нульмерной системы состоит из линейной комбинации x 0 переменных, называемой разделяющей переменной, и системы уравнений

${\ displaystyle {\ 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}}}$

где ч является одномерным многочленом от й 0 степени D и г 0,..., г п являются одномерными многочленами х 0 степеней меньше D.

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

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

Например, для системы из предыдущего раздела каждая линейная комбинация переменной, за исключением кратных x, y и x + y, является разделяющей переменной. Если выбрать t = х - у/2 в качестве разделяющей переменной, то RUR равен

${\ displaystyle {\ 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 {case}}}$

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

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

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

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

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

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

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

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

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

Основная статья: продолжение гомотопии

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Второй решатель - это PHCpack, написанный под руководством Дж. Вершельде. PHCpack реализует метод продолжения гомотопии. Этот решатель вычисляет изолированные комплексные решения полиномиальных систем, содержащих столько же уравнений, сколько и переменных.

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

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

• Системы полиномиальных неравенств
• Треугольное разложение
• Метод характеристического множества Ву

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