리얼루트 격리

수학에서, 그리고 보다 구체적으로, 수학적 분석과 컴퓨터 대수에서, 다항식의 실질 뿌리 격리는, 다항식의 각각 (그리고 단 하나) 진짜 뿌리를 포함하는 실선의 분리 간격을 생성하는 것으로 구성된다.

다항식의 실제 뿌리를 계산하기 위한 통상적인 뿌리 찾기 알고리즘이 일부 실제 뿌리를 산출할 수는 있지만, 일반적으로 모든 진짜 뿌리를 찾았다는 것을 증명할 수는 없기 때문에 진짜 뿌리 격리가 유용하다.특히 이런 알고리즘이 루트를 찾지 못하면 실제 루트가 없기 때문에 그런 것인지 알 수 없다.일부 알고리즘은 모든 복잡한 루트를 계산하지만, 일반적으로 복잡한 루트보다 실제 루트가 훨씬 적기 때문에, 대부분의 계산 시간은 일반적으로 비현실 루트 계산에 소비된다(평균적으로 도 $n$ 의 다항식은 $복잡한$ 루트가 n개 있고, $로그$ n $실제$ 루트가 있을 뿐이다; 다항식 루트 § Real 루트의 기하학적 속성 참조).더구나 상상의 부분이 작은 비현실적 뿌리와 실제 뿌리를 구별하기가 어려울 수 있다(다음 절의 윌킨슨의 다항식의 예 참조).

최초의 완전한 실질-루트 격리 알고리즘은 스투름의 정리(1829년)에서 비롯된다.그러나 컴퓨터에 진짜 뿌리 분리 알고리즘이 구현되기 시작했을 때 스투름의 정리에서 파생된 알고리즘은 데카르트의 기호 규칙(1637년)에서 파생된 알고리즘보다 효율성이 떨어지는 것으로 나타났다.

20세기 초부터 데카르트의 기호 규칙에서 파생된 알고리즘을 개선하고, 매우 효율적인 구현을 얻으며, 그들의 계산 복잡성을 계산하기 위한 활발한 연구 활동이 있다.최상의 구현은 1,000도가 넘는 다항식의 실제 뿌리를 일상적으로 분리할 수 있다.^[1]^[2]

사양 및 일반 전략

다항식의 실제 뿌리를 찾기 위해, 공통 전략은 실제 선(또는 루트를 검색하는 그것의 간격)을 각 구간에 최대 하나의 루트를 가질 때까지 분리 간격으로 나누는 것이다.이러한 절차를 루트 격리라고 하며, 정확히 하나의 루트를 포함하는 결과 구간은 이 루트에 대한 격리 구간이다.

