Результат - Resultant

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

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

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

Обозначение

Результат двух одномерных многочленов A и B обычно обозначается или${\ displaystyle \ operatorname {res} (A, B)}$${\ displaystyle \ operatorname {Res} (A, B).}$

Во многих приложениях результирующего многочлены зависят от нескольких неопределенностей и могут рассматриваться как одномерные многочлены от одного из своих неопределенных, с многочленами от других неопределенных в качестве коэффициентов. В этом случае неопределенное значение, которое выбрано для определения и вычисления результата, указывается как нижний индекс: или${\ displaystyle \ operatorname {res} _ {x} (A, B)}$${\ displaystyle \ operatorname {Res} _ {x} (A, B).}$

Степени полиномов используются в определении результирующей. Однако полином степени d можно также рассматривать как полином более высокой степени, где старшие коэффициенты равны нулю. Если для полученного результата используется такая более высокая степень, она обычно указывается в виде нижнего или верхнего индекса, например, или${\ displaystyle \ operatorname {res} _ {d, e} (A, B)}$${\ displaystyle \ operatorname {res} _ {x} ^ {d, e} (A, B).}$

Определение

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

${\ displaystyle A = a_ {0} x ^ {d} + a_ {1} x ^ {d-1} + \ cdots + a_ {d}}$

а также

${\ displaystyle B = b_ {0} x ^ {e} + b_ {1} x ^ {e-1} + \ cdots + b_ {e}}$

ненулевые полиномы степеней d и e соответственно. Обозначу в векторном пространстве (или свободным модуль , если коэффициенты принадлежат коммутативному кольцу) размерности I , элементы которого являются многочленами степени строго меньше , чем я . Карта ${\ Displaystyle {\ mathcal {P}} _ {я}}$

${\ displaystyle \ varphi: {\ mathcal {P}} _ {e} \ times {\ mathcal {P}} _ {d} \ rightarrow {\ mathcal {P}} _ {d + e}}$

такой, что

${\ Displaystyle \ varphi (P, Q) = AP + BQ}$

это линейная карта между двумя пространствами одного измерения. На основе степеней x (перечисленных в порядке убывания) эта карта представлена ​​квадратной матрицей размерности d + e , которая называется матрицей Сильвестра для A и B (для многих авторов и в статье Матрица Сильвестра , матрица Сильвестра определяется как транспонированная матрица; это соглашение здесь не используется, поскольку оно нарушает обычное соглашение для записи матрицы линейной карты).

Таким образом, результат A и B является определителем

${\ displaystyle {\ begin {vmatrix} a_ {0} & 0 & \ cdots & 0 & b_ {0} & 0 & \ cdots & 0 \\ a_ {1} & a_ {0} & \ cdots & 0 & b_ {1} & b_ {0} & \ cdots & 0 \ \ a_ {2} & a_ {1} & \ ddots & 0 & b_ {2} & b_ {1} & \ ddots & 0 \\\ vdots & \ vdots & \ ddots & a_ {0} & \ vdots & \ vdots & \ ddots & b_ {0 } \\ a_ {d} & a_ {d-1} & \ cdots & \ vdots & b_ {e} & b_ {e-1} & \ cdots & \ vdots \\ 0 & a_ {d} & \ ddots & \ vdots & 0 & b_ {e } & \ ddots & \ vdots \\\ vdots & \ vdots & \ ddots & a_ {d-1} & \ vdots & \ vdots & \ ddots & b_ {e-1} \\ 0 & 0 & \ cdots & a_ {d} & 0 & 0 & \ cdots & b_ {e} \ end {vmatrix}},}$

который имеет e столбцов a _i и d столбцов b _j (тот факт, что первый столбец a и первый столбец b имеют одинаковую длину, то есть d = e , здесь только для упрощения отображения определителя). Например, взяв d = 3 и e = 2, получим

${\ displaystyle {\ begin {vmatrix} a_ {0} & 0 & b_ {0} & 0 & 0 \\ a_ {1} & a_ {0} & b_ {1} & b_ {0} & 0 \\ a_ {2} & a_ {1} & b_ {2 } & b_ {1} & b_ {0} \\ a_ {3} & a_ {2} & 0 & b_ {2} & b_ {1} \\ 0 & a_ {3} & 0 & 0 & b_ {2} \ end {vmatrix}}.}$

Если коэффициенты многочленов принадлежат области целостности , то

${\ displaystyle \ operatorname {res} (A, B) = a_ {0} ^ {e} b_ {0} ^ {d} \ prod _ {\ begin {array} {c} 1 \ leq i \ leq d \ \ 1 \ leq j \ leq e \ end {array}} (\ lambda _ {i} - \ mu _ {j}) = a_ {0} ^ {e} \ prod _ {i = 1} ^ {d} B (\ lambda _ {i}) = (- 1) ^ {de} b_ {0} ^ {d} \ prod _ {j = 1} ^ {e} A (\ mu _ {j}),}$

