Geometrical properties of polynomial roots

Original article: w:Geometrical properties of polynomial roots

For the computation of polynomial roots, see Real-root isolation and Root-finding algorithm § Roots of polynomials.

수학(mathematics)에서, 실수 또는 복소수 계수를 갖는 차수 n의 일변수 다항식(univariate polynomial)은, 만약 그들의 중복도(multiplicities)와 함께 세어지면, n 복소수 근(roots)을 가집니다. 그들은 복소 평면(complex plane)에서 n 점의 집합을 형성합니다. 이 기사는 이들 점의 기하학, 즉 다항식의 차수와 계수에서 추론될 수 있는 복소 평면에서의 그들의 위치에 관한 정보에 관한 것입니다.

이들 기하학적 속성 중 일부는, 모든 근을 포함하는 디스크를 정의하는, 근의 절댓값에 대한 위쪽 경계, 또는 두 근 사이의 거리에 대한 아래 경계와 같은, 단일 다항식과 관련됩니다. 그러한 경계는 다항식에 대해 근-찾기 알고리듬(root-finding algorithm), 그들을 튜닝하는 것, 또는 그들의 계산 복잡도(computational complexity)를 계산하는 것에 널리 사용됩니다.

일부 다른 속성은, 실수 계수를 갖는 차수 n의 무작위 다항식의 실수 근의 예상된 숫자, 이것은 충분하게 큰 n에 대해 $1+{\frac {2}{\pi }}\ln(n)$보다 적은 것과 같은, 확률적입니다.

이 기사에서, 고려되는 다항식은 항상 다음을 나타냅니다:

$p(x)=a_{0}+a_{1}x+\cdots +a_{n}x^{n},$

여기서 $a_{0},\dots ,a_{n}$는 실수 또는 복소수이고 $a_{n}\neq 0$입니다; 따라서 n은 다항식의 차수입니다.

Continuous dependence on coefficients

차수 n의 다항식의 n 근은 계수에 연속적으로(continuously) 종속됩니다. 단순 근에 대해, 이것은 암시적 함수 정리(implicit function theorem)로부터 직접 결과입니다. 이것은 중복 근에 대해 역시 참이지만, 약간의 주의가 증명에 대해 필요됩니다.