윌킨슨의 다항식은 다항식의 한 계수를 아주 조금만 수정하면 뿌리의 가치뿐만 아니라 그 성질(실제 또는 복합체)도 극적으로 변화할 수 있다는 것을 보여준다.또한 근사치가 좋더라도 근사치 근원으로 다항식을 평가할 때 0에 가까운 결과를 얻을 수 있다.예를 들어, 20도(Wilkinson의 다항식의 정도)의 다항식이 10에 가까운 루트를 갖는 경우, 루트에서의 다항식의 파생상품은 10 $10^{20};$ ; ${\displaystyle$ 10 $^{20};}$ 이는 루트 값에 대한 10 $10^{20};$ $-$ $10^{-10}$ {\ $displaystyle$ $10^{-10}$ 의 오차가 폴리 값을 생성할 수 있음을 의미한다.10 $10^{10}.$ . $10^{10$ 의 순서에 해당하는 근사 루트에서 명명됨. $10^{10}.$ 그 뒤를 따르며, 아마도 매우 낮은 정도를 제외하고, 뿌리 절연 절차는 정확한 산수를 사용하지 않고는 신뢰할 수 있는 결과를 줄 수 없다.따라서 부동소수계수가 있는 다항식의 뿌리를 분리하려면 합리적인 숫자로 변환한 다음 정수계수가 있는 다항식을 가지기 위해 결과 다항식의 원시 부분을 취하는 것이 좋다.

이 때문에 아래에 기술된 방법들이 이론적으로 실수와 함께 작용하지만, 일반적으로는 정수 계수가 있는 다항식, 합리적 숫자로 끝나는 간격과 함께 실전에 사용된다.또한, 다항식은 항상 사각형이 없어야 한다.거기에는 두 가지 이유가 있다.첫째로, 사각형 자유 인자화를 계산하는 윤의 알고리즘은 다항식 및 그 파생상품의 가장 큰 공통점 계산 비용의 두 배보다 비용이 덜 든다.이는 낮은 수준의 인자를 발생시킬 수 있기 때문에, 알고리즘에서 이것이 필요하지 않은 경우에도 복수 루트가 없는 다항식에만 뿌리분리 알고리즘을 적용하는 것이 일반적으로 유리하다.사각형 없는 다항식만 고려하는 두 번째 이유는 다중 뿌리의 경우 가장 빠른 뿌리 절연 알고리즘이 작동하지 않기 때문이다.

뿌리 격리의 경우, 다항식의 실제 뿌리를 계산하지 않고도 구간에서 계산하는 절차 또는 최소한 구간에 0, 하나 이상의 루트가 포함되어 있는지 여부를 결정하는 절차가 필요하다.이러한 의사결정 절차에서는 실제 뿌리를 포함할 수 있는 간격의 작업 목록을 사용할 수 있다.처음에 목록에는 관심의 모든 뿌리, 일반적으로 전체 실제 선 또는 그 긍정적인 부분을 포함하는 단일 구간이 포함되어 있다.그런 다음 목록의 각 구간을 두 개의 더 작은 구간으로 나눈다.새 간격 중 하나에 루트가 없으면 목록에서 제거된다.루트가 1개 포함된 경우 격리 간격의 출력 목록에 넣는다.그렇지 않으면 추가 분할을 위해 작업 목록에 보관되며, 이 과정은 결국 모든 뿌리가 분리될 때까지 계속될 수 있다.

스투름의 정리

첫 번째 완전한 뿌리 절연 절차 결과는 스투름의 순서라 불리는 다항식 배열의 값의 부호 변이 횟수의 관점에서 구간에 실제 뿌리의 수를 표현하는 스투름의 정리(1829년)이다.스터름의 시퀀스는 다항식 및 그 파생상품에 적용된 유클리드 알고리즘의 변종에서 발생하는 잔류물의 시퀀스다.컴퓨터에 구현했을 때, 스투름의 정리와의 뿌리 격리는 아래에 기술된 다른 방법들에 비해 효율성이 떨어지는 것으로 나타났다.^[3]결과적으로 스투름의 정리는 이론적인 목적에 유용하게 남아 있기는 하지만 효과적인 계산에 거의 사용되지 않는다.

데카르트의 기호 규칙과 그 일반화

데카르트의 기호 법칙은 다항식 계수의 순서에 따른 부호 변동의 수와 그 양의 진짜 뿌리의 수의 차이는 음이 아닌 짝수 정수라고 주장한다.이 수의 부호 변이가 0이면 다항식은 양의 진짜 뿌리를 가지지 못하고, 이 숫자가 1이면 다항식은 고유한 양의 진짜 뿌리를 가지는데, 이것은 하나의 루트다.불행히도 그 반대는 사실이 아니다. 즉, 양의 실제 근이 없거나 단일 양의 단순 근이 있는 다항식은 1보다 큰 여러 부호 변동을 가질 수 있다.

이는 부단의 정리(1807년)에 의해 반쯤 열린 간격( $a,$ $b]$ 의 실제 뿌리에 대해 유사한 결과로 일반화되었다 $.$ $f (x)$ 가 다항식이고 $v$ 가 $f (x$ + $a)$ 와 $f (x$ + $b$ ) 계수의 시퀀스 부호 변화 수의 차이인 경우 $,$ $v$ 에서 간격의 실제 뿌리 수를 뺀 값은 그 곱과 함께 계산된 음이 아닌 짝수 정수다.이것은 데카르트의 기호 법칙의 일반화인데, $b$ 가 충분히 크면 $f (x$ + $b$ ) 계수에 기호 변화가 없고 $,$ 모든 실제 뿌리가 $b$ 보다 작기 때문이다.

부단의 경우 사각형 없는 다항식(복수의 루트가 없는 다항식): 다항식의 계수에서 뿌리의 절대값의 상한 $M$ 과 두 근의 차이의 절대값의 $하한$ m을 계산할 수 있다(다항식의 속성 참조).그 다음, 구간 $[- M,$ $M]$ 을 $m$ 보다 작은 길이의 구간으로 나누면, 모든 실제 루트가 어느 구간에서 포함되며, 구간에는 두 개의 루트가 들어 있지 않다.그러므로 분리 간격은 부단의 정리가 홀수 수의 뿌리를 주장하는 간격이다.

그러나 이 알고리즘은 [- $M,$ $M]$ 구간의 더 강한 칸막이를 사용할 수 없기 때문에 매우 비효율적이다. 왜냐하면, 만약 부단의 정리가 크기가 더 큰 구간에 대해 1보다 큰 결과를 준다면, 여러 개의 뿌리를 포함하지 않는다고 보장할 방법이 없기 때문이다.

빈센트와 관련된 이론들

빈센트의 정리(1834년)^[4]는 가장 효율적인 리얼 루트 분리 알고리즘의 기초에 있는 리얼 루트 격리를 위한 방법을 제공한다.그것은 사각형 없는 다항식(다중근 없는 다항식)의 양의 진짜 뿌리에 관한 것이다. $a_{1},a_{2},\ldots ,$ , $a_{1},a_{2},\ldots ,$ $a_{1},a_{2},\ldots ,$ … $a_{1},a_{2},\ldots ,$ , $a_{1},a_{2},\ldots ,$ 이(가) 양의 실수의 시퀀스라면 $a_{1},a_{2},\ldots ,$ 다음과 같이 하십시오.

c_{k}=a_{1}+{1}+{1}{a_{2}+{\properac {1}{a_{3}+{\properac {1}{1}{\ddots +{1}{1}{a_{k}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}

연속 분수의 k번째 융합이다.

a_{1}+{\properac {1}{a_{2}+{\properac {1}{3}+{\properac {1}{\dots }}}}}}.

빈센트의 정리 — p $p_{0}(x)$ ( $p_{0}(x)$ ) $p_{0}(x)$ 은 $n$ 의 제곱이 없는 다항식이고 $p_{0}(x)$ , $a_{1},a_{2},\ldots ,$ , $a_{1},a_{2},\ldots ,$ , $a_{1},a_{2},\ldots ,$ … $a_{1},a_{2},\ldots ,$ , ${\displaystyle a_{1},a_{2},\ldots$ ,}은 $($ 는) 실수의 순서가 되게 $a_{1},a_{2},\ldots ,$ 한다. $i$ = 1 $, 2,...$ 의 경우 다항식을 고려하십시오.

p_{i}(x)=x^{n1}p_{i-1}\왼쪽(a_{i}+1/x\오른쪽).

그런 다음 $p_{k}(0)=0,$ ( $p_{k}(0)=0,$ ) = $p_{k}(0)=0,$ $p_{k}(0)=0,$ $p_{k}$ p k ${\$ 의 계수 순서에 최대 하나의 부호 변동을 갖는 $p_{k}$ 정수 $k$ 가 있다.

첫 번째 경우 수렴 $c$ 는_k $p_{0}.$ $p_{0}.$ $p_{0}$ 의 양의 근이 된다. 그렇지 $p_{0}.$ 않으면 이 기호 변화수(0 또는 1)는 $c_{k-1}$ k - $c_{k-1}$ 1 {\ $displaystyle$ c_ ${k-1}$ 및 $.$ {\ $displaystystyle c_{k}}$ 에 $c_{k-1}$ 의해 정의된 간격에 $p_{0}$ $p_{0}$ $p_{0}$ 0 $p_{0}$ {\ $displaystystystylease$ p{{{{0 $}$ 의 $실제$ 근의 수이다. $}$

그의 정리를 증명해 준 것에 대해 빈센트는 스스로 유용한 결과를 증명했다.^[4]

빈센트의 보조 정리 — $p (x)$ 가 도 $n$ 의 제곱이 없는 다항식이고 $a,$ $b,$ $c,$ $d$ 가 $\left|{\frac {a}{c}}-{\frac {b}{d}}\right|$ - $\left|{\frac {a}{c}}-{\frac {b}{d}}\right|$ ${\d}{c}-{c}-{\frac{b}{d}}\right}}}}}}$ 이 $\left|{\frac {a}{c}}-{\frac {b}{d}}\right|$ (가) 충분히 작을 정도로 음수가 아닌 경우, 다항 계수의 계수에 최대 1개의 부호 변화가 있다.

q(x)=(cx+d)^{n}p\left\frac {ax+b}{cx+d}\오른쪽),

그리고 이 기호 변수의 수는 ${\frac {a}{c}}$ ${\$ { $a}{c}$ 및 ${\frac {b}{d}}.$ d ${\frac {a}{c}}$ ${\frac {b}{d}}.$ ${\displaystyle {\frac$ { $b}{d}}$ 에 의해 정의된 개방 간격에 있는 $p (x)$ 의 실제 루트 수입니다. $}$

$실제$ 숫자로 작업할 경우 c = $d$ = $1$ 을 항상 선택할 수 있지만, 합리적인 숫자로 효과적인 계산을 하기 때문에 $a,$ $b,$ $c,$ $d$ 가 정수라고 가정하는 것이 일반적으로 편리하다.

"적어도 작은" 조건은 니콜라 오브레쉬코프와 ^[5]알렉산더 오스트로우스키에 의해 독립적으로 정량화되었다.^[6]

Obreschoff-Ostrowski 정리: 청색과 황색으로 기호 변동을 0 또는 1로 하기 위해 뿌리가 없어야 하는 복합 평면의 영역, 왼쪽은

p

의 뿌리에 대해 제외된 영역, 오른쪽은 변환된 다항식의

q

의 뿌리에 대해 제외된 영역, 파란색은 하나의 부호 변동을 가지기 때문에 제외된 영역.켜지지만 제로 부호 변형이 허용된다.

정리(Obreschkoff-Ostrowski) — 다항식 $p (x)$ 가 최대 하나의 루트 $α$ + $iβ$ 를 가질 경우 빈센트의 보조 결과의 결론은 유지된다.

\left(\alpha -{\frac {a}{c}}\right)\left(\alpha -{\frac {b}{d}}\right)+\beta ^{2}\leq {\frac {1}{\sqrt {3}}}\left \beta \left({\frac {a}{c}}-{\frac {b}{d}}\right)\right .

특히 결론은 다음과 같다.

\왼쪽 {\frac {a}{c}-{\frac {b}}}\오른쪽 <{\frac {d}}\frac 이름 {d}(p)}{2{\sqrt{3}}},

여기서 $sep(p)$ 는 $p$ 의 두 뿌리 사이의 최소 거리다.

정수 계수가 있는 다항식의 경우, 최소 거리 $sep(p)$ 는 다항식의 정도와 그 계수의 최대 절대값 측면에서 더 낮은 경계가 될 수 있다. 다항식 루트 § 루트 분리의 특성을 참조한다.이를 통해 빈센트의 이론에 근거한 알고리즘의 최악의 복잡성을 분석할 수 있다.그러나 Obreschkoff-Ostrowski 정리는 이러한 알고리즘의 반복 횟수가 작업 간격의 근방에 있는 루트 사이의 거리에 따라 달라지는 것을 보여준다. 따라서 반복 횟수는 동일한 다항식의 루트에 따라 극적으로 달라질 수 있다.

제임스 5세 우스펜스키는 0 또는 1개의 부호 변동을 얻기 위해 계속 분율(빈센트의 정리에 필요한 정수 $k$ )의 길이에 대한 한계를 부여했다.^[1]^[7]

$정리$ (Uspensky)— $p$ ( $x$ $)$ 를 도 n의 다항식으로 하고, $sep(p)$ 를 $p$ 의 두 뿌리 사이의 최소 거리로 한다.내버려두다

\varepsilon =\left(n+{\frac {1}{n}\오른쪽)^{\frac {1}{n-1.1

그러면 빈센트의 정리에 존재하는 정수의 $k$ 는 다음과 같이 가장 작은 $정수$ h보다 크지 않다.

F_{h-1}\operatorname {sep}(p)2\quad {\text{and}}\quad F_{h-1}{k}\operatorname {sep}(p){\frac {1}{\barepsilon },},},

여기서 $F_{h}$ $F_{h}$ ${\$ 는 $F_{h}$ h번째 피보나치 수이다.

연속분수법

실제 뿌리 분리를 위한 지속적인 분수의 사용은 빈센트에 의해 소개되었지만, 그는 이 아이디어에 대해 Joseph-Louis Lagrange를 언급 없이 인정했다.^[4]빈센트의 정리 알고리즘을 만들기 위해서는 자신의 정리에서 발생하는 $a_{i}$ $a_{i}$ ${\$ 를 선택하는 기준을 제시해야 한다.빈센트 자신도 어떤 선택을 제공했다(아래 참조).다른 선택이 가능하며 알고리즘의 효율성은 이러한 선택에 크게 좌우될 수 있다.아래는 이러한 선택들이 나중에 논의될 보조함수에서 비롯되는 알고리즘을 제시한다.

이 알고리즘을 실행하려면 특정 데이터 구조로 표시된 간격 목록을 사용하여 작업해야 한다.알고리즘은 간격을 선택하고 목록에서 제거하며 0, 1 또는 2개의 작은 간격을 목록에 추가하여 작동하며, 가능한 한 격리 간격을 출력한다.

For isolating the real roots of a polynomial $p (x)$ of degree $n$ , each interval is represented by a pair $(A(x),M(x)),$ where $A (x)$ is a polynomial of degree $n$ and $M(x)={\frac {px+r}{qx+s}}$ is a Möbius transformation with integer coefficients.가지고 있다

A(x)=p(M(x)),

그리고 이 데이터 구조로 대표되는 구간은 끝점으로 $M(\infty )={\frac {p}{q}}$ $M(0)={\frac {r}{s}}$ $M(\infty )={\frac {p}{q}}$ $M(\infty )={\frac {p}{q}}$ ) $M(\infty )={\frac {p}{q}}$ = $M(\infty )={\frac {p}{q}}$ $M(\infty )={\frac {p}{q}}$ = p ${\$ M $(\inflit )={$ $M(0)={\frac {r}{s}}$ $}}},$ $M(0)={\frac {r}{s}}$ ( 0 $M(0)={\frac {r}{s}}$ ) $M(0)={\frac {r}{s}}$ = $M(0)={\frac {r}{s}}$ s ${\$ }{ $s}}}}}}}}$ 이 있는 구간이다.뫼비우스 변환은 이 간격의 $p$ 의 뿌리를 $(0,$ + $+)$ 의 $A$ 의 뿌리에 매핑한다.

