Mixing
Motive of Conjugate Gradient method.
0
$begingroup$
It is known that the solution to the linear system $Ax=b$ where $A$ is symmetric and positive definite is the minimizer of the quadratic function
$f(x)= frac{1}{2} x^T A x - x^T b$
We can solve it using the steepest descent method. However, there is a better method which chooses the direction $p_k$ to be A-conjugate.
The thing I don't understand is why choosing the current direction to be Conjugate to the previous ones is a good thing?
Why is the CG method is better?
numerical-methods numerical-linear-algebra nonlinear-optimization numerical-optimization
asked Jan 18 at 22:24
Dreamer123Dreamer123
32729
$endgroup$
add a comment |
0
$begingroup$
It is known that the solution to the linear system $Ax=b$ where $A$ is symmetric and positive definite is the minimizer of the quadratic function
$f(x)= frac{1}{2} x^T A x - x^T b$
We can solve it using the steepest descent method. However, there is a better method which chooses the direction $p_k$ to be A-conjugate.
The thing I don't understand is why choosing the current direction to be Conjugate to the previous ones is a good thing?
Why is the CG method is better?
numerical-methods numerical-linear-algebra nonlinear-optimization numerical-optimization
asked Jan 18 at 22:24
Dreamer123Dreamer123
32729
$endgroup$
$begingroup$
From what I remember it has something to do with the speed of convergence.
$endgroup$
– J.F
Jan 18 at 22:58
$begingroup$
well for one thing, the search direction ensures that all the residuals $r_k = b-Ax_k$ are mutually orthogonal, therefore it is guaranteed to converge to the exact solution in at most $n$ steps, where $n$ is the dimension of $b.$ But in practice it produces a reasonably solution in much fewer steps.
$endgroup$
– dezdichado
Jan 18 at 23:00
1
$begingroup$
What sources did you use to learn GC? Usually there is an example with very elongated ellipses as level sets as motivating example. There steepest descent results in many small zigzagging steps.
$endgroup$
– LutzL
Jan 19 at 13:36
$begingroup$
Indeed, here's an example from another answer.
$endgroup$
– Algebraic Pavel
Jan 21 at 17:03
$begingroup$
Basically, CG is a way of trying to "unwarp" the energy landscape defined by the quadratic form involving $A$. The clever thing about CG is that it lets us unwarp the surface in a computationally efficient way. See some notes here for more details.
$endgroup$
– jjjjjj
Jan 25 at 17:29
add a comment |
0
0
0
2
$begingroup$
It is known that the solution to the linear system $Ax=b$ where $A$ is symmetric and positive definite is the minimizer of the quadratic function
$f(x)= frac{1}{2} x^T A x - x^T b$
We can solve it using the steepest descent method. However, there is a better method which chooses the direction $p_k$ to be A-conjugate.
The thing I don't understand is why choosing the current direction to be Conjugate to the previous ones is a good thing?
Why is the CG method is better?
numerical-methods numerical-linear-algebra nonlinear-optimization numerical-optimization
asked Jan 18 at 22:24
Dreamer123Dreamer123
32729
$endgroup$
It is known that the solution to the linear system $Ax=b$ where $A$ is symmetric and positive definite is the minimizer of the quadratic function
$f(x)= frac{1}{2} x^T A x - x^T b$
We can solve it using the steepest descent method. However, there is a better method which chooses the direction $p_k$ to be A-conjugate.
The thing I don't understand is why choosing the current direction to be Conjugate to the previous ones is a good thing?
Why is the CG method is better?
numerical-methods numerical-linear-algebra nonlinear-optimization numerical-optimization
numerical-methods numerical-linear-algebra nonlinear-optimization numerical-optimization
asked Jan 18 at 22:24
Dreamer123Dreamer123
32729
asked Jan 18 at 22:24
Dreamer123Dreamer123
32729
asked Jan 18 at 22:24
Dreamer123Dreamer123
32729
asked Jan 18 at 22:24
Dreamer123Dreamer123
32729
asked Jan 18 at 22:24
Dreamer123Dreamer123
32729
32729
$begingroup$
From what I remember it has something to do with the speed of convergence.
$endgroup$
– J.F
Jan 18 at 22:58
$begingroup$
well for one thing, the search direction ensures that all the residuals $r_k = b-Ax_k$ are mutually orthogonal, therefore it is guaranteed to converge to the exact solution in at most $n$ steps, where $n$ is the dimension of $b.$ But in practice it produces a reasonably solution in much fewer steps.
$endgroup$
– dezdichado
Jan 18 at 23:00
1
$begingroup$
What sources did you use to learn GC? Usually there is an example with very elongated ellipses as level sets as motivating example. There steepest descent results in many small zigzagging steps.
$endgroup$
– LutzL
Jan 19 at 13:36
$begingroup$
Indeed, here's an example from another answer.
$endgroup$
– Algebraic Pavel
Jan 21 at 17:03
$begingroup$
Basically, CG is a way of trying to "unwarp" the energy landscape defined by the quadratic form involving $A$. The clever thing about CG is that it lets us unwarp the surface in a computationally efficient way. See some notes here for more details.
$endgroup$
– jjjjjj
Jan 25 at 17:29
add a comment |
$begingroup$
From what I remember it has something to do with the speed of convergence.
$endgroup$
– J.F
Jan 18 at 22:58
$begingroup$
well for one thing, the search direction ensures that all the residuals $r_k = b-Ax_k$ are mutually orthogonal, therefore it is guaranteed to converge to the exact solution in at most $n$ steps, where $n$ is the dimension of $b.$ But in practice it produces a reasonably solution in much fewer steps.
$endgroup$
– dezdichado
Jan 18 at 23:00
1
$begingroup$
What sources did you use to learn GC? Usually there is an example with very elongated ellipses as level sets as motivating example. There steepest descent results in many small zigzagging steps.
$endgroup$
– LutzL
Jan 19 at 13:36
$begingroup$
Indeed, here's an example from another answer.
$endgroup$
– Algebraic Pavel
Jan 21 at 17:03
$begingroup$
Basically, CG is a way of trying to "unwarp" the energy landscape defined by the quadratic form involving $A$. The clever thing about CG is that it lets us unwarp the surface in a computationally efficient way. See some notes here for more details.
$endgroup$
– jjjjjj
Jan 25 at 17:29
$begingroup$
From what I remember it has something to do with the speed of convergence.
$endgroup$
– J.F
Jan 18 at 22:58
$begingroup$
From what I remember it has something to do with the speed of convergence.
$endgroup$
– J.F
Jan 18 at 22:58
$begingroup$
well for one thing, the search direction ensures that all the residuals $r_k = b-Ax_k$ are mutually orthogonal, therefore it is guaranteed to converge to the exact solution in at most $n$ steps, where $n$ is the dimension of $b.$ But in practice it produces a reasonably solution in much fewer steps.
$endgroup$
– dezdichado
Jan 18 at 23:00
$begingroup$
well for one thing, the search direction ensures that all the residuals $r_k = b-Ax_k$ are mutually orthogonal, therefore it is guaranteed to converge to the exact solution in at most $n$ steps, where $n$ is the dimension of $b.$ But in practice it produces a reasonably solution in much fewer steps.
$endgroup$
– dezdichado
Jan 18 at 23:00
1
1
$begingroup$
What sources did you use to learn GC? Usually there is an example with very elongated ellipses as level sets as motivating example. There steepest descent results in many small zigzagging steps.
$endgroup$
– LutzL
Jan 19 at 13:36
$begingroup$
What sources did you use to learn GC? Usually there is an example with very elongated ellipses as level sets as motivating example. There steepest descent results in many small zigzagging steps.
$endgroup$
– LutzL
Jan 19 at 13:36
$begingroup$
Indeed, here's an example from another answer.
$endgroup$
– Algebraic Pavel
Jan 21 at 17:03
$begingroup$
Indeed, here's an example from another answer.
$endgroup$
– Algebraic Pavel
Jan 21 at 17:03
$begingroup$
Basically, CG is a way of trying to "unwarp" the energy landscape defined by the quadratic form involving $A$. The clever thing about CG is that it lets us unwarp the surface in a computationally efficient way. See some notes here for more details.
$endgroup$
– jjjjjj
Jan 25 at 17:29
$begingroup$
Basically, CG is a way of trying to "unwarp" the energy landscape defined by the quadratic form involving $A$. The clever thing about CG is that it lets us unwarp the surface in a computationally efficient way. See some notes here for more details.
$endgroup$
– jjjjjj
Jan 25 at 17:29
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
});
}
});
draft saved
draft discarded
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%2f3078819%2fmotive-of-conjugate-gradient-method%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
draft saved
draft discarded
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.
draft saved
draft discarded
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%2f3078819%2fmotive-of-conjugate-gradient-method%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
$begingroup$
From what I remember it has something to do with the speed of convergence.
$endgroup$
– J.F
Jan 18 at 22:58
$begingroup$
well for one thing, the search direction ensures that all the residuals $r_k = b-Ax_k$ are mutually orthogonal, therefore it is guaranteed to converge to the exact solution in at most $n$ steps, where $n$ is the dimension of $b.$ But in practice it produces a reasonably solution in much fewer steps.
$endgroup$
– dezdichado
Jan 18 at 23:00
1
$begingroup$
What sources did you use to learn GC? Usually there is an example with very elongated ellipses as level sets as motivating example. There steepest descent results in many small zigzagging steps.
$endgroup$
– LutzL
Jan 19 at 13:36
$begingroup$
Indeed, here's an example from another answer.
$endgroup$
– Algebraic Pavel
Jan 21 at 17:03
$begingroup$
Basically, CG is a way of trying to "unwarp" the energy landscape defined by the quadratic form involving $A$. The clever thing about CG is that it lets us unwarp the surface in a computationally efficient way. See some notes here for more details.
$endgroup$
– jjjjjj
Jan 25 at 17:29