Relación de recurrencia

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Patrón que define una secuencia infinita de números

En matemáticas, a relación de recurrencia es una ecuación según la cual $n$ t término de una secuencia de números es igual a alguna combinación de los términos anteriores. A menudo, sólo $k$ los términos anteriores de la secuencia aparecen en la ecuación, para un parámetro $k$ que es independiente de $n$ ; este número $k$ se llama orden de la relación. Si los valores de la primera $k$ los números en la secuencia se han dado, el resto de la secuencia se puede calcular aplicando repetidamente la ecuación.

In recurrencias lineales, el $n$ t term is equated to a linear function of the $k$ términos anteriores. Un ejemplo famoso es la recurrencia para los números Fibonacci,

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

k

n

n

n

Resolver una relación recurrencia significa obtener una solución de forma cerrada: una función no recursiva $n$ .

El concepto de una relación de recurrencia se puede extender a arreglos 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 sucesión en función de los anteriores. Más precisamente, en el caso en que sólo está involucrado el elemento inmediatamente anterior, una relación de recurrencia tiene la forma

0,}" xmlns="http://www.w3.org/1998/Math/MathML">un=φ φ ()n,un− − 1)paran■0,{displaystyle U_{n}=varphi (n,u_{n-1})quad {text{for}quad n título0,}0,}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b39e6366097c9c3c9fb8f9f1c4baaa3b927193b5" style="vertical-align: -0.838ex; width:29.787ex; height:2.843ex;"/>

dónde

{displaystyle varphi:mathbb {N} times Xto X}

es una función, donde $X$ es un conjunto al que deben pertenecer los elementos de una secuencia. Para cualquier ${displaystyle u_{0}in X}$ , esto define una secuencia única con $u_{0}$ como su primer elemento, llamado el valor inicial.

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

{displaystyle u_{n}=varphi (n,u_{n-1},u_{n-2},ldotsu_{n-k})quad {text{for}}quad ngeq k,}

Donde ${displaystyle varphi:mathbb {N} times X^{k}to X}$ es una función que implica $k$ elementos consecutivos de la secuencia. En este caso, $k$ los valores iniciales son necesarios para definir una secuencia.

Ejemplos

Factoriales

El factorial se define por la relación de recurrencia

0,}" xmlns="http://www.w3.org/1998/Math/MathML">n!=n()n− − 1)!paran■0,{displaystyle n!=n(n-1)!quad {text{for}quad n título0,}0,}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/12bc6067e14b24bf50711c08808b7b2b3b7387d0" style="vertical-align: -0.838ex; width:28.122ex; height:2.843ex;"/>

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

{displaystyle f(n)=n}

como su único coeficiente.

Mapa logístico

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

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

con una constante dada $r$ ; dado el mandato inicial $x_{0}$ cada término posterior es determinado por esta relación.

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 sucesión de Fibonacci se define mediante la recurrencia

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

con condiciones iniciales

F_{0}=0

{displaystyle F_{1}=1.}

Explícitamente, la recurrencia produce las ecuaciones

F_{2}=F_{1}+F_{0}

F_{3}=F_{2}+F_{1}

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 métodos descritos a continuación, produciendo la fórmula de Binet, que implica poderes 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

{frac {t}{1-t-t^{2}}}.

Coeficientes binomiales

Un simple ejemplo de una relación de recurrencia multidimensional es dada por los coeficientes binomiales ${tbinom {n}{k}}$ , que cuenta las maneras de seleccionar $k$ elementos de un conjunto de $n$ elementos. Pueden ser calculadas por la relación de recurrencia

{binom {n}{k}}={binom {n-1}{k-1}}+{binom {n-1}{k}},

con los casos de base ${tbinom {n}{0}}={tbinom {n}{n}}=1$ . Usando esta fórmula para calcular los valores de todos los coeficientes binomiales genera un array infinito llamado triángulo de Pascal. Los mismos valores también pueden ser calculados directamente por una fórmula diferente que no es una recurrencia, sino que utiliza factoriales, multiplicación y división, no sólo adiciones:

{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 ser calculada después de la multiplicación, por no introducir números fraccionados). Esta recurrencia es ampliamente utilizada en las computadoras porque no requiere construir una tabla como lo hace la recurrencia bidimensional, y implica números enteros muy grandes como lo hace la fórmula con factoriales (si se utiliza ${textstyle {binom {n}{k}}={binom {n}{n-k}},}$ todos los enteros involucrados son más pequeños que el resultado final).

Operador de diferencias y ecuaciones en diferencias

