stringtranslate.com

Relación de recurrencia

En matemáticas , una relación de recurrencia es una ecuación según la cual el término n de una secuencia de números es igual a alguna combinación de los términos anteriores. A menudo, solo aparecen en la ecuación los términos anteriores de la secuencia, para un parámetro que es independiente de ; este número se denomina 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 las recurrencias lineales , el término n- ésimo 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 en forma cerrada de . Asimismo, las recurrencias lineales con coeficientes polinómicos que dependen de también son importantes, porque muchas funciones elementales y especiales comunes tienen una serie de Taylor cuyos coeficientes satisfacen dicha relación de recurrencia (véase 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 .

Definición

Una relación de recurrencia es una ecuación que expresa cada elemento de una secuencia en función de los elementos anteriores. Más precisamente, en el caso en que solo interviene 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 cualquier , esto define una secuencia única con como su primer elemento, llamado valor inicial . [1]

Es fácil modificar la definición para obtener secuencias que comiencen desde el término de índice 1 o superior.

Esto define una 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.

Ejemplos

Factorial

El factorial se define por la relación de recurrencia

y la condición inicial

Este es un ejemplo de una recurrencia lineal con coeficientes polinomiales de orden 1, con el polinomio simple (en n )

como su único coeficiente.

Mapa logístico

Un ejemplo de una relación de recurrencia es el mapa logístico definido por

para una constante dada El comportamiento de la secuencia depende dramáticamente de la condición inicial, pero es estable cuando varía.

Números de Fibonacci

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 utilizando la recurrencia

con condiciones iniciales

Explícitamente, la recurrencia produce las ecuaciones

etc.

Obtenemos la secuencia de números de Fibonacci, que comienza

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

La recurrencia se puede resolver mediante los métodos descritos a continuación, obteniéndose la fórmula de Binet , que implica potencias de las dos raíces del polinomio característico ; la función generadora de la secuencia es la función racional.

Coeficientes binomiales

Un ejemplo sencillo de una relación de recurrencia multidimensional lo proporcionan 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 . Al utilizar esta fórmula para calcular los valores de todos los coeficientes binomiales se genera una matriz infinita llamada triángulo de Pascal . Los mismos valores también se pueden calcular directamente con una fórmula diferente que no es una recurrencia, 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 para enfatizar que debe calcularse después de la multiplicación, para no introducir números fraccionarios). Esta recurrencia es muy utilizada 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 usan todos los números enteros involucrados son menores que el resultado final).

Operador diferencial y ecuaciones diferenciales

ElEl operador 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 .

Al utilizar la notación de índice para secuencias, la definición se convierte en

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.

Dada la secuencia La 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

Aecuació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 diferencial de orden k y, a la inversa, una ecuación diferencial de orden k en una relación de recurrencia de orden k . Cada transformación es la inversa de la otra y las sucesiones que son solución de la ecuación diferencial son exactamente aquellas que satisfacen la relación de recurrencia.

Por ejemplo, la ecuación diferencial

es equivalente a la relación de recurrencia

en el sentido de que las dos ecuaciones se satisfacen por las mismas secuencias.

Como es equivalente que una sucesión satisfaga una relación de recurrencia o que sea la solución de una ecuación diferencial, los términos "relación de recurrencia" y "ecuación diferencial" a veces se usan indistintamente. Véase Ecuación diferencial racional y Ecuación diferencial matricial para ver ejemplos de usos de "ecuación diferencial" en lugar de "relación de recurrencia".

Las ecuaciones diferenciales se parecen a las ecuaciones diferenciales, y esta semejanza se utiliza a menudo para imitar métodos de resolución de ecuaciones diferenciables para aplicarlos a la resolución de ecuaciones diferenciales y, por lo tanto, relaciones de recurrencia.

Las ecuaciones de suma se relacionan con las ecuaciones diferenciales de la misma manera que las ecuaciones integrales se relacionan con las ecuaciones diferenciales. Véase cálculo de escalas temporales para una unificación de la teoría de ecuaciones diferenciales con la de ecuaciones diferenciales.

De secuencias a cuadrículas

Las relaciones de recurrencia unidimensionales o de una sola variable se refieren a secuencias (es decir, funciones definidas en cuadrículas unidimensionales). Las relaciones de recurrencia multidimensionales o n-dimensionales se refieren a cuadrículas bidimensionales. Las funciones definidas en cuadrículas bidimensionales también se pueden estudiar con ecuaciones en diferencias parciales. [2]

Resolviendo

Solución de relaciones de recurrencia lineal con coeficientes constantes

Solución de relaciones de recurrencia no homogéneas de primer orden con coeficientes variables

Además, para la relación de recurrencia lineal general 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 a 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.

Solución de relaciones de recurrencia lineal homogéneas generales

Muchas relaciones de recurrencia lineal homogéneas pueden resolverse mediante las series hipergeométricas generalizadas . Los casos especiales de éstas conducen a relaciones de recurrencia para los polinomios ortogonales y muchas funciones especiales . Por ejemplo, la solución de