계수의 작은 변화는, 실수 근에서 꽤 큰 허수 부분을 가진 복소수 근으로의 변화를 포함하여, 근의 극적인 변화를 야기할 수 있습니다 (윌킨슨의 다항식(Wilkinson's polynomial)을 참조하십시오). 결과는, 고전적 수치 근-찾기 알고리듬(root-finding algorithm)에 대해, 주어진 계수에서 근을 근사하는 문제는 나쁜-조건(ill-conditioned)이라는 것입니다.

Conjugation

복소수 켤레 근 정리(complex conjugate root theorem)는, 만약 다항식의 계수가 실수이면, 비-실수 근은 형식 (a + ib, a – ib)의 쌍으로 나타난다고 말합니다.

그것은 실수 계수를 가진 다항식의 근은 실수 축에 관해 거울-대칭(mirror-symmetric)임을 따릅니다.

이것은 대수적 켤레(algebraic conjugation)로 확장될 수 있습니다: 유리(rational) 계수를 가진 다항식의 근은 다항식의 갈루아 그룹(Galois group)의 작용 아래에서 켤레(conjugate) (즉, 불변)입니다. 어쨌든, 이 대칭은 기하학적으로 꽤 드물게 해석될 수 있습니다.

Bounds on all roots

다항식 근의 절댓값에 대한 위쪽 경계는 근-찾기 알고리듬(root-finding algorithm)에 대해 널리 사용되며, 근을 검색해야 하는 범위를 제한하는 것, 또는 이들 알고리듬의 계산 복잡도(computational complexity)의 계산에 대해 사용됩니다.

많은 그러한 경계가 주어져 왔고, 더 날카로운 경계는 고려되는 계수의 특성 수열(sequence)에 일반적으로 달려 있습니다. 대부분의 경계는 1보다 크거나 같고, 따라서 오직 1보다 작은 절댓값의 근을 가지는 다항식에 대해 날카롭게 하지 않습니다. 어쨌든 그러한 다항식은, 아래에서 보이는 것처럼, 매우 드뭅니다.

근의 절댓값에 대한 임의의 위쪽 경계는 해당하는 아래쪽 경계를 제공합니다. 사실, 만약 $a_{n}\neq 0$이고 U가 다음의 근의 절댓값의 위쪽 경계이면,

$a_{0}+a_{1}x+\cdots +a_{n}x^{n},$

1/U은 다음의 절댓값의 아래 경계입니다:

$a_{n}+a_{n-1}x+\cdots +a_{0}x^{n},$

왜냐하면 두 다항식의 근은 나머지 하나의 근의 곱셈의 역수이기 때문입니다. 그러므로, 이 기사의 나머지 부분에서, 아래쪽 경계는 명시적으로 제공되지 않을 것입니다.

Lagrange's and Cauchy's bounds

라그랑주(Lagrange)와 코시(Cauchy)는 모든 복소 근에 대한 위쪽 경계를 제공한 최초의 인물들입니다. 라그랑주의 경계는 다음입니다:

$\max \left\{1,\sum _{i=0}^{n-1}\left|{\frac {a_{i}}{a_{n}}}\right|\right\},$

그리고 코시의 경계는 다음입니다:

$1+\max \left\{\left|{\frac {a_{n-1}}{a_{n}}}\right|,\left|{\frac {a_{n-2}}{a_{n}}}\right|,\ldots ,\left|{\frac {a_{0}}{a_{n}}}\right|\right\}$

라그랑주의 경계는, 1이 모든 $\left|{\frac {a_{i}}{a_{n}}}\right|$의 합보다 크지만 가장 큰 것일 때 오직 코시의 경계보다 더 날카롭습니다 (즉, 더 작습니다). 이것은 연습에서 상대적으로 드물고, 코시의 경계가 라그랑주 것보다 더 널리 사용되는지 이유를 설명합니다.

경계 둘 다는 다항식의 동반 행렬(companion matrix)과 그의 전치(transpose)에 적용된 게르시고린 원 정리(Gershgorin circle theorem)로부터 결과입니다. 그들은 기본 방법에 의해 역시 입증될 수 있습니다.

라그랑주의 및 코시의 경계의 증명

만약 z가 다항식의 근이고, |z| ≥ 1이면, 우리는 다음을 가집니다: $|a_{n}||z^{n}|=\left|\sum _{i=0}^{n-1}a_{i}z^{i}\right|\leq \sum _{i=0}^{n-1}|a_{i}z^{i}|\leq \sum _{i=0}^{n-1}|a_{i}||z|^{n-1}.$ $|a_{n}||z|^{n-1}$로 나누면 우리는 다음을 얻습니다: $|z|\leq \sum _{i=0}^{n-1}{\frac {|a_{i}|}{|a_{n}|}},$ 이것은 1보다 더 큰 절댓값의 적어도 하나의 근일 때 라그랑주의 경계입니다. 그렇지 않으면, 1은 근에 대한 경계이고, 라그랑주의 경계보다 더 크지 않습니다. 비슷하게, 코시의 경계에 대해, 우리는, 만약 |z| ≥ 1이면, 다음을 가집니다: $|a_{n}||z^{n}|=\left|\sum _{i=0}^{n-1}a_{i}z^{i}\right|\leq \sum _{i=0}^{n-1}|a_{i}z^{i}|\leq \max |a_{i}|\sum _{i=0}^{n-1}|z|^{i}={\frac {|z|^{n}-1}{|z|-1}}\max |a_{i}|\leq {\frac {|z|^{n}}{|z|-1}}\max |a_{i}|.$ 따라서 $|a_{n}|(|z|-1)\leq \max |a_{i}|.$ |z|에서 풀면, 우리는 만약 1보다 더 큰 절댓값의 근이 있으면 코시의 경계를 얻습니다. 그렇지 않으면, 경계는 역시 정확한데, 왜냐하면 코시의 경계는 1보다 더 크기 때문입니다.

이들 경계는 스케일링에 의해 불변이 아닙니다. 즉, 다항식 p(sx)의 근은 p의 근의 s에 의한 몫이고, p(sx)의 근에 대해 주어진 경계는 p의 경계의 s에 의한 몫이 아닙니다. 따라서, 우리는 가능한 스케일링에 걸쳐 최소화함으로써 더 날카로운 경계를 얻을 것입니다. 이것은, 라그랑주의 및 코시의 경계에 대해, 각각, 다음을 제공합니다:

$\min _{s\in \mathbb {R} _{+}}\left(\max \left\{s,\sum _{i=0}^{n-1}\left|{\frac {a_{i}}{a_{n}}}\right|s^{i-n+1}\right\}\right),$

및

$\min _{s\in \mathbb {R} _{+}}\left(s+\max _{0\leq i\leq n-1}\left(\left|{\frac {a_{i}}{a_{n}}}\right|s^{i-n+1}\right)\right)$.

원래 라그랑주에 의해 주어졌지만, 도널드 커누스(Donald Knuth)에 의해 차센하우스에 공헌된, 또 다른 경계는 다음입니다:

$2\max \left\{\left|{\frac {a_{n-1}}{a_{n}}}\right|,\left|{\frac {a_{n-2}}{a_{n}}}\right|^{1/2},\ldots ,\left|{\frac {a_{0}}{a_{n}}}\right|^{1/n}\right\}.$

이 경계는 스케일링에 의해 불변입니다.

선행 경계의 증명

A를 0 ≤ i < n에 대해 가장 큰 $\left|{\frac {a_{i}}{a_{n}}}\right|^{\frac {1}{n-i}}$인 것으로 놓습니다. 따라서 우리는 $0\leq i<n$에 대해 다음을 가집니다: ${\frac {|a_{i}|}{|a_{n}|}}\leq A^{n-i}$. 만약 z가 p의 근이면, 우리는 다음을 가집니다: $-a_{n}z^{n}=\sum _{i=0}^{n-1}a_{i}z^{i},$ 따라서, $a_{n}$으로 나눈 후에, ${\begin{aligned}|z|^{n}&\leq \sum _{i=0}^{n-1}A^{n-i}|z|^{i}\\&=A{\frac {|z|^{n}-A^{n}}{|z|-A}}.\end{aligned}}$ 우리는 |z| ≤ 2A을 입증하기를 원하므로, 우리는 |z| > A임을 가정할 것입니다 (그렇지 않으면 입증할 것이 없습니다). 따라서 $|z|^{n}\leq A{\frac {|z|^{n}}{|z|-A}},$ 이것은 결과를 제공하는데, 왜냐하면 $|z|>A$이기 때문입니다.

라그랑주는 이 후자가 다음 수열에서 두 개의 가장 큰 값 (같을 수 있음)의 합으로 개선해 왔습니다:

$\left[\left|{\frac {a_{n-1}}{a_{n}}}\right|,\left|{\frac {a_{n-2}}{a_{n}}}\right|^{1/2},\ldots ,\left|{\frac {a_{0}}{a_{n}}}\right|^{1/n}\right].$

라그랑주는 역시 다음 경계를 제공했습니다

$\sum _{i}\left|{\frac {a_{i}}{a_{i+1}}}\right|,$

여기서 $a_{i}$는, 다항식의 항이 증가하는 차수로 정렬될 때, i번째 비-영 계수를 나타냅니다.

Using Hölder's inequality

횔더 부등식(Hölder's inequality)은 모든 각 h-노름에 대한 라그랑주의 및 코시의 경계로 확장을 허용합니다. 다음 수열

$s=(a_{0},\ldots ,a_{n})$

의 h-노름은 임의의 실수 h ≥ 1에 대해 다음이고:

$\|s\|_{h}=\left(\sum _{i=1}^{n}|a_{i}|^{h}\right)^{1/h},$

다음입니다:

$\|s\|_{\infty }=\textstyle {\max _{i=1}^{n}}|a_{i}|.$

만약 1 ≤ h, k ≤ ∞을 갖는 ${\frac {1}{h}}+{\frac {1}{k}}=1$이고, 1 / ∞ = 0이면, p의 근의 절댓값에 대한 위쪽 경계는 다음입니다:

${\frac {1}{|a_{n}|}}\left\|(|a_{n}|,\left\|(|a_{n-1}|,\ldots ,|a_{0}|\right)\|_{h}\right)\|_{k}.$

k = 1 및 k = ∞에 대해, 우리는 각각 코시의 및 라그랑주의 경계를 얻습니다.

h = k = 1/2에 대해, 우리는 다음 경계를 가집니다:

${\frac {1}{|a_{n}|}}{\sqrt {|a_{n}|^{2}+|a_{n-1}|^{2}+\cdots +|a_{0}|^{2}}}.$

이것은 근의 절댓값의 경계일뿐 아니라, 1보다 더 큰 그들의 절댓값의 곱의 경계입니다; 아래의 § Landau's inequality를 참조하십시오.

증명

z를 다음 다항식의 근으로 놓습니다: $p(x)=a^{n}+a_{n-1}x^{n-1}+\cdots +a_{1}x+a_{0}.$ 다음을 설정하면: $A=\left({\frac {|a_{n-1}|}{|a_{n}|}},\ldots ,{\frac {|a_{1}|}{|a_{n}|}},{\frac {|a_{0}|}{|a_{n}|}}\right),$ 우리는 p의 모든 각 근 z 가 다음을 만족시킴을 입증해야 합니다: $z\leq \left\|(1,\left\|A\right\|_{h}\right)\|_{k}.$ 만약 $|z|\leq 1$이면, 부등식은 참입니다; 그래서, 우리는 증명에 나머지 부분에 대해 $|z|>1$을 가정할 것입니다. 방정식을 다음으로 쓰면: $-z^{n}={\frac {a_{n-1}}{a_{n}}}z^{n-1}+\cdots +{\frac {a_{1}}{a_{n}}}z+a_{0},$ 훨더의 부등식(Hölder's inequality)은 다음임을 의미합니다: $|z|^{n}\leq \|A\|_{h}\cdot \left\|(z^{n-1},\ldots ,z,1)\right\|_{k}.$ 만약 k = 1이면, 이것은 다음입니다: $|z|^{n}\leq \|A\|_{1}\max \left\{|z|^{n-1},\ldots ,|z|,1\right\}=\|A\|_{1}|z|^{n-1}.$ 따라서 $|z|\leq \max\{1,\|A\|_{1}\}.$ 경우 1 < k ≤ ∞에서, 기하 진행(geometric progression)에 대해 합 공식은 다음을 제공합니다: $|z|^{n}\leq \|A\|_{h}\left(|z|^{k(n-1)}+\cdots +|z|^{k}+1\right)^{\frac {1}{k}}=\|A\|_{h}\left({\frac {|z|^{kn}-1}{|z|^{k}-1}}\right)^{\frac {1}{k}}\leq \|A\|_{h}\left({\frac {|z|^{kn}}{|z|^{k}-1}}\right)^{\frac {1}{k}}.$ 따라서 $|z|^{kn}\leq \left(\|A\|_{h}\right)^{k}{\frac {|z|^{kn}}{|z|^{k}-1}},$ 이것은 다음으로 단순화됩니다: $|z|^{k}\leq 1+\left(\|A\|_{h}\right)^{k}.$ 따라서, 모든 경우에서 다음입니다: $|z|\leq \left\|\left(1,\|A\|_{h}\right)\right\|_{k},$ 이것은 증명을 완성합니다.

Other bounds

모든 근의 크기에 대해 많은 다른 위쪽 경계는 제공되어 왔습니다.

후지와라(Fujiwara)의 경계

$2\,\max \left\{\left|{\frac {a_{n-1}}{a_{n}}}\right|,\left|{\frac {a_{n-2}}{a_{n}}}\right|^{\frac {1}{2}},\ldots ,\left|{\frac {a_{1}}{a_{n}}}\right|^{\frac {1}{n-1}},\left|{\frac {a_{0}}{2a_{n}}}\right|^{\frac {1}{n}}\right\},$ 

은 최댓값의 두 마지막 인수를 나눔으로써 위의 주어진 경계를 약간 개선합니다.

코지마(Kojima)의 경계는 다음입니다

$2\,\max \left\{\left|{\frac {a_{n-1}}{a_{n}}}\right|,\left|{\frac {a_{n-2}}{a_{n-1}}}\right|,\ldots ,\left|{\frac {a_{0}}{2a_{1}}}\right|\right\},$

여기서 $a_{i}$는, 다항식의 근이 증가하는 차수로 정렬될 때, i번째 비-영 계수를 나타냅니다. 만약 모든 계수가 비-영이면, 후지오라의 경계는 더 날카로운 것인데, 왜냐하면 후지와라의 경계에서 각 원소는 코지마의 경계에서 첫 번째 원소의 기하 평균(geometric mean)이기 때문입니다.

선(Sun)과 히시(Hsieh)는 코시의 경계에 대한 또 다른 개선점을 얻었습니다. 다항식이 일반 항 a_ixⁱ를 갖는 모닉이라고 가정합니다. 선과 히시는 위쪽 경계 1 + d₁ 및 1 + d₂는 다음 방정식으로부터 얻어질 수 있음을 보였습니다.

$d_{1}={\tfrac {1}{2}}\left((|a_{n-1}|-1)+{\sqrt {(|a_{n-1}|-1)^{2}+4a}}\right),\qquad a=\max\{|a_{i}|\}.$

d₂는 다음 삼차 방정식의 양의 근입니다:

$Q(x)=x^{3}+(2-|a_{n-1}|)x^{2}+(1-|a_{n-1}|-|a_{n-2}|)x-a,\qquad a=\max\{|a_{i}|\}$

그들은 d₂ ≤ d₁임을 역시 주목했습니다.

Landau's inequality

먼저의 경계는 분리된 각 근에 대해 위쪽 경계입니다. 란다우의 부등식(Landau's inequality)은 1보다 큰 절댓값을 가지는 근의 곱의 절댓값에 대해 위쪽 경계를 제공합니다. 에드문트 란다우(Edmund Landau)에 의해 1905년에 발견된, 이 부등식은 20세기 동안 적어도 3번은 잊혀지고 재-발견되어 왔습니다.

근의 곱의 이 경계는 분리된 각 근의 최선의 선행 경계보다 훨씬 더 크지는 않습니다. $z_{1},\ldots ,z_{n}$을 다항식 p의 n 근으로 놓습니다. 만약 다음

$M(p)=|a_{n}|\prod _{j=1}^{n}\max(1,|z_{j}|)$

이 p의 말라 측정(Mahler measure)이면,

$M(p)\leq {\sqrt {\sum _{k=0}^{n}|a_{k}|^{2}}}.$

놀랍게도, 근의 1보다 큰 절댓값의 곱의 이 경계는 단일 근에 대해 위에서 주어져 왔던 하나의 근의 최상의 경계보다 훨씬 더 크지는 않습니다. 이 경계는 훨더의 부등식을 사용하여 얻어지는 경계의 하나와 심지어 정확히 같습니다.

이 경계는 정수 계수를 가진 다항식의 약수의 계수를 경계짓기 위해 역시 유용합니다: 만약 다음

$q=\sum _{k=0}^{m}b_{k}x^{k}$

이 p의 약수이면,

$|b_{m}|\leq |a_{n}|,$

및, 비에타의 공식(Vieta's formulas)에 의해, i = 0, ..., m에 대해,

${\frac {|b_{i}|}{|b_{m}|}}\leq {\binom {m}{i}}{\frac {M(p)}{|a_{n}|}},$

여기서 ${\binom {m}{i}}$는 이항 계수(binomial coefficient)입니다. 따라서,

$|b_{i}|\leq {\binom {m}{i}}M(p)\leq {\binom {m}{i}}{\sqrt {\sum _{k=0}^{n}|a_{k}|^{2}}},$

및

$\sum _{i=0}^{m}|b_{k}|\leq 2^{m}M(p)\leq 2^{m}{\sqrt {\sum _{k=0}^{n}|a_{k}|^{2}}}.$

Discs containing some roots

From Rouché theorem

루셰의 정리(Rouché's theorem)는 영을 중심으로 둔 디스크를 정의하고 근의 주어진 숫자를 포함하는 것을 허용합니다. 보다 정확하게, 만약 다음을 만족하는

$|a_{k}|R^{k}>|a_{0}|+\cdots +|a_{k-1}|R^{k-1}+|a_{k+1}|R^{k+1}+\cdots +|a_{n}|R^{n}$

양의 실수 R과 정수 0 ≤ k ≤ n이 있으면, R보다 작은 절댓값의, 중복도와 함께 세어진, 정확하게 k 근이 있습니다.

증명
만약 $|z|=R$이면, 다음입니다: ${\begin{aligned}|a_{0}&+\cdots +a_{k-1}z^{k-1}+a_{k+1}z^{k+1}+\cdots +a_{n}z^{n}|\\&\leq |a_{0}|+\cdots +|a_{k-1}|R^{k-1}+|a_{k+1}|R^{k+1}+\cdots +|a_{n}|R^{n}\\&\leq |a_{k}|R^{k}\leq |a_{k}z^{k}|.\end{aligned}}$ 루셰의 정리에 의해, 이것은 $p(z)$ 및 $z^{k}$가 중복도와 함께 세어진, R보다 작은 절댓값의 근의 같은 숫자를 가짐을 직접적으로 의미합니다. 이 숫자는 k이므로, 그 결과는 입증됩니다.

위의 결과는, 만약 다음 다항식

$h_{k}(x)=|a_{0}|+\cdots +|a_{k-1}|x^{k-1}-|a_{k}|x^{k}+|a_{k+1}|x^{k+1}+\cdots +|a_{n}|x^{n}$

이 x의 일부 양의 실수 값에 대해 음의 값을 취하면, 적용될 수 있을 것입니다.

이 섹션의 남아있는 부분에서, a₀ ≠ 0임을 가정합니다. 만약 그것이 그 경우가 아니면, 영은 근이고, 다른 근의 위치는, 비-영 상수 항을 갖는 다항식을 얻는 것에 대해, 다항식을 불확정의 거듭-제곱으로 나눔으로써 연구될 수 있을 것입니다. 0이 아닌 상수 항을 갖는 다항식.

k = 0 및 k = n에 대해, 데카르트의 부호의 규칙(Descartes' rule of signs)은 다항식은 정확하게 하나의 양의 실수 근을 가짐을 보입니다. 만약 $R_{0}$와 $R_{n}$은 이들 근이면, 위의 결과는 모든 근이 다음임을 보입니다:

$R_{0}\leq |z|\leq R_{1}.$

이들 부등식은 $h_{0}$ 및 $h_{n}$에 역시 적용하고, 이들 경계는 그들의 계수의 절댓값의 주어진 수열과 함께 다항식에 대해 최적입니다. 그들은 따라서 이전 섹션에서 주어진 모든 경계보다 더 날카롭습니다.

0 < k < n에 대해, 데카르트의 부호의 규칙은, $h_{k}(x)$는 중복이 아닌 두 양의 실수 근을 가지는 것 또는 x의 모든 각 양의 값에 대해 비-음의 것 중에 하나입니다. 그래서, 위의 결과는 첫 번째 경우에서 오직 적용될 수 있을 것입니다. 만약 $R_{k,1}<R_{k,2}$는 이들 두 근이면, 위의 결과는 p의 k 근에 대해 다음

$|z|\leq R_{k,1}$

임을 의미하고, n – k 다른 근에 대해, 다음임을 의미합니다:

$|z|\geq R_{k,2}$.

분명하게 $R_{k,1}$과 $R_{k,2}$을 계산하는 것 대신에, 그것은 $h_{k}(R_{k})<0$ (필연적으로 $R_{k,1}<R_{k}<R_{k,2}$)을 만족하는 값 $R_{k}$를 계산하기 위해 일반적으로 충분입니다. 이들 $R_{k}$는 그들의 절댓값의 관점에서 구별하는 근의 속성을 가집니다: 만약, h < k에 대해, $R_{h}$와 $R_{k}$ 둘 다가 존재하면, $R_{h}<|z|<R_{k}$를 만족하는 정확하게 k – h 근 z가 있습니다.

$R_{k}$를 계산하는 것에 대해, 우리는 ${\frac {h(x)}{x^{k}}}$가 볼록 함수(convex function) (그의 이차 도함수가 양수입니다)임을 사용할 수 있습니다. 따라서 $R_{k}$가 존재하는 것과 ${\frac {h(x)}{x^{k}}}$가 그의 고유한 최솟값에서 음수인 것은 필요충분 조건입니다. 이 최솟값을 계산하는 것에 대해, 우리는 임의의 최적화(optimization) 방법, 또는, 대안적으로, ${\frac {h(x)}{x^{k}}}$의 도함수의 고유한 양의 영을 계산하는 것에 대해 뉴턴의 방법(Newton's method)을 사용할 수 있습니다 (그것은 빠르게 수렴하는데, 왜냐하면 그 도함수는 단조적 함수(monotonic function)이기 때문입니다).

우리는 당들랭–그래프 반복(Dandelin–Graeffe iteration)의 제곱하는 연산을 근에 적용함으로써 존재하는 $R_{k}$의 숫자를 증가할 수 있습니다. 만약 근이 구별되는 절댓값을 가지면, 우리는 결국 그들의 절댓값의 관점에서 근을 완전히 분리할 수 있으며, 즉 k = 1, ..., n에 대해 열린 구간 $(R_{k-1},R_{k})$에서 절댓값을 갖는 정확히 하나의 근이 있는 것을 만족하는 n + 1 양의 숫자 $R_{0}<R_{1}<\dots <R_{n}$를 계산하는 것입니다.

From Gershgorin circle theorem

라그랑주 보간(Lagrange interpolation)과 관련된 기저 위에 다항식의 동반 행렬(companion matrix)을 적용한 게르시고린 원 정리(Gershgorin circle theorem)는 보간 점에 중심을 둔 디스크와 다항식의 근을 포함하는 각각을 제공합니다; 자세한 것에 대해 Durand–Kerner method § Root inclusion via Gerschgorin's circles을 참조하십시오.

만약 보간 점이 다항식의 근에 가까우면, 디스크의 반지름은 작고, 이것은 다항식 근을 계산하는 것에 대해 듀랜드–커너 방법의 핵심 요소입니다.

Bounds of real roots

실수 계수를 갖는 다항식에 대해, 종종 오직 실수 근을 경계짓는 것이 유용합니다. p(x)의 음의 근이 p(–x)의 양의 근이므로, 양의 근을 경계짓는 것에 충분합니다.

분명하게, 모든 근의 모든 각 경계는 실수 근에 역시 적용됩니다. 그러나 일부 문맥에서, 실수 근의 더 엄격한 경계가 유용합니다. 예를 들어, 실수-근 격리(real-root isolation)에 대해 연속된 분수의 방법(method of continued fractions)의 효율성은 양의 근의 경계의 견고성에 강하게 좌우됩니다. 이것은 모든 근의 일반적인 경계보다 더 견고한 새로운 경계를 설립하는 것으로 이어집니다. 이들 경계는 일반적으로 계수의 절댓값의 관점뿐만 아니라, 그들의 부호의 관점에서 표현됩니다.

다른 경계는 그것의 모든 근이 실수인 다항식에 오직 적용됩니다 (아래를 참조하십시오).

Bounds of positive real roots

양수 근의 경계를 지정하기 위해, 우리는 모든 계수의 부호가 변경해도 근이 변경되지 않기 때문에, 일반성의 손실 없이 $a_{n}>0$을 가정할 수 있습니다.

다음의 양수 근의 모든 각 위쪽 경계는

$q(x)=a_{n}x^{n}+\sum _{i=0}^{n-1}\min(0,a_{i})x^{i}$

역시 다음의 실수 영들에 대해 경계입니다:

$p(x)=\sum _{i=0}^{n}a_{i}x^{i}$.

사실, 만약 B가 그러한 경계이면, 모든 x > B에 대해, 우리는 p(x) ≥ q(x) > 0을 가집니다.

코시의 경계에 적용되면, 이것은 실수 계수를 갖는 다항식의 실수 근에 대해 다음 위쪽 경계를 제공합니다:

$1+{\textstyle \max _{i=0}^{n-1}}{\frac {-a_{i}}{a_{n}}}$.

만약 이 경계가 1보다 크지 않으면, 이것은 모든 비-영 계수가 같은 부호를 가지고, 양수 근이 있지 않음을 의미합니다.

유사하게, 양수 근의 또 다른 이쪽 경계는 다음입니다:

$2\,{\max _{a_{i}a_{n}<0}}\left({\frac {-a_{i}}{a_{n}}}\right)^{\frac {1}{n-i}}.$

만약 모든 비-영 계수가 같은 부호를 가지면, 양수 근이 없고, 최댓값은 영으로 정의되어야 합니다.

다른 경계는 주로 실수-근 분리(real-root isolation)에 대해 연속된 분수의 방법(method of continued fractions)의 필요성에 대해 최근에 개발되어 왔습니다.

Polynomials whose roots are all real

만약 다항식의 모든 근이 실수이면, 라게르(Laguerre)는 현재 사무엘슨의 부등식(Samuelson's inequality)이라고 불리는 것을 사용함으로써 근의 따라오는 아래쪽 경계와 위쪽 경계를 입증했습니다.

$\sum _{k=0}^{n}a_{k}x^{k}$를 모두 실수 근을 갖는 다항식으로 놓습니다. 그런-다음 그것의 근은 다음 끝점을 갖는 구간 안에 위치됩니다:

$-{\frac {a_{n-1}}{na_{n}}}\pm {\frac {n-1}{na_{n}}}{\sqrt {a_{n-1}^{2}-{\frac {2n}{n-1}}a_{n}a_{n-2}}}.$

예를 들어, 다항식 $x^{4}+5x^{3}+5x^{2}-5x-6=(x+3)(x+2)(x+1)(x-1)$의 근은 다음을 만족시킵니다:

$-3.8118<-{\frac {5}{4}}-{\frac {3}{4}}{\sqrt {\frac {35}{3}}}\leq x\leq -{\frac {5}{4}}+{\frac {3}{4}}{\sqrt {\frac {35}{3}}}<1.3118.$

Root separation

다항식의 근 분리(root separation)는 두 근 사이의 최소 거리, 즉 두 근의 차이의 절댓값의 최솟값입니다:

$\operatorname {sep} (p)=\min\{|\alpha -\beta |\;;\;\alpha \neq \beta {\text{ and }}p(\alpha )=p(\beta )=0\}$

근 분리는 다항식에 대한 근-찾기 알고리듬(root-finding algorithm)의 계산 복잡도(computational complexity)의 기본 매개변수입니다. 사실, 근 분리는 서로 다른 근을 확실히 구별하기 위해 필요한 숫자 표현의 정밀도를 결정합니다. 역시, 실수 근-분리(real-root isolation)에 대해, 그것은 모든 근을 분리하는 데 필요한 구간 분할의 숫자를 경계짓는 것을 허용합니다.

실수 또는 복소수 계수를 갖는 다항식에 대해 차수와 오직 계수의 절댓값의 관점에서 근 분리의 아래쪽 경계를 표현할 수 없는데, 왜냐하면 단일 계수의 작은 변화가 작은 근 분리와 본질적으로 계수의 작은 절댓값을 갖는 제곱-없는 다항식(square-free polynomial)에서 중복 근을 갖는 다항식을 변환하기 때문입니다. 어쨌든, 다항식의 판별식(discriminant)을 포함하면 아래 경계를 허용합니다.

정수 계수를 갖는 제곱-없는 다항식에 대해, 판별식은 정수이고, 따라서 1보다 작지 않은 절댓값을 가집니다. 이것은 판별식과 독립적인 근 분리에 대한 아래쪽 경계를 허용합니다.

Mignotte의 분리 경계는 다음입니다:

$\operatorname {sep} (p)>{\frac {{\sqrt {3}}\Delta (p)}{n^{n/2+1}(\|p\|_{2})^{n-1}}},$

여기서 $\Delta (p)$는 판별식이고, $\textstyle \|p\|_{2}={\sqrt {a_{0}^{2}+a_{1}^{2}+\dots +a_{n}^{2}}}$입니다.

정수 계수를 갖는 제곱-없는 다항식에 대해, 이것은 다음을 의미합니다:

$\operatorname {sep} (p)>{\frac {\sqrt {3}}{n^{n/2+1}(\|p\|_{2})^{n-1}}}>{\frac {1}{2^{2s^{2}}}},$

여기서 s는 p의 비트(bit) 크기, 즉 그것의 계수의 비트크기의 합입니다.

Gauss–Lucas theorem

Main article: Gauss–Lucas theorem

가우스-루카스 정리는 다항식의 근의 볼록 껍질(convex hull)이 다항식의 도함수(derivative)의 근을 포함한다고 말합니다.

때때로 유용한 따름정리는, 만약 다항식의 모든 근이 양의 실수 부분을 가지면, 다항식의 모든 도함수의 근도 마찬가지라는 것입니다.

관련된 결과는 베른슈타인의 부등식(Bernstein's inequality)입니다. 그것은 도함수 P′를 갖는 차수가 n의 다항식 P에 대해 우리가 다음을 가짐을 말합니다:

$\max _{|z|\leq 1}{\big |}P'(z){\big |}\leq n\max _{|z|\leq 1}{\big |}P(z){\big |}.$

Statistical distribution of the roots

만약 무작위 다항식의 계수 a_i가 영의 평균(mean)을 갖는 독립적이고 동일하게 분포되면, 대부분의 복소수 근은 단위 원에 있거나 단위 원에 가깝습니다. 특히, 실수 근은 대부분 ±1 부근에 위치하고, 게다가, 그것들의 예상된 숫자는, 큰 차수에 대해, 차수의 자연 로그(natural logarithm)보다 작습니다.

만약 계수가 영의 평균과 σ의 분산(variance)을 갖는 가우스 분포(Gaussian distributed)이면, 실수 근의 평균 밀도는 Kac 공식으로 제공됩니다:

$m(x)={\frac {\sqrt {A(x)C(x)-B(x)^{2}}}{\pi A(x)}}$

여기서

${\begin{aligned}A(x)&=\sigma \sum _{i=0}^{2n-1}x^{i}=\sigma {\frac {x^{2n}-1}{x-1}},\\B(x)&={\frac {1}{2}}{\frac {d}{dx}}A(x),\\C(x)&={\frac {1}{4}}{\frac {d^{2}}{dx^{2}}}A(x)+{\frac {1}{4x}}{\frac {d}{dx}}A(x).\end{aligned}}$

계수가 비-영 평균과 σ의 분산을 갖는 가우스 분포이면, 유사하지만 더 복잡한 공식이 알려져 있습니다.

Real roots

큰 n에 대해, x 근처의 실수 근의 평균 밀도는 만약 $x^{2}-1\neq 0$이고 다음이면,

$m(\pm 1)={\frac {1}{\pi }}{\sqrt {\frac {n^{2}-1}{12}}}$

점근적으로 다음입니다:

$m(x)={\frac {1}{\pi |1-x^{2}|}}$.

그것은 실수 근의 예상된 숫자가 큰 O 표기법(big O notation)을 사용하여 다음임을 따릅니다:

$N_{n}={\frac {2}{\pi }}\ln n+C+{\frac {2}{\pi n}}+O(n^{-2})$

여기서 C는 근사적으로 0.6257358072와 같은 상수입니다.

다시 말해서, 높은 차수의 무작위 다항식의 실수 근의 예상된 숫자는 차수의 자연 로그보다 작습니다.

Kac, Erdös, 및 다른 사람들은 이들 결과가 만약 그것들이 독립적이고 평균 영을 갖는 같은 분포를 가지면 계수의 그 분포에 둔감하다는 것을 보여주었습니다. 어쨌든, 만약 i-번째 계수의 분산이 ${\binom {n}{i}}$와 같으면, 실수 근의 예상된 숫자는 ${\sqrt {n}}$입니다.

See also

• Descartes' rule of signs
• Marden's theorem
• Newton's identities
• Quadratic function#Upper bound on the magnitude of the roots
• Real-root isolation
• Root-finding of polynomials
• Square-free polynomial
• Vieta's formulas

References

• Rahman, Q. I.; Schmeisser, G. (2002). Analytic theory of polynomials. London Mathematical Society Monographs. New Series. Vol. 26. Oxford: Oxford University Press. ISBN 0-19-853493-0. Zbl 1072.30006.
• Yap, Chee-Keng (2000). Fundamental problems of algorithmic algebra (PDF). Oxford University Press. ISBN 978-0195125160. {{cite book}}: Invalid |ref=harv (help).

External links

• The beauty of the roots, a visualization of the distribution of all roots of all polynomials with degree and integer coefficients in some range.