Бесквадратный многочлен

Многочлен без повторных корней

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

Правило произведения подразумевает, что если p ² делит f , то p делит формальную производную f ′  от f . Обратное также верно и, следовательно, является свободным от квадратов тогда и только тогда, когда является наибольшим общим делителем многочлена и его производной. ^[2] ${\displaystyle f}$ ${\displaystyle 1}$

Бесквадратное разложение или бесквадратная факторизация многочлена — это разложение на множители по степеням бесквадратных многочленов.

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

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

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

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

Алгоритм Юна

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

Таким образом, входными данными является ненулевой многочлен 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_{i}=1;}$
${\displaystyle a_{1},\ldots ,a_{i-1}.}$

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

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

Примечания

Ссылки

1. Yun, David YY (1976). "О бесквадратных алгоритмах разложения". SYMSAC '76 Труды третьего симпозиума ACM по символьным и алгебраическим вычислениям . Ассоциация вычислительной техники. стр. 26–35. doi :10.1145/800205.806320. ISBN 978-1-4503-7790-4. S2CID  12861227.
2. Даммит, Дэвид С.; Фут, Ричард М. (2004). Абстрактная алгебра . стр. 547. ISBN 978-81-265-3228-5.
3. Джанни, П.; Трагер, Б. (1996). «Бесквадратные алгоритмы в положительной характеристике». Применимая алгебра в инженерии, связи и вычислениях . 7 (1): 1–14. doi :10.1007/BF01613611. S2CID  36886948.