Convergence to a fixed point [duplicate]Contraction mapping in the context of $f(x_n)=x_{n+1}$.Confused about...
How can I handle a player who pre-plans arguments about my rulings on RAW?
How to roleplay my character's ethics according to the DM when I don't understand those ethics?
Number of folds to form a cube, using a square paper?
Convert an array of objects to array of the objects' values
Is divide-by-zero a security vulnerability?
Practical reasons to have both a large police force and bounty hunting network?
Where is the fallacy here?
Adjust starting of second line
What kind of inflection is occuring in passive vb + かかった?
Is every open circuit a capacitor?
How can I be pwned if I'm not registered on the compromised site?
A bug in Excel? Conditional formatting for marking duplicates also highlights unique value
What is brightness?
Why is there an extra space when I type "ls" on the Desktop?
Why do phishing e-mails use faked e-mail addresses instead of the real one?
GPL code private and stolen
Can we carry rice to Japan?
The orphan's family
Should I use HTTPS on a domain that will only be used for redirection?
What is better: yes / no radio, or simple checkbox?
An Undercover Army
How do we objectively assess if a dialogue sounds unnatural or cringy?
How to chmod files that have a specific set of permissions
Are Wave equations equivalent to Maxwell equations in free space?
Convergence to a fixed point [duplicate]
Contraction mapping in the context of $f(x_n)=x_{n+1}$.Confused about fixed point method conditionShrinking Map and Fixed Point via Iteration MethodWhich negation of the definition of a null sequence is correct?Relation between two different definitions of quadratic convergenceFixed point, bounded derivativeProving Cauchy when given a sequenceBanach fixed point questionHelp me understand this proof of Implicit Function Theorem on Banach spacesConvergence of functions (in sense of distributions)Banach fixed-point theoremIf the odd function $f:mathbb Rtomathbb R$ letting $x>0$ is continuous at $x$, prove the function is continuous at $-x$.
$begingroup$
This question already has an answer here:
Contraction mapping in the context of $f(x_n)=x_{n+1}$.
3 answers
Let $f : [a,b] rightarrow [a,b]$ be a continuous function s.t. $f'(x)$ is defined on $(a,b)$ and $leftlvert f'(x)rightrvert leqq t$ where $0<t<1$. Prove that for any point $x_0$ in $[a,b]$ the sequence defined by $$ x_n=f(x_{n-1}), n>0$$
converges to one unique fixed point.
Attempt:
Frankly, I have struggled to make a real attempt due to the fact that I can't find notes relating to this.
Obviously, I am assuming that there exists $x$ in$ [a,b]$ s.t. $f(x)=x$ but how do I relate the sequence to this $x$?
I'm strictly not allowed to assume Banach's theorem in this question, nor the Cauchy sequence because they come up on the second part of the course. I rather have to PROVE this.
analysis convergence numerical-methods fixed-point-theorems fixedpoints
New contributor
Grace is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
marked as duplicate by rtybase, Eevee Trainer, mrtaurho, Vinyl_cape_jawa, José Carlos Santos 2 hours ago
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |
$begingroup$
This question already has an answer here:
Contraction mapping in the context of $f(x_n)=x_{n+1}$.
3 answers
Let $f : [a,b] rightarrow [a,b]$ be a continuous function s.t. $f'(x)$ is defined on $(a,b)$ and $leftlvert f'(x)rightrvert leqq t$ where $0<t<1$. Prove that for any point $x_0$ in $[a,b]$ the sequence defined by $$ x_n=f(x_{n-1}), n>0$$
converges to one unique fixed point.
Attempt:
Frankly, I have struggled to make a real attempt due to the fact that I can't find notes relating to this.
Obviously, I am assuming that there exists $x$ in$ [a,b]$ s.t. $f(x)=x$ but how do I relate the sequence to this $x$?
I'm strictly not allowed to assume Banach's theorem in this question, nor the Cauchy sequence because they come up on the second part of the course. I rather have to PROVE this.
analysis convergence numerical-methods fixed-point-theorems fixedpoints
New contributor
Grace is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
marked as duplicate by rtybase, Eevee Trainer, mrtaurho, Vinyl_cape_jawa, José Carlos Santos 2 hours ago
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
$begingroup$
Another related question.
$endgroup$
– rtybase
17 hours ago
$begingroup$
Welcome to Mathematics Stack Exchange! A quick tour will enhance your experience. Here are helpful tips to write a good question and write a good answer.
$endgroup$
– dantopa
15 hours ago
add a comment |
$begingroup$
This question already has an answer here:
Contraction mapping in the context of $f(x_n)=x_{n+1}$.
3 answers
Let $f : [a,b] rightarrow [a,b]$ be a continuous function s.t. $f'(x)$ is defined on $(a,b)$ and $leftlvert f'(x)rightrvert leqq t$ where $0<t<1$. Prove that for any point $x_0$ in $[a,b]$ the sequence defined by $$ x_n=f(x_{n-1}), n>0$$
converges to one unique fixed point.
Attempt:
Frankly, I have struggled to make a real attempt due to the fact that I can't find notes relating to this.
Obviously, I am assuming that there exists $x$ in$ [a,b]$ s.t. $f(x)=x$ but how do I relate the sequence to this $x$?
I'm strictly not allowed to assume Banach's theorem in this question, nor the Cauchy sequence because they come up on the second part of the course. I rather have to PROVE this.
analysis convergence numerical-methods fixed-point-theorems fixedpoints
New contributor
Grace is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
This question already has an answer here:
Contraction mapping in the context of $f(x_n)=x_{n+1}$.
3 answers
Let $f : [a,b] rightarrow [a,b]$ be a continuous function s.t. $f'(x)$ is defined on $(a,b)$ and $leftlvert f'(x)rightrvert leqq t$ where $0<t<1$. Prove that for any point $x_0$ in $[a,b]$ the sequence defined by $$ x_n=f(x_{n-1}), n>0$$
converges to one unique fixed point.
Attempt:
Frankly, I have struggled to make a real attempt due to the fact that I can't find notes relating to this.
Obviously, I am assuming that there exists $x$ in$ [a,b]$ s.t. $f(x)=x$ but how do I relate the sequence to this $x$?
I'm strictly not allowed to assume Banach's theorem in this question, nor the Cauchy sequence because they come up on the second part of the course. I rather have to PROVE this.
This question already has an answer here:
Contraction mapping in the context of $f(x_n)=x_{n+1}$.
3 answers
analysis convergence numerical-methods fixed-point-theorems fixedpoints
analysis convergence numerical-methods fixed-point-theorems fixedpoints
New contributor
Grace is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Grace is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 17 hours ago
Grace
New contributor
Grace is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 17 hours ago
![](https://lh5.googleusercontent.com/-jaqy1BCPPSs/AAAAAAAAAAI/AAAAAAAAAAA/AAN31DWxpXvCu-VVRUMFCRFp5skNZCTV1w/mo/photo.jpg?sz=32)
![](https://lh5.googleusercontent.com/-jaqy1BCPPSs/AAAAAAAAAAI/AAAAAAAAAAA/AAN31DWxpXvCu-VVRUMFCRFp5skNZCTV1w/mo/photo.jpg?sz=32)
Grace Grace
255
255
New contributor
Grace is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Grace is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Grace is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
marked as duplicate by rtybase, Eevee Trainer, mrtaurho, Vinyl_cape_jawa, José Carlos Santos 2 hours ago
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
marked as duplicate by rtybase, Eevee Trainer, mrtaurho, Vinyl_cape_jawa, José Carlos Santos 2 hours ago
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
$begingroup$
Another related question.
$endgroup$
– rtybase
17 hours ago
$begingroup$
Welcome to Mathematics Stack Exchange! A quick tour will enhance your experience. Here are helpful tips to write a good question and write a good answer.
$endgroup$
– dantopa
15 hours ago
add a comment |
$begingroup$
Another related question.
$endgroup$
– rtybase
17 hours ago
$begingroup$
Welcome to Mathematics Stack Exchange! A quick tour will enhance your experience. Here are helpful tips to write a good question and write a good answer.
$endgroup$
– dantopa
15 hours ago
$begingroup$
Another related question.
$endgroup$
– rtybase
17 hours ago
$begingroup$
Another related question.
$endgroup$
– rtybase
17 hours ago
$begingroup$
Welcome to Mathematics Stack Exchange! A quick tour will enhance your experience. Here are helpful tips to write a good question and write a good answer.
$endgroup$
– dantopa
15 hours ago
$begingroup$
Welcome to Mathematics Stack Exchange! A quick tour will enhance your experience. Here are helpful tips to write a good question and write a good answer.
$endgroup$
– dantopa
15 hours ago
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
To prove this from scratch note that by MVT $$|x_n-x_m| leq |x_{m+1}-x_m|+|x_{m+2}-x_{m+1}|$$ $$+cdots+|x_{n}-x_{n-1}|leq |x_{m+1}-x_m| (1+t+t^{2}+cdots+t^{n+m-1})$$ for $n >m$. Also $|x_{m+1}-x_m| leq t^{m-1} |x_2-x_1|$. Using the convergence of the geometric series $sum t^{n}$ conclude that ${x_n}$ is Cauchy. If $x =lim x_n$ then the definition of $x_n$'s and continuity of $f$ tells you that $f(x)=x$. Uniqueness follows easily by MVT.
$endgroup$
$begingroup$
Thank you! This is very helpful :-)
$endgroup$
– Grace
7 hours ago
add a comment |
$begingroup$
The Mean Value Theorem tells you that the sequence ${x_n }$ is Cauchy because $|f(y)-f(x)| leq t|y-x|$. The space $[0, 1]$ is complete, so since the sequence is Cauchy, it must converge.
$endgroup$
add a comment |
$begingroup$
This can be proved using the Banach Fixed Point Theorem.
Intuitively, the BFPT tells us that if there is some function $F$ such that the distance between any two points $x$ and $y$ (when scaled by a constant $q$) is always larger than the distance between the corresponding images ($F(x)$ and $F(y)$), then the sequence
$$x_n = F(x_{n-1}) $$
will converge to a unique fixed point. For a more rigorous treatment of the BFPT statement: https://en.wikipedia.org/wiki/Banach_fixed-point_theorem.
Since in this case you know that
$$|f'(x)| leq t $$
This implies that
$$Big|frac{f(x) - f(y)}{x - y}Big| leq t$$
for all possible points $x,y in [a,b]$. Think about why this is the case (Hint: Use the mean value theorem).
This implies that
$$| f(x) - f(y)| < t |x-y| $$
which is what the BFPT requires. From here, we can just apply the BFPT to state that there is a fixed point in $[a,b]$ for the sequence
$$ x_n = f(x_{n-1})$$
$endgroup$
$begingroup$
Should probably expressly mention that the space $[0, 1]$ is complete, since that is a necessary condition for the Banach fixed point theorem to hold. For an easy counterexample demonstrating that you need completeness, consider $f(x) = x/2$ on $(0, 1]$.
$endgroup$
– Robert Shore
17 hours ago
$begingroup$
@RobertShore Yes, you are right, thanks!
$endgroup$
– Sean Lee
17 hours ago
add a comment |
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
To prove this from scratch note that by MVT $$|x_n-x_m| leq |x_{m+1}-x_m|+|x_{m+2}-x_{m+1}|$$ $$+cdots+|x_{n}-x_{n-1}|leq |x_{m+1}-x_m| (1+t+t^{2}+cdots+t^{n+m-1})$$ for $n >m$. Also $|x_{m+1}-x_m| leq t^{m-1} |x_2-x_1|$. Using the convergence of the geometric series $sum t^{n}$ conclude that ${x_n}$ is Cauchy. If $x =lim x_n$ then the definition of $x_n$'s and continuity of $f$ tells you that $f(x)=x$. Uniqueness follows easily by MVT.
$endgroup$
$begingroup$
Thank you! This is very helpful :-)
$endgroup$
– Grace
7 hours ago
add a comment |
$begingroup$
To prove this from scratch note that by MVT $$|x_n-x_m| leq |x_{m+1}-x_m|+|x_{m+2}-x_{m+1}|$$ $$+cdots+|x_{n}-x_{n-1}|leq |x_{m+1}-x_m| (1+t+t^{2}+cdots+t^{n+m-1})$$ for $n >m$. Also $|x_{m+1}-x_m| leq t^{m-1} |x_2-x_1|$. Using the convergence of the geometric series $sum t^{n}$ conclude that ${x_n}$ is Cauchy. If $x =lim x_n$ then the definition of $x_n$'s and continuity of $f$ tells you that $f(x)=x$. Uniqueness follows easily by MVT.
$endgroup$
$begingroup$
Thank you! This is very helpful :-)
$endgroup$
– Grace
7 hours ago
add a comment |
$begingroup$
To prove this from scratch note that by MVT $$|x_n-x_m| leq |x_{m+1}-x_m|+|x_{m+2}-x_{m+1}|$$ $$+cdots+|x_{n}-x_{n-1}|leq |x_{m+1}-x_m| (1+t+t^{2}+cdots+t^{n+m-1})$$ for $n >m$. Also $|x_{m+1}-x_m| leq t^{m-1} |x_2-x_1|$. Using the convergence of the geometric series $sum t^{n}$ conclude that ${x_n}$ is Cauchy. If $x =lim x_n$ then the definition of $x_n$'s and continuity of $f$ tells you that $f(x)=x$. Uniqueness follows easily by MVT.
$endgroup$
To prove this from scratch note that by MVT $$|x_n-x_m| leq |x_{m+1}-x_m|+|x_{m+2}-x_{m+1}|$$ $$+cdots+|x_{n}-x_{n-1}|leq |x_{m+1}-x_m| (1+t+t^{2}+cdots+t^{n+m-1})$$ for $n >m$. Also $|x_{m+1}-x_m| leq t^{m-1} |x_2-x_1|$. Using the convergence of the geometric series $sum t^{n}$ conclude that ${x_n}$ is Cauchy. If $x =lim x_n$ then the definition of $x_n$'s and continuity of $f$ tells you that $f(x)=x$. Uniqueness follows easily by MVT.
answered 16 hours ago
![](https://i.stack.imgur.com/hmDQO.jpg?s=32&g=1)
![](https://i.stack.imgur.com/hmDQO.jpg?s=32&g=1)
Kavi Rama MurthyKavi Rama Murthy
65.4k42766
65.4k42766
$begingroup$
Thank you! This is very helpful :-)
$endgroup$
– Grace
7 hours ago
add a comment |
$begingroup$
Thank you! This is very helpful :-)
$endgroup$
– Grace
7 hours ago
$begingroup$
Thank you! This is very helpful :-)
$endgroup$
– Grace
7 hours ago
$begingroup$
Thank you! This is very helpful :-)
$endgroup$
– Grace
7 hours ago
add a comment |
$begingroup$
The Mean Value Theorem tells you that the sequence ${x_n }$ is Cauchy because $|f(y)-f(x)| leq t|y-x|$. The space $[0, 1]$ is complete, so since the sequence is Cauchy, it must converge.
$endgroup$
add a comment |
$begingroup$
The Mean Value Theorem tells you that the sequence ${x_n }$ is Cauchy because $|f(y)-f(x)| leq t|y-x|$. The space $[0, 1]$ is complete, so since the sequence is Cauchy, it must converge.
$endgroup$
add a comment |
$begingroup$
The Mean Value Theorem tells you that the sequence ${x_n }$ is Cauchy because $|f(y)-f(x)| leq t|y-x|$. The space $[0, 1]$ is complete, so since the sequence is Cauchy, it must converge.
$endgroup$
The Mean Value Theorem tells you that the sequence ${x_n }$ is Cauchy because $|f(y)-f(x)| leq t|y-x|$. The space $[0, 1]$ is complete, so since the sequence is Cauchy, it must converge.
edited 17 hours ago
answered 17 hours ago
Robert ShoreRobert Shore
2,079116
2,079116
add a comment |
add a comment |
$begingroup$
This can be proved using the Banach Fixed Point Theorem.
Intuitively, the BFPT tells us that if there is some function $F$ such that the distance between any two points $x$ and $y$ (when scaled by a constant $q$) is always larger than the distance between the corresponding images ($F(x)$ and $F(y)$), then the sequence
$$x_n = F(x_{n-1}) $$
will converge to a unique fixed point. For a more rigorous treatment of the BFPT statement: https://en.wikipedia.org/wiki/Banach_fixed-point_theorem.
Since in this case you know that
$$|f'(x)| leq t $$
This implies that
$$Big|frac{f(x) - f(y)}{x - y}Big| leq t$$
for all possible points $x,y in [a,b]$. Think about why this is the case (Hint: Use the mean value theorem).
This implies that
$$| f(x) - f(y)| < t |x-y| $$
which is what the BFPT requires. From here, we can just apply the BFPT to state that there is a fixed point in $[a,b]$ for the sequence
$$ x_n = f(x_{n-1})$$
$endgroup$
$begingroup$
Should probably expressly mention that the space $[0, 1]$ is complete, since that is a necessary condition for the Banach fixed point theorem to hold. For an easy counterexample demonstrating that you need completeness, consider $f(x) = x/2$ on $(0, 1]$.
$endgroup$
– Robert Shore
17 hours ago
$begingroup$
@RobertShore Yes, you are right, thanks!
$endgroup$
– Sean Lee
17 hours ago
add a comment |
$begingroup$
This can be proved using the Banach Fixed Point Theorem.
Intuitively, the BFPT tells us that if there is some function $F$ such that the distance between any two points $x$ and $y$ (when scaled by a constant $q$) is always larger than the distance between the corresponding images ($F(x)$ and $F(y)$), then the sequence
$$x_n = F(x_{n-1}) $$
will converge to a unique fixed point. For a more rigorous treatment of the BFPT statement: https://en.wikipedia.org/wiki/Banach_fixed-point_theorem.
Since in this case you know that
$$|f'(x)| leq t $$
This implies that
$$Big|frac{f(x) - f(y)}{x - y}Big| leq t$$
for all possible points $x,y in [a,b]$. Think about why this is the case (Hint: Use the mean value theorem).
This implies that
$$| f(x) - f(y)| < t |x-y| $$
which is what the BFPT requires. From here, we can just apply the BFPT to state that there is a fixed point in $[a,b]$ for the sequence
$$ x_n = f(x_{n-1})$$
$endgroup$
$begingroup$
Should probably expressly mention that the space $[0, 1]$ is complete, since that is a necessary condition for the Banach fixed point theorem to hold. For an easy counterexample demonstrating that you need completeness, consider $f(x) = x/2$ on $(0, 1]$.
$endgroup$
– Robert Shore
17 hours ago
$begingroup$
@RobertShore Yes, you are right, thanks!
$endgroup$
– Sean Lee
17 hours ago
add a comment |
$begingroup$
This can be proved using the Banach Fixed Point Theorem.
Intuitively, the BFPT tells us that if there is some function $F$ such that the distance between any two points $x$ and $y$ (when scaled by a constant $q$) is always larger than the distance between the corresponding images ($F(x)$ and $F(y)$), then the sequence
$$x_n = F(x_{n-1}) $$
will converge to a unique fixed point. For a more rigorous treatment of the BFPT statement: https://en.wikipedia.org/wiki/Banach_fixed-point_theorem.
Since in this case you know that
$$|f'(x)| leq t $$
This implies that
$$Big|frac{f(x) - f(y)}{x - y}Big| leq t$$
for all possible points $x,y in [a,b]$. Think about why this is the case (Hint: Use the mean value theorem).
This implies that
$$| f(x) - f(y)| < t |x-y| $$
which is what the BFPT requires. From here, we can just apply the BFPT to state that there is a fixed point in $[a,b]$ for the sequence
$$ x_n = f(x_{n-1})$$
$endgroup$
This can be proved using the Banach Fixed Point Theorem.
Intuitively, the BFPT tells us that if there is some function $F$ such that the distance between any two points $x$ and $y$ (when scaled by a constant $q$) is always larger than the distance between the corresponding images ($F(x)$ and $F(y)$), then the sequence
$$x_n = F(x_{n-1}) $$
will converge to a unique fixed point. For a more rigorous treatment of the BFPT statement: https://en.wikipedia.org/wiki/Banach_fixed-point_theorem.
Since in this case you know that
$$|f'(x)| leq t $$
This implies that
$$Big|frac{f(x) - f(y)}{x - y}Big| leq t$$
for all possible points $x,y in [a,b]$. Think about why this is the case (Hint: Use the mean value theorem).
This implies that
$$| f(x) - f(y)| < t |x-y| $$
which is what the BFPT requires. From here, we can just apply the BFPT to state that there is a fixed point in $[a,b]$ for the sequence
$$ x_n = f(x_{n-1})$$
answered 17 hours ago
Sean LeeSean Lee
493211
493211
$begingroup$
Should probably expressly mention that the space $[0, 1]$ is complete, since that is a necessary condition for the Banach fixed point theorem to hold. For an easy counterexample demonstrating that you need completeness, consider $f(x) = x/2$ on $(0, 1]$.
$endgroup$
– Robert Shore
17 hours ago
$begingroup$
@RobertShore Yes, you are right, thanks!
$endgroup$
– Sean Lee
17 hours ago
add a comment |
$begingroup$
Should probably expressly mention that the space $[0, 1]$ is complete, since that is a necessary condition for the Banach fixed point theorem to hold. For an easy counterexample demonstrating that you need completeness, consider $f(x) = x/2$ on $(0, 1]$.
$endgroup$
– Robert Shore
17 hours ago
$begingroup$
@RobertShore Yes, you are right, thanks!
$endgroup$
– Sean Lee
17 hours ago
$begingroup$
Should probably expressly mention that the space $[0, 1]$ is complete, since that is a necessary condition for the Banach fixed point theorem to hold. For an easy counterexample demonstrating that you need completeness, consider $f(x) = x/2$ on $(0, 1]$.
$endgroup$
– Robert Shore
17 hours ago
$begingroup$
Should probably expressly mention that the space $[0, 1]$ is complete, since that is a necessary condition for the Banach fixed point theorem to hold. For an easy counterexample demonstrating that you need completeness, consider $f(x) = x/2$ on $(0, 1]$.
$endgroup$
– Robert Shore
17 hours ago
$begingroup$
@RobertShore Yes, you are right, thanks!
$endgroup$
– Sean Lee
17 hours ago
$begingroup$
@RobertShore Yes, you are right, thanks!
$endgroup$
– Sean Lee
17 hours ago
add a comment |
$begingroup$
Another related question.
$endgroup$
– rtybase
17 hours ago
$begingroup$
Welcome to Mathematics Stack Exchange! A quick tour will enhance your experience. Here are helpful tips to write a good question and write a good answer.
$endgroup$
– dantopa
15 hours ago