Полиномиальный наибольший общий делитель

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

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

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

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

Общее определение

Пусть p и q — полиномы с коэффициентами в области целостности F , обычно это поле или целые числа. Наибольший общий делитель p и q — это многочлен d , который делит p и q , и такой, что каждый общий делитель p и q также делит d . Каждая пара полиномов (не оба равны нулю) имеет НОД тогда и только тогда, когда F — уникальная область факторизации .

Если F — поле и p и q не равны нулю, многочлен d является наибольшим общим делителем тогда и только тогда, когда он делит оба p и q , и он имеет наибольшую степень среди многочленов, обладающих этим свойством. Если p = q = 0 , НОД равен 0. Однако некоторые авторы считают, что в этом случае он не определен.

Наибольший общий делитель p и q обычно обозначается « НОД( p , q ) ».

Наибольший общий делитель не уникален: если d — НОД чисел p и q , то многочлен f является другим НОД тогда и только тогда, когда существует обратимый элемент u из F такой, что

$$f=ud$$

и

$$d=u^{-1}f.$$

Другими словами, НОД уникален с точностью до умножения на обратимую константу.

В случае целых чисел эта неопределенность устраняется путем выбора в качестве НОД единственного положительного числа (есть еще одно, противоположное ему). Согласно этому соглашению, НОД двух целых чисел также является наибольшим (для обычного порядка) общим делителем. Однако, поскольку для многочленов в области целочисленности не существует естественного полного порядка , здесь нельзя действовать таким же образом. Для одномерных многочленов над полем можно дополнительно потребовать, чтобы НОД был унитарным (то есть имел 1 в качестве коэффициента высшей степени), но в более общих случаях общего соглашения не существует. Следовательно, равенства типа d = НОД( p , q ) или НОД( p , q ) = НОД( r , s ) являются частым злоупотреблением обозначениями, которые следует читать « d — НОД чисел p и q » и « p и q». имеют тот же набор НОД, что и r и s ". В частности, НОД( p , q ) = 1 означает, что обратимые константы являются единственными общими делителями. В этом случае по аналогии с целочисленным случаем говорят, что p и q равны взаимно простые полиномы .

Свойства

• Как указано выше, НОД двух многочленов существует, если коэффициенты принадлежат либо полю, кольцу целых чисел, либо, в более общем смысле, уникальной области факторизации .
• Если c — любой общий делитель p и q , то c делит их НОД.
• $\gcd(p,q)=\gcd(q,p).$
• $\gcd(p,q)=\gcd(q,p+rq)$ для любого полинома r . Это свойство лежит в основе доказательства алгоритма Евклида.
• Для любого обратимого элемента k кольца коэффициентов $\gcd(p,q)=\gcd(p,kq)$.
• Следовательно $\gcd(p,q)=\gcd(a_{1}p+b_{1}q,a_{2}p+b_{2}q)$ для любых скаляров $a_{1},b_{1},a_{2},b_{2}$ такой, что $a_{1}b_{2}-a_{2}b_{1}$ является обратимым.
• Если $\gcd(p,r)=1$, затем $\gcd(p,q)=\gcd(p,qr)$.
• Если $\gcd(q,r)=1$, затем $\gcd(p,qr)=\gcd(p,q)\,\gcd(p,r)$.
• Для двух одномерных многочленов p и q над полем существуют многочлены a и b такие, что $\gcd(p,q)=ap+bq$ и $\gcd(p,q)$ делит каждую такую ​​линейную комбинацию p и q ( тождество Безу ).
• Наибольший общий делитель трех и более многочленов можно определить так же, как и для двух многочленов. Его можно вычислить рекурсивно из НОД двух полиномов с помощью тождеств:
  $$\gcd(p,q,r)=\gcd(p,\gcd(q,r)),$$
  и
  $$\gcd(p_{1},p_{2},\dots ,p_{n})=\gcd(p_{1},\gcd(p_{2},\dots ,p_{n})).$$

НОД вручную вычисление

Существует несколько способов найти наибольший общий делитель двух многочленов. Два из них:

1. Факторизация полиномов , при которой находят факторы каждого выражения, затем выбирают набор общих факторов, принадлежащих всем, из каждого набора факторов. Этот метод может быть полезен только в простых случаях, поскольку факторизация обычно сложнее, чем вычисление наибольшего общего делителя.
2. Алгоритм Евклида , который можно использовать для нахождения НОД двух многочленов так же, как и для двух чисел.

