Многочлен без квадратов - Square-free polynomial - Wikipedia

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

А бесквадратное разложение или же бесквадратная факторизация полинома - это факторизация по степеням бесквадратных множителей

где те из аk которые не равны 1 попарно взаимно просты многочлены без квадратов.[1] Каждый ненулевой многочлен с коэффициентами в поле допускает факторизацию без квадратов, которая единственна вплоть до умножение множителей на ненулевые константы. Факторизацию без квадратов намного проще вычислить, чем полную факторизация в несводимый факторов, и поэтому часто предпочтительнее, когда полная факторизация на самом деле не нужна, как для частичная дробь разложение и символическая интеграция из рациональные дроби. Бесквадратная факторизация - это первый шаг полиномиальная факторизация алгоритмы, которые реализованы в системы компьютерной алгебры. Следовательно, алгоритм бесквадратной факторизации является основным в компьютерная алгебра.

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

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

Известны также алгоритмы вычисления бесквадратного разложения многомерных многочленов.[2]

Алгоритм Юна

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

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

Если

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

и

Если мы установим , и мы получаем это

и

Повторяя этот процесс, пока мы находим все

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


повторение

до того как
Выход

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

Квадратный корень

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

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

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

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

  1. ^ а б c d Юн, Дэвид Ю.Ю. (1976). Об алгоритмах разложения без квадратов SYMSAC '76 Труды третьего симпозиума ACM по символьным и алгебраическим вычислениямС. 26–35.
  2. ^ Джанни П., Трагер Б. (1996). Бесквадратные алгоритмы в положительной характеристике Применимая алгебра в инженерии, коммуникации и вычислениях, 7 (1), стр. 1–14.