где и - соответственно корни с учетом их кратностей A и B в любом алгебраически замкнутом поле, содержащем область целостности. Это прямое следствие описывающих свойств полученного продукта, которые приведены ниже. В общем случае целочисленных коэффициентов алгебраически замкнутое поле обычно выбирается как поле комплексных чисел . ${\ displaystyle \ lambda _ {1}, \ dots, \ lambda _ {d}}$${\ displaystyle \ mu _ {1}, \ dots, \ mu _ {e}}$

Характеристики

В этом разделе и его подразделах A и B - два полинома от x соответствующих степеней d и e , и их результат обозначен ${\ displaystyle \ operatorname {res} (A, B).}$

Характеристика свойств

Результирующая двух полиномов A и B соответствующих степеней d и e с коэффициентами в коммутативном кольце R имеет следующие свойства, которые характеризуют результирующую, если R является полем или, в более общем смысле, областью целостности

• Если R является подкольцом другого кольца S , то То есть и В имеют ту же равнодействующую , когда рассматриваются как многочлены над R или S .${\ displaystyle \ operatorname {res} _ {R} (A, B) = \ operatorname {res} _ {S} (A, B).}$
• Если d = 0 (то есть, если является ненулевой константой), то Аналогично, если e = 0 , то${\ displaystyle A = a_ {0}}$${\ displaystyle \ operatorname {res} (A, B) = a_ {0} ^ {e}.}$${\ displaystyle \ operatorname {res} (A, B) = b_ {0} ^ {d}.}$
• ${\ displaystyle \ operatorname {res} (x + a_ {1}, x + b_ {1}) = b_ {1} -a_ {1}}$
• ${\ displaystyle \ operatorname {res} (B, A) = (- 1) ^ {de} \ operatorname {res} (A, B)}$
• ${\ displaystyle \ operatorname {res} (AB, C) = \ operatorname {res} (A, C) \ operatorname {res} (B, C)}$

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

Нули

• Результат двух многочленов с коэффициентами в области целостности равен нулю тогда и только тогда, когда они имеют общий делитель положительной степени.
• Результат двух многочленов с коэффициентами в области целостности равен нулю тогда и только тогда, когда они имеют общий корень в алгебраически замкнутом поле, содержащем коэффициенты.
• Существует многочлен P степени меньше e и многочлен Q степени меньше d такие, что Это обобщение тождества Безу на многочлены над произвольным коммутативным кольцом. Другими словами, результат двух многочленов принадлежит идеалу, порожденному этими многочленами.${\ displaystyle \ operatorname {res} (A, B) = AP + BQ.}$

Инвариантность гомоморфизмами колец

Пусть и Б два многочлена соответствующих степеней дней и е с коэффициентами в коммутативном кольце R и кольцевой гомоморфизм из R в другой коммутативное кольце S . Применение к коэффициентам полинома продолжается до гомоморфизма колец многочленов , который также обозначается этим обозначением, мы имеем: ${\ Displaystyle \ varphi \ двоеточие R \ to S}$${\ displaystyle \ varphi}$${\ displaystyle \ varphi}$${\ Displaystyle Р [х] \ к S [х]}$${\ displaystyle \ varphi.}$

• Если сохраняет степени A и B (то есть если и ), то${\ displaystyle \ varphi}$${\ Displaystyle \ deg (\ varphi (A)) = d}$${\ Displaystyle \ deg (\ varphi (B)) = е}$

${\ displaystyle \ varphi (\ operatorname {res} (A, B)) = \ operatorname {res} (\ varphi (A), \ varphi (B)).}$

• Если и тогда${\ Displaystyle \ deg (\ varphi (A)) <d}$${\ Displaystyle \ deg (\ varphi (B)) <е,}$

${\ displaystyle \ varphi (\ operatorname {res} (A, B)) = 0.}$

• Если и и старший коэффициент A равен, то${\ Displaystyle \ deg (\ varphi (A)) = d}$${\ Displaystyle \ deg (\ varphi (B)) = е <е,}$${\ displaystyle a_ {0}}$

${\ displaystyle \ varphi (\ operatorname {res} (A, B)) = \ varphi (a_ {0}) ^ {ef} \ operatorname {res} (\ varphi (A), \ varphi (B)).}$

• Если и и старший коэффициент B равен, то${\ Displaystyle \ deg (\ varphi (A)) = е <d}$${\ Displaystyle \ deg (\ varphi (B)) = е,}$${\ displaystyle b_ {0}}$

${\ displaystyle \ varphi (\ operatorname {res} (A, B)) = (- 1) ^ {e (df)} \ varphi (b_ {0}) ^ {df} \ operatorname {res} (\ varphi ( A), \ varphi (B)).}$

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

Инвариантность относительно замены переменной

• ${\ Displaystyle \ OperatorName {res} (A (x + a), B (x + a)) = \ operatorname {res} (A (x), B (x))}$
• ${\ displaystyle \ operatorname {res} (A (ax), B (ax)) = a ^ {de} \ operatorname {res} (A (x), B (x))}$
• Если и являются взаимные многочлены из А и В , соответственно, то${\ Displaystyle А_ {г} (х) = х ^ {d} А (1 / х)}$${\ Displaystyle В_ {г} (х) = х ^ {е} В (1 / х)}$

${\ displaystyle \ operatorname {res} (A_ {r}, B_ {r}) = (- 1) ^ {de} \ operatorname {res} (A, B)}$