Факторинг

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

Пример первый. Найдите НОД числа x. ² + 7 х + 6 и х ² - 5 Икс - 6 .

х ² + 7 х + 6 = ( х + 1)( х + 6)

х ² - 5 х - 6 = ( х + 1)( х - 6)

Таким образом, их НОД равен x + 1 .

Алгоритм Евклида

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

Более конкретно, для нахождения НОД двух многочленов a ( x ) и b ( x ) можно предположить b ≠ 0 (в противном случае НОД равен a ( x ) ), и

$$\deg(b(x))\leq \deg(a(x))\,.$$

Евклидово деление дает два многочлена q ( x ) — частное и r ( x ) , — остаток такие, что

$$a(x)=q_{0}(x)b(x)+r_{0}(x)\quad {\text{and}}\quad \deg(r_{0}(x))<\deg(b(x))$$

Многочлен g ( x ) делит и ( x ) , и b ( x ) тогда и только тогда, когда он делит и b ( x ) , и r0 _a ( x ) . Таким образом

$$\gcd(a(x),b(x))=\gcd(b(x),r_{0}(x)).$$

Параметр

$$a_{1}(x)=b(x),b_{1}(x)=r_{0}(x),$$

можно повторить евклидово деление, чтобы получить новые многочлены q ₁ ( x ), r ₁ ( x ), a ₂ ( x ), b ₂ ( x ) и так далее. На каждом этапе мы имеем

$$\deg(a_{k+1})+\deg(b_{k+1})<\deg(a_{k})+\deg(b_{k}),$$

поэтому последовательность в конечном итоге достигнет точки, в которой

$$b_{N}(x)=0$$

и у одного есть НОД:

$$\gcd(a,b)=\gcd(a_{1},b_{1})=\cdots =\gcd(a_{N},0)=a_{N}.$$

Пример: нахождение НОД числа x ² + 7 х + 6 и х ² − 5 х − 6 :

х ² + 7 х + 6 = 1 ⋅ ( х ² − 5 х − 6) + (12 х + 12)

х ² − 5 х − 6 = (12 х + 12) ( 1/12 ​ ​ х - 1 / 2 ) + 0

Поскольку 12 x + 12 — это последний ненулевой остаток, это НОД исходных многочленов, а монический НОД — это x + 1 .

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

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

Одномерные полиномы с коэффициентами в поле

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

Евклидово деление

Евклидово деление многочленов, которое используется в алгоритме Евклида для вычисления НОД, очень похоже на евклидово деление целых чисел. Его существование основано на следующей теореме: для двух одномерных многочленов a и b ≠ 0, определенных над полем, существуют два многочлена q ( частное ) и r ( остаток ), которые удовлетворяют

$$a=bq+r$$

и

$$\deg(r)<\deg(b),$$

где " deg(...) " обозначает степень, а степень нулевого многочлена определяется как отрицательная. Более того, q и r однозначно определяются этими соотношениями.

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

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

Euclidean division

Input: a and b ≠ 0 two polynomials in the variable x;
Output: q, the quotient, and r, the remainder;

begin
    q := 0
    r := a
    d := deg(b)
    c := lc(b)
    while deg(r) ≥ d do
        s := (lc(r)/c) ⋅ xdeg(r)−d
        q := q + s
        r := r − sb
    end do
    return (q, r)
end

Доказательство правильности этого алгоритма основано на том факте, что на протяжении всего цикла «пока» мы имеем a = bq + r и deg( r ) — неотрицательное целое число, которое уменьшается на каждой итерации. Таким образом, доказательство справедливости этого алгоритма также доказывает справедливость евклидова деления.

Алгоритм Евклида

Что касается целых чисел, евклидово деление позволяет нам определить алгоритм Евклида для вычисления НОД.

Начиная с двух многочленов a и b , алгоритм Евклида состоит из рекурсивной замены пары ( a , b ) на ( b , rem( a , b )) (где « rem( a , b ) » обозначает остаток евклидова деления, вычисляется по алгоритму предыдущего раздела), пока b = 0. НОД — это последний ненулевой остаток.

Алгоритм Евклида можно формализовать в стиле рекурсивного программирования следующим образом:

