Многочлен без квадратов

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

В случае одномерных многочленов правило произведения подразумевает, что если p ² делит f , то p делит формальную производную f '  от f . Обратное также верно для нулевой характеристики и для многочленов над конечным полем (или, в более общем смысле, над совершенным полем ). То есть в этих случаях многочлен свободен от квадратов тогда и только тогда, когда 1 является наибольшим общим делителем многочлена и его производной.

Разложение бесквадратно или бесквадратно разложение многочлена является разложением по степеням бесквадратных многочленов

${\ displaystyle f = a_ {1} a_ {2} ^ {2} a_ {3} ^ {3} \ cdots a_ {n} ^ {n} = \ prod _ {k = 1} ^ {n} a_ { к} ^ {к} \,}$

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

Над полем характеристики 0, частное по его НОД и его производной является произведением в приведенном выше разложении без квадратов. Над совершенным полем ненулевой характеристики p это частное является произведением такого, что i не делится на p . Дальнейшие вычисления GCD и точные деления позволяют вычислить факторизацию без квадратов (см. Факторизацию без квадратов по конечному полю ). Для нулевой характеристики известен лучший алгоритм - алгоритм Юна, описанный ниже. ^[1] Его вычислительная сложность , самое большее, в два раза больше, чем вычисление GCD входного полинома и его производной. Точнее, если${\ displaystyle f}$${\ displaystyle a_ {i}}$${\ displaystyle a_ {i}}$${\ displaystyle T_ {n}}$время, необходимое для вычисления НОД двух многочленов степени и частное этих многочленов по НОД, затем верхняя граница времени, необходимого для вычисления разложения без квадратов.${\ displaystyle n}$${\ displaystyle 2T_ {n}}$

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

Алгоритм Юна [ править ]

В этом разделе описывается алгоритм Юна для бесквадратного разложения одномерных многочленов над полем характеристики 0 . ^[1] Он продолжается последовательностью вычислений GCD и точных делений.

Таким образом, входом является ненулевой многочлен f , и первый шаг алгоритма состоит из вычисления НОД a ₀ для f и его формальной производной f ' .

Если

${\ displaystyle f = a_ {1} a_ {2} ^ {2} a_ {3} ^ {3} \ cdots a_ {k} ^ {k}}$

- искомая факторизация, то есть

${\ displaystyle a_ {0} = a_ {2} ^ {1} a_ {3} ^ {2} \ cdots a_ {k} ^ {k-1},}$

${\ displaystyle f / a_ {0} = a_ {1} a_ {2} a_ {3} \ cdots a_ {k}}$

и

${\ displaystyle f '/ a_ {0} = \ sum _ {i = 1} ^ {k} ia_ {i}' a_ {1} \ cdots a_ {i-1} a_ {i + 1} \ cdots a_ { k}.}$

Если мы установим , и , мы получим, что${\ displaystyle b_ {1} = f / a_ {0}}$${\displaystyle c_{1}=f'/a_{0}}$${\displaystyle d_{1}=c_{1}-b_{1}'}$

${\displaystyle \gcd(b_{1},d_{1})=a_{1},}$

${\displaystyle b_{2}=b_{1}/a_{1}=a_{2}a_{3}\cdots a_{n},}$

и

${\displaystyle c_{2}=d_{1}/a_{1}=\sum _{i=2}^{k}(i-1)a_{i}'a_{2}\cdots a_{i-1}a_{i+1}\cdots a_{k}.}$

Повторяя этот процесс, пока не найдем все${\displaystyle b_{k+1}=1}$${\displaystyle a_{i}.}$

Это формализовано в алгоритм следующим образом:

${\displaystyle a_{0}:=\gcd(f,f');\quad b_{1}:=f/a_{0};\quad c_{1}:=f'/a_{0};\quad d_{1}:=c_{1}-b_{1}';\quad i:=1;}$
повторять, пока не выведет
${\displaystyle a_{i}:=\gcd(b_{i},d_{i});\quad b_{i+1}:=b_{i}/a_{i};\quad c_{i+1}:=d_{i}/a_{i};\quad i:=i+1;\quad d_{i}:=c_{i}-b_{i}';}$
${\displaystyle b=1;}$
${\displaystyle a_{1},\ldots ,a_{i-1}.}$

Степень и на единицу меньше, чем степень As, является произведением суммы степеней, является степенью As сложность вычислений GCD и делений увеличивается более чем линейно со степенью, из этого следует, что общая текущая время «повтор» цикл меньше времени выполнения первой линии алгоритма, и что общее время работы алгоритма Yun является ограниченно сверху два раза времени , необходимым для вычисления НОДА и и частного , и с помощью их НОД.${\displaystyle c_{i}}$${\displaystyle d_{i}}$${\displaystyle b_{i}.}$${\displaystyle f}$${\displaystyle b_{i},}$${\displaystyle b_{i}}$${\displaystyle f.}$${\displaystyle f}$${\displaystyle f'}$${\displaystyle f}$${\displaystyle f'}$

Квадратный корень [ править ]

Как правило, полином не имеет квадратного корня . Точнее, большинство многочленов нельзя записать в виде квадрата другого многочлена.

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

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

Заметки [ править ]

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