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

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

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

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

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

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

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

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

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

Наибольший общий делитель не является единственным: если $d$ является НОД $p$ и $q$ , то многочлен $f$ является другим НОД тогда и только тогда, когда существует обратимый элемент $u$ из $F,$ такой что и Другими словами, НОД является единственным с точностью до умножения на обратимую константу. $f=ud$ $d=u^{-1}ф.$

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

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

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

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

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

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

Факторинг

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

Пример первый: Найдите НОД чисел $x 2 + 7 x + 6$ и $x 2 - 5 x - 6$ .

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

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

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

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

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

Более конкретно, для нахождения НОД двух многочленов $a (x)$ и $b (x)$ можно предположить, что $b \neq 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)$ делит как $a (x),$ так и $b (x)$ тогда и только тогда, когда он делит как $b (x)$ , так и $r 0 (x)$ . Таким образом, установив, можно повторить евклидово деление, чтобы получить новые многочлены $q$ $1$ $($ $x$ $),$ $r$ $1$ $($ $x$ $),$ $a$ $2$ $($ $x$ $),$ $b$ $2$ $($ $x$ $)$ и так далее. На каждом этапе мы имеем так что последовательность в конечном итоге достигнет точки, в которой и мы получим НОД: $\gcd(a(x),b(x))=\gcd(b(x),r_{0}(x)).$ $a_{1}(x)=b(x),b_{1}(x)=r_{0}(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 2 + 7 x + 6$ и $x 2 - 5 x - 6$ :

х 2 + 7 х + 6 = 1 \cdot (х 2 - 5 х - 6) + (12 х + 12)

х 2 − 5 х − 6 = (12 х + 12) (.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px} ⁠1/12⁠ х − ⁠1/2⁠ ) ​​+ 0

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

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

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

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

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

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

Евклидово деление многочленов, которое используется в алгоритме Евклида для вычисления НОД, очень похоже на евклидово деление целых чисел. Его существование основано на следующей теореме: даны два одномерных многочлена a и b ≠ 0, определенных над полем, существуют два многочлена q ( частное ) и r ( остаток ), которые удовлетворяют и где " $deg(...)$ " обозначает степень, а степень нулевого многочлена определяется как отрицательная. Более того, q и r однозначно определяются этими соотношениями. $a=bq+r$ $\deg(r)<\deg(b),$

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

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

Евклидово делениеВход:  a и b ≠ 0 два полинома от переменной x ; Выход:  q , частное, и r , остаток;begin  q  := 0  r  := a  d  := deg( b )  c  := lc( b )  while 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. НОД — это последний ненулевой остаток.

Алгоритм Евклида можно формализовать в стиле рекурсивного программирования следующим образом: $\gcd(a,b):={\begin{cases}a&{\text{if }}b=0\\\gcd(b,\operatorname {rem} (a,b))&{\text{otherwise}}.\end{cases}}$

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

г ₀  := а г ₁  := бдля ( i  := 1; r _i ≤ 0; i  := i + 1) сделать  r _{i +1}  := rem( r _{i −1} , r _i ) конец сделатьвернуть  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

такие, что

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$ . Этот алгоритм отличается от алгоритма Евклида несколькими дополнительными вычислениями, выполняемыми на каждой итерации цикла. Поэтому он называется расширенным алгоритмом НОД . Другое отличие от алгоритма Евклида заключается в том, что он также использует частное, обозначаемое «кво», евклидова деления вместо только остатка. Этот алгоритм работает следующим образом.

Расширенный алгоритм НОДВходные данные:  a , b , одномерные многочленыВыходные данные:  g , НОД a и b  u , v , как в приведенном выше утверждении  a ₁ , b ₁ , такое, что  a = g  a ₁ b = g  b ₁Begin ( r ₀ , r ₁ ) := ( a , b ) ( с ₀ , с ₁ ) := (1, 0) ( т0 , т1 ) := (0, ₁₎  для ( i  := 1; r _i ≠ 0; i  := i +1) сделать  q  := quo( r _{i −1} , r _i )  r _{i +1}  := r _{i −1} − qr _i  s _{i +1}  := s _{i −1} − qs _i  t _{i +1}  := t _{i −1} − qt _i конец сделать  g  := r _{i −1} u  := s _{i −1} v  := t _{i −1} a ₁  := (−1)^{i −1} t _i  b ₁  := (−1)ⁱ  t _iКонец

Доказательство того, что алгоритм удовлетворяет своей выходной спецификации, основано на том факте, что для каждого $i$ мы имеем последнее равенство, подразумевающее Утверждение о степенях следует из того факта, что на каждой итерации степени $s$ $i$ и $t$ $i$ увеличиваются максимум по мере уменьшения степени $r$ $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}.$

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

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

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

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