$$\gcd(a,b):={\begin{cases}a&{\text{if }}b=0\\\gcd(b,\operatorname {rem} (a,b))&{\text{otherwise}}.\end{cases}}$$

В императивном стиле программирования делается тот же алгоритм, дающий имя каждому промежуточному остатку:

r0 := a
r1 := b

for (i := 1; ri ≤ 0; i := i + 1) do
    ri+1 := rem(ri−1, ri)
end do

return ri-1.

Последовательность степеней r _i строго убывающая. Таким образом, после не более чем deg( b ) можно получить нулевой остаток, скажем rk _. шагов Поскольку ( a , b ) и ( b , rem( a , b )) делители, набор общих делителей не изменяется алгоритмом Евклида и, таким образом, все пары ( ri _, имеют ri _{одинаковые +1} ) имеют одинаковые множество общих делителей. Таким образом, общие делители a и b являются общими делителями rk _{− 1} и 0. Таким образом, rk _{− 1} является НОД a и b . Это не только доказывает, что алгоритм Евклида вычисляет НОД, но и доказывает, что НОД существуют.

Личность Безу и

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

Если g — наибольший общий делитель двух многочленов a и b (не обоих нулевых), то существуют два многочлена u и v такие, что

$au+bv=g$   (личность Безу)

и либо u = 1, v = 0 , либо u = 0, v = 1 , либо

$$\deg(u)<\deg(b)-\deg(g),\quad \deg(v)<\deg(a)-\deg(g).$$

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

Extended GCD algorithm

Input: a, b, univariate polynomials

Output:
    g, the GCD of a and b
    u, v, as in above statement
    a1, b1, such that
        a = g a1
        b = g b1
Begin
    (r0, r1) := (a, b)
    (s0, s1) := (1, 0)
    (t0, t1) := (0, 1)
  
    for (i := 1; ri ≠ 0; i := i+1) do
        q := quo(ri−1, ri)
        ri+1 := ri−1 − qri
        si+1 := si−1 − qsi
        ti+1 := ti−1 − qti
    end do
    g := ri−1
    u := si−1
    v := ti−1
    a1 := (−1)i−1 ti
    b1 := (−1)i ti
End

Доказательство того, что алгоритм удовлетворяет своей выходной спецификации, основано на том факте, что для каждого i имеем

$$r_{i}=as_{i}+bt_{i}$$

$$s_{i}t_{i+1}-t_{i}s_{i+1}=s_{i}t_{i-1}-t_{i}s_{i-1},$$

последнее равенство подразумевает

$$s_{i}t_{i+1}-t_{i}s_{i+1}=(-1)^{i}.$$

Утверждение о степенях следует из того, что на каждой итерации степени s _i и ti _{увеличиваются} степени ri _{не более чем по мере уменьшения} .

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

Арифметика алгебраических расширений

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

Пусть L — алгебраическое расширение поля K , порожденное элементом, минимальный многочлен f которого имеет степень n . Элементы L обычно представляются одномерными полиномами над K степени меньше n .

Сложение в L — это просто сложение полиномов:

$$a+_{L}b=a+_{K[X]}b.$$

Умножение в L — это умножение многочленов с последующим делением на f :

$$a\cdot _{L}b=\operatorname {rem} (a._{K[X]}b,f).$$

Обратным к ненулевому элементу a из L является коэффициент u в тождестве Безу au + fv = 1 , который можно вычислить с помощью расширенного алгоритма НОД. (НОД равен 1, поскольку минимальный многочлен f неприводим). Неравенство степеней в спецификации расширенного алгоритма НОД показывает, что дальнейшее деление на f не требуется, чтобы получить deg( u ) < deg( f ).

Промежуточные результаты

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

Теория подрезультатов является обобщением этого свойства, которое позволяет в общем случае охарактеризовать НОД двух полиномов, а результирующим является 0-й подрезультатный полином.

подрезультатный i -й многочлен S _i ( P , Q ) двух многочленов P и Q — это многочлен степени не выше i, коэффициенты которого являются полиномиальными функциями коэффициентов P и Q , а i -й главный подрезультатный коэффициент s _i ( P , Q ) коэффициент i S i ₍ ) P , Q . степени Они обладают тем свойством, что НОД P и Q имеет степень d тогда и только тогда, когда

