En matemáticas , una relación de recurrencia es una ecuación según la cual el décimo término de una secuencia de números es igual a alguna combinación de los términos anteriores. A menudo, en la ecuación sólo aparecen términos anteriores de la secuencia, para un parámetro que es independiente de ; este número se llama orden de la relación. Si se han dado los valores de los primeros números de la secuencia, el resto de la secuencia se puede calcular aplicando repetidamente la ecuación.
En recurrencias lineales , el n- ésimo término se equipara a una función lineal de los términos anteriores. Un ejemplo famoso es la recurrencia de los números de Fibonacci , donde el orden es dos y la función lineal simplemente suma los dos términos anteriores. Este ejemplo es una recurrencia lineal con coeficientes constantes , porque los coeficientes de la función lineal (1 y 1) son constantes que no dependen de. Para estas recurrencias, se puede expresar el término general de la secuencia como una expresión de forma cerrada de . Además, las recurrencias lineales con coeficientes polinomiales dependientes también son importantes, porque muchas funciones elementales y especiales comunes tienen una serie de Taylor cuyos coeficientes satisfacen dicha relación de recurrencia (ver función holonómica ).
Resolver una relación de recurrencia significa obtener una solución de forma cerrada : una función no recursiva de .
El concepto de relación de recurrencia se puede extender a matrices multidimensionales , es decir, familias indexadas que están indexadas por tuplas de números naturales .
Una relación de recurrencia es una ecuación que expresa cada elemento de una secuencia en función de los anteriores. Más precisamente, en el caso en el que sólo está involucrado el elemento inmediatamente anterior, una relación de recurrencia tiene la forma
dónde
es una función, donde X es un conjunto al que deben pertenecer los elementos de una secuencia. Para cualquiera , esto define una secuencia única que tiene como primer elemento, llamado valor inicial . [1]
Es fácil modificar la definición para obtener secuencias a partir del término de índice 1 o superior.
Esto define la relación de recurrencia de primer orden . Una relación de recurrencia de orden k tiene la forma
donde es una función que involucra k elementos consecutivos de la secuencia. En este caso, se necesitan k valores iniciales para definir una secuencia.
El factorial está definido por la relación de recurrencia.
y la condición inicial
Este es un ejemplo de recurrencia lineal con coeficientes polinomiales de orden 1, con el polinomio simple
como su único coeficiente.
Un ejemplo de relación de recurrencia es el mapa logístico :
con una constante dada ; dado el término inicial , cada término subsiguiente está determinado por esta relación.
La recurrencia de orden dos satisfecha por los números de Fibonacci es el ejemplo canónico de una relación de recurrencia lineal homogénea con coeficientes constantes (ver más abajo). La secuencia de Fibonacci se define mediante la recurrencia
Explícitamente, la recurrencia produce las ecuaciones
etc.
Obtenemos la secuencia de números de Fibonacci, que comienza
La recurrencia se puede resolver mediante los métodos que se describen a continuación, lo que da como resultado la fórmula de Binet , que involucra potencias de las dos raíces del polinomio característico ; la función generadora de la secuencia es la función racional
Un ejemplo simple de una relación de recurrencia multidimensional lo dan los coeficientes binomiales , que cuentan las formas de seleccionar elementos de un conjunto de elementos. Se pueden calcular mediante la relación de recurrencia.
con los casos base . El uso de esta fórmula para calcular los valores de todos los coeficientes binomiales genera una matriz infinita llamada triángulo de Pascal . Los mismos valores también se pueden calcular directamente mediante una fórmula diferente que no es recurrente, sino que utiliza factoriales , multiplicación y división, no solo sumas:
Los coeficientes binomiales también se pueden calcular con una recurrencia unidimensional:
con el valor inicial (La división no se muestra como fracción por enfatizar que debe calcularse después de la multiplicación, por no introducir números fraccionarios). Esta recurrencia se usa ampliamente en computadoras porque no requiere construir una tabla como lo hace la recurrencia bidimensional, y sí involucra números enteros muy grandes como lo hace la fórmula con factoriales (si se usa, todos los números enteros involucrados son más pequeños que el resultado final). .
Eloperador de diferencia es unoperadorque asignasecuenciasa secuencias y, de manera más general,funcionesa funciones. Se denota comúnmentey se define, ennotación funcional, como
Se trata, pues, de un caso especial de diferencia finita .
Cuando se utiliza la notación de índice para secuencias, la definición se vuelve
Los paréntesis alrededor de y generalmente se omiten y deben entenderse como el término del índice n en la secuencia y no aplicarse al elemento.
secuencia dada lala primera diferencia deaes
ElLa segunda diferencia es que un cálculo simple muestra que
De manera más general: la k -ésima diferencia se define recursivamente como y se tiene
Esta relación se puede invertir, dando
AUna ecuación diferencial de ordenkes una ecuación que involucra laskprimeras diferencias de una secuencia o una función, de la misma manera que unaecuación diferencialde ordenkrelaciona laskprimerasderivadasde una función.
Las dos relaciones anteriores permiten transformar una relación de recurrencia de orden k en una ecuación en diferencias de orden k y, a la inversa, una ecuación en diferencias de orden k en una relación de recurrencia de orden k . Cada transformación es inversa de la otra, y las sucesiones que son solución de la ecuación en diferencias son exactamente aquellas que satisfacen la relación de recurrencia.
Por ejemplo, la ecuación en diferencias
es equivalente a la relación de recurrencia
en el sentido de que las dos ecuaciones son satisfechas por las mismas secuencias.
Como es equivalente que una secuencia satisfaga una relación de recurrencia o sea la solución de una ecuación en diferencias, los dos términos "relación de recurrencia" y "ecuación en diferencias" a veces se usan indistintamente. Consulte Ecuación en diferencias racional y Ecuación en diferencias matricial para ver ejemplos de usos de "ecuación en diferencias" en lugar de "relación de recurrencia".
Las ecuaciones en diferencias se parecen a las ecuaciones diferenciales, y esta semejanza se usa a menudo para imitar métodos para resolver ecuaciones diferenciables y aplicarlos a la resolución de ecuaciones en diferencias y, por lo tanto, relaciones de recurrencia.
Las ecuaciones sumatorias se relacionan con las ecuaciones en diferencias como las ecuaciones integrales se relacionan con las ecuaciones diferenciales. Consulte cálculo de escala de tiempo para conocer una unificación de la teoría de ecuaciones en diferencias con la de ecuaciones diferenciales.
Las relaciones de recurrencia de una sola variable o unidimensionales se refieren a secuencias (es decir, funciones definidas en cuadrículas unidimensionales). Las relaciones de recurrencia multivariable o n-dimensionales se refieren a cuadrículas de dimensiones. Las funciones definidas en cuadrículas también se pueden estudiar con ecuaciones en diferencias parciales . [2]
Además, para la relación general de recurrencia lineal no homogénea de primer orden con coeficientes variables:
También hay un buen método para resolverlo: [3]
Dejar
Entonces
Si aplicamos la fórmula y tomamos el límite , obtenemos la fórmula para ecuaciones diferenciales lineales de primer orden con coeficientes variables; la suma se convierte en una integral y el producto se convierte en la función exponencial de una integral.
Muchas relaciones de recurrencia lineal homogénea pueden resolverse mediante series hipergeométricas generalizadas . Los casos especiales de estos conducen a relaciones de recurrencia para los polinomios ortogonales y muchas funciones especiales . Por ejemplo, la solución a
está dado por
la función de Bessel , mientras
se resuelve por
la serie hipergeométrica confluente . Las secuencias que son soluciones de ecuaciones en diferencias lineales con coeficientes polinomiales se denominan P-recursivas . Para estas ecuaciones de recurrencia específicas se conocen algoritmos que encuentran soluciones polinómicas , racionales o hipergeométricas .
Una ecuación en diferencias racionales de primer orden tiene la forma . Una ecuación de este tipo puede resolverse escribiéndola como una transformación no lineal de otra variable que a su vez evoluciona linealmente. Luego se pueden utilizar métodos estándar para resolver la ecuación en diferencias lineales en .
La recurrencia lineal del orden ,
tiene la ecuación característica
La recurrencia es estable , lo que significa que las iteraciones convergen asintóticamente a un valor fijo, si y sólo si los valores propios (es decir, las raíces de la ecuación característica), ya sean reales o complejas, son todos menores que la unidad en valor absoluto.
En la ecuación en diferencias matricial de primer orden
con vector de estado y matriz de transición , converge asintóticamente al vector de estado estacionario si y solo si todos los valores propios de la matriz de transición (ya sean reales o complejos) tienen un valor absoluto menor que 1.
Considere la recurrencia no lineal de primer orden.
Esta recurrencia es localmente estable , lo que significa que converge a un punto fijo desde puntos suficientemente cercanos a , si la pendiente de en la vecindad de es menor que la unidad en valor absoluto: es decir,
Una recurrencia no lineal podría tener múltiples puntos fijos, en cuyo caso algunos puntos fijos pueden ser localmente estables y otros localmente inestables; para f continua , dos puntos fijos adyacentes no pueden ser ambos localmente estables.
Una relación de recurrencia no lineal también podría tener un ciclo de período para . Tal ciclo es estable, lo que significa que atrae un conjunto de condiciones iniciales de medida positiva, si la función compuesta
con tiempos de aparición es localmente estable según el mismo criterio:
¿Dónde está cualquier punto del ciclo?
En una relación de recurrencia caótica , la variable permanece en una región limitada pero nunca converge a un punto fijo o un ciclo de atracción; cualquier punto fijo o ciclo de la ecuación es inestable. Véase también mapa logístico , transformación diádica y mapa de tiendas .
Al resolver numéricamente una ecuación diferencial ordinaria , normalmente se encuentra una relación de recurrencia. Por ejemplo, al resolver el problema del valor inicial
con el método de Euler y un tamaño de paso , se calculan los valores
por la recurrencia
Los sistemas de ecuaciones diferenciales lineales de primer orden se pueden discretizar exactamente analíticamente utilizando los métodos que se muestran en el artículo sobre discretización .
Algunas de las ecuaciones en diferencias más conocidas tienen su origen en el intento de modelar la dinámica de poblaciones . Por ejemplo, los números de Fibonacci se utilizaron alguna vez como modelo para el crecimiento de una población de conejos.
El mapa logístico se utiliza directamente para modelar el crecimiento de la población o como punto de partida para modelos más detallados de la dinámica de la población. En este contexto, las ecuaciones en diferencias acopladas se utilizan a menudo para modelar la interacción de dos o más poblaciones . Por ejemplo, el modelo de Nicholson-Bailey para una interacción huésped- parásito viene dado por
con representar a los huéspedes y a los parásitos en el momento .
Las ecuaciones de integrodiferencia son una forma de relación de recurrencia importante para la ecología espacial . Estas y otras ecuaciones en diferencias son particularmente adecuadas para modelar poblaciones univoltinas .
Las relaciones de recurrencia también son de fundamental importancia en el análisis de algoritmos . [4] [5] Si un algoritmo está diseñado para dividir un problema en subproblemas más pequeños ( divide y vencerás ), su tiempo de ejecución se describe mediante una relación de recurrencia.
Un ejemplo sencillo es el tiempo que tarda un algoritmo en encontrar un elemento en un vector ordenado con elementos, en el peor de los casos.
Un algoritmo ingenuo buscará de izquierda a derecha, un elemento a la vez. El peor escenario posible es cuando el elemento requerido es el último, por lo que el número de comparaciones es .
Un algoritmo mejor se llama búsqueda binaria . Sin embargo, requiere un vector ordenado. Primero comprobará si el elemento está en el medio del vector. De lo contrario, comprobará si el elemento del medio es mayor o menor que el elemento buscado. En este punto, se puede descartar la mitad del vector y el algoritmo se puede ejecutar nuevamente en la otra mitad. El número de comparaciones estará dado por
cuya complejidad temporal será .
En el procesamiento de señales digitales , las relaciones de recurrencia pueden modelar la retroalimentación en un sistema, donde las salidas en un momento se convierten en entradas para el futuro. Surgen así en los filtros digitales de respuesta al impulso infinito (IIR) .
Por ejemplo, la ecuación para un filtro de retardo tipo peine IIR "feedforward" es:
donde está la entrada en el tiempo , es la salida en el tiempo y controla la cantidad de señal retardada que se devuelve a la salida. De esto podemos ver que
etc.
Las relaciones de recurrencia, especialmente las relaciones de recurrencia lineal, se utilizan ampliamente en economía tanto teórica como empírica. [6] [7] En particular, en macroeconomía se podría desarrollar un modelo de varios sectores amplios de la economía (el sector financiero, el sector de bienes, el mercado laboral, etc.) en el que las acciones de algunos agentes dependan de variables rezagadas. Luego, el modelo se resolvería para los valores actuales de variables clave ( tasa de interés , PIB real , etc.) en términos de valores pasados y actuales de otras variables.
{{cite web}}
: CS1 maint: archived copy as title (link)