Relación de recorrencia

En matemáticas, unha relación de recorrencia é unha ecuación segundo a cal o enésimo termo dunha secuencia de números é igual a algunha combinación dos termos anteriores. Se temos $k$ termos da ecuación para definir o termo $n$, ese número $k$ chámase orde da relación. Se temos os valores dos primeiros $k$ termos da secuencia, o resto da secuencia pódese calcular aplicando repetidamente a ecuación.

Nas recorrencias lineares, o termo Modelo:Mvar-ésimo fórmase mediante unha función linear de $k$ termos anteriores. Un exemplo famoso é a recorrencia dos números de Fibonacci,$$F_n=F_{n-1}+F_{n-2}$$onde a orde é 2 e a función linear é a suma dos dous termos anteriores.

Este exemplo é unha recorrencia linear con coeficientes constantes, porque os coeficientes da función linear (1 e 1) son constantes que non dependen de $n$. Para estas recorrencias, pódese expresar o termo xeral da secuencia como unha expresión de forma explícita de $n$.

Outro tipo de recorrencias son as recorrencias lineares con coeficientes polinómicos dependendo de $n$ (ver ecuación p-recursiva e función holonómica).

Resolver unha relación de recorrencia significa obter unha solución en forma pechada: unha función non recursiva para o termo $n$-ésimo.

Definición

Unha relación de recorrencia é unha ecuación que expresa cada elemento dunha secuencia en función dos anteriores.

$u_n=\phi (n,u_{n-1},u_{n-2},\dots ,u_{n-k})\text{for}n\ge k,$

onde $\phi :\mathbb{N}\times X^k\to X$ é unha función que implica Modelo:Mvar elementos consecutivos da secuencia. Neste caso, son necesarios Modelo:Mvar valores iniciais para definir unha secuencia.

Exemplos

Números de Fibonacci e de Lucas

A recorrencia de orde 2 satisfeita polos números de Fibonacci é o exemplo típico dunha relación de recorrencia linear homoxénea con coeficientes constantes. A secuencia de Fibonacci defínese usando a recorrencia

$F_n=F_{n-1}+F_{n-2}$ coas condicións iniciais $F_0=0,F_1=1.$

Obtemos a secuencia de números de Fibonacci,

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

Modelo:OEIS.

A recorrencia pódese resolver mediante a fórmula de Binet, que implica potencias das dúas raíces do polinomio característico. $t^2=t+1$. A función xeradora da secuencia de Fibonacci é a función racional

$G.f.:\frac{t}{1-t-t^2}.$

A secuencia de Lucas ten a mesma recorrencia con distintas condicións iniciais

$L_n=L_{n-1}+L_{n-2}$ coas condicións iniciais $L_0=2,L_1=1.$

A función xeradora da secuencia de Lucas é

$G.f.:\frac{2-t}{1-t-t^2}.$

A secuencia de números de Lucas é

2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199,...

Modelo:OEIS.

Coeficientes binomiais

Un exemplo sinxelo de relación de recorrencia multidimensional vén dado polos coeficientes binomiais $(\genfrac{}{}{0ex}{}{n}{k})$, que contan as formas de seleccionar $k$ elementos dun conxunto de $n$ elementos. Pódense calcular mediante a relación de recorrencia

$(\genfrac{}{}{0ex}{}{n}{k})=(\genfrac{}{}{0ex}{}{n-1}{k-1})+(\genfrac{}{}{0ex}{}{n-1}{k}),$

cos casos base $(\genfrac{}{}{0ex}{}{n}{0})=(\genfrac{}{}{0ex}{}{n}{n})=1$. Usando esta fórmula para calcular os valores de todos os coeficientes binomiais xera unha matriz infinita chamada triángulo de Pascal. Os mesmos valores tamén se poden calcular directamente mediante unha fórmula diferente que non é unha recorrencia, senón que usa factoriais:

$(\genfrac{}{}{0ex}{}{n}{k})=\frac{n!}{k!(n-k)!}.$

E tamén se poden calcular cunha recorrencia unidimensional:

$(\genfrac{}{}{0ex}{}{n}{k})=(\genfrac{}{}{0ex}{}{n}{k-1})(n-k+1)/k,$

co valor inicial $(\genfrac{}{}{0ex}{}{n}{0})=1$.

Factorial

O factorial defínese pola relación de recorrencia

$n!=n(n-1)!\text{for}n>0,$

e a condición inicial

$0!=1.$

Este é un exemplo de recorrencia linear de orde 1 con coeficiente polinómico Modelo:Mvar.

Mapa loxístico

Outro exemplo de relación de recorrencia é o mapa loxístico:

$x_{n+1}=r{x}_n(1-x_n),$

cunha constante dada $r$. Dado o termo inicial $x_0$, vanse obtendo sucesivamente os termos posteriores.

Operador de diferenzas e ecuacións diferenciais

O operador de diferenzas denomínase comunmente $\mathrm{\Delta },$ e defínese, en notación funcional, como

$(\mathrm{\Delta }f)(x)=f(x+1)-f(x).$

É polo tanto é un caso especial de diferenza finita.