The algorithm works with a list of intervals that, at the beginning, contains the two intervals $(A(x)=p(x),M(x)=x)$ and $(A(x)=p(-x),M(x)=-x),$ corresponding to the partition of the reals into the positive and the negative ones(0이 루트가 아니라고 가정할 수 있다, 있는 것처럼, 알고리즘을 $p (x)/ x$ 에 적용하기에 충분하다).그런 다음 목록의 각 구간 $(A (x),$ $M (x))$ 에 대해 알고리즘이 목록에서 제거한다. $A$ 계수의 부호 변이 수가 0이면 구간에는 루트가 없고, 다음 구간으로 전달된다.부호 변동의 수가 $M(0)$ 인 경우, $M(0)$ ( 0 $M(0)$ ) ${\displaystyle$ M $(0)}$ 과 $M(0)$ $M(\infty )$ ( $M(\infty )$ ) $M(\inflt )$ 에 의해 정의된 간격은 분리 간격이다 $M(\infty )$ .그렇지 않으면 구간( $0,$ +3)을 $(0,$ b $)$ 와 $(b, +\infty)$ 로 나누기 위해 양의 $실수$ b를 선택하고, 각 하위간격의 경우 $(0,$ +∞)에 그 구간을 매핑하는 뫼비우스 $변환$ 으로 M을 구성하여 목록에 두 개의 새로운 구간을 추가한다.유사 코드에서, 이것은 다음을 제공하며, 여기서 $var(A)$ 는 다항식 $A$ 계수의 부호 변동의 수를 나타낸다.

