Ecuación recurrente

Ecuación recurrente

Ecuación recurrente

En matemática, una relación de recurrencia es una ecuación que define una secuencia recursiva; cada término de la secuencia es definido como una función de términos anteriores.

Contenido

Definición

No debe confundirse con Ecuaciones Diferenciales.

En matemáticas, una relación de recurrencia es una ecuación que define una secuencia recursiva; cada término de la secuencia es definido en función de términos anteriores.

Una ecuación recurrente es un tipo específico de relación de recurrencia.

Una relación de recurrencia para la sucesión a_0, a_1, a_2, \cdots es una ecuación que relaciona a_n \, con alguno de sus predecesores a_0, a_1, \cdots, a_{n-1} .

Las condiciones iniciales para la sucesion a_0, a_1, \cdots son valores dados en forma explícita para un número finito de términos de la sucesión.

Resolver una relación de recurrencia consiste en determinar una fórmula explícita (cerrada) para el término general a_n\, , es decir una función no recursiva de n.

Hay dos métodos para resolver relaciones recurrentes : iteración y un método especial que se aplica a las relaciones de recurrencia lineales homogéneas con coeficientes constantes.

Un ejemplo de una relación de recurrencia es el siguiente:

x_{n+1} = rx_n(1-x_n) \,

Algunas definiciones de recurrencia pueden tener relaciones muy complejas(caóticas) y sus comportamientos, a veces son estudiados por los físicos y matemáticos en un campo de las matemáticas conocido como análisis no lineal.

Resolución

Iteración

Para resolver una relación de recurrencia asociada a la sucesión: a_0, a_1, a_2 \, por iteración, utilizamos la relación de recurrencia para escribir el n-ésimo término a_n \, en términos de algunos de sus predecesores. Luego utilizamos de manera sucesiva la relación de recurrencia para reemplazar cada uno de los términos por algunos de sus predecesores. Continuamos hasta llegar a alguno de los casos base.

Recurrencias Lineales

Una relación de recurrencia es lineal de grado k si tiene la siguiente estructura:

c_0(n)a_n + c_1(n) a_{n-1} + \dots + c_{k-1}(n) a_{n-k+1} + c_k(n) a_{n-k} \,

siendo c_i(n) \, funciones reales de n \, , y F(n) \, una función de n.

El adjetivo lineal indica que cada término de la secuencia está definido como una función lineal de sus términos anteriores. El orden de una relación de recurrencia lineal es el número de términos anteriores exigidos por la definición.

En la relación a_n = a_{n-2} \, el orden es dos, porque debe haber al menos dos términos anteriores (ya sean usados o no).

Ejemplos :

3 a_n - {n-1} a_{n-1} + 2 a_{n-2} = 0 \,

Ecuación de Recurrencia lineal homogénea con coeficientes constantes

Se llama ecuación de recurrencia lineal homogénea de grado k, con coeficientes constantes, a una expresión del tipo:

c_0 a_n + c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k} = 0 , c_i \in R , c_k \ne 0

Para poder encontrar una solución, hacen falta unas condiciones de contorno o iniciales a_0 , a_1 , \cdots , a_{k-1} , siendo k el grado de la ecuación.

La recurrencia lineal, junto con las condiciones iniciales a_0 , \cdots , a_{k-1} , determinan la secuencia única.

Sea la ecuación de recurrencia lineal homogénea de orden k anterior, se denomina ecuación característica a la ecuación de grado k:

x^k + c_{n-1} x^{k-1} + \cdots + c_{n-k}
La generación de la funcion racional

Las secuencias lineales recursiva son precisamente las secuencias cuya función de generación es una función racional: el denominador es el polinomio auxiliar (a una transformación), y el numerador se obtiene con los valores iniciales.

El caso más sencillo son las secuencias periódicas,an = an − d, n≥d que tienen secuencia a_0, a_1, \cdots, a_{d-1}, a_0, \cdots y función de generación una suma de una serie geométrica:

\begin{array}{ll} \cfrac{a_0 + a_1 x^1 + \dots + a_{d-1} x^{d-1}}{1 - x^d} = & ( a_0 + a_1 x^1 + \dots + a_{d-1} x^{d-1}) + \\ & ( a_0 + a_1 x^1 + \dots + a_{d-1} x^{d-1}) x^d + \\ & ( a_0 + a_1 x^1 + \dots + a_{d-1} x^{d-1}) x^{2d} + \\ & \dots \end{array}

Más general, dada la relación de recurrencia:

a_n = c_1a_{n-1} + c_2a_{n-2} + ... + c_d a_{n-d} \,

con función de generación

a_0 + a_1x^1 + a_2x^2 + \cdots

la serie es aniquilada por ad y anteriormente por el polinomio:

1 - c_1x^1 - c_2x^2 - \cdots - c_d x^d

Eso es, multiplicando la función de generación por el polinomio

b_n = a_n - c_1 a_{n-1} - c_2 a_{n-2} - \cdots - c_d a_{n-d}

como el coeficiente en xn, que desaparece (por la relación de recurrencia) para n ≥ d. Así:

( a_0 + a_1 x^1 + a_2 x^2 + \dots ) ( 1 - c_1 x^1 - c_2 x^2 - \dots - c_d x^d) = ( b_0 + b_1 x^1 + b_2 x^2 + \dots + b_{d-1} x^{d-1})

como dividiendo:

a_0 + a_1 x^1 + a_2 x^2 + \dots = \cfrac {b_0 + b_1 x^1 + b_2 x^2 + \dots + b_{d-1} x^{d-1}} {1 - c_1 x^1 - c_2 x^2 - \dots - c_d x^d}

expresando la función de generación como una función racional. El denominador es xdp(1 / x), una transformación del polinomio auxiliar (equivalente, invirtiendo el orden de los coeficientes); también se puede usar cualquier múltiplo de esta, pero esta normalización es elegida por ambas porque la relación simple del polinomio auxiliar, y de ese modo b0 = a0.

Relación con la diferencia de ecuaciones

Dada una secuencia \{ a_n \} \, de números reales: la primera diferencia d ( a_n ) \, se define como a_n - a_{n-1} \,

La segunda diferencia d^2 ( a_n ) \, se define como d (a_n) - d(a_{n-1}) \, ,

que se puede simplificar a a_n - 2a_{n-1} + a_{n-2} \, .

Más general: la diferencia d^k \, se define como d^{k-1}(a_n) - d^{k-1}(a_{n-1}) \,

A diferencia de la ecuación es una ecuación compuesta por an y sus diferencias. Cada relación de recurrencia puede ser formulada como una ecuación de diferencia. Por el contrario, cada ecuación de diferencia puede ser formulada como una relación de recurrencia. Algunos autores así utilizan los dos términos intercambiables. Por ejemplo, la ecuación de la diferencia:

3 d^2 (a_n) + 2d (a_n) + 7a_n = 0 \,

es equivalente a la relación de recurrencia:

12 a_n = 8 a_{n-1} - 3 a_{n-2} \,

De este modo se puede resolver relaciones de recurrencia por la reiteración como ecuaciones diferencia, y luego la solución de la ecuación de diferencia, análogamente como una solución de ecuaciones diferenciales ordinarias.

Ver escala de tiempo de cálculo para la unificación de la teoría de las ecuaciones de diferencia con la de las ecuaciones diferenciales.

Resolución

Sean

c_0 a_n + c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_ka_{n-k} =0

una ecuación de recurrencia lineal homogénea, x^k + c_{n-1}x^{k-1} + \cdots + c_{n-k} su ecuación característica y, x_1, x_2, \cdots, x_s las raíces de la ecuación característica con multiplicidades m_1,m_2,\cdots,m_s respectivamente. La solución de esta ecuación sería:

a_n = P_1(n)(x_1)^n+P_2(n)(x_2)^n + \cdots + P_s(n)(x_s)^n


Con P_i(n)\ el polinomio de grado menor o igual que m_{i}-1\, . Para poder calcular los coeficientes de los polinomios P_i(n)\, , necesitamos saber las condiciones iniciales de la ecuación de recurrencia.

Ejemplo : Números de Fibonacci

Los números de Fibonacci están definidos usando la siguiente relación de recurrencia lineal:

F_{n} = F_{n-1}+F_{n-2} \,

con los valores iniciales:

F_1 = 1 \,
F_2 = 1 \,

La secuencia de los números de Fibonacci comienza: 1, 1, 2, 3 ,5, 8, 13, 21 ,34, 55, 89... El objetivo de la resolución de la ecuación de recurrencia es encontrar una forma cerrada para calcular los números de Fibonacci.

La ecuación característica es la siguiente:

x^2 - x - 1 = 0 \,
x_1 = \frac{1 + \sqrt{5}}{2} \,
x_2 = \frac{1 - \sqrt{5}}{2} \,

por lo tanto, la solución general es:

F(n) = A_1 \left( \frac {1+\sqrt{5}} {2} \right)^n + A_2 \left( \frac {1-\sqrt{5}} {2} \right)^n

Para hallar el valor de A1 y A2 resolvemos las siguientes ecuaciones:

F_1 = A_1 \left ( \frac {1+\sqrt{5}} {2} \right ) + A_2 \left ( \frac {1-\sqrt{5}} {2} \right )
F_2 = A_1 \left ( \frac {1+\sqrt{5}} {2} \right )^2 + A_2 \left ( \frac {1-\sqrt{5}} {2} \right )^2

