Мономиальный порядок

редактировать

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

  • Если и - любой другой одночлен, то. ты v {\ Displaystyle и \ leq v} ш {\ displaystyle w} ты ш v ш {\ displaystyle uw \ leq vw}

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

Содержание

  • 1 Определение, детали и варианты
    • 1.1 Ведущие одночлены, члены и коэффициенты
  • 2 Примеры
    • 2.1 Лексикографический порядок
    • 2.2 Градуированный лексикографический порядок
    • 2.3 Градуированный обратный лексикографический порядок
    • 2.4 Порядок ликвидации
    • 2.5 Весовой заказ
  • 3 Связанные понятия
  • 4 ссылки

Определение, детали и варианты

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

В случае конечного числа переменных хорошее упорядочение мономиального порядка эквивалентно конъюнкции следующих двух условий:

  1. Заказ - это общий заказ.
  2. Если u - любой одночлен, то. 1 ты {\ displaystyle 1 \ leq u}

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

Ведущие одночлены, члены и коэффициенты

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

Конкретно, пусть R - произвольное кольцо многочленов. Тогда множество М из (нормированных) мономов R является основой из R, рассматриваемая как векторное пространство над полем коэффициентов. Таким образом, любой ненулевой многочлен p в R имеет единственное выражение в виде линейной комбинации одночленов, где S - конечное подмножество M, а все c u не равны нулю. Когда выбран порядок мономов, старший моном является наибольшим u в S, старший коэффициент - это соответствующий c u, а старший член - это соответствующий c u u. Головной моном / коэффициент / термин иногда используется как синоним «ведущего». Некоторые авторы используют «одночлен» вместо «термин» и «степенное произведение» вместо «одночлен». В этой статье предполагается, что моном не включает коэффициент. п знак равно ты S c ты ты {\ displaystyle p = \ textstyle \ sum _ {u \ in S} c_ {u} u}

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

Примеры

На множестве степеней любой одной переменной x единственными мономиальными порядками являются естественный порядок 1 lt;  x  lt;x 2  lt;x 3  lt;... и его обратное, последнее из которых не является хорошим порядком. Поэтому понятие мономиального порядка становится интересным только в случае нескольких переменных. { Икс п п N } {\ displaystyle \ left \ {x ^ {n} \ mid n \ in \ mathbb {N} \ right \}}

Мономиальный порядок подразумевает порядок отдельных неопределенных. Можно упростить классификацию мономиальных порядков, предположив, что неопределенные имена называются x 1, x 2, x 3,... в порядке убывания для рассматриваемого мономиального порядка, так что всегда x 1 gt; x 2 gt; x 3 gt;…. (Если неопределенных должно быть бесконечно много, это соглашение несовместимо с условием хорошего упорядочения, и можно было бы использовать противоположный порядок; однако случай многочленов от бесконечного числа переменных рассматривается редко.) В примере ниже мы используем x, y и z вместо x 1, x 2 и x 3. При таком соглашении есть еще много примеров различных мономиальных порядков.

Лексикографический порядок