Это означает, что свойство нулевой результирующей инвариантно относительно линейных и проективных изменений переменной.

Инвариантность относительно замены многочленов

• Если a и b ненулевые константы (то есть они не зависят от неопределенного x ), а A и B такие же, как указано выше, то

${\ displaystyle \ operatorname {res} (aA, bB) = a ^ {e} b ^ {d} \ operatorname {res} (A, B).}$

• Если A и B такие же, как указано выше, и C - другой многочлен такой, что степень A - CB равна δ , то

${\ displaystyle \ operatorname {res} (A-CB, B) = b_ {0} ^ {\ delta -d} \ operatorname {res} (A, B).}$

• В частности, если либо Б является унитарным , или градом С <град - град Б , то

${\ displaystyle \ operatorname {res} (A-CB, B) = \ operatorname {res} (A, B),}$

и, если f = deg C > deg A - deg B = d - e , то

${\ displaystyle \ operatorname {res} (A-CB, B) = b_ {0} ^ {e + fd} \ operatorname {res} (A, B).}$

Эти свойства подразумевают, что в алгоритме Евклида для полиномов и всех его вариантах ( псевдоостаточных последовательностях ) результат двух последовательных остатков (или псевдоостаточных остатков) отличается от равнодействующего исходных многочленов на множитель, который легко вычислить. . Наоборот, это позволяет вывести результат исходных многочленов из значения последнего остатка или псевдо-остатка. Это начальная идея алгоритма последовательности подрезультанта-псевдо-остатка , который использует приведенные выше формулы для получения подрезультатных полиномов как псевдоостаточных остатков, а результирующий результат - как последний ненулевой псевдоостаточный остаток (при условии, что результат не равен нулю). Этот алгоритм работает для многочленов от целых чисел или, в более общем смысле, от области целостности без какого-либо деления, кроме точного (то есть без участия дробей). Он включает в себя арифметические операции, в то время как вычисление определителя матрицы Сильвестра стандартными алгоритмами требует арифметических операций. ${\ Displaystyle О (де)}$${\ Displaystyle О ((д + е) ^ {3})}$

Общие свойства

В этом разделе мы рассмотрим два многочлена

${\ displaystyle A = a_ {0} x ^ {d} + a_ {1} x ^ {d-1} + \ cdots + a_ {d}}$

а также

${\ displaystyle B = b_ {0} x ^ {e} + b_ {1} x ^ {e-1} + \ cdots + b_ {e}}$

чей д + е + 2 коэффициентов различные неизвестные . Позволять

${\ Displaystyle R = \ mathbb {Z} [a_ {0}, \ ldots, a_ {d}, b_ {0}, \ ldots, b_ {e}]}$

- кольцо многочленов над целыми числами, определяемыми этими неопределенными. Результирующий часто называют общим результирующим для степеней d и e . Он обладает следующими свойствами. ${\ displaystyle \ operatorname {res} (A, B)}$

• ${\ displaystyle \ operatorname {res} (A, B)}$является абсолютно неприводимым многочленом.
• Если это идеал из порожденного A и B , то есть главный идеал , порожденный .${\ displaystyle I}$${\ displaystyle R [x]}$${\ Displaystyle I \ cap R}$${\ displaystyle \ operatorname {res} (A, B)}$

Однородность

Общий полученный для степеней д и е является однородным по - разному. Точнее:

• Он однороден степени е в${\ displaystyle a_ {0}, \ ldots, a_ {d}.}$
• Он однороден степени d в${\ displaystyle b_ {0}, \ ldots, b_ {e}.}$
• Он однороден степени d + e по всем переменным и${\ displaystyle a_ {i}}$${\ displaystyle b_ {j}.}$
• Если и присвоены вес i (т. Е. Вес каждого коэффициента является его степенью как элементарного симметричного полинома ), то он квазиоднороден общего веса de .${\ displaystyle a_ {i}}$${\ displaystyle b_ {i}}$
• Если P и Q являются однородными многомерными многочленами соответствующих степеней d и e , то их равнодействующая в степенях d и e относительно неопределенного x , обозначенного в § Обозначения , однородна степени de для других неопределенных.${\ displaystyle \ operatorname {res} _ {x} ^ {d, e} (P, Q)}$

Устранение собственности

∗ Пусть - идеал, порожденный двумя многочленами A и B в кольце многочленов, где само является кольцом многочленов над полем. Если хотя бы один из A и B является моническим по x , то: ${\ Displaystyle I = \ langle A, B \ rangle}$${\ Displaystyle R [х],}$${\ Displaystyle R = к [y_ {1}, \ ldots, y_ {n}]}$

• ${\ displaystyle \ operatorname {res} _ {x} (A, B) \ in I \ cap R}$
• Идеалы и определяют одно и то же алгебраическое множество . То есть набор из n элементов алгебраически замкнутого поля является общим нулем элементов тогда и только тогда, когда он является нулем${\ Displaystyle I \ cap R}$${\ displaystyle R \ operatorname {res} _ {x} (A, B)}$${\ Displaystyle I \ cap R}$${\ displaystyle \ operatorname {res} _ {x} (A, B).}$
• Идеал имеет тот же радикал, что и главный идеал. То есть каждый элемент имеет силу, кратную${\ Displaystyle I \ cap R}$ ${\ displaystyle R \ operatorname {res} _ {x} (A, B).}$${\ Displaystyle I \ cap R}$${\ displaystyle \ operatorname {res} _ {x} (A, B).}$
• Все неприводимые множители из разделяй любой элемент${\ displaystyle \ operatorname {res} _ {x} (A, B)}$${\ displaystyle I \ cap R.}$

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

