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

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

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

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

Примеры

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

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

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

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

с

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

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

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

${\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}}$

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

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

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

Приложения

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

${\begin{aligned}&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{aligned}}$

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

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

${\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}}$

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

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

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

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

дает корни

$2\pm {\sqrt {3\pm i}}$

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

$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 году. хотя он был обнаружен в 1976 году, и реализован в Macsyma / Maxima системе компьютерной алгебры . В худшем случае этот алгоритм требует экспоненциального времени, но работает независимо от характеристик основного поля .

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

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

Ссылки

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