function continued fraction is input: P(x), a square-free polynomial,     output: a list of pairs of rational numbers defining isolating intervals     /* Initialization */         L := [(P(x), x), (P(–x), –x)]                /* two starting intervals */         Isol := [ ]     /* Computation */     while L  $\neq$  [ ] do Choose (A(x), M(x)) in L, and remv = 0이면 L v := var(A)에서 과대평가한 다음 */ 만약 v = 1이면 /* 격리구간에서 */(M(0), M(iii)을 찾은 다음 */ (M)과 Isol 출구 b := 일부 양의 정수 B(x) = A(x + b) = w := v - var(B)가 0이면 v – var(B)를 뺀다./* rational root found */             add (M(b), M(b)) to Isol             B(x) := B(x)/x         add (B(x),  M(b + x) to L           /* roots in (b, +∞) */         if w = 0 then exit                  /* Budan's theorem */          if w = 1 then                       /* Budan's theorem again */              add (M(0), M(b)) to Isolw > 1이면 (0, b) */에 A(b/(1 + x), M(b/(1 + x))을 L /* 루트에 추가한다.

알고리즘의 다른 변형은 기본적으로 $b$ 의 선택에 달려 있다.빈센트의 논문과 우스펜스키의 저서에서 $우스펜스키가 (0,$ b)와 관련된 구간의 추가적인 이분화를 피하기 위해 부단의 정리를 사용하지 않았다는 차이점과 함께 항상 b = $1$ 을 가지고 있다.

항상 $b$ = $1$ 을 선택하는 것의 단점은 $x$ → $1$ + $x$ 형태의 변수의 연속적인 변화를 많이 해야 한다는 것이다.이러한 것들은 변수 $x$ → $n$ + $x$ 의 단일 변경으로 대체될 수 있지만, 그럼에도 불구하고 부단의 정리를 적용하기 위해서는 변수의 중간 변경을 해야 한다.

알고리즘의 효율성을 향상시키는 방법은 다항식 계수로 계산된 양의 실제 근의 하한을 $b$ 로 하는 것이다(이러한 한계에 대한 다항식 근의 속성 참조).^[8]^[1]

이등분법

이분법(bisection)은 다항식의 모든 진짜 뿌리를 포함하는 간격에서 시작하여, 0 또는 1개의 루트를 포함하는 간격을 얻을 때까지 재귀적으로 두 부분으로 나눈다.시작 간격은 형식 $(-$ B $,$ $B)$ 일 수 있으며, 여기서 $B$ 는 다항식 루트 속성 § 다항식 루트(복잡한)에 주어진 것과 같은 뿌리의 절대 값에 대한 상한이다.기술적 이유(변수의 단순화, 단순한 복잡도 분석, 컴퓨터의 이항분석을 이용할 수 있는 가능성) 때문에 알고리즘은 일반적으로 [ $0,$ 1 $]$ 구간부터 시작하는 것으로 제시된다 $.$ 변수 $x$ = $By$ 및 $x =$ – $각각$ 이동 간격 $[0,$ 1 $]$ 의 양의 뿌리와 음의 뿌리를 사용할 수 있으므로 일반성의 손실은 없다. (단일 변경 $변수$ x $=$ ( $2By$ – $B)$ 도 사용할 수 있다.)

이 방법은 구간에 0, 1 또는 여러 루트가 있는지 시험하는 알고리즘이 필요하고, 종료를 보증하기 위해 이 시험 알고리즘은 출력 "여러 루트의 가능성"의 무한 배수를 얻을 가능성을 배제해야 한다.스투름의 정리나 빈센트의 보조정리는 그런 편리한 테스트를 제공한다.데카르트의 기호 사용 규칙과 빈센트의 보조 정리는 스터름의 정리 사용보다 계산적으로 훨씬 효율적이기 때문에, 이 절에는 전자만 기술되어 있다.

데카르트의 기호 규칙과 빈센트의 보조 정리에 기초한 이분법(bisection method)은 1976년 아키타스와 콜린스에 의해 수정된 우스펜스키 알고리즘이라는 이름으로 도입되어,^[3] 우스펜스키 알고리즘인 빈센트(Uspensky algorithm)로 일컬어 왔다.데카르트, 빈센트, 우스펜스키 등은 설명하지 않았지만 –아크리트-콜린스 알고리즘 또는 데카르트 방법.

방법은 다음과 같다.루트를 일정 간격으로 검색하는 경우, 먼저 새 다항식 $q (x$ )를 제공하는 $[0,$ 1 $]$ 에 간격을 매핑하기 위한 변수를 변경한다 $.$ $[0,$ 1]에서 $q$ 의 루트를 검색할 경우 $,$ $x\to {\frac {1}{x+1}},$ x $x\to {\frac {1}{x+1}},$ → $x\to {\frac {1}{x+1}},$ x $x\to {\frac {1}{x+1}},$ + $x\to {\frac {1}{x+1}},$ , ${\displaystyle x\to {\frac$ { $1}{x+1},}$ 의 변경으로 간격 $[0, 1]$ 을 $[0,$ +1 $]$ 에 매핑하여 다항식 r $(x$ )을 $x\to {\frac {1}{x+1}},$ 부여한다 $.$ 데카르트의 다항식 $r$ 에 적용되는 기호의 $규칙은 [0$ , 1 $]$ 간격의 $q$ 의 실제 뿌리 수 및 [ $0, 1]$ 에 매핑된 간격의 초기 다항식의 뿌리 수에 대한 표시를 제공한다 $.$ $r$ 의 계수 순서에 부호 변동이 없는 경우, 고려된 간격에 실제 루트가 없다.하나의 부호 변이가 있는 경우, 한 개의 부호 변이가 있는 경우, 한 개의 부호는 분리 간격을 가진다.그렇지 않으면 구간 $[0, 1]$ 을 $[0,$ 1 $/2]$ 과 $[1/2$ , $1]$ 로 나누고 $,$ 변수 $x$ = $y /2$ 와 $x$ = $(y$ + 1 $)/2$ 의 변화에 따라 $[0,$ 1 $]$ 에 매핑한다.빈센트의 보조 정리는 이 절차의 종료를 보장한다.

초기화를 제외하고, 이러한 변수의 모든 변화는 최대 두 개의 매우 단순한 변수의 구성으로 구성되는데, 두 $개$ 의 x → $x /2$ , 변환 $x$ → $x$ + $1$ , 그리고 역 $x$ → 1/ $x$ , 즉 다항식의 계수의 순서를 되돌리는 것으로 구성된다.컴퓨팅 시간의 대부분이 변수의 변화에 할애되기 때문에, [ $0, 1]$ 에 대한 매 간격 매핑으로 구성되는 방법은 좋은 효율을 보장하기 위한 기본이다.

가성음

다음의 표기법은 다음의 가음에서 사용된다.

$p (x)$ 는 [ $0, 1]$ 간격의 실제 루트를 분리해야 하는 다항식이다 $.$
$var(q (x))$ 는 다항식 $q$ 의 계수 시퀀스에서 부호 변동의 수를 나타낸다.
작업 목록의 요소에는 다음과 같은 $형식 (c,$ $k$ , $q ($ x))이 있다 $.$
- $c$ 와 $k$ 는 $c$ < $2$ 와^k 같이 음이 아닌 두 정수로서 $\left[{\frac {c}{2^{k}}},{\frac {c+1}{2^{k}}}\right],$ [ $\left[{\frac {c}{2^{k}}},{\frac {c+1}{2^{k}}}\right],$ 2 $\left[{\frac {c}{2^{k}}},{\frac {c+1}{2^{k}}}\right],$ $\left[{\frac {c}{2^{k}}},{\frac {c+1}{2^{k}}}\right],$ + 1 $\left[{\frac {c}{2^{k}}},{\frac {c+1}{2^{k}}}\right],$ $\left[{\frac {c}{2^{k}}},{\frac {c+1}{2^{k}}}\right],$ ${\displaystyle \left[{\frac {c}{2^{k}}}},{\frac {$ c+1}{2}},{\frac ${c+$ 1}{2}{2}{2}}}}{ $2$ }}{2}}}}}}{2}}}}}} $^{k}}}\오른쪽,}$
- ${\displaystyle q(x)=2^{kn}p\leftp\frac {x+c}{2$ $^{k}}}\right)}$ 여기서 $q(x)=2^{kn}p\left({\frac {x+c}{2^{k}}}\right),$ $n$ 은 $p$ 의 정도( $p$ , $c$ , $k$ 에서 직접 $계산$ 될 수 있지만 알고리즘에서 수행될 것이므로 점진적으로 계산하는 것이 비용이 덜 든다. $p$ 가 정수 계수를 갖는 경우, $q$ 에 대해서도 동일하다)

함수 이분법은 입력:  $p ($  $x$  $),$  즉 square-free  $다항식$ 으로서 $,$  $p$  $(0)$  $p$ (1) $0$  0과 같이 구간의 루트가 검색되는 출력: 삼쌍 $(c,$   $k,$   $h$ ) 목록으로 $\left[{\frac {c}{2^{k}}},{\frac {c+h}{2^{k}}}\right]$  [ $\left[{\frac {c}{2^{k}}},{\frac {c+h}{2^{k}}}\right]$  2  $\left[{\frac {c}{2^{k}}},{\frac {c+h}{2^{k}}}\right]$ ,  $\left[{\frac {c}{2^{k}}},{\frac {c+h}{2^{k}}}\right]$ +  $\left[{\frac {c}{2^{k}}},{\frac {c+h}{2^{k}}}\right]$   $\left[{\frac {c}{2^{k}}},{\frac {c+h}{2^{k}}}\right]$   $[\$ ]를 나타낸다. $c {c}{2^{k}},{\frac {c+h}{2$  $^{k}}}\right]}$      /* Initialization */     L := [(0, 0, p(x))] /* a single element in the working list L */     Isol := [ ]     n := degree(p}}     /* Computation */     while L  $\neq$  [ ] do Choose (c, k,  $q (x))$  in L, and remove it from L         if  $q (0) = 0$  then  $q (x) := q (x)/ x$              n := n – 1                /* A rational root found */(c, k, 0) Isol v := $\operatorname {var} ((x+1)^{n}q(1/(x+1)))$   $\operatorname {var} ((x+1)^{n}q(1/(x+1)))$ ( $\operatorname {var} ((x+1)^{n}q(1/(x+1)))$ ( x $\operatorname {var} ((x+1)^{n}q(1/(x+1)))$ +  $\operatorname {var} ((x+1)^{n}q(1/(x+1)))$ )  $\operatorname {var} ((x+1)^{n}q(1/(x+1)))$   $\operatorname {var} ((x+1)^{n}q(1/(x+1)))$ ( 1 $\operatorname {var} ((x+1)^{n}q(1/(x+1)))$ / $\operatorname {var} ((x+1)^{n}q(1/(x+1)))$ (  $\operatorname {var} ((x+1)^{n}q(1/(x+1)))$ +  $\operatorname {var} ((x+1)^{n}q(1/(x+1)))$ ) $\operatorname {var} ((x+1)^{n}q(1/(x+1)))$ )  ${\displaystyle \operatorname {var}(x+1)^{nq(1/(x+1$ )))에 추가 $)$ }만약 v=1그때 /* 격리 간격을 발견했다 */을(c, k, 1)에 Isol 만약 v입니다.;1그때 /* Bisecting */을 추가하(2c, k+1,2nq(x/2){2^{n\displaystyle}(x/2)}에 나는 추가(2c+1, k+1,2nq((x+1)/2){2^{n\displaystyle}((x+1)/2)}.   로엘엔드

이 절차는 본질적으로 콜린스와 아키타스가 설명한 것이다.^[3]실행 시간은 주로 고려해야 할 간격의 수와 변수의 변화에 따라 달라진다.알고리즘 발표 이후, 주로 21세기 초반부터 연구 주체가 되어 온 효율성의 향상을 위한 방법이 있다.

최근 개선 사항

Akritas-Collins bisection 알고리즘을 개선하기 위한 다양한 방법이 제안되었다.그들은 variables,[9]의 변화를 대략적인 산수(부동 소수 점과 구간 연산)의 variations,[9]뉴턴의 메서드를 사용할 때 빠른 polyn의 사용 possible,[9]간판의 전화 번호를 알려 올바른 값 가져오기를 허용하는 사용의 단순함을 잃지 않고 다항식의 긴 목록을 저장하기를 피하기 위한 방법이 있다.omial 함께Ithmetic,^[10] 근접한 뿌리의 군집일 경우 이분류의 긴 사슬을 위한 단축키,^[10] 다항식 평가에서 불안정 문제를 제한하기 위한 불균등한 부분에서의 이분법.^[10]

이러한 모든 개선은 복잡성을 갖는 정수 계수로 다항식의 모든 실제 뿌리를 분리하는 알고리즘으로 이어진다(Logarithm 계수를 생략하는 데 소프트 O 표기법, $õ$ 사용).

{\tilde{O}(n^{2}(k+t),

여기서 $n$ 은 다항식의 정도, $k$ 는 0이 아닌 항의 수, $t$ 는 계수의 최대 자릿수다.^[10]

이 알고리즘의 구현은 매우 근접한 루트를 가진 다항식의 경우(이항법에서 이전에 가장 어려웠던 경우)에서도 다항식의 실제 루트를 계산하기 위해 구현된 다른 어떤 방법보다 효율적인 것으로 보인다.^[2]

참조

원천

Alesina, Alberto; Massimo Galuzzi (1998). "A new proof of Vincent's theorem". L'Enseignement Mathématique. 44 (3–4): 219–256. Archived from the original on 2014-07-14. Retrieved 2018-12-16.
Akritas, Alkiviadis G. (1986). There's no "Uspensky's Method". Proceedings of the fifth ACM Symposium on Symbolic and Algebraic Computation (SYMSAC '86). Waterloo, Ontario, Canada. pp. 88–90.
Akritas, Alkiviadis G.; Strzeboński, A. W.; Vigklas, P. S. (2008). "Improving the performance of the continued fractions method using new bounds of positive roots" (PDF). Nonlinear Analysis: Modelling and Control. 13 (3): 265–279. doi:10.15388/NA.2008.13.3.14557.
Akritas, Alkiviadis G.; Strzeboński, Adam W. (2005). "A Comparative Study of Two Real Root Isolation Methods" (PDF). Nonlinear Analysis: Modelling and Control. 10 (4): 297–304. doi:10.15388/NA.2005.10.4.15110.
Collins, George E.; Akritas, Alkiviadis G. (1976). Polynomial Real Root Isolation Using Descartes' Rule of Signs. SYMSAC '76, Proceedings of the third ACM symposium on Symbolic and algebraic computation. Yorktown Heights, NY, USA: ACM. pp. 272–275. doi:10.1145/800205.806346.
Kobel, Alexander; Rouillier, Fabrice; Sagraloff, Michael (2016). "Computing real roots of real polynomials ... and now for real!". ISSAC '16, Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation. Waterloo, Canada. arXiv:1605.00410. doi:10.1145/2930889.2930937.
Obreschkoff, Nikola (1963). Verteilung und Berechnung der Nullstellen reeller Polynome (in German). Berlin: VEB Deutscher Verlag der Wissenschaften. p. 81.
Ostrowski, A. M. (1950). "Note on Vincent's theorem". Annals of Mathematics. Second Series. 52 (3): 702–707. doi:10.2307/1969443. JSTOR 1969443.
Rouillier, F.; Zimmerman, P. (2004). "Efficient isolation of polynomial's real roots". Journal of Computational and Applied Mathematics. 162 (1): 33–50. Bibcode:2004JCoAM.162...33R. doi:10.1016/j.cam.2003.08.015.
Sagraloff, M.; Mehlhorn, K. (2016). "Computing real roots of real polynomials". Journal of Symbolic Computation. 73: 46–86. arXiv:1308.4088. doi:10.1016/j.jsc.2015.03.004.
Tsigaridas, P. E.; Emiris, I. Z. (2006). "Univariate polynomial real root isolation: Continued fractions revisited". LNCS. Lecture Notes in Computer Science. 4168: 817–828. arXiv:cs/0604066. Bibcode:2006cs........4066T. doi:10.1007/11841036_72. ISBN 978-3-540-38875-3. S2CID 516130.
Uspensky, James Victor (1948). Theory of Equations. New York: McGraw–Hill Book Company.
Vincent, Alexandre Joseph Hidulphe (1834). "Mémoire sur la résolution des équations numériques". Mémoires de la Société Royale des Sciences, de L' Agriculture et des Arts, de Lille (in French): 1–34.
Vincent, Alexandre Joseph Hidulphe (1836). "Note sur la résolution des équations numériques" (PDF). Journal de Mathématiques Pures et Appliquées. 1: 341–372.
Vincent, Alexandre Joseph Hidulphe (1838). "Addition à une précédente note relative à la résolution des équations numériques" (PDF). Journal de Mathématiques Pures et Appliquées. 3: 235–243. Archived from the original (PDF) on 2013-10-29. Retrieved 2018-12-16.

[TE-1] 티가리다스 & 에미리스 2006

[KRS-2] 코벨, 룰리에 & 사그랄로프 2016

[CA-3] 콜린스 & 아키르타스 1976

[Vincent-memoire-4] 빈센트 1834년

[Obr_1920-5] 오브레슈코프 1963

[O_1950-6] 오스트로우스키 1950

[Uspensky-7] 우센스키 1948년

[8] 아크리타스 & 스트레보우스키 2005

[RZ-9] 룰리에 & 짐머맨 2004

[SM-10] 새그랄로프 & 멜혼 2016

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[10]

Search