Полиномиальное разложение
Факторизация по композиции функций

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

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

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

Примеры

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

ф = х 6 − 3 х 3 + 1 {\displaystyle f=x^{6}-3x^{3}+1}

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

г = х 2 − 3 х + 1  и  час = х 3 {\displaystyle g=x^{2}-3x+1{\text{ и }}h=x^{3}}

с

ф ( х ) = ( г ∘ час ) ( х ) = г ( час ( х ) ) = г ( х 3 ) = ( х 3 ) 2 − 3 ( х 3 ) + 1 , {\displaystyle f(x)=(g\circ h)(x)=g(h(x))=g(x^{3})=(x^{3})^{2}-3(x^{3})+1,}

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

Менее тривиально,

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

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

Многочлен может иметь различные разложения на неразложимые многочлены, где где для некоторых . Ограничение в определении многочленами степени больше единицы исключает бесконечное множество разложений, возможных с линейными многочленами. ф = г 1 ∘ г 2 ∘ ⋯ ∘ г м = час 1 ∘ час 2 ∘ ⋯ ∘ час н {\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 я}

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

Приложения

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

х 8 + 4 х 7 + 10 х 6 + 16 х 5 + 19 х 4 + 16 х 3 + 10 х 2 + 4 х − 1 = ( х 2 − 2 ) ∘ ( х 2 ) ∘ ( х 2 + х + 1 ) {\displaystyle {\begin{align}&x^{8}+4x^{7}+10x^{6}+16x^{5}+19x^{4}+16x^{3}+10x^{2}+4x-1\\={}&\left(x^{2}-2\right)\circ \left(x^{2}\right)\circ \left(x^{2}+x+1\right)\end{align}}}

можно вычислить с помощью 3 умножений и 3 сложений, используя разложение, в то время как метод Горнера потребовал бы 7 умножений и 8 сложений.

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

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

корни этого неприводимого многочлена можно вычислить как [5]

1 ± 2 1 / 6 , 1 ± − 1 ± 3 i 2 1 / 3 . {\displaystyle 1\pm 2^{1/6},1\pm {\frac {\sqrt {-1\pm {\sqrt {3}}i}}{2^{1/3}}}.}

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

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

дает корни [5]

2 ± 3 ± i {\displaystyle 2\pm {\sqrt {3\pm i}}}

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

2 − 9 ( 8 10 i 3 3 / 2 + 72 ) 2 / 3 + 36 ( 8 10 i 3 3 / 2 + 72 ) 1 / 3 + 156 ( 8 10 i 3 3 / 2 + 72 ) 1 / 3 6 − − ( 8 10 i 3 3 / 2 + 72 ) 1 / 3 − 52 3 ( 8 10 i 3 3 / 2 + 72 ) 1 / 3 + 8 2 . {\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 / Maxima . [8] Этот алгоритм занимает экспоненциальное время в худшем случае, но работает независимо от характеристик базового поля .

Алгоритм 1989 года работает за полиномиальное время, но с ограничениями на характеристику. [9]

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

Примечания

  1. ^ ab JF Ritt , «Простые и составные многочлены», Труды Американского математического общества 23 :1:51–66 (январь, 1922) doi :10.2307/1988911 JSTOR  1988911
  2. ^ Жан-Шарль Фожер, Людовик Перре, «Эффективный алгоритм разложения многомерных полиномов и его применение в криптографии», Журнал символических вычислений , 44 :1676-1689 (2009), doi :10.1016/j.jsc.2008.02.005
  3. ^ Капи Корралес-Родриганьес, «Заметка о теореме Ритта о разложении многочленов», Журнал чистой и прикладной алгебры 68 :3:293–296 (6 декабря 1990 г.) doi :10.1016/0022-4049(90)90086-W
  4. ^ Приведенные ниже примеры были рассчитаны с использованием Maxima .
  5. ^ ab Где каждый ± берется независимо.
  6. ^ Дэвид Р. Бартон, Ричард Зиппель (1985). «Алгоритмы полиномиальной декомпозиции». Журнал символических вычислений . 1 (2): 159–168. doi :10.1016/S0747-7171(85)80012-2.
  7. ^ Ричард Зиппель, Функциональная декомпозиция, 1996.
  8. ^ См. функцию полидекомп.
  9. ^ Козен, Декстер ; Ландау, Сьюзен (1989). «Алгоритмы полиномиальной декомпозиции». Журнал символических вычислений . 7 (5): 445–456. CiteSeerX 10.1.1.416.6491 . doi :10.1016/S0747-7171(89)80027-6. 
  10. ^ Рауль Бланкерц (2014). "Алгоритм полиномиального времени для вычисления всех минимальных разложений полинома" (PDF) . ACM Communications in Computer Algebra . 48 (187): 1.Архивировано 24.09.2015 в Wayback Machine

Ссылки

  • Джоэл С. Коэн (2003). "Глава 5. Разложение полиномов". Компьютерная алгебра и символьные вычисления: математические методы . ISBN 1-56881-159-4.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Polynomial_decomposition&oldid=1243173954"