viene dado por

la función de Bessel , mientras que

se resuelve mediante

Las series hipergeométricas confluentes . Las sucesiones que son las soluciones de ecuaciones diferenciales lineales con coeficientes polinómicos se denominan P-recursivas . Para estas ecuaciones de recurrencia específicas se conocen algoritmos que encuentran soluciones polinómicas , racionales o hipergeométricas .

Solución de ecuaciones diferenciales racionales de primer orden

Una ecuación diferencial racional de primer orden tiene la forma . Dicha ecuación se puede resolver escribiéndola como una transformación no lineal de otra variable que evoluciona linealmente. Luego se pueden utilizar métodos estándar para resolver la ecuación diferencial lineal en .

Estabilidad

Estabilidad de recurrencias lineales de orden superior

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 solo si los valores propios (es decir, las raíces de la ecuación característica), ya sean reales o complejos, son todos menores que la unidad en valor absoluto.

Estabilidad de recurrencias matriciales lineales de primer orden

En la ecuación diferencial de matrices de primer orden

con vector de estado y matriz de transición , converge asintóticamente al vector de estado estable si y solo si todos los valores propios de la matriz de transición (ya sea real o compleja) tienen un valor absoluto menor que 1.

Estabilidad de recurrencias no lineales de primer orden

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 . Un ciclo de este tipo es estable, lo que significa que atrae un conjunto de condiciones iniciales de medida positiva, si la función compuesta

con los 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 acotada pero nunca converge a un punto fijo o a un ciclo de atracción; todos los puntos fijos o ciclos de la ecuación son inestables. Véase también mapa logístico , transformación diádica y mapa de carpas .

Relación con ecuaciones diferenciales

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 con exactitud analítica utilizando los métodos que se muestran en el artículo sobre discretización .

Aplicaciones

Biología matemática

Algunas de las ecuaciones diferenciales 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 en su día como modelo para el crecimiento de una población de conejos.

El mapa logístico se utiliza ya sea directamente para modelar el crecimiento de la población o como punto de partida para modelos más detallados de dinámica de la población. En este contexto, las ecuaciones diferenciales 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 la representación de los huéspedes y 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 de diferencia son particularmente adecuadas para modelar poblaciones univoltinas .

Ciencias de la Computación

Las relaciones de recurrencia también son de importancia fundamental en el análisis de algoritmos . [4] [5] Si un algoritmo está diseñado para dividir un problema en subproblemas más pequeños ( dividir y vencer ), su tiempo de ejecución se describe mediante una relación de recurrencia.

Un ejemplo simple 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 verificará si el elemento está en el medio del vector. Si no, entonces verificará si el elemento del medio es mayor o menor que el elemento buscado. En este punto, se puede descartar la mitad del vector y se puede ejecutar el algoritmo nuevamente en la otra mitad. El número de comparaciones estará dado por

cuya complejidad temporal será .

Procesamiento de señales digitales

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 dado se convierten en entradas para el futuro. Por lo tanto, surgen en filtros digitales de respuesta de impulso infinita (IIR) .

Por ejemplo, la ecuación para un filtro peine IIR de retardo "feedforward" es:

donde es la entrada en el momento , es la salida en el momento , y controla qué cantidad de la señal retrasada se devuelve a la salida. De esto podemos ver que

etc.

Ciencias económicas

Las relaciones de recurrencia, especialmente las relaciones de recurrencia lineal, se utilizan ampliamente tanto en la economía teórica como en la 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 los que las acciones de algunos agentes dependen de variables rezagadas. El modelo luego se resolvería para los valores actuales de las variables clave ( tasa de interés , PIB real , etc.) en términos de los valores pasados ​​y actuales de otras variables.

Véase también

Referencias

Notas al pie

  1. ^ Jacobson, Nathan, Álgebra básica 2 (2.ª ed.), § 0.4. pág. 16.
  2. ^ Ecuaciones en diferencias parciales, Sui Sun Cheng, CRC Press, 2003, ISBN  978-0-415-29884-1
  3. ^ "Copia archivada" (PDF) . Archivado (PDF) desde el original el 5 de julio de 2010 . Consultado el 19 de octubre de 2010 .{{cite web}}: CS1 maint: archived copy as title (link)
  4. ^ Cormen, T. et al, Introducción a los algoritmos , MIT Press, 2009
  5. ^ R. Sedgewick, F. Flajolet, Introducción al análisis de algoritmos , Addison-Wesley, 2013
  6. ^ Stokey, Nancy L .; Lucas, Robert E. Jr .; Prescott, Edward C. (1989). Métodos recursivos en dinámica económica. Cambridge: Harvard University Press. ISBN 0-674-75096-9.
  7. ^ Ljungqvist, Lars ; Sargent, Thomas J. (2004). Teoría macroeconómica recursiva (segunda edición). Cambridge: MIT Press. ISBN 0-262-12274-X.

Bibliografía

Enlaces externos