Метод Кро́некера — метод разложения многочлена с целыми коэффициентами на неприводимые множители над кольцом целых чисел; предложен в 1882 Кронекером.
Алгоритм Кронекера находит для данного многочлена многочлен , такой, что делится на , или доказывает, что такого многочлена нет.
Описание метода Алгоритм Кронекера основан на следующих соображениях:
Если степень многочлена равна , то степень хотя бы одного множителя многочлена не превосходит ; Значения как , так и в целых точках — целые числа, причем ) делит для любого целого ; При фиксированном , если не равно 0, то может принимать только конечное множество значений, состоящее из делителей числа ; Коэффициенты многочлена однозначно восстанавливаются по его значениям в точке.
Таким образом, для получается конечное число возможностей; непосредственным делением проверяем, получили ли делитель многочлена .
Строгое Изложение:
Рассмотрим — многочлен степени . Пусть приводим над . Тогда и один из двух многочленов и имеет степень не выше . Пусть без ограничения общности . Тогда , следовательно . Рассмотрим различных целых чисел таких, что . Поскольку числа имеют конечное количество целых делителей, можно перебрать всевозможные наборы значений для . По каждому такому набору построим интерполяционный многочлен степени . Если теперь , к многочленам и можно применить тот же метод, и так до тех пор, пока все множители не станут неприводимыми. В противном случае, если , многочлен уже является неприводимым.
Одномерный алгоритм Кронекера
Запись алгоритма Дано:
Надо:
Где: — степень полинома , — степень полинома , — целочисленное.
Цикл от до Если () то
Ответ найден. Конец если Конец цикла
Если (ответ не найден) то — множество делителей (целочисленных) Цикл от до — множество делителей (целочисленных) декартово произведение и Цикл для каждого Построить многочлен степени , такой, что для Если ( делится на ) то
Решение успешно найдено, ответ Конец если Конец цикла Конец цикла Конец если
Конец.
ЗАМЕЧАНИЕ. Достаточно научиться разлагать на множители многочлены со старшим коэффициентом, равным единице. Действительно, если старший коэффициент равен , то домножив на и сделав замену , сводим задачу к этому случаю. После её решения остается сделать обратную замену и сократить на общий множитель 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; 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;
Пример (это многочлен с целыми коэффициентами и без рациональных корней). Если где степень k многочлена не больше степени , то . Тогда . Делители этих чисел: для первого +1 и −1, для второго +1, −1, +5, −5, для третьего +1,-1, +3, -3, +7,-7,+ 21, -21. Всего получается комбинации. Две комбинации отличающиеся лишь знаком, дают по сути один многочлен. Поэтому можно проверять лишь половину. Остаются 32 случая. Перебирая все эти случаи, можно найти лишь один многочлен 2-й степени, делящий . Это . Оба сомножителя этого разложения неприводимы (как многочлены 2-й и 3-й степеней, не имеющие рациональных корней).
Многомерный алгоритм Кронекера
Запись условий задачи Пусть — область целостности с однозначным разложением на множители, . Требуется разложить на неприводимые множители.
Запись алгоритма Дано:
Надо: — разложение
Переменные: многочлен , разложение многочлена , множество элементов типа .
Идея реализации: Редуцировать задачу к одномерному случаю, путём введения новой неизвестной и заменой всех переменных достаточно высокими степенями этой неизвестной. Факторизовать получившийся многочлен. Выполнить обратную подстановку, пробным делением убедиться, получено ли желаемое разложение.
Начало Выбрать целое большее, чем степени отдельных переменных в заменить все переменные степенями новой неизвестной :
Разложить на неприводимые множители, то есть
.число_множителей := 1
Цикл пока Цикл для каждого подмножества пока
Если делится на то .множитель[.число_множителей]:= .число_множителей:=.число_множителей + 1
.удалить{} Конец если Конец цикла
Конец цикла .множитель[.число_множителей]:= Конец
В этом алгоритме обратное преобразование определяется на одночленах по формуле:
для , далее распространяется по линейности.
Литература Е. В. Панкратьев «Элементы компьютерной алгебры.» М.:МГУ, 2007; Kronecker L. «J. reine und angew. Math.», 1882; Окунев Л. Я. «Высшая алгебра», М., 1937; Курош А. Г. «Курс высшей алгебры», 11 изд., М., 1975;
Категория:Многочлены Категория:Численные методы