Alexander Borzunov has written an interesting article about his Python code that uses fast matrix exponentiation to automatically optimize certain algorithms. It's definitely a recommended read.

In his article, Alexander mentions that it's difficult to directly derive a matrix exponentiation algorithm for recursively-defined sequences such as \[

F_n = \begin{cases}

0, & n = 0\\

1, & n = 1\\

1, & n = 2\\

7(2F_{n-1} + 3F_{n-2})+4F_{n-3}+5n+6, & n \geq 3

\end{cases}

\] While it's true that it's not entirely simple, there is a relatively straightforward way to do this that's worth knowing.

The only difficultly is due to the term \(5n+6\), but we can eliminate it by setting

\(F_n = G_n + an+b\), then solving for appropriate values of \(a, b\).

Substituting and grouping terms we have \[

G_n + an+b = 7(2G_{n-1} + 3G_{n-2})+4G_{n-3} + 39an-68a+39b+5n+6,

\] and equating powers of \(n\) we need to solve the equations \[

\begin{align*}

a &= 39a+5,\\

b &= -68a+39b+6.

\end{align*}

\] Setting \(a = -\frac{5}{38}, b = -\frac{142}{361}\) we end up with the homogeneous system \[

G_n = \begin{cases}

\frac{142}{361}, & n = 0\\

\frac{379}{722}, & n = 1\\

\frac{237}{361}, & n = 2\\

7(2G_{n-1} + 3G_{n-2})+4G_{n-3}, & n \geq 3

\end{cases}

\] This is now easily cast into matrix exponentiation form using the standard method.

## No comments:

## Post a Comment