IFS: системи ітерованих функцій та фрактальні атрактори
Папороть Барнслі неможливо відрізнити від справжнього листка папороті,
проте її породжують лише чотири прості афінні перетворення, що
застосовуються випадково одне за одним. Системи ітерованих функцій —
один з найкрасивіших сюрпризів математики: нескінченно деталізована
самоподібна структура, закодована жменькою чисел. Застосовуйте ті самі
стиснення знову й знову — до точки, до набору точок, до цілого
зображення — і завжди постає той самий фрактальний атрактор,
незалежно від того, з чого ви почали.
1. Стискувальні відображення та теорема про нерухому точку
Математичний рушій IFS — це
теорема Банаха про нерухому точку (також відома як
теорема про стискувальні відображення). Вона гарантує, що будь-яке
стискувальне перетворення має єдину нерухому точку — і що повторне
застосування перетворення збігається до цієї нерухомої точки з
будь-якого початкового положення.
// Означення стискувального відображення Функція f : X → X є
стискувальним відображенням, якщо: d(f(x), f(y)) ≤ c · d(x, y) для всіх x, y ∈ X,
та деякого c ∈ [0, 1) Де: d(·,·) = метрика відстані c = коефіцієнт
стиснення (менший = швидша збіжність) Теорема Банаха про нерухому точку: Якщо X
— повний метричний простір і f є стисненням: → f має ЄДИНУ
нерухому точку x* таку, що f(x*) = x* → для будь-якої початкової точки x₀,
послідовність x₀, f(x₀), f²(x₀),... збігається до x* зі швидкістю cⁿ Приклад:
f(x) = 0.5x на ℝ Нерухома точка: x* = 0 Починаючи з x₀ = 100: 100, 50,
25, 12.5, ... → 0
Для IFS відповідним метричним простором є не ℝ, а
простір компактних підмножин ℝ², оснащений
метрикою Хаусдорфа — максимальною відстанню, на яку
потрібно «перетягнути» одну множину, щоб вона накрила іншу. У цьому
просторі одночасне застосування набору стиснень саме є стисненням, а
його нерухома точка — це фрактальний атрактор.
2. Означення IFS та атрактор
Система ітерованих функцій складається зі скінченного
набору стискувальних відображень на ℝⁿ, зазвичай афінних перетворень:
// IFS — це: {f₁, f₂, ..., fₙ}, де кожне fᵢ є стисненням // Кожне
fᵢ зазвичай є афінним відображенням: fᵢ(x) = Aᵢ · x + bᵢ Де: Aᵢ = матриця 2×2
(масштабування, поворот, зсув) bᵢ = 2D-вектор перенесення
Обмеження: усі власні значення Aᵢ мають модуль < 1 (стиснення)
// Атрактор IFS A — це єдина компактна множина, що задовольняє: A = f₁(A)
∪ f₂(A) ∪ ... ∪ fₙ(A) Інтуїція: A — це множина, що відображається сама в себе
під дією всіх перетворень одночасно. Це «об'єднання n масштабованих
копій самої себе» — самоподібність за означенням. // Збіжність:
починаючи з БУДЬ-ЯКОЇ компактної множини S₀: S_{k+1} = f₁(Sₖ) ∪ f₂(Sₖ) ∪ ... ∪
fₙ(Sₖ) S_k → A (у метриці Хаусдорфа, експоненційно швидко)
Атрактор єдиний і не залежить від початкової точки.
Чи починаєте ви з однієї точки, заповненого квадрата чи випадкової
каракулі — після достатньої кількості ітерацій орбіта збігається до того самого
фрактального атрактора A. IFS діє як «рецепт», що задає
атрактор неявно через рівняння самоподібності A = ∪ fᵢ(A).
3. Алгоритм гри хаосу
Детермінований підхід (застосування всіх fᵢ до кожної точки на кожній
ітерації) вимагає відстеження експоненційно зростаючих множин.
Гра хаосу — це ймовірнісний алгоритм, що ефективно
відмальовує атрактор, простежуючи одну випадкову орбіту:
// Гра хаосу (Barnsley 1988) 1. Почніть з будь-якої точки x₀ ∈ ℝ² 2.
Повторіть N разів: - Виберіть перетворення fᵢ випадково з імовірністю
pᵢ - x_{n+1} = fᵢ(x_n) - Відмалюйте x_{n+1} (пропустіть перші ~20 ітерацій для
«розігріву») Властивості: - Імовірності pᵢ є довільними (будь-яке pᵢ > 0
дає збіжність) - Природний вибір: pᵢ ∝ |det(Aᵢ)| (пропорційно
площі, яку воно покриває) → рівномірна щільність на атракторі - Після
N=100 000 ітерацій атрактор вже видно оком - Після N=1
000 000 ітерацій: високоякісний рендеринг Часова складність: O(N) —
відмальовує будь-який IFS-фрактал за мілісекунди // Скелет на JavaScript: let x
= 0, y = 0; for (let i = 0; i < 1e6; i++) { const f =
chooseTransform(); // випадково, зважено за ймовірністю [x, y] =
applyAffine(f, x, y); if (i > 20) plotPixel(x, y); }
4. Папороть Барнслі детально
Папороть Майкла Барнслі (1988) — це знаковий приклад: чотири афінні
перетворення, що породжують структуру, візуально ідентичну листку
папороті Blechnum spicant, аж до дрібних прожилок:
// Папороть Барнслі — 4 афінні перетворення (x' = ax + by + e, y' = cx
+ dy + f) // a b c d e f ймов. значення //
──────────────────────────────────────────────────────────────────────────
f1: [ 0.00, 0.00, 0.00, 0.16, 0.00, 0.00 ] p=0.01 // стебло f2: [ 0.85,
0.04, -0.04, 0.85, 0.00, 1.60 ] p=0.85 // основний листок (масштабована копія) f3:
[ 0.20, -0.26, 0.23, 0.22, 0.00, 1.60 ] p=0.07 // ліва пірчинка f4:
[-0.15, 0.28, 0.26, 0.24, 0.00, 0.44 ] p=0.07 // права пірчинка
Інтерпретація: f1: стискає всю папороть у крихітний відрізок стебла біля
основи f2: копіює всю папороть у масштабі 85%, трохи повернуту →
тіло основного листка f3: бере папороть, повертає на 83° проти годинникової стрілки, масштабує до 30% →
маленькі ліві пірчинки f4: бере папороть, повертає на 37° за годинниковою стрілкою, масштабує до 37%
→ маленькі праві пірчинки Рівняння самоподібності: Fern = f1(Fern) ∪
f2(Fern) ∪ f3(Fern) ∪ f4(Fern) // Вікно рендерингу: x ∈ [-2.5, 2.5], y
∈ [0, 10] // Відображення на пікселі полотна: px = (x+2.5)/5 * width, py =
(1-y/10) * height
Імовірності кодують відносну «вагу» кожного перетворення в
атракторі. f₂ має ймовірність 0.85, бо тіло основного листка
займає ~85% площі атрактора. Якщо встановити всі ймовірності
рівними 0.25, гра хаосу все одно збігається до тієї самої папороті, але
стебло та малі пірчинки відмальовуються з надто великою кількістю точок, тоді як
основне тіло недостатньо вибирається.
5. Класичні IFS-фрактали
Трикутник Серпінського (3 стиснення)
// Три стиснення, кожне масштабує на 0.5 до іншого кута
// Вершини трикутника: A=(0,0), B=(1,0), C=(0.5, √3/2) f1(x) = 0.5·x //
до A=(0,0) f2(x) = 0.5·x + (0.5, 0) // до B=(1,0) f3(x) =
0.5·x + (0.25, √3/4) // до C // Еквівалент через гру хаосу: // Виберіть
випадковий кут; зсуньтеся на половину відстані до нього; відмалюйте; повторіть // Після ~50
ітерацій: постає трикутник Серпінського Розмірність Хаусдорфа:
log(3)/log(2) ≈ 1.585
Сніжинка Коха як IFS (4 стиснення)
// IFS для кривої Коха (один бік сніжинки) // Масштабуйте кожну
копію на 1/3, розмістіть 4 копії: f1: масштаб 1/3, перенесення до [0, 1/3] //
лівий відрізок f2: масштаб 1/3, поворот +60°, перенесення до [1/3] // ліва
вершина f3: масштаб 1/3, поворот -60°, перенесення до ... // права вершина f4:
масштаб 1/3, перенесення до [2/3, 1] // правий відрізок Розмірність Хаусдорфа:
log(4)/log(3) ≈ 1.262
IFS-атрактори загалом мають нецілі розмірності Хаусдорфа — вони
надто шорсткі й деталізовані, щоб бути одновимірними кривими, але
недостатньо заповнені, щоб бути двовимірними областями. Розмірність
кількісно описує їхню «проміжність».
Для самоподібної IFS, що задовольняє
умову відкритої множини (перетворені копії не перекриваються,
окрім хіба що на межах), розмірність Хаусдорфа d задовольняє
рівняння Морана:
// Рівняння Морана для самоподібної IFS (умова відкритої множини) Σᵢ rᵢᵈ = 1
Де: rᵢ = коефіцієнт стиснення i-го перетворення
(|det(Aᵢ)|^{1/n}) d = розмірність Хаусдорфа (= Мінковського = подоби)
Приклади: трикутник Серпінського: 3 відображення, кожне rᵢ = 1/2 3 · (1/2)^d = 1 →
d = log(3)/log(2) ≈ 1.585 множина Кантора (2 відображення, кожне r=1/3): 2 · (1/3)^d
= 1 → d = log(2)/log(3) ≈ 0.631 крива Коха (4 відображення, кожне r=1/3): 4 ·
(1/3)^d = 1 → d = log(4)/log(3) ≈ 1.262 щільна IFS (багато відображень з
великим r): d → 2 (наближається до заповнення площини)
Коли умова відкритої множини не виконується (копії
перекриваються), рівняння Морана дає верхню межу, а фактична
розмірність Хаусдорфа може бути меншою. Обчислення точної розмірності для
IFS з перекриттям (наприклад, випадкових IFS) — відкрита проблема в математиці:
гіпотеза про точні перекриття досі не повністю розв'язана.
7. Теорема колажу та фрактальне стиснення
Теорема колажу — це обернена задача: за заданим
цільовим зображенням T знайти IFS, атрактор якої апроксимує T. Вона стверджує,
що якщо вдається накрити T перетвореними копіями його самого
(«колаж»), то атрактор IFS буде близьким до T з похибкою,
обмеженою похибкою покриття.
// Теорема колажу (Barnsley) Якщо можна знайти перетворення
f₁,...,fₙ такі, що: d_H(T, f₁(T) ∪ ... ∪ fₙ(T)) ≤ ε То атрактор IFS
A задовольняє: d_H(A, T) ≤ ε / (1 − c) Де c = максимальний
коефіцієнт стиснення серед усіх перетворень (Для c=0.5 та ε=0.1:
гарантовано d_H(A,T) ≤ 0.2) Це є основою ФРАКТАЛЬНОГО СТИСНЕННЯ
ЗОБРАЖЕНЬ: 1. Розбийте цільове зображення на блоки-ранги (плитки 8×8 або 16×16
пікселів) 2. Для кожного блоку-рангу: знайдіть блок-домен
(більшу плитку будь-де в зображенні), який після перетворення (масштабування +
афінне відображення кольору) найкраще апроксимує блок-ранг 3. Збережіть:
(позиція домену, поворот, масштаб, яскравість) для кожного блоку-рангу →
зазвичай коефіцієнт стиснення від 10:1 до 100:1 4. Декодування: почніть з будь-якого
зображення, повторно застосовуйте всі афінні відображення → збігається до
оригіналу після ~8 ітерацій
Фрактальне стиснення зображень (розроблене Барнслі та Жакеном у
1990-х) комерційно використовувалося в енциклопедіях на CD-ROM (його застосовувала Encarta).
Воно поступилося JPEG, а пізніше JPEG2000 та WebP, бо
практичні коефіцієнти стиснення були подібними, але кодування було набагато повільнішим
(пошук найкращого блоку-домену для кожного блоку-рангу обчислювально
дорогий). Як математичний прийом воно залишається елегантним — по суті, ви
шукаєте IFS, атрактором якої є зображення.
8. Реалізація: рендеринг IFS на JavaScript
// Повний рендерер гри хаосу для IFS (Canvas 2D) function renderIFS(canvas,
transforms, iterations = 500_000) { const ctx =
canvas.getContext('2d'); const W = canvas.width, H = canvas.height; //
Будуємо масив кумулятивних імовірностей для зваженого випадкового вибору const
cumProb = []; let total = 0; for (const t of transforms) { total +=
t.prob; cumProb.push(total); } // Відображаємо координати фрактала на пікселі полотна
// межі: автовизначення або передача {xmin, xmax, ymin, ymax} const xmin=-3,
xmax=3, ymin=0, ymax=10; const toX = x => (x - xmin) / (xmax - xmin) *
W; const toY = y => (1 - (y - ymin) / (ymax - ymin)) * H; // Буфер-гістограма
для розфарбовування за щільністю const buf = new Uint32Array(W * H);
let x = 0, y = 0; for (let i = 0; i < iterations; i++) { // Вибираємо
перетворення за ймовірністю const r = Math.random() * total; const t
= transforms[cumProb.findIndex(p => r <= p)]; // Застосовуємо афінне
перетворення: [a b; c d] * [x; y] + [e; f] const nx = t.a*x + t.b*y +
t.e; const ny = t.c*x + t.d*y + t.f; x = nx; y = ny; if (i < 20)
continue; // розігрів: пропускаємо перші точки const px = Math.floor(toX(x));
const py = Math.floor(toY(y)); if (px >= 0 && px < W
&& py >= 0 && py < H) buf[py * W + px]++; } //
Рендеринг: використовуємо логарифмічне розфарбовування за щільністю для кращої деталізації const imgData =
ctx.createImageData(W, H); const maxDensity = Math.max(...buf); const
logMax = Math.log1p(maxDensity); for (let i = 0; i < buf.length;
i++) { if (buf[i] === 0) continue; const t = Math.log1p(buf[i]) /
logMax; const idx = i * 4; imgData.data[idx] = Math.floor(50 + 150 *
t); // R imgData.data[idx+1] = Math.floor(150 + 100 * t); // G
imgData.data[idx+2] = Math.floor(50 + 50 * t); // B
imgData.data[idx+3] = 255; } ctx.putImageData(imgData, 0, 0); } //
Перетворення папороті Барнслі: const barnsleyFern = [ { a:0, b:0, c:0,
d:0.16, e:0, f:0, prob:0.01 }, { a:0.85, b:0.04, c:-0.04,d:0.85, e:0,
f:1.60, prob:0.85 }, { a:0.20, b:-0.26,c:0.23, d:0.22, e:0, f:1.60,
prob:0.07 }, { a:-0.15,b:0.28, c:0.26, d:0.24, e:0, f:0.44, prob:0.07
}, ]; renderIFS(myCanvas, barnsleyFern);
Логарифмічне розфарбовування за щільністю призначає яскравість пропорційно до log(1 + потраплянь),
а не безпосередньо до кількості потраплянь, виявляючи дрібні деталі в областях
малої щільності, які були б невидимими за лінійного розфарбовування. Це той самий
прийом, який використовує алгоритм flame fractal для свого
характерного сяйливого вигляду з високим динамічним діапазоном.
Дослідження IFS: Зміна лише одного коефіцієнта на 0.01
може кардинально змінити форму атрактора, водночас зберігаючи
його впізнавану спорідненість. Простір IFS-фракталів — це багатий простір
параметрів: дослідження простору параметрів IFS використовувалися як інструменти
генеративного мистецтва, а проєкт розподіленої заставки Electric Sheep
еволюціонував параметри фрактального полум'я за допомогою генетичних алгоритмів,
керованих голосуванням користувачів.