Suche…


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 3 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.



Modified text is an extract of the original Stack Overflow Documentation
Lizenziert unter CC BY-SA 3.0
Nicht angeschlossen an Stack Overflow