Mixing
Help understanding this limiting argument in QR algorithm
This is from Peter Lax's Linear Algebra, Chapter 18.
If $A$ is a self adjoint matrix, and if we denote by $U$ the matrix whose columns are its eigenvectors
$$U = (u_1,dots,u_n)$$
If the corresponding eigenvalues are $d_1, dots, d_n$, then $A = UDU^T$, and $A^k = UD^kU^T$. It follows from this formula that the columns of $A^k$ are linear combinations of the eigenvectors of $A$ of the following form:
$$b_1d_1^ku_1 + cdots + b_nd_n^ku_n$$
where $b_1, dots, b_n$ do not depend on $k$.
We now assume that the eigenvalues of $A$ are distinct and positive, and arrange them in decreasing order
$$d_1 > d_2 > dots > d_n > 0$$
It then follows that provided $b_1 neq 0$, the first column of $A^k$ is very close to a constant multiple of $u_1$.
I don't understand here why this would be close to a multiple of $u_1$ for large $k$. Intuitively, it does make some amount of sense as for large powers $k$, $d_1^k$ should dominate the others, but I don't know how to formulate this rigorously.
real-analysis matrices numerical-methods proof-explanation
asked Nov 20 '18 at 17:01
Anu
665215
add a comment |
This is from Peter Lax's Linear Algebra, Chapter 18.
If $A$ is a self adjoint matrix, and if we denote by $U$ the matrix whose columns are its eigenvectors
$$U = (u_1,dots,u_n)$$
If the corresponding eigenvalues are $d_1, dots, d_n$, then $A = UDU^T$, and $A^k = UD^kU^T$. It follows from this formula that the columns of $A^k$ are linear combinations of the eigenvectors of $A$ of the following form:
$$b_1d_1^ku_1 + cdots + b_nd_n^ku_n$$
where $b_1, dots, b_n$ do not depend on $k$.
We now assume that the eigenvalues of $A$ are distinct and positive, and arrange them in decreasing order
$$d_1 > d_2 > dots > d_n > 0$$
It then follows that provided $b_1 neq 0$, the first column of $A^k$ is very close to a constant multiple of $u_1$.
I don't understand here why this would be close to a multiple of $u_1$ for large $k$. Intuitively, it does make some amount of sense as for large powers $k$, $d_1^k$ should dominate the others, but I don't know how to formulate this rigorously.
real-analysis matrices numerical-methods proof-explanation
asked Nov 20 '18 at 17:01
Anu
665215
add a comment |
This is from Peter Lax's Linear Algebra, Chapter 18.
If $A$ is a self adjoint matrix, and if we denote by $U$ the matrix whose columns are its eigenvectors
$$U = (u_1,dots,u_n)$$
If the corresponding eigenvalues are $d_1, dots, d_n$, then $A = UDU^T$, and $A^k = UD^kU^T$. It follows from this formula that the columns of $A^k$ are linear combinations of the eigenvectors of $A$ of the following form:
$$b_1d_1^ku_1 + cdots + b_nd_n^ku_n$$
where $b_1, dots, b_n$ do not depend on $k$.
We now assume that the eigenvalues of $A$ are distinct and positive, and arrange them in decreasing order
$$d_1 > d_2 > dots > d_n > 0$$
It then follows that provided $b_1 neq 0$, the first column of $A^k$ is very close to a constant multiple of $u_1$.
I don't understand here why this would be close to a multiple of $u_1$ for large $k$. Intuitively, it does make some amount of sense as for large powers $k$, $d_1^k$ should dominate the others, but I don't know how to formulate this rigorously.
real-analysis matrices numerical-methods proof-explanation
asked Nov 20 '18 at 17:01
Anu
665215
This is from Peter Lax's Linear Algebra, Chapter 18.
If $A$ is a self adjoint matrix, and if we denote by $U$ the matrix whose columns are its eigenvectors
$$U = (u_1,dots,u_n)$$
If the corresponding eigenvalues are $d_1, dots, d_n$, then $A = UDU^T$, and $A^k = UD^kU^T$. It follows from this formula that the columns of $A^k$ are linear combinations of the eigenvectors of $A$ of the following form:
$$b_1d_1^ku_1 + cdots + b_nd_n^ku_n$$
where $b_1, dots, b_n$ do not depend on $k$.
We now assume that the eigenvalues of $A$ are distinct and positive, and arrange them in decreasing order
$$d_1 > d_2 > dots > d_n > 0$$
It then follows that provided $b_1 neq 0$, the first column of $A^k$ is very close to a constant multiple of $u_1$.
I don't understand here why this would be close to a multiple of $u_1$ for large $k$. Intuitively, it does make some amount of sense as for large powers $k$, $d_1^k$ should dominate the others, but I don't know how to formulate this rigorously.
real-analysis matrices numerical-methods proof-explanation
real-analysis matrices numerical-methods proof-explanation
asked Nov 20 '18 at 17:01
Anu
665215
asked Nov 20 '18 at 17:01
Anu
665215
asked Nov 20 '18 at 17:01
Anu
665215
asked Nov 20 '18 at 17:01
Anu
665215
asked Nov 20 '18 at 17:01
Anu
665215
665215
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
Divide through by $d_1^k$ and note that the various $frac{d_i^k}{d_1^k} longrightarrow 0$ except for $d_1^k$. So the leading term eventually dominates the sum. (That is, by ignoring the subleading terms, the relative error goes to zero; we do not claim the absolute error decreases, because it does not.)
(This method is analogous to the technique used to show that rational functions converge to a particular limit: divide the numerator and denominator by the largest power of the variable so that the subleading terms go to zero in the limit.)
answered Nov 20 '18 at 17:09
Eric Towers
31.8k22265
Thank you for your response! I understand that this would mean that the limit as $k rightarrow infty$ of $frac{A_{.,1}^k}{d_1^k}$ would be $b_1u_1$, but I still don't understand how this may mean that $A_{.,1}$ is close to a constant multiple of $u_1$. What am I missing?
– Anu
Nov 20 '18 at 17:19
@Anu : Er... $b_1 d_1^k u_1$ is explicitly a multiple of $u_1$, it is the $b_1 d_1^k$ multiple of $u_1$. The rest is less and less relevant. That is, the $A_{,1}$ column is more and more nearly parallel to $u_1$ by the limiting argument above.
– Eric Towers
Nov 20 '18 at 23:56
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3006581%2fhelp-understanding-this-limiting-argument-in-qr-algorithm%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
Divide through by $d_1^k$ and note that the various $frac{d_i^k}{d_1^k} longrightarrow 0$ except for $d_1^k$. So the leading term eventually dominates the sum. (That is, by ignoring the subleading terms, the relative error goes to zero; we do not claim the absolute error decreases, because it does not.)
(This method is analogous to the technique used to show that rational functions converge to a particular limit: divide the numerator and denominator by the largest power of the variable so that the subleading terms go to zero in the limit.)
answered Nov 20 '18 at 17:09
Eric Towers
31.8k22265
Thank you for your response! I understand that this would mean that the limit as $k rightarrow infty$ of $frac{A_{.,1}^k}{d_1^k}$ would be $b_1u_1$, but I still don't understand how this may mean that $A_{.,1}$ is close to a constant multiple of $u_1$. What am I missing?
– Anu
Nov 20 '18 at 17:19
@Anu : Er... $b_1 d_1^k u_1$ is explicitly a multiple of $u_1$, it is the $b_1 d_1^k$ multiple of $u_1$. The rest is less and less relevant. That is, the $A_{,1}$ column is more and more nearly parallel to $u_1$ by the limiting argument above.
– Eric Towers
Nov 20 '18 at 23:56
add a comment |
Divide through by $d_1^k$ and note that the various $frac{d_i^k}{d_1^k} longrightarrow 0$ except for $d_1^k$. So the leading term eventually dominates the sum. (That is, by ignoring the subleading terms, the relative error goes to zero; we do not claim the absolute error decreases, because it does not.)
(This method is analogous to the technique used to show that rational functions converge to a particular limit: divide the numerator and denominator by the largest power of the variable so that the subleading terms go to zero in the limit.)
answered Nov 20 '18 at 17:09
Eric Towers
31.8k22265
Thank you for your response! I understand that this would mean that the limit as $k rightarrow infty$ of $frac{A_{.,1}^k}{d_1^k}$ would be $b_1u_1$, but I still don't understand how this may mean that $A_{.,1}$ is close to a constant multiple of $u_1$. What am I missing?
– Anu
Nov 20 '18 at 17:19
@Anu : Er... $b_1 d_1^k u_1$ is explicitly a multiple of $u_1$, it is the $b_1 d_1^k$ multiple of $u_1$. The rest is less and less relevant. That is, the $A_{,1}$ column is more and more nearly parallel to $u_1$ by the limiting argument above.
– Eric Towers
Nov 20 '18 at 23:56
add a comment |
Divide through by $d_1^k$ and note that the various $frac{d_i^k}{d_1^k} longrightarrow 0$ except for $d_1^k$. So the leading term eventually dominates the sum. (That is, by ignoring the subleading terms, the relative error goes to zero; we do not claim the absolute error decreases, because it does not.)
(This method is analogous to the technique used to show that rational functions converge to a particular limit: divide the numerator and denominator by the largest power of the variable so that the subleading terms go to zero in the limit.)
answered Nov 20 '18 at 17:09
Eric Towers
31.8k22265
Divide through by $d_1^k$ and note that the various $frac{d_i^k}{d_1^k} longrightarrow 0$ except for $d_1^k$. So the leading term eventually dominates the sum. (That is, by ignoring the subleading terms, the relative error goes to zero; we do not claim the absolute error decreases, because it does not.)
(This method is analogous to the technique used to show that rational functions converge to a particular limit: divide the numerator and denominator by the largest power of the variable so that the subleading terms go to zero in the limit.)
answered Nov 20 '18 at 17:09
Eric Towers
31.8k22265
answered Nov 20 '18 at 17:09
Eric Towers
31.8k22265
answered Nov 20 '18 at 17:09
Eric Towers
31.8k22265
answered Nov 20 '18 at 17:09
Eric Towers
31.8k22265
31.8k22265
Thank you for your response! I understand that this would mean that the limit as $k rightarrow infty$ of $frac{A_{.,1}^k}{d_1^k}$ would be $b_1u_1$, but I still don't understand how this may mean that $A_{.,1}$ is close to a constant multiple of $u_1$. What am I missing?
– Anu
Nov 20 '18 at 17:19
@Anu : Er... $b_1 d_1^k u_1$ is explicitly a multiple of $u_1$, it is the $b_1 d_1^k$ multiple of $u_1$. The rest is less and less relevant. That is, the $A_{,1}$ column is more and more nearly parallel to $u_1$ by the limiting argument above.
– Eric Towers
Nov 20 '18 at 23:56
add a comment |
Thank you for your response! I understand that this would mean that the limit as $k rightarrow infty$ of $frac{A_{.,1}^k}{d_1^k}$ would be $b_1u_1$, but I still don't understand how this may mean that $A_{.,1}$ is close to a constant multiple of $u_1$. What am I missing?
– Anu
Nov 20 '18 at 17:19
@Anu : Er... $b_1 d_1^k u_1$ is explicitly a multiple of $u_1$, it is the $b_1 d_1^k$ multiple of $u_1$. The rest is less and less relevant. That is, the $A_{,1}$ column is more and more nearly parallel to $u_1$ by the limiting argument above.
– Eric Towers
Nov 20 '18 at 23:56
Thank you for your response! I understand that this would mean that the limit as $k rightarrow infty$ of $frac{A_{.,1}^k}{d_1^k}$ would be $b_1u_1$, but I still don't understand how this may mean that $A_{.,1}$ is close to a constant multiple of $u_1$. What am I missing?
– Anu
Nov 20 '18 at 17:19
Thank you for your response! I understand that this would mean that the limit as $k rightarrow infty$ of $frac{A_{.,1}^k}{d_1^k}$ would be $b_1u_1$, but I still don't understand how this may mean that $A_{.,1}$ is close to a constant multiple of $u_1$. What am I missing?
– Anu
Nov 20 '18 at 17:19
@Anu : Er... $b_1 d_1^k u_1$ is explicitly a multiple of $u_1$, it is the $b_1 d_1^k$ multiple of $u_1$. The rest is less and less relevant. That is, the $A_{,1}$ column is more and more nearly parallel to $u_1$ by the limiting argument above.
– Eric Towers
Nov 20 '18 at 23:56
@Anu : Er... $b_1 d_1^k u_1$ is explicitly a multiple of $u_1$, it is the $b_1 d_1^k$ multiple of $u_1$. The rest is less and less relevant. That is, the $A_{,1}$ column is more and more nearly parallel to $u_1$ by the limiting argument above.
– Eric Towers
Nov 20 '18 at 23:56
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3006581%2fhelp-understanding-this-limiting-argument-in-qr-algorithm%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