$$s_{0}(P,Q)=\cdots =s_{d-1}(P,Q)=0\ ,s_{d}(P,Q)\neq 0.$$

В этом случае S _d ( P , Q ) является НОД P и Q и

$$S_{0}(P,Q)=\cdots =S_{d-1}(P,Q)=0.$$

коэффициент промежуточных полиномов определяется как определитель подматрицы матрицы Сильвестра P Каждый и Q . Это означает, что промежуточные результаты хорошо «специализируются». Точнее, промежуточные результаты определены для полиномов над любым коммутативным кольцом R и обладают следующим свойством.

Пусть φ кольцевой гомоморфизм кольца R в другое коммутативное кольцо S. — Он продолжается до другого гомоморфизма, обозначаемого также φ, между кольцами полиномов над R и S . Тогда, если P и Q — одномерные многочлены с коэффициентами из R такие, что

$$\deg(P)=\deg(\varphi (P))$$

и

$$\deg(Q)=\deg(\varphi (Q)),$$

тогда промежуточные полиномы и главные промежуточные коэффициенты φ ( P ) и φ ( Q ) являются образом φ полиномов P и Q .

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

Техническое определение

Позволять

$$P=p_{0}+p_{1}X+\cdots +p_{m}X^{m},\quad Q=q_{0}+q_{1}X+\cdots +q_{n}X^{n}.$$

два одномерных многочлена с коэффициентами в поле K. — Обозначим через ${\mathcal {P}}_{i}$ векторное пространство K размерности i полиномов степени меньше i . Для неотрицательного целого числа i такого, что i ≤ m и i ≤ n , пусть

$$\varphi _{i}:{\mathcal {P}}_{n-i}\times {\mathcal {P}}_{m-i}\rightarrow {\mathcal {P}}_{m+n-i}$$

— линейное отображение такое, что

$$\varphi _{i}(A,B)=AP+BQ.$$

Результат и P , которая является является Q определителем матрицы Сильвестра (квадратной) матрицей $\varphi _{0}$ на основе степеней X . Аналогично, i -подрезультирующий полином определяется через определители подматриц матрицы $\varphi _{i}.$

Опишем эти матрицы более точно;

Пусть p _i = 0 для i < 0 или i > m , и q _i = 0 для i < 0 или i > n . Матрица Сильвестра — это ( m + n ) × ( m + n ) -матрица такая, что коэффициент i -й строки и j -го столбца pm _{равен + j - i} для j ≤ n и q _{j - i} для j > n :

$$S={\begin{pmatrix}p_{m}&0&\cdots &0&q_{n}&0&\cdots &0\\p_{m-1}&p_{m}&\cdots &0&q_{n-1}&q_{n}&\cdots &0\\p_{m-2}&p_{m-1}&\ddots &0&q_{n-2}&q_{n-1}&\ddots &0\\\vdots &\vdots &\ddots &p_{m}&\vdots &\vdots &\ddots &q_{n}\\\vdots &\vdots &\cdots &p_{m-1}&\vdots &\vdots &\cdots &q_{n-1}\\p_{0}&p_{1}&\cdots &\vdots &q_{0}&q_{1}&\cdots &\vdots \\0&p_{0}&\ddots &\vdots &0&q_{0}&\ddots &\vdots \\\vdots &\vdots &\ddots &p_{1}&\vdots &\vdots &\ddots &q_{1}\\0&0&\cdots &p_{0}&0&0&\cdots &q_{0}\end{pmatrix}}.$$

Матрица T _i ​ $\varphi _{i}$ — это ( m + n − i ) × ( m + n − 2 i ) -подматрица матрицы S , полученная удалением последних i строк нулей в подматрице столбцов от 1 до n − i и от n + 1 до m. + n − i из S (то есть удаление i столбцов в каждом блоке и i последних строк нулей). Главный промежуточный коэффициент s _i является определителем m + n − 2 i первых строк таблицы T _i .

Пусть V _{i —} матрица ( m + n - 2 i ) × ( m + n - i ) , определенная следующим образом. Сначала мы добавляем ( i + 1) столбцов нулей справа от ( m + n − 2 i − 1) × ( m + n − 2 i − 1) единичной матрицы . Затем мы ограничиваем нижнюю часть полученной матрицы строкой, состоящей из ( m + n − i − 1) нулей, за которыми следует X ^я , Х ^{я -1} , ..., Х , 1 :

