algorithm
Exposición de matrices

Exposición de matrices para resolver problemas de ejemplo

Encuentre f (n): n ^ésimo número de Fibonacci. El problema es bastante fácil cuando n es relativamente pequeño. Podemos usar la recursión simple, f(n) = f(n-1) + f(n-2) , o podemos usar el enfoque de programación dinámica para evitar el cálculo de la misma función una y otra vez. Pero, ¿qué harás si el problema dice: Dado 0 <n <10⁹, encuentra f (n) mod 999983? La programación dinámica fallará, entonces, ¿cómo abordamos este problema?

Primero veamos cómo la exponenciación matricial puede ayudar a representar una relación recursiva.

Requisitos previos:

• Dadas dos matrices, saber encontrar su producto. Además, dada la matriz de producto de dos matrices, y una de ellas, sabe cómo encontrar la otra matriz.
• Dada una matriz de tamaño d X d, saber cómo encontrar su n ^ésima potencia en O (d ³ log (n)).

Patrones:

Al principio necesitamos una relación recursiva y queremos encontrar una matriz M que pueda llevarnos al estado deseado desde un conjunto de estados ya conocidos. Supongamos que, conocemos los k estados de una relación de recurrencia dada y queremos encontrar el estado (k + 1) ^th . Sea M una matriz k X k , y construimos una matriz A: [k X 1] a partir de los estados conocidos de la relación de recurrencia, ahora queremos obtener una matriz B: [k X 1] que representará el conjunto de estados siguientes, es decir, MXA = B como se muestra a continuación:

       |  f(n)  |     | f(n+1) |
       | f(n-1) |     |  f(n)  |
   M X | f(n-2) |  =  | f(n-1) |
       | ...... |     | ...... |
       | f(n-k) |     |f(n-k+1)|

Entonces, si podemos diseñar M en consecuencia, ¡nuestro trabajo estará listo! La matriz se utilizará para representar la relación de recurrencia.

Tipo 1:
Comencemos con el más simple, f(n) = f(n-1) + f(n-2)
Obtenemos, f(n+1) = f(n) + f(n-1) .
Supongamos que sabemos f(n) y f(n-1) ; Queremos averiguar f(n+1) .
A partir de la situación mencionada anteriormente, la matriz A y la matriz B se pueden formar como se muestra a continuación:

 Matrix A          Matrix B

|  f(n)  |        | f(n+1) |
| f(n-1) |        |  f(n)  |

[Nota: la matriz A siempre se diseñará de tal manera que, todos los estados de los que depende f(n+1) , estarán presentes]
Ahora, necesitamos diseñar una matriz M 2X2 tal que satisfaga MXA = B como se indicó anteriormente.
El primer elemento de B es f(n+1) que en realidad es f(n) + f(n-1) . Para obtener esto, de la matriz A , necesitamos 1 X f (n) y 1 X f (n-1) . Así que la primera fila de M será [1 1] .

| 1   1 |  X  |  f(n)  |  =  | f(n+1) |
| ----- |     | f(n-1) |     | ------ |

[Nota: ----- significa que no estamos preocupados por este valor.]
De manera similar, el segundo elemento de B es f(n) que puede obtenerse simplemente tomando 1 X f (n) de A , por lo que la segunda fila de M es [1 0].

| ----- |  X  |  f(n)  |  =  | ------ |
| 1   0 |     | f(n-1) |     |  f(n)  |

Entonces conseguimos nuestra deseada 2 X 2 M de la matriz.

| 1   1 |  X  |  f(n)  |  =  | f(n+1) |
| 1   0 |     | f(n-1) |     |  f(n)  |

Estas matrices se derivan simplemente utilizando la multiplicación de matrices.

Tipo 2:

Hagámoslo un poco complejo: encuentre f(n) = a X f(n-1) + b X f(n-2) , donde a y b son constantes.
Esto nos dice que f(n+1) = a X f(n) + b X f(n-1) .
Hasta este punto, esto debe quedar claro que la dimensión de las matrices será igual al número de dependencias, es decir, en este ejemplo particular, nuevamente 2. Entonces, para A y B , podemos construir dos matrices de tamaño 2 X 1 :

Matrix A             Matrix B
|  f(n)  |          | f(n+1) |
| f(n-1) |          |  f(n)  |

Ahora para f(n+1) = a X f(n) + b X f(n-1) , necesitamos [a, b] en la primera fila de la matriz objetivo M. Y para el segundo elemento en B , es decir, f(n) ya tenemos eso en la matriz A , así que simplemente tomamos eso, lo que lleva a la segunda fila de la matriz M a [1 0]. Esta vez tenemos:

