Русская Википедия:Метод Кронекера

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Метод Кронекера — метод разложения многочлена с целыми коэффициентами на неприводимые множители над кольцом целых чисел; предложен в 1882 Кронекером.

Алгоритм Кронекера находит для данного многочлена <math>F(x)</math> многочлен <math>f(x)</math>, такой, что <math>F(x)</math> делится на <math>f(x)</math>, или доказывает, что такого многочлена нет.

Описание метода

Алгоритм Кронекера основан на следующих соображениях:

  1. Если степень многочлена <math>F</math> равна <math>n</math>, то степень хотя бы одного множителя <math>f</math> многочлена не превосходит <math>\left\lfloor {n\over 2} \right\rfloor</math> ;
  2. Значения как <math>F</math> , так и <math>f</math> в целых точках — целые числа, причем <math>f(i</math>) делит <math>F(i)</math> для любого целого <math>i</math>;
  3. При фиксированном <math>i</math>, если <math>F(i)</math> не равно 0, то <math>f(i)</math> может принимать только конечное множество значений, состоящее из делителей числа <math>F(i)</math>;
  4. Коэффициенты многочлена <math>f</math> однозначно восстанавливаются по его значениям в точке.

Таким образом, для <math>f</math> получается конечное число возможностей; непосредственным делением проверяем, получили ли делитель многочлена <math>F</math>.

Строгое Изложение:

Рассмотрим <math>f(x) \in \mathbb{Z}[x]</math> — многочлен степени <math>n</math>. Пусть <math>f(x)</math> приводим над <math>\mathbb{Z}</math>. Тогда <math>f(x) = g(x)h(x)</math> и один из двух многочленов <math>g(x)</math> и <math>h(x)</math> имеет степень не выше <math>n/2</math>. Пусть без ограничения общности <math>\operatorname{deg} \, g(x) \leqslant n/2</math>. Тогда <math>\forall a \in \mathbb{Z} \; g(a) \in \mathbb{Z}</math>, следовательно <math>f(a) \vdots g(a)</math>. Рассмотрим <math>m=n/2+1</math> различных целых чисел <math>a_i, i=\overline{1,m}</math> таких, что <math>f(a_i)\not=0</math>. Поскольку числа <math>f(a_i)</math> имеют конечное количество целых делителей, можно перебрать всевозможные наборы значений для <math>g(a_i)</math>. По каждому такому набору построим интерполяционный многочлен <math>g^*(x)</math> степени <math>m-1=n/2</math>. Если теперь <math>f(x)\mathrel{\vdots}g^*(x)</math>, к многочленам <math>g^*(x)</math> и <math>\frac{f(x)}{g^*(x)}</math> можно применить тот же метод, и так до тех пор, пока все множители не станут неприводимыми. В противном случае, если <math>\forall g^*(x) \ f(x)\mathrel{\cancel\vdots} g^*(x)</math>, многочлен <math>f(x)</math> уже является неприводимым.

Одномерный алгоритм Кронекера

Запись алгоритма

Дано: <math>f(x) \in \mathbb{Z}[x]</math>

Надо: <math>g(x) \in \mathbb{Z}[x]</math>

Где: <math>n</math> — степень полинома <math>f</math>, <math>m</math> — степень полинома <math>g</math>, <math>i</math> — целочисленное.

Цикл от <math>i = 0</math> до <math>[n/2]</math>

Если (<math>f(i) = 0</math>) то
<math>g=x-i</math>
<math>m=1</math>
Ответ найден.
Конец если

Конец цикла

Если (ответ не найден) то

<math>U</math> — множество делителей <math>f(0)</math> (целочисленных)
Цикл от <math>i = 1</math> до <math>[n/2]</math>
<math>M</math> — множество делителей <math>f(i)</math> (целочисленных)
<math>U := </math> декартово произведение <math>U</math> и <math>M</math>
Цикл для каждого <math>u \in U</math>
Построить многочлен <math>g</math> степени <math>i</math>, такой, что <math>g(j)=u(j)</math> для <math>j=0...i</math>
Если (<math>f</math> делится на <math>g</math>) то
<math>m=i</math>
Решение успешно найдено, ответ <math>g</math>
Конец если
Конец цикла
Конец цикла

Конец если

Конец.

ЗАМЕЧАНИЕ. Достаточно научиться разлагать на множители многочлены со старшим коэффициентом, равным единице. Действительно, если старший коэффициент равен <math>a</math>, то домножив на <math>a^{n-1}</math> и сделав замену <math>x = y/a</math>, сводим задачу к этому случаю. После её решения остается сделать обратную замену и сократить на общий множитель an−1 . Однако этот метод обычно оказывается неэффективным: из-за увеличения коэффициентов ухудшаются различные оценки и скорость работы алгоритмов. Поэтому в большинстве работающих алгоритмов таких преобразований не производится.

Реализация на Maple

kronecker:=proc(f::polynom)
 local g,i,n,U,V,j;
 with(linalg);
 n:=degree(f)/2; 
 U:=myfactor(subs(x=0,f));
 for i from 1 to n do
   U:=U,myfactor(subs(x=i,f));
   V:=mcarp(U);
   for j in V do   
    g:=interp([$0..i],j,x);
    if rem(f,g,x)=0 and not type(g,'constant') then     
      print(g);               
    end if;
   end do;
  end dо;  
end proc;

