Difference between revisions of "Fixed point"

From TORI
Jump to: navigation, search
 
m (Text replacement - "\$([^\$]+)\$" to "\\(\1\\)")
 
(2 intermediate revisions by 2 users not shown)
Line 1: Line 1:
  +
[[File:Tet5loplot.jpg|400px|thumb|Graphical search for the [[fixed point]]s of [[tetration]]; \(y\!=\!\mathrm{tet}_b(x)\) versus \(x\) for various \(b\) ]]
−
For a given function $f$, the '''fixed point''' is solution $L$ of equation
  
  +
For a given function \(f\), the '''fixed point''' is solution \(L\) of equation
−
:$(1) ~ ~ ~ ~ ~ ~ L = f(L)$
  
  +
:\((1) ~ ~ ~ ~ ~ ~ L = f(L)\)
−
In the simple case, $f$ is just [[holomorphic function]] of a single variable; then $L$ is assumed to be a [[complex number]].
 
  +
In the simple case, \(f\) is just [[holomorphic function]] of a single variable; then \(L\) is assumed to be a [[complex number]].
 
<ref name="fpcz">
  
<ref name="fpcz">
 
http://en.citizendium.org/wiki/Fixed_point
  
http://en.citizendium.org/wiki/Fixed_point
 
</ref>
  
</ref>
   
−
In the theory of [[linear operator]]s, for some operator $f$, the [[eigenfunction]] with eigenvalue unity is fixed point of operator $f$.
 +
In the theory of [[linear operator]]s, for some operator \(f\), the [[eigenfunction]] with eigenvalue unity is fixed point of operator \(f\).
   
 
==Examples==
  
==Examples==
   
−
In some cases, the [[inverse function]] $g=f^{-1}$ exists, and often the fixed point of function $f$ is also fixed point of function $g$, id est,
 +
In some cases, the [[inverse function]] \(g=f^{-1}\) exists, and often the fixed point of function \(f\) is also fixed point of function \(g\), id est,
−
:$(2) ~ ~ ~ ~ ~ ~ L=g(L)$
 +
:\((2) ~ ~ ~ ~ ~ ~ L=g(L)\)
−
For example, the fixed point of the [[logarithm]] is also fixed point of the [[exponential]], although not every fixed point of the exponential is also fixed point of logarithm.
+
The fixed point of the [[logarithm]] is also fixed point of the [[exponential]], although not every fixed point of the exponential is also fixed point of logarithm.
   
 
In many cases, the fixed point can be approximated by the straightforward iteration of equation (1) or equation (2).
  
In many cases, the fixed point can be approximated by the straightforward iteration of equation (1) or equation (2).
   
 
For example, the fixed point of exponential
  
For example, the fixed point of exponential
−
: $L = -\mathrm{ProductLog}(-1)^* \approx 0.3181315052047641+ 1.3372357014306895 \mathrm{i}$
 +
: \(L = -\mathrm{ProductLog}(-1)^* \approx 0.3181315052047641+ 1.3372357014306895 \mathrm{i}\)
 
can be evaluated iterating expression
  
can be evaluated iterating expression
−
: $L=\ln(L)$
 +
: \(L=\ln(L)\)
−
with initial approximation $L\approx\mathrm i$.
 +
with initial approximation \(L\approx\mathrm i\).
   
−
Fixed points of a [[transfer function]] $f$ are good choice as asymptotic s of the [[superfunction]] $F$;
 +
Fixed points of a [[transfer function]] \(f\) are good choice as asymptotic s of the [[superfunction]] \(F\);
−
fixed point $L$ of the exponential in the example above is asymptotic value of [[tetration]] tet:
 +
fixed point \(L\) of the exponential in the example above is asymptotic value of [[tetration]] tet:
−
:$(3) ~ ~ ~ ~ ~ \displaystyle
 +
:\((3) ~ ~ ~ ~ ~ \displaystyle
−
\lim_{y\rightarrow +\infty} \mathrm{tet}(x\!+\mathrm i y) = L ~ ~ ~ \forall x \in \mathbb R$
 +
\lim_{y\rightarrow +\infty} \mathrm{tet}(x\!+\mathrm i y) = L ~ ~ ~ \forall x \in \mathbb R\)
   
 
The [[Wolfram (software)]] offers the table of evaluations of some fixed points for some elementary functions
  
The [[Wolfram (software)]] offers the table of evaluations of some fixed points for some elementary functions
Line 37: Line 38:
 
This section is borrowed from there.
 
This section is borrowed from there.
   
−
A hyperbolic fixpoint is a [[fixpoint]] $a$ of $f$ such that $|f'(a)|\neq 0,1$.
 +
A hyperbolic fixpoint is a [[fixpoint]] \(a\) of \(f\) such that \(|f'(a)|\neq 0,1\).
   
−
For a locally analytic function with hyperbolic fixpoint at $0$, i.e. $f(z)=c_1 z + c_2z^2 + \dots$, $|c_1|\neq 0,1$, there is always a locally analytic and injective function $\sigma$ that satisfies the [[Schröder equation]]
 +
For a locally analytic function with hyperbolic fixpoint at \(0\), i.e. \(f(z)=c_1 z + c_2z^2 + \dots\), \(|c_1|\neq 0,1\), there is always a locally analytic and injective function \(\sigma\) that satisfies the [[Schröder equation]]
−
$$\sigma(f(z))=c_1 \sigma(z))$$
 +
