1

For example, the function $f(x)=x^2$ has fixed points $(0,0)$ and $(1,1)$, but the algorithm can only converge to $(0,0)$. Does anyone have a good explanation of why this is so?

NoChance
  • 6,427
Clay Lang
  • 11
  • 3
    Please be more clear about which algorithm you're talking about. – morrowmh Feb 20 '23 at 00:09
  • The idea is that to solve the equation f(x)=x, you estimate the solution for x as x_0 and let x_1=f(x_0), x_2=f(x_1), x_3=f(x_2), etc. This should converge to an approximate solution for x. – Clay Lang Feb 20 '23 at 00:12
  • 1
    Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. – Community Feb 20 '23 at 00:14
  • 1
    Because if you guess something between $0$ and $1$ and then square it, it will get smaller. Thus the iterations will go toward $0$, not $1$. – Randall Feb 20 '23 at 00:19
  • 1
    It's relatively easy to show that $x=0$ is an attracting fixed point and that $x=1$ is repelling using cobweb diagrams or the first derivative test. This is a typical homework exercise. – Brian Borchers Feb 20 '23 at 00:24
  • 1
    To add, it seems like you are talking about the fixed point theorem. Note that the theorem does not apply here as $f:x\mapsto x^2$ on $[0,1]$ does not satisfy the hypotheses of the fixed point theorem. – Andrew Feb 20 '23 at 00:25
  • @AndrewZhang what fp theorem are you talking about? – Randall Feb 20 '23 at 00:25
  • The contraction mapping theorem – Andrew Feb 20 '23 at 00:27
  • 1
    Read about attractors. Point (0,0) is an attractor, while (1,1) is an unstable equilibrium. – John Alexiou Feb 20 '23 at 13:15
  • 1
    Also, this link talks about attractors and repellers. – John Alexiou Feb 20 '23 at 13:37

1 Answers1

0

It can be easily shown that if $z$ is a fixed point of $f$ and $|f'(z)|>1$, the fixed point method, $x_{n+1} = f(x_n)$ cannot converge to $z$, unless by chance we have that $x_k = k$ for some $k$ (and, even then, round-off errors can prevent convergence).

What is behind this fact is that, for differentiable $f$, there will be a neighbourhood of $z$ where $|f'|>1$ and so, for large enough $n$, we have that $$ |x_{n+1} - z| = |g'(\xi)||x_n-z| > |x_n-z|, \quad \xi \in [x_n, z], $$

so the error is increasing, implying that there is no convergence.

This is the case in your example, where we have that $f'(1)=2$.

PierreCarre
  • 20,974
  • 1
  • 18
  • 34