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

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

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

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

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

Обозначения

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

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

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

Определение

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

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

и

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

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

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

такой, что

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

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

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

$${\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, получим

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

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

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

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

Свойства

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

Характеризующие свойства

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

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

Нули

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

кольцевым

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

• Если $\varphi$ сохраняет степени A и B (то есть, если $\deg(\varphi (A))=d$ и $\deg(\varphi (B))=e$), затем
  $$\varphi (\operatorname {res} (A,B))=\operatorname {res} (\varphi (A),\varphi (B)).$$
• Если $\deg(\varphi (A))<d$ и $\deg(\varphi (B))<e,$ затем
  $$\varphi (\operatorname {res} (A,B))=0.$$
• Если $\deg(\varphi (A))=d$ и $\deg(\varphi (B))=f<e,$ а старший коэффициент A равен $a_{0}$ затем
  $$\varphi (\operatorname {res} (A,B))=\varphi (a_{0})^{e-f}\operatorname {res} (\varphi (A),\varphi (B)).$$
• Если $\deg(\varphi (A))=f<d$ и $\deg(\varphi (B))=e,$ а старший коэффициент B равен $b_{0}$ затем
  $$\varphi (\operatorname {res} (A,B))=(-1)^{e(d-f)}\varphi (b_{0})^{d-f}\operatorname {res} (\varphi (A),\varphi (B)).$$

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

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

• $\operatorname {res} (A(x+a),B(x+a))=\operatorname {res} (A(x),B(x))$
• $\operatorname {res} (A(ax),B(ax))=a^{de}\operatorname {res} (A(x),B(x))$
• Если $A_{r}(x)=x^{d}A(1/x)$ и $B_{r}(x)=x^{e}B(1/x)$ являются обратными полиномами A B и тогда соответственно,
  $$\operatorname {res} (A_{r},B_{r})=(-1)^{de}\operatorname {res} (A,B)$$

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

полиномов

• Если a и b — ненулевые константы (то есть они не зависят от неопределенного x ), а A и B такие же, как указано выше, то
  $$\operatorname {res} (aA,bB)=a^{e}b^{d}\operatorname {res} (A,B).$$
• Если A и B такие же, как указано выше, а C — другой полином, такой, что степень A – CB равна δ , то
  $$\operatorname {res} (B,A-CB)=b_{0}^{\delta -d}\operatorname {res} (B,A).$$
• В частности, если либо B является monic , либо deg C < deg A – deg B , то
  $$\operatorname {res} (B,A-CB)=\operatorname {res} (B,A),$$
  и если f = deg C > deg A – deg B = d – e , то
  $$\operatorname {res} (B,A-CB)=b_{0}^{e+f-d}\operatorname {res} (B,A).$$

Эти свойства подразумевают, что в алгоритме Евклида для полиномов и во всех его вариантах ( последовательностях псевдоостатков ) результирующая двух последовательных остатков (или псевдоостатков) отличается от результирующей исходных полиномов на фактор, который легко вычислить. . И наоборот, это позволяет вывести результирующую исходных полиномов из значения последнего остатка или псевдоостатка. Это стартовая идея алгоритма subresultant-pseudo-remainder-sequence , который использует приведенные выше формулы для получения субрезультирующих полиномов в качестве псевдоостатков, а результирующего — в качестве последнего ненулевого псевдоостатка (при условии, что результирующий не равен нулю). Этот алгоритм работает для полиномов целых чисел или, в более общем плане, для целой области без какого-либо деления, кроме точного деления (то есть без использования дробей). Это включает в себя $O(de)$ арифметических операций, тогда как вычисление определителя матрицы Сильвестра стандартными алгоритмами требует $O((d+e)^{3})$ арифметические операции.

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

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

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

и

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

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

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

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

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

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

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

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

Свойство ликвидации

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

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

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

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

Вычисление

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

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

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

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

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

к

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

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

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

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

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

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

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

Общий случай

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

$${\begin{aligned}P_{1}(x_{1},\ldots ,x_{n})&=0\\&\;\;\vdots \\P_{k}(x_{1},\ldots ,x_{n})&=0\end{aligned}}$$

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

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

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

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

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

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

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

Теория чисел

Дискриминант теории полинома, который является фундаментальным инструментом в чисел , равен $a_{0}^{-1}(-1)^{n(n-1)/2}\operatorname {res} _{x}(f(x),f'(x))$, где $a_{0}$ является ведущим коэффициентом $f(x)$ и $n$ его степень.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Позволять

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

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

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

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

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

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

Однородный результат

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

$$(A,B)\mapsto AP+BQ,$$

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

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

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

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

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

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

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

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

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

общих

Однородный полином степени d от n переменных может иметь до

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

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

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

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

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

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

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

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

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

общего

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

Результат полиномов по полю

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

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

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

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

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

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

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

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

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

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

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

U -результат

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

• Теория устранения
• Промежуточный результат
• Нелинейная алгебра

Ссылки

• Гельфанд, ИМ; Капранов М.М.; Зелевинский, А. В. (1994), Дискриминанты, результанты и многомерные детерминанты , Бостон: Birkhäuser, ISBN.  978-0-8176-3660-9
• Маколей, Ф.С. (1916), Алгебраическая теория модульных систем , Корнеллская библиотека исторических математических монографий, издательство Кембриджского университета, ISBN  978-1275570412

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

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