迭代函数

在集合 ${\displaystyle X}$  上的迭代函数的形式定义为:

设 ${\displaystyle X}$  是集合和 ${\displaystyle f:X\rightarrow X}$  是函数。定义 ${\displaystyle f}$  的 ${\displaystyle n}$  次迭代 ${\displaystyle f^{n}}$  为 ${\displaystyle f^{0}=\operatorname {id} _{X}}$  而 ${\displaystyle f^{n+1}=f\circ f^{n}}$ ，这里的 ${\displaystyle \operatorname {id} _{X}}$  是在 ${\displaystyle X}$  上的恒等函数。

在上述中，${\displaystyle f\circ g}$  指示函数复合；就是说 ${\displaystyle (f\circ g)(x)=f(g(x))}$ 。

换句话说，迭代函数也可以表示为以下的形式：

${\displaystyle f^{n}(x)={\underbrace {f(f(f(...f(f} _{n}}(x))...)))}$ 

${\displaystyle f^{0}(x)}$ 定义为${\displaystyle x}$ 。

${\displaystyle f^{-n}(x)}$ 定义为${\displaystyle f^{n}(x)}$ 的反函数。（如果${\displaystyle f^{n}(x)}$ 的反函数不存在，则${\displaystyle f^{-n}(x)}$ 也不存在）

因此，${\displaystyle f^{1}(x)}$ 就是${\displaystyle f(x)}$ ，${\displaystyle f^{2}(x)}$ 是${\displaystyle f(f(x))}$ ，${\displaystyle f^{0}(x)}$ 是恒等函数${\displaystyle x}$ ，${\displaystyle f^{-1}(x)}$ 是${\displaystyle f(x)}$ 的反函数（如果存在的话），而${\displaystyle f^{\frac {1}{2}}(x)}$ 就是能够使得合成函数${\displaystyle g(g(x))}$ 正好是${\displaystyle f(x)}$ 的函数${\displaystyle g(x)}$ 。

注意，一般情况下，${\displaystyle f^{n}(x)}$ 并不等于${\displaystyle (f(x))^{n}}$ 或${\displaystyle f(x^{n})}$ ，而例如${\displaystyle \sin ^{-1}(x)}$ 是${\displaystyle \sin(x)}$ 的反函数，亦即${\displaystyle \arcsin(x)}$ ，而不是${\displaystyle {\frac {1}{\sin(x)}}=\csc(x)}$ 。

一些特殊函数的幂次为（其中${\displaystyle a}$ 、${\displaystyle b}$ 、${\displaystyle n}$ 可为任意复数，亦即${\displaystyle a,b,n\in \mathbb {C} }$ ）：

${\displaystyle f(x)=a}$ ，${\displaystyle f^{n}(x)=a{\text{ if }}n\in \mathbb {R} \land n>0,f^{n}(x)=x{\text{ if }}n=0}$ （在${\displaystyle n}$ 是负实数或虚数的时候并没有定义，就好比${\displaystyle 0^{n}}$ 在${\displaystyle n}$ 是负实数或虚数的时候也没有定义）

${\displaystyle f(x)=x+a}$ ，${\displaystyle f^{n}(x)=x+na}$ 

${\displaystyle f(x)=ax}$ ，${\displaystyle f^{n}(x)=a^{n}x}$ 

${\displaystyle f(x)=x^{a}}$ ，${\displaystyle f^{n}(x)=x^{a^{n}}}$ （注意迭代幂次要由右往左算）

${\displaystyle f(x)=ax+b}$ ，${\displaystyle f^{n}(x)=a^{n}x+{\frac {a^{n}-1}{a-1}}b}$ （${\displaystyle a\neq 1}$ ）

${\displaystyle f(x)=bx^{a}}$ ，${\displaystyle f^{n}(x)=b^{\frac {a^{n}-1}{a-1}}x^{a^{n}}}$ （${\displaystyle a\neq 1}$ ）

