2
$\begingroup$

I was going through the contraction mapping theorem in my book where it says, that if $\phi: G\to G$ is a contraction, then $\phi$ has a unique fixed point $\alpha$ on $G$.

Sequence {$x_n$}, $x_{n+1} = \phi(x_n) $ for $n=0,1,2...$ converges to $\alpha$ with $$|x_n - \alpha |\leq\frac{\lambda^n }{1- \lambda} |x_1 - x_0| $$ for n=1,2,3,4....

Can a contraction have only a unique fixed point? Cannot there be multiple fixed points? Like this?

enter image description here

Or cannot it have any fixed points at all?

enter image description here

$\endgroup$
  • 4
    $\begingroup$ Look at the slope of the red curve at the first intersection point. It's greater than 1. This means, points near that intersection point, you'll have $|x-y| < |f(x)-f(y)|$ and so it can't be a contraction. $\endgroup$ – aes Mar 7 '15 at 6:07
  • $\begingroup$ @aes got it, thanks $\endgroup$ – S.Dan Mar 7 '15 at 6:18
  • $\begingroup$ @aes I added another part to the question, again there must be something wrong with it, just can;t figure it out myself $\endgroup$ – S.Dan Mar 7 '15 at 6:27
  • 2
    $\begingroup$ The range is not a subset of the domain in your second image. This is required; it needs to be a map $f: X \rightarrow X$. $\endgroup$ – aes Mar 7 '15 at 7:29
9
$\begingroup$

Yes, a contraction has a unique fixed point. Proof: Let $d(\cdot,\cdot)$ be our distance function (which is absolute value on the real numbers, but works in more general settings).

Assume $\phi$ is a contraction and $a,b$ are both fixed points. Let $0<k<1$ be our contraction constant. Then $d(g(a),g(b))<k\cdot d(a,b)$, since it's a contraction, but $g(a)=a,g(b)=b$, so $d(g(a),g(b))=d(a,b)$, hence $d(a,b)<k\cdot d(a,b)$, which is only possible if $d(a,b)=0$, hence $a=b$.

$\endgroup$
7
$\begingroup$

If you have two fixed points $a,b$, you have $\phi(a)=a, \phi(b)=b$, so $|\phi(a)-\phi(b)|=|a-b|$, violating the requirement of a contraction that $|\phi(a)-\phi(b)| \lt |a-b|$

$\endgroup$
  • $\begingroup$ Added another part to the question. Can it have zero fixed points? $\endgroup$ – S.Dan Mar 7 '15 at 6:27
  • $\begingroup$ No, it has to have exactly one fixed point if the range is within the domain. If the domain is $[c,d]$ we must have $\phi(c)-c \ge 0, \phi(d)-d \le 0$ and the intermediate value theorem guarantees a root of $\phi(x)-x$ $\endgroup$ – Ross Millikan Mar 7 '15 at 14:28
5
$\begingroup$

If $a'$ and $a$ are fixed points, then $d(f(a'),f(a))=d(a',a)<\lambda d(a',a)$ with $0<\lambda <1$, which implies that $d(a,a')=0$ and hence $a=a'$.

$\endgroup$
3
$\begingroup$

A contraction mapping can never have more than one fixed point: if $a,b$ are both fixed points, then $d(a,b)=d(f(a),f(b))\leq \lambda d(a,b)$. This is only possible if $d(a,b)=0$.

On the other hand, by Banach fixed-point theorem, any contraction mapping of a complete metric space into itself has a fixed point. The proof is fairly straightforward: for any $x$, successive applications of the contraction to $x$ yield a Cauchy sequence, which converges by completeness, and by continuity the limit must be a fixed point.

The hypothesis of completeness is necessary, for example consider the map $x\mapsto x/2$ on $(0,1)$ with standard metric. It is a contraction mapping without any fixed points. Of course, there is a fixed point in the completion, namely $0$.

$\endgroup$
1
$\begingroup$

You seem to be a bit confused about how to think of a contraction as a line on a graph. Let's assume that we are looking for a contraction on $[0,1]$, though we could use any complete subset of the reals (or even the real line itself.

Intuitively, we have:

  • The line $y=x$ plotted on $[0,1]$ (so $x,y\in[0,1]$).

Then a curve corresponding to a contraction is one such that:

  • The curve corresponds to a function $y=f(x)$ for $0\le x\le1$.
  • The curve's $x$ and $y$ values never leave the square $[0,1]\times[0,1]$ - in other words, we always have $0\le x\le1,0\le y\le1$.
  • The slope of the curve is bounded above by some fixed constant $\lambda<1$.

Then the curve has a unique intersection with $y=x$; i.e., there is a unique point such that $x=f(x)$. For example:

enter image description here

Of course, we don't require the curve to be differentiable in general, so it might not always make sense to talk about the 'slope' of the curve, but that's what you should have in mind.

Your curves don't count as contraction mappings - the first one has slope greater than $1$ at some points, and the second leaves the square given by $0\le x\le1,0\le y\le1$, which is not allowed

$\endgroup$

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.