algorithm
Matrix Exponentiation

Esponenziazione della matrice per risolvere problemi di esempio

Trova f (n): ^n-esimo numero di Fibonacci. Il problema è abbastanza semplice quando n è relativamente piccolo. Possiamo usare la ricorsione semplice, f(n) = f(n-1) + f(n-2) , oppure possiamo usare un approccio di programmazione dinamica per evitare il calcolo della stessa funzione più e più volte. Ma cosa farai se il problema dice, Dato 0 <n <10⁹, trova f (n) mod 999983? La programmazione dinamica fallirà, quindi come affrontiamo questo problema?

Per prima cosa vediamo come l'esponenziazione della matrice può aiutare a rappresentare la relazione ricorsiva.

Prerequisiti:

• Date due matrici, sai come trovare il loro prodotto. Inoltre, data la matrice di prodotto di due matrici, e una di esse, sai come trovare l'altra matrice.
• Data una matrice di dimensione d X d, sapere come trovare il suo n ^esima potenza a O (D ³ log (n)).

Patterns:

All'inizio abbiamo bisogno di una relazione ricorsiva e vogliamo trovare una matrice M che possa portarci allo stato desiderato da un insieme di stati già noti. Supponiamo che, conosciamo gli stati k di una data relazione di ricorrenza e vogliamo trovare lo stato (k + 1) ^th . Sia M una matrice k X k , e costruiamo una matrice A: [k X 1] dagli stati noti della relazione di ricorrenza, ora vogliamo ottenere una matrice B: [k X 1] che rappresenterà l'insieme di prossimi stati, cioè MXA = B come mostrato di seguito:

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

Quindi, se possiamo progettare M di conseguenza, il nostro lavoro sarà fatto! La matrice verrà quindi utilizzata per rappresentare la relazione di ricorrenza.

Tipo 1:
Iniziamo con il più semplice, f(n) = f(n-1) + f(n-2)
Otteniamo, f(n+1) = f(n) + f(n-1) .
Supponiamo che conosciamo f(n) ed f(n-1) ; Vogliamo scoprire f(n+1) .
Dalla situazione sopra riportata, la matrice A e la matrice B possono essere formate come mostrato di seguito:

 Matrix A          Matrix B

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

[Nota: la matrice A sarà sempre progettata in modo tale che, ogni stato su cui f(n+1) dipende, sarà presente]
Ora, abbiamo bisogno di progettare una matrice M 2X tale che soddisfi MXA = B come detto sopra.
Il primo elemento di B è f(n+1) che è in realtà f(n) + f(n-1) . Per ottenere questo, dalla matrice A , abbiamo bisogno, 1 X f (n) e 1 X f (n-1) . Quindi la prima riga di M sarà [1 1] .

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

[Nota: ----- significa che non siamo preoccupati per questo valore.]
Allo stesso modo, il secondo elemento di B è f(n) che può essere ottenuto semplicemente prendendo 1 X f (n) da A , quindi la 2a riga di M è [1 0].

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

Allora otteniamo la nostra desiderata 2 X 2 matrice M.

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

Queste matrici sono semplicemente derivate usando la moltiplicazione della matrice.

Tipo 2:

Facciamolo un po 'complesso: trova f(n) = a X f(n-1) + b X f(n-2) , dove a e b sono costanti.
Questo ci dice, f(n+1) = a X f(n) + b X f(n-1) .
A questo punto, dovrebbe essere chiaro che la dimensione delle matrici sarà uguale al numero di dipendenze, cioè in questo particolare esempio, ancora 2. Quindi per A e B , possiamo costruire due matrici di dimensione 2 X 1 :

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

Ora per f(n+1) = a X f(n) + b X f(n-1) , abbiamo bisogno di [a, b] nella prima riga della matrice obiettiva M. E per il secondo elemento in B , cioè f(n) abbiamo già nella matrice A , quindi prendiamo semplicemente quello che conduce, la 2a riga della matrice M a [1 0]. Questa volta otteniamo:

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

Piuttosto semplice, eh?

Tipo 3:

Se sei sopravvissuto fino a questo stadio, sei cresciuto molto più vecchio, ora affrontiamo una relazione un po 'complessa: trova f(n) = a X f(n-1) + c X f(n-3) ?
Ops! Pochi minuti fa, tutto ciò che abbiamo visto erano stati contigui, ma qui manca lo stato f (n-2) . Adesso?

In realtà questo non è più un problema, possiamo convertire la relazione come segue: f(n) = a X f(n-1) + 0 X f(n-2) + c X f(n-3) , deducendo f(n+1) = a X f(n) + 0 X f(n-1) + c X f(n-2) . Ora, vediamo che questa è in realtà una forma descritta nel Tipo 2. Quindi qui la matrice obiettivo M sarà 3 X 3 , e gli elementi sono:

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

Questi sono calcolati allo stesso modo del tipo 2, se lo trovi difficile, provalo su carta e penna.

Tipo 4:

La vita diventa complessa come l'inferno, e Mr, Problema ora ti chiede di trovare f(n) = f(n-1) + f(n-2) + c dove c è una qualsiasi costante.
Ora questo è nuovo e tutto ciò che abbiamo visto in passato, dopo la moltiplicazione, ogni stato in A si trasforma nel suo stato successivo in 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

Quindi, normalmente non possiamo ottenere attraverso la moda precedente, ma che ne dici di aggiungere c come stato:

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

Ora, non è molto difficile da progettare M. Ecco come è fatto, ma non dimenticare di verificare:

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

Tipo 5:

Mettiamola del tutto: trova f(n) = a X f(n-1) + c X f(n-3) + d X f(n-4) + e . Lascia che sia un esercizio per te. Prima prova a scoprire gli stati e la matrice M. E controlla se corrisponde alla tua soluzione. Trova anche la matrice A e 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 volte la ricorrenza viene data in questo modo:

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

In breve:

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

Qui, possiamo dividere le funzioni in base a pari dispari e mantenere 2 matrici diverse per entrambe e calcolarle separatamente.

Tipo 7:

Ti senti poco sicuro di te? Buon per te. A volte potremmo aver bisogno di mantenere più di una ricorrenza, dove sono interessati. Ad esempio, lascia che una ricorrenza sia; atopm essere:

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

Qui, la recidiva g (n) dipende da f(n) e questo può essere calcolato nella stessa matrice ma di dimensioni maggiori. Da questi iniziamo a disegnare le matrici A e 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) |

Qui, g(n+1) = 2g(n-1) + f(n+1) and f(n+2) = 2f(n+1) + 2f(n) . Ora, usando i processi sopra indicati, possiamo trovare la matrice obiettiva M come:

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

Quindi, queste sono le categorie di base delle relazioni di ricorrenza che vengono utilizzate per risolvere questa semplice tecnica.