How to use fixed point theorems

a repository of mathematical know-how

How to use fixed point theorems

Title: *

Area of mathematics: *

A comma-separated list of areas of mathematics to which this article applies. Use ">" to tag in a subcategory. Example: Analysis > Harmonic analysis, Combinatorics

Keywords:

A comma-separated list of keywords associated with this article. Example: free group

Used in:

A comma-separated list of examples of where this technique is used. Example: Cauchy-Schwarz inequality

Parent articles:		Order

Body:

[QUICK DESCRIPTION]
Let $X$ be a set and let $f$ be a function from $X$ to $X$. A ''fixed point'' of $f$ is an element $x\in X$ such that $f(x)=x$. A ''fixed point theorem'' is a theorem that asserts that every function that satisfies some given property must have a fixed point. If you have an equation and want to prove that it has a solution, and if it is hard to find that solution explicitly, then consider trying to rewrite the equation in the form $f(x)=x$ and applying a fixed point theorem. This method can be applied not just to numerical equations but also to equations involving vectors or functions. In particular, fixed point theorems are often used to prove the existence of solutions to differential equations.

[PREREQUISITES]
A knowledge of some of the main fixed point theorems (though these are also discussed in the article, and links are given to Wikipedia articles about them).

[note article incomplete] There should be several examples. In particular, there should be at least one example for each of the fixed point theorems mentioned below. [/note]

[GENERAL DISCUSSION]
Some of the major fixed point theorems that can be used in analysis and topology: the [[w:Brouwer fixed point theorem]], the [[w:Lefschetz fixed-point theorem|Lefschetz fixed point theorem]], the [[w:contraction mapping theorem]], and the [[w:Schauder fixed point theorem]].

[EXAMPLE]
Let $A$ be an $n\times n$ matrix with non-negative entries. A result with many applications is that $A$ must have an [[w:eigenvector]] with non-negative coefficients.

To prove this, let $S$ be the subset of $\R^n$ that consists of all vectors $(x_1,\dots,x_n)$ such that each $x_i$ is non-negative and $x_1+\dots+x_n=1$. If there exists $x\in S$ such that $Ax=0$, then we are done. Otherwise, we know that for every $x\in S$, $Ax$ has non-negative entries, not all of them zero. Let us write $|Ax|$ for the sum of the coefficients of $Ax$. Then the map $\phi:x\mapsto Ax/|Ax|$ is a continuous map from $S$ to $S$.

Now geometrically $S$ is a simplex of dimension $n-1$, and therefore it is homeomorphic to a ball of dimension $n-1$. The [[w:Brouwer fixed point theorem]] implies that $\phi$ has a fixed point, so there must be some $x$ such that $Ax=|Ax|x$. This $x$ is an eigenvector with eigenvalue $|Ax|$, so the result is proved.

[EXAMPLE]
Let $X$ be a [[w:Banach space]], and let $B$ and $A$ be linear operators on $X$.
If $A$ is invertible and $\Vert B-A\Vert\cdot\Vert A^{-1}\Vert <1$, then the [[w:Contraction Mapping Theorem]] can be used to show that $B$ is also invertible.
Informally, this says that if $B$ closely approximates an invertible operator, then $B$ is invertible.

To show that $B$ is invertible, we will show that for each $y$ in $X$, there is a unique $x$ such that $Bx=y$.
Let $y$ be an element of $X$.
If $Bx_0=y$ for some $x_0$ in $X$, then we have $y=Bx_0=(B-A)x_0+Ax_0$.
Multiplying by $A^{-1}$, we have $A^{-1}y=A^{-1}(B-A)x_0+x_0$.
To simplify notation, write $z=A^{-1}y$ and $C=A^{-1}(B-A)$, so that $x_0=z-Cx_0$.

Now we'll define a function $f$ on $X$ by $f(x)=z-Cx$.
If we can show that $f$ is a contraction mapping, then the fixed point of $f$ will be $x_0$, as $f(x)=x$ gives us $x=z-Cx$.

Let $x$ and $y$ be elements of $X$.
Then $\vert f(x)-f(y)\vert = \vert C(x-y)\vert \leq \Vert A^{-1}\Vert\cdot\Vert B-A\Vert\,\vert x-y\vert$.
By assumption, $\Vert B-A\Vert\cdot\Vert A^{-1}\Vert<1$, so $f$ is a contraction mapping, which gives us the desired fixed point $x_0$.

The proof of the contraction mapping theorem proceeds by iterating the contraction. In this case, since the contraction is a linear map, one can do this explicitly and see what one obtains. The first few iterates of the function $f$ above are $z-Cx$, $z-C(z-Cx)=z-Cz+C^2x$, $z-Cz+C^2z-C^3x$, and we see that, because $\|C\|<1$, this sequence is converging to the point $z-Cz+C^2z-C^3z+\dots$.

If $A$ is the identity and $\|C\|<1$, then this is particularly easy to see directly: the inverse of $I+C$ is $I-C+C^2-C^3+\dots$, and one can justify it by noting that $(I+C)(I-C+C^2-\dots+(-1)^nC^n)=I-C^{n+1}$, which converges to $I$. One can deduce the general case from this too, since $A+(B-A)=A(I+A^{-1}(B-A))$. Therefore, the contraction mapping theorem is not essential in this example.

[note attention] It would be nice to have an example of the contraction mapping theorem applied in a less linear context so that one can't just write down a solution anyway. [/note]

This is a stub

A stub is an article that is not sufficiently complete to be interesting.

Notifications

File attachments

Changes made to the attachments are not permanent until you save this post. The first "listed" file will be included in RSS feeds.

Attach new file:

Images are larger than 640x480 will be resized. The maximum upload size is 1 MB. Only files with the following extensions may be uploaded: jpg jpeg gif png svg.

Revision information

Log message:

An explanation of the additions or updates being made to help other authors understand your motivations.

How to use fixed point theorems

Recent articles

Active forum topics

Recent comments