Teorema de Budan

Contar raíces reales de un polinomio en un intervalo

En matemáticas, el teorema de Budan es un teorema que permite acotar el número de raíces reales de un polinomio en un intervalo y calcular la paridad de este número. Fue publicado en 1807 por François Budan de Boislaurent .

Joseph Fourier publicó un teorema similar de forma independiente en 1820. Cada uno de estos teoremas es un corolario del otro. El enunciado de Fourier aparece con más frecuencia en la literatura del siglo XIX y se lo ha denominado teorema de Fourier , de Budan-Fourier , de Fourier-Budan e incluso teorema de Budan.

La formulación original de Budan se utiliza en algoritmos modernos y rápidos para el aislamiento de raíces reales de polinomios.

Variación de signos

Sea una sucesión finita de números reales. Una variación de signo o cambio de signo en la sucesión es un par de índices i < j tales que y j = i + 1 o para todo k tal que i < k < j . ${\displaystyle c_{0},c_{1},c_{2},\ldots c_{k}}$ ${\displaystyle c_{i}c_{j}<0,}$ ${\displaystyle c_{k}=0}$

En otras palabras, se produce una variación de signo en la secuencia en cada lugar donde cambian los signos, al ignorar los ceros.

Para estudiar las raíces reales de un polinomio, se puede utilizar el número de variaciones de signo de varias sucesiones. Para el teorema de Budan, es la sucesión de los coeficientes. Para el teorema de Fourier, es la sucesión de valores de las derivadas sucesivas en un punto. Para el teorema de Sturm , es la sucesión de valores en un punto de la sucesión de Sturm .

La regla de los signos de Descartes

Todos los resultados descritos en este artículo se basan en la regla de los signos de Descartes.

Si p ( x ) es un polinomio univariante con coeficientes reales, denotemos por # ₊ ( p ) el número de sus raíces reales positivas, contadas con su multiplicidad, ^[1] y por v ( p ) el número de variaciones de signo en la secuencia de sus coeficientes. La regla de los signos de Descartes afirma que

v ( p ) – # ₊ ( p ) es un entero par no negativo.

En particular, si v ( p ) ≤ 1 , entonces se tiene # ₊ ( p ) = v ( p ) .

Declaración de Budan

Dado un polinomio univariado p ( x ) con coeficientes reales, denotemos por # _{( ℓ , r ]} ( p ) el número de raíces reales, contadas con sus multiplicidades, ^[1] de p en un intervalo semiabierto ( ℓ , r ] (con ℓ < r números reales). Denotemos también por v _h ( p ) el número de variaciones de signo en la sucesión de los coeficientes del polinomio p _h ( x ) = p ( x + h ) . En particular, se tiene v ( p ) = v ₀ ( p ) con la notación de la sección precedente.

El teorema de Budan es el siguiente:

