反復関数系のソースを表示

[[画像:Sierpinski1.png|thumb|right|250px|IFSで作成された[[シェルピンスキーのギャスケット]]]]

'''反復関数系'''（はんぷくかんすうけい、[[英語|英]]: '''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を扱うソフトウェアではそのような手法は採用されていない）。

== 例: フラクタルの「シダ」 ==
[[画像:Fractal_fern_explained.png|thumb|right|150px|IFSを使ったフラクタルのシダ]]
反復関数系を用いたシダ状の画像計算の例を以下に示す。

最初に描画する点は原点 (''x''<sub>0</sub> = 0, ''y''<sub>0</sub> = 0) であり、そこから次の点の座標を計算するため、次の4つの座標変換のうちの1つを無作為に選んで反復的に適用する。

:''x''<sub>''n'' + 1</sub> = 0
:''y''<sub>''n'' + 1</sub> = 0.16 ''y''<sub>''n''</sub>

この座標変換は1%の確率で選択され、右図で緑色で示されている線分上の点の描画に相当する。

:''x''<sub>''n'' + 1</sub> = 0.2 ''x''<sub>''n''</sub>&nbsp;&minus;&nbsp;0.26&nbsp;''y''<sub>''n''</sub>
:''y''<sub>''n'' + 1</sub> = 0.23 ''x''<sub>''n''</sub>&nbsp;+&nbsp;0.22 ''y''<sub>''n''</sub>&nbsp;+&nbsp;1.6

この座標変換は7%の確率で選択され、右図の黒の四角形内の任意の点から赤の四角形内の図形への写像となる。

:''x''<sub>''n'' + 1</sub> = &minus;0.15 ''x''<sub>''n''</sub> + 0.28 ''y''<sub>''n''</sub>
:''y''<sub>''n'' + 1</sub> = 0.26 ''x''<sub>''n''</sub> + 0.24 ''y''<sub>''n''</sub> + 0.44

この座標変換は7%の確率で選択され、右図の黒の四角形内の任意の点から濃い青の四角形内の図形への写像となる。

:''x''<sub>''n'' + 1</sub> = 0.85 ''x''<sub>''n''</sub> + 0.04 ''y''<sub>''n''</sub>
:''y''<sub>''n'' + 1</sub> = &minus;0.04 ''x''<sub>''n''</sub> + 0.85 ''y''<sub>''n''</sub> + 1.6

この座標変換は85%の確率で選択され、右図の黒の四角形内の任意の点から青の四角形内の図形への写像となる。

最初の座標変換が茎の描画となる。2番目の座標変換は左下の葉、3番目は右下の葉の描画に相当する。4番目の座標変換は3番目までで描画される部分を縮小して若干傾けてコピーしたものであり、反復的な適用によってシダ全体が描画される。IFSの再帰的性質により、全体がそれぞれの葉を拡大したコピーになっている。なお、ここでは、座標の範囲を -5 <= x <= 5 と 0 <= y <= 10 としている。

== 歴史 ==
[[画像:Menger sponge (IFS).jpg|thumb|200px|[[メンガーのスポンジ]], 3次元IFS]]
IFS を現在の形式で考案したのは John Hutchinson である（1981年）。Michael Barnsley の著書 ''Fractals Everywhere'' で一般に知られるようになった（1988年）。彼らは、1957年に Georges de Rham が考案した自己相似な曲線である de Rham 曲線の考え方を一般化したのだった。さらにそれ以前に[[カントール集合]]の考え方が1884年に登場していた。

== 関連項目 ==
* [[L-system]]
* [[フラクタル圧縮]]
* [[フラクタルフレーム]]

== 外部リンク ==
*[http://www.cut-the-knot.org/ctk/ifs.shtml A definition of IFS and a Java illustration with several built-in examples] at cut-the-knot
*[http://flam3.com/flame.pdf The Fractal Flame Algorithm]

{{Fractals}}
{{Normdaten}}
{{DEFAULTSORT:はんふくかんすうけい}}
[[Category:フラクタル]]
[[Category:数学に関する記事]]