Teoria de números/Eficiência do algoritmo de Euclides: diferenças entre revisões
| [edição não verificada] | [edição não verificada] |
Conteúdo apagado Conteúdo adicionado
demonstração: Fórmula de Binet (começo) |
Demonstração (continuando...) |
||
Linha 256:
Neste ponto, recorre-se à [[Álgebra linear]], para obter um jeito simples de calcular o produto acima.
Se puder ser escrito
:<math>\begin{bmatrix} 1 \\ 0 \end{bmatrix} = \alpha v+\alpha'v'\,\!</math>, com <math>v\,\!</math> e <math>v'\,\!</math> sendo auto-vetores de <math>Q\,\!</math>, ou seja, vetores não nulos tais que <math>Qv = \lambda_1 v\,\!</math> e <math>Qv' = \lambda_2 v'\,\!</math>, será possível obter:
:<math>\begin{bmatrix} F_{n+1} \\ F_{n} \end{bmatrix} = Q^n(\alpha v + \alpha' v') = \alpha (Q^n v) + \alpha' (Q^n v') = \alpha (\lambda_1^n v) + \alpha' (\lambda_2^n v')\,\!</math>
A partir daí será bastante simples conseguir a fórmula explicita para <math>F_n\,\!</math> (a segunda componente do vetor à esquerda), pois <math>v, v', \alpha, \alpha', \lambda_1, \lambda_2\,\!</math> seriam constantes.
É, portanto, necessário determinar essas constantes, a começar pelos auto-valores de <math>Q\,\!</math>. Tem-se:
:<math>\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} x \\ y \end{bmatrix} = \lambda \begin{bmatrix} x \\ y \end{bmatrix} \Leftrightarrow \left\{\begin{matrix}
x & + & y & = & \lambda x\\
x & & & = & \lambda y
\end{matrix}\right.\,\!</math>
Logo <math>\lambda y + y = \lambda^2 y\,\!</math>, ou seja, <math>(\lambda^2 -\lambda - 1)\cdot y = 0\,\!</math>
Assim, <math>y=0\,\!</math> (que implica <math>x=0\,\!</math>) ou <math>\lambda^2 -\lambda - 1 = 0\,\!</math>. O primeiro caso não é de interesse, pois auto-vetores não são nulos.
Note que a equação acima possui duas raízes:
* <math>\lambda_1 = \varphi = \frac{1 + \sqrt{5}}{2}\,\!</math>
* <math>\lambda_2 = \hat{\varphi} = \frac{1 - \sqrt{5}}{2}\,\!</math>
Além disso, se <math>\lambda\,\!</math> é raiz da equação, então para cada <math>y\not = 0\,\!</math>, o vetor
:<math>\begin{bmatrix} \lambda y \\ y \end{bmatrix} = y \begin{bmatrix} \lambda \\ 1 \end{bmatrix}\,\!</math> é um auto-vetor de <math>Q\,\!</math>.
Em particular, se <math>y=1\,\!</math>, os auto-vetores correspondentes a cada raiz da equação quadrática são:
* <math>v = \begin{bmatrix} \varphi \\ 1 \end{bmatrix}\,\!</math>
* <math>v'= \begin{bmatrix} \hat{\varphi} \\ 1 \end{bmatrix}\,\!</math>
De modo que <math>Qv = \varphi v\,\!</math> e <math>Qv' = \hat{\varphi} v'\,\!</math>
== Exercícios ==
# Verifique, utilizando o princípio de indução, que:
# Escreva outra demonstração para a fórmula de Binet, utilizando o princípio de indução.
Por enquanto, não há muitos exercícios sobre este capítulo. O leitor está convidado a adicionar mais ítens a essa seção, para ajudar a melhorar o texto.
[[Categoria:
| |||