close

Вход

Забыли?

вход по аккаунту

код для вставкиСкачать
ИвГУ, ф-т МиКН, курс 2
"КОМПЬЮТЕРНАЯ АЛГЕБРА"
Тема 8.
Алгоритм Кронекера
факторизации в кольце
Z[x]
Лектор: Н. И. Яцкин, 2014
2
Идея алгоритма Кронекера
1. Если степень заданного приводимого
многочлена ( ) ∈ [ ] равна n, то ( )
обязан иметь нетривиальный делитель
( )степени, не превышающей целую часть
n/2 (обозначим ее m).
2. Значения как ( ), так и ( ) в целых
точках — целые числа, причем ( )| ( ) для
любого целого i .
3. Рассмотрим целые числа = , , … , .
Если какое-либо из них является корнем
многочлена ( ), то по теореме Безу ( )
имеет линейный делитель ( ) = − .
3
4. В противном случае для каждого значения ( ) рассмотрим
(конечное!) множество
всех его делителей; значение ( )
должно принадлежать .
5. Образуем прямое (декартово) произведение
=
×
× …×
- также конечное множество. Элементами являются конечные
списки вида [ , , … , ], каждый из которых однозначно
определяет интерполяционный многочлен
( )=
,
−
−
,
имеющий, вообще говоря, рациональные коэффициенты.
4
6. Если при очередном выборе списка [ , , … , ]
соответствующий многочлен ( )
- имеет положительную степень и целые коэффициенты;
- делит данный многочлен ( ), причем частное ( )/ ( )
также имеет целые коэффициенты,
то ( ) можно принять в качестве нетривиального делителя для
данного многочлена.
7. Если исчерпав все множество мы не найдем ни одного
нетривиального делителя, то это будет свидетельствовать о
неприводимости данного многочлена ( ).
5
Дополнительные детали.
В начале исследования целесообразно вычислить содержание и
примитивный множитель для данного многочлена и в дальнейшем
исследовать только последний.
Исследование первого (числового) множителя должно
выполняться методами арифметики натуральных чисел; они
рассматривались ранее, здесь мы на этом останавливаться не будем.
6
ВСПОМОГАТЕЛЬНЫЕ
ПРОЦЕДУРЫ
1. DIVISORS, множество всех делителей целого числа
2. ContPrim, содержание и примитивный множитель для многочлена
3. INTERPOL, интерполяционный многочлен Лагранжа
4a. CartesianS, декартово произведение двух множеств
4b. CartesianSL, то же для множеств, составленных из списков
4c. SetOfLists, замена элементов одноэлементными списками
4d. CartesianLS декартово произведение нескольких множеств
7
1. DIVISORS
- процедура, вычисляющая множество всех
делителей целого числа. (См. встроенные команды floor, mod и union.)
> DIVISORS:=proc(a::integer)
local DIVISORS,k;
if a=0 then
RETURN(`All integers divide zero!`)
end if;
DIVISORS:={1,-1,a,-a}; # Тип 'set'.
for k from 2 to floor(abs(a)/2) do
if a mod k=0 then
DIVISORS:=DIVISORS union {k,-k,a/k,-a/k};
end if;
end do;
RETURN(DIVISORS);
end proc;
8
Пример применения.
> map(DIVISORS,[0,1,2,4,6,450]);
[ All integers divide zero! , { -1, 1 }, { -2, -1, 1, 2 }, { -4, -2, -1, 1, 2, 4 },
{ -6, -3, -2, -1, 1, 2, 3, 6 }, { -450, -225, -150, -90, -75, -50, -45, -30, -25, -18, -15,
-10, -9, -6, -5, -3, -2, -1, 1, 2, 3, 5, 6, 9, 10, 15, 18, 25, 30, 45, 50, 75, 90, 150, 225,
450 } ]
Встроенный аналог.
Эта процедура возвращает только положительные делители.
> map(numtheory[divisors],[0,1,2,4,6,450]);
[ { }, { 1 }, { 1, 2 }, { 1, 2, 4 }, { 1, 2, 3, 6 },
{ 1, 2, 3, 5, 6, 9, 10, 15, 18, 25, 30, 45, 50, 75, 90, 150, 225, 450 } ]
9
2. ContPrim - процедура, вычисляющая содержание и
примитивный множитель для целочисленного многочлена.
(См. предыдущую тему.)
3. INTERPOL
– процедура вычисления интерполяционного
многочлена Лагранжа.
Понадобится встроенная функция ListTools[MakeUnique], с помощью
которой осуществляется контроль выполнения условия на список: в нем не
должно быть повторяющихся элементов.
10
Начало кода (проверка корректности вводимых данных).
> INTERPOL:=proc(X::list,Y::list,x::name)
local n,i,j,f,P;
n:=nops(X);
if n=0 or n<>nops(Y) or
not ListTools[MakeUnique](X)=X then
ERROR();
end if;
…………………………………………………………………
…………………………………………………………………
Продолжим?
11
f:=0;
# Начало формирования суммы произведений.
for i from 1 to n do
P:=Y[i];
# Начало формирования очередного произведения.
for j from 1 to n do
if j<>i then
P:=simplify(P*(x-X[j])/(X[i]-X[j]));
# Накопление сомножителей в произведении.
end if;
end do;
f:=sort(simplify(f+P),x);
# Накопление слагаемых в сумме.
end do;
RETURN(f);
end proc;
12
INTERPOL := proc (X::list, Y::list, x ::name)
local n, i, j, f , P;
n := nops( X ) ;
if n0 or nnops( Y ) or not ( ListTools[ MakeUnique ]( X )X ) then
ERROR ( )
end if ;
f := 0;
for i to n do
P := Y[ i ] ;
for j to n do
if ji then P := simplify( P( xX[ j ] )/( X[ i ]X[ j ] ) ) end if
end do ;
f := sort ( simplify( f P ), x )
end do ;
RETURN( f )
13
Пример применения.
> X:=[0,1,2,3];Y:=[-2,4,5,3];
X := [ 0, 1, 2, 3 ]
Y := [ -2, 4, 5, 3 ]
> f:=INTERPOL(X,Y,x);
1 3 7 2 55
f := x  x  x 2
3
2
6
Проверка соответствия интерполяционным данным.
> for i from 1 to nops(X) do
evalb(Y[i]=eval(f,x=X[i])); end do;
true true true true
Проверка целочисленности интерполяционного многочлена.
> type(f,polinom(integer));
false
14
15
Рене́ Дека́рт
(фр. René Descartes,
лат. Renatus Cartesius —
Картезий; 1596 — 1650) —
французский философ,
математик, механик,
физик и физиолог,
создатель аналитической
геометрии и современной
алгебраической символики.
16
4a. CartesianS
- процедура вычисления
прямого (декартова) произведения двух множеств.
> CartesianS:=proc(A::set,B::set)
local a,b,AxB;
AxB:={};
for a in A do
for b in B do
AxB:=AxB union {[a,b]};
end do;
end do;
RETURN(AxB);
end proc;
17
CartesianS := proc (A::set , B::set)
local a, b, AxB ;
AxB := { };
for a in A do for b in B do AxB := AxB union { [ a, b ] } end do end do ;
RETURN ( AxB )
end proc
Пример применения. Результирующее множество
состоит из двухэлементных списков.
> A:={a,b,c,d};B:={1,2,3};CartesianS(A,B);
A := { a, b, c, d }
B := { 1, 2, 3 }
{ [ a , 1 ], [ a , 2 ], [ a , 3 ], [ b , 1 ], [ b , 2 ], [ b , 3 ] , [ c , 1 ], [ c , 2 ] , [ c , 3 ], [ d , 1 ] , [ d , 2 ] , [ d , 3 ] }
18
4b. CartesianSL
– процедура, вычисляющая декартово
произведение двух множеств, элементами которых являются списки.
При умножении происходит слияние списков.
> CartesianSL:=proc(A::set(list),B::set(list))
local a,b,AxB;
AxB:={};
for a in A do
for b in B do
AxB:=AxB union {[a[],b[]]};
end do;
end do;
RETURN(AxB);
end proc;
19
Пример применения.
> A:={[a],[b],[c]};B:={[1,1],[1,2],[2,1],[2,2]};
A := { [ a ], [ b ], [ c ] }
B := { [ 1, 1 ], [ 1, 2 ], [ 2, 1 ], [ 2, 2 ] }
> CartesianSL(A,B);
{ [ a, 1, 1 ], [ a, 1, 2 ], [ a, 2, 1 ], [ a, 2, 2 ], [ b, 1, 1 ], [ b, 1, 2 ], [ b, 2, 1 ], [ b, 2, 2 ], [ c, 1, 1 ],
[ c, 1, 2 ], [ c, 2, 1 ], [ c, 2, 2 ] }
20
4c. SetOfLists
- вспомогательная процедура, заменяющая
элементы в данном множестве одноэлементными списками.
> SetOfLists:=proc(A::set)
local a,B;
B:={};
for a in A do
B:=B union {[a]};
end do;
RETURN(B);
end proc;
Пример применения.
> A:={a,b,c};SetOfLists(A);
A := { a, b, c }
{ [ a ], [ b ], [ c ] }
21
4d. CartesianLS
- процедура декартова перемножения
нескольких множеств (объединенных в список). Произведение строится
индуктивно, с использованием процедур SetOfLists и CartesianSL.
> CartesianLS:=proc(U::list(set))
local n,i,P,N,V;
n:=nops(U);
if n=0 then
RETURN(NULL);
end if;
22
N:=1;
for i from 1 to n do
N:=N*nops(U[i]);
V[i]:=SetOfLists(U[i]);
end do;
if N=0 then
RETURN({});
end if;
P:=V[1];
for i from 2 to n do
P:=CartesianSL(P,V[i]);
end do;
RETURN(P);
end proc;
23
Пример применения.
> L:=[{a,b,c},{1,2,3,4},{alpha,beta}];
L := [ { a, b, c } , { 1, 2, 3, 4 }, { ,  } ]
> CartesianLS(L);
{ [ a , 1,  ] , [ a , 1,  ] , [ a , 2,  ] , [ a, 2 ,  ] , [ a, 3 ,  ] , [ a, 3,  ] , [ a, 4 ,  ] , [ a , 4,  ] ,
[ b, 1,  ], [ b, 1,  ], [ b, 2,  ], [ b, 2,  ], [ b, 3,  ], [ b, 3,  ], [ b, 4,  ], [ b, 4,  ],
[ c, 1,  ], [ c, 1,  ], [ c, 2,  ], [ c, 2,  ], [ c, 3,  ], [ c, 3,  ], [ c, 4,  ], [ c, 4,  ] }
24
ОСНОВНЫЕ ПРОЦЕДУРЫ
1. kroneker,
тест на неприводимость целочисленного многочлена
(в случае приводимости возвращается некоторый нетривиальный делитель)
2. kronekerIRR,
модификация теста с возвращением (в случае
приводимости) некоторого неприводимого делителя
3. kronekerFACTS
факторизация целочисленного многочлена
(разложение на неприводимые множители)
25
1. kroneker - процедура,
тестирующая заданный
целочисленный многочлен
на неприводимость его
примитивной части
(true означает: "примитивный
множитель неприводим").
В случае приводимости должен
возвращаться найденный
нетривиальный делитель.
26
Полный перечень возвращаемых данных:
(1) трехчленная последовательность ответов:
содержание, примитивный множитель, true –
в случае неприводимости;
(2) пятичленная последовательность ответов:
содержание, примитивный множитель, false, делитель, частное –
в случае приводимости.
Содержание (натуральное число) на неприводимость (простоту)
не исследуется.
27
> kroneker:=proc(f::polynom(integer),x::name)
local n,m,i,cf,prf,X,Y,DY,U,M,mu,g;
n:=degree(f,x);
if n=0 then
RETURN(abs(f),sign(f),false,NULL,NULL);
end if;
cf,prf:=ContPrim(f,x);
# Вычисление содержания и примитивного множителя.
m:=floor(n/2);
# Степень нетривиального делителя,
# если он существует, не превышает целой части
# от полустепни m данного многочлена.
28
X:=array(0..m);
# Заготовка для массива из m+1 первых
# неотрицательных целых чисел.
Y:=array(0..m);
# Заготовка для массива значений данного
# многочлена на точках массива Х.
# Далее следует заполнение этих массивов.
for i from 0 to m do
X[i]:=i; Y[i]:=eval(prf,x=X[i]);
29
if Y[i]=0 then
RETURN(cf,prf,false,x-X[i],quo(prf,x-X[i],x));
# Если в массиве Х оказался корень данного
# многочлена, то этот многочлен имеет
# (по теореме Безу) линейный множитель;
# многочлен prf приводим. Возвращается
# пятичленная последовательность ответов.
end if;
DY[i]:=DIVISORS(Y[i]);
# Для ненулевого элемента массива Y вычисляется
# множество всех его делителей.
end do;
30
U:=[seq(DY[i],i=0..m)];
# Составляется список множеств делителей.
M:=CartesianLS(U);
# Производится декартово перемножение всех этих
# множеств. Далее элементы декартова произведения
# (списки mu) по очереди просматриваются.
for mu in M do
g:=INTERPOL(convert(X,list),mu,x);
# Вычисление интерполяционного многочлена
# по очередному списку mu.
31
if type(g,polynom(integer)) and
degree(g,x)>=1 and
rem(prf,g,x)=0 and
type(quo(prf,g,x),polynom(integer)) then
# Для того, чтобы интерполяционный многочлен
# был отобран как нетривиальный делитель
# данного многочлена, необходимо,
# (1) чтобы он был целочисленным,
# (2) положительной степени;
# (3) делил данный многочлен;
# (4) чтобы частное также было целочисленным.
32
if coeff(g,x,degree(g,x))<0 then
g:=-g;
# Добиваемся положительности старшего
# коэффициента найденного делителя.
end if;
RETURN(cf,prf,false,g,quo(prf,g,x));
# Многочлен prf приводим. Возвращается
# пятичленная последовательность ответов.
end if;
end do;
33
RETURN(cf,prf,true);
# Ни один из списков не породил нетривиальный
# делитель. Примитивный множитель данного
# многочлена неприводим. Возвращается
# пятичленная последовательность ответов.
# (четвертый ответ = повторение второго).
end proc;
Примеры применения.
> f:=2*x^5+x^4+x^2+x+2;g:=2*x^4+8;
g := 2 x 48
f := 2 x 5x 4x 2x2
> kroneker(f,x);kroneker(g,x);
1, 2 x 5x 4x 2x2, true , 2 x 5x 4x 2x2, 1
2, x 44, false , x 22 x2, x 22 x2
34
С целью отслеживания промежуточных этапов работы процедуры
вставим в нее трассировочные принты. (Обратите внимание на то, что
массивы X и Y вычисляются не по заданному многочлену f, а по его
примитивной части prf.)
> h:=18*x^5+6*x^4+12*x^3+27*x^2+9*x+18;
kroneker(h,x);
h := 18 x 56 x 412 x 327 x 29 x18
cf 3
prf 6 x 52 x 44 x 39 x 23 x6
X[ 0, 1, 2 ], Y[ 6, 30, 304 ], U[ { -6, -3, -2, -1, 1, 2, 3, 6 },
{ -30 , -15 , -10 , -6, -5, -3, -2, -1, 1, 2, 3, 5, 6, 10, 15, 30 },
{ -304 , -152 , -76 , -38 , -19 , -16 , -8, -4, -2, -1, 1, 2, 4, 8, 16, 19, 38, 76, 152, 304 } ]
35
[ -6, -30, -304 ], g125 x 2101 x6
[ -6, -30, -152 ], g49 x 225 x6
[ -6, -30, -76 ], g11 x 213 x6
[ -6, -30 , -38 ], g8 x 232 x6
35 2 83
[ -6, -30, -19 ], g x  x6
2
2
………………………………………………………………
Пропущено порядка 500 строк (испытаний).
………………………………………………………………
36
[ -2, -6, -38 ], g14 x 210 x2
9 2 1
[ -2, -6, -19 ], g x  x2
2
2
[ -2, -6, -16 ], g3 x 2x2
3, 6 x 52 x 44 x 39 x 23 x6, false , 3 x 2x2, 2 x 33
37
2. kronekerIRR – модификация
процедуры kroneker,
отличающаяся тем, что в случае
приводимости данного многочлена
возвращаться неприводимый
делитель. Идея модификации:
повторное применение процедуры
kroneker к получаемым
нетривиальным делителям, до
достижения неприводимости.
38
> kronekerIRR:=proc(f::polynom(integer),x::name)
local cf,prf,h,kr;
kr:= kroneker(f,x);
if kr[3] then
RETURN(kr);
else
cf:=kr[1];
prf:= kr[2];
h:= kr[4];
while not kroneker(h,x)[3] do
h:=kroneker(h,x)[4];
end do;
RETURN(cf,prf,false,h,quo(prf,h,x));
end if;
end proc;
39
Примеры применения.
> f:=expand((x^4+x^3+x^2+x+1)*(x^3+1));
f := x 72 x 4x 62 x 3x 5x 2x1
> kroneker(f,x);
1, x 72 x 4x 62 x 3x 5x 2x1, false , x 31, x 4x 3x 2x1
В качестве нетривиального делителя возвращен приводимый многочлен
+ .
> kronekerIRR(f,x);
1, x 72 x 4x 62 x 3x 5x 2x 1, false , x1, x 6x 4x 3x 21
Возвращен неприводимый делитель
+ .
40
3. kronekerFACTS – итерируя
процедуру kronekerIRR,
получаем процедуру разложения
на множители (факторизации)
целочисленного многочлена
(см. аналогичную процедуру
FACTORS для натуральных чисел).
41
Процедура kronekerFACTS возвращает структурированный
список следующего вида:
, [
,
], … , [
,
]
,
где
scal – скалярный множитель (содержание, с точностью до знака);
,…,
– неприводимые множители;
,…,
- их кратности.
42
Понадобится встроенная команда
k:=ListTools[Search](a,lst);
возвращающая k=0, если элемент a отсутствует в списке lst, или, в
противном случае – номер k позиции первого вхождения элемента a в
список lst.
> kronekerFACTS:=
proc(f::polynom(integer),x::name)
local n,scal,prf,
kr,g,h,irr,mlt,lng,ans,i,k;
43
n:=degree(f,x);
if n<=1 then RETURN(f); end if;
scal,prf:=ContPrim(f,x);
kr:=kronekerIRR(prf,x);
g,h:=kr[4],kr[5];
irr,mlt:=[g],[1];
while not (h=1 or h=-1) do
kr:=kronekerIRR(h,x);
g,h:=kr[4],kr[5];
k:=ListTools[Search](g,irr);
if k=0 then
irr,mlt:=[irr[],g],[mlt[],1];
else
mlt[k]:=mlt[k]+1;
end if;
end do;
44
lng:=nops(irr);
ans:=[];
for i from 1 to lng do
ans:=[ans[],[irr[i],mlt[i]]];
end do;
RETURN([scal*signum(h),ans]);
end proc;
45
Примеры применения.
f:=x^7+2*x^6+2*x^5+3*x^4+3*x^3+2*x^2+2*x+1;
f := x 72 x 62 x 53 x 43 x 32 x 22 x1
> kronekerFACTS(f,x);
[ 1, [ [ x1, 3 ], [ x 21, 1 ], [ x 2x1, 1 ] ] ]
Проверка с помощью встроенной функции:
> factor(f);
( x 21 ) ( x 2x1 ) ( x1 ) 3
46
1/--страниц
Пожаловаться на содержимое документа