¿Cómo funciona la multiplicación de matrices para obtener el enésimo número de Fibonacci?

Answer 1

Necesitas usar la ecuación básica de la secuencia de Fibonacci.

[matemáticas] F (n) = F (n – 1) + F (n – 2) [/ matemáticas]

[matemáticas] F (n – 1) = F (n – 1) [/ matemáticas]

confundido .. por qué usar un hecho obvio de que [matemáticas] F (n-1) = F (n-1) [/ matemáticas], bueno, pronto lo verás.

[matemáticas] \ begin {bmatrix} F (n) \\ F (n-1) \ end {bmatrix} = \ begin {bmatrix} 1 & 1 \\ 1 & 0 \ end {bmatrix} \ begin {bmatrix} F (n-1 ) \\ F (n-2) \ end {bmatrix} [/ math]

Esto parece correcto, correcto. Pero si representamos [matemática] A (n) = [/ matemática] [matemática] \ begin {bmatrix} F (n) \\ F (n-1) \ end {bmatrix} [/ math], entonces podemos ver que [matemáticas] A (n) = C * A (n – 1) [/ matemáticas]

que ahora es una recurrencia simple en la que cada término puede ser encontrado por:

[matemáticas] A (1) = C * A (0) \; base \; case [/ math]

[matemáticas] A (2) = C * A (1) = C * (C * A (0)) = C ^ 2 * A (0) [/ matemáticas], o

[matemáticas] A (n) = C ^ n * A (0) [/ matemáticas]

la enésima potencia de la matriz se puede encontrar utilizando la exponenciación O (logN)

Esto se puede generalizar a [matemáticas] F (n) = aF (n – 1) + bF (n-2) + c [/ matemáticas]

use 2 ecuaciones auxiliares, [matemáticas] F (n-1) = F (n-1) \; y\; c = c [/ matemáticas]

Formando la ecuación, [matemáticas] \ begin {bmatrix} F (n) \\ F (n-1) \\ c \ end {bmatrix} = \ begin {bmatrix} a & b & c \\ 1 & 0 & 0 \\ 0 & 0 & 1 \ end {bmatrix} \ begin {bmatrix} F (n-1) \\ F (n-2) \\ c \ end {bmatrix} [/ math]

Creo que entiendes el punto.

Answer 2

La fórmula recursiva para la serie de Fibonacci es [matemática] f (n + 1 [/ matemática] [matemática]) = f (n) + f (n-1) [/ matemática]

y [matemáticas] f (n) = 1 * f (n) [/ matemáticas]

Ahora, podemos usar la matriz para calcular las dos ecuaciones anteriores simultáneamente:

me gusta

[matemáticas] \ left [\ begin {array} {c} F_ {n + 1} \\ F_n \ end {array} \ right] = \ left [\ begin {array} {ccc} F_n & + & F_ {n -1} \\ F_n & & \ end {array} \ right] [/ math]

Que podemos traducir a:

[matemáticas] \ left [\ begin {array} {c} F_ {n + 1} \\ F_n \ end {array} \ right] = \ left [\ begin {array} {cc} 1 & 1 \\ 1 & 0 \ end {array} \ right] \ left [\ begin {array} {c} F_n \\ F_ {n-1} \ end {array} \ right] [/ math]

Los casos base para las series de Fibonacci son f (0) = 0 yf (1) = 1.

podemos simplificar la ecuación recursiva como

[matemáticas] \ left [\ begin {array} {c} F_ {n + 1} \\ F_n \ end {array} \ right] = \ left [\ begin {array} {cc} 1 & 1 \\ 1 & 0 \ end {array} \ right] ^ n \ left [\ begin {array} {c} 1 \\ 0 \ end {array} \ right] [/ math]