Construcción y utilización de las series de polinomios Sturm en un ordenador
Enviado por Aladar Peter Santha
Mirando la gráfica de una función polinomio en la pantalla de un ordenador, a veces podría ser difícil decir si el polinomio tiene, en un intervalo dado, un cero simple, varios ceros simples muy cercanos o bien varios ceros simples o múltiples muy cerca uno de otro. En estos casos difíciles, sería bien disponer de un procedimiento seguro para determinar el número de los ceros reales distintos de la función polinomio en un intervalo dado.
Se recuerda que los anillos de polinomios con coeficientes racionales o reales son anillos euclídeos y que dos polinomios de estos anillos tienen siempre máximo común divisor y mínimo común múltiplo. Aunque los polinomios con coeficientes enteros no forman un anillo euclideo, los polinomios con coeficientes enteros se pueden considerar como con coeficientes racionales y se puede demostrar que tendrán máximo común divisor y mínimo común múltiplo con coeficientes enteros.
Si es la función polinomio asociada al polinomio sea la función polinomio asociada al polinomiodonde es un máximo común divisor del polinomioy de su polinomio derivado Entonces ytienen los mismos ceros reales, pero los ceros deson simples.
Definición: Se dice que la sucesión finita de funciones polinomios (no nulas)
(1)
, es una sucesión de Sturm asociada a la función polinomiosi cumple las condiciones siguientes:
1)
2) no tiene ceros reales.
3) no tienen ceros reales comunes.
4) Si entonces
5) Si es un cero real de entonces cambia de signo, de – a +,
, cuando pasa por de manera creciente.
Teorema 1: Cualquiera que sea la función polinomio existe una sucesión de Sturm asociada a ella.
Demostración: Sean y Teniendo en cuenta que es un anillo euclideo, tienen un máximo común divisor. Según el algoritmo modificado de Euclides,
…………………………………………………………………… (2)
, se obtiene la sucesión de polinomios,
(3)
, donde (obviamente) es un máximo común divisor de yy la sucesión (3) cumple las condiciones siguientes:
…………………………. (4)
Hay que demostrar que la sucesión (3) así definida es una sucesión Sturm. En efecto, la condición 1) se cumple obviamente. Teniendo ahora en cuenta que los ceros reales de son simples y que es un máximo común divisor de y de su derivada, resulta que no tiene ceros reales y por tanto, la sucesión considerada cumple también la condición 2).
Evidentemente, y no pueden tener un cero real común, puesto que no tiene ceros reales. Si fuera un cero común de y entonces de
, resultaría que es también un cero de y así sería un cero común de y Repitiendo el razonamiento anterior de un número finito de veces, se llegaría a la conclusión de que es un cero real de La contradicción obtenida demuestra que y no pueden tener raíces reales comunes y por tanto, la sucesión considerada cumple la condición 3).
Si y entonces, según la condición 3),
Por otra parte,
Así pues, la sucesión considerada cumple también la condición 4).
Sea ahora un cero real de Según las hipótesis, es un cero simple de y así no será un cero para Por tanto,
, donde De lo anteriormente expuesto resulta que
, donde
Al ser una función continua en R, resulta que existe un entornode tal que para x perteneciente a este entorno se cumpla la desigualdad Así, el signo de en el intervaloserá tal como se indica en la tabla siguiente:
– | 0 | + | ||||||||
+ | + | |||||||||
– | 0 | + |
, de donde resulta que la sucesión considerada cumple también la condición 5) para que sea una sucesión de Sturm.
Si no es un cero de la función polinomio entonces a la sucesión de Sturm (3) se le puede asociar la sucesión numérica siguiente:
(5)
Eliminando en la sucesión (5) a todos los términos nulos y sustituyendo los restantes términos con sus respectivos signos, se obtiene una sucesión de signos. Cuando dos términos consecutivos de esta sucesión son de signos distintos diremos que hay un cambio en la sucesión de signos. Si es el número de los cambios en la sucesión de signos, se dice que es el número de los cambios de signo en la sucesión (5). Con otras palabras, es el número de los cambios de signo en la sucesión de Sturm considerada en el punto r.
Teorema 2 (de Sturm): Si los números reales y no son ceros de la función polinomio y entonces y el número de los ceros reales distintos de en el intervalo será
Demostración: Si es el número de los cambios de signo en la sucesión de Sturm para está claro que este número solo puede variar, cuando pasa por un cero real de alguna de las funciones polinomios de esta sucesión, ya que las funciones continuas no pueden cambiar de signo sin pasar por el valor cero.
A continuación se distinguen dos casos, según que es un cero de un polinomioo bien del polinomio
a) Si es un cero del polinomio según las propiedades 3) y 4) de la sucesión de Sturm resulta que
(6)
Dado que las funciones y son continuas se puede encontrar tal que estas dos funciones no tengan ceros reales en el intervaloAsí, en este intervalo, y conservan el signo de y respectivamente.
Por tanto, de la desigualdad (6) se obtienen las dos desigualdades siguientes:
(7)
(8)
Por consiguiente, en la sucesión
(9)
, habrá un solo cambio de signo, puesto que, según la relación (7), y son de signos distintos y así uno de ellos tendrá el signo de
De la misma manera, de (8) resulta que en la sucesión
, habrá un solo cambio de signo.
Así pues, no cambia cuando pasa, de manera creciente, por un cero de una función polinomio que ocupa una posición intermedia en la sucesión de Sturm.
b) Si es un cero real del polinomio no puede ser un cero para ya que es un cero simple de Por tanto, existe tal que en el intervalono tenga ningún cero real y así no cambiará de signo en este intervalo. Suponiendo que es de signo positivo en el intervaloresulta que es creciente en este intervalo y así cuando pasa por el cero de manera creciente, cambiará de signo, de menos en más. Así, en la sucesión de Sturm correspondiente al punto habrá un cambio de signo entre los términos:
, sin embargo, entre los términos
, de la sucesión de Sturm correspondiente al punto no habrá cambio de signo. Por consiguiente, cuando pasa de manera creciente por en la sucesión de Sturm se pierde un cambio de signo.
Razonando de manera análoga, se llega a la misma conclusión cuando se supone que es de signo negativo sobre el intervaloDe esta manera, cuando crece, desde el valor hasta el valor se disminuirá en uno, cada vez que pasa por un cero de y así la diferencia será igual con el número de los ceros reales de la función polinomio en el intervalo
Ejemplo 1: Sea la función polinomio asociada al polinomio
Se verifica fácilmente que 1 es un máximo común divisor del polinomio y Así la sucesión de Sturm asociada a está formada de las funciones siguientes:
(10)
, definidas por:
Es fácil averiguar que 3 es una cota superior de los ceros positivos de y que es una cota inferior de los ceros negativos de la misma función. Así los ceros reales de pertenecen al intervalo Los signos de los valores de las funciones (10), calculadas en las extremidades de este intervalo, se exponen en la tabla siguiente:
-2 | + | – | + | – | + | 4 |
3 | + | + | + | + | + | 0 |
Así pues, el número de los ceros reales distintos de es .
Dado que
, y
, los números 1, 0 y 1 no son ceros de y así, para obtener más información sobre los ceros, podemos considerar la tabla:
-2 | + | – | + | – | + | 4 |
-1 | – | + | + | – | + | 3 |
0 | + | + | – | + | + | 2 |
1 | – | – | + | + | + | 1 |
3 | + | + | + | + | + | 0 |
Puesto que
, tiene dos ceros positivos y dos negativos. Luego, de las igualdades
, resulta que tiene un cero único en cada uno de los intervalos:
Ejemplo 2: Seala función polinomio asociada al polinomio
El máximo común divisor de es y
La sucesión de Sturm asociada a está compuesta de las funciones polinomios
, definidas por:
Puesto que es una cota inferior de los ceros negativos de y 4 es una cota superior para los ceros positivos de los ceros reales de pertenecen al intervalo Calculando los valores de la función en los puntos:
, se observa que ninguno de ellos es un cero de Para hallar el número de los ceros reales de y para ver la distribución de estos ceros en el intervalo anterior, consideremos la tabla:
-4 | – | + | – | + | – | + | 5 |
-2 | – | + | – | + | – | + | 5 |
-1.5 | + | – | + | + | – | + | 4 |
-1 | – | – | + | – | – | + | 3 |
0 | – | + | + | – | – | + | 3 |
1 | + | – | – | – | + | + | 2 |
1.5 | – | – | – | + | + | + | 1 |
2 | + | + | + | + | + | + | 0 |
4 | + | + | + | + | + | + | 0 |
Puesto que
, tiene 5 ceros reales distintos. Por otra parte, de
, resulta que no tiene ceros reales en los intervalos
Así, todas los ceros reales de deben pertenecer al conjunto:
Dado que
, resulta que tiene dos ceros negativos y tres positivos.
Finalmente, de las igualdades
, resulta que cada uno de los intervalos siguientes contiene exactamente un cero de
Ejemplo 3: Sea la función polinomio asociada al polinomio
Se puede averiguar que los polinomios P(X) y P'(X) son primos entre sí, es decir, 1 es un máximo común divisor de ellos. La sucesión de Sturm asociada a está compuesta de las funciones polinomios , definidas por:
Puesto que -1 y 1 son una cota inferior de los ceros negativos y una cota superior de los ceros positivos de respectivamente, los ceros reales de pertenecen al intervalo Los signos de los valores de las funciones polinomios de la sucesión de Sturm, calculadas en las extremidades del intervalo anterior, quedan expuestos en la tabla:
-1 | + | – | – | – | + | 2 |
1 | + | + | – | – | + | 2 |
Puesto que resulta que no tiene ceros reales.
Durante mucho tiempo el teorema de Sturm era considerado como un teorema muy interesante pero de poca utilidad, debido al volumen de los cálculos. Con la llegada de la informática se puede decir que ha llegado la hora del teorema de Sturm, en el sentido que su utilización en los ordenadores ha llegado a ser tan sencilla y cómoda como la de los otros teoremas.
A continuación se exponen los procedimientos para hallar la serie de polinomios Sturm asociada a un polinomio con coeficientes enteros. Si se trata de un polinomio con coeficientes decimales, antes de introducirlo en el ordenador, hay que multiplicar el polinomio con una potencia de 10, para que el polinomio obtenido tenga coeficientes enteros. En el caso de un polinomio con coeficientes fraccionarios, hay que multiplicar el polinomio con el mínimo común múltiplo de los denominadores de sus coeficientes.
El programa siguiente determina la serie de polinomios Sturm asociado a un polinomio dado, calcula una cota superior de los ceros positivos y una cota inferior de los negativos y finalmente halla el número de los ceros reales. Los coeficientes del polinomio tienen que ser enteros y contenidos en los elementos de una matriz unidimensional de tipo String. Las cotas de los ceros mencionadas se determina por un método anónimo y simple para programarlo, aunque existen métodos mejores, cuya programación necesita un poco más de esfuerzo.
Public Function AlgoritmoSturm(ByRef p0() As String, ByVal n As Integer) As String
Dim i As Integer, i0 As Integer, k1 As Integer, j0 As Integer, js As Integer
Dim g0 As Integer, g1 As Integer, g2 As Integer, gz As Integer, gx As Integer
Dim sw2 As Integer, gc As Integer, s1 As Integer, sr As Integer, ist As Integer
Dim si As Integer, sd As Integer, fp() As Integer, ai As Double, bi As Double
Dim m2 As String, m11 As String, rp As String, p1() As String, x(2) As String
Dim rr() As String, pd() As String, pi() As String, rc As String, x0() As String
Dim ps() As String, sci As String, scs As String, s() As String, rrr As Integer
Dim mcd() As String, pd0() As String, cotas() As Double, cx1 As String
Dim cx2 As String, c1() As String, c2() As String, q0() As String, pr As String
Dim ra As String, cxp0 As String, cxp0d As String, cx0 As String, cxpd As String
rc = Chr$(13) + Chr$(10): q0() = p0(): cxp0 = FormatoPol(q0())
' Derivada del polinomio
g0 = UBound(p0())
ReDim pd0(g0 – 1)
For i = 0 To g0 – 1
x(1) = Mid$(Str$(g0 – i), 2): x(2) = p0(i): pd0(i) = Multiplicar(x(), n)
Next i
cxp0d = FormatoPol(pd0())
mcd() = CalculoMCDPOL(q0(), pd0(), n)
cx0 = FormatoPol(mcd())
If UBound(mcd()) <> 0 Then
c1() = DivisionEspecialPOL(p0(), mcd(), n)
Else
c1() = p0()
End If
cx1 = FormatoPol(c1())
g1 = UBound(c1())
cotas() = CotasCeros(c1())
ai = cotas(2): bi = cotas(1)
ReDim pd(g1 – 1)
For i = 0 To g1 – 1
x(1) = Mid$(Str$(g1 – i), 2): x(2) = c1(i): pd(i) = Multiplicar(x(), n)
Next i
cxpd = FormatoPol(pd())
c2() = pd(): g2 = g1 – 1: js = 0: ist = 1
sr = (g1 + 2) * (g1 + 3) / 2
ReDim s(sr), z(g1), fp(g1 + 2)
For i = 0 To g1
s(js) = c1(i): js = js + 1
Next i
fp(0) = -1: fp(ist) = js – 1
ist = ist + 1: gz = g2 + 1
c2() = RutinaSturm(c2(), n)
For i = 0 To gz – 1
s(js) = c2(i): js = js + 1
Next i
fp(ist) = js – 1
ist = ist + 1
Do
gz = 0: s1 = 0: gc = g1 – g2
For i0 = 0 To gc
If c1(i0) <> "0" Then
x(1) = c1(i0): x(2) = c2(0): x(1) = MinComMult(x(), n): x(2) = c1(i0)
rr() = DivisionEuclidea(x(), n): m11 = rr(1)
If Left$(m11, 1) = "-" Then m11 = Mid$(m11, 2)
If m11 <> "1" Then
For k1 = i0 To g1
x(1) = c1(k1): x(2) = m11: c1(k1) = Multiplicar(x(), n)
Next k1
End If
x(1) = c1(i0): x(2) = c2(0): rr() = DivisionEuclidea(x(), n): m2 = rr(1)
For k1 = i0 To i0 + g2
x(1) = c2(k1 – i0): x(2) = m2: rp = Multiplicar(x(), n)
x(1) = c1(k1): x(2) = rp: c1(k1) = Restar(x(), n)
Next k1
End If
Next i0
ReDim z(g1)
j0 = gc + 1: j = j0
For i = j0 To g1
If c1(i) <> "0" Then
z(i – j) = c1(i): gz = gz + 1
If s1 = 0 Then s1 = s1 + 1
Else
If s1 = 1 Then
z(i – j) = c1(i): gz = gz + 1
Else
j = j + 1
End If
End If
Next i
sw2 = 0
For i = 0 To gz – 1
If z(i) <> "0" Then
ReDim p1(gz – 1)
For j = 0 To gz – 1: p1(j) = z(j): Next j
c1() = c2(): g1 = UBound(c1())
For i0 = 0 To gz – 1
If Left$(p1(i0), 1) = "-" Then
p1(i0) = Mid$(p1(i0), 2)
Else
If p1(i0) <> "0" Then p1(i0) = "-" + p1(i0)
End If
Next i0
c2() = p1()
g2 = UBound(c2())
c2() = RutinaSturm(c2(), n)
For i0 = 0 To gz – 1
s(js) = c2(i0): js = js + 1
Next i0
fp(ist) = js – 1: ist = ist + 1
c2() = RutinaSturm(c2(), n)
sw2 = 1: Exit For
End If
Next i
If sw2 = 0 Then Exit Do
Loop
cx2 = ""
For i = 0 To ist – 2
cx2 = cx2 + "Polinomio"
cx2 = cx2 + " (" + Str$(i + 1) + ") = "
gx = fp(i + 1) – fp(i) – 1
ReDim x0(gx)
For j = 0 To gx: x0(j) = s(fp(i) + 1 + j): Next j
cx2 = cx2 + FormatoPol(x0()) + rc
Next i
' =========== Número de todos los ceros reales ===========
' Valores de los polinomios Sturm en el punto ai.
ReDim pi(ist – 1), ps(ist – 1)
For i = 1 To ist – 2
pi(i) = s(fp(i – 1) + 1)
For j = fp(i – 1) + 2 To fp(i)
x(1) = pi(i): x(2) = ai: pi(i) = MultiplicarDec(x(), n)
x(1) = pi(i): x(2) = s(j): pi(i) = SumarDec(x(), n)
Next j
If pi(i) <> "0" Then
If Left$(pi(i), 1) <> "-" Then pi(i) = "1" Else pi(i) = "-1"
End If
Next i
pi(i) = s(js – 1)
'Valores de los polinomios Sturm en el punto bi.
For i = 1 To ist – 2
ps(i) = s(fp(i – 1) + 1)
For j = fp(i – 1) + 2 To fp(i)
x(1) = ps(i): x(2) = bi: ps(i) = MultiplicarDec(x(), n)
x(1) = ps(i): x(2) = s(j): ps(i) = SumarDec(x(), n)
Next j
If ps(i) <> "0" Then
If Left$(ps(i), 1) <> "-" Then ps(i) = "1" Else ps(i) = "-1"
End If
Next i
ps(i) = s(js – 1)
For i = 1 To ist – 2
If pi(i) <> "0" Then
If Val(pi(i)) * Val(pi(i + 1)) < 0 Then si = si + 1
Else
If Val(pi(i – 1)) * Val(pi(i + 1)) <= 0 Then si = si + 1
End If
Next i
For i = 1 To ist – 2
If ps(i) <> "0" Then
If Val(ps(i)) * Val(ps(i + 1)) < 0 Then sd = sd + 1
Else
If Val(ps(i – 1)) * Val(ps(i + 1)) <= 0 Then sd = sd + 1
End If
Next i
rrr = Abs(si – sd)
' Sucesiones de signos Sturm
sci = "": scs = ""
For i = 1 To ist – 1
If pi(i) <> "0" Then
If pi(i) = "1" Then sci = sci + " + " Else sci = sci + " – "
End If
Next i
For i = 1 To ist – 1
If ps(i) <> "0" Then
If ps(i) = "1" Then scs = scs + " + " Else scs = scs + " – "
End If
Next i
ra = rc + "Polonomio:" + rc
ra = ra + "P( X ) = " + cxp0 + rc + " " + rc
ra = ra + "Polinomio derivado:" + rc
ra = ra + "P'( X ) = " + cxp0d + rc + " " + rc
ra = ra + "M.C.D.[ P( X ) ; P' ( X ) ) = " + cx0 + rc + " " + rc
If cx0 <> "1" Then
ra = ra + "P0(X) = P( X ) / M.C.D.[ P( X ) ; P'( X ) ] " + rc
ra = ra + rc + "P0(X)= " + cx1 + rc
ra = ra + "P0'(X) = " + cxpd + rc
Else
ra = ra + rc + "P0(X)=P(X) , P0'(X)=P'(X)" + rc
End If
ra = ra + rc + "Cota inferior de los ceros negativos = " + Str$(ai) + rc
ra = ra + "Cota superior de los ceros positivos = " + Str$(bi) + rc
ra = ra + rc + "Sucesión de polinomios Sturm:" + rc
ra = ra + rc + cx2 + rc
ra = ra + rc + "Suceciones de signos:" + rc
ra = ra + rc + sci + rc
ra = ra + scs + rc
ra = ra + rc + "Número total de los ceros reales distintos = " + Str$(rrr) + rc
AlgoritmoSturm = ra
End Function
"= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
Public Function RutinaSturm(ByRef c2() As String, ByVal n As Integer)
Dim i As Integer, rr() As String
Dim rr0 As String, x(2) As String
Dim g2 As Integer
g2 = UBound(c2())
rr0 = c2(0)
For i = 0 To g2
If c2(i) <> "0" Then
x(1) = rr0: x(2) = c2(i)
rr0 = MaxComDiv(x(), n)
If rr0 = "1" Then Exit For
End If
Next i
If rr0 <> "1" Then
For i = 0 To g2
x(1) = c2(i): x(2) = rr0
rr() = DivisionEuclidea(x(), n)
c2(i) = rr(1)
Next i
End If
RutinaSturm = c2()
End Function
"= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
Public Function CotasCeros(ByRef q() As String) As Variant
' TRANSFORMACIONES DEL POLINOMIO
Dim i As Integer, z As Integer, e As Integer, gq As Integer
Dim a As Double, b As Double, r(2) As Double, ct() As Double
gq = UBound(q())
ReDim ct(gq, 2) As Double
For i = 0 To gq
ct(i, 1) = Val(q(i))
Next i
' Transformación de X en -X
e = gq Mod 2
For i = 0 To gq
If e <> 0 Then
ct(i, 2) = (-1) ^ (i + 1) * ct(i, 1)
Else
ct(i, 2) = (-1) ^ i * ct(i, 1)
End If
Next i
' r(1) cota superior de los ceros positivos
' r(2) cota inferior de los ceros negativos
' Método Anónimo
a = Abs(ct(1, 1))
For i = 2 To gq
If Abs(ct(i, 1)) > a Then
a = Abs(ct(i, 1))
End If
Next i
b = Abs(ct(0, 1))
For i = 1 To gq – 1
If Abs(ct(i, 1)) > b Then
b = Abs(ct(i, 1))
End If
Next i
r(1) = 1 + a / Abs(ct(0, 1))
r(2) = -r(1)
r(1) = (Int(r(1) * 100) + 1) / 100
r(2) = (Int(r(2) * 100) – 1) / 100
CotasCeros = r()
End Function
"= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
Public Function FormatoPol(ByRef x0() As String) As String
Dim i As Integer, gx As Integer, ax As String, cx As String
gx = UBound(x0())
For i = 0 To gx
If x0(i) <> "0" Then
If i = 0 Then
If x0(0) <> "1" And x0(0) <> "-1" Then
cx = x0(0)
Else
If gx <> 0 Then
If x0(0) = "-1" Then
cx = "-"
End If
Else
If x0(0) = "-1" Then
cx = Str$(-1)
Else
cx = Mid$(Str$(1), 2)
End If
End If
End If
If gx <> 0 Then
If gx = 1 Then
cx = cx + " X"
Página siguiente |