Наибольший общий делитель полинома - Polynomial greatest common divisor

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

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

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

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

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

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

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

Наибольший общий делитель п и q обычно обозначается "gcd (п, q)".

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

${displaystyle f=ud}$

и

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

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

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

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

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

${displaystyle gcd(p,q,r)=gcd(p,gcd(q,r)),}$

и

${displaystyle gcd(p_{1},p_{2},dots ,p_{n})=gcd(p_{1},gcd(p_{2},dots ,p_{n})).}$

НОД вручную

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

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

Факторинг

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

Пример 1: найти НОД Икс² + 7Икс + 6 и Икс² − 5Икс − 6.

Икс² + 7Икс + 6 = (Икс + 1)(Икс + 6)

Икс² − 5Икс − 6 = (Икс + 1)(Икс − 6)

Таким образом, их НОД Икс + 1.

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

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

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

${displaystyle deg(b(x))leq deg(a(x)),.}$

Евклидово деление дает два полинома q(Икс), то частное и р(Икс), то остаток такой, что

${displaystyle a(x)=q_{0}(x)b(x)+r_{0}(x)qquad { ext{and}}qquad deg(r_{0}(x))<deg(b(x))}$

Полином грамм(Икс) разделяет оба а(Икс) и б(Икс) тогда и только тогда, когда он делит оба б(Икс) и р₀(Икс). Таким образом

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

Параметр

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

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

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

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

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

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

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

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

Икс² + 7Икс + 6 = 1 ⋅ (Икс² − 5Икс − 6) + (12 Икс + 12)

Икс² − 5Икс − 6 = (12 Икс + 12) (1/12 Икс − 1/2) + 0

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

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

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

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

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

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

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

${displaystyle a=bq+r}$

и

${displaystyle deg(r)<deg(b),}$

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

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

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

Евклидово делениеВход: а и б ≠ 0 два многочлена от переменной Икс;Выход: q, частное и р, остаток;Начинать    q := 0    р := а    d : = град (б)    c : = lc (б)    пока град (р) ≥ d делать        s := lc (р)/c Иксград (р)−d        q := q + s        р := р − сб    конец делать    возвращаться (q, р)конец

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

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

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

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

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

${displaystyle gcd(a,b):={ ext{if }}b=0{ ext{ then }}a{ ext{ else }}gcd(b,operatorname {rem} (a,b)).}$

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

${displaystyle {egin{aligned}r_{0}:=a _{1}:=bend{aligned}}}$за (${displaystyle i:=1}$; ${displaystyle r_{i}eq 0}$; ${displaystyle i:=i+1}$) делать    ${displaystyle {egin{aligned}r_{i+1}&:=operatorname {rem} (r_{i-1},r_{i})end{aligned}}}$конец делатьвозвращаться ${displaystyle (r_{i-1}).}$

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

Идентичность Безу и расширенный алгоритм НОД

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

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

${displaystyle au+bv=gquad }$ (Личность Безу)

и либо ты = 1, v = 0, или же ты = 0, v = 1, или же

${displaystyle deg(u)<deg(b)-deg(g),quad deg(v)<deg(a)-deg(g).}$

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

Расширенный НОД алгоритмВход: а, б, одномерные многочленыВыход:    грамм, НОД а и б    ты, v, как в заявлении выше а1, б1, так что ${displaystyle {egin{aligned}a=ga_{1}=gb_{1}end{aligned}}}$Начинать    ${displaystyle {egin{array}{ll}r_{0}=a&r_{1}=bs_{0}=1&s_{1}=0 _{0}=0&t_{1}=1end{array}}}$      за (я = 1; ря ≠ 0; я = я+1) делать        ${displaystyle q=operatorname {quo} (r_{i-1},r_{i})}$        ${displaystyle {egin{aligned}r_{i+1}&=r_{i-1}-qr_{i}s_{i+1}&=s_{i-1}-qs_{i} _{i+1}&=t_{i-1}-qt_{i}end{aligned}}}$    конец делать    ${displaystyle {egin{aligned}g&=r_{i-1}u&=s_{i-1}v&=t_{i-1}end{aligned}}}$    ${displaystyle {egin{aligned}a_{1}&=(-1)^{i-1}t_{i}_{1}&=(-1)^{i}s_{i}end{aligned}}}$конец

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

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

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

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

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

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

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

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

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

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

