algorithm
Exponentiation Matricielle

Exponentiation de matrice pour résoudre des problèmes d'exemple

Trouver f (n): n ^ème numéro de Fibonacci. Le problème est assez facile quand n est relativement petit. Nous pouvons utiliser la récursivité simple, f(n) = f(n-1) + f(n-2) , ou nous pouvons utiliser l'approche de programmation dynamique pour éviter le calcul de la même fonction encore et encore. Mais que ferez-vous si le problème indique: Compte tenu de 0 <n <10 find, recherchez f (n) mod 999983? La programmation dynamique échouera, alors comment pouvons-nous résoudre ce problème?

Voyons d'abord comment l'exponentiation de la matrice peut aider à représenter une relation récursive.

Conditions préalables:

• Compte tenu de deux matrices, sachez trouver leur produit. En outre, sachez que la matrice de produit de deux matrices et l’une d’elles permettent de trouver l’autre matrice.
• Étant donné une matrice de taille d X d , sachez trouver sa n ^e puissance dans O (d ³ log (n)) .

Motifs:

Au début, nous avons besoin d'une relation récursive et nous voulons trouver une matrice M qui peut nous conduire à l'état souhaité à partir d'un ensemble d'états déjà connus. Supposons que nous connaissions les k états d'une relation de récurrence donnée et que nous voulons trouver le (k + 1) ^ème état. Soit M une matrice k X k , et nous construisons une matrice A: [k X 1] à partir des états connus de la relation de récurrence, nous voulons maintenant obtenir une matrice B: [k X 1] qui représentera l'ensemble des états suivants, c.-à-d. MXA = B comme indiqué ci-dessous:

       |  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)|

Donc, si nous pouvons concevoir M en conséquence, notre travail sera fait! La matrice sera alors utilisée pour représenter la relation de récurrence.

Type 1:
Commençons par le plus simple, f(n) = f(n-1) + f(n-2)
On obtient, f(n+1) = f(n) + f(n-1) .
Supposons que nous connaissions f(n) et f(n-1) ; Nous voulons découvrir f(n+1) .
A partir de la situation indiquée ci-dessus, la matrice A et la matrice B peuvent être formées comme indiqué ci-dessous:

 Matrix A          Matrix B

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

[Note: la matrice A sera toujours conçue de telle sorte que chaque état dont dépend f(n+1) sera présent]
Maintenant, nous devons concevoir une matrice 2X2 M telle qu'elle satisfasse à MXA = B comme indiqué ci-dessus.
Le premier élément de B est f(n+1) qui est en fait f(n) + f(n-1) . Pour obtenir ceci, à partir de la matrice A , nous avons besoin de 1 X f (n) et 1 X f (n-1) . La première ligne de M sera donc [1 1] .

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

[Note: ----- signifie que nous ne sommes pas concernés par cette valeur.]
De même, le deuxième élément de B est f(n) qui peut être obtenu en prenant simplement 1 X f (n) de A , donc la 2ème ligne de M est [1 0].

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

Ensuite , nous obtenons notre 2 X 2 désiré matrice M.

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

Ces matrices sont simplement dérivées à l'aide de la multiplication matricielle.

Type 2:

Rendons-le un peu complexe: trouver f(n) = a X f(n-1) + b X f(n-2) , où a et b sont des constantes.
Cela nous dit, f(n+1) = a X f(n) + b X f(n-1) .
A ce stade, il convient de préciser que la dimension des matrices sera égale au nombre de dépendances, c’est-à-dire dans cet exemple, à nouveau 2. Ainsi, pour A et B , nous pouvons construire deux matrices de taille 2 X 1 :

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

Maintenant, pour f(n+1) = a X f(n) + b X f(n-1) , nous avons besoin de [a, b] dans la première ligne de la matrice d’objectifs M. Et pour le 2ème élément de B , c'est-à-dire f(n) nous avons déjà cela dans la matrice A , donc nous prenons cela, ce qui conduit à la 2ème ligne de la matrice M à [1 0]. Cette fois nous obtenons:

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

Assez simple, hein?

Type 3:

Si vous avez survécu jusqu'à ce stade, vous êtes devenu beaucoup plus vieux, maintenant nous sommes confrontés à une relation un peu complexe: find f(n) = a X f(n-1) + c X f(n-3) ?
Oups! Il y a quelques minutes, nous n'avons vu que des états contigus, mais ici, l'état f (n-2) est absent. À présent?

En fait, ce n'est plus un problème, nous pouvons convertir la relation comme suit: f(n) = a X f(n-1) + 0 X f(n-2) + c X f(n-3) , déduisant f(n+1) = a X f(n) + 0 X f(n-1) + c X f(n-2) . Maintenant, nous voyons que c'est en fait une forme décrite dans le type 2. Donc ici la matrice d'objectifs M sera 3 X 3 et les éléments sont:

| 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) |

Celles-ci sont calculées de la même manière que le type 2, si vous trouvez cela difficile, essayez-le sur un stylo et du papier.

Type 4:

La vie devient complexe en enfer, et Mr, Problem vous demande maintenant de trouver f(n) = f(n-1) + f(n-2) + c où c est une constante.
Maintenant, c'est un nouveau et tout ce que nous avons vu dans le passé, après la multiplication, chaque état dans A se transforme en son état suivant dans 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

Donc, normalement, nous ne pouvons pas passer à travers la mode précédente, mais que diriez-vous d'ajouter c comme un état:

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

Maintenant, il n'est pas très difficile de concevoir M. Voici comment faire, mais n'oubliez pas de vérifier:

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

Type 5:

Disons-le simplement: trouver f(n) = a X f(n-1) + c X f(n-3) + d X f(n-4) + e . Laissons-le comme un exercice pour vous. Essayez d'abord de trouver les états et la matrice M. Et vérifiez si cela correspond à votre solution. Trouvez également les matrices A et 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 |

Type 6:

Parfois, la récurrence est donnée comme ceci:

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

En bref:

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

Ici, nous pouvons diviser les fonctions dans la base de pair impair et conserver 2 matrices différentes pour les deux et les calculer séparément.

Type 7:

Se sentir un peu trop confiant? Bien pour vous. Parfois, il peut être nécessaire de maintenir plusieurs récurrences, là où cela les intéresse. Par exemple, laissez une récurrence être:

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

Ici, la récurrence g (n) dépend de f(n) et celle-ci peut être calculée dans la même matrice mais de dimensions accrues. À partir de cela, commençons par concevoir les matrices A et 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) |

Ici, g(n+1) = 2g(n-1) + f(n+1) and f(n+2) = 2f(n+1) + 2f(n) . Maintenant, en utilisant les processus indiqués ci-dessus, nous pouvons trouver que la matrice d'objectifs M est:

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

Donc, ce sont les catégories de base des relations de récurrence qui sont utilisées pour résoudre par cette technique simple.