Misplaced Pages

Revision as of 06:48, 2 April 2009

In mathematics, a fixed point (sometimes shortened to fixpoint) of a function is a point that is mapped to itself by the function. That is to say, x is a fixed point of the function f if and only if f(x) = x. For example, if f is defined on the real numbers by

${\displaystyle \ f(x)=x^{2}-3x+4,}$

then 2 is a fixed point of f, because f(2) = 2.

Not all functions have fixed points: for example, if f is a function defined on the real numbers as f(x) = x + 1, then it has no fixed points, since x is never equal to x + 1 for any real number. In graphical terms, a fixed point means the point (x, f(x)) is on the line y = x, or in other words the graph of f has a point in common with that line. The example f(x) = x + 1 is a case where the graph and the line are a pair of parallel lines.

Points which come back to the same value after a finite number of iterations of the function are known as periodic points; a fixed point is a periodic point with period equal to one.

Attractive fixed points

An attractive fixed point of a function f is a fixed point x₀ of f such that for any value of x in the domain that is close enough to x₀, the iterated function sequence

${\displaystyle x,\ f(x),\ f(f(x)),\ f(f(f(x))),\dots }$

converges to x₀. How close is "close enough" is sometimes a subtle question.

The natural cosine function ("natural" means in radians, not degrees or other units) has exactly one fixed point, which is attractive. In this case, "close enough" is not a stringent criterion at all -- to demonstrate this, start with any real number and repeatedly press the cos key on a calculator. It quickly converges to about 0.739085013, which is a fixed point. That is where the graph of the cosine function intersects the line ${\displaystyle y=x}$.

Not all fixed points are attractive: for example, x = 0 is a fixed point of the function f(x) = 2x, but iteration of this function for any value other than zero rapidly diverges. However, if the function f is continuously differentiable in an open neighbourhood of a fixed point x₀, and |f '(x₀)| < 1, attraction is guaranteed.

Attractive fixed points are a special case of a wider mathematical concept of attractors.

An attractive fixed point is said to be a stable fixed point if it is also Lyapunov stable.

A fixed point is said to be a neutrally stable fixed point if it is Lyapunov stable but not attracting. The center of a linear homogeneous differential equation of the second order is an example of a neutrally stable fixed point.

Theorems guaranteeing fixed points

There are numerous theorems in different parts of mathematics that guarantee that functions, if they satisfy certain conditions, have at least one fixed point. These are amongst the most basic qualitative results available: such fixed-point theorems that apply in generality provide valuable insights.

Convergence

A formal definition of convergence can be stated as follows. Suppose ${\displaystyle {{p}_{n}}}$ as ${\displaystyle n}$ goes from ${\displaystyle 0}$ to ${\displaystyle \infty }$ is a sequence that converges to ${\displaystyle p}$, with ${\displaystyle {p}_{n}\neq 0}$ for all ${\displaystyle n}$. If positive constants ${\displaystyle \lambda }$ and ${\displaystyle \alpha }$ exist with

${\displaystyle \lim _{n\rightarrow \infty }{\frac {\left|{p}_{n+1}-p\right|}{{\left|{p}_{n}-p\right|}^{\alpha }}}=\lambda }$

then ${\displaystyle {{p}_{n}}}$ as ${\displaystyle n}$ goes from ${\displaystyle 0}$ to ${\displaystyle \infty }$ converges to ${\displaystyle p}$ of order ${\displaystyle \alpha }$, with asymptotic error constant ${\displaystyle \lambda }$

There is a nice checklist for checking the convergence of a fixed point ${\displaystyle p}$ for a function ${\displaystyle f(x)=x}$.

1) First check that:

${\displaystyle f(p)=p}$

2) Check for linear convergence. Start by finding ${\displaystyle \left|f^{\prime }(p)\right|}$. If....

${\displaystyle \left|f^{\prime }(p)\right|\in (0,1]}$	then we have linear convergence
${\displaystyle \left|f^{\prime }(p)\right|>1}$	series diverges
${\displaystyle \left|f^{\prime }(p)\right|=0}$	then we have at least linear convergence and maybe something better, we should check for quadratic

3) If we find that we have something better than linear we should check for quadratic convergence. Start by finding ${\displaystyle \left|f^{\prime \prime }(p)\right|}$ If....

${\displaystyle \left|f^{\prime \prime }(p)\right|\neq 0}$	then we have quadratic convergence provided that ${\displaystyle f^{\prime \prime }(p)}$ is continuous
${\displaystyle \left|f^{\prime \prime }(p)\right|=0}$	then we have something even better than quadratic convergence
${\displaystyle \left|f^{\prime \prime }(p)\right|}$ does not exist	then we have convergence that is better than linear but still not quadratic

Applications

In many fields, equilibria or stability are fundamental concepts that can be described in terms of fixed points. For example, in economics, a Nash equilibrium of a game is a fixed point of the game's best response correspondence.

In compilers, fixed point computations are used for whole program analysis, which are often required to do code optimization. The vector of PageRank values of all web pages is the fixed point of a linear transformation derived from the World Wide Web's link structure.

Logician Saul Kripke makes use of fixed points in his influential theory of truth. He shows how one can generate a partially defined truth predicate (one which remains undefined for problematic sentences like "This sentence is not true"), by recursively defining "truth" starting from the segment of a language which contains no occurrences of the word, and continuing until the process ceases to yield any newly well-defined sentences. (This will take a denumerable infinity of steps.) That is, for a language L, let L-prime be the language generated by adding to L, for each sentence S in L, the sentence "S is true." A fixed point is reached when L-prime is L; at this point sentences like "This sentence is not true" remain undefined, so, according to Kripke, the theory is suitable for a natural language which contains its own truth predicate.

Topological fixed point property

A topological space ${\displaystyle X}$ is said to have the fixed point property (briefly FPP) if for any continuous function

${\displaystyle f:X\to X}$

there exists ${\displaystyle x\in X}$ such that ${\displaystyle f(x)=x}$.

The FPP is a topological invariant, i.e. is preserved by any homeomorphism. The PPF is also preserved by any retraction.

According to Brouwer fixed point theorem every compact and convex subset of an euclidean space do have the FPP. Compactnes alone does not imply the FPP and convexity is not even a topological property so it makes sense to ask how to topologically characterize the FPP. In 1932 Borsuk asked whether compactness togheter with contractibility could be a necessary and sufficient condition for the FPP to hold. The problem was open for 20 years until the conjecture was disproved by Kinoshita who found an example of a compact contractible space without the FPP.

See also

• Eigenvector
• Equilibrium
• Attractor
• Stability theory
• Stationary point
• Normal form of Möbius transformation
• Invariant (mathematics)
• Fixed point combinator
• Fixed point property
• Idempotent
• Fixed-point theorems
• Least fixed point and greatest fixed point
• Nielsen theory

References

1. Numerical Analysis, 8th Edition, Burden and Faires, Section 2.4 Error Analysis for Iterative Methods
2. Kinoshita, S. On Some Contractible Continua without Fixed Point Property. Fund. Math. 40 (1953), 96-98

External links

• Animations for Fixed Point Iteration

• Fixed points
• Game theory