Interpret the problem as solving k linear systems sequentially

Question

I am studying mathematical programming in Matlab,

I just understand questions in the point of view from a mathematician. (My real task is writing code in Matlab)

I have $A^k x=b$ where A is any square matrix, b is a vector and k is a positive number. I am solving this by LU factorization.

My real question to you is

How can I Interpret the problem as solving k linear systems sequentially?

Please help me to do its mathematical demonstration? Thanks a lot

Answer 1

Let $x_1$ be the solution to $Ax=b$ and let $x_2$ be the solution to $Ax=x_1$. Then $A^2x_2=A(Ax_2)=Ax_1=b$, so that $x_2$ is the solution to $Ax=b$. Get the idea?

Answer 2

It is probably not the best idea to perform $k$ systems resolutions, this is a costly operation. In addition, you must do this sequentially, i.e. $k$ times, which is a lot.

Another option is to compute $A^k$ before the resolution, which can be done by successive squarings and products, in $O(\log(k))$ steps, which can be much better than $k$.