El diferencia de operador es un operador que mapea secuencias a secuencias, y, más generalmente, funciones a funciones. Es comúnmente denotado $Delta$ y se define, en la notación funcional, como

{displaystyle (Delta f)(x)=f(x+1)-f(x).}

Es, pues, un caso especial de diferencia finita.

Cuando se usa la notación de índice para secuencias, la definición se vuelve

{displaystyle (Delta a)_{n}=a_{n+1}-a_{n}.}

Los paréntesis alrededor $Delta f$ y ${displaystyle Delta a}$ son generalmente omitidos, y ${displaystyle Delta a_{n}}$ debe entenderse como el término del índice $n$ en la secuencia ${displaystyle Delta a,}$ y no $Delta$ aplicado al elemento ${displaystyle a_{n}.}$

secuencia dada ${displaystyle a=(a_{n})_{nin mathbb {N} },}$ el primera diferencia de $a$ es ${displaystyle Delta a.}$

El segunda diferencia es ${displaystyle Delta ^{2}a=(Delta circ Delta)a=Delta (Delta a).}$ Un cálculo simple muestra que

{displaystyle Delta ^{2}a_{n}=a_{n+2}-2a_{n+1}+a_{n}.}

Más generalmente: el $k$ la diferencia se define recursivamente como ${displaystyle Delta ^{k}=Delta circ Delta ^{k-1},}$ y uno tiene

{displaystyle Delta ^{k}a_{n}=sum _{t=0}^{k}(-1)^{t}{binom {k}{t}}a_{n+k-t}.}

Esta relación se puede invertir, dando

{displaystyle a_{n+k}=a_{n}+{k choose 1}Delta a_{n}+cdots +{k choose k}Delta ^{k}(a_{n}).}

A ecuación de diferencia de orden $k$ es una ecuación que involucra el $k$ primeras diferencias de una sucesión o una función, al igual que una ecuación diferencial de orden $k$ relaciona las $k$ primeras derivadas de una función.

Las dos relaciones anteriores permiten transformar una relación de recurrencia de orden $k$ en una ecuación en diferencia de orden $k$ y, por el contrario, una ecuación en diferencia de orden $k$ en 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 en diferencias son exactamente las que satisfacen la relación de recurrencia.

Por ejemplo, la ecuación de diferencias

{displaystyle 3Delta ^{2}a_{n}+2Delta a_{n}+7a_{n}=0}

es equivalente a la relación de recurrencia

{displaystyle 3a_{n+2}=4a_{n+1}-8a_{n},}

en el sentido de que las dos ecuaciones son satisfechas por las mismas sucesiones.

Como es equivalente a que una sucesión 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 de diferencia" a veces se usan indistintamente. Consulte Ecuación en diferencia racional y Ecuación en diferencia matricial para ver ejemplos de usos de "ecuación en diferencia" en lugar de "relación de recurrencia"

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

Las ecuaciones de suma se relacionan con las ecuaciones de diferencia como las ecuaciones integrales se relacionan con las ecuaciones diferenciales. Ver cálculo de escala de tiempo para una unificación de la teoría de las ecuaciones en diferencias con la de las ecuaciones diferenciales.

De secuencias a cuadrículas

Las relaciones de recurrencia monovariable o unidimensional son sobre secuencias (es decir, funciones definidas en redes unidimensionales). Las relaciones de recurrencia multivariable o n-dimensional se tratan $n$ - Cuadrículas dimensionales. Funciones definidas en $n$ - También se puede estudiar con ecuaciones parciales de diferencia.

Resolver

Resolver relaciones de recurrencia lineal con coeficientes constantes

Resolver relaciones de recurrencia no homogéneas de primer orden con coeficientes variables

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

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

también hay un buen método para resolverlo:

a_{n+1}-f_{n}a_{n}=g_{n}

{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}}}

{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

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

Entonces

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

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

{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}}}

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 $h to 0$ , obtenemos la fórmula para las 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.

Resolver relaciones generales de recurrencia lineal homogénea

Muchas relaciones de recurrencia lineales homogéneas pueden resolverse mediante la serie hipergeométrica generalizada. Los casos especiales de estos conducen a relaciones de recurrencia para los polinomios ortogonales y muchas funciones especiales. Por ejemplo, la solución a

J_{n+1}={frac {2n}{z}}J_{n}-J_{n-1}

está 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 con

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

la serie hipergeométrica confluente. Las sucesiones que son las soluciones de ecuaciones en diferencias 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.

Resolver ecuaciones en diferencias racionales de primer orden

