# Convergent iteration

Printable View

• December 17th 2008, 04:38 PM
namelessguy
Convergent iteration
Can someone help me with this problem?
Consider the fixed point iteration
$x_{k+1}=(m+1)x_k-{x_k}^2$, k=0,1,2,...where $1\leq m \leq 2$
a) Show that the iteration converges for any initial guess $x_0$ satisfying $m-1/5 \leq x_0 \leq m+1/5$
b) Assume that the iteration converges, find m such that the method converges quadratically.

I think I got part a) by letting $g(x)=(m+1)x-x^2$, then take the derivative $g'(x)=2x+m+1$. I then show that there exists $0<k<1$ such that $\mid g'(x) \mid <k$, and by a theorem this implies the iteration converges for any initial guess in the specified interval.
For part b), I need to find m such that $lim_{k\to \infty} \frac{|x_{k+1}-x|}{|x_k-x|^2}= lim_{k\to \infty} \frac{|(m+1)x_k-{x_k}^2-x|}{|x_k-x|^2}$ exists, but I don't get anywhere from here. Hope someone can give a hand.
• December 17th 2008, 10:53 PM
CaptainBlack
Quote:

Originally Posted by namelessguy
Can someone help me with this problem?
Consider the fixed point iteration
$x_{k+1}=(m+1)x_k-{x_k}^2$, k=0,1,2,...where $1\leq m \leq 2$
a) Show that the iteration converges for any initial guess $x_0$ satisfying $m-1/5 \leq x_0 \leq m+1/5$
b) Assume that the iteration converges, find m such that the method converges quadratically.

I think I got part a) by letting $g(x)=(m+1)x-x^2$, then take the derivative $g'(x)=2x+m+1$. I then show that there exists $0<k<1$ such that $\mid g'(x) \mid <k$, and by a theorem this implies the iteration converges for any initial guess in the specified interval.
For part b), I need to find m such that $lim_{k\to \infty} \frac{|x_{k+1}-x|}{|x_k-x|^2}= lim_{k\to \infty} \frac{|(m+1)x_k-{x_k}^2-x|}{|x_k-x|^2}$ exists, but I don't get anywhere from here. Hope someone can give a hand.

Assuming that the itteration converges it is obvious it must converge to either $x=0$ or $x=m$, but it is easy to show that itteration will not converge to $x=0$.

So suppose $x_n=m+\varepsilon$

Then:

$x_{n+1}=(m+1)(m+\varepsilon)-(m_\varepsilon)^2=m+\varepsilon(1-m)-\varepsilon^2$

So if $m=1$ the itteration converges quadraticaly to $x=m=1$

CB
All times are GMT -8. The time now is 12:06 PM.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 25, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8900300860404968, "perplexity_flag": "head"}