부단의 정리

수학에서 부단의 정리는 다항식의 실제 뿌리 수를 일정한 간격으로 경계하고, 이 숫자의 패리티를 계산하기 위한 정리다.1807년 프랑수아 부단 드 보이슬라우렌트에 의해 출판되었다.

비슷한 정리가 1820년 조셉 푸리에 의해 독자적으로 발표되었다.이 각각의 이론들은 다른 이론의 핵심이다.푸리에의 진술은 19세기 문헌에 더 자주 나타나며 푸리에, 부단-푸리에, 푸리에-부단, 심지어 부단의 정리까지 언급되어 왔다.

부단의 원래 제형은 다항식의 진짜 뿌리 절연을 위한 빠른 현대 알고리즘에 사용된다.

부호변동

$c_{0},c_{1},c_{2},\ldots c_{k}$ $c_{0},c_{1},c_{2},\ldots c_{k}$ , $c_{0},c_{1},c_{2},\ldots c_{k}$ $c_{0},c_{1},c_{2},\ldots c_{k}$ , $c_{0},c_{1},c_{2},\ldots c_{k}$ c $c_{0},c_{1},c_{2},\ldots c_{k}$ , $c_{0},c_{1},c_{2},\ldots c_{k}$ … c ${\$ 을(를) 실수의 유한한 순서가 되도록 $c_{0},c_{1},c_{2},\ldots c_{k}$ 한다.시퀀스의 부호 변동 또는 부호 변경은 $모든$ $k$ 에 $c_{k}=0$ $c_{i}c_{j}<0,$ $c_{i}c_{j}<0,$ $c_{i}c_{j}<0,$ j < $c_{i}c_{j}<0,$ {\ $displaystyle c_{i}c_{j}<0$ $j$ = $i$ + $1$ $c_{k}=0$ c = $c_{k}=0$ $c_{k}=0$ 인 지수 $쌍$ 이다 $.$

즉, 0을 무시하면 기호가 바뀌는 각 장소의 순서에 따라 기호의 변동이 발생한다.

다항식의 실제 근원을 연구하기 위해, 여러 시퀀스의 부호 변형 수를 사용할 수 있다.부단의 정리로는 계수의 순서가 된다.부단-푸리에 정리에서는 한 점에서 연속적인 파생상품의 값의 순서다.스투름의 정리에서는 스투름 순서의 한 지점에 있는 값의 순서다.

데카르트의 기호 법칙

이 글에서 설명한 모든 결과는 데카르트의 기호 규칙에 근거한다.

$p (x)$ 가 실제 계수를 갖는 일변량 다항식인 경우 $+$ #( $p)$ 양수 실질 근의 수, 그 다항성으로 계수하고,^[1] $v$ ( $p)$ 계수 순서의 부호 변동의 수를 나타내자.데카르트의 기호 법칙은 다음과 같이 주장한다.

v (p)

–

#(+ p)

는 음이 아닌 짝수 정수다.

특히 $v (p)$ ≤ $1$ 이면 $#(+ p)$ = $v (p$ )가 있다 $.$

부단의 성명

실제 계수를 갖는 일변량 $다항식$ p $(x)$ 를 주어진다면, $#((ℓ, r] p)$ 실제 근의 수를 그 곱과 함께 계산한 ^[1] $p$ 의 개수로 반개방 간격 $($ (, $r)$ 으로 나타내도록 하자. (, < r $real$ numbers)또한 다항식 $p h (x)$ = $p (x$ + $h$ )의 계수 순서에 있는 부호 변동의 수를 $v h (p)$ 로 나타내자 $.$ 특히 앞의 절의 표기법을 $가진$ v( $p)$ = $v 0 (p)$ 가 있다.

부단의 정리는 다음과 같다.

v_{\ell }(p)-v_{r}(p)-\#_{(\ell ,r]}

v_{\ell }(p)-v_{r}(p)-\#_{(\ell ,r]}

(

v_{\ell }(p)-v_{r}(p)-\#_{(\ell ,r]}

)

v_{\ell }(p)-v_{r}(p)-\#_{(\ell ,r]}

-

v_{\ell }(p)-v_{r}(p)-\#_{(\ell ,r]}

v_{\ell }(p)-v_{r}(p)-\#_{(\ell ,r]}

(

v_{\ell }(p)-v_{r}(p)-\#_{(\ell ,r]}

)

v_{\ell }(p)-v_{r}(p)-\#_{(\ell ,r]}

-

v_{\ell }(p)-v_{r}(p)-\#_{(\ell ,r]}

# (

v_{\ell }(p)-v_{r}(p)-\#_{(\ell ,r]}

, r

v_{\ell }(p)-v_{r}(p)-\#_{(\ell ,r]}

{\

}-{r

}-(p)-\#_{(\ell ,r)}}}}}}}}}

은 음이 아닌 짝수 정수다

v_{\ell }(p)-v_{r}(p)-\#_{(\ell ,r]}

.

$\#_{(\ell ,r]}$ ( $\#_{(\ell ,r]}$ , r $\#_{(\ell ,r]}$ ${\$ $v_{\ell }(p)\geq v_{r}(p).$ $]}}}}}$ 이( $v_{\ell }(p)\geq v_{r}(p).$ ) 음이 아니므로 $\#_{(\ell ,r]}$ , 이는 $v_{\ell }(p)\geq v_{r}(p).$ $v_{\ell }(p)\geq v_{r}(p).$ ( $v_{\ell }(p)\geq v_{r}(p).$ p $v_{\ell }(p)\geq v_{r}(p).$ ) $v_{\ell }(p)\geq v_{r}(p).$ v $v_{\ell }(p)\geq v_{r}(p).$ ( p $v_{\ell }(p)\geq v_{r}(p).$ ) $v_{\ell }(p)\geq v_{r}(p).$ . ${\displaystyle v_{\ell }\geq v_{r}(p$ )을 의미한다 $.$ $}$

This is a generalization of Descartes' rule of signs, as, if one chooses $r$ sufficiently large, it is larger than all real roots of $p$ , and all the coefficients of $p_{r}(x)$ are positive, that is $v_{r}(p)=0.$ Thus ${\dis$ $플레이스타일 v_{0}(p)=v_{0}(p)-v_{r}(p),$ $\#_{+}=\#_{(0,r)},$ # $\#_{+}=\#_{(0,r)},$ = $\#_{+}=\#_{(0,r)},$ # $\#_{+}=\#_{(0,r)},$ r $\#_{+}=\#_{(0,r)},$ ${\displaystyle \#_{+}=\#_{r}}}},$ 이것이 $v_{0}(p)=v_{0}(p)-v_{r}(p),$ $\#_{+}=\#_{(0,r)},$ 데카르트의 서명 규칙을 부단의 정리 특수한 사례로 만든다.

As for Descartes' rule of signs, if $v_{\ell }(p)-v_{r}(p)\leq 1,$ one has ${\displaystyle \#_{(\ell ,r]}=v_{\ell }(p)-v_{r}(p).$ $}$ $v_{\ell }(p)-v_{r}(p)\leq 1$ $v_{\ell }(p)-v_{r}(p)\leq 1$ ( $v_{\ell }(p)-v_{r}(p)\leq 1$ ) $v_{\ell }(p)-v_{r}(p)\leq 1$ - $v_{\ell }(p)-v_{r}(p)\leq 1$ r $v_{\ell }(p)-v_{r}(p)\leq 1$ ( $v_{\ell }(p)-v_{r}(p)\leq 1$ ) $v_{\ell }(p)-v_{r}(p)\leq 1$ 1 ${\displaystyle v_{\ell }-v_{r}(p)\leq$ 1 $}$ 이 $v_{\ell }(p)-v_{r}(p)\leq 1$ (가) 1이면 "0루트 테스트"와 "원루트 테스트"가 있다는 뜻이다.

예

1. $p(x)=x^{3}-7x+7,$ p $p(x)=x^{3}-7x+7,$ ( $p(x)=x^{3}-7x+7,$ ) = $p(x)=x^{3}-7x+7,$ - $p(x)=x^{3}-7x+7,$ $p(x)=x^{3}-7x+7,$ + 7 $p(x)=x^{3}-7x+7,$ , $p(x)=x^{3}-7x+7,$ 과 $p(x)=x^{3}-7x+7,$ (와) $(0,2)$ 열린 $(0,2)$ 0 , $(0,2)$ ) $(0,2)$ {\ $displaystyle (0,$ 2)}을(를) 감안하면 $(0,2)$ 1은 다음과 같다.

{\displaysty}p(x+0)&=p(x)=x^{3}-7x+7\\p(x+2)=(x+2)^{3}-7(x+2)+7=x^{3}+6x^{2}+5x+1\end{arged}}.