Добавление в L это просто сложение многочленов:

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

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

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

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

Субрезультанты

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

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

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

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

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

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

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

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

${displaystyle deg(P)=deg(varphi (P))}$

и

${displaystyle deg(Q)=deg(varphi (Q)),}$

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

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

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

Позволять

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

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

${displaystyle varphi _{i}:{mathcal {P}}_{n-i} imes {mathcal {P}}_{m-i}ightarrow {mathcal {P}}_{m+n-i}}$

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

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

В результирующий из п и Q является определителем Матрица Сильвестра, которая представляет собой (квадратную) матрицу ${displaystyle varphi _{0}}$ на основании полномочий Икс. Точно так же я-подрезультатный полином определяется через определители подматриц матрицы ${displaystyle varphi _{i}.}$

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

Позволять п_я = 0 для я <0 или я > м, и q_я = 0 для я <0 или я > п. В Матрица Сильвестра это (м + п) × (м + п) -матрица такая, что коэффициент при я-й ряд и j-й столбец п_м+j−я за j ≤ п и q_j−я за j > п:^[2]

${displaystyle S={egin{pmatrix}p_{m}&0&cdots &0&q_{n}&0&cdots &0p_{m-1}&p_{m}&cdots &0&q_{n-1}&q_{n}&cdots &0p_{m-2}&p_{m-1}&ddots &0&q_{n-2}&q_{n-1}&ddots &0vdots &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 �&p_{0}&ddots &vdots &0&q_{0}&ddots &vdots &vdots &vdots &ddots &p_{1}&vdots &vdots &ddots &q_{1}�&0&cdots &p_{0}&0&0&cdots &q_{0}end{pmatrix}}.}$

Матрица Т_я из ${displaystyle varphi _{i}}$ это (м + п − я) × (м + п − 2я) -подматрица S который получается удалением последнего я строки нулей в подматрице столбцов с 1 по п − я и п +1 к м + п − я из S (это удаление я столбцы в каждом блоке и я последние строки нулей). В главный промежуточный коэффициент s_я является определителем м + п − 2я первые ряды Т_я.

Позволять V_я быть (м + п − 2я) × (м + п − я) матрица определяется следующим образом. Сначала добавляем (я + 1) столбцы нулей справа от (м + п − 2я − 1) × (м + п − 2я − 1) единичная матрица. Затем ограничиваем нижнюю часть получившейся матрицы строкой, состоящей из (м + п − я - 1) нули с последующими Икс^я, Икс^я−1, ..., Икс, 1:

${displaystyle V_{i}={egin{pmatrix}1&0&cdots &0&0&0&cdots &0�&1&cdots &0&0&0&cdots &0vdots &vdots &ddots &vdots &vdots &ddots &vdots &0�&0&cdots &1&0&0&cdots &0�&0&cdots &0&X^{i}&X^{i-1}&cdots &1end{pmatrix}}.}$

В этих обозначениях я-го подрезультант полином - определитель матричного произведения V_яТ_я. Его коэффициент степени j - определитель квадратной подматрицы матрицы Т_я состоящий из м + п − 2я - 1 первые ряды и (м + п − я − j)-бросать.

Набросок доказательства

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

Как определено, столбцы матрицы Т_я - векторы коэффициентов некоторых многочленов, принадлежащих образу ${displaystyle varphi _{i}}$. Определение я-й подрезультатный многочлен S_я показывает, что вектор его коэффициентов представляет собой линейную комбинацию этих векторов-столбцов, и, таким образом, что S_я принадлежит имиджу ${displaystyle varphi _{i}.}$

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

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

