ЗМІСТ
1. ВСТУП ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 2
2. КЛАСИЧНІ ФРАКТАЛИ ... ... ... ... ... ... ... ... ... ... ... .. 3
2.1. Самоподоба ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .3
2.2. Сніжинка Коха ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 3
2.3. Килим Серпінського ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 5
3. L-СИСТЕМИ ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .... 6
4. Хаотична динаміка ... ... ... ... ... ... ... ... ... ... ... ... 10
4.1. Аттрактор Лоренца ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 10
4.2. Множини Мандельброта і Жюліа ... ... ... ... ... ... ... ... .. 11
5. ВИСНОВОК ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 13
6. СПИСОК ЛІТЕРАТУРИ ... ... ... ... ... ... ... ... ... ... ... ... ... ... .14
1.Вступ
Коли більшості людей здавалося, що геометрія в природі обмежується такими простими фігурами, як лінія, коло, конічний перетин, багатокутник, сфера, квадратична поверхню, а також їх комбінаціями. Наприклад, що може бути гарніше твердження про те, що планети в нашій сонячній системі рухаються навколо сонця по еліптичних орбітах?
Однак багато природні системи настільки складні і нерегулярні, що використання лише знайомих об'єктів класичної геометрії для їх моделювання представляється безнадійним. Як наприклад, побудувати модель гірського хребта або крони дерева в термінах геометрії? Як описати те різноманіття біологічних конфігурацій, яке ми спостерігаємо в світі рослин і тварин? Уявіть собі всю складність системи кровообігу, що складається з безлічі капілярів і судин і доставляє кров до кожної клітинки людського тіла. Уявіть, як хитромудро влаштовані легені та нирки, що нагадують за структурою дерева з гіллястою кроною.
Настільки ж складною та нерегулярної може бути і динаміка реальних природних систем. Як підступитися до моделювання каскадних водоспадів або турбулентних процесів, що визначають погоду?
Фрактали і математичний хаос --- відповідні засоби для дослідження поставлених питань. Термін фрактал відноситься до деякої статичної геометричної конфігурації, такий як миттєвий знімок водоспаду. Хаос --- термін динаміки, використовуваний для опису явищ, подібних турбулентному поведінки погоди. Нерідко те, що ми спостерігаємо в природі, інтригує нас нескінченним повторенням одного і того ж візерунка, збільшеного чи зменшеного у скільки завгодно разів. Наприклад, у дерева є гілки. На цих гілках є гілки трохи менше і т.д. Теоретично, елемент «розгалуження» повторюється нескінченно багато разів, стаючи все менше і менше. Те ж саме можна помітити, роздивляючись фотографію гірського рельєфу. Спробуйте трохи наблизити зображення гірської гряди --- ви знову побачите гори. Так виявляється характерне для фракталов властивість самоподібності.
У багатьох роботах по фракталах самоподібність використовується як визначального властивості. Дотримуючись Бенуа Мадельброту, ми приймаємо точку зору, згідно з якою фрактали повинні визначатися в термінах фрактальної (дробової) розмірності. Звідси і походження слова фрактал (від лат. Fractus --- дробовий).
Поняття дробової розмірності являє собою складну концепцію, яка викладається в кілька етапів. Пряма --- це одновимірний об'єкт, а площину --- двовимірний. Якщо гарненько перекрутивши пряму і площину, можна підвищити розмірність отриманої конфігурації, при цьому нова розмірність звичайно буде дробової в деякому сенсі, який нам належить уточнити. Зв'язок дробової розмірності і самоподібності полягає в тому, що за допомогою самоподібності можна сконструювати безліч дробової розмірності найбільш простим чином. Навіть у випадку набагато більш складних фракталів, таких як межа множини Мандельброта, коли чисте самоподібність відсутня, є майже повне повторення базової форми у все більш і більш зменшеному вигляді.
Багато чудові властивості фракталів та хаосу відкриваються при вивченні ітерованих відображень. При цьому починають з деякої функції y = f (x) і розглядають поведінку послідовності f (x), f (f (x)), f (f (f (x ))),... У комплексній площині роботи такого роду сягають , по всій видимості, до імені Келі, який досліджував метод Ньютона знаходження кореня в додатку до комплексних, а не тільки до речових, функцій (1879). Чудового прогресу у вивченні ітерованих комплексних відображень домоглися Гастон Жюліа і П'єр Фату (1919). Природно, все було зроблено без допомоги комп'ютерної графіки. У наші дні, багато хто вже бачили барвисті постери з зображенням множин Жюліа і множини Мандельброта, тісно з ними пов'язаного. Освоєння математичної теорії хаосу природно почати саме з ітерованих відображень.
Вивчення фракталів та хаосу відкриває чудові можливості, як у дослідженні нескінченного числа додатків, так і в області чистої математики. Але в той же час, як це часто трапляється в так званій новій математиці, відкриття спираються на піонерські роботи великих математиків минулого. Сер Ісаак Ньютон розумів це, кажучи: «Якщо я і бачив далі інших, те тільки тому, що стояв на плечах гігантів».
2.КЛАСІЧЕСКІЕ ФРАКТАЛИ
2.1. Самоподоба.
Розділимо відрізок прямої на N рівних частин. Тоді кожну частину можна вважати копією всього відрізка, зменшеного в 1 / r разів. Очевидно, N і r пов'язані ставленням Nr = 1 Якщо квадрат розбити на N рівних квадратів (з площею, в 1 / r 2 разів менше площі вихідного), то співвідношення запишеться як Nr 2 = 1. Відповідно, загальна формула співвідношення запишеться у вигляді:
Nr d = 1. (2.1)
Безліч, побудовані вище, володіють цілою розмірністю. Задамося питанням, чи можливо таке побудова, при якому показник d в рівності (2.1) НЕ є цілим, тобто таке, що при розбитті вихідного безлічі на N непересічних підмножин, отриманих масштабуванням оригіналу з коефіцієнтом r, значення d не буде виражатися цілим числом. Відповідь --- рішуче так! Така безліч називається самоподібним фракталом. Величину d називають фрактальної (дробової) розмірністю або розмірністю подоби. Явна вираз для d через N і r знаходиться логарифмування обох частин (2.1):
logN
d = --------- (2.2)
log 1 / r
Логарифм можна взяти по будь-якій підставі, відмінному від одиниці, наприклад по підставі 10 або по підставі е ~ 2,7183.
2.2. Сніжинка Коха.
Кордон сніжинки, придуманою Гельгом фон Кохом в 1904 році (ріс.2.2.1), описується кривої, складеної з трьох однакових фракталів розмірності d ~ 1,2618. Кожна третину сніжинки будується ітеративне, починаючи з однією з сторін рівностороннього трикутника. Нехай K o --- Початковий відрізок. Приберемо середню третину і додамо два нових відрізка такої ж довжини, як показано на рис. 2.2.2. Назвемо отримане безліч K 1. Повторимо дану процедуру багато разів, на кожному кроці замінюючи середню третину двома новими відрізками. Позначимо через K n фігуру, отриману після n-го кроку.
Інтуїтивно ясно, що послідовність кривих K n при n прагне до нескінченності сходиться до деякої граничної кривої К. Розглянемо деякі властивості цієї кривої.
Якщо взяти копію К, зменшену в три рази (r = 1 / 3), То все безліч До можна скласти з N = 4 таких копій. Отже, ставлення самоподібності (2.1) виконується при зазначених N і r, а розмірність фракталу буде:
d = log (4) / log (3) ~ 1,2618
Рис 2.2.1. Сніжинка Коха.
Ще одна важлива властивість, якою володіє кордон сніжинки Коха --- її нескінченна довжина. Це може здатися дивним, тому що ми звикли мати справу з кривими з курсу математичного аналізу. Зазвичай гладкі або хоча б кусково-гладкі криві завжди мають кінцеву довжину (у чому можна переконатися інтегруванням). Мандельброт в зв'язку з цим опублікував ряд захоплюючих робіт, в яких досліджується питання про вимірювання довжини берегової лінії Великобританії. В якості моделі він
Рис. 2.2.2. Побудова сніжинки Коха.
SHAPE \ * MERGEFORMAT
використовував фрактальну криву, що нагадує кордон сніжинки за тим винятком, що в неї введений елемент випадковості, що враховує випадковість у природі. У результаті виявилося, що крива, що описує берегову лінію, має нескінченну довжину.
Доказ приводиться в [1].
2.3. Килим Серпінського.
Ще один приклад простого самоподібного фрактала --- килим Серпінського (рис. 2.3.1), придуманий польським математиком Вацлавом Вацлавом Серпіньським в 1915 році. Сам термін килим (gasket) належить Мандельброта. У способі побудови, наступному нижче, ми починаємо з деякої області і послідовно викидаємо внутрішні підобласті. Пізніше ми розглянемо й інші способи, зокрема з використанням L-систем, а також на основі ітерованих функцій.
Рис 2.3.1. Килим Серпінського
Нехай початкова множина S 0 --- рівносторонній трикутник разом з областю, яку він замикає. Розіб'ємо S 0 на чотири менші трикутні області, з'єднавши відрізками середини сторін початкового трикутника. Видалимо внутрішність маленької центральної трикутної області. Назвемо залишився безліч S 1 (рис. 2.3.2). Потім повторимо процес для кожного із трьох маленьких трикутників і отримаємо наступне наближення S 2. Продовжуючи таким чином, отримаємо послідовність вкладених множин S n, чиє перетин утворює килим S.
З побудови видно, що весь килим є об'єднання N = 3 істотно не пересічних зменшених у два рази копій; коефіцієнт подібності r = Ѕ (як по горизонталі, так і по вертикалі). Отже, S --- самоподібних фрактал з розмірністю:
d = log (3) / log (2) ~ 1,5850.
Рис. 2.3.2. Побудова килима Серпінського
Очевидно, що сумарна площа частин, викинутих при побудові, в точності дорівнює площі вихідного трикутника. На першому кроці ми викинули ј частину площі. На наступному кроці ми викинули три трикутники, причому площа кожного дорівнює ј 2 площі вихідного. Міркуючи таким чином, ми переконуємося, що повна частка викинутої площі становила:
1 / 4 + 3 * (1 / 4 2) + 3 2 * (1 / 4 3) + ... + 3 n-1 * (1 / 4 n) + ....
Ця сума дорівнює 1 (доказ в [1]). Отже, ми можемо стверджувати, що залишився безліч S, тобто килим, має площу міри нуль. Це виділяє безліч S в розряд «досконалого», в тому сенсі, що воно розбиває своє доповнення на нескінченне число трикутних областей, володіючи при цьому нульовою товщиною.
3. L-системи.
Поняття L-систем, тісно пов'язане з самоподібними фракталами, з'явилося тільки в 1968 році завдяки Арістріду Лінденмайеру. Спочатку L-системи були введені при вивченні формальних мов, а також використовувалися в біологічних моделях селекції. З їх допомогою можна будувати багато відомих самоподібні фрактали, включаючи сніжинку Коха і килим Серпінського. Деякі інші класичні побудови, наприклад криві Пеано (роботи Пеано, Гільберта, Серпинського), також укладаються в цю схему. І звичайно, L-системи відкривають шлях до нескінченною різноманітністю нових фракталів, що і послужило причиною їх широкого застосування в комп'ютерній графіці для побудови фрактальних дерев і рослин. Розглянуті в цій роботі L-системи обмежуються випадком детермінованих L-систем і графікою на площині.
Для графічної реалізації L-систем в якості підсистеми висновку використовується так звана Тертл-графіка (turtle - черепаха). При цьому точка (черепашка) рухається по екрану дискретними кроками, як правило прокреслюючи свій слід, але при необхідності може переміщатися без малювання. У нашому розпорядженні є три параметри (x, y, a), де (x, y) --- координати черепашки, a --- напрямок, в якому вона дивиться. Черепашка навчена інтерпретувати й виконувати послідовність команд, що задаються кодовим словом, літери якого читаються зліва направо. Кодове слово являє собою результат роботи L-системи і може включати наступні літери:
F --- переміститися вперед на один крок, промальовував слід.
b --- переміститися вперед на один крок, НЕ промальовував слід.
[--- Відкрити гілку (докладніше див нижче)
] --- Закрити гілку (докладніше див нижче)
+ --- Збільшити кут a на величину q
- --- Зменшити кут a на величину q
Розмір кроку і величина збільшення за кутом q задаються заздалегідь і залишаються незмінними для всіх переміщень черепашки. Якщо початкове напрямок руху а (кут, відлічуваний від позитивного напрямку осі Х) не вказано, то вважаємо а рівним нулю.
Кілька прикладів ілюструють застосування команд розгалуження (позначаються], [) і допоміжних змінних (позначаються X, Y, і т.д.). Команди розгалуження використовуються для побудови дерев рослин, а допоміжні змінні помітно полегшують побудову деяких L-систем.
Формально, детермінована L-система складається з алфавіту, слова ініціалізації, званого аксіомою або ініціатором, і набору породжують правил, що вказують, як слід перетворювати слово при переході від рівня до рівня (від ітерації до ітерації). Наприклад, можна замінювати букву F за допомогою породжує правила newf = F-F + + FF, що відповідає L-системі для сніжинки Коха, що розглядається нижче. Символи +, -,], [не оновлюються, а просто залишаються на тих місцях, де вони зустрілися. Оновлення букв у цьому слові передбачається одночасним, тобто букви слова одного рівня оновлюються раніше будь-який букви наступного рівня.
L-система, що відповідає сніжинці Коха (рис. 2.2.1), задається наступним чином:
p = p / 3
Аксіома: F + + F + + F
Породжує правило: newf = F-F + + FF
Графічне подання аксіоми F + + F + + F --- рівносторонній трикутник. Черепашка робить один крок вперед, потім кут а збільшується на 2p / 3 і черепашка робить ще один крок.
На першому кроці кожна буква F у слові-ініціатора F + + F + + F замінюється на F-F + + FF:
(F-F + + FF) + (F-F + + FF) + (F-F + + FF)
Повторюючи цей процес, на другому кроці отримаємо:
F-F + + FFF-F + + F-F + + F-F + + FFF-F + + F-F + F-F + + FFF-F + + F-F + + F-F + + FFF -F + + F-F + F-F + + FF-F-F + + F-F + + F-F + + FFF-F + + FF
і т.д. Причому, переконавшись на власному досвіді програмування L-систем знаю, що для сніжинки Коха на 20-й ітерації породжує правило займає кілька мегабайт тексту!
Ось ще деякі фрактали, побудовані з використанням L-системи:
Рис. 3.1. Дракон Хартера-Хатвея після 12-ти ітерацій
і його L-система:
p = p / 4
Аксіома: FX
Породжує правило: newf = F
newx = X + YF +
newy =-FX-Y
Рис 3.2. Дерево після 5-ти ітерацій
і його L-система:
p = p / 7
Аксіома: F
Породжує правило: newf = F [+ F] F [-F] F
Рис. 3.3. Квадрат Госпер після 2-х ітерацій [2]
і його L-система:
p = p / 2
Аксіома:-FX
Породжує правило: newf = F
n ewx = + FYFY-FX-FX + FY + FYFX + FY-FXFX-FY-FX + FYFXFX-FY-FXFY + FY + FX-FX-FY + FY + FXFX
newy = FYFY-FX-FX + FY + FY-FX-FXFY + FX + FYFYFX-FY + FX + FYFY + FX-FYFX-FX-FY + FY + FXFX-
4. Хаотична динаміка
4.1. Аттрактор Лоренца
До теперішнього моменту ми вивчали фрактали, які є статичними постатями. Наш підхід цілком прийнятний до тих пір, поки не виникає необхідність розгляду таких природних явищ, як падаючі потоки води, турбулентні завихрення диму, метеосістеми і потоки на виході реактивних двигунів. У цих випадках один-єдиний фрактал відповідає моментального знімку даного феномена. Структури, що змінюються в часі, ми визначаємо як динамічні системи. Інтуїтивно зрозуміло, що динамічної протилежністю фрактала є хаос. Це означає, що хаос описує стан крайньої непередбачуваності, що виникає у динамічній системі, в той час як фрактальність описує крайню іррегулярностью або изрезанность, притаманну геометричної конфігурації.
Досить швидко стало зрозуміло, що багато хаотичні динамічні системи, що описують феномени оточуючого нас світу, влаштовані дуже складно і не можуть бути представлені традиційними методами математичного аналізу. Мабуть, немає ніякої можливості отримати математичні вирази для рішень в замкнутому вигляді, навіть якщо використовувати нескінченні ряди або спеціальні функції.
Розглянемо знаменитий приклад, вельми наочно демонструє, що стоїть за терміном «хаотична динаміка». Едвард Лоренц з Массачусетського технологічного інституту в 1961 році займався чисельними дослідженнями метеосістем, зокрема моделюванням конвекційних струмів в атмосфері [1]. Він написав програму для вирішення наступної системи диференціальних рівнянь:
dx / dt = s (-x + y),
dy / dt = rx - y - xz,
dz / dt =-bz + xy.
У подальших розрахунках параметри s, r і b постійні і приймають значення s = -10, r = 28 і b = 8 / 3.
Згідно з описом експерименту, який належить самому Лоренцу, він знаходив значення рішення протягом тривалого часу, а потім зупинив рахунок. Його зацікавила деяка особливість рішення, яка виникала десь в середині інтервалу рахунки, і тому він повторив обчислення з цього моменту. Результати повторного рахунку, очевидно, збіглися б з результатами початкового рахунку, якщо б початкові значення для повторного рахунку в точності були рівні отриманим раніше значенням для цього моменту часу. Лоренц злегка змінив ці значення, зменшивши число вірних десяткових знаків. Помилки, введені таким чином, були вкрай невеликі. Але найнесподіваніше було попереду. Знову перелічене рішення деякий час добре узгоджувалося зі старим. Проте, в міру рахунку розбіжність зростала, і поступово стало ясно, що нове рішення зовсім не нагадує старе (малюнки наведено в [1], стор 149).
Лоренц знову повторював і перевіряв обчислення (ймовірно, не довіряючи комп'ютера), перш ніж усвідомив важливість експерименту. Те, що він спостерігав, тепер називається суттєвою залежністю від початкових умов --- основною рисою, притаманною хаотичної динаміці. Істотну залежність іноді називають ефектом метелика. Таку назву відноситься до неможливості робити довгострокові прогнози погоди. Сам Лоренц роз'яснив це поняття у статті «Передбачуваність: чи може помах крилець метелика у Бразилії призвести до утворення торнадо в Техасі?», Опублікованій в 1979 році [3, стор 322].
Незважаючи на велику значимість експерименту Лоренца, в даній курсовій роботі не будуть розглядатися моделі, пов'язані з динамічними системами, описуваними диференціальними рівняннями. Навпаки, ми будемо розглядати найпростіші моделі хаотичної динаміки --- дискретні, до яких відноситься знамените і всюдисуще безліч Мандельброта і супутні йому безлічі Жюліа.
Рис. 4.1.1. Аттрактор Лоренца.
4.2. Множини Мандельброта і Жюліа.
Ймовірно, не можна навести приклад такого комп'ютерного експерименту, який враженням від результатів перевершував би те почуття подиву, і захоплення, яке викликає графічну побудову множин Мандельброта і безлічі Жюліа на площині. Ці безлічі відносяться до хаотичної динаміці на комплексній площині.
Безліч Мандельброта і безліч Жюліа визначається як межа безлічі точок z, що прагнуть до нескінченності при ітерірованіі
f (z) = z 2 + c,
де с - комплексна константа. При цьому безлічі Жюліа (див. рис. 4.2.2) при різних із можуть представлятися як завгодно складно і красиво, але всі вони розподіляються на два типи: зв'язкові або незв'язні. Безліч Мандельброта (див. рис. 4.2.1) служить індикатором для двох типів множин Жюліа функції z 2 + c. Кожна точка в множині Мандельброта представляє значення с, для якого безліч Жюліа цілком докладно і кожна точка з доповнення до безлічі Мандельброта представляє значення с, для якого безліч Жюліа цілком нескладно.
Побудова даних множин зводиться до побудови орбіт f (z), що перевіряються на обмеженість. Тобто на малюнок потрапляє лише та точка на комплексній площині (закладена плоским екраном монітора), яка при ітерірованіі функції f (z 0), остання не прагне до нескінченності, а залишається обмеженою на якомусь рівні. Перевірка йде для кожної точки (x, y).
Нескладно написати програму для побудови множини Мандельброта. Єдина проблема, яка може виникнути при використанні цієї програми на малопотужних ЕОМ --- великий обсяг обчислень. Для того, щоб отримати прийнятне зображення множини, бажано відображати щонайменше 256x256 пікселів. Більш вдалі візуалізації виходять при використанні вікна 400x400 пікселів і більше. При цьому кількість ітерацій достатньо 20-ти. Для отримання більш якісного побудови безлічі можна збільшити кількість ітерацій до 50, 70, 100 і більше.
Рис 4.2.1 Область 3-періодичності множини Мандельброта
Рис. 4.2.2. Безліч Жюліа.
5. ВИСНОВОК.
Дана курсова робота є введенням у світ фракталів. Ми розглянули тільки саму малу частину того, які бувають фрактали, на основі яких принципів вони будуються. Наприклад в книгу [1] включений розгляд СІФ (систем ітерованих функцій), випадкових фракталів, і багато іншого з теорії фракталів.
На додаток хочеться відзначити застосування фракталів в комп'ютерних технологіях, крім просто побудови красивих зображень на екрані комп'ютера. Фрактали в комп'ютерних технологіях застосовуються в наступних областях:
1. Стиснення зображень та інформації
2. Приховування інформації на зображенні, в звуці, ...
3. Шифрування даних за допомогою фрактальних алгоритмів
4. Створення фрактальної музики
5. Моделювання систем
6. СПИСОК ЛІТЕРАТУРИ
1. Фрактали і хаос у динамічних системах. Основи теорії. Москва: Постмаркет, 2000. - 352 с.
2. Програма FractInt © 1990 Soup Group Company.
3. James Gleick, Chaos: Making a New Science, Viking, New York, 1987.
1. ВСТУП ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 2
2. КЛАСИЧНІ ФРАКТАЛИ ... ... ... ... ... ... ... ... ... ... ... .. 3
2.1. Самоподоба ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .3
2.2. Сніжинка Коха ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 3
2.3. Килим Серпінського ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 5
3. L-СИСТЕМИ ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .... 6
4. Хаотична динаміка ... ... ... ... ... ... ... ... ... ... ... ... 10
4.1. Аттрактор Лоренца ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 10
4.2. Множини Мандельброта і Жюліа ... ... ... ... ... ... ... ... .. 11
5. ВИСНОВОК ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 13
6. СПИСОК ЛІТЕРАТУРИ ... ... ... ... ... ... ... ... ... ... ... ... ... ... .14
1.Вступ
Коли більшості людей здавалося, що геометрія в природі обмежується такими простими фігурами, як лінія, коло, конічний перетин, багатокутник, сфера, квадратична поверхню, а також їх комбінаціями. Наприклад, що може бути гарніше твердження про те, що планети в нашій сонячній системі рухаються навколо сонця по еліптичних орбітах?
Однак багато природні системи настільки складні і нерегулярні, що використання лише знайомих об'єктів класичної геометрії для їх моделювання представляється безнадійним. Як наприклад, побудувати модель гірського хребта або крони дерева в термінах геометрії? Як описати те різноманіття біологічних конфігурацій, яке ми спостерігаємо в світі рослин і тварин? Уявіть собі всю складність системи кровообігу, що складається з безлічі капілярів і судин і доставляє кров до кожної клітинки людського тіла. Уявіть, як хитромудро влаштовані легені та нирки, що нагадують за структурою дерева з гіллястою кроною.
Настільки ж складною та нерегулярної може бути і динаміка реальних природних систем. Як підступитися до моделювання каскадних водоспадів або турбулентних процесів, що визначають погоду?
Фрактали і математичний хаос --- відповідні засоби для дослідження поставлених питань. Термін фрактал відноситься до деякої статичної геометричної конфігурації, такий як миттєвий знімок водоспаду. Хаос --- термін динаміки, використовуваний для опису явищ, подібних турбулентному поведінки погоди. Нерідко те, що ми спостерігаємо в природі, інтригує нас нескінченним повторенням одного і того ж візерунка, збільшеного чи зменшеного у скільки завгодно разів. Наприклад, у дерева є гілки. На цих гілках є гілки трохи менше і т.д. Теоретично, елемент «розгалуження» повторюється нескінченно багато разів, стаючи все менше і менше. Те ж саме можна помітити, роздивляючись фотографію гірського рельєфу. Спробуйте трохи наблизити зображення гірської гряди --- ви знову побачите гори. Так виявляється характерне для фракталов властивість самоподібності.
У багатьох роботах по фракталах самоподібність використовується як визначального властивості. Дотримуючись Бенуа Мадельброту, ми приймаємо точку зору, згідно з якою фрактали повинні визначатися в термінах фрактальної (дробової) розмірності. Звідси і походження слова фрактал (від лат. Fractus --- дробовий).
Поняття дробової розмірності являє собою складну концепцію, яка викладається в кілька етапів. Пряма --- це одновимірний об'єкт, а площину --- двовимірний. Якщо гарненько перекрутивши пряму і площину, можна підвищити розмірність отриманої конфігурації, при цьому нова розмірність звичайно буде дробової в деякому сенсі, який нам належить уточнити. Зв'язок дробової розмірності і самоподібності полягає в тому, що за допомогою самоподібності можна сконструювати безліч дробової розмірності найбільш простим чином. Навіть у випадку набагато більш складних фракталів, таких як межа множини Мандельброта, коли чисте самоподібність відсутня, є майже повне повторення базової форми у все більш і більш зменшеному вигляді.
Багато чудові властивості фракталів та хаосу відкриваються при вивченні ітерованих відображень. При цьому починають з деякої функції y = f (x) і розглядають поведінку послідовності f (x), f (f (x)), f (f (f (x ))),... У комплексній площині роботи такого роду сягають , по всій видимості, до імені Келі, який досліджував метод Ньютона знаходження кореня в додатку до комплексних, а не тільки до речових, функцій (1879). Чудового прогресу у вивченні ітерованих комплексних відображень домоглися Гастон Жюліа і П'єр Фату (1919). Природно, все було зроблено без допомоги комп'ютерної графіки. У наші дні, багато хто вже бачили барвисті постери з зображенням множин Жюліа і множини Мандельброта, тісно з ними пов'язаного. Освоєння математичної теорії хаосу природно почати саме з ітерованих відображень.
Вивчення фракталів та хаосу відкриває чудові можливості, як у дослідженні нескінченного числа додатків, так і в області чистої математики. Але в той же час, як це часто трапляється в так званій новій математиці, відкриття спираються на піонерські роботи великих математиків минулого. Сер Ісаак Ньютон розумів це, кажучи: «Якщо я і бачив далі інших, те тільки тому, що стояв на плечах гігантів».
2.КЛАСІЧЕСКІЕ ФРАКТАЛИ
2.1. Самоподоба.
Розділимо відрізок прямої на N рівних частин. Тоді кожну частину можна вважати копією всього відрізка, зменшеного в 1 / r разів. Очевидно, N і r пов'язані ставленням Nr = 1 Якщо квадрат розбити на N рівних квадратів (з площею, в 1 / r 2 разів менше площі вихідного), то співвідношення запишеться як Nr 2 = 1. Відповідно, загальна формула співвідношення запишеться у вигляді:
Nr d = 1. (2.1)
Безліч, побудовані вище, володіють цілою розмірністю. Задамося питанням, чи можливо таке побудова, при якому показник d в рівності (2.1) НЕ є цілим, тобто таке, що при розбитті вихідного безлічі на N непересічних підмножин, отриманих масштабуванням оригіналу з коефіцієнтом r, значення d не буде виражатися цілим числом. Відповідь --- рішуче так! Така безліч називається самоподібним фракталом. Величину d називають фрактальної (дробової) розмірністю або розмірністю подоби. Явна вираз для d через N і r знаходиться логарифмування обох частин (2.1):
logN
d = --------- (2.2)
log 1 / r
Логарифм можна взяти по будь-якій підставі, відмінному від одиниці, наприклад по підставі 10 або по підставі е ~ 2,7183.
2.2. Сніжинка Коха.
Кордон сніжинки, придуманою Гельгом фон Кохом в 1904 році (ріс.2.2.1), описується кривої, складеної з трьох однакових фракталів розмірності d ~ 1,2618. Кожна третину сніжинки будується ітеративне, починаючи з однією з сторін рівностороннього трикутника. Нехай K o --- Початковий відрізок. Приберемо середню третину і додамо два нових відрізка такої ж довжини, як показано на рис. 2.2.2. Назвемо отримане безліч K 1. Повторимо дану процедуру багато разів, на кожному кроці замінюючи середню третину двома новими відрізками. Позначимо через K n фігуру, отриману після n-го кроку.
Інтуїтивно ясно, що послідовність кривих K n при n прагне до нескінченності сходиться до деякої граничної кривої К. Розглянемо деякі властивості цієї кривої.
Якщо взяти копію К, зменшену в три рази (r = 1 / 3), То все безліч До можна скласти з N = 4 таких копій. Отже, ставлення самоподібності (2.1) виконується при зазначених N і r, а розмірність фракталу буде:
d = log (4) / log (3) ~ 1,2618
Рис 2.2.1. Сніжинка Коха.
Ще одна важлива властивість, якою володіє кордон сніжинки Коха --- її нескінченна довжина. Це може здатися дивним, тому що ми звикли мати справу з кривими з курсу математичного аналізу. Зазвичай гладкі або хоча б кусково-гладкі криві завжди мають кінцеву довжину (у чому можна переконатися інтегруванням). Мандельброт в зв'язку з цим опублікував ряд захоплюючих робіт, в яких досліджується питання про вимірювання довжини берегової лінії Великобританії. В якості моделі він
Рис. 2.2.2. Побудова сніжинки Коха.
SHAPE \ * MERGEFORMAT
(А) |
(Б) |
(В) |
(Г) |
використовував фрактальну криву, що нагадує кордон сніжинки за тим винятком, що в неї введений елемент випадковості, що враховує випадковість у природі. У результаті виявилося, що крива, що описує берегову лінію, має нескінченну довжину.
Доказ приводиться в [1].
2.3. Килим Серпінського.
Ще один приклад простого самоподібного фрактала --- килим Серпінського (рис. 2.3.1), придуманий польським математиком Вацлавом Вацлавом Серпіньським в 1915 році. Сам термін килим (gasket) належить Мандельброта. У способі побудови, наступному нижче, ми починаємо з деякої області і послідовно викидаємо внутрішні підобласті. Пізніше ми розглянемо й інші способи, зокрема з використанням L-систем, а також на основі ітерованих функцій.
Рис 2.3.1. Килим Серпінського
Нехай початкова множина S 0 --- рівносторонній трикутник разом з областю, яку він замикає. Розіб'ємо S 0 на чотири менші трикутні області, з'єднавши відрізками середини сторін початкового трикутника. Видалимо внутрішність маленької центральної трикутної області. Назвемо залишився безліч S 1 (рис. 2.3.2). Потім повторимо процес для кожного із трьох маленьких трикутників і отримаємо наступне наближення S 2. Продовжуючи таким чином, отримаємо послідовність вкладених множин S n, чиє перетин утворює килим S.
З побудови видно, що весь килим є об'єднання N = 3 істотно не пересічних зменшених у два рази копій; коефіцієнт подібності r = Ѕ (як по горизонталі, так і по вертикалі). Отже, S --- самоподібних фрактал з розмірністю:
d = log (3) / log (2) ~ 1,5850.
Рис. 2.3.2. Побудова килима Серпінського
Очевидно, що сумарна площа частин, викинутих при побудові, в точності дорівнює площі вихідного трикутника. На першому кроці ми викинули ј частину площі. На наступному кроці ми викинули три трикутники, причому площа кожного дорівнює ј 2 площі вихідного. Міркуючи таким чином, ми переконуємося, що повна частка викинутої площі становила:
1 / 4 + 3 * (1 / 4 2) + 3 2 * (1 / 4 3) + ... + 3 n-1 * (1 / 4 n) + ....
Ця сума дорівнює 1 (доказ в [1]). Отже, ми можемо стверджувати, що залишився безліч S, тобто килим, має площу міри нуль. Це виділяє безліч S в розряд «досконалого», в тому сенсі, що воно розбиває своє доповнення на нескінченне число трикутних областей, володіючи при цьому нульовою товщиною.
3. L-системи.
Поняття L-систем, тісно пов'язане з самоподібними фракталами, з'явилося тільки в 1968 році завдяки Арістріду Лінденмайеру. Спочатку L-системи були введені при вивченні формальних мов, а також використовувалися в біологічних моделях селекції. З їх допомогою можна будувати багато відомих самоподібні фрактали, включаючи сніжинку Коха і килим Серпінського. Деякі інші класичні побудови, наприклад криві Пеано (роботи Пеано, Гільберта, Серпинського), також укладаються в цю схему. І звичайно, L-системи відкривають шлях до нескінченною різноманітністю нових фракталів, що і послужило причиною їх широкого застосування в комп'ютерній графіці для побудови фрактальних дерев і рослин. Розглянуті в цій роботі L-системи обмежуються випадком детермінованих L-систем і графікою на площині.
Для графічної реалізації L-систем в якості підсистеми висновку використовується так звана Тертл-графіка (turtle - черепаха). При цьому точка (черепашка) рухається по екрану дискретними кроками, як правило прокреслюючи свій слід, але при необхідності може переміщатися без малювання. У нашому розпорядженні є три параметри (x, y, a), де (x, y) --- координати черепашки, a --- напрямок, в якому вона дивиться. Черепашка навчена інтерпретувати й виконувати послідовність команд, що задаються кодовим словом, літери якого читаються зліва направо. Кодове слово являє собою результат роботи L-системи і може включати наступні літери:
F --- переміститися вперед на один крок, промальовував слід.
b --- переміститися вперед на один крок, НЕ промальовував слід.
[--- Відкрити гілку (докладніше див нижче)
] --- Закрити гілку (докладніше див нижче)
+ --- Збільшити кут a на величину q
- --- Зменшити кут a на величину q
Розмір кроку і величина збільшення за кутом q задаються заздалегідь і залишаються незмінними для всіх переміщень черепашки. Якщо початкове напрямок руху а (кут, відлічуваний від позитивного напрямку осі Х) не вказано, то вважаємо а рівним нулю.
Кілька прикладів ілюструють застосування команд розгалуження (позначаються], [) і допоміжних змінних (позначаються X, Y, і т.д.). Команди розгалуження використовуються для побудови дерев рослин, а допоміжні змінні помітно полегшують побудову деяких L-систем.
Формально, детермінована L-система складається з алфавіту, слова ініціалізації, званого аксіомою або ініціатором, і набору породжують правил, що вказують, як слід перетворювати слово при переході від рівня до рівня (від ітерації до ітерації). Наприклад, можна замінювати букву F за допомогою породжує правила newf = F-F + + FF, що відповідає L-системі для сніжинки Коха, що розглядається нижче. Символи +, -,], [не оновлюються, а просто залишаються на тих місцях, де вони зустрілися. Оновлення букв у цьому слові передбачається одночасним, тобто букви слова одного рівня оновлюються раніше будь-який букви наступного рівня.
L-система, що відповідає сніжинці Коха (рис. 2.2.1), задається наступним чином:
p = p / 3
Аксіома: F + + F + + F
Породжує правило: newf = F-F + + FF
Графічне подання аксіоми F + + F + + F --- рівносторонній трикутник. Черепашка робить один крок вперед, потім кут а збільшується на 2p / 3 і черепашка робить ще один крок.
На першому кроці кожна буква F у слові-ініціатора F + + F + + F замінюється на F-F + + FF:
(F-F + + FF) + (F-F + + FF) + (F-F + + FF)
Повторюючи цей процес, на другому кроці отримаємо:
F-F + + FFF-F + + F-F + + F-F + + FFF-F + + F-F + F-F + + FFF-F + + F-F + + F-F + + FFF -F + + F-F + F-F + + FF-F-F + + F-F + + F-F + + FFF-F + + FF
і т.д. Причому, переконавшись на власному досвіді програмування L-систем знаю, що для сніжинки Коха на 20-й ітерації породжує правило займає кілька мегабайт тексту!
Ось ще деякі фрактали, побудовані з використанням L-системи:
Рис. 3.1. Дракон Хартера-Хатвея після 12-ти ітерацій
і його L-система:
p = p / 4
Аксіома: FX
Породжує правило: newf = F
newx = X + YF +
newy =-FX-Y
Рис 3.2. Дерево після 5-ти ітерацій
і його L-система:
p = p / 7
Аксіома: F
Породжує правило: newf = F [+ F] F [-F] F
Рис. 3.3. Квадрат Госпер після 2-х ітерацій [2]
і його L-система:
p = p / 2
Аксіома:-FX
Породжує правило: newf = F
n ewx = + FYFY-FX-FX + FY + FYFX + FY-FXFX-FY-FX + FYFXFX-FY-FXFY + FY + FX-FX-FY + FY + FXFX
newy = FYFY-FX-FX + FY + FY-FX-FXFY + FX + FYFYFX-FY + FX + FYFY + FX-FYFX-FX-FY + FY + FXFX-
4. Хаотична динаміка
4.1. Аттрактор Лоренца
До теперішнього моменту ми вивчали фрактали, які є статичними постатями. Наш підхід цілком прийнятний до тих пір, поки не виникає необхідність розгляду таких природних явищ, як падаючі потоки води, турбулентні завихрення диму, метеосістеми і потоки на виході реактивних двигунів. У цих випадках один-єдиний фрактал відповідає моментального знімку даного феномена. Структури, що змінюються в часі, ми визначаємо як динамічні системи. Інтуїтивно зрозуміло, що динамічної протилежністю фрактала є хаос. Це означає, що хаос описує стан крайньої непередбачуваності, що виникає у динамічній системі, в той час як фрактальність описує крайню іррегулярностью або изрезанность, притаманну геометричної конфігурації.
Досить швидко стало зрозуміло, що багато хаотичні динамічні системи, що описують феномени оточуючого нас світу, влаштовані дуже складно і не можуть бути представлені традиційними методами математичного аналізу. Мабуть, немає ніякої можливості отримати математичні вирази для рішень в замкнутому вигляді, навіть якщо використовувати нескінченні ряди або спеціальні функції.
Розглянемо знаменитий приклад, вельми наочно демонструє, що стоїть за терміном «хаотична динаміка». Едвард Лоренц з Массачусетського технологічного інституту в 1961 році займався чисельними дослідженнями метеосістем, зокрема моделюванням конвекційних струмів в атмосфері [1]. Він написав програму для вирішення наступної системи диференціальних рівнянь:
dx / dt = s (-x + y),
dy / dt = rx - y - xz,
dz / dt =-bz + xy.
У подальших розрахунках параметри s, r і b постійні і приймають значення s = -10, r = 28 і b = 8 / 3.
Згідно з описом експерименту, який належить самому Лоренцу, він знаходив значення рішення протягом тривалого часу, а потім зупинив рахунок. Його зацікавила деяка особливість рішення, яка виникала десь в середині інтервалу рахунки, і тому він повторив обчислення з цього моменту. Результати повторного рахунку, очевидно, збіглися б з результатами початкового рахунку, якщо б початкові значення для повторного рахунку в точності були рівні отриманим раніше значенням для цього моменту часу. Лоренц злегка змінив ці значення, зменшивши число вірних десяткових знаків. Помилки, введені таким чином, були вкрай невеликі. Але найнесподіваніше було попереду. Знову перелічене рішення деякий час добре узгоджувалося зі старим. Проте, в міру рахунку розбіжність зростала, і поступово стало ясно, що нове рішення зовсім не нагадує старе (малюнки наведено в [1], стор 149).
Лоренц знову повторював і перевіряв обчислення (ймовірно, не довіряючи комп'ютера), перш ніж усвідомив важливість експерименту. Те, що він спостерігав, тепер називається суттєвою залежністю від початкових умов --- основною рисою, притаманною хаотичної динаміці. Істотну залежність іноді називають ефектом метелика. Таку назву відноситься до неможливості робити довгострокові прогнози погоди. Сам Лоренц роз'яснив це поняття у статті «Передбачуваність: чи може помах крилець метелика у Бразилії призвести до утворення торнадо в Техасі?», Опублікованій в 1979 році [3, стор 322].
Незважаючи на велику значимість експерименту Лоренца, в даній курсовій роботі не будуть розглядатися моделі, пов'язані з динамічними системами, описуваними диференціальними рівняннями. Навпаки, ми будемо розглядати найпростіші моделі хаотичної динаміки --- дискретні, до яких відноситься знамените і всюдисуще безліч Мандельброта і супутні йому безлічі Жюліа.
Рис. 4.1.1. Аттрактор Лоренца.
4.2. Множини Мандельброта і Жюліа.
Ймовірно, не можна навести приклад такого комп'ютерного експерименту, який враженням від результатів перевершував би те почуття подиву, і захоплення, яке викликає графічну побудову множин Мандельброта і безлічі Жюліа на площині. Ці безлічі відносяться до хаотичної динаміці на комплексній площині.
Безліч Мандельброта і безліч Жюліа визначається як межа безлічі точок z, що прагнуть до нескінченності при ітерірованіі
f (z) = z 2 + c,
де с - комплексна константа. При цьому безлічі Жюліа (див. рис. 4.2.2) при різних із можуть представлятися як завгодно складно і красиво, але всі вони розподіляються на два типи: зв'язкові або незв'язні. Безліч Мандельброта (див. рис. 4.2.1) служить індикатором для двох типів множин Жюліа функції z 2 + c. Кожна точка в множині Мандельброта представляє значення с, для якого безліч Жюліа цілком докладно і кожна точка з доповнення до безлічі Мандельброта представляє значення с, для якого безліч Жюліа цілком нескладно.
Побудова даних множин зводиться до побудови орбіт f (z), що перевіряються на обмеженість. Тобто на малюнок потрапляє лише та точка на комплексній площині (закладена плоским екраном монітора), яка при ітерірованіі функції f (z 0), остання не прагне до нескінченності, а залишається обмеженою на якомусь рівні. Перевірка йде для кожної точки (x, y).
Нескладно написати програму для побудови множини Мандельброта. Єдина проблема, яка може виникнути при використанні цієї програми на малопотужних ЕОМ --- великий обсяг обчислень. Для того, щоб отримати прийнятне зображення множини, бажано відображати щонайменше 256x256 пікселів. Більш вдалі візуалізації виходять при використанні вікна 400x400 пікселів і більше. При цьому кількість ітерацій достатньо 20-ти. Для отримання більш якісного побудови безлічі можна збільшити кількість ітерацій до 50, 70, 100 і більше.
Рис 4.2.1 Область 3-періодичності множини Мандельброта
Рис. 4.2.2. Безліч Жюліа.
5. ВИСНОВОК.
Дана курсова робота є введенням у світ фракталів. Ми розглянули тільки саму малу частину того, які бувають фрактали, на основі яких принципів вони будуються. Наприклад в книгу [1] включений розгляд СІФ (систем ітерованих функцій), випадкових фракталів, і багато іншого з теорії фракталів.
На додаток хочеться відзначити застосування фракталів в комп'ютерних технологіях, крім просто побудови красивих зображень на екрані комп'ютера. Фрактали в комп'ютерних технологіях застосовуються в наступних областях:
1. Стиснення зображень та інформації
2. Приховування інформації на зображенні, в звуці, ...
3. Шифрування даних за допомогою фрактальних алгоритмів
4. Створення фрактальної музики
5. Моделювання систем
6. СПИСОК ЛІТЕРАТУРИ
1. Фрактали і хаос у динамічних системах. Основи теорії. Москва: Постмаркет, 2000. - 352 с.
2. Програма FractInt © 1990 Soup Group Company.
3. James Gleick, Chaos: Making a New Science, Viking, New York, 1987.
[1] Дослідження аттрактора Лоренца включається зараз в будь-який
математичний пакет, наприклад, Mathematica, Maple.
математичний пакет, наприклад, Mathematica, Maple.