c++ - 二阶线性递推方程的矩阵表示

Question

我可以计算一阶线性递归方程的矩阵表示。我通过使用快速矩阵求幂 计算高阶。我从本教程中学到了这一点 http://fusharblog.com/solving-linear-recurrence-for-programming-contest/

但我在计算二阶线性递归方程的矩阵表示时遇到问题。例如 -

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

你能帮我找出上面方程的矩阵表示或者给我一些见解吗？提前致谢。

Answer 1

这是二次多项式。众所周知的复发

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

通常称为 quadratic map通常不能以封闭形式求解。二次迭代

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

是 Mandelbrot 分形的迭代。这是定义 Mandelbrot set 的复杂 map 的真实版本.