| a   b |  X  |  f(n)  |  =  | f(n+1) |
| 1   0 |     | f(n-1) |     |  f(n)  |

Bastante simple, ¿eh?

Tipo 3:

Si ha sobrevivido hasta esta etapa, ha envejecido mucho, ahora enfrentemos una relación un poco compleja: encontrar f(n) = a X f(n-1) + c X f(n-3) ?
Ups! Hace unos minutos, todo lo que vimos fueron estados contiguos, pero aquí falta el estado f (n-2) . ¿Ahora?

En realidad esto ya no es un problema, podemos convertir la relación de la siguiente manera: f(n) = a X f(n-1) + 0 X f(n-2) + c X f(n-3) , deduciendo f(n+1) = a X f(n) + 0 X f(n-1) + c X f(n-2) . Ahora, vemos que esto es en realidad una forma descrita en el Tipo 2. Así que aquí la matriz objetivo M será 3 X 3 , y los elementos son:

| a 0 c |     |  f(n)  |     | f(n+1) |
| 1 0 0 |  X  | f(n-1) |  =  |  f(n)  |
| 0 1 0 |     | f(n-2) |     | f(n-1) |

Estos se calculan de la misma manera que en el tipo 2, si le resulta difícil, pruébelo con lápiz y papel.

Tipo 4:

La vida se está volviendo compleja, y el Sr. Problema ahora te pide que encuentres f(n) = f(n-1) + f(n-2) + c donde c es cualquier constante.
Ahora, este es uno nuevo y todo lo que hemos visto en el pasado, después de la multiplicación, cada estado en A se transforma en su próximo estado en B.

f(n) = f(n-1) + f(n-2) + c
f(n+1) = f(n) + f(n-1) + c
f(n+2) = f(n+1) + f(n) + c
.................... so on

Entonces, normalmente no podemos hacerlo a través de la moda anterior, pero ¿qué tal si agregamos c como un estado:

      |  f(n)  |   | f(n+1) |
  M X | f(n-1) | = |  f(n)  |
      |    c   |   |    c   |

Ahora, no es mucho difícil diseñar M. Así es como se hace, pero no te olvides de verificar:

  | 1 1 1 |     |  f(n)  |     | f(n+1) |
  | 1 0 0 |  X  | f(n-1) |  =  |  f(n)  |
  | 0 0 1 |     |    c   |     |    c   |

Tipo 5:

Pongámoslo del todo: encuentre f(n) = a X f(n-1) + c X f(n-3) + d X f(n-4) + e . Vamos a dejarlo como un ejercicio para ti. Primero intenta averiguar los estados y la matriz M. Y comprueba si coincide con tu solución. También encuentra la matriz A y B.

| a 0 c d 1 |
| 1 0 0 0 0 |
| 0 1 0 0 0 |
| 0 0 1 0 0 |
| 0 0 0 0 1 |

Tipo 6:

A veces la recurrencia se da así:

f(n) = f(n-1)   -> if n is odd
f(n) = f(n-2)   -> if n is even

En breve:

f(n) = (n&1) X f(n-1) + (!(n&1)) X f(n-2)

Aquí, podemos dividir las funciones en la base de pares impares y mantener 2 matrices diferentes para ambas y calcularlas por separado.

Tipo 7:

¿Te sientes un poco demasiado seguro? Bien por usted. A veces es posible que tengamos que mantener más de una recurrencia, cuando estén interesados. Por ejemplo, deje que una recurrencia re; atopm sea:

g(n) = 2g(n-1) + 2g(n-2) + f(n)

Aquí, la recurrencia g (n) depende de f(n) y esto se puede calcular en la misma matriz pero de dimensiones aumentadas. A partir de estos, primero diseñemos las matrices A y B.

 Matrix A            Matrix B
|  g(n)  |          | g(n+1) |
| g(n-1) |          |  g(n)  |
| f(n+1) |          | f(n+2) |
|  f(n)  |          | f(n+1) |

Aquí, g(n+1) = 2g(n-1) + f(n+1) and f(n+2) = 2f(n+1) + 2f(n) . Ahora, utilizando los procesos mencionados anteriormente, podemos encontrar que la matriz objetivo M es:

| 2 2 1 0 |
| 1 0 0 0 |
| 0 0 2 2 |
| 0 0 1 0 |

Por lo tanto, estas son las categorías básicas de relaciones de recurrencia que se utilizan para resolver con esta técnica simple.