sakura

Relación de recurrencia

DEFINICIÓN

una relación de recurrencia es una ecuación que define una secuencia recursiva.

Una ecuación recurrente es un tipo específico de 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 sucesión $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.

Recurrencia 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.

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}$ g

La generación de la función 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, $a n = a n - 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 $a d$ 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 $x n$ , 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 $x d p (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 $b 0 = a 0$ .

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 $a n$ 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

$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.

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 secuenci a 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 $A 1$ y $A 2$ 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}}$

$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 coeficiente 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, c o n s t a n t e$		$C 0, c o n s t a n t e$
$n$		$C 0 + C 1 n$
$n 2$		$C 0 + C 1 n + C 2 n 2$
$n^t,t\in Z^+$		$C_0+C_1n+\cdots+C_tn^t$
$r^n, r\in R$		$C 0 r n$
$n t r n$		$r n (C 0 + C 1 n + C 2 n 2)$
$sen(An),A\in R$		$C 0 s e n (A n) + C 1 c o s (A n)$
$cos(An), A\in R$		$C 0 s e n (A n) + C 1 c o s (A n)$
$r^nsen(An), A\in R$		$C 0 r n s e n (A n) + C 1 r n c o s (A n)$
$r^ncos(An), A\in R$		$C 0 r n s e n (A n) + C 1 r n c o s (A n)$

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 sumando 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 Hanói

La ecuación de recurrencia asociada con el problema de las Torres de Hanói 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 \,$

Recurrencia 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.

lunes, 13 de junio de 2011

Recurrencia Lineales

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

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.

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.

Ejemplo: Torres de Hanói

Recurrencia No lineales