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

редактировать

Многочлен без повторяющегося корня

В математике, многочлен без квадратов - это многочлен, определенный для поля (или, в более общем смысле, уникальный домен факторизации ), который не имеет в качестве множителя ни одного квадрата фактора, отличного от единицы. В важном случае одномерных многочленов над полем k это означает, что $f ∈ k [X] {\ displaystyle f \ in k [X]}$ $f \ in k [X]$ не содержит квадратов тогда и только тогда, когда $b 2 ∤ е {\ displaystyle b ^ {2} \ nmid f}$ $b ^ 2 \ nmid f$ для каждого многочлена $b ∈ k [X] {\ displaystyle b \ in k [X]}$ $b \ in k [X]$ положительной степени. В приложениях в физике и технике полином без квадратов обычно называют полиномом без повторяющихся корней . Такие полиномы называются сепарабельными, но разделимость в идеальном поле равносильна тому, что они не содержат квадратов.

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

f = a 1 a 2 2 a 3 3 ⋯ ann = ∏ К = 1 nakk {\ Displaystyle f = a_ {1} a_ {2} ^ {2} a_ {3} ^ {3} \ cdots a_ {n} ^ {n} = \ prod _ {k = 1} ^ {n} a_ {k} ^ {k} \,}

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

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

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

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

Существуют также известные алгоритмы для вычисления бесквадратного разложения многомерных многочленов.

Алгоритм Юня

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

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

Если

f = a 1 a 2 2 a 3 3 ⋯ akk {\ displaystyle f = a_ {1} a_ {2} ^ {2} a_ {3} ^ {3} \ cdots a_ {k} ^ {k}}

f = a_1 a_2 ^ 2 a_3 ^ 3 \ cdots a_k ^ k

- желаемая факторизация, поэтому мы имеем

a 0 = a 2 1 a 3 2 ⋯ akk - 1, {\ displaystyle a_ {0} = a_ {2} ^ { 1} a_ {3} ^ {2} \ cdots a_ {k} ^ {k-1},}

a_0 = a_2 ^ 1 a_3 ^ 2 \ cdots a_k ^ {k-1},

f / a 0 = a 1 a 2 a 3 ⋯ ak {\ displaystyle f / a_ {0} = a_ {1} a_ {2} a_ {3} \ cdots a_ {k}}

f / a_0 = a_1 a_2 a_3 \ cdots a_k

f ′ / a 0 = ∑ i = 1 kiai ′ a 1 ⋯ ai - 1 ai + 1 ⋯ ak. {\ displaystyle f '/ a_ {0} = \ sum _ {i = 1} ^ {k} ia_ {i}' a_ {1} \ cdots a_ {i-1} a_ {i + 1} \ cdots a_ { k}.}

f'/a_0 = \sum_{i=1}^k i a_i' a_1 \cdots a_{i-1} a_{i+1} \cdots a_k.

Если мы установим $b 1 = f / a 0 {\ displaystyle b_ {1} = f / a_ {0}}$ $b_1=f/a_0$ , $c 1 = f ′ / a 0 {\ displaystyle c_ {1} = f '/ a_ {0}}$ $c_1=f'/a_0$ и $d 1 = c 1 - b 1 ′ {\ displaystyle d_ {1} = c_ {1} -b_ {1}'}$ $d_1=c_1-b_1'$ , получаем, что

gcd (b 1, d 1) = a 1, {\ displaystyle \ gcd (b_ {1}, d_ {1}) = a_ {1},}

\ gcd (b_1, d_1) = a_1,

б 2 = б 1 / а 1 = а 2 а 3 ⋯ ан, {\ displaystyle b_ {2} = b_ {1} / a_ {1} = a_ {2} a_ {3} \ cdots a_ {n}, }

b_2 = b_1 / a_1 = a_2 a_3 \ cdots a_n,

c 2 = d 1 / a 1 = ∑ i = 2 k (i - 1) ai ′ a 2 ⋯ ai - 1 ai + 1 ⋯ ak. {\ 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}.}

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.

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

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

$a 0: = gcd (f, f '); b 1: = f / a 0; c 1: = f ′ / a 0; d 1: = c 1 - b 1 ′; я: = 1; {\ 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;}$ $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;$ . repeat. $ai: = gcd (bi, di); b i + 1: = b i / a i; c i + 1: = d i / a i; я: = я + 1; d i: = c i - b i ′; {\ 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} ';}$ $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}';$ . до $b = 1; {\ displaystyle b = 1;}$ $b=1;$ . Вывод $a 1,…, a i - 1. {\ displaystyle a_ {1}, \ ldots, a_ {i-1}.}$ $a_1, \ ldots, a_ {i-1}.$

Степень $ci {\ displaystyle c_ {i}}$ $c_{i}$ и $di {\ displaystyle d_ {i}}$ $d_{i}$ на единицу меньше степени $bi. {\ displaystyle b_ {i}.}$ $b_i.$ Поскольку $f {\ displaystyle f}$ $f$ является произведением $bi, {\ displaystyle b_ {i},}$ $b_i,$ сумма степеней $bi {\ displaystyle b_ {i}}$ $b_ {i}$ является степенью $f. {\ displaystyle f.}$ $f.$ Поскольку сложность вычислений и делений GCD увеличивается более чем линейно с увеличением степени, из этого следует, что общее время выполнения цикла "повторения" меньше, чем время выполнения первого строка алгоритма, и что общее время работы алгоритма Юня ограничено сверху вдвое большим временем, необходимым для вычисления НОД $f {\ displaystyle f}$ $f$ и $f ′ {\ displaystyle f '}$ $f'$ и частное $f {\ displaystyle f}$ $f$ и $f ′ {\ displaystyle f'}$ $f'$ по их НОД.

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

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

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

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

Примечания