relacionesrecurrencia

7/23/2019 RelacionesRecurrencia

http://slidepdf.com/reader/full/relacionesrecurrencia 1/4

TEMA #2: Relaciones de Recurrencia

Progresión Geométrica

Es una sucesión infinita de números donde el cociente de cualquier término (distinto del

primero) entre su predecesor es una constante llamada razón común.

Relación de Recurrencia

Es una ecuación en donde para obtener el valor actual se depende de uno o más valores

predecesores inmediatos a él.

an+1 + can = f (n), a = A, n ≥

cnan + cn!1an!1 + cn!"an!" = f (n), a = A1 , a1 = A2, n ≥ "

Condiciones Frontera o Iniciales

#on los valores iniciales que se necesitan para resolver la relación de recurrencia, se

denotan como a o a1.

Primer Orden$uando la relación de recurrencia sólo depende de su predecesor inmediato, por e%emplo&

an+1 = 3an, a = ', n ≥

Lineal

$uando cada término con subndice de la relación de recurrencia aparece elevado a la

primera potencia, por e%emplo&

an+1 = 3an, a = ', n ≥

Homogénea

$uando f (n) = para todo n ∈ N, por e%emplo&

an+1 = 3an ⇒ an+1 ! 3an = 0, a = ', n ≥

Coeficientes Constantes

$uando cada término con subndice de la relación de recurrencia está multiplicado por unaconstante, por e%emplo&

an+1 = 3an, a = ', n ≥

Segundo Orden

$uando la relación de recurrencia depende de sus dos predecesores inmediatos, por

e%emplo&

an = an-1 + 5an-2, a = , a1 = 1, n ≥ "

No Lineal

$uando alún término con subndice de la relación de recurrencia aparece elevado a una

potencia diferente a la primera potencia, por e%emplo&

an+12 = 3an

2, a = ', n ≥

No Homogénea



$uando f (n) ≠ para todo n ∈ N, por e%emplo&

an+1 = 3an + n ⇒ an+1 ! 3an = n, a = ', n ≥

Coeficientes Variales

$uando alún término con subndice de la relación de recurrencia está multiplicado por una

valor variable, por e%emplo&an = nan!1, a = 1, n ≥ 1

Solución General

El valor de an es una función de n que no depende de los términos anteriores de la sucesión,una ve* definido a, que se obtiene a partir de la relación de recurrencia.

!ransformación de una Relación de Recurrencia No Lineal a Lineal

#e puede transforma una relación de recurrencia no lineal a lineal para poder resolverla

mediante una sustitución alebraica bn = an". E%emplo&

an+1" = 3an

", a = ', n ≥

bn+1 = 'bn, b = , n ≥ na ve* -ec-o esto procedemos a resolverla como una relación de recurrencia lineal, para

este e%emplo corresponde a de primer orden, -omoénea con coeficientes constantes.

/espués de resolverla sacamos ra* a cada número obtenido en la solución eneral para

tener la solución eneral de la relación de recurrencia no lineal. E%emplo&

bn = (')n, b = , n ≥

an = '(√')n, a = ', n ≥

Solución General de las Relaciones de Recurrencia de Primer Orden" Lineales"

Homogéneas # con Coeficientes Constantes

0a solución eneral de la relación de recurrencia

an+1 = can, donde n ≥ ,

c es una constante a = A es única está dada por

an = Acn, n ≥ .

Está última ecuación es una función discreta cuo dominio es el con%unto N de los enteros

no neativos.

Solución General de las Relaciones de Recurrencia de Segundo Orden" Lineales"

Homogéneas # con Coeficientes Constantes


cnan + cn!1an!1 + cn!"an!" = , donde n ≥ ",

cn, cn!1, cn!" son constantes diferentes de cero tenemos a = A1 , a1 = A2, reali*amos losiuiente&

• #ustituimos an = dr n, donde c ≠ r ≠ . btendremos&

