Solve for x in (A^k)*x=b (sequentially, LU factorization)

9 ビュー (過去 30 日間)
Mark
Mark 2011 年 11 月 24 日
コメント済み: Sheraline Lawles 2021 年 2 月 22 日
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
Walter Roberson 2011 年 11 月 24 日
However, I would suggest that LU will not help much. See instead http://www.maths.lse.ac.uk/Personal/martin/fme4a.pdf
  1 件のコメント
Nicholas Lamm
Nicholas Lamm 2018 年 7 月 9 日
編集済み: Rena Berman 2018 年 7 月 9 日
A) Linking to the documentation is about the least helpful thing you can do and B) youre not even right, LU decomposition is great for solving matrices and is even cheaper in certain situations.

サインインしてコメントする。

その他の回答 (1 件)

Derek O'Connor
Derek O'Connor 2011 年 11 月 28 日
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).
  4 件のコメント
Derek O'Connor
Derek O'Connor 2011 年 11 月 28 日
Oh dear. It has just struck me that this may be a homework problem and I have given the game away.
Sheraline Lawles
Sheraline Lawles 2021 年 2 月 22 日
Just a note... sadly, the above link to Derek O'Connor's webpage is no longer active.

サインインしてコメントする。

カテゴリ

Help Center および File ExchangeLinear Algebra についてさらに検索

Community Treasure Hunt

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

Start Hunting!

Translated by