Введение

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

Нули

Результант двух многочленов с коэффициентами в интегральной области равен нулю тогда и только тогда, когда у них есть общий делитель положительной степени. Результант двух многочленов с коэффициентами в интегральной области равен нулю тогда и только тогда, когда у них есть общий корень в алгебраически замкнутом поле, содержащем коэффициенты этих многочленов. Существуют многочлен P степени меньше e и многочлен Q степени меньше d такие, что Это обобщение тождества Безу для многочленов над произвольным коммутативным кольцом. Иными словами, результат двух многочленов принадлежит идеалу, порожденному этими многочленами.

Вычисления

Теоретически, результирующая может быть вычислена с использованием формулы, выражающей её как произведение разностей корней. Однако, поскольку корни обычно не могут быть вычислены точно, такой алгоритм был бы неэффективным и численно неустойчивым. Поскольку результирующая является симметричной функцией корней каждого многочлена, её также можно вычислить, используя фундаментальную теорему о симметричных многочленах, но это было бы крайне неэффективно. Поскольку результирующая является определителем матрицы Сильвестра (и матрицы Безу), её можно вычислить с помощью любого алгоритма для вычисления определителей. Это требует арифметических операций. Поскольку известны алгоритмы с лучшей сложностью (см. ниже), этот метод не используется на практике. Отсюда следует, что вычисление результирующей тесно связано с алгоритмом Евклида для многочленов. Это показывает, что вычисление результирующей двух многочленов степеней d и e может быть выполнено за арифметических операций в поле коэффициентов. Однако, когда коэффициенты являются целыми числами, рациональными числами или полиномами, эти арифметические операции подразумевают ряд вычислений НОД коэффициентов, которые имеют сопоставимый порядок и делают алгоритм неэффективным. Последовательности псевдоостатков, подчиненных результирующей, были введены для решения этой проблемы и избежания любых вычислений с дробями и НОД коэффициентов. Более эффективный алгоритм получается, используя хорошее поведение результирующей при гомоморфизме колец на коэффициентах: для вычисления результирующей двух многочленов с целочисленными коэффициентами вычисляют их результирующие по достаточно большому числу простых чисел, а затем восстанавливают результат с помощью китайской теоремы об остатках. Использование быстрого умножения целых чисел и многочленов позволяет создавать алгоритмы для вычисления результирующих и наибольших общих делителей, которые имеют лучшую временную сложность, порядка сложности умножения, умноженной на логарифм размера входных данных (где s – верхняя граница числа цифр входных многочленов).

Применение к многочленным системам

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

Теория чисел

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

Компьютерная алгебра

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

Результант Маколея

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

Вычислимость

Поскольку вычисление результирующей может быть сведено к вычислению определителей и наибольшего общего делителя многочлена, существуют алгоритмы вычисления результирующей за конечное число шагов. Однако, общая результирующая является многочленом очень высокой степени (экспоненциальной относительно n), зависящим от огромного числа переменных. Из этого следует, что, за исключением очень малых n и очень малых степеней входных многочленов, общую результирующую на практике невозможно вычислить даже с использованием современных компьютеров. Более того, число мономов общей результирующей настолько велико, что, если бы она была вычислима, результат нельзя было бы сохранить в доступных устройствах памяти, даже для относительно небольших значений n и степеней входных многочленов. Поэтому вычисление результирующей имеет смысл только для многочленов, коэффициенты которых принадлежат полю или являются многочленами от нескольких переменных над полем. В случае входных многочленов с коэффициентами в поле, точное значение результирующей редко важно, имеет значение лишь её равенство (или неравенство) нулю. Поскольку результирующая равна нулю тогда и только тогда, когда ранг матрицы Маколея меньше числа её строк, это равенство нулю можно проверить, применив метод Гаусса к матрице Маколея. Это обеспечивает вычислительную сложность, где d – максимальная степень входных многочленов. Другой случай, когда вычисление результирующей может предоставить полезную информацию, – это когда коэффициенты входных многочленов являются многочленами от небольшого числа переменных, часто называемых параметрами. В этом случае, если результирующая не равна нулю, она определяет гиперповерхность в параметрическом пространстве. Точка принадлежит этой гиперповерхности, если и только если существуют значения переменных, которые вместе с координатами точки являются корнями входных многочленов. Иными словами, результирующая является результатом "исключения" переменных из входных многочленов.