algorithm
Matrix-Exponentiation

Matrixexponentiation zur Lösung von Beispielproblemen

Finde f (n): ^nte Fibonacci-Nummer. Das Problem ist ziemlich einfach, wenn n relativ klein ist. Wir können die einfache Rekursion verwenden, f(n) = f(n-1) + f(n-2) , oder wir können einen dynamischen Programmieransatz verwenden, um die Berechnung derselben Funktion immer wieder zu vermeiden. Aber was werden Sie tun, wenn das Problem lautet: Gegeben 0 <n <10, finden Sie f (n) mod 999983? Dynamische Programmierung wird fehlschlagen, wie gehen wir dieses Problem an?

Sehen wir uns zunächst an, wie Matrix-Exponentiation helfen kann, rekursive Beziehungen darzustellen.

Voraussetzungen:

• Wenn Sie zwei Matrizen verwenden, wissen Sie, wie Sie ihr Produkt finden. Außerdem wissen die Produktmatrix zweier Matrizen und eine davon, wie sie die andere Matrix finden können.
• Mit einer Matrix der Größe d X d wissen Sie, wie Sie die n- ^te Potenz in O (d ³ log (n)) finden .

Muster:

Zunächst benötigen wir eine rekursive Beziehung und wollen eine Matrix M finden, die uns aus einer Menge bereits bekannter Zustände in den gewünschten Zustand führen kann. Nehmen wir an, wir kennen die k Zustände einer gegebenen Rekursionsbeziehung und wollen den (k + 1) ^-ten Zustand finden. Sei M eine k X k -Matrix, und wir bauen eine Matrix A: [k X 1] aus den bekannten Zuständen der Wiederholungsbeziehung auf, jetzt wollen wir eine Matrix B: [k X 1] erhalten, die die Menge von darstellt nächste Zustände, dh MXA = B wie unten gezeigt:

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

Wenn wir also M entsprechend gestalten können, ist unsere Arbeit erledigt! Die Matrix wird dann zur Darstellung der Wiederholungsbeziehung verwendet.

Typ 1:
Beginnen wir mit dem einfachsten, f(n) = f(n-1) + f(n-2)
Wir erhalten f(n+1) = f(n) + f(n-1) .
Nehmen wir an, wir kennen f(n) und f(n-1) ; Wir wollen f(n+1) herausfinden.
Aus der oben genannten Situation können Matrix A und Matrix B wie folgt gebildet werden:

 Matrix A          Matrix B

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

[Anmerkung: Matrix A wird immer so gestaltet, dass jeder Zustand, von dem f(n+1) abhängt, vorhanden ist.]
Nun müssen wir eine 2X2- Matrix M so entwerfen, dass sie MXA = B wie oben angegeben erfüllt.
Das erste Element von B ist f(n+1) was tatsächlich f(n) + f(n-1) . Um dies aus der Matrix A zu erhalten , benötigen wir 1 x f (n) und 1 x f (n-1) . Die erste Zeile von M ist also [1 1] .

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

[Hinweis: ----- bedeutet, dass wir uns nicht um diesen Wert kümmern.]
In ähnlicher Weise ist der zweite Punkt von B f(n) der durch einfaches Abnehmen von 1 X f (n) von A erhalten werden kann , so dass die zweite Reihe von M [1 0] ist.

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

Dann erhalten wir unsere gewünschte 2 X 2 Matrix M.

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

Diese Matrizen werden einfach durch Matrixmultiplikation abgeleitet.

Typ 2:

Machen wir es etwas komplexer: find f(n) = a X f(n-1) + b X f(n-2) , wobei a und b Konstanten sind.
Dies sagt uns, f(n+1) = a X f(n) + b X f(n-1) .
Insofern sollte klar sein, dass die Dimension der Matrizen gleich der Anzahl der Abhängigkeiten sein wird, dh in diesem speziellen Beispiel noch einmal 2. Für A und B können wir also zwei Matrizen der Größe 2 X 1 bauen :

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

Für f(n+1) = a X f(n) + b X f(n-1) benötigen wir [a, b] in der ersten Zeile der Zielmatrix M. Und für das 2. Element in B , dh f(n) wir bereits das in der Matrix A , also nehmen wir nur das, was die 2. Zeile der Matrix M zu [1 0] führt. Diesmal bekommen wir:

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

Ganz einfach, wie?

Typ 3:

Wenn Sie bis zu diesem Stadium überlebt haben, sind Sie viel älter geworden, jetzt stellen wir uns einer etwas komplexen Beziehung: find f(n) = a X f(n-1) + c X f(n-3) ?
Ooops! Vor ein paar Minuten sahen wir nur zusammenhängende Zustände, aber hier fehlt der Zustand f (n-2) . Jetzt?

Eigentlich ist dies kein Problem mehr, wir können die Relation wie folgt konvertieren: f(n) = a X f(n-1) + 0 X f(n-2) + c X f(n-3) , wobei f(n+1) = a X f(n) + 0 X f(n-1) + c X f(n-2) . Nun sehen wir, dass dies tatsächlich eine Form ist, die in Typ 2 beschrieben wird. Also wird hier die Zielmatrix M 3 x 3 sein und die Elemente sind:

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

Diese werden wie bei Typ 2 berechnet. Wenn Sie Schwierigkeiten haben, versuchen Sie es mit Stift und Papier.

Typ 4:

Das Leben wird so kompliziert wie die Hölle, und Mr, Problem fordert Sie jetzt auf, f(n) = f(n-1) + f(n-2) + c wobei c eine Konstante ist.
Jetzt ist dies ein neuer und alles, was wir in der Vergangenheit gesehen haben, transformiert sich nach der Multiplikation jeder Zustand in A in seinen nächsten Zustand 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

Normalerweise können wir es nicht durch die vorige Mode bringen, aber wie wäre es, wenn wir c als Zustand hinzufügen:

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

Nun, es ist nicht schwer, M zu entwerfen. So wird's gemacht, aber vergessen Sie nicht zu überprüfen:

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

Typ 5:

Sagen wir es zusammen: find f(n) = a X f(n-1) + c X f(n-3) + d X f(n-4) + e . Lassen Sie es uns als Übung für Sie. Versuchen Sie zunächst, die Zustände und die Matrix M herauszufinden. Und prüfen Sie, ob es zu Ihrer Lösung passt. Finden Sie auch Matrix A und 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 |

Typ 6:

Manchmal wird die Wiederholung wie folgt gegeben:

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

Zusamenfassend:

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

Hier können wir die Funktionen in ungerade gerade Basis aufteilen und für beide zwei unterschiedliche Matrix beibehalten und sie separat berechnen.

Typ 7:

Sich etwas zu selbstsicher fühlen? Schön für dich. Manchmal müssen wir mehr als eine Wiederholung beibehalten, wenn sie interessiert sind. Zum Beispiel sei eine Wiederholung re; atopm:

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

Hier ist die Wiederholung g (n) von f(n) abhängig und dies kann in derselben Matrix berechnet werden, jedoch mit größeren Abmessungen. Daraus lassen wir zunächst die Matrizen A und B entwerfen.

 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 ist g(n+1) = 2g(n-1) + f(n+1) and f(n+2) = 2f(n+1) + 2f(n) . Unter Verwendung der oben genannten Prozesse können wir die objektive Matrix M folgendermaßen finden:

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

Dies sind also die grundlegenden Kategorien von Wiederholungsbeziehungen, die verwendet werden, um diese einfache Technik zu lösen.