$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,$ такие что и тогда подрезультантные многочлены и главные подрезультантные коэффициенты $φ$ $($ $P$ $)$ и $φ$ $($ $Q$ $)$ являются образом $φ$ тех же многочленов $P$ и $Q$ . $\deg(P)=\deg(\varphi (P))$ $\deg(Q)=\deg(\varphi (Q)),$

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

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

Пусть будут два одномерных многочлена с коэффициентами в поле K. Обозначим через K $векторное$ пространство размерности $i$ многочленов степени меньше $i$ . Для неотрицательного целого числа $i$ такого, что $i$ $\leq$ $m$ и $i$ $\leq$ $n$ , пусть будет линейным отображением таким, что $P=p_{0}+p_{1}X+\cdots +p_{m}X^{m},\quad Q=q_{0}+q_{1}X+\cdots +q_{n}X^{n}.$ ${\mathcal {P}}_{i}$ $\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$ является определителем матрицы Сильвестра , которая является (квадратной $)$ матрицей на основе степеней $X.$ Аналогично, $i$ -субрезултантный полином определяется через определители подматриц матрицы $\varphi _{0}$ $\varphi _{i}.$

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

Пусть $p i = 0$ для $i < 0$ или $i > m$ , и $q i = 0$ для $i < 0$ или $i > n$ . Матрица Сильвестра — это матрица $(m + n) \times (m + n)$ такая, что коэффициент $i$ -й строки и $j$ -го столбца равен $p m + j - i$ для $j \leq n$ и $q j - i$ для $j > n$ : ^{[примечание 1]} $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$ из является $($ $m$ $+$ $n$ $-$ $i$ $) \times ($ $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$ . $\varphi _{i}$

Пусть $V i$ будет матрицей $(m + n - 2 i) \times (m + n - i)$ , определенной следующим образом. Сначала мы добавляем $(i + 1)$ столбцов нулей справа от единичной матрицы $(m + n - 2 i - 1) \times (m + n - 2 i - 1 )$ . Затем мы ограничиваем нижнюю часть полученной матрицы строкой, состоящей из $($ $m$ $+$ $n$ $-$ $i$ $- 1)$ нулей, за которыми следуют $X$ $i$ $,$ $X$ $i$ $-1$ $, ...,$ $X$ $, 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$ являются векторами коэффициентов некоторых полиномов, принадлежащих образу . Определение $i$ -го подрезультирующего полинома $S$ $i$ показывает, что вектор его коэффициентов является линейной комбинацией этих векторов-столбцов, и, таким образом, S _i принадлежит образу $\varphi _{i}$ $\varphi _{i}.$

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

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

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

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

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

После вычисления НОД многочлена и его производной дальнейшие вычисления НОД обеспечивают полную факторизацию многочлена без квадратов , которая является факторизацией , где для каждого $i$ многочлен $f$ $i$ либо равен 1, если $f$ не имеет корня кратности $i$ , либо является многочленом без квадратов (то есть многочленом без кратных корней), корни которого в точности являются корнями кратности $i$ многочлена $f$ (см. алгоритм Юна ). $f=\prod _{i=1}^{\deg(f)}f_{i}^{i}$

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

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

Последовательность Штурма полинома с действительными коэффициентами — это последовательность остатков, полученная с помощью варианта алгоритма Евклида, примененного к полиному и его производной. Для получения последовательности Штурма достаточно просто заменить инструкцию алгоритма Евклида на $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$ $\in$ $R$ $[$ $X$ $]$ , обозначаемое " $cont($ $p$ $)$ ", является НОД его коэффициентов. Полином $q$ $\in$ $F$ $[$ $X$ $]$ может быть записан , где p $\in$ $R$ $[$ $X$ $]$ и $c$ $\in$ $R$ : достаточно взять в качестве $c$ кратное всех знаменателей коэффициентов $q$ (например, их произведение) и $p = cq . Содержание q$ $определяется$ $как$ $:$ В обоих случаях $содержание$ определяется $с$ точностью до умножения на единицу R . $q={\frac {p}{c}}$ $\operatorname {cont} (q)={\frac {\operatorname {cont} (p)}{c}}.$

Примитивная часть многочлена в $R [X]$ или $F [X]$ определяется как $\operatorname {primpart} (p)={\frac {p}{\operatorname {cont} (p)}}.$

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

Таким образом, каждый многочлен в $R [X]$ или $F [X]$ может быть разложен на множители , и это разложение уникально с точностью до умножения содержимого на единицу $R$ и примитивной части на обратную этой единице. $p=\operatorname {cont} (p)\,\operatorname {primpart} (p),$

Из леммы Гаусса следует, что произведение двух примитивных многочленов является примитивным. Отсюда следует, что и $\operatorname {primpart} (pq)=\operatorname {primpart} (p)\operatorname {primpart} (q)$ $\operatorname {cont} (pq)=\operatorname {cont} (p)\operatorname {cont} (q).$

Соотношение между НОД иРи болееФ

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

Если $q 1$ и $q 2$ принадлежат $F [X]$ , то $\operatorname {primpart} (\gcd _{F[X]}(q_{1},q_{2}))=\gcd _{R[X]}(\operatorname {primpart} (q_{1}),\operatorname {primpart} (q_{2})).$

Если $p 1$ и $p 2$ принадлежат $R [X]$ , то и $\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 1, ..., x n]$ , и то, что предшествует, дает алгоритм для их вычисления.

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

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

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

