Ecuaciones recursivas homogeneas

SEP

SNEST

DGEST

INSTITUTO TECNOLÓGICO DE TOLUCA

PROGRAMACIÓN NUMÉRICA

ING. ALEJANDRO ARELLANO TORRES

REPORTE: ECUACIONES RECURSIVAS HOMOGENEAS

DE LA O OJEDA KEVIN ALAIN SALAZAR MEDINA SAN ROMAN ORTEGA EDUARDO ANTONIO

METEPEC, MÉXICO A 9 DE ABRIL DE 2010

Ecuaciones de Recurrencia Las relaciones de recurrencia pueden considerarse como técnicas avanzadas de conteo.Resuelven problemas cuya solución no puede obtenerse usando variaciones, permutaciones, combinaciones, etc. Para introducir la teoría de las relaciones de recurrencia tomemos la conocida sucesión de Fibonacci, donde cada término, a partir del tercero, se obtiene sumando los dos anteriores, esto es: f n =f n-1 +f n+2 si n≥3 Una expresión de este tipo, en la que el término general de la sucesión seescribe en función de algunos otros términos anteriores, recibe los nombres de relación de recurrencia, ecuación de recurrencia o ecuación de diferencias. La relación de recurrencia no determina de manera única la sucesión. Para ello es necesario conocer algunos términos de la sucesión, lo que llamaremos condiciones iniciales o condiciones de frontera. En el caso anterior a 1 =1 y a 2 =1. Si queremosobtener un término concreto de una sucesión dada en forma recurrente debemos ir obteniendo todos los anteriores lo cual no es muy práctico. Interesa pues, determinar una expresión del tipo a n =g(n) en la que el termino general de la sucesión dependa sólo de la posición que ocupa y no de términos anteriores. A una expresión de ese tipo se llama solución de la ecuación de recurrencia. Definición: Unaecuación de recurrencia lineal de orden k con coeficientes constantes es una relación c n a n +c n-1 a n-1 +…+c n-k a n-k =b n , n≥k Donde c n ,c n-1 ,…,c n-k son constantes con c n ≠0 y c n-k ≠0 y b n (n entero) es una sucesión conocida. Diremos que es homogénea si b n =0, y de grado k. Ejemplo: La relación de recurrencia P n = (1.11) P n-1 es una relación de recurrencia lineal y homogénea deorden uno. La relación de recurrencia a n =a n-1 +a2 n-2 no es lineal. La relación de recurrencia H n =2H n-1 +1 no es homogénea y B n =nB n-1 no es de coeficientes constantes. Soluciones: Dada: c n a n +c n-1 a n-1 +…+c n-k a n-k =0 r (c n rk+c n-1 rk-1+…+c n-k )=0 y r≠0 para que r n sea solución debe ser raíz del polinomio P(x)= c n xk+c n-1 xk-1+…+c n-k
n-k

Al Polinomio P(x) se le llamapolinomio característico de la ecuación de recurrencia y sus raíces determinan la forma de la solución.

Así:

a) Si P(x) tiene sus k raíces distintas r 1 ,r 2 ,…,r k , entonces las k soluciones independientes(no múltiplos escalares una de otra) son r 1 n,r 2 n,…,r k n y la solución general es: a n =α 1 r 1 n+α 2 r 2 n+…+α k r k n Donde α 1 , α 2 ,…, α k son constantes que se determinan utilizandolas condiciones iniciales. b) Si P(x) tiene alguna raíz de multiplicidad >1 Sea P(x)=(x-r 1 )k1(x-r 2 )k2…(x-r t )kt con k 1 +k 2 …k t =k. Es decir P(x) tiene raíces distintas r 1 ,r 2 ,…,r t con multiplicidad k 1 ,k 2 ,…,k t respectivamente. Entonces cada raíz contribuye con tantas soluciones como indique su multiplicidad. Eso es, para cada j=1,…,t se tiene que las k j sucesiones (r j )n,n(r j)n,n2(r j )n,…,nkj-1(r j )n son soluciones independientes de la ecuación de recurrencia. Ejemplo: 2a n+3 =a n+2 + 2a n+1 -a n , n≥0, a 0 =0,a 1 =1,a 2 =2, P(x)= 2x3-x2-2x+1 Raices= 1,-1, 1/2 Solucion general: a n = α(1)n+β(-1)n+ϒ(1/2)n Las condiciones frontera para , a 0 =0, a 1 =1y a 2 =2 ecuaciones: α+β+ϒ=0 α-β+1/2ϒ=1 α+β+1/4ϒ=2 determinan el sistema de

cuya solución es α=5/2, β=1/6, ϒ=-8/3La solución es a n =5/2+(1/6)(-1)n-(8/3)(1/2)n Otros ejemplos: 1) a n =2a n-1 -2a n-2 , n≥2, a 0 =1, a 1 =2, P(x)= x2-2x+2 Raíces: 1+i, 1-i Solucion general: a n =α(1+i)n+β(1-i)n Aplicando propiedades de numeros complejos ���� ���� a n =√2 n[(α+β)cos n +(α-β)isen n ] 4 4 Haciendo k 1 = α+β y k 2 = (α-β)i

El sistema de ecuaciones queda: k 1 cos 0 +k 2 sen 0=1 ���� ���� √2[k 1 cos 4 +k 2 sen...