Thus, $v_{0}(p)-v_{2}(p)=2-0=2,$ and Budan's theorem asserts that the polynomial $p(x)$ has either two or zero real roots in the open interval ${\displaystyle (0,2).$ $}$

2. $p(x)=x^{3}-7x+7$ p $p(x)=x^{3}-7x+7$ ( $p(x)=x^{3}-7x+7$ ) $p(x)=x^{3}-7x+7$ = $p(x)=x^{3}-7x+7$ 3 $p(x)=x^{3}-7x+7$ - 7 $p(x)=x^{3}-7x+7$ + $p(x)=x^{3}-7x+7$ $(\displaystyle p(x)=x^{3}-7x+7}$ 을(를) 가진 사람은 $p(x)=x^{3}-7x+7$

p(x+1)=(x+1)^{3}-7(x+1)+7=x^{3}+3x^{2}-4x+1

따라서 $v_{0}(p)-v_{1}(p)=2-2=0,$ $v_{0}(p)-v_{1}(p)=2-2=0,$ ( $v_{0}(p)-v_{1}(p)=2-2=0,$ ) $v_{0}(p)-v_{1}(p)=2-2=0,$ - $v_{0}(p)-v_{1}(p)=2-2=0,$ $v_{0}(p)-v_{1}(p)=2-2=0,$ ( $v_{0}(p)-v_{1}(p)=2-2=0,$ ) $v_{0}(p)-v_{1}(p)=2-2=0,$ = 2 $v_{0}(p)-v_{1}(p)=2-2=0,$ - $v_{0}(p)-v_{1}(p)=2-2=0,$ = $v_{0}(p)-v_{1}(p)=2-2=0,$ ${\displaystyle v_{0}-v_{1}(p)=2-2=0,},$ 부단의 $v_{0}(p)-v_{1}(p)=2-2=0,$ 정리는 $p(x)$ p $p(x)$ ( $(0,1).$ $){\$ $displaystyle$ $p(x$ $)$ 가 열린 간격에 실제 루트가 없다고 $p(x)$ $(0,1).$ 한다 $.$ $}$ 부단의 정리를 제로루트 시험으로 사용한 예다 $(0,1).$ .

