algorithm
Matrix Exponentiation

Matriseksponentiering för att lösa exempelproblem

Hitta f (n): n: ^e Fibonacci-numret. Problemet är ganska enkelt när n är relativt liten. Vi kan använda enkel rekursion, f(n) = f(n-1) + f(n-2) , eller vi kan använda dynamisk programmeringsmetod för att undvika beräkning av samma funktion om och om igen. Men vad ska du göra om problemet säger: Med tanke på 0 <n <10⁹, hitta f (n) mod 999983? Dynamisk programmering kommer att misslyckas, så hur löser vi det här problemet?

Låt oss först se hur matriseksponentiering kan hjälpa till att representera rekursiv relation.

förutsättningar:

• Med två matriser, vet du hur du hittar deras produkt. Vidare, med tanke på produktmatrisen för två matriser, och en av dem, vet hur man hittar den andra matrisen.
• Med tanke på en matris med storlek d X d , veta hur man hittar sin n: ^a kraft i O (d ³ log (n)) .

Mönster:

Först behöver vi en rekursiv relation och vi vill hitta en matris M som kan leda oss till önskat tillstånd från en uppsättning av redan kända tillstånd. Låt oss anta att vi känner till k- tillstånden för en given återfallsrelation och vi vill hitta det (k + 1): ^e tillståndet. Låt M vara en k X k- matris, och vi bygger en matris A: [k X 1] från de kända tillstånden för återfallsrelationen, nu vill vi få en matris B: [k X 1] som kommer att representera uppsättningen av nästa tillstånd, dvs. MXA = B som visas nedan:

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

Så om vi kan utforma M i enlighet med detta kommer vårt jobb att göras! Matrisen kommer sedan att användas för att representera återfallsrelationen.

Typ 1:
Låt oss börja med den enklaste, f(n) = f(n-1) + f(n-2)
Vi får, f(n+1) = f(n) + f(n-1) .
Låt oss anta att vi vet f(n) och f(n-1) ; Vi vill ta reda på f(n+1) .
Från den ovan angivna situationen kan matris A och matris B formas såsom visas nedan:

 Matrix A          Matrix B

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

[Obs: Matris A kommer alltid att utformas på ett sådant sätt att varje tillstånd som f(n+1) beror på kommer att vara närvarande]
Nu måste vi utforma en 2X2- matris M så att den uppfyller MXA = B enligt ovan.
Det första elementet i B är f(n+1) som faktiskt är f(n) + f(n-1) . För att få detta, från matris A , behöver vi 1 X f (n) och 1 X f (n-1) . Så den första raden med M kommer att vara [1 1] .

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

[Obs: ----- betyder att vi inte är oroliga för detta värde.]
På liknande sätt är den andra delen av B f(n) som kan erhållas genom att helt enkelt ta 1 X f (n) från A , så den andra raden av M är [1 0].

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

Sedan får vi vår önskade 2 X 2 matris M.

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

Dessa matriser härrör helt enkelt med hjälp av matrismultiplikation.

Typ 2:

Låt oss göra det lite komplicerat: hitta f(n) = a X f(n-1) + b X f(n-2) , där a och b är konstanter.
Detta säger oss, f(n+1) = a X f(n) + b X f(n-1) .
Hittills borde detta vara tydligt att matrisernas dimension kommer att vara lika med antalet beroenden, dvs i detta specifika exempel, återigen. Så för A och B kan vi bygga två matriser i storlek 2 X 1 :

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) behöver vi [a, b] i den första raden med objektivmatris M. Och för det andra objektet i B , dvs f(n) vi det redan i matris A , så vi tar bara det, som leder, den andra raden i matrisen M till [1 0]. Den här gången får vi:

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

Ganska enkelt, va?

Typ 3:

Om du har överlevt till detta skede har du blivit mycket äldre, låt oss nu möta en lite komplex relation: hitta f(n) = a X f(n-1) + c X f(n-3) ?
Oj! För några minuter sedan var allt vi såg sammanhängande tillstånd, men här saknas tillståndet f (n-2) . Nu?

Egentligen är detta inte ett problem längre, vi kan konvertera förhållandet enligt följande: f(n) = a X f(n-1) + 0 X f(n-2) + c X f(n-3) , drar f(n+1) = a X f(n) + 0 X f(n-1) + c X f(n-2) . Nu ser vi det, det här är faktiskt en form som beskrivs i typ 2. Så här kommer objektivmatrisen M att vara 3 X 3 och elementen är:

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

Dessa beräknas på samma sätt som typ 2, om du har svårt kan du prova det på penna och papper.

Typ 4:

Livet blir komplicerat som helvete, och Mr, Problem ber dig nu att hitta f(n) = f(n-1) + f(n-2) + c där c är någon konstant.
Nu är detta ett nytt och allt vi har sett tidigare, efter multiplikationen, förvandlas varje tillstånd i A till sitt nästa tillstånd i 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

Så normalt sett kan vi inte få det genom tidigare mode, men vad sägs om vi lägger till c som ett tillstånd:

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

Nu är det inte mycket svårt att designa M. Så här görs, men glöm inte att verifiera:

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

Typ 5:

Låt oss säga det helt: hitta f(n) = a X f(n-1) + c X f(n-3) + d X f(n-4) + e . Låt oss lämna det som en övning för dig. Försök först ta reda på tillstånden och matrisen M. Och kolla om det stämmer med din lösning. Hitta även matris A och 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:

Ibland ges återfallet så här:

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

Kortfattat:

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

Här kan vi dela funktionerna utifrån udda jämna och hålla 2 olika matriser för båda och beräkna dem separat.

Typ 7:

Känner du dig lite för säker? Bra för dig. Ibland kan vi behöva hålla mer än ett återfall, där de är intresserade. Låt till exempel en återfall återkomma; atopm vara:

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

Här är återfall g (n) beroende av f(n) och detta kan beräknas i samma matris men av ökade dimensioner. Låt oss från början designa matriserna A och 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) |

Här är g(n+1) = 2g(n-1) + f(n+1) and f(n+2) = 2f(n+1) + 2f(n) . Genom att använda de processer som anges ovan kan vi hitta den objektiva matrisen M :

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

Så det är de grundläggande kategorierna för återfallsrelationer som används för att lösa denna enkla teknik.