По крайней мере , один из А и В является унитарным, А п кортеж является нулем , если и только если существует такое , что является общим нулем A и B . Такой общий нуль также нуль всех элементов И наоборот, если является общим нулем элементов этого является нуль равнодействующей, и существует такое , что является общим нулем A и B . Так и есть точно такие же нули. ${\ displaystyle (\ beta _ {1}, \ ldots, \ beta _ {n})}$${\ displaystyle \ operatorname {res} _ {x} (A, B)}$${\ displaystyle \ alpha}$${\ displaystyle (\ beta _ {1}, \ ldots, \ beta _ {n}, \ alpha)}$${\ displaystyle I \ cap R.}$${\ displaystyle (\ beta _ {1}, \ ldots, \ beta _ {n}, \ alpha)}$${\ displaystyle I \ cap R,}$${\ displaystyle \ alpha}$${\ displaystyle (\ beta _ {1}, \ ldots, \ beta _ {n}, \ alpha)}$${\ Displaystyle I \ cap R}$${\ displaystyle R \ operatorname {res} _ {x} (A, B)}$

Вычисление

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

В полученный в результате является определяющим из матрицы Сильвестра (и из матрицы Безу ), может быть вычислена с использованием любого алгоритма для вычисления определителей. Для этого нужны арифметические операции. Поскольку известны алгоритмы более высокой сложности (см. Ниже), этот метод на практике не используется. ${\ Displaystyle О (п ^ {3})}$

Из § Инвариантность относительно замены многочленов следует, что вычисление результирующей функции сильно связано с алгоритмом Евклида для многочленов . Это показывает, что вычисление результата двух многочленов степеней d и e может быть выполнено с помощью арифметических операций в области коэффициентов. ${\ Displaystyle О (де)}$

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

Использование быстрого умножения целых чисел и многочленов позволяет использовать алгоритмы для результирующих и наибольших общих делителей, которые имеют лучшую временную сложность , которая имеет порядок сложности умножения, умноженного на логарифм размера входных данных ( где s - верхняя граница количества цифр входных многочленов). ${\ displaystyle \ log (s (d + e)),}$

Приложение к полиномиальным системам

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

Случай двух уравнений с двумя неизвестными

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

${\ Displaystyle {\ begin {align} P (x, y) & = 0 \\ Q (x, y) & = 0, \ end {align}}}$

где P и Q - полиномы полной степени d и e соответственно . Тогда является многочленом от x , который в общем случае имеет степень de (по свойствам § Однородности ). Значение по й является корнем R тогда и только тогда , когда либо существует в алгебраически замкнутом поле , содержащих коэффициенты, таким образом, что , или и (в данном случае, говорит , что Р и Q имеют общий корень на бесконечности ). ${\ Displaystyle R = \ OperatorName {res} _ {y} ^ {d, e} (P, Q)}$${\ displaystyle \ alpha}$${\ displaystyle \ beta}$${\ Displaystyle Р (\ альфа, \ бета) = Q (\ альфа, \ бета) = 0}$${\ Displaystyle \ градус (п (\ альфа, у)) <д}$${\ Displaystyle \ deg (Q (\ альфа, y)) <е}$${\ Displaystyle х = \ альфа}$

Следовательно, решения системы получаются путем вычисления корней R , и для каждого корня вычисляется общий корень (корень) из и${\ displaystyle \ alpha,}$${\ Displaystyle Р (\ альфа, у),}$ ${\ Displaystyle Q (\ альфа, у),}$${\ displaystyle \ operatorname {res} _ {x} (P, Q).}$

Теоремы Без вытекает из значения , произведения степеней P и Q . На самом деле, после линейной замены переменных, можно предположить , что, для каждого корня х равнодействующей, существует ровно одно значение у таких , что ( х , у ) является общим нулем P и Q . Это показывает , что число общих нулей не превосходит степень равнодействующих, то есть не более чем произведение степеней P и Q . С некоторыми техническими особенностями это доказательство может быть расширено, чтобы показать, что с учетом кратностей и нулей на бесконечности количество нулей в точности равно произведению степеней. ${\ displaystyle \ deg \ left (\ operatorname {res} _ {y} (P, Q) \ right) \ leq de}$

Общий случай

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

${\ Displaystyle P_ {1} (x_ {1}, \ ldots, x_ {n}) = 0}$

${\ displaystyle \ vdots}$

${\ Displaystyle P_ {k} (x_ {1}, \ ldots, x_ {n}) = 0}$

путем вычисления результирующих каждой пары относительно исключения одного неизвестного и повторения процесса до получения одномерных многочленов. К сожалению, это приводит к появлению множества ложных решений, которые трудно устранить. ${\ displaystyle (P_ {i}, P_ {j})}$${\ displaystyle x_ {n}}$

Метод, представленный в конце 19 века, работает следующим образом: ввести k - 1 новых неопределенных и вычислить ${\ Displaystyle U_ {2}, \ ldots, U_ {k}}$

${\ displaystyle \ operatorname {res} _ {x_ {n}} (P_ {1}, U_ {2} P_ {2} + \ cdots + U_ {k} P_ {k}).}$

Это многочлен , коэффициенты которого являются многочленами, у которых есть свойство, которое является общим нулем этих коэффициентов многочлена, тогда и только тогда, когда одномерные многочлены имеют общий ноль, возможно, на бесконечности . Этот процесс может повторяться до тех пор, пока не будут найдены одномерные многочлены. ${\ Displaystyle U_ {2}, \ ldots, U_ {k}}$${\ displaystyle x_ {1}, \ ldots, x_ {n-1},}$${\ Displaystyle \ альфа _ {1}, \ ldots, \ альфа _ {п-1}}$${\ Displaystyle P_ {я} (\ альфа _ {1}, \ ldots, \ альфа _ {п-1}, x_ {п})}$

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

Этот алгоритм очень сложен и имеет огромную временную сложность . Поэтому его интерес в основном исторический.

Другие приложения

Теория чисел

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

Если и являются алгебраическими числами , такими , что , то есть корень равнодействующего и является корнем , где это степень из . В сочетании с тем фактом, что это корень , это показывает, что набор алгебраических чисел является полем . ${\ displaystyle \ alpha}$${\ displaystyle \ beta}$${\ Displaystyle Р (\ альфа) = Q (\ бета) = 0}$${\ Displaystyle \ гамма = \ альфа + \ бета}$${\ displaystyle \ operatorname {res} _ {x} (P (x), Q (zx)),}$${\ Displaystyle \ тау = \ альфа \ бета}$${\ displaystyle \ operatorname {res} _ {x} (P (x), x ^ {n} Q (z / x))}$${\ displaystyle n}$${\ displaystyle Q (y)}$${\ displaystyle 1 / \ beta}$${\ Displaystyle у ^ {п} Q (1 / у) = 0}$

Пусть алгебраическое расширение поля , создаваемого элементом , который имеет в качестве минимального многочлена . Каждый элемент может быть записан как где - многочлен. Тогда является корнем и эта равнодействующая является степенью минимального многочлена от${\ Displaystyle К (\ альфа)}$${\ displaystyle \ alpha,}$${\ Displaystyle P (x)}$${\ Displaystyle \ бета \ в К (\ альфа)}$${\ Displaystyle \ бета = Q (\ альфа),}$${\ displaystyle Q}$${\ displaystyle \ beta}$${\ displaystyle \ operatorname {res} _ {x} (P (x), zQ (x)),}$${\ displaystyle \ beta.}$

Алгебраическая геометрия

Для двух плоских алгебраических кривых, определенных как нули многочленов P ( x , y ) и Q ( x , y ) , результат позволяет вычислить их пересечение. Точнее, корни - это координаты x точек пересечения и общих вертикальных асимптот, а корни - координаты y точек пересечения и общих горизонтальных асимптот. ${\ displaystyle \ operatorname {res} _ {y} (P, Q)}$${\ displaystyle \ operatorname {res} _ {x} (P, Q)}$

Рациональной кривой плоскость может быть определена с помощью параметрического уравнения

${\ Displaystyle х = {\ гидроразрыва {P (t)} {R (t)}}, \ qquad y = {\ frac {Q (t)} {R (t)}},}$

где P , Q и R - многочлены. Неявное уравнение кривой дается

${\ displaystyle \ operatorname {res} _ {t} (xR-P, yR-Q).}$

Степень этой кривой является высокая степень P , Q и R , которая равна общей степени равнодействующей.

Символическая интеграция

В символической интеграции , для вычисления первообразных из более рациональной дроби , используется в частичном разложении дроби для разложения интеграла в «рациональную часть», которая представляет собой сумму рациональных дробей, antiprimitives рациональные дробей, и «логарифмической части» , которая является сумма рациональных дробей вида

${\ Displaystyle {\ гидроразрыва {P (x)} {Q (x)}},}$

где Q представляет собой бесквадратно полином и Р есть многочлен меньшей степени , чем Q . Первообразная такой функции обязательно включает логарифмы и, как правило, алгебраические числа (корни Q ). Фактически, первообразная

${\ displaystyle \ int {\ frac {P (x)} {Q (x)}} dx = \ sum _ {Q (\ alpha) = 0} {\ frac {P (\ alpha)} {Q '(\ альфа)}} \ log (x- \ alpha),}$

где сумма берется по всем комплексным корням Q .

Количество алгебраических чисел, задействованных в этом выражении, обычно равно степени Q , но часто бывает, что может быть вычислено выражение с меньшим количеством алгебраических чисел. Метод Лазара – Риобу – Трагера дал выражение, в котором количество алгебраических чисел минимально, без каких-либо вычислений с алгебраическими числами.

Позволять

${\ Displaystyle S_ {1} (r) S_ {2} (r) ^ {2} \ cdots S_ {k} (r) ^ {k} = \ operatorname {res} _ {r} (rQ '(x) -P (x), Q (x))}$

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

${\ displaystyle \ int {\ frac {P (x)} {Q (x)}} dx = \ sum _ {i = 1} ^ {k} \ sum _ {S_ {i} (\ alpha) = 0} \ alpha \ log (T_ {i} (\ alpha, x)),}$

где внутренние суммы пробегают корни (если сумма равна нуль, как являющиеся пустая сумма ), и есть многочлен степени я в х . Вклад Лазар-Rioboo является доказательством того, что это subresultant степени я из и он, таким образом , получается бесплатно, если в результате вычисляется по subresultant последовательности псевдо-остатка . ${\ displaystyle S_ {i}}$${\ displaystyle S_ {i} = 1}$${\ Displaystyle Т_ {я} (г, х)}$${\ Displaystyle Т_ {я} (г, х)}$${\ Displaystyle rQ '(х) -P (х)}$${\ displaystyle Q (x).}$

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

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

Однородный результирующий

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

${\ Displaystyle (А, В) \ mapsto AP + BQ,}$

где A пробегает двумерные однородные многочлены степени q - 1 , а B пробегает однородные многочлены степени p - 1 . Другими словами, однородный равнодействующий P и Q является равнодействующим P ( x , 1) и Q ( x , 1), когда они рассматриваются как многочлены степени p и q (их степень по x может быть ниже, чем их общая степень):

${\ Displaystyle \ OperatorName {Res} (P (x, y), Q (x, y)) = \ operatorname {res} _ {p, q} (P (x, 1), Q (x, 1)) .}$

(Для различения двух результирующих здесь используется заглавная буква «Res», хотя стандартного правила для заглавной буквы аббревиатуры не существует).

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

• Результат двух однородных многочленов над областью целостности равен нулю тогда и только тогда, когда они имеют ненулевой общий ноль над алгебраически замкнутым полем, содержащим коэффициенты.
• Если Р и Q две двумерный однородные многочленов с коэффициентами в коммутативном кольце R и кольцевой гомоморфизм из R в другой коммутативное кольце S , то расширение для многочленов над R , имеет те${\ Displaystyle \ varphi \ двоеточие R \ to S}$${\ displaystyle \ varphi}$

${\ displaystyle \ operatorname {Res} (\ varphi (P), \ varphi (Q)) = \ varphi (\ operatorname {Res} (P, Q)).}$

• Свойство однородного равнодействующего быть нулем инвариантно относительно любой проективной замены переменных.

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

Результирующая Маколея

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

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

Результат общих однородных многочленов

Однородный многочлен степени д в п переменных может иметь до

${\ displaystyle {\ binom {n + d-1} {n-1}} = {\ frac {(n + d-1)!} {(n-1)! \, d!}}}$

коэффициенты; он называется общим , если эти коэффициенты являются различными неопределенными.

Пусть есть n общих однородных многочленов от n неопределенных соответствующих степеней. Вместе они содержат ${\ Displaystyle P_ {1}, \ ldots, P_ {n}}$ ${\ displaystyle d_ {1}, \ dots, d_ {n}.}$

${\ Displaystyle \ сумма _ {я = 1} ^ {п} {\ binom {п + d_ {я} -1} {п-1}}}$

неопределенные коэффициенты. Пусть C - кольцо многочленов над целыми числами от всех этих неопределенных коэффициентов. Многочлены принадлежат , таким образом, и их результирующая ( по- прежнему должны быть определены) принадлежит C . ${\ Displaystyle P_ {1}, \ ldots, P_ {n}}$${\ Displaystyle С [x_ {1}, \ ldots, x_ {n}],}$

Степень Маколея - это целое число, лежащее в основе теории Маколея. Для определения полученного, каждый рассматривает матрицу Маколея , который является матрицей над мономиальной основой из C -линейной карты ${\ Displaystyle D = d_ {1} + \ cdots + d_ {n} -n + 1,}$

${\ Displaystyle (Q_ {1}, \ ldots, Q_ {n}) \ mapsto Q_ {1} P_ {1} + \ cdots + Q_ {n} P_ {n},}$

в котором каждый пробегает однородные многочлены степени и область значений является С - модуль однородных многочленов степени D . ${\ displaystyle Q_ {i}}$${\ displaystyle D-d_ {i},}$

Если n = 2 , матрица Маколея является матрицей Сильвестра и является квадратной матрицей , но это больше не верно для n > 2 . Таким образом, вместо того, чтобы рассматривать определитель, мы рассматриваем все максимальные миноры , то есть определители квадратных подматриц, которые имеют столько же строк, сколько матрица Маколея. Маколей доказал, что C -идеал, порожденный этими главными минорами, является главным идеалом , порожденным наибольшим общим делителем этих миноров. Поскольку мы работаем с многочленами с целыми коэффициентами, этот наибольший общий делитель определяется с точностью до знака. Родовые Маколи результирующий представляет наибольший общий делитель , который становится 1 , когда для каждого I , ноль заменяется на все коэффициенты , за исключением коэффициента , для которых один является замещенным. ${\ displaystyle P_ {i},}$${\ displaystyle x_ {i} ^ {d_ {i}},}$

Свойства обобщенного результирующего Маколея

• Результирующий элемент общего положения Маколея является неприводимым многочленом .
• Она однородна степени по коэффициентам, где - граница Безу .${\ displaystyle B / d_ {i}}$${\ displaystyle P_ {i},}$${\ displaystyle B = d_ {1} \ cdots d_ {n}}$
• Произведение с равнодействующей каждого монома степени D в принадлежит идеалу, порожденному${\ displaystyle x_ {1}, \ dots, x_ {n}}$${\ displaystyle C [x_ {1}, \ dots, x_ {n}]}$${\ displaystyle P_ {1}, \ dots, P_ {n}.}$

Результат многочленов над полем

С этого момента мы считаем, что однородные многочлены степеней имеют свои коэффициенты в поле k , то есть они принадлежат к их равнодействующей , определяемой как элемент k, полученный заменой неопределенных коэффициентов в общем результирующем на фактические коэффициенты в${\ Displaystyle P_ {1}, \ ldots, P_ {n}}$${\ displaystyle d_ {1}, \ ldots, d_ {n}}$ ${\ displaystyle k [x_ {1}, \ dots, x_ {n}].}$${\ displaystyle P_ {i}.}$

Основное свойство равнодействующей является то , что он равен нулю тогда и только тогда , когда есть ненулевая общий нуль в алгебраически замкнутым расширением по к . ${\ Displaystyle P_ {1}, \ ldots, P_ {n}}$

Часть этой теоремы «только если» является результатом последнего свойства предыдущего абзаца и является эффективной версией Projective Nullstellensatz : если результат не равен нулю, то

${\ Displaystyle \ langle x_ {1}, \ ldots, x_ {n} \ rangle ^ {D} \ substeq \ langle P_ {1}, \ ldots, P_ {n} \ rangle,}$

где - степень Маколея, - максимальный однородный идеал. Это означает, что нет другого общего нуля, кроме единственного общего нуля, (0, ..., 0) ,${\ Displaystyle D = d_ {1} + \ cdots + d_ {n} -n + 1}$${\ Displaystyle \ langle x_ {1}, \ ldots, x_ {n} \ rangle}$${\ Displaystyle P_ {1}, \ ldots, P_ {n}}$${\ displaystyle x_ {1}, \ ldots, x_ {n}.}$

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

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

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

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

В случае входных полиномов с коэффициентами в поле точное значение результирующего редко имеет значение, имеет значение только его равенство (или нет) нулю. Поскольку результат равен нулю, если и только если ранг матрицы Маколея ниже, чем количество ее строк, это равенство нулю может быть проверено путем применения исключения Гаусса к матрице Маколея. Это обеспечивает вычислительную сложность, где d - максимальная степень входных полиномов. ${\ Displaystyle d ^ {О (п)},}$

Другой случай, когда вычисление результата может предоставить полезную информацию, - это когда коэффициенты входных многочленов являются многочленами от небольшого числа неопределенных, часто называемых параметрами. В этом случае результат, если не ноль, определяет гиперповерхность в пространстве параметров. Точка принадлежит этой гиперповерхности тогда и только тогда, когда существуют значения, которые вместе с координатами точки являются нулем входных многочленов. Другими словами, результат является результатом « исключения » из входных полиномов. ${\ displaystyle x_ {1}, \ ldots, x_ {n}}$${\ displaystyle x_ {1}, \ ldots, x_ {n}}$

U -результат

Результат Маколея обеспечивает метод, названный Маколеем « U -результатом», для решения систем полиномиальных уравнений .

Учитывая , п - 1 однородных многочленов степеней в п неизвестных над полем к их U -resultant является результирующим из п полиномов где ${\ Displaystyle P_ {1}, \ ldots, P_ {n-1},}$${\ displaystyle d_ {1}, \ ldots, d_ {n-1},}$${\ displaystyle x_ {1}, \ ldots, x_ {n},}$${\ Displaystyle P_ {1}, \ ldots, P_ {n-1}, P_ {n},}$

${\ Displaystyle P_ {n} = u_ {1} x_ {1} + \ cdots + u_ {n} x_ {n}}$

является общей линейной формой , коэффициенты которой являются новыми неопределенными. Обозначение или для этих общих коэффициентов является традиционным, и является источником термина U -результант. ${\ displaystyle u_ {1}, \ ldots, u_ {n}.}$${\ displaystyle u_ {i}}$${\ displaystyle U_ {i}}$

U -resultant является однородным многочленом он равен нуль тогда и только тогда , когда общие нули образуют проективное алгебраическое множество положительной размерности (то есть, существует бесконечно много нулей проективных над алгебраически замкнутым расширением в к ). Если U -результант не равен нулю, его степень является границей Безу . U -результат факторизуется над алгебраически замкнутым расширением k в произведение линейных форм. Если такой линейный коэффициент, то являются однородными координатами от общего нуля Кроме того, каждый общий нуль может быть получен из одного из этих линейных факторов, а кратность как фактор равна кратность пересечения из при этом нулю. Другими словами, U -результант представляет собой полностью явную версию теоремы Безу . ${\ displaystyle k [u_ {1}, \ ldots, u_ {n}].}$${\ Displaystyle P_ {1}, \ ldots, P_ {n-1}}$ ${\ displaystyle d_ {1} \ cdots d_ {n-1}.}$${\ Displaystyle \ альфа _ {1} и_ {1} + \ ldots + \ альфа _ {п} и_ {п}}$${\ displaystyle \ alpha _ {1}, \ ldots, \ alpha _ {n}}$${\ displaystyle P_ {1}, \ ldots, P_ {n-1}.}$${\ displaystyle P_ {i}}$

Расширение на большее количество полиномов и вычислений

U -resultant как определено Маколей требует количество однородных полиномов в системе уравнений будет , где это число неизвестных. В 1981 году Дэниел Лазард расширил это понятие на случай, когда количество многочленов может отличаться от , а результирующее вычисление может быть выполнено с помощью специальной процедуры исключения Гаусса с последующим вычислением символического определителя . ${\ displaystyle n-1}$${\ displaystyle n}$${\ displaystyle n-1}$

Пусть - однородные многочлены от степеней над полем k . Без ограничения общности можно предположить, что Установка для i > k оценка Маколея имеет вид${\ Displaystyle P_ {1}, \ ldots, P_ {k}}$${\ displaystyle x_ {1}, \ ldots, x_ {n},}$${\ displaystyle d_ {1}, \ ldots, d_ {k},}$${\ displaystyle d_ {1} \ geq d_ {2} \ geq \ cdots \ geq d_ {k}.}$${\ displaystyle d_ {i} = 1}$${\ displaystyle D = d_ {1} + \ cdots + d_ {n} -n + 1.}$

Позвольте быть новым неопределенным и определить. В этом случае матрица Маколея определяется как матрица на основе одночленов линейного отображения ${\ Displaystyle и_ {1}, \ ldots, и_ {п}}$${\ displaystyle P_ {k + 1} = u_ {1} x_ {1} + \ cdots + u_ {n} x_ {n}.}$${\ displaystyle x_ {1}, \ ldots, x_ {n},}$

${\ Displaystyle (Q_ {1}, \ ldots, Q_ {k + 1}) \ mapsto P_ {1} Q_ {1} + \ cdots + P_ {k + 1} Q_ {k + 1},}$

где для каждого I , пробегает линейное пространство , состоящее из нуля и однородных многочлены степени . ${\ displaystyle Q_ {i}}$${\ displaystyle D-d_ {i}}$

Сокращая матрицу Маколея с помощью варианта исключения Гаусса , мы получаем квадратную матрицу линейных форм в . Определитель этой матрицы есть U -результат. Как и в оригинальной U -resultant, оно равно нулю тогда и только тогда , когда имеют бесконечно много общих проективных нулей (то есть , если проективное алгебраическое множество определяется имеет бесконечно много точек над алгебраическим замыканием на к ). Как и в случае с исходным U -результатом, когда этот U -результант не равен нулю, он разлагается на линейные множители по любому алгебраически замкнутому расширению k . Коэффициенты этих линейных множителей представляют собой однородные координаты общих нулей, а кратность общего нуля равна кратности соответствующего линейного множителя. ${\ displaystyle u_ {1}, \ ldots, u_ {n}.}$${\ Displaystyle P_ {1}, \ ldots, P_ {k}}$${\ Displaystyle P_ {1}, \ ldots, P_ {k}}$${\ Displaystyle P_ {1}, \ ldots, P_ {k},}$

Число строк матрицы Маколея меньше, чем где e ~ 2,7182 - обычная математическая константа , а d - среднее арифметическое степеней матрицы. Отсюда следует, что все решения системы полиномиальных уравнений с конечным числом проективных нулей может быть определена во времени. Хотя эта оценка велика, она почти оптимальна в следующем смысле: если все входные степени равны, то временная сложность процедуры полиномиальна от ожидаемого числа решений ( теорема Безу ). Это вычисление может быть практически жизнеспособным, когда n , k и d не велики. ${\ displaystyle (ed) ^ {n},}$${\ displaystyle P_ {i}.}$ ${\ displaystyle d ^ {O (n)}.}$

Смотрите также

• Теория исключения
• Субрезультант

Заметки

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

• Гельфанд И.М.; Капранов ММ; Зелевинский, А.В. (1994), Дискриминанты, результирующие и многомерные детерминанты , Бостон: Биркхойзер, ISBN. 978-0-8176-3660-9
• Macaulay, FS (1902), "Some Formul in Elimination" , Proc. Лондонская математика. Soc. , 35 : 3-27, DOI : 10.1112 / ПНИЛИ / s1-35.1.3
• Macaulay, FS (1916), Алгебраическая теория модульных систем , Корнельская библиотека исторических математических монографий, Cambridge University Press, ISBN 978-1275570412
• Салмон, Джордж (1885) [1859], Уроки, вводные в современную высшую алгебру (4-е изд.), Дублин, Ходжес, Фиггис и Ко, ISBN 978-0-8284-0150-0

Внешние ссылки

• Вайсштейн, Эрик В. «Результат» . MathWorld .