다항식 분해

수학에서 다항식 분해는 다항식 f를 다항식 g와 h의 함수 구성 $g{\displaystyle }$ ${\displaystyle \circ }$ ${\displaystyle h}$ ${\displaystyle g\circle h}$으로 표현하는데, 여기서 g와 h는 1보다 큰 학위를 가지고 있다. 대수적 함수 분해다.알고리즘은 다항식 시간에 단항 다항식을 분해하는 것으로 알려져 있다.null

이러한 방식으로 분해할 수 있는 다항식은 복합 다항식이다. 외설적인 다항식 또는 때로는 주요 다항식^[1](다항식 제품으로는 고려할 수 없는 불가침 다항식과 혼동되지 않음)이 아니다.null

이 글의 나머지 부분에서는 단변 다항식만을 논하고 있으며, 임의 수준의 다항 다항식에도 알고리즘이 존재한다.^[2]null

예

가장 간단한 경우, 다항식 중 하나는 단항식이다.예를 들어,

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

로 분해되다.

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

그 이후

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

함수 구성을 나타내기 위해 링 오퍼레이터 기호 ∘을 사용한다.null

좀 더 사소한 것은 아니지만,

${\displaystyle {\signified}&x^{6}-6x^{5}+21x^{4}-44x^{3}+68x^{2}-64x+41\\={}&(x^{3}+9x^{2}+32x41)\caps(x^{2-2x)\c)\x(x)\x)\x)\x(x)\x)\x^(x2x2x)\x)\x)\x)\x2x2x2x.\end{정렬}}}$

유니크함

A polynomial may have distinct decompositions into indecomposable polynomials where ${\displaystyle f=g_{1}\circ g_{2}\circ \cdots \circ g_{m}=h_{1}\circ h_{2}\circ \cdots \circ h_{n}}$ where ${\displaystyle g_{i}\neq h_{i}}$ for some ${\displ$$aystyle i}$.1도 이상의 다항식 정의에 대한 제한은 선형 다항식으로 가능한 무한히 많은 분해물을 제외한다.null

조셉 $릿$은${\displaystyle }$m = ${\displaystyle n}$ ${\displaystyle$m=$n}$, 그리고 성분의 정도가 선형 변환까지는 같지만 순서는 다를 수 있다는 것을 증명했다; 이것이 리트의 다항식 분해 정리다.^[1][3]예를 들어 $x{\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$∘ ${\displaystyle {}^{}}$ ${\displaystyle {3\mathrm{}}^{}}$= x ${\displaystyle {3\mathrm{}}^{}}$ ${\displaystyle {}^{}}$ x ${\displaystyle {2\mathrm{}}^{}}$ ${\$ x$^{2}\circle 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\\={}&\left(x^{2}-2\right)\circ \left(x^{2}\right)\circ \left(x^{2}+x+1\right)\end{aligned}}}$

Horner의 방법은 7이 필요한 반면, 분해법을 사용하여 3 곱으로만 계산할 수 있다.

다항식 분해는 일부 수정 불가능한 다항식에도 불구하고 활성산소를 사용하여 상징 뿌리를 계산할 수 있다.이 기술은 많은 컴퓨터 대수 체계에서 사용된다.^[4]예를 들어 분해 사용

${\displaystyle {\just+{6x^{6}-6x^{5}+15x^{4}-20x^{3}+15x^{2}-6x-1\\\={}&\\\\}\ft(x^{3}-2x1\오른쪽)\reput \reftend(x^{ned}}}}}})}$

이 수정 불가능한 다항식의 뿌리는 다음과^[5] 같이 계산할 수 있다.

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

뿌리에 대한 명시적인 공식이 있는 사분위 다항식의 경우에도 분해를 이용한 해결은 더 간단한 형태를 주는 경우가 많다.예를 들어, 분해

${\displaystyle {\cHB{x^}{4}-8x^{3}+18x^{2}-8x+2\\={}&(x^{2}+1)\nd(x^{2}-4x+1)\ediated}}}}}}$

뿌리를^[5] 내리다

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

그러나 4분위 공식을 쉽게 적용하면 동일한 결과를 얻을 수 있지만 단순화하기가 어렵고 이해하기 어려운 형식이다.

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

알고리즘

다항식 분해를 위한 최초의 알고리즘은 1976년에 발견되었지만 1985년에 발표되었고,^[7] 맥시마/맥시마 컴퓨터 대수 체계에서 구현되었다.^[6][8]그 알고리즘은 최악의 경우 기하급수적인 시간이 걸리지만, 기반 영역의 특성과는 독립적으로 작동한다.null

1989년 알고리즘은 다항식 시간에 실행되지만 특성에 제약이 있다.^[9]null

2014년 알고리즘은 특성에 대한 제한 없이 다항 시간 내에 분해물을 계산한다.^[10]null

메모들

참조

• Joel S. Cohen (2003). "Chapter 5. Polynomial Decomposition". Computer Algebra and Symbolic Computation. ISBN 1-56881-159-4.