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

Математическая концепция в теории полиномов

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

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

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

Обозначения

Результат двух одномерных полиномов 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}}$$

deпространствосвободный модульii ${\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 + eСильвестра ABМатрица Сильвестра

Таким образом, результирующая 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}},}$$

ea _idb _jabd = ed = 3e = 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}),}$$

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

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

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

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

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

• Если R является подкольцом другого кольца S , то То есть A и B имеют один и тот же результат, если рассматривать их как полиномы над 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.}$

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

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

• Если сохраняет степени A и B (то есть если и ), то ${\displaystyle \varphi }$ ${\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.}$$
• Если и и старший коэффициент A равен тогда ${\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)).}$$
• Если и и старший коэффициент B равен тогда ${\displaystyle \deg(\varphi (A))=f<d}$ ${\displaystyle \deg(\varphi (B))=e,}$ ${\displaystyle b_{0}}$
  $${\displaystyle \varphi (\operatorname {res} (A,B))=(-1)^{e(d-f)}\varphi (b_{0})^{d-f}\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))}$
• Если и являются обратными полиномами A и B соответственно, то ${\displaystyle A_{r}(x)=x^{d}A(1/x)}$ ${\displaystyle B_{r}(x)=x^{e}B(1/x)}$
  $${\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} (B,A-CB)=b_{0}^{\delta -d}\operatorname {res} (B,A).}$$
• В частности, если либо B является monic , либо deg C < deg A – deg B , то
  $${\displaystyle \operatorname {res} (B,A-CB)=\operatorname {res} (B,A),}$$
  и если f = deg C > deg A – deg B = d – e , то
  $${\displaystyle \operatorname {res} (B,A-CB)=b_{0}^{e+f-d}\operatorname {res} (B,A).}$$

Эти свойства подразумевают, что в алгоритме Евклида для полиномов и во всех его вариантах ( последовательностях псевдоостатков ) результирующая двух последовательных остатков (или псевдоостатков) отличается от результирующей исходных полиномов на фактор, который легко вычислить. . И наоборот, это позволяет вывести результирующую исходных полиномов из значения последнего остатка или псевдоостатка. Это исходная идея алгоритма subresultant-pseudo-remainder-sequence , который использует приведенные выше формулы для получения субрезультирующих полиномов в качестве псевдоостатков, а результирующего — в качестве последнего ненулевого псевдоостатка (при условии, что результирующий не равен нулю). Этот алгоритм работает для полиномов целых чисел или, в более общем плане, для целой области без какого-либо деления, кроме точного деления (то есть без использования дробей). Он включает в себя арифметические операции, тогда как вычисление определителя матрицы Сильвестра стандартными алгоритмами требует арифметических операций. ${\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 + e +2неопределенными

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

общим результатомde ${\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)}$

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

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

• Он однороден степени e по ${\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[x],}$ ${\displaystyle R=k[y_{1},\ldots ,y_{n}]}$

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

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

Поскольку по крайней мере один из A и B является моническим, кортеж из n является нулем тогда и только тогда, когда существует такой, который является общим нулем 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})}$ ${\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 O(n^{3})}$

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

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

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

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

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

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

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

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

PQполных степеней dexв общем случаеdexRалгебраически замкнутом полеPQ ${\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}$ ${\displaystyle x=\alpha }$

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

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

Общий случай

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

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

${\displaystyle (P_{i},P_{j})}$ ${\displaystyle x_{n}}$

Метод, предложенный в конце XIX века, работает следующим образом: вводят 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 a_{0}^{-1}(-1)^{n(n-1)/2}\operatorname {res} _{x}(f(x),f'(x))}$ ${\displaystyle a_{0}}$ ${\displaystyle f(x)}$ ${\displaystyle 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 .}$

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

Учитывая две плоские алгебраические кривые , определенные как нули полиномов P ( x , y ) и Q ( x , y ) , результат позволяет вычислить их пересечение. Точнее, корнями являются x -координаты точек пересечения и общих вертикальных асимптот, а корнями являются y -координаты точек пересечения и общих горизонтальных асимптот. ${\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)}},}$$

PQRуравнение

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

кривойPQR

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

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

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

Qмногочлен без квадратовPQ. логарифмыQ

$${\displaystyle \int {\frac {P(x)}{Q(x)}}dx=\sum _{Q(\alpha )=0}{\frac {P(\alpha )}{Q'(\alpha )}}\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)),}$$

пустая суммаixпромежуточным результатомiпромежуточной последовательности псевдоостатков ${\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).}$

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

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

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

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

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

Aq − 1Bp − 1PQP ( x , 1)Q ( x , 1)pqx

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

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

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

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

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

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

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

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

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

$${\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 \sum _{i=1}^{n}{\binom {n+d_{i}-1}{n-1}}}$$

CC ${\displaystyle P_{1},\ldots ,P_{n}}$ ${\displaystyle C[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},}$$

ко-областьCD ${\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 , полученный заменой в общем результате неопределенных коэффициентов действительными коэффициентами поля k. тот ${\displaystyle P_{1},\ldots ,P_{n}}$ ${\displaystyle d_{1},\ldots ,d_{n}}$ ${\displaystyle k[x_{1},\dots ,x_{n}].}$ ${\displaystyle P_{i}.}$

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

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

$${\displaystyle \langle x_{1},\ldots ,x_{n}\rangle ^{D}\subseteq \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^{O(n)},}$

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

U -результат

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

Учитывая n - 1 однородных многочленов степеней от n неопределенных над полем k , их U -результат является результатом n многочленов , где ${\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 -результат является однородным многочленом в Он равен нулю тогда и только тогда, когда общие нули образуют проективное алгебраическое множество положительной размерности (т. е. существует бесконечно много проективных нулей над алгебраически замкнутым расширением k ) . Если 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 \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 -результат, как это определено Маколеем, требует , чтобы количество однородных многочленов в системе уравнений было , где - количество неопределенных. В 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 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},}$$

i ${\displaystyle Q_{i}}$ ${\displaystyle D-d_{i}}$

Сокращая матрицу Маколея вариантом исключения Гаусса , получаем квадратную матрицу линейных форм в. Определителем этой матрицы является U -результат. Как и в случае с исходным U -результатом, он равен нулю тогда и только тогда, когда имеет бесконечно много общих проективных нулей (то есть, если проективное алгебраическое множество, определенное как, имеет бесконечно много точек над алгебраическим замыканием k ). Опять же, как и в случае с исходным 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},}$

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

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

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

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

1. Салмон, Джордж (1885) [1859], Вводные уроки в современную высшую алгебру (4-е изд.), Дублин, Ходжес, Фиггис и компания, урок VIII, стр. 66, ISBN 978-0-8284-0150-0
2. Маколей, FS (1902), «Некоторые формулы устранения», Proc. Лондонская математика. Соц. , 35 : 3–27, doi : 10.1112/plms/s1-35.1.3
3. Кокс, Дэвид; Литтл, Джон; О'Ши, Донал (2005), Использование алгебраической геометрии , Springer Science + Business Media , ISBN 978-0387207339, Глава 3. Результирующие

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

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

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