Полиномиальное разложение - Polynomial decomposition

В математике полиномиальное разложение выражает многочлен ж как функциональный состав ${\displaystyle g\circ h}$ многочленов грамм и час, куда грамм и час имеют степень больше 1; это алгебраический функциональная декомпозиция. Алгоритмы известны тем, что разлагаются одномерные многочлены в полиномиальное время.

Полиномы, которые разложимы таким образом: составные полиномы; те, которых нет, называются неразложимые многочлены иногда простые многочлены.^[1] (не путать с неприводимые многочлены, чего не может быть разложены на произведения многочленов ).

В оставшейся части статьи обсуждаются только одномерные многочлены; алгоритмы также существуют для многомерных многочленов произвольной степени.^[2]

Примеры

В простейшем случае одним из многочленов является одночлен. Например,

${\displaystyle f=x^{6}-3x^{3}+1}$

разлагается на

${\displaystyle g=x^{2}-3x+1{\text{ and }}h=x^{3}}$

поскольку

${\displaystyle f(x)=(g\circ h)(x)=g(h(x))=g(x^{3})=(x^{3})^{2}-3(x^{3})+1,}$

с использованием символ оператора кольца ∘ обозначать функциональная композиция.

Менее банально,

${\displaystyle {\begin{aligned}&x^{6}-6x^{5}+21x^{4}-44x^{3}+68x^{2}-64x+41\\={}&(x^{3}+9x^{2}+32x+41)\circ (x^{2}-2x).\end{aligned}}}$

Уникальность

Многочлен может иметь различные разложения на неразложимые многочлены, где ${\displaystyle f=g_{1}\circ g_{2}\circ \cdots \circ g_{m}=h_{1}\circ h_{2}\circ \cdots \circ h_{n}}$ куда ${\displaystyle g_{i}\neq h_{i}}$ для некоторых ${\displaystyle i}$. Ограничение в определении на многочлены степени больше единицы исключает бесконечное множество разложений, возможных с линейными многочленами.

Джозеф Ритт доказал, что ${\displaystyle m=n}$, и степени компонентов одинаковы, но, возможно, в разном порядке; это Теорема Ритта о разложении полиномов.^[1][3] Например, ${\displaystyle x^{2}\circ x^{3}=x^{3}\circ x^{2}}$.

Приложения

Полиномиальное разложение может позволить более эффективное вычисление полинома. Например,

${\displaystyle {\begin{aligned}&x^{8}+4x^{7}+10x^{6}+16x^{5}+19x^{4}+16x^{3}+10x^{2}+4x-1\\={}&(x^{2}-2)\circ (x^{2})\circ (x^{2}+x+1)\end{aligned}}}$

можно вычислить только с 3 умножениями, используя разложение, в то время как Метод Хорнера потребуется 7.

Полиномиальное разложение позволяет вычислять символические корни, используя радикалы, даже для некоторых неприводимые многочлены. Этот прием используется во многих системы компьютерной алгебры.^[4] Например, используя разложение

${\displaystyle {\begin{aligned}&x^{6}-6x^{5}+15x^{4}-20x^{3}+15x^{2}-6x-1\\={}&(x^{3}-2)\circ (x^{2}-2x+1),\end{aligned}}}$

корни этого неприводимого многочлена могут быть вычислены как

${\displaystyle 1\pm 2^{1/6},1\pm {\frac {\sqrt {-1\pm {\sqrt {3}}i}}{2^{1/3}}}}$.^[5]

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

${\displaystyle {\begin{aligned}&x^{4}-8x^{3}+18x^{2}-8x+2\\={}&(x^{2}+1)\circ (x^{2}-4x+1)\end{aligned}}}$

дает корни

${\displaystyle 2\pm {\sqrt {3\pm i}}}$^[5]

но прямое применение формула четвертой степени дает эквивалентные результаты, но в форме, которую трудно упрощать и сложно понять:

${\displaystyle 2-{\frac {\sqrt {{9\left({\frac {8{\sqrt {10}}i}{3^{3/2}}}+72\right)^{2/3}+36\left({\frac {8{\sqrt {10}}i}{3^{3/2}}}+72\right)^{1/3}+156} \over {\left({\frac {8{\sqrt {10}}i}{3^{3/2}}}+72\right)^{1/3}}}}{6}}-{{\sqrt {-\left({\frac {8{\sqrt {10}}i}{3^{3/2}}}+72\right)^{1/3}-{{52} \over {3\left({\frac {8{\sqrt {10}}i}{3^{3/2}}}+72\right)^{1/3}}}+8}} \over 2}}$.

Алгоритмы

Первый алгоритм полиномиального разложения был опубликован в 1985 г.^[6] хотя он был открыт в 1976 году^[7] и реализован в Macsyma система компьютерной алгебры.^[8] Этот алгоритм использует экспоненциальное время наихудшего случая, но работает независимо от характеристика лежащих в основе поле.

Более поздние алгоритмы работают за полиномиальное время, но с ограничениями на характеристики.^[9]

Самый последний алгоритм вычисляет разложение за полиномиальное время и без ограничений на характеристику.^[10]

Примечания

1. Дж. Ф. Ритт, "Простые и составные многочлены", Труды Американского математического общества 23: 1: 51–66 (январь 1922 г.) Дои:10.2307/1988911 JSTOR  1988911
2. Жан-Шарль Фогер, Людовик Перре, "Эффективный алгоритм разложения многомерных многочленов и его приложения к криптографии", Журнал символических вычислений, 44:1676-1689 (2009), Дои:10.1016 / j.jsc.2008.02.005
3. Капи Корралес-Родриганьес, "Заметка о теореме Ритта о разложении многочленов", Журнал чистой и прикладной алгебры 68: 3: 293–296 (6 декабря 1990 г.) Дои:10.1016 / 0022-4049 (90) 90086-В
4. Примеры ниже были рассчитаны с использованием Максима.
5. Где каждый ± взят независимо.
6. Дэвид Р. Бартон, Ричард Зиппель, «Алгоритмы полиномиального разложения», Журнал символических вычислений 1:159–168 (1985)
7. Ричард Зиппель, "Функциональная декомпозиция" (1996) полный текст
8. Доступен в его преемнике с открытым исходным кодом, Максима см. polydecomp функция
9. Декстер Козен, Сьюзан Ландау, "Алгоритмы полиномиального разложения", Журнал символических вычислений 7:445–456 (1989)
10. Рауль Бланкерц, «Алгоритм с полиномиальным временем для вычисления всех минимальных разложений полинома», ACM-коммуникации в компьютерной алгебре 48: 1 (выпуск 187, март 2014 г.) полный текст В архиве 2015-09-24 на Wayback Machine

Рекомендации

• Джоэл С. Коэн, "Полиномиальное разложение", глава 5 Компьютерная алгебра и символьные вычисления, 2003, ISBN  1-56881-159-4