Upload
jedson-guedes
View
705
Download
2
Embed Size (px)
DESCRIPTION
Otimização (resolução) de Equações de recorrência lineares a coeficientes constantes e não-homogêneas: link.
Citation preview
Otimizacao de equacoes derecorrencia lineares
Jedson B. Guedes
http://jedsonguedes.wordpress.com
Neste texto sera apresentada uma maneira de se otimizar umaequacao de recorrencia linear a coeficientes constantesnao-homogeneas.
Eis alguns exemplos:
I cn = 7cn−1 + 2n
I un = 3un−2 + 5n−1
Definicao formal
Sejaun = a1un−1 + · · ·+ akun−k + f (n), n ≥ k ,
onde
f (n) =l∑
i=1
bni Pi (n),
com Pi (n) sendo um polinomio em n de grau bi .
Otimizacao - Exemplo
Uma tecnica bem util e bastante utilizada e a de transformar umaequacao de recorrencia linear a coeficientes constantesnao-homogenea em uma linear a coeficientes constanteshomogenea.Um exemplo do uso de tal tecnica e mostrado abaixo.
Nos sao dadas as seguintes informacoes:
un = 2un−1 + 3n, n ≥ 1u0 = 1
Otimizacao - Exemplo
E se multiplicarmos a equacao de recorrencia dada por tres,encontramos
3 · un = 3 · 2un−1 + 3 · 3n
3un = 6un−1 + 3n+1 (2)
Otimizacao - Exemplo
A equacao dada nao foi multiplicada por tres por acaso.Repare que agora o termo que torna a equacao dadanao-homogenea, que neste caso e o 3n+1, esta presente em ambasas equacoes.
Com isso podemos subtrair (2) de (1), para eliminar o termo queas deixa nao-homogeneas.
un+1 − 3un = 2un − 6un−1
un+1 = 5un − 6un−1 (3)
Exemplo
A relacao de recorrencia (3) e linear homogenea e equivalenteaquela dada que e nao-homogenea.
Portanto, basta utilizar o mesmo processo visto na nota de aulaEquacoes de recorrencia, I : achar o polinomio caracterıstico, usar osomatorio dado, montar o sistema de equacoes e substituir osvalores.
Exemplo
O polinomio caracterıstico de un+1 = 5un − 6un−1 e
p(x) = x2 − 5x + 6.
Suas raızes: {2,3}. Cada raiz tem multiplicidade igual a 1.
Exemplo
Dessa forma, podemos montar o seguinte sistema de equacoes:{u0 = λ020 + λ130 = 1u1 = λ021 + λ131 = 5
⇓{λ0 + λ1 = 1
2λ0 + 3λ1 = 5
Com isso, achamos que λ0 = −2 e λ1 = 3.
Exemplo
Reescrevendo o un em funcao nao mais de Qi (n), mas em funcaode λi , temos
un = λ02n + λ13n
Substituindo os valores de λi ,
un = −2 · 2n + 3 · 3n
⇓
un = −2n+1 + 3n+1
Pronto!
Reescrevendo o un em funcao nao mais de Qi (n), mas em funcaode λi , temos
un = λ02n + λ13n
Substituindo os valores de λi ,
un = −2 · 2n + 3 · 3n
⇓
un = −2n+1 + 3n+1
So isso.
Pronto!
Usando raciocınio analogo, e possıvel reslover mais uma gama derelacoes de recorrencia.
A dificuldade deste metodo esta em reparar quais operacoes fazerpara se conseguir eliminar a parte nao-homogenea, o que pode naoser tao obvio.
Outro problema e que pode ser preciso repetir os passos iniciaisvarias e varias vezes, como veremos abaixo.
Exemplo 2
Sejaun = 2un−1 + n + 2n, n ≥ 1u0 = 0
Multiplicando por dois a equacao dada:
2un = 4un−1 + 2n + 2n+1 (4)
Exemplo 2
Ainda da equacao dada, temos que
un = 2un−1 + n + 2n
⇓
un+1 = 2un + (n + 1) + 2n+1 (5)
Subtraindo (4) de (5):
(5− 4) : un+1 − 2un = 2un − 4un−1 + (n + 1)− 2n (6)
un+1 = 4un − 4un−1 − n + 1 (7)
un+2 = 4un+1 − 4un − (n + 1) + 1 (8)
Exemplo 2
Como ainda ha termo deixando a equacao de recorrencia naohomogenea, continuamos.
(8− 7) : un+2 − un+1 = 4un+1 − 8un + 4un−1 − 1 (9)
un+2 = 5un+1 − 8un + 4un−1 − 1 (10)
un+3 = 5un+2 − 8un+1 + 4un − 1 (11)
Exemplo 2
(11 - 10):
un+3 − un+2 = 5un+2 − 13un+1 + 12un − 4un−1 (12)
un+3 = 6un+2 − 13un+1 + 12un − 4un−1 (13)
Exemplo 2
Agora, sim, encontramos uma equacao de recorrencia linear acoeficientes constantes homogenea, a equacao (13):
un+3 = 6un+2 − 13un+1 + 12un − 4un−1.
Com isso, a otimizamos da forma ja conhecida.
Exemplo 2
Primeiramente, achamos seu polinomio caracterıstico. O qual edefinido por
P(x) = x4 − 6x3 + 13x2 − 12x + 4
Exemplo 2
Podemos - e devemos - reescrever tal polinomio na formaP(x) = (x − r1)m1(x − r2)m2 . . . (x − rp)mp , p ≤ k. Assim, osupracitado polinomio caracterıstico fica:
P(x) = (x − 2)2(x − 1)2
Exemplo 2
Seguindo com o processo, encontraremos uma relacao derecorrencia que e equivalente a primeira, mas dada em funcao de napenas, que e
un = −2− n + 2n+1 + n2n.
Um outro caminho
Esta relacao deu bastante trabalho, basicamente devido asmanobras que foram necessarias para se conseguir uma relacao derecorrencia homogenea equivalente a primeira, pois apos achar opolinomio caracterıstico, o processo foi o ja conhecido.
Voltemos, pois, ao passo em que estamos a achar o polinomiocaracterıstico. Repare que
P(x) = (x − 2)2(x − 1)2 = (x − 2)1(x − 1)1+1(x − 2)0+1.
O polinomio caracterıstico pelo produto de produtorios!
Os expoentes nao foram postos assim por acaso, mas para facilitara visualizacao e identificacao.
P(x) = (x − 2)1︸ ︷︷ ︸(H)
(x − 1)1+1(x − 2)0+1︸ ︷︷ ︸(N−H)
(H) significa a parte homogenea, ao passo que (N-H) representa aparte nao-homogenea.
O polinomio caracterıstico pelo produto de produtorios!
Ha um teorema que diz que o polinomio caracterıstico pode serescrito como um produto de produtorios, que e definido por:
P(x) =∏
(x − ri )mi ·
∏(x − bi )grau
Pi (n)+1
ri e a raiz homogenea e bi e a parte nao-homogenea.
O polinomio caracterıstico pelo produto de produtorios!
E gracas a este teorema que podemos reescrever P(x) como
P(x) = (x − 2)1(x − 1)1+1(x − 2)0+1
E, de fato, podemos verificar que as raızes deP(x) = x4 − 6x3 + 13x2 − 12x + 4 sao {2, 1}.
Para que se apreenda bem o uso deste produto de produtorio,outro exemplo e dado a seguir.Considere
un = 5un−1 − 6un−2 + n22n.
O polinomio caracterıstico pelo produto de produtorios!Exemplo
A parte homogenea e 5un−1 − 6un−2 e suas raızes sao {2, 3}, umavez que o polinomio caracterıstico deste e x2 − 5x + 6, e cada raizpossui multiplicidade igual a 1.
Assim, o produtorio da parte homogenea sera∏(x − ri )
mi = (x − 2)1(x − 3)1.
O polinomio caracterıstico pelo produto de produtorios!Exemplo
A parte nao-homogena e n22n.
Em 2n, temos que 2 e raiz de multiplicidade 1.Teremos, entao, expoente igual a 3, que surge da multiplicidade den2, que e 2, adicionado de 1.
Desta forma, o produtorio da parte nao-homogenea sera∏(x − bi )grau
Pi (n)+1 = (x − 2)3.
O polinomio caracterıstico pelo produto de produtorios!Exemplo
O polinomio caracterıstico de un = 5un−1 − 6un−2 + n22n e,portanto,
P(x) = (x − 2)(x − 3) · (x − 2)3
P(x) = (x − 2)4(x − 3).