$$V_{i}={\begin{pmatrix}1&0&\cdots &0&0&0&\cdots &0\\0&1&\cdots &0&0&0&\cdots &0\\\vdots &\vdots &\ddots &\vdots &\vdots &\ddots &\vdots &0\\0&0&\cdots &1&0&0&\cdots &0\\0&0&\cdots &0&X^{i}&X^{i-1}&\cdots &1\end{pmatrix}}.$$

При таких обозначениях i - й промежуточный полином является определителем матричного произведения V _i T _i . Ее коэффициент степени j является определителем квадратной подматрицы T _i, состоящей из ее m + n - 2 i - 1 первых строк и ( m + n - i - j ) -й строки.

доказательства

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

Согласно определению, столбцы матрицы T _i представляют собой векторы коэффициентов некоторых полиномов, принадлежащих образу $\varphi _{i}$. Определение i -го промежуточного многочлена S _i что вектор его коэффициентов представляет собой линейную комбинацию этих вектор-столбцов и, таким образом, что Si _{показывает ,} принадлежит образу $\varphi _{i}.$

Если степень НОД больше i , то тождество Безу показывает, что каждый ненулевой многочлен в образе $\varphi _{i}$ имеет степень выше, чем я . Это означает, что S _i = 0 .

Если, с другой стороны, степень НОД равна i , то тождество Безу снова позволяет доказать, что кратные НОД, имеющие степень ниже m + n − i, находятся в образе $\varphi _{i}$. Векторное пространство этих кратных имеет размерность m + n − 2 i и имеет базу из полиномов попарно разных степеней, не меньших i . Это означает, что подматрица m + n − 2 i первых строк формы эшелона столбцов T _i является единичной матрицей и, следовательно, s _i не равна 0. Таким образом, S _i является многочленом в образе $\varphi _{i}$, которое кратно НОД и имеет ту же степень. Таким образом, это наибольший общий делитель.

НОД и поиск корня

Бесквадратная факторизация

Основная статья: Бесквадратная факторизация

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

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

$$f=\prod _{i=1}^{\deg(f)}f_{i}^{i}$$

где для каждого i многочлен f _i либо равен 1, если f не имеет корня кратности i , либо является многочленом без квадратов (то есть многочленом без кратного корня), корни которого в точности являются корнями кратности i из f (см. алгоритм Юна ).

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

Последовательность штурма

Основная статья: Последовательность Штурма

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

$$r_{i+1}:=\operatorname {rem} (r_{i-1},r_{i})$$

алгоритма Евклида

$$r_{i+1}:=-\operatorname {rem} (r_{i-1},r_{i}).$$

Пусть V ( a ) — количество смен знаков в последовательности при оценке в точке a . Теорема Штурма утверждает, что V ( a ) − V ( b ) — это количество действительных корней многочлена в интервале [ a , b ] . Таким образом, последовательность Штурма позволяет вычислить количество вещественных корней в заданном интервале. Разделив интервал до тех пор, пока каждый подинтервал не будет содержать не более одного корня, это обеспечивает алгоритм, который находит действительные корни в интервалах произвольно малой длины.

НОД над кольцом и его полем дробей

В этом разделе мы рассматриваем полиномы над уникальной областью факторизации R , обычно кольцом целых чисел, и над его полем частных F , обычно полем рациональных чисел, и мы обозначаем R [ X ] и F [ X ] кольца многочленов от множества переменных над этими кольцами.

Примитивная факторизация частей и содержания

См. Также: Содержание (алгебра) и лемма Гаусса (многочлен).

Содержимое p многочлена p ∈ R [ X ] , обозначаемое « cont( ) » , является НОД его коэффициентов. Многочлен q ∈ F [ X ] можно записать

$$q={\frac {p}{c}}$$

где p ∈ R [ X ] и c ∈ R : достаточно взять в качестве c кратное всем знаменателям коэффициентов q (например, их произведение) и p = cq . Содержимое определяется q : как

$$\operatorname {cont} (q)={\frac {\operatorname {cont} (p)}{c}}.$$

В обоих случаях содержание определяется с точностью до единицу R. на умножения

Примитивная часть многочлена в R [ X ] или F [ X ] определяется формулой