cndr n + cn!1dr n!1 + cn!"dr n!" = .

• #acamos factor común. btendremos una ecuación cuadrática llamada ecuación

característica&

cnr " + cn!1r 1 + cn!"r = .



• 2esolvemos la ecuación cuadrática obtenemos las races de esa ecuación r 1 r ",

estas son llamadas raíces características. Estas races pueden ser& números realesdistintos, números reales iuales números comple%os con%uados, (sólo

anali*aremos los dos primeros casos).

• #i las races obtenidas son números reales distintos vamos formando la solución

eneral de la siuiente manera&an = c1(r 1)

n + c"(r ")n.

• #i las races obtenidas son números reales iuales vamos formando la solución

eneral de la siuiente manera&

an = c1(r 1)n + c"n(r ")

n.

• na ve* teniendo este avance de la solución eneral con las condiciones iniciales

formamos un sistema de ecuaciones -allamos c1 c". E%emplo&

a = c1(r 1) + c"(r ")

⇒ A1 = c1 + c"

a1 = c1(r 1)1 + c"(r ")

1 ⇒ A" = c1r 1 + c"r ",

entonces tenemos el sistemas de ecuaciones& A1 = c1 + c"

A" = c1r 1 + c"r ".

• $on los valores a obtenidos de las races c1 c", las constantes c1 c" obtenemos

la solución eneral de la relación de recurrencia&

an = c1(r 1)n + c"(r ")

n ⇒ 2aces distintas

an = c1(r 1)n + c"n(r ")

n ⇒ 2aces iuales

Solución General de las Relaciones de Recurrencia de Primer o Segundo Orden"

Lineales" No Homogéneas # con Coeficientes Constantes


d nan + d n!1an!1 + d n!"an!" = f (n), donde n ≥ ",

d n, d n!1, d n!" son constantes diferentes de cero, f(n) ≠ tenemos a = A1 , a1 = A2, se obtienesumando la solución -omoénea asociada (an

h) la solución particular (an p)&

an = anh + an

p

2eali*amos lo siuiente&

• 2esolvemos la relación -omoénea asociada como se conoce (sin sacar las

constantes), pasos anteriormente dados, as obtenemos la solución -omoénea

asociada (anh).

• 3-ora iremos a obtener la solución particular. 0o primero es ver la función dada en

f (n) observamos la Tabla 1 para ver cual es la an p&

f (n) an $

c, constante

nn"

nt , t ∈ Z+

r n, r ∈ R

nt r n

A, constante

A1n + A

A"n" + A1n + A

At nt + At !1n

t !1 + ... + A1n + A

Ar n

r n ( At nt + At !1n

t !1 + ... + A1n + A)

Tabla 1



• #i an p contiene races distintas a las obtenidas en an

h entonces pasamos al siuiente

paso. #i contiene una ra* iual a las obtenidas en anh entonces an

p = nan p pasamos

al siuiente paso. #i contiene dos races iuales a las obtenidas en anh entonces an

p =

n"an p pasamos al siuiente paso.

• btenemos el valor de cada constante de la an p, o sea, las constantes At , At !1, ..., A1,

A, etc. Eso lo loramos sustituendo cada término an de la relación de recurrenciadada por la an

p resolviendo la ecuación. 4or e%emplo& f (n) = r n, por lo tanto an p =

Ar n, entonces se obtiene alo as&

cn Ar n + cn!1 Ar n!1 + cn!" Ar n!" = r n

• $on la solución -omoénea asociada (anh) la solución particular (an

p) obtenidas a

tenemos la solución eneral de la relación de recurrencia&

an = anh + an

p

• #ólo falta calcular los valores c1 c" (de la solución -omoénea asociada),

mediante un sistema de ecuaciones, sustituendo con las condiciones inicialesdadas. 5 con esto tenemos a la solución eneral de la relación de recurrencia.

relacionesrecurrencia

Documents