Факторизация полиномов

Этот калькулятор находит разложение многочлена на рациональные множители.

Данный калькулятор находит разложение входного многочлена одной переменной на неразлагаемые множители с рациональными коэффициентами. Чтобы лучше понять, как работает калькулятор можно включить галочку 'Детали', а также изучить материал, представленный сразу за калькулятором.

PLANETCALC, Разложение полинома с рациональными коэффициентами

Разложение полинома с рациональными коэффициентами

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

Разложение полинома в рациональных числах1

  • преобразовать входной полином в рациональных числах Q[x] в нормированный полином в целых числах Z[x]
  • Найти все квадратичные множители при помощи Разложения Юна
  • Выполнить последующие шаги для всех множителей степени выше 1
    • Если старший коэффициент не равен 1, преобразовать полином в монический следующим образом:
      v = a_n^{n-1}u(y/a_n)=\sum_{i=0}^{n-1} a_n^{n-1-i}a_iy^i+y^n, где
      v(y) - полученный монический полином (старший коэффициент = 1),
      u(x) - входной полином,
      an - старший коэффициент u(x),
      x = any
    • Найти неразлагаемые множители v(y)=v1v2...vr в конечном поле Fp[x]
    • Используем преобразование Хенселя для повышения степени разложения до верхней границы коэффициентов
      • Определим верхнюю границу коэффициентов результата:
        B=2^n\sqrt{n+i}||v||, где
        ||v||=max({|a_n|,...,|a_0|}) - максимальное абсолютное значение коэффициента входного многочлена (высота полинома)
      • Выполнить преобразование Хенселя k\geq \frac{ln(2B)}{ln(p)} раз
    • проверить, полученные множители делением v(y)/vi в кольце целых чисел Z[x], убрать неправильные множители
    • Выполнить обратное преобразование монического полинома:
      u(x)=pp(v_1(a_nx))pp(v_2(a_nx))...pp(v_r(a_nx))
      pp - примитивная часть полинома, функция убирает контент полинома

  1. Joel S. Cohen, Computer Algebra and Symbolyc Computation : Mathematical Methods, par. 9. Polynomial Factorization 

  2. Дональд Кнут, Искусство программирования том 2 ,пар. 4.6.2 Факторизация полиномов 

Ссылка скопирована в буфер обмена
PLANETCALC, Факторизация полиномов

Комментарии