Why do you memoize the matrix method and not the iterative method? When I memoize the iterative method, I end up with about constant time for each of the steps:
Around 1000 gives Iterative: 0.054137468338 Matrix: 1.92105817795

This all stays in memory for my machine.

You can find the improved fork of your code here:
gist.github.com/ClashTheBunny/762a497d920a24aada69