31
edits
Changes
Técnicas Avançadas de Contagem (view source)
Revision as of 00:02, 30 November 2015
, 00:02, 30 November 2015no edit summary
RecSol2 := proc(a, b, u, v)
local evals, S, alpha, beta, ans , n;
Resolve-se a equação característica
evals := solve(x^2 - a * x - b = 0, x);
Depois, resolve-se o sistema de equações lineares
S := solve(alpha * evals[1] + beta * evals[2] = u,
alpha * evals[1]^2 + beta * evals[2]^2 = v,
alpha,beta);
ans := subs(S,alpha*evals[1]^n + beta*evals[2]^n);
RETURN( unapply( ans , n ) );
end:
Paraobservar como funciona, iremos tentar alguns casos de teste. Paraconstruir uma função para calcular a sequencia Fibonacci chamamos nosso novo procedimento:
f := RecSol2(1,1,1,1,5);
O procedimento resultante ode ser usado para calcular o termo geral da sequencia Fibonacci.
f(n);
Da mesma forma, os primeiros cinco números Fibonacci podem ser calculados da seguinte forma:
seq(simplify(f(n)), n = 1..10);
Agora apresentamos uma resolução que pode lidar com o caso de raízes repetidas.
Antes de olharmos para a nova versão do RecSol2, vamos olhar para um exemplo envolvendo uma relação de recorrência com um valor double próprio (raiz de seu polinômio característico). A relação de recorrência
<math> r_} {n = 4 r_ {N-1} - 4 r_ {N-2} </math>
tem a equação característica
char_eqn := x^2 - 4 * x + 4 = 0;
com eigenvalues?????
evals := [solve(char_eqn, x)];
No geral, para testar um eigenvalue repetido, que é o caso para este exemplo, apenas testamos se
evalb(evals[1] = evals[2]);
(Nota: Nós não requeremos o uso de EVALB em uma instrução condicional já que expressões são automaticamente avaliados como booleans.) Se chamarmos a raiz dupla (2 neste caso) <math> \ lambda </math>, então a relação de recorrência tem a solução explícita
<math> r_{n} = \alpha \lambda^{n} + n \beta \lambda^{n} </math>
para todos os positivos inteiros n, e para algumas constantes <math> \alpha </math> and <math> \beta </math>. Assumir as condições iniciais de <math> r_{1} = 1 and r_{2} = 4 </math>, o conjunto S de equações a resolver é:
S := alpha * evals[1] + beta * evals[2] = 1,
alpha * evals[1]^2 + 2* beta * evals[2]^2 = 4;
Como antes, para obter as soluções, digitamos:
rsols := solve(S, alpha, beta);
É neste ponto que a diferença com o caso de raizes distintas aparece. O nth termo da sequencia, quando á um double eigenvalue, é dado ṕor:
subs(rsols , alpha * evals[1]^n + n * beta * evals[1]^n );
Os passos feitos neste exemplo são bem gerais Um procedimento geral para resolver uma recorrência de dois termos da forma r(n) = a r(n-1) + b r(n-2), com os valors iniciais values r(1) = u and r(2) = v é:
RecSolver2 := proc(a,b,u,v)
local ans, evals, S, alpha, beta, rsols, n;
resolve a equação característica
evals := solve(x^2 - a * x - b = 0, x);
resolve o sistema de equações lineares
S := alpha * evals[1] + beta * evals[2] = u,
alpha * evals[1]^2 + beta * evals[2]^2 = v;
rsols := solve(S, alpha, beta);
if evals[1] = evals[2] then # repeated roots
ans := subs(rsols,alpha*evals[1]^n + beta*n*evals[1]^n);
else
ans := subs(rsols,alpha*evals[1]^n + beta*evals[2]^n );
fi;
RETURN( unapply(ans , n ) );
end: