Iteration for fixed point
$begingroup$
Suppose $x_{k+1}= g(x_k)$ is fixed point iteration for some continuously diffrentiable $g(x)$. The theorem im learning says that if $g(r) = r$ and $|g'(r)| < 1$ then the fixed point iteration converges to $r$ for initial guess $x_0$ sufficiently close to $r$.
MY question is: Is the converse is also true? That is, if the fixed point iteration converges to $r$, then we must have $|g'(r)|<1$?
OR is it possible to have situations where $g'(r) geq 1$ with $(x_k)$ convergent to $r$.
numerical-methods
$endgroup$
add a comment |
$begingroup$
Suppose $x_{k+1}= g(x_k)$ is fixed point iteration for some continuously diffrentiable $g(x)$. The theorem im learning says that if $g(r) = r$ and $|g'(r)| < 1$ then the fixed point iteration converges to $r$ for initial guess $x_0$ sufficiently close to $r$.
MY question is: Is the converse is also true? That is, if the fixed point iteration converges to $r$, then we must have $|g'(r)|<1$?
OR is it possible to have situations where $g'(r) geq 1$ with $(x_k)$ convergent to $r$.
numerical-methods
$endgroup$
add a comment |
$begingroup$
Suppose $x_{k+1}= g(x_k)$ is fixed point iteration for some continuously diffrentiable $g(x)$. The theorem im learning says that if $g(r) = r$ and $|g'(r)| < 1$ then the fixed point iteration converges to $r$ for initial guess $x_0$ sufficiently close to $r$.
MY question is: Is the converse is also true? That is, if the fixed point iteration converges to $r$, then we must have $|g'(r)|<1$?
OR is it possible to have situations where $g'(r) geq 1$ with $(x_k)$ convergent to $r$.
numerical-methods
$endgroup$
Suppose $x_{k+1}= g(x_k)$ is fixed point iteration for some continuously diffrentiable $g(x)$. The theorem im learning says that if $g(r) = r$ and $|g'(r)| < 1$ then the fixed point iteration converges to $r$ for initial guess $x_0$ sufficiently close to $r$.
MY question is: Is the converse is also true? That is, if the fixed point iteration converges to $r$, then we must have $|g'(r)|<1$?
OR is it possible to have situations where $g'(r) geq 1$ with $(x_k)$ convergent to $r$.
numerical-methods
numerical-methods
asked 8 hours ago
Jimmy SabaterJimmy Sabater
2,240319
2,240319
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
Let $g(x)=x$. Then the sequence $(x_k)$ is constant hence convergent. We have $g'(x)=1$ for all $x$.
$endgroup$
1
$begingroup$
how about if $|g'(r)| > 1$ can we find counterexample ?
$endgroup$
– Jimmy Sabater
8 hours ago
add a comment |
$begingroup$
Suppose you have the function $f(x)=kx(x-a)+a$ so that $f(a)=a$
Then $f'(x)=2kx-k = k(2x-1)$ and if $aneq frac 12$ it is possible to choose a value of $k$ to make $f'(a)$ any value you choose.
The difference is that if $|f'(a)| gt 1$ there is no open interval containing $a$ in which the iteration converges - this only happens at the point.
The behaviour in general where $|f'(a)| = 1$ depends on the function.
$endgroup$
add a comment |
$begingroup$
The iteration $x_{n+1}=sin(x_n)$ converges towards $r=0$ despite the derivative there being $cos(0)=1$.
For $y_k=x_k^2$ one has the estimate by the Leibniz rule on alternating series
$$small
y_{k+1}=frac12(1-cos(2x_k))
le y_k-frac13y_k^2+frac2{45}y_k^3
%=y_kfrac{1-frac{1}{15}y_k^2-frac2{135}y_k^3}{1+frac13y_k}
lefrac{y_k}{1+frac13y_k}\~\small
implies y_{k+1}^{-1}gefrac13+y_k^{-1}implies y_klefrac{y_0}{1+frac{k}3y_0}
$$
so that one finds the convergence by the non-geometric majorant
$$small
|x_k|lefrac{|x_0|}{sqrt{1+frac{k}3x_0^2}}.
$$
$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%2f3081576%2fiteration-for-fixed-point%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Let $g(x)=x$. Then the sequence $(x_k)$ is constant hence convergent. We have $g'(x)=1$ for all $x$.
$endgroup$
1
$begingroup$
how about if $|g'(r)| > 1$ can we find counterexample ?
$endgroup$
– Jimmy Sabater
8 hours ago
add a comment |
$begingroup$
Let $g(x)=x$. Then the sequence $(x_k)$ is constant hence convergent. We have $g'(x)=1$ for all $x$.
$endgroup$
1
$begingroup$
how about if $|g'(r)| > 1$ can we find counterexample ?
$endgroup$
– Jimmy Sabater
8 hours ago
add a comment |
$begingroup$
Let $g(x)=x$. Then the sequence $(x_k)$ is constant hence convergent. We have $g'(x)=1$ for all $x$.
$endgroup$
Let $g(x)=x$. Then the sequence $(x_k)$ is constant hence convergent. We have $g'(x)=1$ for all $x$.
answered 8 hours ago
FredFred
44.7k1846
44.7k1846
1
$begingroup$
how about if $|g'(r)| > 1$ can we find counterexample ?
$endgroup$
– Jimmy Sabater
8 hours ago
add a comment |
1
$begingroup$
how about if $|g'(r)| > 1$ can we find counterexample ?
$endgroup$
– Jimmy Sabater
8 hours ago
1
1
$begingroup$
how about if $|g'(r)| > 1$ can we find counterexample ?
$endgroup$
– Jimmy Sabater
8 hours ago
$begingroup$
how about if $|g'(r)| > 1$ can we find counterexample ?
$endgroup$
– Jimmy Sabater
8 hours ago
add a comment |
$begingroup$
Suppose you have the function $f(x)=kx(x-a)+a$ so that $f(a)=a$
Then $f'(x)=2kx-k = k(2x-1)$ and if $aneq frac 12$ it is possible to choose a value of $k$ to make $f'(a)$ any value you choose.
The difference is that if $|f'(a)| gt 1$ there is no open interval containing $a$ in which the iteration converges - this only happens at the point.
The behaviour in general where $|f'(a)| = 1$ depends on the function.
$endgroup$
add a comment |
$begingroup$
Suppose you have the function $f(x)=kx(x-a)+a$ so that $f(a)=a$
Then $f'(x)=2kx-k = k(2x-1)$ and if $aneq frac 12$ it is possible to choose a value of $k$ to make $f'(a)$ any value you choose.
The difference is that if $|f'(a)| gt 1$ there is no open interval containing $a$ in which the iteration converges - this only happens at the point.
The behaviour in general where $|f'(a)| = 1$ depends on the function.
$endgroup$
add a comment |
$begingroup$
Suppose you have the function $f(x)=kx(x-a)+a$ so that $f(a)=a$
Then $f'(x)=2kx-k = k(2x-1)$ and if $aneq frac 12$ it is possible to choose a value of $k$ to make $f'(a)$ any value you choose.
The difference is that if $|f'(a)| gt 1$ there is no open interval containing $a$ in which the iteration converges - this only happens at the point.
The behaviour in general where $|f'(a)| = 1$ depends on the function.
$endgroup$
Suppose you have the function $f(x)=kx(x-a)+a$ so that $f(a)=a$
Then $f'(x)=2kx-k = k(2x-1)$ and if $aneq frac 12$ it is possible to choose a value of $k$ to make $f'(a)$ any value you choose.
The difference is that if $|f'(a)| gt 1$ there is no open interval containing $a$ in which the iteration converges - this only happens at the point.
The behaviour in general where $|f'(a)| = 1$ depends on the function.
answered 8 hours ago
Mark BennetMark Bennet
80.9k981179
80.9k981179
add a comment |
add a comment |
$begingroup$
The iteration $x_{n+1}=sin(x_n)$ converges towards $r=0$ despite the derivative there being $cos(0)=1$.
For $y_k=x_k^2$ one has the estimate by the Leibniz rule on alternating series
$$small
y_{k+1}=frac12(1-cos(2x_k))
le y_k-frac13y_k^2+frac2{45}y_k^3
%=y_kfrac{1-frac{1}{15}y_k^2-frac2{135}y_k^3}{1+frac13y_k}
lefrac{y_k}{1+frac13y_k}\~\small
implies y_{k+1}^{-1}gefrac13+y_k^{-1}implies y_klefrac{y_0}{1+frac{k}3y_0}
$$
so that one finds the convergence by the non-geometric majorant
$$small
|x_k|lefrac{|x_0|}{sqrt{1+frac{k}3x_0^2}}.
$$
$endgroup$
add a comment |
$begingroup$
The iteration $x_{n+1}=sin(x_n)$ converges towards $r=0$ despite the derivative there being $cos(0)=1$.
For $y_k=x_k^2$ one has the estimate by the Leibniz rule on alternating series
$$small
y_{k+1}=frac12(1-cos(2x_k))
le y_k-frac13y_k^2+frac2{45}y_k^3
%=y_kfrac{1-frac{1}{15}y_k^2-frac2{135}y_k^3}{1+frac13y_k}
lefrac{y_k}{1+frac13y_k}\~\small
implies y_{k+1}^{-1}gefrac13+y_k^{-1}implies y_klefrac{y_0}{1+frac{k}3y_0}
$$
so that one finds the convergence by the non-geometric majorant
$$small
|x_k|lefrac{|x_0|}{sqrt{1+frac{k}3x_0^2}}.
$$
$endgroup$
add a comment |
$begingroup$
The iteration $x_{n+1}=sin(x_n)$ converges towards $r=0$ despite the derivative there being $cos(0)=1$.
For $y_k=x_k^2$ one has the estimate by the Leibniz rule on alternating series
$$small
y_{k+1}=frac12(1-cos(2x_k))
le y_k-frac13y_k^2+frac2{45}y_k^3
%=y_kfrac{1-frac{1}{15}y_k^2-frac2{135}y_k^3}{1+frac13y_k}
lefrac{y_k}{1+frac13y_k}\~\small
implies y_{k+1}^{-1}gefrac13+y_k^{-1}implies y_klefrac{y_0}{1+frac{k}3y_0}
$$
so that one finds the convergence by the non-geometric majorant
$$small
|x_k|lefrac{|x_0|}{sqrt{1+frac{k}3x_0^2}}.
$$
$endgroup$
The iteration $x_{n+1}=sin(x_n)$ converges towards $r=0$ despite the derivative there being $cos(0)=1$.
For $y_k=x_k^2$ one has the estimate by the Leibniz rule on alternating series
$$small
y_{k+1}=frac12(1-cos(2x_k))
le y_k-frac13y_k^2+frac2{45}y_k^3
%=y_kfrac{1-frac{1}{15}y_k^2-frac2{135}y_k^3}{1+frac13y_k}
lefrac{y_k}{1+frac13y_k}\~\small
implies y_{k+1}^{-1}gefrac13+y_k^{-1}implies y_klefrac{y_0}{1+frac{k}3y_0}
$$
so that one finds the convergence by the non-geometric majorant
$$small
|x_k|lefrac{|x_0|}{sqrt{1+frac{k}3x_0^2}}.
$$
answered 5 hours ago
LutzLLutzL
57.3k42054
57.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.
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%2f3081576%2fiteration-for-fixed-point%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