Наибольший общий делитель полинома

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален. Найти источники:  «Наибольший общий делитель полинома»  -  новости  · газеты  · книги  · ученый  · JSTOR ( сентябрь 2012 г. ) ( Узнайте, как и когда удалить это сообщение в шаблоне )

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

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

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

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

Общее определение [ править ]

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

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

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

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

${\displaystyle f=ud}$

и

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

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

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

Свойства [ править ]

• Как указано выше, НОД двух многочленов существует, если коэффициенты принадлежат либо полю, кольцу целых чисел, либо, в более общем смысле, уникальной области факторизации .
• Если c - любой общий делитель p и q , то c делит их НОД.
• ${\displaystyle \gcd(p,q)=\gcd(q,p).}$
• ${\displaystyle \gcd(p,q)=\gcd(q,p+rq)}$для любого полинома r . Это свойство лежит в основе доказательства алгоритма Евклида.
• Для любого обратимого элемента к кольцу коэффициентов, .${\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)}$
• Для двух одномерных многочленов p и q над полем существуют многочлены a и b , такие, что и делит каждую такую ​​линейную комбинацию p и q ( тождество Безу ).${\displaystyle \gcd(p,q)=ap+bq}$${\displaystyle \gcd(p,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. Алгоритм Евклида , который может быть использован для нахождения НОД двух многочленов таким же образом , как и для двух чисел.

Факторинг [ править ]

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

Пример один: Найти НОД х ² + 7 х + 6 и х ² - 5 х - 6 .

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

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

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

Евклидов алгоритм [ править ]

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

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

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

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

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

Многочлен g ( x ) делит как a ( x ), так и b ( x ) тогда и только тогда, когда он делит как b ( x ), так и r ₀ ( 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 ₁ ( x ), r ₁ ( x ), a ₂ ( x ), b ₂ ( x ) и так далее. На каждом этапе у нас есть

${\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 x + 12 - последний ненулевой остаток, это НОД исходных многочленов, а монический НОД равен x + 1 .

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

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

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

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

Евклидово деление [ править ]

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

${\displaystyle a=bq+r}$

и

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

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

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

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

Евклидово делениеВходные данные:  a и b ≠ 0 два многочлена от переменной x ;Выходные данные:  q - частное и r - остаток;Начните  q  : = 0  r  : = a  d  : = deg ( b )  c  : = lc ( b ),  а deg ( r ) ≥ d  do  s  : =lc ( r )/c x deg ( r ) - d  q  : = q + s  r  : = r - sb  end do  return ( q , r ) end

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

Алгоритм Евклида [ править ]

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

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

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

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

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

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

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

Личность Безу и расширенный алгоритм НОД [ править ]

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

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

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

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

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

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

Расширенный алгоритм GCDВвод:  a , b , одномерные многочлены.Выходные данные:  g , НОД a и b  u , v , как в приведенном выше заявлении  a 1 , b 1 , так что  Begin${\displaystyle {\begin{aligned}a=ga_{1}\\b=gb_{1}\end{aligned}}}$ ${\displaystyle {\begin{array}{ll}r_{0}=a&r_{1}=b\\s_{0}=1&s_{1}=0\\t_{0}=0&t_{1}=1\end{array}}}$  for ( i = 1 ; r i ≠ 0 ; i = i +1 ) do  end do end${\displaystyle q=\operatorname {quo} (r_{i-1},r_{i})}$ ${\displaystyle {\begin{aligned}r_{i+1}&=r_{i-1}-qr_{i}\\s_{i+1}&=s_{i-1}-qs_{i}\\t_{i+1}&=t_{i-1}-qt_{i}\end{aligned}}}$  ${\displaystyle {\begin{aligned}g&=r_{i-1}\\u&=s_{i-1}\\v&=t_{i-1}\end{aligned}}}$ ${\displaystyle {\begin{aligned}a_{1}&=(-1)^{i-1}t_{i}\\b_{1}&=(-1)^{i}s_{i}\end{aligned}}}$

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

${\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 _i и t _i увеличиваются не более чем по мере уменьшения степени r _i .

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

Арифметика алгебраических расширений [ править ]

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

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

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

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

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

${\displaystyle 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-м подрезультатным многочленом. ^[1]

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

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

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

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

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

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

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

и

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

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

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

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

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

Полученный из P и Q представляет собой определитель матрицы Сильвестра , который является (квадрат) матрицей на основаниях полномочий X . Точно так же i -подушечный многочлен определяется в терминах определителей подматриц матрицы${\displaystyle \varphi _{0}}$${\displaystyle \varphi _{i}.}$

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

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

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

Матрица Т _я из является ( т + п - я ) × ( т + п - 2 я ) -подматрица S , который получает путь удаления последней я строка нулей в подматрице из колонн 1 до п - я и от n + 1 до m + n - i из S (то есть удаляются i столбцов в каждом блоке и i последних строк нулей). Главный субрезультатный коэффициент s _i${\displaystyle \varphi _{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 ⁱ , X ⁱ⁻¹ , ..., X , 1:

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

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

Набросок доказательства [ править ]

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

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

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

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

НОД и поиск корней [ править ]

Факторизация без квадратов [ править ]

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

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

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

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

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

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

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

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

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

${\displaystyle 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 ] как кольца многочленов от множества переменных над этими кольцами.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

и

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

Связь между НОД по R и над F [ править ]

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

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

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

Если p ₁ и p ₂ принадлежат R [ X ], то

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

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

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

и

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

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

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

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

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

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

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

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

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

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

${\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 [ X ]) входных многочленов. Таким образом, остаточная псевдо-последовательность позволяет вычисления НОДА - й в Q [ X ] без введения фракций в 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.}$

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

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

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

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

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

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

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

${\displaystyle 4663\,X-6150,}$

${\displaystyle 1.}$

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

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

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

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

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

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

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

${\displaystyle 9326\,X-12300,}$

${\displaystyle 260708.}$

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

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

${\displaystyle {\begin{aligned}r_{0}:=a\\r_{1}:=b\end{aligned}}}$для (;;) делать${\displaystyle i:=1}$${\displaystyle r_{i}\neq 0}$${\displaystyle i:=i+1;}$  , если потом ещеконецесли конец сделать.${\displaystyle {\begin{aligned}d_{i}&:=\deg(r_{i-1})-\deg(r_{i})\\\gamma _{i}&:=\operatorname {lc} (r_{i})\end{aligned}}}$  ${\displaystyle i=1}$  ${\displaystyle {\begin{aligned}\beta _{1}&:=(-1)^{d_{1}+1}\\\psi _{1}&:=-1\end{aligned}}}$  ${\displaystyle {\begin{aligned}\beta _{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})}{\beta _{i}}}}$

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

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

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

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

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

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

где | lc ( B ) | является абсолютным значением ведущего коэффициента B (коэффициента X ^b ).

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

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

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

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

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

Предположим , , и . Если взять, то - конечное кольцо (не поле, поскольку не является максимальным по ). Алгоритм Евклида, примененный к изображениям in, завершается успешно и возвращает 1. Это означает, что НОД для in также должен быть 1. Следует отметить , что этот пример может легко быть обработан любым способом , потому что степени были слишком малы для выражения набухает произойти, но это показывает , что , если два полинома имеет НОД 1, то модульный алгоритм может прекратить действие после одного идеала .${\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]}$${\displaystyle f,g}$${\displaystyle F[x]}$${\displaystyle I}$

См. Также [ править ]

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

Ссылки [ править ]

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