Relación de recurrencia

El factorial se define mediante la relación de recurrencia.

${\displaystyle n!=n\cdot (n-1)!\quad {\text{para}}\quad n>0,}$

y la condición inicial

${\displaystyle 0!=1.}$

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

${\displaystyle n}$

como su único coeficiente.

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

${\displaystyle x_{n+1}=rx_{n}(1-x_{n}),}$

para una constante dada${\displaystyle r.}$El comportamiento de la secuencia depende drásticamente de${\displaystyle r,}$pero es estable cuando la condición inicial${\displaystyle x_{0}}$varía.

La recurrencia de orden dos que satisfacen los números de Fibonacci es el ejemplo canónico de una relación de recurrencia lineal homogénea con coeficientes constantes (véase más abajo). La sucesión de Fibonacci se define utilizando la recurrencia

${\displaystyle F_{n}=F_{n-1}+F_{n-2}}$

con condiciones iniciales

${\displaystyle F_{0}=0}$

${\displaystyle F_{1}=1.}$

Explícitamente, la recurrencia produce las ecuaciones

${\displaystyle F_{2}=F_{1}+F_{0}}$

${\displaystyle F_{3}=F_{2}+F_{1}}$

${\displaystyle F_{4}=F_{3}+F_{2}}$

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, obteniendo la fórmula de Binet , que involucra potencias de las dos raíces del polinomio característico.${\displaystyle t^{2}=t+1}$; la función generadora de la secuencia es la función racional

${\displaystyle {\frac {t}{1-tt^{2}}}.}$

Un ejemplo sencillo de una relación de recurrencia multidimensional lo proporcionan los coeficientes binomiales.${\displaystyle {\tbinom {n}{k}}}$, que cuentan las formas de seleccionar${\displaystyle k}$elementos de un conjunto de${\displaystyle n}$elementos. Se pueden calcular mediante la relación de recurrencia.

${\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}},}$

con los casos base${\displaystyle {\tbinom {n}{0}}={\tbinom {n}{n}}=1}$Al usar 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 mediante una fórmula diferente que no es una recurrencia, pero que utiliza factoriales , multiplicación y división, no solo sumas:

${\displaystyle {\binom {n}{k}}={\frac {n!}{k!(n-k)!}}.}$

Los coeficientes binomiales también se pueden calcular con una recurrencia unidimensional:

${\displaystyle {\binom {n}{k}}={\binom {n}{k-1}}(n-k+1)/k,}$

