Inicio - Matematicas

Construccion y utilizacion de las series de polinomios Sturm en un ordenador

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 de decir si el polinomio tiene, en un intervalo dado, una raíz simple, varias raíces simples muy cercanas o bien varias raíces simples o múltiples muy cerca una de otra. 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 P(X), 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 1: Se dice que la sucesión finita de funciones polinomios (no nulas)

(1)

, es una sucesión de Sturm, asociada a la función polinomio si cumple las condiciones siguientes:

1)

2) no tiene raíces reales.

3) no tienen raíces reales comunes.

4) Si entonces

5) Si es una raíz real de f, entonces cambia de signo, de – a +,

, cuando x 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 par, tienen un máximo común divisor. Suponiendo que este máximo común divisor es el resto parcial en el algoritmo modificado de Euclides, tendremos:

(2)

A continuación sean,

(3)

Hay que demostrar que la sucesión (1) así definida cumple las cinco condicione. En efecto, la condición 1) se cumple obviamente. Teniendo ahora en cuenta que las raíces reales de son simples y que es un máximo común divisor de y su derivada, resulta que no tiene raíces reales y por tanto, la sucesión considerada cumple también la condición 2).

Si en las relaciones (2) se tiene en cuenta las igualdades (3), se obtiene que

(4)

Obviamentey no pueden tener una raíz real común, puesto que no tiene raíces reales. Si fuera una raíz común de y entonces de

, resultaría que es también una raíz de y así sería una raíz 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 una raíz 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 una raíz real de Según las hipótesis, es una raíz simple de y así no será una raíz 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:

x

0

- 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 una raíz de la función polinomio entonces a la sucesión de Sturm (3.1.1) 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 son 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 a y b no son raíces de la función polinomio y entonces y la función polinomio tendrá en el intervalo raíces reales distintas.

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 entonces puede variar, cuando x pasa por una raíz real a 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 a es una raíz de un polinomioo bien del polinomio

a) Si es una raíz 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 raíces 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 x pasa, de manera creciente, por una raíz de una función polinomio que ocupa una posición intermedia en la sucesión de Sturm.

b) Si a es una raíz real del polinomio a no puede ser una raíz para ya que a es una raíz simple de Por tanto, existe tal que en el intervalono tenga ninguna raíz 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 x pasa por la raíz a, 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 x 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 x crece, desde el valor a hasta el valor b, se disminuirá en uno, cada vez que x pasa por una raíz de y así la diferencia será igual con el número de las raíces reales de la función polinomio en el intervalo

Ejemplo 1: Sea f la función polinomio asociada al polinomio

Se verifica fácilmente que 1 es un máximo común divisor del polinomio y de su polinomio derivado

Así, la sucesión de Sturm asociada a está formada de las funciones polinomios siguientes:

(10)

, definidas por

Calculando una cota superior de las raices positivas y una cota inferior de las negativas de se puede averiguar que las raíces reales depertenecen al intervalo Los signos de los valores de las funciones (10), calculadas en las extremidades de este intervalo, se exponen en la tabla siguiente:

x

f1

f2

f3

f4

f5

W(x)

-2

+

-

+

-

+

4

3

+

+

+

+

+

0

Así pues, el número de las raíces reales distintas de es

Dado que

, y

, los números 1,0 y 1 no son raíces de y así, para obtener más información sobre las raíces, podemos considerar la tabla:

x

W(x)

-2

+

-

+

-

+

4

-1

-

+

+

-

+

3

0

+

+

-

+

+

2

1

-

-

+

+

+

1

3

+

+

+

+

+

0

Puesto que

, tiene dos raíces positivas y dos negativas. Luego, de las igualdades

, resulta que tiene única 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 polinómicas

, definidas por:

Utilizando el método expuesto en el teorema 3.3.6 para el cálculo da las cotas de las raíces reales, se obtiene que las raíces reales de pertenecen al intervalo (4,4). Calculando los valores de la función en los puntos:

, se observa que ninguno de ellos es una raíz de Para hallar el número de las raíces reales de y para ver la distribución de estas raíces en el intervalo anterior, consideremos la tabla:

x

W(x)

4

-

+

-

+

-

+

5

-2

-

+

-

+

-

+

5

-1.5

+

-

+

+

-

+

4

-1

-

-

+

-

-

+

3

0

-

+

+

-

-

+

3

1

+

-

-

-

+

+

2

1.5

-

-

-

+

+

+

1

2

+

+

+

+

+

+

0

4

+

+

+

+

+

+

0

Puesto que

, tiene 5 raíces reales. Por otra parte, de

, resulta que no tiene raíces reales en los intervalos

Así, todas las raíces reales de deben pertenecer al conjunto:

Dado que

, resulta que tiene dos raíces negativas y tres positivas.

Finalmente, de las igualdades

, resulta que cada uno de los intervalos siguientes contiene exactamente una raíz de

Ejemplo 4.11.3: Sea f 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:

Calculando una cota superior para las raíces positivas y una cota inferior para las raíces negativas de se obtiene que las raíces de pertenecen al intervalo (1,1).

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:

x

W(x)

-1

+

-

-

-

+

2

1

+

+

-

-

+

2

Puesto que

, resulta que no tiene raíces 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 sencillo y cómodo como la de cualquier otro teorema.

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.

A continuación se expone un programa que determina la serie de polinomios Sturm asociado a un polinomio dado, calcula una cota superior de las raíces positivas y una cota inferior de las negativas y finalmente halla el número de las raíces reales. Los coeficientes del polinomio tienen que ser enteros y contenidos en los elementos de una matriz unidimensional de tipo String. Las cotas de las raíces 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, rrr As Integer

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, producto As String, sci As String, scs As String

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

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() = CotasRaices(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)

End If

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

End If

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

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 las raíces 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

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

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

End If

Else

If Val(pi(i - 1)) * Val(pi(i + 1)) <= 0 Then

si = si + 1

End If

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

End If

Else

If Val(ps(i - 1)) * Val(ps(i + 1)) <= 0 Then

sd = sd + 1

End If

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

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

End If

Next i

ra = rc + “Polonomio:” + rc

ra = ra + “P0( X ) = ” + cxp0 + rc + ” ” + rc

ra = ra + “Polinomio derivado:” + rc

ra = ra + “P0′( X ) = ” + cxp0d + rc + ” ” + rc

ra = ra + “M.C.D.[ P0( X ) ; P0' ( X ) ) = " + cx0 + rc + " " + rc

If cx0 <> "1" Then

ra = ra + "P(X) = P0( X ) / M.C.D.[ P0( X ) ; P0'( X ) ] ” + rc

ra = ra + rc + “P(X)= ” + cx1 + rc

ra = ra + “P’(X) = ” + cxpd + rc

End If

ra = ra + rc + “Cota inferior de las raíces negativas = ” + Str$(ai) + rc

ra = ra + “Cota superior de las raíces positivas = ” + 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 las raíces reales = ” + 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 CotasRaíces(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 las raíces positivas

‘ r(2) cota inferior de la raíces negativas

‘ 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

CotasRaices = 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

Entradas relacionadas

  • Descomposicion de fracciones
  • Método de las series de Taylor para resolver ecuaciones diferenciales lineales y no lineales
  • Aproximaciones polinomiales,sucesiones y series infinitas…
  • Ortogonalidad y series de Fourier
  • El espacio vectorial y anillo de los polinomios con elementos de geometría analítica
  • Componentes fisicos de un ordenador
  • Series de Fourier y Transformada de La Place
  • Modelos Matematicos