НОД и поиск корней

Факторизация без квадратов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Смотрите также: Содержание (алгебра) и Лемма Гаусса (полином)

В содержание полинома п ∈ р[Икс], обозначается "cont (п) ", является НОД его коэффициентов. Полином q ∈ F[Икс] может быть написано

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

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

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

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

В примитивная часть полинома от р[Икс] или же F[Икс] определяется

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

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

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

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

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

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

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

и

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

Связь между НОД по р и более F

Отношения предыдущего раздела подразумевают сильную связь между НОД в р[Икс] И в F[Икс]. Во избежание двусмысленности обозначение "gcd"будут проиндексированы в дальнейшем кольцом, в котором вычисляется НОД.

Если q₁ и q₂ принадлежать F[Икс], тогда

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

Если п₁ и п₂ принадлежать р[Икс], тогда

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

и

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

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

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

Доказательство существования НОД для многомерных многочленов

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

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

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

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

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

Ведь если применить алгоритм Евклида к следующим многочленам ^[3]

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

и

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

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

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

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

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

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

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

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

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

А псевдоостаточная последовательность - последовательность (псевдо) остатков р_я получается заменой по инструкции

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

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

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

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

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

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

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

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

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

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

${displaystyle 1254542875143750,X-1654608338437500,}$

${displaystyle 12593338795500743100931141992187500.}$

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

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

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

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

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

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

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

${displaystyle 4663,X-6150,}$

${displaystyle 1.}$

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

Субрезультант псевдоостаточной последовательности

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

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

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

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

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

${displaystyle 9326,X-12300,}$

${displaystyle 260708.}$

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

Алгоритм вычисления подрезультатной последовательности с псевдоостаточными остатками приведен ниже. В этом алгоритме вход (а, б) является парой многочленов от Z[ИКС]. В р_я последовательные псевдоостаточные числа в Z[X], переменные я и d_я неотрицательные целые числа, а греческие буквы обозначают элементы в Z. Функции град () и rem () обозначают степень полинома и остаток от евклидова деления. В алгоритме этот остаток всегда находится в Z[ИКС]. Наконец, деления, обозначенные /, всегда точны и имеют результат либо в Z[X] или в Z.

${displaystyle {egin{aligned}r_{0}:=a _{1}:=bend{aligned}}}$за (${displaystyle i:=1}$; ${displaystyle r_{i}eq 0}$; ${displaystyle i:=i+1;}$) делать    ${displaystyle {egin{aligned}d_{i}&:=deg(r_{i-1})-deg(r_{i})gamma _{i}&:=operatorname {lc} (r_{i})end{aligned}}}$    если ${displaystyle i=1}$ тогда        ${displaystyle {egin{aligned}eta _{1}&:=(-1)^{d_{1}+1}psi _{1}&:=-1end{aligned}}}$    еще        ${displaystyle {egin{aligned}eta _{i}&:=-gamma _{i-1}psi _{i}^{d_{i}}psi _{i}&:={frac {(-gamma _{i-1})^{d_{i-1}}}{psi _{i-1}^{d_{i-1}-1}}}end{aligned}}}$    конец, если    ${displaystyle r_{i+1}:={frac {operatorname {rem} (gamma _{i}^{d_{i}+1}r_{i-1},r_{i})}{eta _{i}}}}$конец делать.

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

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

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

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

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

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

где | lc (B) | - модуль старшего коэффициента B (коэффициент Икс^б).

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

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

Модульный алгоритм GCD

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

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

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

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

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

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

1. Басу, Поллак и Рой 2006
2. Многие авторы определяют матрицу Сильвестра как транспонирование S. Это нарушает обычное соглашение о написании матрицы линейной карты.
3. Кнут 1969
4. ван Хойдж и Монаган 2004

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