（注意任何非零复数的任何复数次方都有定义：${\displaystyle a^{n}=e^{n\ln a}=e^{{\text{Re}}(n\ln a)}(\cos({\text{Im}}(n\ln a)+i\sin({\text{Im}}(n\ln a))}$ ，当${\displaystyle a}$ 为负实数或虚数时，${\displaystyle \ln(a)=\ln(|a|)+i{\text{arg}}(a)}$ ，其中${\displaystyle |a|}$ 为复数${\displaystyle a}$ 的绝对值，${\displaystyle {\text{arg}}(a)}$ 为复数${\displaystyle a}$ 的主幅角，${\displaystyle {\text{Re}}(a)}$ 为复数${\displaystyle a}$ 的实部，${\displaystyle {\text{Im}}(a)}$ 为复数${\displaystyle a}$ 的虚部）

函数幂亦有类似指数律的定理，其中${\displaystyle m}$ 、${\displaystyle n}$ 可为任意复数，亦即${\displaystyle m,n\in \mathbb {C} }$ ：

${\displaystyle f^{m}(f^{n}(x))=f^{m+n}(x)}$ 

${\displaystyle (f^{m})^{n}(x)=f^{mn}(x)}$ 

注意函数的合成是不可交换的（${\displaystyle gf(x)}$ 并不一定等于${\displaystyle fg(x)}$ ）但因为可结合（${\displaystyle h(gf)(x)}$ 一定等于${\displaystyle (hg)f(x)}$ ），所以会符合幂结合性，因此这两条“函数幂的指数律”并没有任何问题。

这跟例如指数拓展到次方为负整数、分数、无理数、复数，以及阶乘运算跟排列组合运算${\displaystyle P_{n}^{m}}$ 、${\displaystyle C_{n}^{m}}$ 拓展到非整数和负数时（使用伽玛函数）一样，二项式定理也可以用这种方式拓展到负整数、分数、无理数、复数，只是会变成无穷级数而不再是有限级数而已，包括矩阵的${\displaystyle n}$ 次方以及微分${\displaystyle n}$ 次（${\displaystyle n}$ 为负整数时等同于积分${\displaystyle -n}$ 次），也都可以用这种方式，把${\displaystyle n}$ 拓展到任意复数，或例如已知“首项”、“公差/公比”、“项数”的等差数列或等比数列要求出全部项的和或乘积的公式，也都可以用这种方式，拓展到项数为负整数、分数、无理数、复数的情况（包括一般的${\displaystyle \sum _{x=m}^{n}f(x)}$ 与${\displaystyle \prod _{x=m}^{n}f(x)}$ 中，${\displaystyle f(x)}$ 为常见的函数如多项式函数、指数函数、对数函数、三角函数的时候，${\displaystyle m}$ 跟${\displaystyle n}$ 也能拓展到任意复数，就跟积分式${\displaystyle \int _{m}^{n}f(x)}$ 一样），至于超运算${\displaystyle a[n]b}$ 能不能拓展到分数、无理数或复数，则是数学中未解决的问题之一。

函数 ${\displaystyle f^{n}}$  的序列叫做 Picard 序列，得名于埃米尔·皮卡。对于一个给定 ${\displaystyle x\in X}$ ，${\displaystyle f^{n}(x)}$  的值的序列叫做 ${\displaystyle x}$  的轨道。

如果对于某个整数 ${\displaystyle m}$  有 ${\displaystyle f^{n}(x)=f^{n+m}(x)}$ ，则轨道叫做周期轨道。对于给定 ${\displaystyle x}$  最小的这种 ${\displaystyle m}$  值叫做轨道的周期。点 ${\displaystyle x}$  自身叫周期点。

如果m=1，就是说如果对于某个X中的x有f(x) = x，则x被称为迭代序列的不动点。不动点的集合经常指示为Fix（f）。存在一些不动点定理保证在各种情况下不动点的存在性，包括巴拿赫不动点定理和Brouwer不动点定理。

有很多技术通过不动点迭代（英语：Fixed-point iteration）产生了序列收敛加速。例如，应用于一个迭代不动点的Aitken方法叫做Steffensen方法，生成二次收敛。 不动点理论同样也适用于经济学领域。

通过迭代，可以发现有向一个单一点收缩和会聚的一个集合。在这种情况下，会聚到的这个点叫做吸引不动点。反过来说，迭代也可以表现得从一个单一点发散；这种情况叫不稳定不动点。

当轨道的点会聚于一个或多个极限的时候，轨道的会聚点的集合叫做极限集合或 ω-极限集合。

吸引和排斥的想法类似推广；依据在迭代下小邻域行为，可把迭代分类为稳定集合和不稳定集合。

其他极限行为也有可能；比如，游荡点是总是移动永不回到甚至接近起点的点。

著名的迭代函数包括曼德博集合和迭代函数系统。

如果 f 是一个群元素在一个集合上的作用，则迭代函数对应于自由群。

• 旋转数（英语：Rotation number）
• Sarkovskii定理（英语：Sharkovskii's theorem）

• Vasile I. Istratescu, Fixed Point Theory, An Introduction, D.Reidel, Holland (1981). ISBN 90-277-1224-7