Лексикографический порядок (lex) сначала сравнивает показатели x 1 в одночленах, а в случае равенства сравнивает показатели x 2 и так далее. Название образовано из сходства с обычным алфавитным порядком, используемым в лексикографии для словарей, если одночлены представлены последовательностью показателей неопределенных. Если количество неопределенных элементов фиксировано (как это обычно бывает), лексикографический порядок является правильным, хотя это не относится к лексикографическому порядку, применяемому к последовательностям различной длины (см. Лексикографический порядок § Упорядочение последовательностей различная длина для. Гребнера основы вычислений этого упорядочение имеет тенденцию быть самым дорогим, поэтому его следует избегать, насколько это возможно, для очень простых вычислений, за исключением.

Градуированный лексикографический порядок

Градуированный лексикографический порядок (grlex или deglex для лексикографического порядка степеней ) сначала сравнивает общую степень (сумму всех показателей), а в случае равенства применяет лексикографический порядок. Этот порядок является не только хорошим, он также обладает тем свойством, что любому одночлену предшествует только конечное число других одночленов; это не относится к лексикографическому порядку, где все (бесконечно много) степеней x меньше, чем y (этот лексикографический порядок, тем не менее, хороший порядок, связан с невозможностью построения бесконечной убывающей цепочки мономов). Хотя это очень естественно, этот порядок используется редко: базис Грёбнера для градуированного обратного лексикографического порядка, который следует ниже, легче вычислить и предоставляет ту же информацию о входном наборе многочленов.

Градуированный обратный лексикографический порядок

Градуированный обратный лексикографический порядок (grevlex, или degrevlex для обратного лексикографического порядка степеней) сначала сравнивает общую степень, затем использует обратный лексикографический порядок в качестве разрешения конфликтов, но он меняет результат лексикографического сравнения, так что лексикографически более крупные одночлены той же степени считаются дегревлексом меньшего размера. Для того, чтобы окончательный порядок демонстрировал обычное упорядочение неопределенных x 1 gt; x 2 gt;…gt; x n, кроме того, необходимо, чтобы лексикографический порядок разрешения конфликтов перед изменением считал последний неопределенный x n наибольшим, что означает, что он надо начинать с этого неопределенного. Таким образом, конкретный рецепт градуированного обратного лексикографического порядка состоит в том, чтобы сначала сравнить по общей степени, затем сравнить показатели последнего неопределенного x n, но обратить результат (так, чтобы моном с меньшим показателем был больше в порядке), а затем (как всегда только в случае ничьей) аналогичным сравнением x n −1, и так далее, заканчивая x 1.

Различия между градуированными лексикографическими и обратными лексикографическими порядками незначительны, поскольку они фактически совпадают для 1 и 2 неопределенных. Первое различие касается одночленов степени 2 в трех неопределенных, которые классифицируются лексикографически, но в обратном лексикографическом порядке. Общая тенденция состоит в том, что обратный порядок показывает все переменные среди малых одночленов любой заданной степени, тогда как при необратимом порядке интервалы наименьших одночленов любой заданной степени будут образованы только из наименьших переменных. Икс 1 2 gt; Икс 1 Икс 2 gt; Икс 1 Икс 3 gt; Икс 2 2 gt; Икс 2 Икс 3 gt; Икс 3 2 {\ displaystyle x_ {1} ^ {2}gt; x_ {1} x_ {2}gt; x_ {1} x_ {3}gt; x_ {2} ^ {2}gt; x_ {2} x_ {3}gt; x_ { 3} ^ {2}} Икс 1 2 gt; Икс 1 Икс 2 gt; Икс 2 2 gt; Икс 1 Икс 3 gt; Икс 2 Икс 3 gt; Икс 3 2 {\ displaystyle x_ {1} ^ {2}gt; x_ {1} x_ {2}gt; x_ {2} ^ {2}gt; x_ {1} x_ {3}gt; x_ {2} x_ {3}gt; x_ { 3} ^ {2}}

Порядок ликвидации

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

Порядок веса

Порядок веса зависит от вектора, называемого вектором веса. Сначала он сравнивает скалярное произведение последовательностей экспонент мономов с этим вектором веса, а в случае равенства использует какой-то другой фиксированный порядок мономов. Например, приведенные выше ранжированные заказы являются весовыми порядками для вектора весов «общей степени» (1,1,..., 1). Если a i - рационально независимые числа (так, в частности, ни одно из них не равно нулю, а все дроби иррациональны), то ничья не может произойти, а сам вектор весов определяет мономиальный порядок. В противном случае можно было бы использовать другой весовой вектор, чтобы разорвать связи, и так далее; после использования n линейно независимых весовых векторов не может остаться никаких связей. Фактически можно определить любой мономиальный порядок с помощью последовательности весовых векторов ( Кокс и др., Стр. 72–73), например (1,0,0,..., 0), (0,1,0,..., 0),... (0,0,..., 1) для lex, или (1,1,1,..., 1), (1,1,..., 1,0),... (1,0,..., 0) для grevlex. ( а 1 , , а п ) р 0 п {\ displaystyle (a_ {1}, \ ldots, a_ {n}) \ in \ mathbb {R} _ {\ geq 0} ^ {n}} а я а j {\ displaystyle {\ tfrac {a_ {i}} {a_ {j}}}}

Например, рассмотрим одночлены,,, и ; приведенные выше порядки мономов упорядочили бы эти четыре монома следующим образом: Икс y 2 z {\ displaystyle xy ^ {2} z} z 2 {\ displaystyle z ^ {2}} Икс 3 {\ displaystyle x ^ {3}} Икс 2 z 2 {\ Displaystyle х ^ {2} г ^ {2}}

  • Лекс: (власть доминирует). Икс 3 gt; Икс 2 z 2 gt; Икс y 2 z gt; z 2 {\ displaystyle x ^ {3}gt; x ^ {2} z ^ {2}gt; xy ^ {2} zgt; z ^ {2}} Икс {\ displaystyle x}
  • Grlex: (доминирует общая степень; более высокая степень разрыва связи среди первых двух). Икс 2 z 2 gt; Икс y 2 z gt; Икс 3 gt; z 2 {\ displaystyle x ^ {2} z ^ {2}gt; ху ^ {2} zgt; x ^ {3}gt; z ^ {2}} Икс {\ displaystyle x}
  • Grevlex: (преобладает общая степень; меньшая степень разрыва связи среди первых двух). Икс y 2 z gt; Икс 2 z 2 gt; Икс 3 gt; z 2 {\ displaystyle xy ^ {2} zgt; x ^ {2} z ^ {2}gt; x ^ {3}gt; z ^ {2}} z {\ displaystyle z}
  • Весовой порядок с вектором весов (1,2,4): (скалярные произведения 10gt; 9gt; 8gt; 3 не оставляют здесь никаких связей, которые нужно разорвать). Икс 2 z 2 gt; Икс y 2 z gt; z 2 gt; Икс 3 {\ displaystyle x ^ {2} z ^ {2}gt; ху ^ {2} zgt; z ^ {2}gt; x ^ {3}}

Связанные понятия

  • An порядка ликвидации гарантирует, что одночлен с участием любого из множества неизвестных всегда будет больше, чем одночлен, не связанные с каким - либо из них.
  • Заказ продукта, тем легче пример порядка ликвидации. Он состоит в объединении мономиальных порядков на непересекающихся множествах неопределенных в мономиальный порядок на их объединении. Он просто сравнивает показатели неопределенностей в первом наборе, используя первый мономиальный порядок, затем разрывает связи, используя другой мономиальный порядок на неопределенных значениях второго набора. Этот метод, очевидно, распространяется на любое непересекающееся объединение множеств неопределенных; лексикографический порядок может быть получен таким образом из одноэлементных наборов { x 1 }, { x 2 }, { x 3 },... (с уникальным мономиальным порядком для каждого одноэлементного набора).

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

Рекомендации

  • Дэвид Кокс; Джон Литтл; Донал О'Ши (2007). Идеалы, разновидности и алгоритмы: введение в вычислительную алгебраическую геометрию и коммутативную алгебру. Springer. ISBN   978-0-387-35650-1.
Последняя правка сделана 2024-01-07 03:44:03
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте