Результирующий - Resultant

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

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

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

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

Обозначение

Результирующая двух одномерных многочленов А и 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 и е соответственно. Обозначим через ${\displaystyle {\mathcal {P}}_{i}}$ в векторное пространство (или же бесплатный модуль если коэффициенты принадлежат коммутативному кольцу) размерности я элементы которого суть многочлены степени строго меньше, чем я. Карта

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

такой, что

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

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

Результат А и 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}},}$

у которого есть е столбцы а_я и d столбцы б_j (тот факт, что первый столбец аи первый столбец бодинаковой длины, то есть d = е, здесь только для упрощения отображения определителя) .Например, взяв d = 3 и е = 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}),}$

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

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

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

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

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

• Если р это подкольцо другого кольца S, тогда ${\displaystyle \operatorname {res} _{R}(A,B)=\operatorname {res} _{S}(A,B).}$ То есть А и B имеют тот же результат, когда рассматриваются как многочлены от р или же S.
• Если d = 0 (это если ${\displaystyle A=a_{0}}$ ненулевая константа), то ${\displaystyle \operatorname {res} (A,B)=a_{0}^{e}.}$ Аналогично, если е = 0, тогда ${\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)}$

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

Нули

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

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

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

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

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

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

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

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

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

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

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

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

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

• ${\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 A_{r}(x)=x^{d}A(1/x)}$ и ${\displaystyle B_{r}(x)=x^{e}B(1/x)}$ являются обратные многочлены из А и Bсоответственно, то

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

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

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

• Если а и б ненулевые константы (т. е. не зависят от неопределенного Икс), и А и B такие же, как указано выше, тогда

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

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

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

• В частности, если B является моник, или же град C <град А - град B, тогда

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

и если ж = град C > град А - град B = d – е, тогда

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

Эти свойства означают, что в Евклидов алгоритм для многочленов, и все его варианты (псевдоостаточные последовательности ), равнодействующая двух последовательных остатков (или псевдоостаточных остатков) отличается от равнодействующей исходных многочленов множителем, который легко вычислить. Наоборот, это позволяет вывести результат исходных многочленов из значения последнего остатка или псевдо-остатка. Это исходная идея подрезультат-алгоритм псевдо-остаточной последовательности, который использует приведенные выше формулы для получения подрезультатные полиномы как псевдоостаточный остаток, а результирующий как последний ненулевой псевдоостаточный остаток (при условии, что результат не равен нулю). Этот алгоритм работает для многочленов от целых чисел или, в более общем смысле, от области целостности без какого-либо деления, кроме точного (то есть без использования дробей). Это включает в себя ${\displaystyle O(de)}$ арифметические операции, в то время как вычисление определителя матрицы Сильвестра стандартными алгоритмами требует ${\displaystyle O((d+e)^{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}}$

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

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

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

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

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

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

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

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

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

• ${\displaystyle \operatorname {res} _{x}(A,B)\in I\cap R}$
• Идеалы ${\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.}$

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

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

Вычисление

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

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

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

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

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

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

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

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

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

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

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

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

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

Общий случай

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

${\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 \alpha _{1},\ldots ,\alpha _{n-1}}$ является общим нулем этих полиномиальных коэффициентов тогда и только тогда, когда одномерные многочлены ${\displaystyle P_{i}(\alpha _{1},\ldots ,\alpha _{n-1},x_{n})}$ иметь общий ноль, возможно в бесконечности. Этот процесс может повторяться до тех пор, пока не будут найдены одномерные многочлены.

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

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

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

Теория чисел

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

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

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

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

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

А рациональная плоская кривая может быть определен параметрическое уравнение

${\displaystyle x={\frac {P(t)}{R(t)}},\qquad y={\frac {Q(t)}{R(t)}},}$

куда п, Q и р являются многочленами. An неявное уравнение кривой задается

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

В степень этой кривой - высшая степень п, Q и р, равная полной степени результирующей.

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

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

${\displaystyle {\frac {P(x)}{Q(x)}},}$

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

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

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

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

Позволять

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

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

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

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

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

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

${\displaystyle (A,B)\mapsto AP+BQ,}$

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

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

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

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

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

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

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

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

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

Результирующая Маколея, названный в честь Фрэнсис Соуэрби Маколей, также называемый многомерный результат, или мультиполиномиальный результат,^[3] является обобщением однородной равнодействующей на п однородные многочлены в п неопределенный. Результат Маколея является полиномом от коэффициентов этих п однородных многочленов, который обращается в нуль тогда и только тогда, когда многочлены имеют общее ненулевое решение в алгебраически замкнутое поле содержащие коэффициенты, или, что то же самое, если п гиперповерхности, определяемые полиномами, имеют общий нуль в п –1 мерное проективное пространство. Многомерный результирующий с Базы Грёбнера, один из основных инструментов эффективного теория исключения (теория исключения на компьютерах).

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

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

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

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

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

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

${\displaystyle \sum _{i=1}^{n}{\binom {n+d_{i}-1}{n-1}}}$

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

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

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

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

Если п = 2, матрица Маколея является матрицей Сильвестра и является квадратная матрица, но это уже не так для п > 2. Таким образом, вместо того, чтобы рассматривать определитель, учитываются все максимальные несовершеннолетние, то есть определители квадратных подматриц, которые имеют столько же строк, сколько матрица Маколея. Маколей доказал, что C-идеалом, порожденным этими главными минорами, является главный идеал, который порождается наибольший общий делитель этих несовершеннолетних. При работе с многочленами с целыми коэффициентами этот наибольший общий делитель определяется по его знаку. В общий результат Маколея является наибольшим общим делителем, который становится 1, когда для каждого я, ноль заменяется на все коэффициенты ${\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}.}$

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

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

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

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

${\displaystyle \langle x_{1},\ldots ,x_{n}\rangle ^{D}\subseteq \langle P_{1},\ldots ,P_{n}\rangle ,}$

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

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

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

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

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

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

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

U-результат

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

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

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

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

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

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

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

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

Позволять ${\displaystyle u_{1},\ldots ,u_{n}}$ быть новыми независимыми и определять ${\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},}$

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

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

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

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

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

Примечания

1. Лосось 1885, урок VIII, с. 66.
2. Маколей 1902.
3. Кокс, Дэвид; Литтл, Джон; О'Ши, Донал (2005), Использование алгебраической геометрии, Springer Science + Business Media, ISBN  978-0387207339, Глава 3. Результаты

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

• Гельфанд, И. М .; Капранов, М.М .; Зелевинский, А. (1994), Дискриминанты, результирующие и многомерные детерминанты, Бостон: Birkhäuser, ISBN  978-0-8176-3660-9
• Маколей, Ф.С. (1902), «Некоторая формула в устранении», Proc. Лондонская математика. Soc., 35: 3–27, Дои:10.1112 / плмс / с1-35.1.3
• Маколей, Ф.С. (1916), Алгебраическая теория модульных систем, Корнельская библиотека историко-математических монографий, издательство Кембриджского университета, ISBN  978-1275570412
• Лосось, Джордж (1885) [1859], Уроки, вводные в современную высшую алгебру (4-е изд.), Дублин, Ходжес, Фиггис и Ко, ISBN  978-0-8284-0150-0

внешняя ссылка

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