В математике , А бесквадратно полином является полиномом , определенным над полем (или в более общем смысле , в области целостности ) , который не имеет в качестве делителя какого - либо квадрата непостоянного полинома . [1] одномерный полином имеет квадратную форму свободен тогда и только тогда , когда он не имеет кратный корня в алгебраически замкнутом поле , содержащего его коэффициенты. Это мотивирует то, что в приложениях в физике и технике полином без квадратов обычно называют полиномом без повторяющихся корней .
В случае одномерных многочленов правило произведения подразумевает, что если p 2 делит f , то p делит формальную производную f ' от f . Обратное также верно для нулевой характеристики и для многочленов над конечным полем (или, в более общем смысле, над совершенным полем ). То есть в этих случаях многочлен свободен от квадратов тогда и только тогда, когда 1 является наибольшим общим делителем многочлена и его производной.
Разложение бесквадратно или бесквадратно разложение многочлена является разложением по степеням бесквадратных многочленов
где те из a k , которые непостоянны, являются попарно взаимно простыми многочленами без квадратов (здесь два многочлена называются взаимно простыми , их наибольший общий делитель является константой; другими словами, это взаимно простота над полем частных коэффициентов что считается). [1] Каждый ненулевой многочлен представляет собой факторизацию без квадратов, которая уникальна с точностью до умножения и деления множителей на ненулевые константы. Бесквадратная факторизация гораздо легче вычислить , чем полная факторизация в неприводимые факторы, и, таким образом , часто предпочтительно , когда полная факторизация на самом деле не требуется, так как для разложения дроби и символической интеграции в рациональных дробях . Факторизация без квадратов - это первый шаг алгоритмов полиномиальной факторизации , которые реализованы в системах компьютерной алгебры . Таким образом, алгоритм бесквадратной факторизации является базовым в компьютерной алгебре .
Над полем характеристики 0 частное своим НОД со своей производной является произведением в приведенном выше разложении без квадратов. Над совершенным полем ненулевой характеристики p это частное является произведениемтакое, что i не делится на p . Дальнейшие вычисления GCD и точные деления позволяют вычислить факторизацию без квадратов (см. Факторизацию без квадратов по конечному полю ). Для нулевой характеристики известен лучший алгоритм - алгоритм Юна, описанный ниже. [1] Его вычислительная сложность , самое большее, в два раза больше, чем вычисление GCD входного полинома и его производной. Точнее, если время, необходимое для вычисления НОД двух многочленов степени и частное этих многочленов по НОД, то - это верхняя граница времени, необходимого для вычисления разложения без квадратов.
Существуют также известные алгоритмы для вычисления разложения без квадратов многомерных многочленов , которые обычно осуществляются путем рассмотрения многомерного многочлена как одномерного многочлена с полиномиальными коэффициентами и рекурсивного применения одномерного алгоритма. [2]
Алгоритм Юня
В этом разделе описывается алгоритм Юна для бесквадратного разложения одномерных многочленов над полем характеристики 0 . [1] Он продолжается последовательностью вычислений GCD и точных делений.
Таким образом, входом является ненулевой многочлен f , и первый шаг алгоритма состоит из вычисления НОД a 0 для f и его формальной производной f ' .
Если
- искомая факторизация, то есть
а также
Если мы установим , а также , мы получаем это
а также
Повторяя этот процесс до тех пор, пока мы находим все
Это формализовано в алгоритм следующим образом:
повторить
до того как
Выход
Степень а также на единицу меньше, чем степень В виде продукт сумма степеней степень Поскольку сложность вычислений и делений GCD увеличивается более чем линейно с увеличением степени, из этого следует, что общее время выполнения цикла «повторения» меньше, чем время выполнения первой строки алгоритма, и что общее время выполнения Алгоритм Юна имеет верхнюю границу, в два раза превышающую время, необходимое для вычисления НОД а также и частное а также их НОД.
Квадратный корень
Как правило, полином не имеет квадратного корня . Точнее, большинство многочленов нельзя записать в виде квадрата другого многочлена.
Многочлен имеет квадратный корень тогда и только тогда, когда все показатели бесквадратного разложения четны. В этом случае квадратный корень получается делением этих показателей на 2.
Таким образом, проблема определения того, имеет ли многочлен квадратный корень, и его вычисления, если он существует, является частным случаем бесквадратной факторизации.
Заметки
Рекомендации
- ^ a b c d Юнь, Дэвид YY (1976). «Об алгоритмах бесквадратной декомпозиции» . SYMSAC '76 Труды третьего симпозиума ACM по символьным и алгебраическим вычислениям. Ассоциация вычислительной техники. С. 26–35. DOI : 10.1145 / 800205.806320 . ISBN 978-1-4503-7790-4. S2CID 12861227 .
- ^ Gianni, P .; Трагер, Б. (1996). «Бесквадратные алгоритмы в положительной характеристике». Применимая алгебра в инженерии, коммуникации и вычислениях . 7 (1): 1–14. DOI : 10.1007 / BF01613611 . S2CID 36886948 .