反復関数系
反復関数系（はんぷくかんすうけい、英: Iterated function system、IFS）はフラクタルの一種であり、一般に2次元のフラクタルの描画や計算に用いられる。IFSフラクタルは自身のいくつかのコピーの和集合から成り、各コピーは関数によって変形されている（そのため「関数系」と呼ばれる）。典型例としてはシェルピンスキーのギャスケットがある。その関数は一般に収縮写像であり、点の集合がより近くなり、形がより小さくなる。従ってIFSフラクタルは、自身の縮小コピーを（場合によっては重ね合わせて）まとめたものであり、各部を詳細に見れば、その部分もそれ自身の縮小コピーから構成されていて、これが永遠に続く。このため、フラクタルとしての自己相似性が生じる。
定義
形式的には、次のように表される。
- [math]S = \bigcup_i^N f_i(S),\,[/math]
ここで
- [math]S \subset \mathbb{R}^n\,[/math]
と
- [math]f_i:\mathbb{R}^n\to\mathbb{R}^n.[/math]
は、反復関数である。S はハッチンソンオペレータの固定点であり、関数群 [math]f_i[/math] の和集合である。
属性
合成を伴う関数群 [math]f_i[/math] の集合はモノイドを形成する。関数が2つだけの場合、モノイドは二項モノイドとなる。その合成は無限二分木として視覚化され、あるノードでは左右の子ノードのいずれかの関数で合成される。一般化すると、p 個の関数があるとき、P進数木での合成として視覚化できる。
関数合成がこのようになされるため、モノイドの各元はP進数について同型的と見ることができる。すなわち、P進数の各桁がどの関数で合成するかを示しているのである。
二項モノイドの自己同型は合同群（modular group）である。これにより、カントール集合などの多くのフラクタルの自己相似性が説明されると見ることもできる。
例
各関数 [math]f_i[/math] は線型性、より正確に言えばアフィン写像を持つ必要がある場合もあり、それによって行列で表現できるようになる。しかし、投影変換やメビウス変換といった非線型関数から構築されるIFSもある。フラクタルフレームは、非線型関数によるIFSの例である。
IFSフラクタルを計算する最も典型的なアルゴリズムとして、カオスゲームがある。平面上の点の座標を無作為に選び、関数系から無作為に選んだ関数を繰り返し適用して、その点を描画する。別のアルゴリズムでは、与えられた最大長までの考えられる関数列を生成し、各関数列を初期座標や初期図形に適用した結果を描画する。
これらのアルゴリズムは、フラクタル全体に分散する各点を生成する汎用的構築法を提供する。フラクタルの微小な部分を描画する場合、計算される各点の多くはスクリーンの範囲外になってしまう。従って、IFSでのズームは現実的でないことになる。フラクタルの微小な部分の詳細が必要な場合、計算すべき軌道に基づいた局所的構築手法の方が効率的と思われる（IFSを扱うソフトウェアではそのような手法は採用されていない）。
例: フラクタルの「シダ」
反復関数系を用いたシダ状の画像計算の例を以下に示す。
最初に描画する点は原点 (x0 = 0, y0 = 0) であり、そこから次の点の座標を計算するため、次の4つの座標変換のうちの1つを無作為に選んで反復的に適用する。
- xn + 1 = 0
- yn + 1 = 0.16 yn
この座標変換は1%の確率で選択され、右図で緑色で示されている線分上の点の描画に相当する。
- xn + 1 = 0.2 xn − 0.26 yn
- yn + 1 = 0.23 xn + 0.22 yn + 1.6
この座標変換は7%の確率で選択され、右図の黒の四角形内の任意の点から赤の四角形内の図形への写像となる。
- xn + 1 = −0.15 xn + 0.28 yn
- yn + 1 = 0.26 xn + 0.24 yn + 0.44
この座標変換は7%の確率で選択され、右図の黒の四角形内の任意の点から濃い青の四角形内の図形への写像となる。
- xn + 1 = 0.85 xn + 0.04 yn
- yn + 1 = −0.04 xn + 0.85 yn + 1.6
この座標変換は85%の確率で選択され、右図の黒の四角形内の任意の点から青の四角形内の図形への写像となる。
最初の座標変換が茎の描画となる。2番目の座標変換は左下の葉、3番目は右下の葉の描画に相当する。4番目の座標変換は3番目までで描画される部分を縮小して若干傾けてコピーしたものであり、反復的な適用によってシダ全体が描画される。IFSの再帰的性質により、全体がそれぞれの葉を拡大したコピーになっている。なお、ここでは、座標の範囲を -5 <= x <= 5 と 0 <= y <= 10 としている。
歴史
.jpg){kind=link}
IFS を現在の形式で考案したのは John Hutchinson である（1981年）。Michael Barnsley の著書 Fractals Everywhere で一般に知られるようになった（1988年）。彼らは、1957年に Georges de Rham が考案した自己相似な曲線である de Rham 曲線の考え方を一般化したのだった。さらにそれ以前にカントール集合の考え方が1884年に登場していた。