16-Métodos-de Resolução

Prévia do material em texto

Me´todos de Resoluc¸a˜o de Relac¸o˜es de Recorreˆncia
Existem diferentes me´todos para resolver relac¸o˜es de recorreˆncia:
I Me´todo iterativo ou de substituic¸a˜o
I Me´todo de suposic¸a˜o e verificac¸a˜o
I Me´todo das ra´ızes caracter´ısticas
1 / 33
Me´todo iterativo ou de substituic¸a˜o
Consideremos o exemplo da Torre de Hano´i, onde{
Tn = 2Tn−1 + 1
T1 = 1
Tn = 2Tn−1 + 1
2Tn−1 = 2(2Tn−2) + 2
22Tn−2 = 23Tn−3 + 22
...
2n−2T2 = 2n−1T1 + 2n−2
Tn = 2
n−1T1 + (1 + 2 + 22 + · · ·+ 2n−2)
Usando a condic¸a˜o inicial T1 = 1, temos
Tn = 1 + 2 + 2
2 + · · ·+ 2n−2
Lembrando que 1 + 2 + 22 + · · ·+ 2n−1 = 1−2n1−2 = 2n − 1.
Logo, Tn = 2
n − 1, n ≥ 1.
2 / 33
Me´todo iterativo para o problem das Ovais
Consideremos o exemplo do problema das ovais, onde{
an = an−1 + 2(n − 1)
a1 = 2
an = an−1 + 2(n − 1)
an−1 = an−2 + 2(n − 2)
an−2 = an−3 + 2(n − 3)
...
a2 = a1 + 2(n − (n − 1))
an = a1 + 2[(n − 1) + (n − 2) + · · ·+ (n − (n − 1))
Como a1 = 2, temos
an = 2 + 2[(n + n + · · ·+ n)︸ ︷︷ ︸
n(n−1)
−(1 + 2 + · · ·+ (n − 1))]
3 / 33
continuac¸a˜o
Lembrando que:
∑n
i=1 i =
1
2 [n(n − 1)]
Segue que:
an = 2+2[n
2− 12(n2+n)] = 2+2[n(n−1)− 22(n−1)n] = 2+n2−n
Portanto,
an = 2 + n(n − 1), n ≥ 1
Observac¸a˜o:
O me´todo iterativo, ou de substituic¸a˜o, e´ u´til para relac¸o˜es de
recorreˆncia do tipo
an = can−1 + f (n)
para n ≥ 1 e a0 dado.
4 / 33
Suposic¸a˜o e Verificac¸a˜o
Consideremos o exemplo da Torre de Hano´i{
Tn = 2Tn−1 + 1
T1 = 1
Vamos tabular Tn para valores pequenos de n:
n Tn
1 1 =21 − 1
2 3 =22 − 1
3 7 =23 − 1
4 15 =24 − 1
5 31 =25 − 1
Suposic¸a˜o: Tn = 2
n − 1
5 / 33
Verificac¸a˜o
Induc¸a˜o em n:
I Seja P(n) a afirmac¸a˜o: Tn = 2n − 1∀n ∈ N, n ≥ 1.
I Base: P(1) e´ verdadeira porque T1 = 21 − 1 = 1.
I Passo da induc¸a˜o: Assuma que P(k) e´ verdadeira, isto e´,
Tk = 2
k − 1. Para provar que P(k + 1) e´ verdadeira,
precisamos mostar que Tk+1 = 2
k+1 − 1.
Desenvolvendo: Tk+1 = 2Tk + 1, pela relac¸a˜o de recorreˆncia.
Portanto,
Tk+1 = 2 (2
k − 1)︸ ︷︷ ︸
H.I .
+1 = 2(k + 1)− 2 + 1 = 2(k + 1)− 1
Logo, P(k + 1) e´ verdadeira e pelo P.I.M. P(n) e´ verdadeira
∀n ≥ 1.
6 / 33
Relac¸o˜es de recorreˆncia lineares
Uma relac¸a˜o de recorreˆncia e´ dita linear se ela e´ da forma:
an = c1an−1 + c2an−2 + · · ·+ cdan−d + f (n)
onde ci , i = 1, · · · d sa˜o constantes.
Neste caso, dizemos que a ordem da relac¸a˜o de recorreˆncia e´ d .
Se f (n) = 0 a relac¸a˜o de recorreˆncia e´ dita linear homogeˆnea.
Caso contra´rio e´ linear na˜o homogeˆnea.
7 / 33
Exemplos
1. Sequeˆncia de Fibonacci: an = an−1 + an−2, com a0 = 1 e
a1 = 1, tem ordem 2 e e´ uma relac¸a˜o de recorreˆncia linear
homogeˆnea, f (n) = 0;
2. Torre de Hano´i: an = 2an−1 + 1 tem ordem 1 e e´ uma relac¸a˜o
de recorreˆncia linear na˜o-homogeˆnea, f (n) = 1;
3. Ovais: an = 2an−1 + 2(n − 1) tem ordem 1 e e´ uma relac¸a˜o
de recorreˆncia linear na˜o-homogeˆnea, f (n) = 2(n − 1);
8 / 33
Resolvendo a relac¸a˜o de Fibonacci por suposic¸a˜o e
verificac¸a˜o
A relac¸a˜o de recorreˆncia e condic¸o˜es iniciais da relac¸a˜o de
Fibonacci, sa˜o dadas por{
Fn = Fn−1 + Fn−2
F0 = F1 = 1
Suposic¸a˜o: Fn = cαn, onde c e α sa˜o paraˆmetros introduzidos a
serem achados.
Verificac¸a˜o: cαn = cαn−1 + cαn−2 dividindo por cαn−2:
α2 = α+ 1
α2 − α− 1 = 0, enta˜o
α1 =
1 +
√
5
2
α2 =
1−√5
2
Observe que c pode ser qualquer coisa, mas α = 1±
√
5
2
Fn = c(
1+
√
5
2 )
n ou Fn = c(
1−√5
2 )
n
9 / 33
Teorema
Na verdade, qualquer combinac¸a˜o linear, isto e´, uma soma das 2
soluc¸o˜es cada uma delas multiplicadas por constantes, e´ tambe´m
uma soluc¸a˜o. Este e´ o resultado do teorema:
Se an = α
n
1 e an = α
n
2 sa˜o 2 soluc¸o˜es de uma recorreˆncia linear
an =
∑d
i=1 cian−i enta˜o an = k1α
n
1 + k2α
n
2 e´ tambe´m uma soluc¸a˜o,
onde k1 e k2 sa˜o constantes.
Prova: Temos que an =
∑d
i=1 cian−i . Queremos provar que
k1α
n
1 + k2α
n
2 e´ soluc¸a˜o de an.
Substituindo αn1 =
∑d
i=1 ciα
n−1
1 (1) e
αn2 =
∑d
i=1 ciα
n−1
2 (2)
Multiplicando (1) por k1, (2) por k2 e somando, temos:
k1α
n
1 + k2α
n
2 =
d∑
i=1
k1ciα
n−i
1 +
d∑
i=1
k2ciα
n−i
2 =
d∑
i=1
ci (k1α
n−i
1 + k2α
n−i
2 )
10 / 33
Continuac¸a˜o da relac¸a˜o de Fibonacci
Logo, pelo teorema anterior, temos:
(∗) Fn = k1
(
1 +
√
5
2
)n
+ k2
(
1−√5
2
)n
onde k1 e k2 sa˜o constantes.
Agora com as condic¸o˜es iniciais F0 = 1 e F1 = 1, temos o sistema
de 2 equac¸o˜es lineares e 2 inco´gnitas:{
F0 = k1 + k2 = 1
F1k1
(
1+
√
5
2
)
+ k2
(
1−√5
2
)
= 1
Resolvendo, encontramos k1 =
1+
√
5
2
√
5
e k2 =
√
5−1
2
√
5
. Logo,
substituindo em (∗), temos:
Fn =
1√
5
(
1 +
√
5
2
)n+1
− 1√
5
(
1−√5
2
)n+1
, n ≥ 0
11 / 33
Me´todo Geral para Recorreˆncias Lineares
Dada uma recorreˆncia linear homogeˆnea
an =
d∑
i=1
cian−i = c1an−1 + c2an−2 + · · ·+ cdan−d
Substituindo an = α
n na recorreˆncia:
αn = c1α
n−1 + c2αn−2 + · · ·+ cdαn−d
dividindo por αn−d
αd = c1α
d−1 + c2αd−2 + · · ·+ cd−1α+ cd
Rearrumando:
αd − c1αd−1 − c2αd−2 − · · · − cd−1α− cd = 0
Essa equac¸a˜o pe chamada equac¸a˜o caracter´ıstica da recorreˆncia.
12 / 33
Observac¸a˜o
Os coeficientes da equac¸a˜o caracter´ıstica sa˜o os mesmos da
recorreˆncia. Sabemos do Teorema Fundamental da A´lgebra que um
polinoˆmio de grau k, tem exatamente k ra´ızes, na˜o necessa´riamente
distintas. Sendo assim a equac¸a˜o caracter´ıstica tera´ d ra´ızes. A
soluc¸a˜o depende agora do fato das ra´ızes serem distintas ou na˜o.
Vamos ver primeiro, o caso simples, onde as ra´ızes sa˜o todas
distintas.
Se temos d condic¸o˜es de fronteira, enta˜o obtemos d equac¸o˜es
lineares com d inco´gnitas, ou seja, temos uma soluc¸a˜o u´nica
c1, c2, · · · , cd . Este e´ nosso pro´ximo resultado.
13 / 33
Caso simples: as ra´ızes sa˜o todas distintas
Se a equac¸a˜o caracter´ıstica tem d ra´ızes distintas r1, · · · , rd enta˜o
a soluc¸a˜o da recorreˆncia tem a forma:
an = k1r
n
1 + k2r
n
2 + · · ·+ kd rnd
As constantes ci dependem das condic¸o˜es de fronteira.
Obs.: As ra´ızes na˜o precisam ser reais, podem ser complexas.
Cada condic¸a˜o gera uma equac¸a˜o linear dessas constantes.
Suponha que temos a0 = b0, a1 = b1, · · · , ad−1 = bd−1. Essas
condic¸o˜es geram as equac¸o˜es lineares a seguir:
b0 = k1 + k2 + · · ·+ cd
b1 = k1r1 + k2r2 + · · ·+ kd rd
...
bd−1 = k1rd−11 + k2r2d − 1 + · · ·+ kd rd−1d
14 / 33
Exemplo
Exemplo: Resolva a relac¸a˜o de recorreˆncia an = an−1 + 2an−2
com n ≥ 3, a1 = 1 e a2 = 3.
Seja an = α
n, substituindo na equac¸a˜o, temos:
αn = αn−1 + 2αn−2
Dividindo por αn−2, temos a seguinte equac¸a˜o caracter´ıstica:
α2 − α− 2 = 0
(α+ 1)(α− 2) = 0 ra´ızes: −1, 2.
Soluc¸a˜o: c1(−1)n + c2(2n){
a1 = 1 = −c1 + 2c2
a2 = 3 = c1 + 4c2
c1 =
1
3 e c2 =
2
3
Logo,
an =
1
2
(−1)n + 2
3
2n ∀n ≥ 1
15 / 33
Exemplo
Resolva a relac¸a˜o de recorreˆncia an = an−1 + 2an−2 − 3an−3 com
n ≥ 0, a0 = 1, a1 = 2 e a2 = 0.
Soluc¸a˜o: Equac¸a˜o caracter´ıstica:
α3 − 2α2 − α+ 3 = (α2 − α− 2)(α− 1) = 0
ra´ızes: 1,−1, 2.
an = c11
n + c2(−1)n + c32n = c1+ c2(−1)n + c32n e´ soluc¸a˜o geral.
Precisamos encontrar c1, c2, c3 tais que,
a0 = 1 = c1 + c2 + c3
a1 = 2 = c1 − c2 + 2c3
a2 = 0 = c1 + c2 + 4c3
Enta˜o, c1 = 2, c2 = −23 e c3 = −13
Portanto,
an = 2− 2
3
(−1)n − 1
3
2n ∀n ≥ 0
16 / 33
Ra´ızes repetidas
Teorema: Se r e´ uma raiz de multiplicidade m da equac¸a˜o
caracter´ıstica de uma recorreˆncia, enta˜o rn, nrn, n2rn, · · · , nm−1rn
sa˜o tambe´m soluc¸o˜es da recorreˆncia.
Ex.: Suponha que temos uma equac¸a˜o caracter´ıstica de reocrreˆnciacom raiz r1 de multiplicidade 2, r2 de multiplicidade 1, r3 de
multiplicidade3, enta˜o a soluc¸a˜o tem a forma:
an = k1r
n
1 + k2nr
n
1︸ ︷︷ ︸
2
+ k3r
n
2︸︷︷︸
1
+ k4r
n
3 + k5nr
n
3 + k6n
2rn3︸ ︷︷ ︸
3
Como antes, as constantes dependem das condic¸o˜es de fronteira.
Obs.: Resolver recorreˆncias lineares e´ similar a resolver equac¸o˜es
diferenciais lineares.
17 / 33
Exemplo
Seja a relac¸a˜o de recorreˆncia com condic¸o˜es iniciais, dada:
an = an−1 + (an−1 − an−2)
a0 = 0 e a1 = 1
an = 2an−1 − an−2
an − 2an−1 + an−2 = 0 equac¸a˜o linear homogeˆnea
α2 − 2α+ 1 = 0⇒ (α− 1)2 = 0
α = 1 com multiplicidade 2.
18 / 33
Continuac¸a˜o
Logo, an = c1(1)
n + c2n(1)
n = c1 + c2n
Usando as condic¸o˜es de fronteira{
0 = c1 + c2(0)
1 = c1 + c2(1)
Enta˜o, c2 = 0 e c2 = 1.
Soluc¸a˜o: an = c1 + c2n = 0 + (1)n = n.
19 / 33
Equac¸o˜es Lineares na˜o Homogeˆneas
an − c1an−1 + c2an−2 + · · ·+ cdan−d = f (n)
ci , 1 ≤ i ≤ d sa˜o constantes.
Resoluc¸a˜o: (3 passos)
1. Substitua f (n) por 0 e resolva a equac¸a˜o de recorreˆncia
homogeˆnea obtida (ignore as condic¸o˜es iniciais). A soluc¸a˜o
obtida e´ chamada soluc¸a˜o homogeˆnea
2. Volte com f (n) e ache uma soluc¸a˜o para a equac¸a˜o (ignore as
condic¸o˜es iniciais). Essa soluc¸a˜o e´ chamada soluc¸a˜o particular.
3. Some a soluc¸a˜o homogeˆnea e a particular para obter uma
soluc¸a˜o geral. Enta˜o use as condic¸o˜es iniciais para determinar
as constantes envolvidas.
20 / 33
Exemplo
Seja a equac¸a˜o de recorreˆncia an − 4an−1 = 3n.
a1 = 1. Veja que f (n) = 3
n
Resoluc¸a˜o:
Passo 1: Resolver a relac¸a˜o recorreˆncia homogeˆnea
an − 4an−1 = 0
α− 4 = 0, enta˜o α = 4.
Soluc¸a˜o homogeˆnea: SH = c14
n
21 / 33
Continuac¸a˜o
Passo 2: Achar soluc¸a˜o particular
an − 4an−1 = 3n︸︷︷︸
f (n)
Em geral, para uma soluc¸a˜o particular, tenta-se uma soluc¸a˜o
de mesma natureza de f (n). Neste caso f (n) e´ exponencial.
Vamos tentar SP = an = c3
n, substituindo na equac¸a˜o:
c3n = 4c3n−1 + 3n, dividindo por 3n−1, temos:
3c = 4c + 3⇒ c = −3
Enta˜o SP = −3 · 3n = −3n+1
22 / 33
continuac¸a˜o
Passo 3: Soluc¸a˜o geral: an = SH + SP
an = c14
n − 3n+1
Agora, usamos as condic¸a˜o inicial: a1 = 1.
1 = c14− 31=1 = 4c1 − 9⇒ 4c1 − 9 = 1
4c1 = 10⇒ c1 = 5
2
an =
9
4
4n − 3n+1
23 / 33
Exemplo
Seja a equac¸a˜o de recorreˆncia an = 4an−1 − 4an−2 + n.{
a0 = 4
a1 = 7
Resoluc¸a˜o:
Passo 1: Resolver a relac¸a˜o de recorreˆncia homogeˆnea
an − 4an−1 + 4an−2 = 0
Equac¸a˜o caracter´ıstica α2 − 4α+ 4 = 0, enta˜o
(α− 2)2 = 0⇒ α = 2 com multiplicidade 2.
Soluc¸a˜o homogeˆnea: SH = c12
n + c2n2
n
24 / 33
Continuac¸a˜o
Passo 2: Achar a soluc¸a˜o particular . f (n) = n e´ uma equac¸a˜o do 1o
grau em n, enta˜o tentar SP = cn + d .
cn + d = 4(c(n − 1) + d)− 4(c(n − 2) + d) + n
cn + d = 4cn − 4c + 4d − 4cn + 8c − 4d + n
cn + d = 4c + n
(c − 1)n + (d − 4c) = 0
resolvendo essa equac¸a˜o:
c − 1 = 0⇒ c = 1
d − 4c = 0⇒ d = 4c = 4
SP = n + 4
25 / 33
Continuac¸a˜o
Passo 3: Soluc¸a˜o geral: an = SH + SP
an = c12
n + c2n2
n + (n + 4)
Agora usando as condic¸o˜es iniciais{
a0 = 4 = c1 + 4 ⇒ c1 = 0
a1 = 7 = c12 + c2 + 1 + 4 ⇒ c2 = 1
Soluc¸a˜o: an = n2n + n + 4 para n ≥ 0
26 / 33
Observac¸a˜o
Em geral, para achar uma soluc¸a˜o particular, tente uma soluc¸a˜o da
mesma natureza que f (n). Por exemplo, se f (n) e´ um polinoˆmio
de grau r enta˜o tente para a soluc¸a˜o particular um polinoˆmio de
grau r . Sena˜o funcionar, tente um polinoˆmio de grau r + 1 e assim
por diante.
Exemplo f (n) = n2, enta˜o tente SP = an
2 + bn + c .
Se f (n) e´ uma exponencial, enta˜o tente para soluc¸a˜o particular,
uma SP = exp de mesma natureza
Exemplo f (n) = 2n, enta˜o SP = a2
n.
27 / 33
Soluc¸a˜o da Torre de Hanoi por ra´ızes caracter´ısticas
{
Tn = 2Tn−1 + 1
T1 = 1
Tn = 2Tn−1 + 1
Passo 1: Homogeˆnea
Tn − 2Tn−1 = 0
α− 2 = 0⇒ α = 2
SH = A2
n
Passo 2: Particular
Tn − 2Tn−1 = 1
SP = A1. Substituindo, temos: A1 − 2A1 = 1⇒ A1 = −1
Portanto, SP = −1
28 / 33
Continuac¸a˜o
Passo 3: Soluc¸a˜o Geral: an = A2
n − 1 Condic¸a˜o inicial:
T1 = A2− 1⇒ 1 = 2A− 1⇒ A = 1
Soluc¸a˜o: Tn = 2
n − 1
29 / 33
Soluc¸a˜o do Problema das Ovais
{
an = an−1 + 2(n − 1)
a1 = 2
Passo 1: Soluc¸a˜o homogeˆnea
an − an−1 = 0
α− 1 = 0⇒ α = 1
SH = A1
n = A
30 / 33
Continuac¸a˜o
Passo 2: Soluc¸a˜o Particular
an − an−1 = 2(n − 1)︸ ︷︷ ︸
f (n)
SP = A1n + A2. Substituindo, temos:
A1n + A2 − [A1(n − 1) + A2] = 2n − 2
Simplificando, temos
A1n + A2 − A1n + A1 − A2 = 2n − 2⇒ A1 = 2n − 2
A1 + 0n = 2n − 2. Logo, A1 = −2 e 2 = 0, um absurdo, ou
seja, esta equac¸a˜o na˜o tem soluc¸a˜o.
31 / 33
Continuac¸a˜o
2a tentativa: Vamos tentar SP = Bn
2 + Cn + D
(Bn2 + Cn + D)− [B(n − 1)2 + C (n − 1) + D] = 2n − 2
Bn2 + Cn + D − B(n2 − 2n + 1)− C (n − 1)− D = 2n − 2
Simplificando, temos:
2Bn − B + C = 2n − 2
2Bn + (C − B) = 2n − 2
{
2B = 2 ⇒ B = 1
C − B = −2 ⇒ C − 1 = −2⇒ C = −1
Portanto, SP = n
2 − n + D. Como na˜o ha´ restric¸o˜es para D,
podemos escolher qualquer D. Por exemplo, D = 0.
SP = n
2 − n
32 / 33
Continuac¸a˜o
Passo 3: Soluc¸a˜o Geral: an = A+ n
2 − n Condic¸a˜o inicial:
2 = A+ 1− 1⇒ A = 2
Soluc¸a˜o: an = 2 + n
2 − n ou ainda, an = 2 + n(n − 1), para
n ≥ 1.
33 / 33