Una ecuación de diferencia racional de primer orden tiene la forma $w_{t+1}={tfrac {aw_{t}+b}{cw_{t}+d}}$ . Tal ecuación se puede resolver por escrito $w_{t}$ como una transformación no lineal de otra variable $x_{t}$ que en sí mismo evoluciona linealmente. Entonces los métodos estándar se pueden utilizar para resolver la ecuación de diferencia lineal en $x_{t}$ .

Estabilidad

Estabilidad de recurrencias lineales de orden superior

La recurrencia lineal del orden $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 complejas, son todos menores que la unidad en valor absoluto.

Estabilidad de las recurrencias de matrices lineales de primer orden

En la ecuación de diferencia matricial de primer orden

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

con vector de estado $x$ y matriz de transición $A$ , $x$ converge asintotically to the steady state vector $x^{*}$ si y sólo si todos los eigenvalues de la matriz de transición $A$ (si es real o complejo) tiene un valor absoluto inferior a 1.

Estabilidad de recurrencias no lineales de primer orden

Considere la recurrencia no lineal de primer orden

x_{n}=f(x_{n-1}).

Esta recurrencia es localmente estable, lo que significa que converge a un punto fijo $x^{*}$ de puntos suficientemente cerca $x^{*}$ , si la pendiente de $f$ en el barrio $x^{*}$ es más pequeño que la unidad en valor absoluto: es decir,

<math alttext="{displaystyle |f'(x^{*})|Silenciof.()xAlternativa Alternativa )Silencio.1.{displaystyle Silenciof'(x^{*}) Mantenerse informado1.}<img alt="{displaystyle |f'(x^{*})|

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 $k$ para $1}" xmlns="http://www.w3.org/1998/Math/MathML">k■1{displaystyle k] 1" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5cda43bd4034dc2d04cd562005d0af81d3d2dbc6" style="vertical-align: -0.338ex; width:5.472ex; height:2.176ex;"/>$ . Este ciclo es estable, lo que significa que atrae un conjunto de condiciones iniciales de medida positiva, si la función compuesta

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

con $f$ apareciendo $k$ tiempos es localmente estable según el mismo criterio:

<math alttext="{displaystyle |g'(x^{*})|Silenciog.()xAlternativa Alternativa )Silencio.1,{displaystyle Silenciog'(x^{*})<img alt="|g'(x^{*})|

Donde $x^{*}$ es cualquier punto en el ciclo.

En una relación de recurrencia caótica, la variable $x$ permanece en una región atada pero nunca converge a un punto fijo o un ciclo de atracción; cualquier punto fijo o ciclos de la ecuación son inestables. Vea también mapa logístico, transformación dyadica y mapa de tiendas.

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 de valor inicial

y'(t)=f(t,y(t)), y(t_{0})=y_{0},

con el método de Euler y un tamaño de paso $h$ , uno calcula los valores

y_{0}=y(t_{0}), y_{1}=y(t_{0}+h), y_{2}=y(t_{0}+2h), dots

por la recurrencia

{displaystyle ,y_{n+1}=y_{n}+hf(t_{n},y_{n}),t_{n}=t_{0}+nh}

Los sistemas de ecuaciones diferenciales lineales de primer orden se pueden discretizar exactamente de forma 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 en diferencias más conocidas tienen su origen en el intento de modelar la dinámica de la población. Por ejemplo, los números de Fibonacci alguna vez se usaron como modelo para el crecimiento de una población de conejos.

El mapa logístico se usa 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

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

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

con $N_{t}$ representando a los anfitriones, y $P_{t}$ los parásitos, a la vez $t$ .

Las ecuaciones de integraldiferencia 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.

Informática

Las relaciones de recurrencia también son de fundamental importancia en el análisis de algoritmos. 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 simple es el tiempo que un algoritmo toma para encontrar un elemento en un vector ordenado con $n$ elementos, en el peor caso.

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

Un mejor algoritmo se llama búsqueda binaria. Sin embargo, requiere un vector ordenado. Primero verificará si el elemento está en el medio del vector. De lo contrario, comprobará si el elemento medio es mayor o menor que el elemento buscado. En este punto, la mitad del vector se puede descartar y el algoritmo se puede ejecutar nuevamente en la otra mitad. El número de comparaciones estará dado por

c_{1}=1

c_{n}=1+c_{n/2}

la complejidad del tiempo ${displaystyle O(log _{2}(n))}$ .

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

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

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

Donde $x_{t}$ es la entrada a la vez $t$ , $y_{t}$ es la salida a la vez $t$ , y $alpha$ controla cuánto de la señal retardada se invierte de nuevo en la salida. De esto podemos ver que

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.

Economía

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

Contenido relacionado

Más resultados...