<math>\sigma(f(z))=c_1 \sigma(z))\</math>
−
$\sigma$ is unique up to a multiplicative constant and is called the [[Schröder coordinates]] of $f$ at 0.
 +
\(\sigma\) is unique up to a multiplicative constant and is called the [[Schröder coordinates]] of \(f\) at 0.
   
 
Hyperbolic fixed points are good for application of the [[regular iteration]]
  
Hyperbolic fixed points are good for application of the [[regular iteration]]
Line 52: Line 53:
 
==References==
  
==References==
 
<references/>
  
<references/>
  +
  +
http://bruce-shapiro.com/math481A/notes/9-fixed-point.pdf
  +
ruce E. Shapiro, Ph.D. Math 481A Lecture Notes. Lesson 9. Fixed Point Iteration. (approx. 2011)
  +
  +
http://dbs.uni-leipzig.de/file/icde2002-sf.pdf
  +
Sergey Melnik,
  +
Hector Garcia-Molina,
  +
Erhard Rahm. Similarity Flooding: A Versatile Graph Matching Algorithm and its Application to Schema Matching.
  +
Proceedings of the 18th International Conference on Data Engineering (ICDEí02) 1063-6382/02 $17.00 © 2002 IEEE.
  +
.. In this paper we presented a simple structural algorithm based on fixpoint computation that is usable for matching of diverse data structures. ..
   
 
[[Category:Mathematical functions]]
  
[[Category:Mathematical functions]]

Latest revision as of 18:26, 30 July 2019

Graphical search for the fixed points of tetration; \(y\!=\!\mathrm{tet}_b(x)\) versus \(x\) for various \(b\)

For a given function \(f\), the fixed point is solution \(L\) of equation

\((1) ~ ~ ~ ~ ~ ~ L = f(L)\)

In the simple case, \(f\) is just holomorphic function of a single variable; then \(L\) is assumed to be a complex number. [1]

In the theory of linear operators, for some operator \(f\), the eigenfunction with eigenvalue unity is fixed point of operator \(f\).

Examples

In some cases, the inverse function \(g=f^{-1}\) exists, and often the fixed point of function \(f\) is also fixed point of function \(g\), id est,

\((2) ~ ~ ~ ~ ~ ~ L=g(L)\)

The fixed point of the logarithm is also fixed point of the exponential, although not every fixed point of the exponential is also fixed point of logarithm.

In many cases, the fixed point can be approximated by the straightforward iteration of equation (1) or equation (2).

For example, the fixed point of exponential

\(L = -\mathrm{ProductLog}(-1)^* \approx 0.3181315052047641+ 1.3372357014306895 \mathrm{i}\)

can be evaluated iterating expression

\(L=\ln(L)\)

with initial approximation \(L\approx\mathrm i\).

Fixed points of a transfer function \(f\) are good choice as asymptotic s of the superfunction \(F\); fixed point \(L\) of the exponential in the example above is asymptotic value of tetration tet:

\((3) ~ ~ ~ ~ ~ \displaystyle \lim_{y\rightarrow +\infty} \mathrm{tet}(x\!+\mathrm i y) = L ~ ~ ~ \forall x \in \mathbb R\)

The Wolfram (software) offers the table of evaluations of some fixed points for some elementary functions [2].

Hyperbolic fixpoint

The hyperops [3] uses the term fixpoint instead of fixed point. This section is borrowed from there.

A hyperbolic fixpoint is a fixpoint \(a\) of \(f\) such that \(|f'(a)|\neq 0,1\).

For a locally analytic function with hyperbolic fixpoint at \(0\), i.e. \(f(z)=c_1 z + c_2z^2 + \dots\), \(|c_1|\neq 0,1\), there is always a locally analytic and injective function \(\sigma\) that satisfies the Schröder equation \(\sigma(f(z))=c_1 \sigma(z))\\) \(\sigma\) is unique up to a multiplicative constant and is called the Schröder coordinates of \(f\) at 0.

Hyperbolic fixed points are good for application of the regular iteration

Other meanings of the term

Sometimes, fixed point refers to the style of the numerical representation of real constants, that has maximum rounding error, uniformly distributed along the area of numbers allowed. Practically, in this case, any real number is approximated as ratio of some integer number to the integer constant that is the same for all numbers. To avoid confusions, the term fixed point arithmetics is recommended for such a case [4].

References

  1. ↑ http://en.citizendium.org/wiki/Fixed_point
  2. ↑ http://mathworld.wolfram.com/FixedPoint.html
  3. ↑ http://math.eretrandre.org/hyperops_wiki/index.php?title=Hyperbolic_fixpoint
  4. ↑ http://en.wikipedia.org/wiki/Fixed-point_arithmetic

http://bruce-shapiro.com/math481A/notes/9-fixed-point.pdf ruce E. Shapiro, Ph.D. Math 481A Lecture Notes. Lesson 9. Fixed Point Iteration. (approx. 2011)

http://dbs.uni-leipzig.de/file/icde2002-sf.pdf Sergey Melnik, Hector Garcia-Molina, Erhard Rahm. Similarity Flooding: A Versatile Graph Matching Algorithm and its Application to Schema Matching. Proceedings of the 18th International Conference on Data Engineering (ICDEí02) 1063-6382/02 $17.00 © 2002 IEEE. .. In this paper we presented a simple structural algorithm based on fixpoint computation that is usable for matching of diverse data structures. ..

Retrieved from "https://mizugadro.mydns.jp/t/index.php?title=Fixed_point&oldid=28010"