con el valor inicial${\textstyle {\binom {n}{0}}=1}$(La división no se muestra como una fracción para enfatizar que debe calcularse después de la multiplicación, para no introducir números fraccionarios). Esta recurrencia se usa ampliamente en computadoras porque no requiere construir una tabla como la recurrencia bidimensional, y no involucra enteros muy grandes como la fórmula con factoriales (si se usa${\textstyle {\binom {n}{k}}={\binom {n}{n-k}},}$Todos los números enteros involucrados son menores que el resultado final.

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 de múltiples variables o n-dimensionales se refieren a${\displaystyle n}$cuadrículas -dimensionales. Funciones definidas en${\displaystyle n}$-Las mallas también pueden estudiarse con ecuaciones de diferencias parciales. ^{[ 5 ]}

Además, para la relación de recurrencia lineal no homogénea de primer orden general con coeficientes variables:

${\displaystyle a_{n+1}=f_{n}a_{n}+g_{n},\qquad f_{n}\neq 0,}$

También hay un buen método para resolverlo: ^{[ 6 ]}

${\displaystyle a_{n+1}-f_{n}a_{n}=g_{n}}$

${\displaystyle {\frac {a_{n+1}}{\prod _{k=0}^{n}f_{k}}}-{\frac {f_{n}a_{n}}{\prod _{k=0}^{n}f_{k}}}={\frac {g_{n}}{\prod _{k=0}^{n}f_{k}}}}$

${\displaystyle {\frac {a_{n+1}}{\prod _{k=0}^{n}f_{k}}}-{\frac {a_{n}}{\prod _{k=0}^{n-1}f_{k}}}={\frac {g_{n}}{\prod _{k=0}^{n}f_{k}}}}$

Dejar

${\displaystyle A_{n}={\frac {a_{n}}{\prod _{k=0}^{n-1}f_{k}}},}$

Entonces

${\displaystyle A_{n+1}-A_{n}={\frac {g_{n}}{\prod _{k=0}^{n}f_{k}}}}$

${\displaystyle \sum _{m=0}^{n-1}(A_{m+1}-A_{m})=A_{n}-A_{0}=\sum _{m=0}^{n-1}{\frac {g_{m}}{\prod _{k=0}^{m}f_{k}}}}$

${\displaystyle {\frac {a_{n}}{\prod _{k=0}^{n-1}f_{k}}}=A_{0}+\sum _{m=0}^{n-1}{\frac {g_{m}}{\prod _{k=0}^{m}f_{k}}}}$

${\displaystyle a_{n}=\left(\prod _{k=0}^{n-1}f_{k}\right)\left(A_{0}+\sum _{m=0}^{n-1}{\frac {g_{m}}{\prod _{k=0}^{m}f_{k}}}\right)}$

Si aplicamos la fórmula a${\displaystyle a_{n+1}=(1+hf_{nh})a_{n}+hg_{nh}}$y tomar el límite${\displaystyle h\to 0}$, 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 lineales homogéneas pueden resolverse mediante la serie hipergeométrica generalizada . Casos especiales de estas conducen a relaciones de recurrencia para los polinomios ortogonales y muchas funciones especiales . Por ejemplo, la solución a

${\displaystyle J_{n+1}={\frac {2n}{z}}J_{n}-J_{n-1}}$

es dado por

${\displaystyle J_{n}=J_{n}(z),}$

la función de Bessel , mientras que

${\displaystyle (b-n)M_{n-1}+(2n-b+z)M_{n}-nM_{n+1}=0}$

se resuelve mediante

${\displaystyle M_{n}=M(n,b;z)}$

Las series hipergeométricas confluentes . Las secuencias que son soluciones de ecuaciones lineales en diferencias 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 .

Además, para la relación de recurrencia lineal no homogénea general con coeficientes constantes, se puede resolver basándose en la variación de parámetros. ^{[ 7 ]}

Una ecuación de diferencias racionales de primer orden tiene la forma${\displaystyle w_{t+1}={\tfrac {aw_{t}+b}{cw_{t}+d}}}$. Dicha ecuación se puede resolver escribiendo${\displaystyle w_{t}}$como una transformación no lineal de otra variable${\displaystyle x_{t}}$que a su vez evoluciona linealmente. Entonces se pueden utilizar métodos estándar para resolver la ecuación de diferencias lineal en${\displaystyle x_{t}}$.

La recurrencia lineal de orden${\displaystyle d}$,

${\displaystyle a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots +c_{d}a_{n-d},}$

tiene la ecuación característica

${\displaystyle \lambda ^{d}-c_{1}\lambda ^{d-1}-c_{2}\lambda ^{d-2}-\cdots -c_{d}\lambda ^{0}=0.}$

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.

En la ecuación de diferencias matriciales de primer orden

${\displaystyle [x_{t}-x^{*}]=A[x_{t-1}-x^{*}]}$

con vector de estado${\displaystyle x}$y matriz de transición${\displaystyle A}$,${\displaystyle x}$converge asintóticamente al vector de estado estacionario${\displaystyle x^{*}}$si y solo si todos los valores propios de la matriz de transición${\displaystyle A}$(ya sean reales o complejos) tienen un valor absoluto menor que  1.

Consideremos la recurrencia no lineal de primer orden.

${\displaystyle x_{n}=f(x_{n-1}).}$

Esta recurrencia es localmente estable , lo que significa que converge a un punto fijo.${\displaystyle x^{*}}$desde puntos suficientemente cercanos a${\displaystyle x^{*}}$, si la pendiente de${\displaystyle f}$ en el vecindario de${\displaystyle x^{*}}$es menor que la unidad en valor absoluto: es decir,

${\displaystyle |f'(x^{*})|<1.}$

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 una función 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${\displaystyle k}$para${\displaystyle k>1}$. Dicho ciclo es estable, lo que significa que atrae un conjunto de condiciones iniciales de medida positiva, si la función compuesta

${\displaystyle g(x):=f\circ f\circ \cdots \circ f(x)}$

con${\displaystyle f}$apareciendo${\displaystyle k}$El tiempo es localmente estable según el mismo criterio:

${\displaystyle |g'(x^{*})|<1,}$

dónde${\displaystyle x^{*}}$es cualquier punto del ciclo.

En una relación de recurrencia caótica , la variable${\displaystyle x}$Permanece en una región acotada, pero nunca converge a un punto fijo ni a un ciclo atractor; 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 tienda .

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 en su momento como modelo para el crecimiento de una población de conejos.

El mapa logístico se utiliza directamente para modelar el crecimiento poblacional o como punto de partida para modelos más detallados de dinámica poblacional. En este contexto, las ecuaciones de 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

${\displaystyle N_{t+1}=\lambda N_{t}e^{-aP_{t}}}$

${\displaystyle P_{t+1}=N_{t}(1-e^{-aP_{t}}),}$

con${\displaystyle N_{t}}$representando a los anfitriones y${\displaystyle P_{t}}$los parásitos, en ese momento${\displaystyle t}$.

Las ecuaciones integro-diferenciales 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 . ^{[ 8 ] [ 9 ]} 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${\displaystyle n}$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${\displaystyle n}$.

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, verificará si el elemento central 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 vendrá dado por

${\displaystyle c_{1}=1}$

${\displaystyle c_{n}=1+c_{n/2}}$

cuya complejidad temporal será${\displaystyle O(\log _{2}(n))}$.

En el procesamiento digital de señales , las relaciones de recurrencia pueden modelar la retroalimentación en un sistema, donde las salidas en un momento dado se convierten en entradas para un momento futuro. Por lo tanto, surgen en los filtros digitales de respuesta impulsional infinita (IIR) .

Por ejemplo, la ecuación para un filtro peine IIR de "alimentación directa" con retardo${\displaystyle T}$es:

${\displaystyle y_{t}=(1-\alpha )x_{t}+\alpha y_{t-T},}$

dónde${\displaystyle x_{t}}$es la entrada en el momento${\displaystyle t}$,${\displaystyle y_{t}}$es la salida en el tiempo${\displaystyle t}$, y${\displaystyle \alpha }$controla la cantidad de señal retardada que se realimenta a la salida. De esto podemos ver que

${\displaystyle y_{t}=(1-\alpha )x_{t}+\alpha ((1-\alpha )x_{t-T}+\alpha y_{t-2T})}$

${\displaystyle y_{t}=(1-\alpha )x_{t}+(\alpha -\alpha ^{2})x_{t-T}+\alpha ^{2}y_{t-2T}}$

etc.

Las relaciones de recurrencia, especialmente las lineales, se utilizan ampliamente tanto en la economía teórica como en la empírica. ^{[ 10 ] [ 11 ]} En particular, en macroeconomía se puede 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 dependen de variables rezagadas. El modelo se resolvería entonces para obtener los valores actuales de las variables clave ( tasa de interés , PIB real , etc.) en función de los valores pasados ​​y actuales de otras variables.

• Batchelder, Paul M. (1967). Introducción a las ecuaciones de diferencias lineales . Dover Publications.
• Miller, Kenneth S. (1968). Ecuaciones de diferencias lineales . WA Benjamin.
• Fillmore, Jay P.; Marx, Morris L. (1968). "Secuencias recursivas lineales". SIAM Rev. Vol.  10, n.º  3, págs. 324–353 . JSTOR 2027658 .  
• Brousseau, Alfred (1971). Recursión lineal y secuencias de Fibonacci . Asociación de Fibonacci.
• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest y Clifford Stein . Introducción a los algoritmos , segunda edición. MIT Press y McGraw-Hill, 1990. ISBN 0-262-03293-7Capítulo 4: Recurrencias, págs.  62–90.
• Graham, Ronald L.; Knuth , Donald E .; Patashnik, Oren (1994). Matemáticas concretas: Fundamentos para la informática (2.ª  ed.). Addison-Wesley. ISBN 0-201-55802-5.
• Enders, Walter (2010). Series temporales econométricas aplicadas (3.ª  ed.). Archivado del original el 10 de noviembre de 2014.
• Cull, Paul; Flahive, Mary ; Robson, Robbie (2005). Ecuaciones en diferencias: De conejos al caos . Springer. ISBN 0-387-23234-6.Capítulo 7.
• Jacques, Ian (2006). Matemáticas para la economía y los negocios (Quinta  ed.). Prentice Hall. pp. 551–568 . ISBN  0-273-70195-9.Capítulo 9.1: Ecuaciones en diferencias.
• Minh, Tang; Van To, Tan (2006). "Uso de funciones generadoras para resolver ecuaciones de recurrencia lineales no homogéneas" (PDF) . Actas de la Conferencia Internacional sobre Simulación, Modelado y Optimización, SMO'06 . págs. 399–404 . Archivado del original (PDF) el 4 de marzo de 2016. Consultado el 7 de agosto de 2014 . 
• Polyanin, Andrei D. "Ecuaciones en diferencias y funcionales: soluciones exactas" .En EqWorld - El mundo de las ecuaciones matemáticas.
• Polyanin, Andrei D. "Ecuaciones en diferencias y funcionales: métodos" .En EqWorld - El mundo de las ecuaciones matemáticas.
• Wang, Xiang-Sheng; Wong, Roderick (2012). "Asintótica de polinomios ortogonales mediante relaciones de recurrencia". Anal. Appl . 10 (2): 215– 235. arXiv : 1101.4371 . doi : 10.1142/S0219530512500108 . S2CID 28828175 .