$$\operatorname {primpart} (p)={\frac {p}{\operatorname {cont} (p)}}.$$

В обоих случаях это полином из R [ X ], который является примитивным , что означает, что 1 является НОД его коэффициентов.

Таким образом, каждый многочлен из R [ X ] или F [ X ] может быть факторизован как

$$p=\operatorname {cont} (p)\,\operatorname {primpart} (p),$$

и эта факторизация уникальна с точностью до умножения содержания на единицу R и примитивной части на обратную эту единицу.

Лемма Гаусса подразумевает, что произведение двух примитивных многочленов примитивно. Отсюда следует, что

$$\operatorname {primpart} (pq)=\operatorname {primpart} (p)\operatorname {primpart} (q)$$

и

$$\operatorname {cont} (pq)=\operatorname {cont} (p)\operatorname {cont} (q).$$

Связь между НОД над R и над F

Соотношения предыдущего раздела подразумевают сильную связь между НОД в R [ X ] и в F [ X ] . Чтобы избежать двусмысленности, обозначение « НОД » в дальнейшем будет индексироваться по кольцу, в котором вычисляется НОД.

Если q1 _​ и q2 _, принадлежат F [ X ] то

$$\operatorname {primpart} (\gcd _{F[X]}(q_{1},q_{2}))=\gcd _{R[X]}(\operatorname {primpart} (q_{1}),\operatorname {primpart} (q_{2})).$$

Если p1 _​ и p2 _X принадлежат R [ ] , то

$$\gcd _{R[X]}(p_{1},p_{2})=\gcd _{R}(\operatorname {cont} (p_{1}),\operatorname {cont} (p_{2}))\gcd _{R[X]}(\operatorname {primpart} (p_{1}),\operatorname {primpart} (p_{2})),$$

и

$$\gcd _{R[X]}(\operatorname {primpart} (p_{1}),\operatorname {primpart} (p_{2}))=\operatorname {primpart} (\gcd _{F[X]}(p_{1},p_{2})).$$

Таким образом, вычисление полиномиальных НОД — это, по сути, одна и та же проблема над F [ X ] и над R [ X ] .

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

Доказательство существования НОД

В предыдущем разделе мы видели, что НОД полиномов в R [ X ] можно вывести из НОД в R и в F [ X ] . Более пристальный взгляд на доказательство показывает, что это позволяет нам доказать существование НОД в R [ X ] , если они существуют в R и в F [ X ] . В частности, если НОД существуют в R и если X сводится к одной переменной, это доказывает, что НОД существуют в R [ X ] (алгоритм Евклида доказывает существование НОД в F [ X ] ).

Полином от n переменных можно рассматривать как одномерный многочлен над кольцом многочленов от ( n - 1 ) переменных. Таким образом, рекурсия по числу переменных показывает, что если НОД существуют и могут быть вычислены в , то они существуют и могут быть вычислены в каждом кольце многомерных полиномов над R. R В частности, если R — либо кольцо целых чисел, либо поле, то НОД существуют в R [ x ₁ , ..., x _n ] , и то, что предшествует, предоставляет алгоритм для их вычисления.

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

Последовательности псевдоостатков

В этом разделе мы рассматриваем область целостности Z (обычно кольцо Z целых чисел) и ее поле частных Q (обычно поле Q рациональных чисел). Учитывая два многочлена A и B в кольце одномерных многочленов Z [ X ] , евклидово деление (над Q ) A на B дает частное и остаток, которые могут не принадлежать Z [ X ] .

Ибо, если применить алгоритм Евклида к следующим полиномам

$$X^{8}+X^{6}-3X^{4}-3X^{3}+8X^{2}+2X-5$$

и

$$3X^{6}+5X^{4}-4X^{2}-9X+21,$$

последовательные остатки алгоритма Евклида равны

$${\begin{aligned}&-{\tfrac {5}{9}}X^{4}+{\tfrac {1}{9}}X^{2}-{\tfrac {1}{3}},\\&-{\tfrac {117}{25}}X^{2}-9X+{\tfrac {441}{25}},\\&{\tfrac {233150}{19773}}X-{\tfrac {102500}{6591}},\\&-{\tfrac {1288744821}{543589225}}.\end{aligned}}$$

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

The псевдоделение было введено, чтобы разрешить вариант алгоритма Евклида, для которого все остатки принадлежат Z [ X ] .