Entonces:

A_1 = \frac {1} {\sqrt{5}}

y

A_2 = \frac{-1}{\sqrt{5}}

La forma cerrada para los números de Fibonacci es:

F(n) = \frac{1}{\sqrt{5}} \left( \left( \frac{1+\sqrt{5}}{2} \right)^n - \left( \frac{1-\sqrt{5}}{2} \right)^n \right)

Ecuación de Recurrencia lineal NO homogénea con coeficientes constantes

Recibe el nombre de ecuación de recurrencia lineal no homogénea de grado k, con coeficientes constantes, una expresión del tipo: c_0a_n + c_1a_{n-1} + c_2a_{n-2} +\cdots+ c_ka_{n-k} =F(n) , c_i\in R , c_k \ne 0.

Resolución

La solución general sería: a_n=a_n^{(h)} + a_n^{(p)} , donde a_n^{(h)} es la solución de la ecuación de recurrencia lineal homogénea asociada es decir la ecuación : c_0a_n + c_1a_{n-1} + c_2a_{n-2} +\cdots+ c_ka_{n-k} =0 , c_i\in R , c_k \ne 0 y donde a_n^{(p)} es la solución particular que depende de la función F(n). Por lo tanto los pasos a seguir serían, primero calcular la solución de la ecuación homogénea, calcular una solución particular para F(n) y sumarla a la homogénea, y a continuación aplicar las condiciones iniciales para calcular las constantes. En la siguiente tabla, encontramos cuales son las posibles soluciones particulares:

F(n) {a_n}^{(p)}
C,constante C0,constante
n C0 + C1n
n2 C0 + C1n + C2n2
n^t,t\in Z^+ C_0+C_1n+\cdots+C_tn^t
r^n, r\in R C0rn
ntrn rn(C0 + C1n + C2n2)
sen(An),A\in R C0sen(An) + C1cos(An)
cos(An), A\in R C0sen(An) + C1cos(An)
r^nsen(An), A\in R C0rnsen(An) + C1rncos(An)
r^ncos(An), A\in R C0rnsen(An) + C1rncos(An)
      • Consideraciones:

1. Si F(n) es una combinación lineal de algunas de las funciones de la tabla anterior, su solución particular es la combinación lineal de las soluciones particulares de esas mismas funciones.

2.Si uno de los sumandos de F(n) es el producto de una constante por una solución de la ecuación característica homogénea asociada, entonces es necesario multiplicar la solución particular correspondiente a este sumando por la menor potencia de n, n´ tal que este nuevo producto no sea solución de la ecuación característica homogénea asociada.

Ejemplo: Torres de Hanoi

La ecuación de recurrencia asociada con el problema de las Torres de Hanoi es la siguiente:

T_{n} =2 T_{n-1}+1 \,

Con las condiciones iniciales:

T_1=1 \,

Se resuelve la siguiente homogénea:

T_n^{(h)}=2T_{n-1}

La ecuación característica es: x − 2 = 0, entonces x = 2

Entonces : T_n^{(h)}= A2^n

A continuación, se resuelve la ecuación particular: T_n^{(p)} =B=2B+1, entonces B = − 1.

T_n = A2^n-1 \, , entonces igualando con las condiciones iniciales la solución es : T_n = 2^n-1 \,

Recurrencias No lineales

Para resolver recurrencias no lineales tenemos muchas opciones de las cuales:

  • Buscar transformaciones o cambios de variables que hagan la recurrencia lineal.
  • Para el caso t(n) = a \cdot t \left ( \frac{n}{b} \right ) + f(n) , hay un teorema muy útil que es el Teorema Maestro.

La recurrencia en la computación

La conexión con el análisis de algoritmos estriba en que la forma que se ha adoptado para medir las complejidades, utiliza funciones cuyo dominio son los números naturales, o en otras palabras, sucesiones. Si el algoritmo es recurrente, es de esperarse que las complejidades, como funciones que estiman la demanda de recursos a lo largo de la ejecución, sean sucesiones que satisfacen ciertas ecuaciones de recurrencia. En un algoritmo recursivo, la función t(n) que establece su complejidad viene dada por una ecuación de recurrencia. Una ecuación de recurrencia nos permiten indicar el tiempo de ejecución para los distintos casos del algoritmo recursivo (casos base y recursivo).

Ejemplo : Cálculo del factorial