푸리에의 진술

푸리에-부단 정리 또는 부단-푸리에 정리(때로는 부단의 정리만)라고도 불리는 푸리에의 다항실근근근 정리(Fourier-Budan-Fourier 정리)는 부단의 $정리$ ( $h$ = l와 r의 경우 p $(x$ + $h$ ) 계수의 순서가 $h$ 에서 p(x + h)의 파생순서에 의해 대체된다는 점을 제외하면 부단의 정리와는 정확히 같다.

각각의 정리는 다른 정리의 한 부분이다.이것은 테일러의 팽창에 기인한다.

{\displaystyle p(x)=\sum _{i=0}^{\frac {p^{p^{{p^{(h)}{i!}}}}(x-h)^{i}}}}}}}{i}}}}}}}{i}}}}}.

$p (x$ + $h)$ 의 $x i$ 계수가 $p$ $p^{(i)}(h)$ ( $p^{(i)}(h)$ ) $p^{(i)}(h)$ ( ( $p^{(i)}(h)$ $){\displaystyle$ p $^{(i)}(h$ $)}$ 의 $p^{(i)}(h)$ 양수임을 암시하는 다항식 $p$ at $h$ 의 계수.따라서 푸리에의 정리나 부단의 정리에서 고찰한 순서는 부항의 변이 횟수가 같다.

이 두 가지 정리 사이의 강한 관계는 19세기에 일어난 우선적 논란과 같은 정리를 위해 여러 개의 이름을 사용하는 것을 설명할 수 있을 것이다.현대 용법에서는 컴퓨터 연산의 경우, 순서들이 부단의 정리보다 푸리에의 정리에서 훨씬 큰 계수를 가지기 때문에 부단의 정리가 일반적으로 선호된다.

증명

각각의 정리가 다른 정리의 진원지이기 때문에 푸리에의 정리를 증명하기에 충분하다.

따라서 다항식 $p (x)$ 와 구간 $(l, r)$ 을 고려하십시오. $x$ 의 $값$ 이 $l$ 에서 r로 증가할 때, p의 파생상품 순서에 있어서의 부호변동의 $수$ 는 x의 $값$ 이 p의 루트나 그 파생상품 중 하나를 통과할 때만 변할 수 있다.

다항식 $p$ 또는 그 파생상품 중 $하나$ 를 f로 나타내자. $f$ 의 다중성 $m$ 의 모든 루트 $h$ 에 대해, 이 다항식은 일부 상수 $a$ 에 대해 $a(x-h)^{m}$ $a(x-h)^{m}$ ( $a(x-h)^{m}$ - h $a(x-h)^{m}$ ) $a(x-h)^{m}$ ${\$ 만큼 $h$ 에 가까운 근사치를 나타낸다.더욱이 $i$ = 1, $...,$ $m$ 의 경우, 그것의 $\textstyle a(x-h)^{m-i}\prod _{j=1}^{i}(m-j+1).$ 파생상품은 $\textstyle a(x-h)^{m-i}\prod _{j=1}^{i}(m-j+1).$ ( $\textstyle a(x-h)^{m-i}\prod _{j=1}^{i}(m-j+1).$ - h $\textstyle a(x-h)^{m-i}\prod _{j=1}^{i}(m-j+1).$ ) m $\textstyle a(x-h)^{m-i}\prod _{j=1}^{i}(m-j+1).$ - $\textstyle a(x-h)^{m-i}\prod _{j=1}^{i}(m-j+1).$ $\textstyle a(x-h)^{m-i}\prod _{j=1}^{i}(m-j+1).$ j $\textstyle a(x-h)^{m-i}\prod _{j=1}^{i}(m-j+1).$ = 1 $\textstyle a(x-h)^{m-i}\prod _{j=1}^{i}(m-j+1).$ ( $\textstyle a(x-h)^{m-i}\prod _{j=1}^{i}(m-j+1).$ - $\textstyle a(x-h)^{m-i}\prod _{j=1}^{i}(m-j+1).$ + 1) $\textstyle a(x-h)^{m-i}\prod _{j=1}^{i}(m-j+1).$ . ${\$ 1)로 근사치를 구한다 $.$ $}$ $f$ 와 $\textstyle a(x-h)^{m-i}\prod _{j=1}^{i}(m-j+1).$ 그 m 첫 $번째$ 파생상품에 의해 형성된 순서에서 $x$ < $h$ 에 $대한$ m 기호 편차가 있고 $x$ ≥ $h$ 에 대한 0이 있다.

이것은 $x$ 가 증가하여 다중성 $m$ 의 $p$ 루트를 통과할 때, 파생상품의 순서에서 부호 변동의 수가 $m만큼$ 감소함을 보여준다.

자, $i$ > $0$ 의 경우 $h$ 를 $p^{(i-1)}.$ 의 ith $f=p^{(i)}$ f $f=p^{(i)}$ = $f=p^{(i)}$ ( $p^{(i-1)}.$ i $){\$ $displaystyle$ $f=p^{($ $p^{(i-1)}.$ $)}}}$ 의 루트가 되지 않는 $p$ 의 $f=p^{(i)}$ ith 파생상품 f = p = p = p = p = $p^{(i-1)}.$ = p $=p$ ^{(i $p^{(i-1)}.$ 의 루트가 되게 $p^{(i-1)}.$ 한다 $.$ $p^{(i-1)}.$ 고려해야 할 두 가지 사례가 있다. $f=p^{(i)}$ $h$ 의 다중성 $m$ 이 짝수이면 f $f=p^{(i)}$ = $f=p^{(i)}$ ( i $){\$ p $p^{(i-1)}$ ( $p^{(i-1)}$ - 1 $){\$ )은 $f=p^{(i)}$ $p^{(i-1)}$ $x$ 가 $h$ 를 통과할 때 일정한 기호를 유지한다 $p^{(i-1)}$ .이는 파생상품 순서의 변동 징후 수가 짝수 $m만큼$ 감소한다는 것을 의미한다.반면 $m$ 이 홀수일 $f=p^{(i)}$ f $f=p^{(i)}$ = $f=p^{(i)}$ ( $){\$ $h$ 에서 기호가 변경되는 $f=p^{(i)}$ 반면 p $p^{(i-1)}$ ( $p^{(i-1)}$ - $){\$ 는 그렇지 않다 $p^{(i-1)}$ . $따라서$ m + 1 $부호$ 변형이 있다.따라서 $x$ 가 $h$ 를 통과할 때 부호변동 횟수는 m $또는$ m + $1$ 중 하나가 감소하는데, $이$ 는 각각의 경우에 음이 아닌 짝수다.

역사

다항식의 진짜 뿌리를 세고 찾아내는 문제는 19일 초에야 체계적으로 연구되기 시작했다.

1807년 프랑수아 부단 데 보이슬라우렌트는 데카르트의 기호 규칙 $($ 간격 $($ 0, +10 $)$ 에 유효함)을 어떤 구간으로든 연장하는 방법을 발견했다.^[2]

Joseph Fourier는 비슷한 정리를 1820년에 발표했는데,^[3] 그는 20년 이상 일했다.^[4]

두 이론의 유사성 때문에 두 이론이 독립적으로 발견되었음에도 불구하고 우선적인 논란이 있었다.^[5]^[6]^[4]19세기 동안 방정식 이론에 관한 교과서에 사용된 것은 일반적으로 푸리에의 공식화 및 증거였다.

19세기에 사용

부단과 푸리에의 이론은 비록 다항식의 진짜 뿌리 수를 구간에 세는 문제를 완전히 해결하지는 못하지만 곧 매우 중요한 것으로 여겨졌다.이 문제는 1827년 스투름에 의해 완전히 해결되었다.

스투름의 정리가 데카르트의 기호 규칙에 근거한 것은 아니지만, 스투름과 푸리에의 정리들은 일련의 숫자의 부호 변이 수를 사용하는 것뿐만 아니라 문제의 유사한 접근에 의해서도 관련이 있다.스투름 자신은 푸리에의 방법에서 영감을 얻었다는 것을 인정했다: ^[7]« Cest en m'appuyant sur les principles qu'il a poses, et et en imitant ses demonstration, que j'ai trovévé les levais emoncer. »로 번역되는 것은 그가 제시한 원칙들에 의존하고 내가 제시하려고 하는 새로운 이론들을 발견했다는 그의 증거를 모방함으로써이다. »

이 때문에 19세기 동안 푸리에와 스투름의 이론은 거의 모든 방정식 이론에 관한 책에서 함께 등장하였다.

푸리에와 부단은 결국 부호 변동의 수가 최대 1개씩 차이가 나는 방식으로 뿌리를 찾는 간격의 크기를 줄이는 문제를 열어 최종 간격에 각각 1개씩의 루트가 포함되어 있음을 증명했다.이 문제는 1834년 알렉산드르 조셉 히둘프 빈센트에 의해 해결되었다.^[8]대략적으로 말해서 빈센트의 정리는 뫼비우스 변형에 의한 변수의 부단의 선형 변형을 대체하기 위해 계속적인 분수를 사용하는 것으로 구성되어 있다.

부단의, 푸리에의, 빈센트 정리는 19세기 말에 망각 속으로 가라앉았다.마지막 저자는 20세기 후반 이전의 이러한 이론들을 언급하였다.^[9]그것들은 콜린스와 아키르타스에 의해 1976년에 다시 소개되었는데, 컴퓨터 대수학에서 컴퓨터의 진짜 뿌리 격리를 위한 효율적인 알고리즘을 제공했기 때문이다.^[10]

참고 항목

참조

^ ^a ^b 이것은 다중성 $m$ 의 루트가 m $루트로$ 계산된다는 것을 의미한다.
^ Budan, François D. (1807). Nouvelle méthode pour la résolution des équations numériques. Paris: Courcier.
^ Fourier, Jean Baptiste Joseph (1820). "Sur l'usage du théorème de Descartes dans la recherche des limites des racines". Bulletin des Sciences, par la Société Philomatique de Paris: 156–165.
^ ^a ^b Arago, François (1859), Biographies of distinguished scientific men, Boston: Ticknor and Fields (English Translation), p. 383
^ Akritas, Alkiviadis G. (1981). "On the Budan–Fourier Controversy". ACM SIGSAM Bulletin. 15 (1): 8–10. doi:10.1145/1089242.1089243. S2CID 6086015.
^ Akritas, Alkiviadis G. (1982). "Reflections on a Pair of Theorems by Budan and Fourier". Mathematics Magazine. 55 (5): 292–298. doi:10.2307/2690097. JSTOR 2690097.
^ Hourya, Benis-Sinaceur (1988). "Deux moments dans l'histoire du Théorème d'algèbre de Ch. F. Sturm". Revue d'histoire des sciences. 41 (2): 108.
^ Vincent, Alexandre Joseph Hidulph (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: 1–34.
^ Serret, Joseph A. (1877). Cours d'algèbre supérieure. Tome I. Gauthier-Villars. pp. 363–368.
^ Collins, G. E.; Akritas, A. G. (1976). Polynomial real root isolation using Descarte's rule of signs. Proceedings of the 1976 ACM symposium on Symbolic and Algebraic Computation. pp. 272–275.

외부 링크

O'Connor, John J.; Robertson, Edmund F., "Budan de Boislaurent", MacTutor History of Mathematics archive, University of St Andrews

[mult-1] 이것은 다중성 $m$ 의 루트가 m $루트로$ 계산된다는 것을 의미한다.

[nmethode-2] Budan, François D. (1807). Nouvelle méthode pour la résolution des équations numériques. Paris: Courcier.

[Fourier-3] Fourier, Jean Baptiste Joseph (1820). "Sur l'usage du théorème de Descartes dans la recherche des limites des racines". Bulletin des Sciences, par la Société Philomatique de Paris: 156–165.

[arago-4] Arago, François (1859), Biographies of distinguished scientific men, Boston: Ticknor and Fields (English Translation), p. 383

[BF-5] Akritas, Alkiviadis G. (1981). "On the Budan–Fourier Controversy". ACM SIGSAM Bulletin. 15 (1): 8–10. doi:10.1145/1089242.1089243. S2CID 6086015.

[Reflections-6] Akritas, Alkiviadis G. (1982). "Reflections on a Pair of Theorems by Budan and Fourier". Mathematics Magazine. 55 (5): 292–298. doi:10.2307/2690097. JSTOR 2690097.

[Sturm-7] Hourya, Benis-Sinaceur (1988). "Deux moments dans l'histoire du Théorème d'algèbre de Ch. F. Sturm". Revue d'histoire des sciences. 41 (2): 108.

[paper_1834-8] Vincent, Alexandre Joseph Hidulph (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: 1–34.

[Serret-9] Serret, Joseph A. (1877). Cours d'algèbre supérieure. Tome I. Gauthier-Villars. pp. 363–368.

[10] Collins, G. E.; Akritas, A. G. (1976). Polynomial real root isolation using Descarte's rule of signs. Proceedings of the 1976 ACM symposium on Symbolic and Algebraic Computation. pp. 272–275.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

Search