Cando se usa a notación de índices para secuencias, a definición pasa a ser

$(\mathrm{\Delta }a{)}_n=a_{n+1}-a_n.$

Os parénteses ao redor de $\mathrm{\Delta }f$ e $\mathrm{\Delta }a$ omítense xeralmente, e $\mathrm{\Delta }{a}_n$ debe entenderse como o termo do índice Modelo:Mvar na secuencia $\mathrm{\Delta }a,$ e non $\mathrm{\Delta }$ aplicado ao elemento $a_n.$

Dada a secuencia $a=(a_n{)}_{n\in \mathbb{N}},$ as primeiras diferenzas de Modelo:Mvar son $\mathrm{\Delta }a.$ As segundas diferenzas son ${\mathrm{\Delta }}^{2}a=(\mathrm{\Delta }\circ \mathrm{\Delta })a=\mathrm{\Delta }(\mathrm{\Delta }a).$ Un simple cálculo demostra que

${\mathrm{\Delta }}^2{a}_n=a_{n+2}-2a_{n+1}+a_n.$

As Modelo:Mvar-ésimas diferenzas defínense recursivamente como ${\mathrm{\Delta }}^k=\mathrm{\Delta }\circ {\mathrm{\Delta }}^{k-1},$ e temos

${\mathrm{\Delta }}^k{a}_n=\sum _{t=0}^k(-1{)}^t(\genfrac{}{}{0ex}{}{k}{t})a_{n+k-t}.$

Esta relación pódese invertir, dando

$a_{n+k}=a_n+(\genfrac{}{}{0ex}{}{k}{1})\mathrm{\Delta }{a}_n+\cdots +(\genfrac{}{}{0ex}{}{k}{k}){\mathrm{\Delta }}^k(a_n).$

A ecuación de diferenzas de orde Modelo:Mvar é unha ecuación que implica as Modelo:Mvar primeiras diferenzas dunha secuencia ou función, do mesmo xeito que unha ecuación diferencial de orde Modelo:Mvar relaciona as Modelo:Mvar primeiras derivadas dunha función.

Nas dúas ecuacións vistas enriba cada unha é a inversa da outra, e as secuencias que son solución da ecuación diferencial son exactamente as que satisfán a relación de recorrencia.

Por exemplo, a ecuación da diferenzas

$3{\mathrm{\Delta }}^2{a}_n+2\mathrm{\Delta }{a}_n+7a_n=0$

é equivalente á relación de recorrencia

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

As ecuacións de diferenzas aseméllanse ás ecuacións diferenciais, e esta semellanza utilízase a miúdo para imitar os métodos de resolución de ecuacións diferenciables para aplicar á resolución das ecuacións de diferenzas e, polo tanto, as relacións de recorrencia.

Resolvendo

Resolución de relacións lineares de recorrencia con coeficientes constantes

Os métodos máis habituais de resolver este tipo de recorrencias é mediante funcións xeradoras ou mediante a forma matricial.

A forma matricial consiste en diagonalizar a matriz da recorrencia. Por exemplo, se consideremos a recorrencia de orde 3, $a_n=x{a}_{n-1}+y{a}_{n-2}+z{a}_{n-3}$, con condicións iniciais $a_0,a_1,a_2$, temos

$$\left(\begin{array}{c}{a}_{n+1}\\ a_n\\ a_{n-1}\end{array}\right)=\left(\begin{array}{c}x{a}_n+y{a}_{n-1}+z{a}_{n-2}\\ a_n\\ a_{n-1}\end{array}\right)=\left[\begin{array}{ccc}x& y& z\\ 1& 0& 0\\ 0& 1& 0\end{array}\right]\left(\begin{array}{c}{a}_n\\ a_{n-1}\\ a_{n-2}\end{array}\right)$$

Que podemos expresar en forma abreviada como $v_{n+1}=A{v}_n$ e un vector de condicións iniciais $v_0=\left(\begin{array}{c}{a}_2\\ a_1\\ a_0\end{array}\right)$.

Se diagonalizamos $A=PD{P}^{-1}$, coa técnica de eigenvalores e eigenvectores, é fácil calcular a matriz $A$ elevada a unha potencia, neste caso por ter o termo inicial $a_2$ necesitamos elevar a $n-1$ para obter $a_{n+1}$, $A^{n-1}=P{D}^{n-1}{P}^{-1}$.

Así temos $$\left(\begin{array}{c}{a}_{n+1}\\ a_n\\ a_{n-1}\end{array}\right)=P\left[\begin{array}{ccc}{d}_{0,0}^{n-1}& 0& 0\\ 0& d_{1,1}^{n-1}& 0\\ 0& 0& d_{2,2}^{n-1}\end{array}\right]P^{-1}{v}_0.$$.

Resolución de relacións de recorrencia non homoxéneas de primeira orde con coeficientes variables

Para a relación xeral de recorrencia linear non homoxénea de primeira orde con coeficientes variables:

$a_{n+1}=f_n{a}_n+g_n,f_n\ne 0,$

tamén hai un bo método para resolvela:

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