${\displaystyle v_{\ell }(p)-v_{r}(p)-\#_{(\ell ,r]}}$es un entero par no negativo.

Como no es negativo, esto implica ${\displaystyle \#_{(\ell ,r]}}$ ${\displaystyle v_{\ell }(p)\geq v_{r}(p).}$

Esta es una generalización de la regla de los signos de Descartes, ya que, si uno elige r suficientemente grande, es mayor que todas las raíces reales de p , y todos los coeficientes de son positivos, es decir Por lo tanto y lo que hace de la regla de los signos de Descartes un caso especial del teorema de Budan. ${\displaystyle p_{r}(x)}$ ${\displaystyle v_{r}(p)=0.}$ ${\displaystyle v_{0}(p)=v_{0}(p)-v_{r}(p),}$ ${\displaystyle \#_{+}=\#_{(0,r)},}$

En cuanto a la regla de los signos de Descartes, si uno tiene Esto significa que, si uno tiene una "prueba de raíz cero" y una "prueba de raíz única". ${\displaystyle v_{\ell }(p)-v_{r}(p)\leq 1,}$ ${\displaystyle \#_{(\ell ,r]}=v_{\ell }(p)-v_{r}(p).}$ ${\displaystyle v_{\ell }(p)-v_{r}(p)\leq 1}$

Ejemplos

1. Dado el polinomio y el intervalo abierto , se tiene ${\displaystyle p(x)=x^{3}-7x+7,}$ ${\displaystyle (0,2)}$

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

Así, el teorema de Budan afirma que el polinomio tiene dos o cero raíces reales en el intervalo abierto. ${\displaystyle v_{0}(p)-v_{2}(p)=2-0=2,}$ ${\displaystyle p(x)}$ ${\displaystyle (0,2).}$

2. Con el mismo polinomio se tiene ${\displaystyle p(x)=x^{3}-7x+7}$

${\displaystyle p(x+1)=(x+1)^{3}-7(x+1)+7=x^{3}+3x^{2}-4x+1.}$

Por tanto, el teorema de Budan afirma que el polinomio no tiene raíz real en el intervalo abierto. Este es un ejemplo del uso del teorema de Budan como prueba de raíz cero. ${\displaystyle v_{0}(p)-v_{1}(p)=2-2=0,}$ ${\displaystyle p(x)}$ ${\displaystyle (0,1).}$

La declaración de Fourier

El teorema de Fourier sobre raíces reales de polinomios , también llamado teorema de Fourier-Budan o teorema de Budan-Fourier (a veces simplemente teorema de Budan ), es exactamente el mismo que el teorema de Budan, excepto que, para h = l y r , la secuencia de los coeficientes de p ( x + h ) se reemplaza por la secuencia de las derivadas de p en h .

Cada teorema es un corolario del otro. Esto resulta de la expansión de Taylor .

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

del polinomio p en h , lo que implica que el coeficiente de x ⁱ en p ( x + h ) es el cociente de por i ! , un número positivo. Por lo tanto, las sucesiones consideradas en el teorema de Fourier y en el teorema de Budan tienen el mismo número de variaciones de signo. ${\displaystyle p^{(i)}(h)}$

Esta fuerte relación entre los dos teoremas puede explicar la controversia sobre la prioridad que se produjo en el siglo XIX y el uso de varios nombres para el mismo teorema. En el uso moderno, para los cálculos informáticos, el teorema de Budan es generalmente preferido ya que las secuencias tienen coeficientes mucho mayores en el teorema de Fourier que en el de Budan, debido al factor factorial.

Prueba

Como cada teorema es un corolario del otro, basta con demostrar el teorema de Fourier.

Prueba:

Sea el grado de , de modo que son polinomios no constantes, es una constante distinta de cero y son todos idénticamente cero. ${\displaystyle n}$ ${\displaystyle f}$ ${\displaystyle f,f',...,f^{(n-1)}}$ ${\displaystyle f^{(n)}}$ ${\displaystyle f^{(n+1)},...}$

En función del signo la variación sólo puede variar en una raíz de al menos uno de ${\displaystyle t,}$ ${\displaystyle v_{t}(f)}$ ${\displaystyle f,f',...,f^{(n-1)}.}$

Si varía en , entonces, para algunos , tiene una raíz en , y cada uno de no tiene raíz en . ${\displaystyle v_{t}(f)}$ ${\displaystyle t=r}$ ${\displaystyle k}$ ${\displaystyle f^{(k)}(x)}$ ${\displaystyle t}$ ${\displaystyle f,f',...,f^{(k-1)}}$ ${\displaystyle t}$

Si , entonces para algún y algún polinomio que satisface . Al calcular explícitamente en y para un pequeño , tenemos ${\displaystyle k=0}$ ${\displaystyle f(x)=(x-r)^{s}p(x-r)}$ ${\displaystyle s\geq 1}$ ${\displaystyle p}$ ${\displaystyle p(0)\neq 0}$ ${\displaystyle f,f',...,f^{(n)}}$ ${\displaystyle r}$ ${\displaystyle r-\epsilon }$ ${\displaystyle \epsilon }$ ${\displaystyle v_{r}(f)=v_{r-\epsilon }(f)-s-2s',\quad \exists s'\geq 0.}$

En esta ecuación, el término se debe a que los signos de las derivadas superiores pueden llegar a ser cero . ${\displaystyle -s}$ ${\displaystyle f,f',...,f^{(s)}}$ ${\displaystyle (-1)^{s}\operatorname {sign} (p(0)),(-1)^{s-1}\operatorname {sign} (p(0)),...,-\operatorname {sign} (p(0)),\operatorname {sign} (p(0))}$ ${\displaystyle 0,0,...,0,\operatorname {sign} (p(0))}$ ${\displaystyle -2s',\quad \exists s'\geq 0}$

Si , entonces, dado que algunas derivadas se ponen a cero en , pero ambas y permanecen distintas de cero, solo perdemos un número par de cambios de signo: ${\displaystyle k\geq 1}$ ${\displaystyle r}$ ${\displaystyle f^{(k-1)}(x)}$ ${\displaystyle f^{(n)}(x)}$

$${\displaystyle v_{r}(f)=v_{r-\epsilon }(f)-2s',\quad \exists s'\geq 0}$$

Si varía en , entonces argumentando de manera similar, encontramos que para ambos casos, podemos tomar un pequeño tal que . ${\displaystyle v_{t}(f)}$ ${\displaystyle t=l}$ ${\displaystyle \epsilon }$ ${\displaystyle v_{l+\epsilon }(f)=v_{l}(f)}$

Historia

El problema de contar y localizar las raíces reales de un polinomio comenzó a estudiarse sistemáticamente recién a principios del siglo XIX.

En 1807, François Budan de Boislaurent descubrió un método para extender la regla de los signos de Descartes —válida para el intervalo (0, +∞) —a cualquier intervalo. ^[2]

Joseph Fourier publicó un teorema similar en 1820 ^[3] , en el que trabajó durante más de veinte años. ^[4]

Debido a la similitud entre ambos teoremas, hubo una controversia prioritaria, ^{[5] [6]} a pesar de que ambos teoremas fueron descubiertos independientemente. ^[4] Fueron generalmente la formulación y la demostración de Fourier las que se utilizaron, durante el siglo XIX, en los libros de texto sobre la teoría de ecuaciones .

Uso en el siglo XIX

Los teoremas de Budan y Fourier fueron considerados muy importantes, aunque no resuelven completamente el problema de contar el número de raíces reales de un polinomio en un intervalo. Este problema fue resuelto completamente en 1827 por Sturm .

Aunque el teorema de Sturm no se basa en la regla de los signos de Descartes , los teoremas de Sturm y de Fourier están relacionados no sólo por el uso del número de variaciones de signo de una secuencia de números, sino también por un enfoque similar del problema. El propio Sturm reconoció haberse inspirado en los métodos de Fourier: ^[7] « C'est en m'appuyant sur les principes qu'il a posés, et en imitant ses démonstrations, que j'ai trouvé les nouveaux théorèmes que je vais énoncer. » que se traduce como « Es apoyándome en los principios que él ha expuesto e imitando sus demostraciones como he encontrado los nuevos teoremas que estoy a punto de presentar. »

Debido a esto, durante el siglo XIX, los teoremas de Fourier y Sturm aparecieron juntos en casi todos los libros sobre teoría de ecuaciones.

Fourier y Budan dejaron abierto el problema de reducir el tamaño de los intervalos en los que se buscan raíces de forma que, finalmente, la diferencia entre los números de variaciones de signo sea como máximo uno, permitiendo certificar que los intervalos finales contienen como máximo una raíz cada uno. Este problema fue resuelto en 1834 por Alexandre Joseph Hidulph Vincent. ^[8] Grosso modo, el teorema de Vincent consiste en utilizar fracciones continuas para sustituir las transformaciones lineales de la variable de Budan por transformaciones de Möbius .

Los teoremas de Budan, Fourier y Vincent cayeron en el olvido a finales del siglo XIX. El último autor que los mencionó antes de la segunda mitad del siglo XX fue Joseph Alfred Serret . ^[9] Fueron introducidos nuevamente en 1976 por Collins y Akritas, para proporcionar, en álgebra computacional , un algoritmo eficiente para el aislamiento de raíces reales en computadoras. ^[10]

Véase también

• Propiedades de las raíces polinómicas
• Algoritmo de búsqueda de raíces

Referencias

1. Esto significa que una raíz de multiplicidad m se cuenta como m raíces.
2. Budan, François D. (1807). Nuevo método para la resolución de ecuaciones numéricas. París: Courcier.
3. Fourier, Jean Baptiste José (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.
4. Arago, François (1859), Biografías de científicos distinguidos, Boston: Ticknor and Fields (traducción al inglés), pág. 383
5. Akritas, Alkiviadis G. (1981). "Sobre la controversia Budan-Fourier". Boletín ACM SIGSAM . 15 (1): 8–10. doi : 10.1145/1089242.1089243 . S2CID  6086015.
6. Akritas, Alkiviadis G. (1982). "Reflexiones sobre un par de teoremas de Budan y Fourier". Revista de Matemáticas . 55 (5): 292–298. doi :10.2307/2690097. JSTOR  2690097.
7. Benis-Sinaceur, Hourya (1988). "Deux momentos dans l'histoire du Théorème d'algèbre de Ch. F. Sturm" (PDF) . Revista de Historia de las Ciencias . 41 (2): 99-132 (pág. 108). doi :10.3406/rhs.1988.4093. S2CID  201270382.
8. Vicente, 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.
9. Serret, José A. (1877). Cours d'algèbre supérieure. Tomo I. Gauthier-Villars. págs. 363–368.
10. Collins, GE ; Akritas, AG (1976). Aislamiento de raíces reales polinómicas utilizando la regla de signos de Descarte. Actas del simposio ACM de 1976 sobre computación simbólica y algebraica. págs. 272–275. doi : 10.1145/800205.806346 .

Enlaces externos

O'Connor, John J.; Robertson, Edmund F. , "Budan de Boislaurent", Archivo MacTutor de Historia de las Matemáticas , Universidad de St Andrews