Pergunta

I can calculate the Matrix representation of first degree Linear recurrence equations. And I calculate for higher order by using fast matrix exponentiation. I learnt this from this tutorial http://fusharblog.com/solving-linear-recurrence-for-programming-contest/

But I am facing problem in calculating the matrix representation of Second Degree Linear recurrence equations. For example -

S(n) = a * (S(n - 1))^2 + b * S(n - 1) + c
where S(0) = d

Can you help me to figure out the matrix representation of the above equation or give me some insights? Thanks in advance.

Foi útil?

Solução

This is polynomial of second degree. The well-known recurrence

 x_(n+1) = (x_n)^2 + c

that is often called the quadratic map is not in general solvable in closed form. Quadratic iteration

x_(n+1) = a (x_n)^2 + b x_n + c

is iteration of the Mandelbrot fractals. This is the real version of the complex map defining the Mandelbrot set.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top