Так, если применить алгоритм Евклида к следующим многочленам ^[2] и последовательные остатки алгоритма Евклида будут следующими: Видно, что, несмотря на малую степень и малый размер коэффициентов входных многочленов, приходится манипулировать и упрощать целые дроби довольно большого размера. $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]$ .

Если и и $a$ $\geq$ $b$ , то псевдоостаток от псевдоделения $A$ на $B$ , обозначаемый $prem($ $A$ $,$ $B$ $)$ , равен , где $lc($ $B$ $)$ — старший коэффициент $B$ (коэффициент при $X$ $b$ ). $\deg(A)=a$ $\deg(B)=b$ $\operatorname {prem} (A,B)=\operatorname {rem} (\operatorname {lc} (B)^{a-b+1}A,B),$

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

Последовательность псевдоостатка — это последовательность (псевдо)остатков $r i ,$ полученная путем замены инструкции алгоритма Евклида на , где $α$ — элемент $Z$ , который делит ровно каждый коэффициент числителя. Различные варианты $α$ дают различные последовательности псевдоостатка, которые описаны в следующих подразделах. $r_{i+1}:=\operatorname {rem} (r_{i-1},r_{i})$ $r_{i+1}:={\frac {\operatorname {prem} (r_{i-1},r_{i})}{\alpha }},$

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

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

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

Простейшая (для определения) последовательность остатков состоит в том, чтобы всегда брать $α = 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.$

r ₀  := a r ₁  := b for ( i  := 1; r _i ≠ 0; i  := i +1) do  d _i  := deg( r _{i −1} ) − deg( r _i )  γ _i  := lc( r _i )  if  i = 1 then  β ₁  := (−1) ^{d ₁ +1} ψ ₁  := −1  else  ψ _i  := (− γ _{i −1} ) ^{d _{i −1}} / ψ _{i −1}^{d _{i −1} −1} β _i  := − γ _{i −1}ψ _i^{d _i}  end if  r _{i +1}  := rem( γ _i^{d _i +1} r _{i −1} , r _i ) / β _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$ $\geq$ $b$ , то модифицированный псевдоостаток $prem2($ $A$ $,$ $B$ $)$ псевдоделения $A$ на $B$ равен , где $|$ $lc($ $B$ $)$ $|$ — абсолютное значение старшего коэффициента $B$ (коэффициента $X$ $b$ ). $\deg(A)=a$ $\deg(B)=b$ $\operatorname {prem2} (A,B)=-\operatorname {rem} (\left|\operatorname {lc} (B)\right|^{a-b+1}A,B),$

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

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

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

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

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

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

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

Примечания

^ Многие авторы определяют матрицу Сильвестра как транспонированную матрицу $S.$ Это нарушает обычное соглашение о записи матрицы линейной карты.

Ссылки

Цитаты

^ ab Басу, Поллак и Рой 2006
^ Кнут 1969
^ Ван Хой и Монаган 2004

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

Басу, Саугата; Поллак, Ричард; Рой, Мари-Франсуаза (2006). Алгоритмы в реальной алгебраической геометрии, глава 4.2. Springer-Verlag .
Davenport, James H .; Siret, Yvon; Tournier, Évelyne (1988). Компьютерная алгебра: системы и алгоритмы для алгебраических вычислений . Перевод с французского A. Davenport и JH Davenport. Academic Press. ISBN 978-0-12-204230-0.
ван Хой, М.; Монаган, МБ (2004). Алгоритмы для вычисления НОД полиномов над полями алгебраических функций . ISSAC 2004. стр. 297–304.
Джавади, СММ; Монаган, МБ (2007). Разреженный модульный алгоритм НОД для полиномов над полями алгебраических функций . ISSAC 2007. стр. 187–194.
Кнут, Дональд Э. (1969). Искусство программирования II . Эддисон-Уэсли. С. 370–371.
Кнут, Дональд Э. (1997). Получисленные алгоритмы . Искусство программирования. Т. 2 (Третье изд.). Рединг, Массачусетс: Addison-Wesley. С. 439–461, 678–691. ISBN 0-201-89684-2.
Loos, Rudiger (1982), "Обобщенные полиномиальные остаточные последовательности", в B. Buchberger; R. Loos; G. Collins (ред.), Computer Algebra , Springer Verlag
Паола Бойто: Методы на основе структурированных матриц для приближенного полиномиального НОД , Scuola Normale Superiore Pisa, ISBN 978-88-7642-380-2 (2011).