Фрактальная геометрия и аффинные системы итерируемых функций (IFS)

Сжимающие аффинные преобразования

В основе IFS лежит классическое аффинное преобразование плоскости: r_new = A*r + b, где A — матрица 2x2, задающая поворот и масштабирование, а b — вектор параллельного переноса. Чтобы набор таких преобразований мог породить фрактал, они обязаны быть сжимающими. Математически это означает, что расстояние между любыми двумя точками после применения преобразования должно стать строго меньше их первоначального расстояния. В терминах линейной алгебры это требование сводится к тому, что модули всех собственных значений матрицы A должны быть строго меньше единицы. Применение такого сжимающего преобразования к любой начальной фигуре всегда уменьшает ее габариты, одновременно смещая и поворачивая ее на плоскости.

Аттрактор Хатчинсона: математическое чудо

Представим, что мы задали набор из нескольких (например, трех) различных сжимающих аффинных преобразований. Выдающаяся теорема Джона Хатчинсона утверждает, что для любого такого набора существует один, и только один, уникальный непустой компактный геометрический объект (называемый аттрактором IFS), который абсолютно не меняется (инвариантен) при одновременном применении к нему всех преобразований системы. То есть, если взять этот объект, сжать его тремя разными способами и объединить полученные мини-копии вместе, они сложатся в точности в исходный объект! Форма этого аттрактора совершенно не зависит от начальных условий, а закодирована исключительно в матричных коэффициентах самих аффинных преобразований.

Папоротник Барнсли и треугольник Серпинского

Знаменитым примером применения IFS является Папоротник Барнсли. С помощью всего четырех аффинных преобразований (четырех матриц 2x2 и четырех векторов сдвига) математик Майкл Барнсли смог с фотографической точностью смоделировать сложнейшую геометрию ветки реального папоротника. Каждое преобразование отвечает за отдельную часть: стебель, левую ветку, правую ветку и верхушку. Применяя этот набор функций итеративно (случайным образом выбирая одно из преобразований на каждом шаге, так называемый Chaos Game алгоритм), компьютер за секунды отрисовывает на экране лист папоротника с бесконечной детализацией. Классический треугольник Серпинского генерируется еще проще: нужны всего три аффинных преобразования, сжимающих пространство ровно в два раза к трем вершинам базового треугольника.

Фрактальная размерность Хаусдорфа-Безиковича

Фракталы ломают базовое аналитическое понимание размерности. Отрезок имеет размерность 1, квадрат — 2, куб — 3. Но какова размерность треугольника Серпинского? Он состоит из линий, но их бесконечно много, он изрезан дырами, поэтому его площадь строго равна нулю (он не двумерен). Аналитическая геометрия вводит понятие размерности Хаусдорфа-Безиковича, которая может быть дробным (нецелым) числом. Для строго самоподобных фракталов, генерируемых IFS, размерность d вычисляется из алгебраического уравнения подобия. Если мы собираем фигуру из N копий, каждая из которых сжата в k раз, то размерность вычисляется как d = ln(N) / ln(k). Для треугольника Серпинского N=3, k=2, следовательно, его пространственная размерность равна ln(3)/ln(2), что составляет примерно 1.58. Этот объект существует в парадоксальном математическом промежутке между линией и поверхностью.