Let $f(x)$ be $x^2-x-2$. I want to find the root using FPI in an interval where it will converge. I have chosen $g(x)=x^2-2$ and so $g'(x)=2x$. The convergence condition, $|g'(x)|<1$ is obviously satisfied in $-0.5<x<0.5$.

Problem: I have failed to find a consistent interval outside of this convergence interval up to $\pm 1$ for which the iteration consistently diverges.

Question: Does this convergence condition only guarantee convergence (in the bounds) but not divergence (outside the bounds)?

  • $\begingroup$ Is that fixed-point iteration fixed? From $x^2=2+x$ one finds the better iteration $x_{n+1}=\sqrt{2+x_n}$ for the positive root. $\endgroup$ – LutzL Apr 16 at 16:25
  • $\begingroup$ Yes, but I thought the reason it’s ‘better’ is because it satisfies abs(g’(x))<1 in some interval. But g(x) in op works just fine up to -+1. $\endgroup$ – AKubilay Apr 16 at 18:10
  • $\begingroup$ $g(x)=\sqrt{2+x}$ has $g'(x)=\frac1{2\sqrt{2+x}}\le\frac25$ for all $x>0$, $g(x)=1+\frac2x$ has $g'(x)=-\frac{2}{x^2}>-1$ for $x>\frac32$, so you get intervals with $|g'(x)|<1$ for many fixed-point functions. $\endgroup$ – LutzL Apr 16 at 18:53

Let us consider the fixed point iterations associated to the function $g: x \mapsto x^2-2$, defined by the quadratic map $$ x_{n+1} = {x_n}^2 - 2, \qquad x_0 \in \Bbb R . $$ This map has many periodic points, even with large period. The period-one fixed points $-1$, $2$ are both repelling fixed points (indices $2>1$ and $4>1$, respectively). Thus, fixed-point iterations will not converge towards these values unless the starting value $x_0$ is exactly equal to $-1$ or $2$. Setting $y_n = -\frac{1}{4} x_n + \frac{1}{2}$, the logistic map $y_{n+1} = r y_n (1-y_n)$ with parameter $r=4$ is obtained, which exact solution is bounded and exhibits chaotic behavior (see also this article). Therefore, $$ x_n = 2\cos\left(2^n\cos^{-1}(x_0/2)\right) $$ is bounded and exhibits chaotic behavior too (the sequence does not diverge to infinity).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.