写像あるいは函数の反復（はんぷく、英: iteration）とは、同じ写像あるいは函数を繰り返し適用する操作である[1]。写像の繰り返しや反復合成とも呼ぶ[2][3]。ある初期値に写像の反復を適用することで得られる点列を軌道という。

年利で増える残高計算、世代ごとに増減する生物の個体数の計算、ニュートン法のような数値計算で方程式の解を求める問題など、反復によって表すことができるさまざまな科学・数学の問題がある[4]。
定義

集合 X とその上で定義される写像 f: X → X について、非負整数 n に対する f の n 回反復 f n は f n = f ∘ f ∘ ⋯ ∘ f ⏞ n {\displaystyle f^{n}=\overbrace {f\circ f\circ \cdots \circ f} ^{n}} f n : x ↦ f ( f ( ⋯ f ⏞ n ( x ) ⋯ ) ) {\displaystyle f^{n}:x\mapsto \overbrace {f(f(\cdots f} ^{n}(x)\cdots ))}

によって定義される[2]。ここに ? は写像の合成、すなわち (f ? g)(x) = g(f(x)) を意味する。例えば、 f ( x ) = x {\displaystyle f(x)={\sqrt {x}}}

という写像であれば、その2回反復および3回反復は f 2 ( x ) = x {\displaystyle f^{2}(x)={\sqrt {\sqrt {x}}}} f 3 ( x ) = x {\displaystyle f^{3}(x)={\sqrt {\sqrt {\sqrt {x}}}}}

で与えられる[5]。他の表記法としては f [n] といった書き方もあるが、f n 表記の使用が多い[6]。

f 0 については、一般に恒等写像として定義する。すなわち、f 0(x) = x である[7]。f が逆写像 f −1: X → X を持つ場合は、 f − n : x ↦ f − 1 ( f − 1 ( ⋯ f − 1 ⏞ n ( x ) ⋯ ) ) {\displaystyle f^{-n}:x\mapsto \overbrace {f^{-1}(f^{-1}(\cdots f^{-1}} ^{n}(x)\cdots ))}

が定義される[2]。
軌道詳細は「軌道 (力学系)」を参照

ℤ を整数全体の集合とする。f を同相写像として、ある点 x ∈ X に対して O ( x ) = { f n ( x ) ;   n ∈ Z } {\displaystyle O(x)=\{f^{n}(x);\ n\in \mathbb {Z} \}}

で与えられる集合 O(x) を、x を通る軌道という[7]。このとき、点 x は軌道の初期値と呼ばれる[8]。
不動点、周期点詳細は「不動点」および「周期点」を参照

点 x が写像 f に対して f ( x ) = x {\displaystyle f(x)=x}

を満たすとき、x を不動点という[9]。f の全ての不動点の集合を Fix(f ) などと記す[10]。

また、f と x に対して、 f m ( x ) = x {\displaystyle f^{m}(x)=x}

を満たす最小の m > 0 を周期といい、点 x を周期 m の周期点という[10]。f の m 周期の周期点の集合を Perm(f ) などと記す[10]。m 周期点 x を通る軌道 { ⋯   f m − 1 ( x ) ,   x ,   f ( x ) ,   f 2 ( x ) , ⋯ ,   f m − 1 ( x ) ,   x ⏞ m ,   f ( x ) ,   f 2 ( x ) , ⋯ } {\displaystyle \{\cdots \ f^{m-1}(x),\ \overbrace {x,\ f(x),\ f^{2}(x),\cdots ,\ f^{m-1}(x),\ x} ^{m},\ f(x),\ f^{2}(x),\cdots \}}