−1 (number): Difference between revisions
en>EmausBot m r2.7.3) (Robot: Adding tr:−1 (sayı) |
No edit summary |
||
Line 1: | Line 1: | ||
:''Not to be confused with a [[stationary point]] where f'''(''x'') = 0''.'' | |||
:''Not to be confused with [[fixed-point arithmetic]], a form of limited-precision arithmetic in computing.'' | |||
[[Image:Fixed point example.svg|thumb|right|A function with three fixed points]] | |||
In [[mathematics]], a '''fixed point''' (sometimes shortened to '''fixpoint''', also known as an '''invariant point''') of a [[function (mathematics)|function]] is an element of the function's [[Domain of a function|domain]] that is mapped to itself by the function. A set of fixed points is sometimes called a ''fixed set''. That is to say, ''c'' is a fixed point of the function ''f''(''x'') [[if and only if]] ''f''(''c'') = ''c''. This means ''f''(''f''(...''f''(''c'')...)) = ''f<sup>n</sup>''(''c'') = ''c'', an important terminating consideration when recursively computing ''f''. | |||
For example, if ''f'' is defined on the [[real number]]s by | |||
:<math>\ f(x) = x^2 - 3 x + 4,</math> | |||
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 a function|graph]] of ''f'' has a point in common with that line. | |||
Points which come back to the same value after a finite number of [[iterated function|iterations]] of the function are known as [[periodic point]]s; a fixed point is a periodic point with period equal to one. In [[projective geometry]], a fixed point of a [[collineation]] is called a ''double point''.<ref>[[H. S. M. Coxeter]] (1942) ''Non-Euclidean Geometry'', page 36, [[University of Toronto Press]]</ref> | |||
==Attractive fixed points== | |||
[[Image:Cosine fixed point.svg|250px|thumb|The [[fixed point iteration]] ''x''<sub>''n''+1</sub> = cos ''x''<sub>''n''</sub> with initial value ''x''<sub>1</sup> = -1.]] | |||
An ''attractive fixed point'' of a function ''f'' is a fixed point ''x''<sub>0</sub> of ''f'' such that for any value of ''x'' in the domain that is close enough to ''x''<sub>0</sub>, the [[iterated function]] sequence | |||
:<math>x,\ f(x),\ f(f(x)),\ f(f(f(x))), \dots</math> | |||
[[Limit of a sequence|converges]] to ''x''<sub>0</sub>. An expression of prerequisites and proof of the existence of such solution is given by [[Banach fixed point theorem]]. | |||
The natural [[cosine]] function ("natural" means in [[radian]]s, 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 (checking first that the calculator is in "radians" mode). It eventually converges to about 0.739085133, which is a fixed point. That is where the graph of the cosine function intersects the line <math>y = x</math>. | |||
Not all fixed points are attractive: for example, ''x'' = 0 is a fixed point of the function ''f''(''x'') = 2''x'', 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''<sub>0</sub>, and <math>|f\,'(x_0)|<1</math>, attraction is guaranteed. | |||
Attractive fixed points are a special case of a wider mathematical concept of [[attractor]]s. | |||
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 differential equation#Homogeneous equations with constant coefficients|linear homogeneous differential equation]] of the second order is an example of a neutrally stable fixed point. | |||
==Applications== | |||
In many fields, equilibria or [[stability theory|stability]] are fundamental concepts that can be described in terms of fixed points. For example, in [[economics]], a [[Nash equilibrium]] of a [[game theory|game]] is a fixed point of the game's [[best response|best response correspondence]]. However, in physics, more precisely in the [[Phase Transition|theory of Phase Transitions]], ''linearisation'' near an ''unstable'' fixed point has led to [[Kenneth G. Wilson|Wilson]]'s Nobel prize-winning work inventing the [[renormalization group]], and to the mathematical explanation of the term "[[critical phenomenon]]". | |||
In [[compilers]], fixed point computations are used for whole program analysis, which are often required to do code [[Optimization (computer science)|optimization]].{{Citation needed|date=January 2012}} | |||
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 [[Countable set|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. | |||
The concept of fixed point can be used to define the [[Limit of a function|convergence]] of a function. | |||
==Topological fixed point property== | |||
{{main|Fixed point property}} | |||
A [[topological space]] <math>X</math> is said to have the ''fixed point property'' (briefly FPP) if for any [[continuous function]] | |||
:<math>f\colon X \to X</math> | |||
there exists <math>x \in X</math> such that <math>f(x)=x</math>. | |||
The FPP is a [[topological invariant]], i.e. is preserved by any [[homeomorphism]]. The FPP is also preserved by any [[Retract#Retract|retraction]]. | |||
According to the [[Brouwer fixed point theorem]], every [[compact space|compact]] and [[convex set|convex]] subset of a [[euclidean space]] has the FPP. Compactness 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 [[Karol Borsuk|Borsuk]] asked whether compactness together with [[contractible space|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 [[Shin'ichi Kinoshita|Kinoshita]] who found an example of a compact contractible space without the FPP.<ref>Kinoshita, S. On Some Contractible Continua without Fixed Point Property. ''Fund. Math.'' '''40''' (1953), 96–98</ref> | |||
== Generalization to partial orders: prefixpoint and postfixpoint == | |||
The notion and terminology is generalized to a [[partial order]]. Let ≤ be a partial order over a set ''X'' and let ''f'':''X'' → ''X'' be a function over ''X''. Then a '''prefixpoint''' (also spelled '''pre-fixpoint''') of ''f'' is any ''p'' such that ''f''(''p'') ≤ ''p''. Analogously a '''postfixpoint''' (or '''post-fixpoint''') of ''f'' is any ''p'' such that ''p'' ≤ ''f''(''p'').<ref name="DaveyPriestley2002">{{cite book|author1=B. A. Davey|author2=H. A. Priestley|title=Introduction to Lattices and Order|url=http://books.google.com/books?id=vVVTxeuiyvQC&pg=PA182|year=2002|publisher=Cambridge University Press|isbn=978-0-521-78451-1|page=182}}</ref> One way to express the [[Knaster–Tarski theorem]] is to say that a [[monotone function]] on a [[complete lattice]] has a [[least fixpoint]] which coincides with its least prefixpoint (and similarly its greatest fixpoint coincides with its greatest postfixpoint). Prefixpoints and postfixpoints have applications in [[theoretical computer science]].<ref>Yde Venema (2008) [http://staff.science.uva.nl/~yde/teaching/ml/mu/mu2008.pdf Lectures on the Modal μ-calculus]</ref> | |||
==See also== | |||
<div style="-moz-column-count:3; column-count:3;"> | |||
*[[Eigenvector]] | |||
*[[equilibrium point|Equilibrium]] | |||
*[[Attractor]] | |||
*[[Stability theory]] | |||
*[[Stationary point]] | |||
*[[Möbius transformation#Fixed points|Normal form of Möbius transformation]] | |||
*[[Invariant (mathematics)]] | |||
*[[Fixed-point combinator]] | |||
*[[Fixed point property]] | |||
*[[Idempotent]] | |||
*[[Fixed-point theorem]]s | |||
*[[Least fixed point]] and [[greatest fixed point]] | |||
*[[Nielsen theory]] | |||
*[[Sierpinski triangle]] | |||
</div> | |||
==Notes== | |||
{{reflist}} | |||
==External links== | |||
* [http://math.fullerton.edu/mathews/a2001/Animations/RootFinding/FixedPoint/FixedPoint.html Animations for Fixed Point Iteration] | |||
* [http://www.osaka-ue.ac.jp/zemi/nishiyama/math2010/fixedpoint.pdf An Elegant Solution for Drawing a Fixed Point] | |||
[[Category:Fixed points (mathematics)| ]] | |||
[[Category:Game theory]] |
Revision as of 10:26, 3 February 2014
- Not to be confused with a stationary point where f'(x) = 0.
- Not to be confused with fixed-point arithmetic, a form of limited-precision arithmetic in computing.
In mathematics, a fixed point (sometimes shortened to fixpoint, also known as an invariant point) of a function is an element of the function's domain that is mapped to itself by the function. A set of fixed points is sometimes called a fixed set. That is to say, c is a fixed point of the function f(x) if and only if f(c) = c. This means f(f(...f(c)...)) = fn(c) = c, an important terminating consideration when recursively computing f. For example, if f is defined on the real numbers by
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.
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. In projective geometry, a fixed point of a collineation is called a double point.[1]
Attractive fixed points
An attractive fixed point of a function f is a fixed point x0 of f such that for any value of x in the domain that is close enough to x0, the iterated function sequence
converges to x0. An expression of prerequisites and proof of the existence of such solution is given by Banach fixed point theorem.
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 (checking first that the calculator is in "radians" mode). It eventually converges to about 0.739085133, which is a fixed point. That is where the graph of the cosine function intersects the line .
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 x0, and , 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.
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. However, in physics, more precisely in the theory of Phase Transitions, linearisation near an unstable fixed point has led to Wilson's Nobel prize-winning work inventing the renormalization group, and to the mathematical explanation of the term "critical phenomenon".
In compilers, fixed point computations are used for whole program analysis, which are often required to do code optimization.Potter or Ceramic Artist Truman Bedell from Rexton, has interests which include ceramics, best property developers in singapore developers in singapore and scrabble. Was especially enthused after visiting Alejandro de Humboldt National Park.
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.
The concept of fixed point can be used to define the convergence of a function.
Topological fixed point property
Mining Engineer (Excluding Oil ) Truman from Alma, loves to spend time knotting, largest property developers in singapore developers in singapore and stamp collecting. Recently had a family visit to Urnes Stave Church. A topological space is said to have the fixed point property (briefly FPP) if for any continuous function
The FPP is a topological invariant, i.e. is preserved by any homeomorphism. The FPP is also preserved by any retraction.
According to the Brouwer fixed point theorem, every compact and convex subset of a euclidean space has the FPP. Compactness 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 together 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.[2]
Generalization to partial orders: prefixpoint and postfixpoint
The notion and terminology is generalized to a partial order. Let ≤ be a partial order over a set X and let f:X → X be a function over X. Then a prefixpoint (also spelled pre-fixpoint) of f is any p such that f(p) ≤ p. Analogously a postfixpoint (or post-fixpoint) of f is any p such that p ≤ f(p).[3] One way to express the Knaster–Tarski theorem is to say that a monotone function on a complete lattice has a least fixpoint which coincides with its least prefixpoint (and similarly its greatest fixpoint coincides with its greatest postfixpoint). Prefixpoints and postfixpoints have applications in theoretical computer science.[4]
See also
Notes
43 year old Petroleum Engineer Harry from Deep River, usually spends time with hobbies and interests like renting movies, property developers in singapore new condominium and vehicle racing. Constantly enjoys going to destinations like Camino Real de Tierra Adentro.
External links
- ↑ H. S. M. Coxeter (1942) Non-Euclidean Geometry, page 36, University of Toronto Press
- ↑ Kinoshita, S. On Some Contractible Continua without Fixed Point Property. Fund. Math. 40 (1953), 96–98
- ↑ 20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.
My blog: http://www.primaboinca.com/view_profile.php?userid=5889534 - ↑ Yde Venema (2008) Lectures on the Modal μ-calculus