Newton-Raphson on strictly convex function
Maybe someone can give me a hint here:
question 1: Given a sequence {$x_n$} which is the Newton-Raphson sequence on some $f(x)$ s.t. $f(x)$ is strictly convex and $f'>0$.
Let $alpha$ be the unique root of $f$ (i.e $f(alpha$) = 0).
For any $x_0$ initial guess,
prove that $alpha < x_n$ and $x_n > x_{n+1}$.
I know that I should use the fact that for any given $x_0,x_1$ s.t. $x_0 < x_1, f'(x_0) < frac{f(x_1) - f(x_0)}{x_1 - x_0}$, and although I can see the geometrical correctness instantly, I am having a hard time to prove it formally.
Appreciate your guidance,
Yotam.
numerical-methods convex-analysis numerical-optimization newton-raphson numerical-calculus
edited Nov 29 '18 at 13:13
LutzL
56.3k42054
asked Nov 29 '18 at 11:18
Yotam Raz
215
add a comment |
Maybe someone can give me a hint here:
question 1: Given a sequence {$x_n$} which is the Newton-Raphson sequence on some $f(x)$ s.t. $f(x)$ is strictly convex and $f'>0$.
Let $alpha$ be the unique root of $f$ (i.e $f(alpha$) = 0).
For any $x_0$ initial guess,
prove that $alpha < x_n$ and $x_n > x_{n+1}$.
I know that I should use the fact that for any given $x_0,x_1$ s.t. $x_0 < x_1, f'(x_0) < frac{f(x_1) - f(x_0)}{x_1 - x_0}$, and although I can see the geometrical correctness instantly, I am having a hard time to prove it formally.
Appreciate your guidance,
Yotam.
numerical-methods convex-analysis numerical-optimization newton-raphson numerical-calculus
edited Nov 29 '18 at 13:13
LutzL
56.3k42054
asked Nov 29 '18 at 11:18
Yotam Raz
215
add a comment |
Maybe someone can give me a hint here:
question 1: Given a sequence {$x_n$} which is the Newton-Raphson sequence on some $f(x)$ s.t. $f(x)$ is strictly convex and $f'>0$.
Let $alpha$ be the unique root of $f$ (i.e $f(alpha$) = 0).
For any $x_0$ initial guess,
prove that $alpha < x_n$ and $x_n > x_{n+1}$.
I know that I should use the fact that for any given $x_0,x_1$ s.t. $x_0 < x_1, f'(x_0) < frac{f(x_1) - f(x_0)}{x_1 - x_0}$, and although I can see the geometrical correctness instantly, I am having a hard time to prove it formally.
Appreciate your guidance,
Yotam.
numerical-methods convex-analysis numerical-optimization newton-raphson numerical-calculus
edited Nov 29 '18 at 13:13
LutzL
56.3k42054
asked Nov 29 '18 at 11:18
Yotam Raz
215
Maybe someone can give me a hint here:
question 1: Given a sequence {$x_n$} which is the Newton-Raphson sequence on some $f(x)$ s.t. $f(x)$ is strictly convex and $f'>0$.
Let $alpha$ be the unique root of $f$ (i.e $f(alpha$) = 0).
For any $x_0$ initial guess,
prove that $alpha < x_n$ and $x_n > x_{n+1}$.
I know that I should use the fact that for any given $x_0,x_1$ s.t. $x_0 < x_1, f'(x_0) < frac{f(x_1) - f(x_0)}{x_1 - x_0}$, and although I can see the geometrical correctness instantly, I am having a hard time to prove it formally.
Appreciate your guidance,
Yotam.
numerical-methods convex-analysis numerical-optimization newton-raphson numerical-calculus
numerical-methods convex-analysis numerical-optimization newton-raphson numerical-calculus
edited Nov 29 '18 at 13:13
LutzL
56.3k42054
asked Nov 29 '18 at 11:18
Yotam Raz
215
edited Nov 29 '18 at 13:13
LutzL
56.3k42054
asked Nov 29 '18 at 11:18
Yotam Raz
215
edited Nov 29 '18 at 13:13
LutzL
56.3k42054
edited Nov 29 '18 at 13:13
LutzL
56.3k42054
edited Nov 29 '18 at 13:13
LutzL
56.3k42054
56.3k42054
asked Nov 29 '18 at 11:18
Yotam Raz
215
asked Nov 29 '18 at 11:18
Yotam Raz
215
asked Nov 29 '18 at 11:18
Yotam Raz
215
215
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
Because of convexity, the tangent $f(a)+f'(a)(x-a)$ is a supporting hyper"plane" and thus completely below the function. Which means that at the root of the tangent, the function value is above zero, positive. As $f$ is strictly increasing, this means that $x_1$ is right of the root with $f(x_1)>0$, independent of the position of $x_0$, if that is not already the root $α$. This property then also holds for all further Newton iterates.
As the tangent in $x_n$ is also monotonically increasing, the positive value $f(x_n)>0$ implies that the next iterate $x_{n+1}$ has to be left of $x_n$.
answered Nov 29 '18 at 13:20
LutzL
56.3k42054
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%2f3018500%2fnewton-raphson-on-strictly-convex-function%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
Because of convexity, the tangent $f(a)+f'(a)(x-a)$ is a supporting hyper"plane" and thus completely below the function. Which means that at the root of the tangent, the function value is above zero, positive. As $f$ is strictly increasing, this means that $x_1$ is right of the root with $f(x_1)>0$, independent of the position of $x_0$, if that is not already the root $α$. This property then also holds for all further Newton iterates.
As the tangent in $x_n$ is also monotonically increasing, the positive value $f(x_n)>0$ implies that the next iterate $x_{n+1}$ has to be left of $x_n$.
answered Nov 29 '18 at 13:20
LutzL
56.3k42054
add a comment |
Because of convexity, the tangent $f(a)+f'(a)(x-a)$ is a supporting hyper"plane" and thus completely below the function. Which means that at the root of the tangent, the function value is above zero, positive. As $f$ is strictly increasing, this means that $x_1$ is right of the root with $f(x_1)>0$, independent of the position of $x_0$, if that is not already the root $α$. This property then also holds for all further Newton iterates.
As the tangent in $x_n$ is also monotonically increasing, the positive value $f(x_n)>0$ implies that the next iterate $x_{n+1}$ has to be left of $x_n$.
answered Nov 29 '18 at 13:20
LutzL
56.3k42054
add a comment |
Because of convexity, the tangent $f(a)+f'(a)(x-a)$ is a supporting hyper"plane" and thus completely below the function. Which means that at the root of the tangent, the function value is above zero, positive. As $f$ is strictly increasing, this means that $x_1$ is right of the root with $f(x_1)>0$, independent of the position of $x_0$, if that is not already the root $α$. This property then also holds for all further Newton iterates.
As the tangent in $x_n$ is also monotonically increasing, the positive value $f(x_n)>0$ implies that the next iterate $x_{n+1}$ has to be left of $x_n$.
answered Nov 29 '18 at 13:20
LutzL
56.3k42054
Because of convexity, the tangent $f(a)+f'(a)(x-a)$ is a supporting hyper"plane" and thus completely below the function. Which means that at the root of the tangent, the function value is above zero, positive. As $f$ is strictly increasing, this means that $x_1$ is right of the root with $f(x_1)>0$, independent of the position of $x_0$, if that is not already the root $α$. This property then also holds for all further Newton iterates.
As the tangent in $x_n$ is also monotonically increasing, the positive value $f(x_n)>0$ implies that the next iterate $x_{n+1}$ has to be left of $x_n$.
answered Nov 29 '18 at 13:20
LutzL
56.3k42054
answered Nov 29 '18 at 13:20
LutzL
56.3k42054
answered Nov 29 '18 at 13:20
LutzL
56.3k42054
answered Nov 29 '18 at 13:20
LutzL
56.3k42054
56.3k42054
add a comment |
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%2f3018500%2fnewton-raphson-on-strictly-convex-function%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
