Mixing
Why do we not need information of the eigenvalues of $A$ for the CG method, but we do need it for the...
$begingroup$
I'm currently reading up on information about the Chebyshev method and the Conjugate Gradient method for finding the solution of a system $$Amathbf{u}=mathbf{f}$$ where $A$ is an SPD matrix, but I am getting confused about something. For the Chebyshev method we know for the iterands that $$||mathbf{y}^k-mathbf{u}||_2leq 2Big(frac{sqrt{kappa_2(M^{-1}A)}-1}{sqrt{kappa_2(M^{-1}A)}+1}Big)^k ||mathbf{u}-mathbf{u}^0||_2$$
Where for the CG method we have that the iterates satisfy
$$||mathbf{u}-mathbf{u}^k||leq 2Big(frac{sqrt{kappa_2(A)}-1}{sqrt{kappa_2(A)}+1}Big)^k ||mathbf{u}-mathbf{u}^0||$$ Where $kappa_2(A)$ denotes the condition number of $A$.
As becomes obvious, both inequalities contain the condition number. However, in my literature it says that for application of the CG method, we do not need knowledge of the eigenvalues, whereas for the Chebyshev method, we do. Why is this? Does this have nothing to do with these bounds on the iterates?
Perhaps my explanation is a bit vague and perhaps the mentioned bounds are irrelevant for the necessity of knowledge of the eigenvalues, but I mentioned them anyway. Any explanation is appreciated!
linear-algebra numerical-methods eigenvalues-eigenvectors algorithms computational-mathematics
asked Jan 31 at 11:37
S. CrimS. Crim
406212
$endgroup$
add a comment |
$begingroup$
I'm currently reading up on information about the Chebyshev method and the Conjugate Gradient method for finding the solution of a system $$Amathbf{u}=mathbf{f}$$ where $A$ is an SPD matrix, but I am getting confused about something. For the Chebyshev method we know for the iterands that $$||mathbf{y}^k-mathbf{u}||_2leq 2Big(frac{sqrt{kappa_2(M^{-1}A)}-1}{sqrt{kappa_2(M^{-1}A)}+1}Big)^k ||mathbf{u}-mathbf{u}^0||_2$$
Where for the CG method we have that the iterates satisfy
$$||mathbf{u}-mathbf{u}^k||leq 2Big(frac{sqrt{kappa_2(A)}-1}{sqrt{kappa_2(A)}+1}Big)^k ||mathbf{u}-mathbf{u}^0||$$ Where $kappa_2(A)$ denotes the condition number of $A$.
As becomes obvious, both inequalities contain the condition number. However, in my literature it says that for application of the CG method, we do not need knowledge of the eigenvalues, whereas for the Chebyshev method, we do. Why is this? Does this have nothing to do with these bounds on the iterates?
Perhaps my explanation is a bit vague and perhaps the mentioned bounds are irrelevant for the necessity of knowledge of the eigenvalues, but I mentioned them anyway. Any explanation is appreciated!
linear-algebra numerical-methods eigenvalues-eigenvectors algorithms computational-mathematics
asked Jan 31 at 11:37
S. CrimS. Crim
406212
$endgroup$
1
$begingroup$
This only answers a small part of what you were asking, but for CG you can still run the algorithm without knowing the eigenvalues or condition number. In this case the algorithm will still satisfy the bound you have, however you won't be able to compute the bound without knowing the condition number and $| u-u^0|$
$endgroup$
– tch
Jan 31 at 16:31
add a comment |
$begingroup$
I'm currently reading up on information about the Chebyshev method and the Conjugate Gradient method for finding the solution of a system $$Amathbf{u}=mathbf{f}$$ where $A$ is an SPD matrix, but I am getting confused about something. For the Chebyshev method we know for the iterands that $$||mathbf{y}^k-mathbf{u}||_2leq 2Big(frac{sqrt{kappa_2(M^{-1}A)}-1}{sqrt{kappa_2(M^{-1}A)}+1}Big)^k ||mathbf{u}-mathbf{u}^0||_2$$
Where for the CG method we have that the iterates satisfy
$$||mathbf{u}-mathbf{u}^k||leq 2Big(frac{sqrt{kappa_2(A)}-1}{sqrt{kappa_2(A)}+1}Big)^k ||mathbf{u}-mathbf{u}^0||$$ Where $kappa_2(A)$ denotes the condition number of $A$.
As becomes obvious, both inequalities contain the condition number. However, in my literature it says that for application of the CG method, we do not need knowledge of the eigenvalues, whereas for the Chebyshev method, we do. Why is this? Does this have nothing to do with these bounds on the iterates?
Perhaps my explanation is a bit vague and perhaps the mentioned bounds are irrelevant for the necessity of knowledge of the eigenvalues, but I mentioned them anyway. Any explanation is appreciated!
linear-algebra numerical-methods eigenvalues-eigenvectors algorithms computational-mathematics
asked Jan 31 at 11:37
S. CrimS. Crim
406212
$endgroup$
I'm currently reading up on information about the Chebyshev method and the Conjugate Gradient method for finding the solution of a system $$Amathbf{u}=mathbf{f}$$ where $A$ is an SPD matrix, but I am getting confused about something. For the Chebyshev method we know for the iterands that $$||mathbf{y}^k-mathbf{u}||_2leq 2Big(frac{sqrt{kappa_2(M^{-1}A)}-1}{sqrt{kappa_2(M^{-1}A)}+1}Big)^k ||mathbf{u}-mathbf{u}^0||_2$$
Where for the CG method we have that the iterates satisfy
$$||mathbf{u}-mathbf{u}^k||leq 2Big(frac{sqrt{kappa_2(A)}-1}{sqrt{kappa_2(A)}+1}Big)^k ||mathbf{u}-mathbf{u}^0||$$ Where $kappa_2(A)$ denotes the condition number of $A$.
As becomes obvious, both inequalities contain the condition number. However, in my literature it says that for application of the CG method, we do not need knowledge of the eigenvalues, whereas for the Chebyshev method, we do. Why is this? Does this have nothing to do with these bounds on the iterates?
Perhaps my explanation is a bit vague and perhaps the mentioned bounds are irrelevant for the necessity of knowledge of the eigenvalues, but I mentioned them anyway. Any explanation is appreciated!
linear-algebra numerical-methods eigenvalues-eigenvectors algorithms computational-mathematics
linear-algebra numerical-methods eigenvalues-eigenvectors algorithms computational-mathematics
asked Jan 31 at 11:37
S. CrimS. Crim
406212
asked Jan 31 at 11:37
S. CrimS. Crim
406212
asked Jan 31 at 11:37
S. CrimS. Crim
406212
asked Jan 31 at 11:37
S. CrimS. Crim
406212
asked Jan 31 at 11:37
S. CrimS. Crim
406212
406212
1
$begingroup$
This only answers a small part of what you were asking, but for CG you can still run the algorithm without knowing the eigenvalues or condition number. In this case the algorithm will still satisfy the bound you have, however you won't be able to compute the bound without knowing the condition number and $| u-u^0|$
$endgroup$
– tch
Jan 31 at 16:31
add a comment |
1
$begingroup$
This only answers a small part of what you were asking, but for CG you can still run the algorithm without knowing the eigenvalues or condition number. In this case the algorithm will still satisfy the bound you have, however you won't be able to compute the bound without knowing the condition number and $| u-u^0|$
$endgroup$
– tch
Jan 31 at 16:31
1
1
$begingroup$
This only answers a small part of what you were asking, but for CG you can still run the algorithm without knowing the eigenvalues or condition number. In this case the algorithm will still satisfy the bound you have, however you won't be able to compute the bound without knowing the condition number and $| u-u^0|$
$endgroup$
– tch
Jan 31 at 16:31
$begingroup$
This only answers a small part of what you were asking, but for CG you can still run the algorithm without knowing the eigenvalues or condition number. In this case the algorithm will still satisfy the bound you have, however you won't be able to compute the bound without knowing the condition number and $| u-u^0|$
$endgroup$
– tch
Jan 31 at 16:31
add a comment |
0
active
oldest
votes
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%2f3094796%2fwhy-do-we-not-need-information-of-the-eigenvalues-of-a-for-the-cg-method-but%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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.
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%2f3094796%2fwhy-do-we-not-need-information-of-the-eigenvalues-of-a-for-the-cg-method-but%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
1
$begingroup$
This only answers a small part of what you were asking, but for CG you can still run the algorithm without knowing the eigenvalues or condition number. In this case the algorithm will still satisfy the bound you have, however you won't be able to compute the bound without knowing the condition number and $| u-u^0|$
$endgroup$
– tch
Jan 31 at 16:31