Если $\deg(A)=a$ и $\deg(B)=b$ и a ≥ b псевдоостаток , от псевдо деления A на B , обозначаемый prem( A , B ) равен

$$\operatorname {prem} (A,B)=\operatorname {rem} (\operatorname {lc} (B)^{a-b+1}A,B),$$

где lc( B ) — старший коэффициент B (коэффициент X ^б ).

Псевдоостаток от псевдоделения двух многочленов из Z [ X ] всегда принадлежит Z [ X ] .

Последовательность псевдоостатков — это последовательность (псевдо)остатков r _i, полученная заменой инструкции

$$r_{i+1}:=\operatorname {rem} (r_{i-1},r_{i})$$

алгоритма Евклида

$$r_{i+1}:={\frac {\operatorname {prem} (r_{i-1},r_{i})}{\alpha }},$$

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

Поскольку общие делители двух многочленов не изменяются, если многочлены умножаются на обратимые константы (в Q ), последний ненулевой член в последовательности псевдоостатка является НОД (в Q [ X ] ) входных многочленов. Следовательно, последовательности псевдоостатков позволяют вычислять НОД в Q [ X ] без введения дробей в Q .

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

Тривиальная последовательность псевдоостатков

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

$$-15\,X^{4}+3\,X^{2}-9,$$

$$15795\,X^{2}+30375\,X-59535,$$

$$1254542875143750\,X-1654608338437500,$$

$$12593338795500743100931141992187500.$$

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

Примитивная последовательность псевдоостатков

Примитивная последовательность псевдоостатка состоит в том, что в качестве α принимается содержимое числителя. Таким образом, все r _i являются примитивными полиномами.

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

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

$$-5\,X^{4}+X^{2}-3,$$

$$13\,X^{2}+25\,X-49,$$

$$4663\,X-6150,$$

$$1.$$

Небольшой размер коэффициентов скрывает тот факт, что было вычислено количество целых чисел НОД и делений на НОД.

Подрезультативная последовательность псевдоостатка

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

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

При тех же входных данных, что и в предыдущих разделах, последовательные остатки

$$15\,X^{4}-3\,X^{2}+9,$$

$$65\,X^{2}+125\,X-245,$$

$$9326\,X-12300,$$

$$260708.$$

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

Алгоритм вычисления промежуточной последовательности с псевдоостатками приведен ниже. В этом алгоритме входные данные ( a , b ) представляют собой пару полиномов от Z [ X ] . r — _i это последовательные псевдоостатки в Z [ X ] , переменные i и d _i неотрицательные целые числа, а греческие буквы обозначают элементы в Z. — Функции deg() и rem() обозначают степень многочлена и остаток евклидова деления. В алгоритме этот остаток всегда находится в Z [ X ] . деления, обозначаемые /, всегда точны и дают результат либо в Z [ X ], либо в Z. Наконец ,

r0 := a
r1 := b
for (i := 1; ri ≠ 0; i := i+1) do
    di := deg(ri−1) − deg(ri)
    γi := lc(ri)
    if i = 1 then
        β1 := (−1)d1+1
        ψ1 := −1
    else
        ψi := (−γi−1)di−1 / ψi−1di−1−1
        βi := −γi−1ψidi
    end if
    ri+1 := rem(γidi+1 ri−1, ri) / βi
end for

Примечание: «lc» обозначает ведущий коэффициент, коэффициент высшей степени переменной.

Этот алгоритм вычисляет не только наибольший общий делитель (последний ненулевой r _i ), но и все промежуточные полиномы: остаток r _i представляет собой (deg( r _{i −1} ) − 1) -й промежуточный полином. Если deg( r _i ) < deg( r _{i −1} ) − 1 , deg( r _i ) -й промежуточный многочлен равен lc( r _i ) ^{ты( р _{я -1} )-deg( р _я )-1} р _я . Все остальные промежуточные полиномы равны нулю.

Последовательность Штурма с псевдоостатками

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

Если $\deg(A)=a$ и $\deg(B)=b$ и a ≥ b модифицированный псевдоостаток prem2( A , B ) псевдоделения A на B равен

$$\operatorname {prem2} (A,B)=-\operatorname {rem} (\left|\operatorname {lc} (B)\right|^{a-b+1}A,B),$$

