Mixing
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
asked Jan 21 at 6:51
Jimmy SabaterJimmy Sabater
2,897324
$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
asked Jan 21 at 6:51
Jimmy SabaterJimmy Sabater
2,897324
$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
asked Jan 21 at 6:51
Jimmy SabaterJimmy Sabater
2,897324
$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 Jan 21 at 6:51
Jimmy SabaterJimmy Sabater
2,897324
asked Jan 21 at 6:51
Jimmy SabaterJimmy Sabater
2,897324
asked Jan 21 at 6:51
Jimmy SabaterJimmy Sabater
2,897324
asked Jan 21 at 6:51
Jimmy SabaterJimmy Sabater
2,897324
asked Jan 21 at 6:51
Jimmy SabaterJimmy Sabater
2,897324
2,897324
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
The iteration $x_{n+1}=sin(x_n)$ converges towards $r=0$ despite the derivative there being $cos(0)=1$.
Details on the convergence
For $y_k=x_k^2$ one has the estimate by the Leibniz rule on alternating series
$$
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}\~\
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
$$
|x_k|lefrac{|x_0|}{sqrt{1+frac{k}3x_0^2}}.
$$
answered Jan 21 at 10:27
LutzLLutzL
59.3k42057
$endgroup$
$begingroup$
A good example with a nice bound. I also like $x_{k+1} = tan^{-1}{x_k}$ for which I imagine we can also apply alternating series. Please reconsider the use of the small font. I have to magnify it to read it.
$endgroup$
– Carl Christian
Jan 22 at 22:54
$begingroup$
From $x_{k+1}=x_k-frac13x_k^3+...$ you get by similar Bernoulli-like considerations $x_{k+1}^{-2}approx x_k^{-2}+frac23$. Exact inequalities are a little bit more complicated, as there is no nice identity for the square of the arcus tangent.
$endgroup$
– LutzL
Jan 22 at 23:05
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$.
answered Jan 21 at 6:53
FredFred
47.6k1849
$endgroup$
1
$begingroup$
how about if $|g'(r)| > 1$ can we find counterexample ?
$endgroup$
– Jimmy Sabater
Jan 21 at 6:59
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.
answered Jan 21 at 7:13
Mark BennetMark Bennet
81.5k983180
$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$
The iteration $x_{n+1}=sin(x_n)$ converges towards $r=0$ despite the derivative there being $cos(0)=1$.
Details on the convergence
For $y_k=x_k^2$ one has the estimate by the Leibniz rule on alternating series
$$
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}\~\
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
$$
|x_k|lefrac{|x_0|}{sqrt{1+frac{k}3x_0^2}}.
$$
answered Jan 21 at 10:27
LutzLLutzL
59.3k42057
$endgroup$
$begingroup$
A good example with a nice bound. I also like $x_{k+1} = tan^{-1}{x_k}$ for which I imagine we can also apply alternating series. Please reconsider the use of the small font. I have to magnify it to read it.
$endgroup$
– Carl Christian
Jan 22 at 22:54
$begingroup$
From $x_{k+1}=x_k-frac13x_k^3+...$ you get by similar Bernoulli-like considerations $x_{k+1}^{-2}approx x_k^{-2}+frac23$. Exact inequalities are a little bit more complicated, as there is no nice identity for the square of the arcus tangent.
$endgroup$
– LutzL
Jan 22 at 23:05
add a comment |
$begingroup$
The iteration $x_{n+1}=sin(x_n)$ converges towards $r=0$ despite the derivative there being $cos(0)=1$.
Details on the convergence
For $y_k=x_k^2$ one has the estimate by the Leibniz rule on alternating series
$$
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}\~\
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
$$
|x_k|lefrac{|x_0|}{sqrt{1+frac{k}3x_0^2}}.
$$
answered Jan 21 at 10:27
LutzLLutzL
59.3k42057
$endgroup$
$begingroup$
A good example with a nice bound. I also like $x_{k+1} = tan^{-1}{x_k}$ for which I imagine we can also apply alternating series. Please reconsider the use of the small font. I have to magnify it to read it.
$endgroup$
– Carl Christian
Jan 22 at 22:54
$begingroup$
From $x_{k+1}=x_k-frac13x_k^3+...$ you get by similar Bernoulli-like considerations $x_{k+1}^{-2}approx x_k^{-2}+frac23$. Exact inequalities are a little bit more complicated, as there is no nice identity for the square of the arcus tangent.
$endgroup$
– LutzL
Jan 22 at 23:05
add a comment |
$begingroup$
The iteration $x_{n+1}=sin(x_n)$ converges towards $r=0$ despite the derivative there being $cos(0)=1$.
Details on the convergence
For $y_k=x_k^2$ one has the estimate by the Leibniz rule on alternating series
$$
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}\~\
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
$$
|x_k|lefrac{|x_0|}{sqrt{1+frac{k}3x_0^2}}.
$$
answered Jan 21 at 10:27
LutzLLutzL
59.3k42057
$endgroup$
The iteration $x_{n+1}=sin(x_n)$ converges towards $r=0$ despite the derivative there being $cos(0)=1$.
Details on the convergence
For $y_k=x_k^2$ one has the estimate by the Leibniz rule on alternating series
$$
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}\~\
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
$$
|x_k|lefrac{|x_0|}{sqrt{1+frac{k}3x_0^2}}.
$$
answered Jan 21 at 10:27
LutzLLutzL
59.3k42057
edited Jan 22 at 22:57
answered Jan 21 at 10:27
LutzLLutzL
59.3k42057
answered Jan 21 at 10:27
LutzLLutzL
59.3k42057
answered Jan 21 at 10:27
LutzLLutzL
59.3k42057
59.3k42057
$begingroup$
A good example with a nice bound. I also like $x_{k+1} = tan^{-1}{x_k}$ for which I imagine we can also apply alternating series. Please reconsider the use of the small font. I have to magnify it to read it.
$endgroup$
– Carl Christian
Jan 22 at 22:54
$begingroup$
From $x_{k+1}=x_k-frac13x_k^3+...$ you get by similar Bernoulli-like considerations $x_{k+1}^{-2}approx x_k^{-2}+frac23$. Exact inequalities are a little bit more complicated, as there is no nice identity for the square of the arcus tangent.
$endgroup$
– LutzL
Jan 22 at 23:05
add a comment |
$begingroup$
A good example with a nice bound. I also like $x_{k+1} = tan^{-1}{x_k}$ for which I imagine we can also apply alternating series. Please reconsider the use of the small font. I have to magnify it to read it.
$endgroup$
– Carl Christian
Jan 22 at 22:54
$begingroup$
From $x_{k+1}=x_k-frac13x_k^3+...$ you get by similar Bernoulli-like considerations $x_{k+1}^{-2}approx x_k^{-2}+frac23$. Exact inequalities are a little bit more complicated, as there is no nice identity for the square of the arcus tangent.
$endgroup$
– LutzL
Jan 22 at 23:05
$begingroup$
A good example with a nice bound. I also like $x_{k+1} = tan^{-1}{x_k}$ for which I imagine we can also apply alternating series. Please reconsider the use of the small font. I have to magnify it to read it.
$endgroup$
– Carl Christian
Jan 22 at 22:54
$begingroup$
A good example with a nice bound. I also like $x_{k+1} = tan^{-1}{x_k}$ for which I imagine we can also apply alternating series. Please reconsider the use of the small font. I have to magnify it to read it.
$endgroup$
– Carl Christian
Jan 22 at 22:54
$begingroup$
From $x_{k+1}=x_k-frac13x_k^3+...$ you get by similar Bernoulli-like considerations $x_{k+1}^{-2}approx x_k^{-2}+frac23$. Exact inequalities are a little bit more complicated, as there is no nice identity for the square of the arcus tangent.
$endgroup$
– LutzL
Jan 22 at 23:05
$begingroup$
From $x_{k+1}=x_k-frac13x_k^3+...$ you get by similar Bernoulli-like considerations $x_{k+1}^{-2}approx x_k^{-2}+frac23$. Exact inequalities are a little bit more complicated, as there is no nice identity for the square of the arcus tangent.
$endgroup$
– LutzL
Jan 22 at 23:05
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$.
answered Jan 21 at 6:53
FredFred
47.6k1849
$endgroup$
1
$begingroup$
how about if $|g'(r)| > 1$ can we find counterexample ?
$endgroup$
– Jimmy Sabater
Jan 21 at 6:59
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$.
answered Jan 21 at 6:53
FredFred
47.6k1849
$endgroup$
1
$begingroup$
how about if $|g'(r)| > 1$ can we find counterexample ?
$endgroup$
– Jimmy Sabater
Jan 21 at 6:59
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$.
answered Jan 21 at 6:53
FredFred
47.6k1849
$endgroup$
Let $g(x)=x$. Then the sequence $(x_k)$ is constant hence convergent. We have $g'(x)=1$ for all $x$.
answered Jan 21 at 6:53
FredFred
47.6k1849
answered Jan 21 at 6:53
FredFred
47.6k1849
answered Jan 21 at 6:53
FredFred
47.6k1849
answered Jan 21 at 6:53
FredFred
47.6k1849
47.6k1849
1
$begingroup$
how about if $|g'(r)| > 1$ can we find counterexample ?
$endgroup$
– Jimmy Sabater
Jan 21 at 6:59
add a comment |
1
$begingroup$
how about if $|g'(r)| > 1$ can we find counterexample ?
$endgroup$
– Jimmy Sabater
Jan 21 at 6:59
1
1
$begingroup$
how about if $|g'(r)| > 1$ can we find counterexample ?
$endgroup$
– Jimmy Sabater
Jan 21 at 6:59
$begingroup$
how about if $|g'(r)| > 1$ can we find counterexample ?
$endgroup$
– Jimmy Sabater
Jan 21 at 6:59
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.
answered Jan 21 at 7:13
Mark BennetMark Bennet
81.5k983180
$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.
answered Jan 21 at 7:13
Mark BennetMark Bennet
81.5k983180
$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.
answered Jan 21 at 7:13
Mark BennetMark Bennet
81.5k983180
$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 Jan 21 at 7:13
Mark BennetMark Bennet
81.5k983180
answered Jan 21 at 7:13
Mark BennetMark Bennet
81.5k983180
answered Jan 21 at 7:13
Mark BennetMark Bennet
81.5k983180
answered Jan 21 at 7:13
Mark BennetMark Bennet
81.5k983180
81.5k983180
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
