Construcción y utilización de las series de polinomios Sturm en un ordenador

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:

, 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:

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:

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:

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:

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"