где | ЖК( Б ) | – абсолютное значение старшего коэффициента B (коэффициент X ^б ).

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

Обратите внимание, что алгоритм вычисления промежуточной последовательности псевдоостатка, приведенный выше, будет вычислять неправильные промежуточные полиномы, если использовать $-\mathrm {prem2} (A,B)$ вместо $\operatorname {prem} (A,B)$.

Модульный алгоритм НОД

Если f и g являются полиномами от F [ x ] для некоторого конечно порожденного поля F , алгоритм Евклида является наиболее естественным способом вычисления их НОД. Однако современные системы компьютерной алгебры используют его только в том случае, если F конечно из-за явления, называемого увеличением промежуточного выражения . Хотя степени продолжают уменьшаться во время работы алгоритма Евклида, если F не конечно , то разрядность полиномов может увеличиваться (иногда резко) во время вычислений, поскольку повторяющиеся арифметические операции в F имеют тенденцию приводить к более крупным выражениям. Например, сложение двух рациональных чисел, знаменатели которых ограничены b, приводит к рациональному числу, знаменатель которого ограничен b. ² , поэтому в худшем случае размер бита может почти удвоиться всего за одну операцию.

Чтобы ускорить вычисление, возьмем кольцо D, для которого f и g находятся в D [ x ] , и возьмем идеал I такой, что D / I — конечное кольцо. Затем вычислите НОД над этим конечным кольцом с помощью алгоритма Евклида. Используя методы реконструкции ( китайская теорема об остатках , рациональная реконструкция можно восстановить НОД функции f и g по ее образу по модулю числа идеалов I. и т. д.) , Можно доказать что это работает при условии, что мы отбрасываем модульные изображения с неминимальными степенями и избегаем идеалов I по модулю, у которых старший коэффициент равен нулю.

Предполагать $F=\mathbb {Q} ({\sqrt {3}})$, $D=\mathbb {Z} [{\sqrt {3}}]$, $f={\sqrt {3}}x^{3}-5x^{2}+4x+9$ и $g=x^{4}+4x^{2}+3{\sqrt {3}}x-6$. Если мы возьмем $I=(2)$ затем $D/I$ является конечным кольцом (не полем, поскольку $I$ не является максимальным в $D$). Алгоритм Евклида, примененный к изображениям $f,g$ в $(D/I)[x]$ завершается успешно и возвращает 1. Это означает, что НОД $f,g$ в $F[x]$ тоже должно быть 1. Обратите внимание, что этот пример можно легко обработать любым методом, поскольку степени были слишком малы для возникновения раздутия выражения, но он иллюстрирует, что если два многочлена имеют НОД 1, то модульный алгоритм, скорее всего, завершится после достижения единственного идеала. $I$.

См. также

• Список полиномиальных тем
• Алгоритм многомерного деления

Ссылки

Библиография

• Басу, Саугата; Поллак, Ричард; Рой, Мари-Франсуаза (2006). Алгоритмы реальной алгебраической геометрии, глава 4.2 . Спрингер-Верлаг .
• Давенпорт, Джеймс Х .; Сирет, Ивон; Турнье, Эвелин (1988). Компьютерная алгебра: системы и алгоритмы алгебраических вычислений . Перевод с французского А. Давенпорта и Дж. Х. Давенпорта. Академическая пресса. ISBN  978-0-12-204230-0 .
• ван Хой, М.; Монаган, МБ (2004). Алгоритмы вычисления полиномиального НОД над полями алгебраических функций . ISSAC 2004. стр. 297–304.
• Джавади, СММ; Монаган, МБ (2007). Разреженный модульный алгоритм НОД для полиномов над полями алгебраических функций . ISSAC 2007. стр. 187–194.
• Кнут, Дональд Э. (1969). Искусство компьютерного программирования II . Аддисон-Уэсли. стр. 370–371.
• Кнут, Дональд Э. (1997). Получисловые алгоритмы . Искусство компьютерного программирования. Том. 2 (Третье изд.). Ридинг, Массачусетс: Аддисон-Уэсли. стр. 439–461, 678–691. ISBN  0-201-89684-2 .
• Лоос, Рюдигер (1982), «Обобщенные полиномиальные остаточные последовательности», у Б. Бухбергера; Р. Лоос; Дж. Коллинз (ред.), Компьютерная алгебра , Springer Verlag