74 views (last 30 days)

Show older comments

Without computing A^k, solve for x in (A^k)*x=b.

A) Sequentially? (Pseudocode)

for n=1:k

x=A\b;

b=x;

end

Is the above process correct?

B) LU factorizaion?

How is this accompished?

Walter Roberson
on 24 Nov 2011

http://www.mathworks.com/help/techdoc/ref/lu.html for LU factorization.

However, I would suggest that LU will not help much. See instead http://www.maths.lse.ac.uk/Personal/martin/fme4a.pdf

Nicholas Lamm
on 9 Jul 2018

Derek O'Connor
on 28 Nov 2011

Contrary to what Walter says, LU Decomposition is a great help in this problem. See my solution notes to Lab Exercise 6 --- LU Decomposition and Matrix Powers

Additional Information

Here is the Golub-Van Loan Algorithm for solving (A^k)*x = b

[L,U,P] = lu(A);

for m = 1:k

y = L\(P*b);

x = U\y;

b = x;

end

Matlab's backslash operator "\" is clever enough to figure out that y = L\(P*b) is forward substitution, while x = U\y is back substitution, each of which requires O(n^2) work.

Total amount of work is: O(n^3) + k*O(n^2) = O(n^3 + k*n^2)

If k << n then this total is effectively O(n^3).

Sheraline Lawles
on 22 Feb 2021

Just a note... sadly, the above link to Derek O'Connor's webpage is no longer active.

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!