Newton's method, neighborhood of convergence
$begingroup$
For Newton's method, my book says that for convergence, the starting point, $x^{(0)}$, must be sufficiently close to $x^*$, the actual root.
According to the following inequality, where $C = frac{sup|f''(x)|}{inf|f'(x)|}$,
$$|x^*-x^{(n+1)}| leq frac{1}{2}C(x^*-x^{(n)})^2,$$
which implies that
$$frac{1}{2}C|x^*-x^{(0)}| <1$$ needs to be satisfied for $x^{(0)}$ to be considered sufficiently close enough to $x^*$ (otherwise the distance between $x^*$ and $x^{(n+1)}$ might not decrease).
I'm having trouble understanding how to reach $frac{1}{2}C|x^*-x^{(0)}| <1$. Why is the condition not $frac{1}{2}C(x^*-x^{(0)})^2 <1?$
algebra-precalculus numerical-methods newton-raphson
asked Dec 11 '18 at 11:31
platypus17platypus17
296
$endgroup$
add a comment |
$begingroup$
For Newton's method, my book says that for convergence, the starting point, $x^{(0)}$, must be sufficiently close to $x^*$, the actual root.
According to the following inequality, where $C = frac{sup|f''(x)|}{inf|f'(x)|}$,
$$|x^*-x^{(n+1)}| leq frac{1}{2}C(x^*-x^{(n)})^2,$$
which implies that
$$frac{1}{2}C|x^*-x^{(0)}| <1$$ needs to be satisfied for $x^{(0)}$ to be considered sufficiently close enough to $x^*$ (otherwise the distance between $x^*$ and $x^{(n+1)}$ might not decrease).
I'm having trouble understanding how to reach $frac{1}{2}C|x^*-x^{(0)}| <1$. Why is the condition not $frac{1}{2}C(x^*-x^{(0)})^2 <1?$
algebra-precalculus numerical-methods newton-raphson
asked Dec 11 '18 at 11:31
platypus17platypus17
296
$endgroup$
add a comment |
$begingroup$
For Newton's method, my book says that for convergence, the starting point, $x^{(0)}$, must be sufficiently close to $x^*$, the actual root.
According to the following inequality, where $C = frac{sup|f''(x)|}{inf|f'(x)|}$,
$$|x^*-x^{(n+1)}| leq frac{1}{2}C(x^*-x^{(n)})^2,$$
which implies that
$$frac{1}{2}C|x^*-x^{(0)}| <1$$ needs to be satisfied for $x^{(0)}$ to be considered sufficiently close enough to $x^*$ (otherwise the distance between $x^*$ and $x^{(n+1)}$ might not decrease).
I'm having trouble understanding how to reach $frac{1}{2}C|x^*-x^{(0)}| <1$. Why is the condition not $frac{1}{2}C(x^*-x^{(0)})^2 <1?$
algebra-precalculus numerical-methods newton-raphson
asked Dec 11 '18 at 11:31
platypus17platypus17
296
$endgroup$
For Newton's method, my book says that for convergence, the starting point, $x^{(0)}$, must be sufficiently close to $x^*$, the actual root.
According to the following inequality, where $C = frac{sup|f''(x)|}{inf|f'(x)|}$,
$$|x^*-x^{(n+1)}| leq frac{1}{2}C(x^*-x^{(n)})^2,$$
which implies that
$$frac{1}{2}C|x^*-x^{(0)}| <1$$ needs to be satisfied for $x^{(0)}$ to be considered sufficiently close enough to $x^*$ (otherwise the distance between $x^*$ and $x^{(n+1)}$ might not decrease).
I'm having trouble understanding how to reach $frac{1}{2}C|x^*-x^{(0)}| <1$. Why is the condition not $frac{1}{2}C(x^*-x^{(0)})^2 <1?$
algebra-precalculus numerical-methods newton-raphson
algebra-precalculus numerical-methods newton-raphson
asked Dec 11 '18 at 11:31
platypus17platypus17
296
asked Dec 11 '18 at 11:31
platypus17platypus17
296
asked Dec 11 '18 at 11:31
platypus17platypus17
296
asked Dec 11 '18 at 11:31
platypus17platypus17
296
asked Dec 11 '18 at 11:31
platypus17platypus17
296
296
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
You have a recursive inequality of the type $$d_{k+1}le qd_k^2.$$ You could now successively insert it into itself to find a general law, but what is easier is to just multiply with $q$ to get
$$(qd_{k+1})le (qd_k)^2.$$
This is easier to iterate, and you get
$$
(qd_k)le (qd_0)^{2^k}
$$
The upper bound is part of the geometric sequence, and thus converges to zero for $|qd_0|<1$. For $|qd_0|ge 1$ the bound diverges and thus allows no statement on the convergence of the sequence $(d_k)_{kinBbb N}$.
answered Dec 11 '18 at 11:52
LutzLLutzL
58.8k42055
$endgroup$
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%2f3035200%2fnewtons-method-neighborhood-of-convergence%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
$begingroup$
You have a recursive inequality of the type $$d_{k+1}le qd_k^2.$$ You could now successively insert it into itself to find a general law, but what is easier is to just multiply with $q$ to get
$$(qd_{k+1})le (qd_k)^2.$$
This is easier to iterate, and you get
$$
(qd_k)le (qd_0)^{2^k}
$$
The upper bound is part of the geometric sequence, and thus converges to zero for $|qd_0|<1$. For $|qd_0|ge 1$ the bound diverges and thus allows no statement on the convergence of the sequence $(d_k)_{kinBbb N}$.
answered Dec 11 '18 at 11:52
LutzLLutzL
58.8k42055
$endgroup$
add a comment |
$begingroup$
You have a recursive inequality of the type $$d_{k+1}le qd_k^2.$$ You could now successively insert it into itself to find a general law, but what is easier is to just multiply with $q$ to get
$$(qd_{k+1})le (qd_k)^2.$$
This is easier to iterate, and you get
$$
(qd_k)le (qd_0)^{2^k}
$$
The upper bound is part of the geometric sequence, and thus converges to zero for $|qd_0|<1$. For $|qd_0|ge 1$ the bound diverges and thus allows no statement on the convergence of the sequence $(d_k)_{kinBbb N}$.
answered Dec 11 '18 at 11:52
LutzLLutzL
58.8k42055
$endgroup$
add a comment |
$begingroup$
You have a recursive inequality of the type $$d_{k+1}le qd_k^2.$$ You could now successively insert it into itself to find a general law, but what is easier is to just multiply with $q$ to get
$$(qd_{k+1})le (qd_k)^2.$$
This is easier to iterate, and you get
$$
(qd_k)le (qd_0)^{2^k}
$$
The upper bound is part of the geometric sequence, and thus converges to zero for $|qd_0|<1$. For $|qd_0|ge 1$ the bound diverges and thus allows no statement on the convergence of the sequence $(d_k)_{kinBbb N}$.
answered Dec 11 '18 at 11:52
LutzLLutzL
58.8k42055
$endgroup$
You have a recursive inequality of the type $$d_{k+1}le qd_k^2.$$ You could now successively insert it into itself to find a general law, but what is easier is to just multiply with $q$ to get
$$(qd_{k+1})le (qd_k)^2.$$
This is easier to iterate, and you get
$$
(qd_k)le (qd_0)^{2^k}
$$
The upper bound is part of the geometric sequence, and thus converges to zero for $|qd_0|<1$. For $|qd_0|ge 1$ the bound diverges and thus allows no statement on the convergence of the sequence $(d_k)_{kinBbb N}$.
answered Dec 11 '18 at 11:52
LutzLLutzL
58.8k42055
answered Dec 11 '18 at 11:52
LutzLLutzL
58.8k42055
answered Dec 11 '18 at 11:52
LutzLLutzL
58.8k42055
answered Dec 11 '18 at 11:52
LutzLLutzL
58.8k42055
58.8k42055
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.
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%2f3035200%2fnewtons-method-neighborhood-of-convergence%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
