algorithm
Potęgowanie macierzy

Potęgowanie macierzy w celu rozwiązania przykładowych problemów

Znajdź f (n): n- ^ta liczba Fibonacciego. Problem jest dość łatwy, gdy n jest stosunkowo małe. Możemy użyć prostej rekurencji, f(n) = f(n-1) + f(n-2) , lub możemy zastosować podejście programowania dynamicznego, aby uniknąć obliczania tej samej funkcji w kółko. Ale co zrobisz, jeśli problem mówi: Biorąc pod uwagę 0 <n <10⁹, znajdź f (n) mod 999983? Programowanie dynamiczne zakończy się niepowodzeniem, więc jak rozwiązać ten problem?

Najpierw zobaczmy, jak potęgowanie macierzy może pomóc w reprezentacji relacji rekurencyjnej.

Wymagania wstępne:

• Biorąc pod uwagę dwie matryce, wiedz, jak znaleźć ich produkt. Ponadto, biorąc pod uwagę macierz produktu dwóch macierzy i jednej z nich, umie znaleźć drugą macierz.
• Biorąc pod uwagę macierz wielkości d X d , umie znaleźć jej n- ^tą moc w O (d ³ log (n)) .

Wzory:

Najpierw potrzebujemy relacji rekurencyjnej i chcemy znaleźć macierz M, która może doprowadzić nas do pożądanego stanu z zestawu już znanych stanów. Załóżmy, że wiemy, stany k danego równanie rekurencyjne i chcemy znaleźć (k + 1) ^th stan. Niech M będzie macierzą k X k , a my budujemy macierz A: [k X 1] na podstawie znanych stanów relacji rekurencji, teraz chcemy uzyskać macierz B: [k X 1], która będzie reprezentować zbiór kolejne stany, tj. MXA = B, jak pokazano poniżej:

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

Jeśli więc możemy odpowiednio zaprojektować M , nasza praca zostanie wykonana! Macierz zostanie następnie wykorzystana do przedstawienia relacji nawrotu.

Typ 1:
Zacznijmy od najprostszego, f(n) = f(n-1) + f(n-2)
Otrzymujemy, f(n+1) = f(n) + f(n-1) .
Załóżmy, że znamy f(n) f(n-1) ; Chcemy dowiedzieć się f(n+1) .
Z powyższej sytuacji można utworzyć macierz A i macierz B, jak pokazano poniżej:

 Matrix A          Matrix B

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

[Uwaga: Macierz A będzie zawsze zaprojektowana w taki sposób, że będzie obecny każdy stan, od którego zależy f(n+1) ]
Teraz musimy zaprojektować macierz M 2X2 , tak aby spełniała MXA = B, jak podano powyżej.
Pierwszym elementem B jest f(n+1) który w rzeczywistości jest f(n) + f(n-1) . Aby to uzyskać, z macierzy A potrzebujemy 1 X f (n) i 1 X f (n-1) . Tak więc pierwszym wierszem M będzie [1 1] .

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

[Uwaga: ----- oznacza, że nie martwimy się tą wartością.]
Podobnie, drugi element B to f(n) który można uzyskać po prostu biorąc 1 X f (n) z A , więc drugi rząd M to [1 0].

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

Następnie otrzymujemy pożądaną macierz 2 X 2 M.

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

Te macierze są po prostu wyprowadzane przy użyciu mnożenia macierzy.

Typ 2:

Niech będzie trochę skomplikowane Znajdź f(n) = a X f(n-1) + b X f(n-2) , gdzie a i b są stałymi.
To mówi nam, f(n+1) = a X f(n) + b X f(n-1) .
Do tej pory powinno być jasne, że wymiar macierzy będzie równy liczbie zależności, tj. W tym konkretnym przykładzie ponownie 2. Zatem dla A i B możemy zbudować dwie macierze o rozmiarze 2 X 1 :

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

Teraz dla f(n+1) = a X f(n) + b X f(n-1) potrzebujemy [a, b] w pierwszym rzędzie macierzy obiektywnej M. A dla drugiego elementu B , tj. f(n) mamy go już w macierzy A , więc bierzemy to, co prowadzi, drugi rząd macierzy M do [1 0]. Tym razem otrzymujemy:

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

Całkiem proste, prawda?

Typ 3:

Jeśli przetrwałeś do tego etapu, znacznie się postarzałeś, spójrzmy teraz na nieco złożoną relację: znajdź f(n) = a X f(n-1) + c X f(n-3) ?
Ups! Kilka minut temu widzieliśmy tylko ciągłe stany, ale tutaj brakuje stanu f (n-2) . Teraz?

W rzeczywistości nie jest to już problemem, możemy przekształcić relację w następujący sposób: f(n) = a X f(n-1) + 0 X f(n-2) + c X f(n-3) , dedukując f(n+1) = a X f(n) + 0 X f(n-1) + c X f(n-2) . Widzimy teraz, że tak naprawdę jest to forma opisana w typie 2. Zatem macierz M obiektywu będzie miała wymiary 3 X 3 , a elementy to:

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

Są one obliczane w taki sam sposób jak typ 2, jeśli masz trudności, wypróbuj je na kartce.

Typ 4:

Życie staje się skomplikowane jak diabli, a Pan, Problem teraz prosi o znalezienie f(n) = f(n-1) + f(n-2) + c gdzie c jest dowolną stałą.
Teraz jest to nowy i wszystko, co widzieliśmy w przeszłości, po pomnożeniu, każdy stan w A przekształca się do następnego stanu w 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

Zwykle nie możemy tego zrobić za pomocą poprzedniej mody, ale co powiesz na dodanie c jako stanu:

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

Teraz nie jest trudno zaprojektować M. Oto jak to zrobić, ale nie zapomnij o weryfikacji:

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

Typ 5:

Ujmijmy to w sumie: znajdź f(n) = a X f(n-1) + c X f(n-3) + d X f(n-4) + e . Zostawmy to jako ćwiczenie dla ciebie. Najpierw spróbuj znaleźć stany i macierz M. I sprawdź, czy pasuje do twojego rozwiązania. Znajdź także macierz A i 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:

Czasami nawrót podaje się w następujący sposób:

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

W skrócie:

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

Tutaj możemy podzielić funkcje na podstawie parzystej nieparzystej i zachować 2 różne macierze dla obu z nich i obliczyć je osobno.

Typ 7:

Czujesz się trochę zbyt pewny siebie? Dobrze dla ciebie. Czasami może zajść potrzeba utrzymania więcej niż jednego nawrotu, jeśli są zainteresowani. Na przykład, niech rekurencja ponownie; atopm będzie:

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

Tutaj powtarzalność g (n) zależy od f(n) i można to obliczyć w tej samej macierzy, ale o zwiększonych wymiarach. Z nich na początku zaprojektujmy macierze A i 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) |

Tutaj g(n+1) = 2g(n-1) + f(n+1) and f(n+2) = 2f(n+1) + 2f(n) . Teraz, stosując powyższe procesy, możemy znaleźć macierz M celu:

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

Są to więc podstawowe kategorie relacji powtarzalności, które są stosowane do rozwiązania tą prostą techniką.