algorithm
Matrixvermenigvuldiging

Matrixvermenigvuldiging om voorbeeldproblemen op te lossen

Zoek f (n): n ^het Fibonacci-nummer. Het probleem is vrij eenvoudig wanneer n relatief klein is. We kunnen eenvoudige recursie gebruiken, f(n) = f(n-1) + f(n-2) , of we kunnen een dynamische programmeerbenadering gebruiken om de berekening van dezelfde functie steeds opnieuw te vermijden. Maar wat gaat u doen als het probleem zegt: Gegeven 0 <n <10⁹, vind f (n) mod 999983? Dynamisch programmeren mislukt, dus hoe pakken we dit probleem aan?

Laten we eerst kijken hoe matrix-exponentiatie kan helpen om een recursieve relatie weer te geven.

Vereisten:

• Gegeven twee matrices, weet hoe ze hun product kunnen vinden. Verder, gezien de productmatrix van twee matrices, en een daarvan, weet hoe de andere matrix te vinden.
• Gegeven een matrix met de grootte d X d , weet je hoe je de ^nde macht in O (d ³ log (n)) kunt vinden .

patronen:

In eerste instantie hebben we een recursieve relatie nodig en we willen een matrix M vinden die ons naar de gewenste toestand kan leiden uit een reeks reeds bekende toestanden. Laten we aannemen dat we de k- toestanden van een bepaalde herhalingsrelatie kennen en we willen de (k + 1) ^e- toestand vinden. Laat M een k X k- matrix zijn en we bouwen een matrix A: [k X 1] op basis van de bekende toestanden van de herhalingsrelatie, nu willen we een matrix B krijgen: [k X 1] die de verzameling van volgende toestanden, dwz MXA = B zoals hieronder weergegeven:

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

Dus als we M dienovereenkomstig kunnen ontwerpen, is ons werk gedaan! De matrix wordt vervolgens gebruikt om de herhalingsrelatie weer te geven.

Type 1:
Laten we beginnen met de eenvoudigste, f(n) = f(n-1) + f(n-2)
We krijgen f(n+1) = f(n) + f(n-1) .
Laten we aannemen dat we f(n) en f(n-1) ; We willen f(n+1) ontdekken.
Uit de hierboven genoemde situatie kunnen matrix A en matrix B worden gevormd zoals hieronder getoond:

 Matrix A          Matrix B

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

[Opmerking: Matrix A wordt altijd zo ontworpen dat elke status waarvan f(n+1) afhankelijk is, aanwezig zal zijn]
Nu moeten we een 2X2- matrix M zodanig ontwerpen dat deze voldoet aan MXA = B zoals hierboven vermeld.
Het eerste element van B is f(n+1) wat eigenlijk f(n) + f(n-1) . Om dit uit matrix A te krijgen , hebben we 1 X f (n) en 1 X f (n-1) nodig . Dus de eerste rij van M is [1 1] .

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

[Opmerking: ----- betekent dat we ons geen zorgen maken over deze waarde.]
Op dezelfde manier is het 2e item van B f(n) die je kunt krijgen door eenvoudigweg 1 X f (n) van A te nemen , dus de 2e rij van M is [1 0].

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

Dan krijgen we onze gewenste 2 X 2 matrix M.

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

Deze matrices worden eenvoudig afgeleid met behulp van matrixvermenigvuldiging.

Type 2:

Laten we het een beetje complex maken: zoek f(n) = a X f(n-1) + b X f(n-2) , waar a en b constanten zijn.
Dit vertelt ons, f(n+1) = a X f(n) + b X f(n-1) .
Tot dusverre moet dit duidelijk zijn dat de dimensie van de matrices gelijk zal zijn aan het aantal afhankelijkheden, dat wil zeggen in dit specifieke voorbeeld opnieuw 2. Dus voor A en B kunnen we twee matrices van maat 2 X 1 bouwen :

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

Nu voor f(n+1) = a X f(n) + b X f(n-1) , hebben we [a, b] nodig in de eerste rij van objectieve matrix M. En voor het 2e item in B , dat wil zeggen f(n) hebben we dat al in matrix A , dus nemen we dat, wat leidt, de 2e rij van de matrix M naar [1 0]. Deze keer krijgen we:

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

Vrij simpel, toch?

Type 3:

Als je dit stadium hebt overleefd, ben je veel ouder geworden, laten we nu een beetje complexe relatie onder ogen zien: f(n) = a X f(n-1) + c X f(n-3) ?
Ooops! Een paar minuten geleden zagen we alleen aaneengesloten toestanden, maar hier ontbreekt de toestand f (n-2) . Nu?

Eigenlijk is dit geen probleem meer, we kunnen de relatie als volgt omzetten: f(n) = a X f(n-1) + 0 X f(n-2) + c X f(n-3) , afleidend f(n+1) = a X f(n) + 0 X f(n-1) + c X f(n-2) . Nu zien we dat dit in feite een vorm is die wordt beschreven in Type 2. Dus hier zal de objectieve matrix M 3 X 3 zijn en de elementen zijn:

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

Deze worden op dezelfde manier berekend als type 2, als u het moeilijk vindt, probeer het dan op pen en papier.

Type 4:

Het leven wordt complex als de hel, en meneer, Probleem vraagt je nu om f(n) = f(n-1) + f(n-2) + c waar c een constante is.
Nu is dit een nieuwe en alles wat we in het verleden hebben gezien, na de vermenigvuldiging, transformeert elke toestand in A naar zijn volgende toestand 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

Dus normaal gesproken kunnen we het niet op de vorige manier krijgen, maar hoe zit het met het toevoegen van c als staat:

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

Nu is het niet zo moeilijk om M te ontwerpen. Dit is hoe het is gedaan, maar vergeet niet te verifiëren:

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

Type 5:

Laten we het helemaal samenvatten: zoek f(n) = a X f(n-1) + c X f(n-3) + d X f(n-4) + e . Laten we het als een oefening voor je laten. Probeer eerst de toestanden en matrix M te achterhalen. En controleer of deze overeenkomt met uw oplossing. Vind ook matrix A en 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:

Soms wordt de herhaling als volgt gegeven:

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

In het kort:

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

Hier kunnen we de functies op basis van oneven even splitsen en 2 verschillende matrix voor beide behouden en ze afzonderlijk berekenen.

Type 7:

Voel je je iets te zelfverzekerd? Goed voor je. Soms moeten we mogelijk meer dan één herhaling handhaven, als ze geïnteresseerd zijn. Laat bijvoorbeeld een herhaling opnieuw; atopm zijn:

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

Hier is herhaling g (n) afhankelijk van f(n) en dit kan worden berekend in dezelfde matrix maar met verhoogde dimensies. Van deze laten we eerst de matrices A en B ontwerpen.

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

Hier, g(n+1) = 2g(n-1) + f(n+1) and f(n+2) = 2f(n+1) + 2f(n) . Nu kunnen we met behulp van de hierboven genoemde processen de objectieve matrix M vinden als:

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

Dit zijn dus de basiscategorieën van terugkerende relaties die worden gebruikt om deze eenvoudige techniek op te lossen.