int Fact(int n){
        if(n<=1){
            return 1;
        else{
            return (n*Fact(n-1));
        }
}

Considerando el producto como operacion basica, podemos construir la ecuacion recurrente para calcular la complejidad del algoritmo como sigue:

Como se ve en el codigo el caso base es para n<=1, para estos valores de n el numero de multiplicaciones que se realiza es 0. Y en otro caso es 1 mas las necesarias para calcular el factorial de n-1. Asi construimos la funcion recurrente:

t(n) = \begin{cases} 0 & \mbox{si } n \le 1 \\ t(n-1) + 1 & \mbox{si } n > 1 \end{cases}

Ahora si resolvemos la ecuación recurrente sabremos la complejidad de este algoritmo en funcion de n. Procedemos a resolver esta ecuación recurrente no lineal:

t(n) = t(n-1) - 1 \,

resolvemos la homogenea:

t(n) = t(n-1) \longrightarrow \quad r - 1 = 0 \longrightarrow \quad r = 1 a_n^h = c 1^n \longrightarrow \quad a_n^h = c

resolvamos ahora la particular:

como la particular' coincide con la r, debemos aumentar el grado multiplicando por n

\longrightarrow a_n^p = n 1^n \longrightarrow \quad a_n^p = n

por lo que la solucion de la ecuacion recurrente queda como sigue:

t(n) = c + n \,

Ahora calculamos c utilizando el caso base, t(1) = 0

t(1) = c + 1 = 0 \longrightarrow \quad c = -1

ya tenemos la solucion: t(n) = n - 1

La ecuacion que nos ha quedado es de grado 1 por lo que la complejidad es del orden exacto de n -> θ(n)

Por ejemplo para calcular el factorial de 3 necesitaremos t(3) productos lo que es igual a

3 - 1 = 2 \longrightarrow \quad 3 \cdot (2 \cdot (1))

Como vemos son 2 productos como nos ha devuelto la ecuación.

Aplicaciones

Entre otras:

  • En la óptica
  • En la teoría de la probabilidad
  • En el estudio de los árboles binarios, pilas y algoritmos de ordenación

Véase también

Obtenido de "Ecuaci%C3%B3n recurrente"

Wikimedia foundation. 2010.

Игры ⚽ Нужен реферат?

Mira otros diccionarios:

  • Miembro de una ecuación — En matemáticas, LHS es la manera informal de llamar el lado izquierdo (left hand side) de una ecuación. Similarmente, RHS es el lado derecho (right hand side) de una ecuación. Cada una es solamente un nombre que se le da a una parte de una… …   Wikipedia Español

  • Número áureo — Para el número de astronomía, ver Número áureo (astronomía) El número áureo o de oro (también llamado número plateado, razón extrema y media,[1] razón áurea, razón dorada, media áurea, proporción áurea y divina proporción) representado por la… …   Wikipedia Español

  • Filtro comb — Saltar a navegación, búsqueda Diagrama y análisis espectral de un filtro comb (IIR+FIR) aplicado a ruido blanco. En el procesamiento de señales, un filtro comb (o peine) se produce al sumarle a la señal original una versión retrasada en el tiempo …   Wikipedia Español

  • Teorema maestro — El Teorema maestro es un método matemático que se usa para resolver ciertos casos particulares de ecuaciones de recurrencia como la siguiente: . Consideremos una función t(n) que no sea decreciente: con constantes a ≥ 1 y b ≥ 2. Obtenemos …   Wikipedia Español

  • Anexo:Episodios de Numb3rs — La siguiente es una lista de episodios de la serie norteamericana NUMB3RS. Contenido 1 Estrenos y Lanzamientos en DVD 2 Primera temporada (2005) 3 Segunda temporada (2005 2006) …   Wikipedia Español

  • Algoritmo de Euclides — El algoritmo de Euclides es un método antiguo y eficaz para calcular el máximo común divisor (MCD). Fue originalmente descrito por Euclides en su obra Elementos. El algoritmo de Euclides extendido es una ligera modificación que permite además… …   Wikipedia Español

  • Sucesión de Fibonacci — Gráfica de la sucesión de Fibonacci hasta f10 En matemática, la sucesión de Fibonacci es la siguiente sucesión infinita de números naturales: La sucesión inicia con …   Wikipedia Español

  • Recursión — Saltar a navegación, búsqueda Anuncio de cacao con una imagen recursiva. La mujer muestra un paquete idéntico al del propio anuncio, conteniendo así a otra mujer que muestra otro paquete más pequeño, de forma recursiva …   Wikipedia Español

  • Exponenciación binaria — Saltar a navegación, búsqueda La exponenciación binaria es un algoritmo utilizado para calcular de forma rápida grandes potencias enteras de un número x dado. También es conocido como potenciación por cuadrados o elevar al cuadrado y multiplicar …   Wikipedia Español

  • Número plateado — El número plateado o razón plateada es una constante matemática. Su nombre es una alusión a la razón áurea; análoga a la forma en que el número áureo es la proporción limitante de la sucesión de Fibonacci, el número plateado es la proporción… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”