Sexa

$A_n=\frac{a_n}{\prod _{k=0}^{n-1}{f}_k},$

Daquela

$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)(A_0+\sum _{m=0}^{n-1}\frac{g_m}{\prod _{k=0}^m{f}_k})$

Se aplicamos a fórmula a $a_{n+1}=(1+h{f}_{nh})a_n+h{g}_{nh}$ e tomamos o límite cando $h\to 0$, obtemos a fórmula para ecuacións diferenciais lineares de primeira orde con coeficientes variables; a suma convértese nunha integral e o produto convértese na función exponencial dunha integral.

Resolución de relacións xerais de recorrencia lineares homoxéneas

Moitas relacións homoxéneas de recorrencia linear poden resolverse mediante a función hiperxeométrica xeralizada. Por exemplo, a solución a

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

ven dada por

$J_n=J_n(z),$

a función de Bessel, mentres

$(b-n)M_{n-1}+(2n-b+z)M_n-n{M}_{n+1}=0$

resólvese con

$M_n=M(n,b;z)$

a función hiperxeométrica confluente.

As secuencias que son solucións de ecuacións de diferenzas lineares con coeficientes polinómicos chámanse ecuacións p-recursivas. Para estas ecuacións de recorrencia específicas coñécense algoritmos que atopan solucións polinómicas, racionais (algoritmo de Abramov) ou hiperxeométricas (algoritmo de Petkovšek).

Resolver ecuacións en diferenzas racionais de primeira orde

Unha ecuación de diferenzas racional de primeira orde ten a forma $w_{t+1}=\frac{a{w}_t+b}{c{w}_t+d}$ . Tal ecuación pódese resolver escribindo $w_t$ como transformación non linear doutra variable $x_t$ que evolúe linearmente. Así logo pódense usar métodos estándar para resolver a ecuación de diferenzas lineares en $x_t$.

Estabilidade

Estabilidade das recorrencias lineares

A recorrencia linear de orde $d$,

$a_n=c_1{a}_{n-1}+c_2{a}_{n-2}+\cdots +c_d{a}_{n-d},$

ten unha ecuación característica de tipo

${\lambda }^d-c_1{\lambda }^{d-1}-c_2{\lambda }^{d-2}-\cdots -c_d{\lambda }^0=0.$

A recorrencia é estable, co significado de que as iteracións converxen asintóticamente a un valor fixo, se e só se os autovalores (é dicir, as raíces da ecuación característica), sexan reais ou complexas, son todos menores que a unidade en valor absoluto.

Estabilidade das recorrencias non lineares de primeira orde

Considere a recorrencia non linear de primeira orde

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

Esta recorrencia é localmente estable, o que significa que converxe a un punto fixo $x^{*}$ desde puntos suficientemente próximos $x^{*}$, se a pendente de $f$ no proximidade de $x^{*}$ é menor que a unidade en valor absoluto: é dicir,

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

Unha recorrencia non linear podería ter varios puntos fixos, nese caso algúns puntos fixos poden ser localmente estables e outros localmente inestables; para unha f continua dous puntos fixos adxacentes non poden ser ambos os dous localmente estables.

Relación coas ecuacións diferenciais

Ao resolver unha ecuación diferencial ordinaria de forma numérica, normalmente atopámonos cunha relación de recorrencia. Por exemplo, ao resolver o problema do valor inicial

$y^{\prime }(t)=f(t,y(t)),y(t_0)=y_0,$

co método de Euler e un tamaño de paso $h$, calculamos os valores

$y_0=y(t_0),y_1=y(t_0+h),y_2=y(t_0+2h),\dots$

coa recorrencia

$y_{n+1}=y_n+hf(t_n,y_n),t_n=t_0+nh$

Os sistemas de ecuacións diferenciais lineares de primeira orde poden discretizarse analíticamente usando os métodos mostrados no artigo de discretización.

Véxase tamén

Bibliografía

• Modelo:Cita libro
• Modelo:Cita libro
• Modelo:Cita libro
• Modelo:Cita libro
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 1990. Modelo:Isbn. Chapter 4: Recurrences, pp. 62–90.
• Modelo:Cita libro
• Modelo:Cita libro
• Modelo:Cita libro chapter 7.
• Modelo:Cita libro Chapter 9.1: Difference Equations.
• Modelo:Cita libro
• Modelo:Cita libro at EqWorld - The World of Mathematical Equations.
• Modelo:Cita libro at EqWorld - The World of Mathematical Equations.
• Modelo:Cita libro

Outros artigos

• Función holonómica
• Función iterada
• Polinomios ortogonais
• Recursión
• Fracción continua
• Coeficiente binomial
• Integración por fórmulas de redución
• Indución matemática
• Ecuación diferencial

Ligazóns externas

• Modelo:Springer
• Modelo:MathWorld
• Modelo:Cite web OEIS miles de recorrencias lineares, ordenadas por orde e sinatura.
• Fibonacci Quarterly publicación con máis de 60 anos de artigos sobre recorrencias (en aberto excluíndo os últimos 5 anos).

Modelo:Control de autoridades