myfactor:=proc(n::integer)
 local a,b,i,j;
 b:=[];
 for i from 1 to abs(n) do
  if (irem(n,i)=0) then  
   b:=ArrayTools[Concatenate](2,b,i);
   b:=ArrayTools[Concatenate](2,b,-i);
  end if;
 end do;
 convert(b,'list');
end proc;

# Next 2 functions computes cartesian product of multiple sets.
# They are taken from http://people.oregonstate.edu/~peterseb/mth355/docs/355f2001-cartesian-product.pdf
carp:=proc(X,Y)
 local Z,x,y;
 Z:={};
 for x in X do
  for y in Y do
   Z:=Z union {[x,y]};
  end do;
 end do;
 return Z;
end proc;

mcarp:=proc()
 local Z,k,x,y; option remember;
  if nargs=0 then
   Z:={};
  elif nargs=1 then
   Z:=args[1];
  else Z:={};
   for x in mcarp( seq(args[k], k=1..nargs-1) ) do
    for y in args[nargs] do
    Z:= Z union {[op(x),y]};
    end do;
   end do;
  end if;
 return Z;
end proc;

Пример

<math>f(x)=x^5-x^4-2x^3-8x^2+6x-1</math>(это многочлен с целыми коэффициентами и без рациональных корней). Если <math>f(x) = g(x) h(x)</math> где степень k многочлена <math>g(x)</math> не больше степени <math>h(x)</math>, то <math>k=2</math>. Тогда <math>f(0)=-1; f(1)=-5; f(2)=-21</math>. Делители этих чисел: для первого +1 и −1, для второго +1, −1, +5, −5, для третьего +1,-1, +3, -3, +7,-7,+ 21, -21. Всего получается <math>2 \cdot 4 \cdot 8=64</math> комбинации. Две комбинации отличающиеся лишь знаком, дают по сути один многочлен. Поэтому можно проверять лишь половину. Остаются 32 случая. Перебирая все эти случаи, можно найти лишь один многочлен 2-й степени, делящий <math>f(x)</math>. Это <math>g(x)=x^2-3x+1</math>. Оба сомножителя этого разложения неприводимы (как многочлены 2-й и 3-й степеней, не имеющие рациональных корней).

Многомерный алгоритм Кронекера

Запись условий задачи

Пусть <math>D</math> — область целостности с однозначным разложением на множители, <math>f(x_1,...,x_n) \in D[x_1,...,x_n]</math>. Требуется разложить <math>f</math> на неприводимые множители.

Запись алгоритма

Дано: <math>f \in \mathbb{Z} [x_1,...,x_n]</math>

Надо: <math>G</math> — разложение

Переменные: многочлен <math> \bar{f} \in \mathbb{Z}[y]</math>, разложение <math> \bar{G} </math> многочлена <math> \bar{f} </math>, множество <math>M</math> элементов типа <math>\mathbb{Z}</math>.

Идея реализации: Редуцировать задачу к одномерному случаю, путём введения новой неизвестной и заменой всех переменных достаточно высокими степенями этой неизвестной. Факторизовать получившийся многочлен. Выполнить обратную подстановку, пробным делением убедиться, получено ли желаемое разложение.

Начало
Выбрать целое <math>d</math> большее, чем степени отдельных переменных в <math>f</math> заменить все переменные степенями новой неизвестной <math>y</math>:

<math>\bar{f}(y):=S_d(f)=f(y,y^d,...,y^{d^{n-1}})</math>

Разложить <math>\bar{f}(y)</math> на неприводимые множители, то есть

<math> \bar{f}(y)= \bar{g}_1(y)... \bar{g}_s(y), \quad \bar{g}_i(y) \in \mathbb{Z}[y], \quad 1 \leq i \leq s</math>

<math>G</math>.число_множителей := 1

<math>m:=1</math>

<math>M:=\{1,...,s\}</math>

Цикл пока <math>m \leq [s/2]</math>

Цикл для каждого подмножества <math>{i_1,...,i_m} \subset M</math> пока <math>m \leq [s/2]</math>
<math>g_{i_1,...,i_m}(x_1,...,x_n):=S^{-1}_d(\bar{g}_{i_1}(y) \bar{g}_{i_2}(y)...\bar{g}_{i_m}(y))</math>
Если <math>f</math> делится на <math>g</math> то
<math>G</math>.множитель[<math>G</math>.число_множителей]:=<math>g</math>
<math>G</math>.число_множителей:=<math>G</math>.число_множителей + 1
<math>f:=f/g</math>
<math>s:=s - m</math>
<math>M</math>.удалить{<math>i_1,...,i_m</math>}
Конец если
Конец цикла
<math>m:=m+1</math>

Конец цикла
<math>G</math>.множитель[<math>G</math>.число_множителей]:=<math>f</math>
Конец

В этом алгоритме обратное преобразование <math>S^{-1}_d</math> определяется на одночленах по формуле:

<math>S^{-1}_d(y^{b_1+db_2+...+d^{v-1}b_v})=x_{1}^{b_1}...x_{v}^{b_v}</math>

<math>(0 \leq b_i < d</math> для <math>1 \leq i \leq v, \quad v \in \mathbb{Z})</math>, далее <math>S^{-1}_d</math> распространяется по линейности.

Литература

  • Е. В. Панкратьев «Элементы компьютерной алгебры.» М.:МГУ, 2007;
  • Kronecker L. «J. reine und angew. Math.», 1882;
  • Окунев Л. Я. «Высшая алгебра», М., 1937;
  • Курош А. Г. «Курс высшей алгебры», 11 изд., М., 1975;

Шаблон:Rq

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Метод_Кронекера&oldid=10372921