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  termos da ecuación para definir o termo , ese número  chámase orde da relación. Se temos os valores dos primeiros  termos da secuencia, o resto da secuencia pódese calcular aplicando repetidamente a ecuación.

Nas recorrencias lineares, o termo -ésimo fórmase mediante unha función linear de  termos anteriores. Un exemplo famoso é a recorrencia dos números de Fibonacci,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 . Para estas recorrencias, pódese expresar o termo xeral da secuencia como unha expresión de forma explícita de . 

Outro tipo de recorrencias son as recorrencias lineares con coeficientes polinómicos dependendo de  (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 -ésimo.

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



onde  é unha función que implica  elementos consecutivos da secuencia. Neste caso, son necesarios  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

  coas condicións iniciais 

Obtemos a secuencia de números de Fibonacci,


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

.

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



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

  coas condicións iniciais 

A función xeradora da secuencia de Lucas é



A secuencia de números de Lucas é 

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

 Coeficientes binomiais 
Un exemplo sinxelo de relación de recorrencia multidimensional vén dado polos coeficientes binomiais , que contan as formas de seleccionar  elementos dun conxunto de  elementos. Pódense calcular mediante a relación de recorrencia



cos casos base . 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:



E tamén se poden calcular cunha recorrencia unidimensional:

co valor inicial . 

 Factorial 
O factorial defínese pola relación de recorrencia



e a condición inicial



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

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



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

 Operador de diferenzas e ecuacións diferenciais 
O operador de diferenzas denomínase comunmente  e defínese, en notación funcional, como


É polo tanto é un caso especial de diferenza finita.

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


Os parénteses ao redor de  e  omítense xeralmente, e  debe entenderse como o termo do índice  na secuencia  e non  aplicado ao elemento 

Dada a secuencia   as primeiras diferenzas de  son  As segundas diferenzas son  Un simple cálculo demostra que



As -ésimas diferenzas defínense recursivamente como  e temos



Esta relación pódese invertir, dando

A ecuación de diferenzas de orde  é unha ecuación que implica as  primeiras diferenzas dunha secuencia ou función, do mesmo xeito que unha ecuación diferencial de orde  relaciona as  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

é equivalente á relación de recorrencia

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, , con condicións iniciais , temos

Que podemos expresar en forma abreviada como  e un  vector de condicións iniciais  .

Se diagonalizamos , coa técnica de eigenvalores e eigenvectores, é fácil calcular a matriz  elevada a unha potencia, neste caso por ter o termo inicial  necesitamos elevar a  para obter ,  .

Así temos 
.

 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:



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






Sexa



Daquela






Se aplicamos a fórmula a  e tomamos o límite cando , 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 xeneralizada. Por exemplo, a solución a



ven dada por



a función de Bessel, mentres



resólvese con



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  . Tal ecuación pódese resolver escribindo  como transformación non linear doutra variable  que evolúe linearmente. Así logo pódense usar métodos estándar para resolver a ecuación de diferenzas lineares en .

 Estabilidade 

 Estabilidade das recorrencias lineares 
A recorrencia linear de orde ,



ten unha ecuación característica de tipo



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



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



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



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



coa recorrencia



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

 Notas 


 Véxase tamén 

 Bibliografía 




 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 1990. . Chapter 4: Recurrences, pp. 62–90.

 chapter 7.
  Chapter 9.1: Difference Equations.

  at EqWorld - The World of Mathematical Equations.
  at EqWorld - The World of Mathematical Equations.

 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 


  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).

Categoría:Combinatoria
Categoría:Álxebra
Categoría:Teoría de números
Categoría:Wikipedia:Páxinas con traducións non revisadas