Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Безліч Мандельброта



План:


Введення

Безліч Мандельброта

Безліч Мандельброта - це безліч таких точок c на комплексній площині, для яких ітеративна послідовність z 0 = 0, z n = z n -1 2 + c (n = 1, 2, 3, ...) не йде на нескінченність. Тобто, це безліч таких c, для яких існує дійсне R, що нерівність | z n | виконується при всіх натуральних n.

Безліч Мандельброта є в певному сенсі фракталом. Його фрагменти не строго подібні вихідного безлічі, але при багаторазовому збільшенні певні частини все більше схожі один на одного.


1. Розширене визначення

Таким чином, вищевказана послідовність може бути розкрита для кожної точки c \! на комплексній площині таким чином:

c = x + i \ cdot y \,
Z_0 = 0 \,
\ Begin {matrix} Z_1 & = & Z_0 ^ 2 + c \ \ \ & = & x + iy \ end {matrix} \,
\ Begin {matrix} Z_2 & = & Z_1 ^ 2 + c \ \ \ & = & (x + iy) ^ 2 + x + iy \ \ \ & = & x ^ 2 +2 ixy-y ^ 2 + x + iy \ \ \ & = & x ^ 2-y ^ 2 + x + (2xy + y) i \ end {matrix} \,
Z_3 = Z_2 ^ 2 + c = ... \,

і так далі.

Якщо переформулювати ці вирази у вигляді ітеративної послідовності значень координат комплексної площини x \! і y \! , Тобто замінивши z_n \! на x_n + i \ cdot y_n , А c \! на p + i \ cdot q \! , Ми отримаємо:

x_ {n +1} = {x_n} ^ 2 - {y_n} ^ 2 + p \,
y_ {n +1} = 2 {x_n} {y_n} + q \,

Візуально, всередині множини Мандельброта можна виділити нескінченна кількість елементарних фігур, причому найбільша в центрі являє собою кардиоиду. Також є набір овалів, що стосуються кардіоїда, розмір яких поступово зменшується, прагнучи до нуля. Кожен з цих овалів має свій набір менших овалів, діаметр яких також прагне до нуля і т. д. Цей процес триває нескінченно, утворюючи фрактал. Також важливо, що ці процеси розгалуження фігур не вичерпують повністю безліч Мандельброта: якщо розглянути із збільшенням додаткові "гілки", то в них можна побачити свої кардіоїда і круги, не пов'язані з головною фігурою. Найбільша фігура (видима при розгляданні основного безлічі) з них знаходиться в області від -1,78 до -1,75 на негативній осі дійсних значень.


2. Історія множини Мандельброта

Вперше безліч Мандельброта було описано в 1905 П'єром Фату (Pierre Fatou), французьким математиком, який працював в області аналітичної динаміки комплексних чисел. Фату вивчав рекурсивні процеси виду

z \ to z ^ 2 + c \,

Почавши з точки z_0 \! на комплексній площині, можна отримати нові точки, послідовно застосовуючи до них цю формулу. Така послідовність точок називається орбітою z_0 \! при перетворенні z \ to z ^ 2 + c \,

Фату знайшов, що орбіта z_0 = 0 \! при цьому перетворенні показує досить складне і цікаве поведінку. Існує нескінченна безліч таких перетворень - своє для кожного значення c \! . В ті часи комп'ютерів ще не було, і Фату, звичайно, не міг побудувати орбіти всіх точок площини, йому доводилося все робити вручну. Грунтуючись на своїх розрахунках, він довів, що орбіта точки, що лежить на відстані більше 2 від початку координат, завжди йде в нескінченність.

Фату ніколи не бачив зображень, які ми зараз знаємо як зображення множини Мандельброта, тому що необхідну кількість обчислень неможливо провести вручну. Професор Бенуа Мандельброт був першим, хто використав для цього комп'ютер.

Фрактали були описані Мандельброт в 1975 в його книзі "Les Objets Fractals: Forme, Hasard et Dimension" ("Фрактальні об'єкти: форма, випадковість і розмірність"). У цій книзі Мандельброт вперше використав термін "фрактал" для позначення математичного феномена, який демонструє настільки непередбачуване і дивовижне поведінка. Ці феномени народжувалися при використанні рекурсивного алгоритму для отримання якої-небудь кривої або безлічі. Безліч Мандельброта - один з таких феноменів, названий по імені свого дослідника.


3. Побудова безлічі

Нескладно довести, що як тільки модуль z n виявиться більше 2 (або, в термінах дійсної і уявної частин, x n 2 + y n 2> 4), послідовність стане прагнути до нескінченності. У разі | c | ≤ 2 це можна довести за допомогою методу математичної індукції. При | c |> 2 точка c свідомо не належить безлічі Мандельброта, що також можна вивести методом індукції, використовуючи рівність z 0 = 0. (Хоча в цьому випадку може існувати інше z 0, для якого відповідна послідовність обмежена по модулю, але для деякого n виконується нерівність | z n |> 2.)

Порівняння | z n | з цим числом (в англомовній літературі його називають "bail-out") дозволяє виділяти точки, які не потрапляють всередину безлічі. Для точок, що лежать всередині безлічі, послідовність не буде мати тенденції до нескінченності і ніколи не досягне цього числа, тому після певного числа ітерацій розрахунок необхідно примусово завершити. Максимальне число ітерацій, після яких число вважається потрапили всередину безлічі, задається в програмі.

Зображення, отримане в такий спосіб, є лише наближенням до реального безлічі Мандельброта. Більш якісні результати можна отримувати, збільшуючи максимальну кількість ітерацій, однак при цьому пропорційно виростає і час розрахунків.

Приклад програми побудови множини (на мові програмування PHP):

  / * Безліч Мандельброта. * /  / * Час створення * /  set_time_limit  (  120  )  ;  function  re_microtime  (  )  {  list  (  $ Usec  ,  $ Sec  )  =  explode  (  ""  ,  microtime  (  )  )  ;  return  (  (  float  )  $ Usec  +  (  float  )  $ Sec  )  ;  }  / * Засікаємо * /  $ Time_start  =  re_microtime  (  )  ;  / * Розмір картинки * /  $ Img_w  =  900  ;  $ Img_h  =  600  ;  / * Початок і кінець креслення * /  $ X_min  =  -  2  ;  $ X_max  =  1  ;  $ Y_min  =  -  1  ;  $ Y_max  =  1  ;  / * Підрахунок кроку * /  if  (  $ X_min  > =  0  &&  $ X_max  > =  0  )  {  $ Step  =  (  $ X_min  +  $ X_max  )  /  $ Img_w  ;  }  elseif  (  $ X_min  <  0  &&  $ X_max  > =  0  )  {  $ Step  =  (  $ X_max  -  $ X_min  )  /  $ Img_w  ;  }  else  {  $ Step  =  (  -  $ X_min  +  $ X_max  )  /  $ Img_w  ;  }  $ Img  =  imagecreatetruecolor  (  $ Img_w  ,  $ Img_h  )  ;  $ C  =  array  (  )  ;  $ Yy  =  0  ;  for  (  $ Y  =  $ Y_min  ;  $ Y  <  $ Y_max  ;  $ Y  =  $ Y  +  $ Step  )  {  $ Xx  =  0  ;  for  (  $ X  =  $ X_min  ;  $ X  <  $ X_max  ;  $ X  =  $ X  +  $ Step  )  {  $ C  [  'X'  ]  =  $ X  ;  $ C  [  'Y'  ]  =  $ Y  ;  $ X  =  $ X  ;  $ Y  =  $ Y  ;  $ Ix  =  0  ;  $ Iy  =  0  ;  $ N  =  0  ;  while  (  (  $ Ix  *  $ Ix  +  $ Iy  *  $ Iy  <  5  )  and  (  $ N  <  64  )  )  {  $ Ix  =  $ X  *  $ X  -  $ Y  *  $ Y  +  $ C  [  'X'  ]  ;  $ Iy  =  2  *  $ X  *  $ Y  +  $ C  [  'Y'  ]  ;  $ X  =  $ Ix  ;  $ Y  =  $ Iy  ;  $ N  + +;  }  $ Col  =  imagecolorallocate  (  $ Img  ,  255  -  $ N  *  5  ,  0  ,  0  )  ;  imagesetpixel  (  $ Img  ,  $ Xx  ,  $ Yy  ,  $ Col  )  ;  $ Xx  + +;  }  $ Yy  + +;  }  $ Time_end  =  re_microtime  (  )  ;  header  (  "Content-type: image / png"  )  ;  / * Виводимо в заголовках час створення * /  header  (  "X-Exec-Time:"  .  (  $ Time_end  -  $ Time_start  )  )  ;  imagepng  (  $ Img  )  ;  imagedestroy  (  $ Img  )  ;  ?> 

Приклад програми побудови множини (на мові програмування C_Sharp):

 using  System  ;  using  System.Collections.Generic  ;  using  System.Linq  ;  using  System.Text  ;  namespace  Mnoj  {  class  Program  {  static  void  Main  (  string  [  ]  args  )  {  double  realCoord, imagCoord  ;  double  realTemp, imagTemp, realTemp2, arg  ;  int  iterations  ;  for  (  imagCoord  =  1.2  ;  imagCoord  > =  -  1.2  ;  imagCoord  - =  0.05  )  {  for  (  realCoord  =  -  0.6  ;  realCoord  <=  1.77  ;  realCoord  + =  0.03  )  {  iterations  =  0  ;  realTemp  =  realCoord  ;  imagTemp  =  imagCoord  ;  arg  =  (  realCoord  *  realCoord  )  +  (  imagCoord  *  imagCoord  )  ;  while  (  (  arg  <  4  )  &&  (  iterations  <  40  )  )  {  realTemp2  =  (  realTemp  *  realTemp  )  -  (  imagTemp  *  imagTemp  )  -  realCoord  ;  imagTemp  =  (  2  *  realTemp  *  imagTemp  )  -  imagCoord  ;  realTemp  =  realTemp2  ;  arg  =  (  realTemp  *  realTemp  )  +  (  imagTemp  *  imagTemp  )  ;  iterations  + =  1  ;  }  switch  (  iterations  %  4  )  {  case  0  :  Console  .  Write  (  "."  )  ;  break  ;  case  1  :  Console  .  Write  (  "O"  )  ;  break  ;  case  2  :  Console  .  Write  (  "0"  )  ;  break  ;  case  3  :  Console  .  Write  (  "@"  )  ;  break  ;  }  }  Console  .  Write  (  "  \ N  "  )  ;  }  Console  .  ReadKey  (  )  ;  }  }  } 

3.1. Додавання кольору

Фрагмент кордону множини Мандельброта в кольоровому варіанті

Строго математично, зображення множин Мандельброта і Жюліа повинні бути чорно-білими. Точка або потрапляє всередину безлічі, або ні. Незважаючи на це, з допомогою комп'ютера ми можемо побудувати і кольорові зображення. Найпоширенішим способом є розфарбовування точок зовні безлічі в колір, рівний кількості ітерацій, за яке точка йде в "нескінченність" або, з точки зору програми, на певну відстань від нуля.

Порядок визначення, чи потрапляє точка z 0 всередину безлічі (традиційно зафарбовують чорним кольором) чи ні (зафарбовується кольором, залежних від швидкості руху до нескінченності) наступний: на кожній ітерації для z n = x n + y n i обчислюється значення модуля | Z_n | = \ sqrt {x_n ^ 2 + y_n ^ 2} , Яке потім порівнюється з "кордоном нескінченності" (зазвичай береться значення, рівне 2). Тут важливо звернути увагу, що вже на даному етапі можна ввести певну оптимізацію обчислень, якщо перевіряти не \ Sqrt {x_n ^ 2 + y_n ^ 2}> 2 , А x_n ^ 2 + y_n ^ 2> 4 , Що значно знизить час розрахунків.

Таким чином, якщо | z n | 2 ≤ 4 при будь-якому числі ітерацій (на практиці - при всіх обчислених ітераціях), то колір точки чорний, в іншому випадку він залежить від останнього значення n, при якому | z n | 2 ≤ 4. Значення n, фактично, позначає швидкість руху z n в нескінченність, і може бути просто індексом у таблиці кольорів, або використовуватися як параметр у більш складному алгоритмі.

Даний алгоритм визначає, що якщо точка віддаляється більше ніж на 2 від початку координат, то вона лежить зовні множини Мандельброта. Для того, щоб визначити, що точка лежить усередині безлічі є багато способів. Найпростіше рішення - обмежити кількість ітерацій якимсь максимумом. Якщо точка не вийшла за вказану межу, можна вважати, що вона знаходиться всередині безлічі.

Крапкам біля кордону безлічі потрібно більше ітерацій для догляду в нескінченність. Тому такі області прорисовуються помітно довше. Чим далі від кордонів безлічі, тим вище швидкість відходу в нескінченність. Для таких точок потрібно менше ітерацій.

Приклад додавання кольору (на PHP):

  / / Default: http://  /  / . Php? Iter1 = 64 & width = 600 & height = 400 & coef = 32  function  BN  (  $ N  ,  $ L  ,  $ R  )  {  return  $ N  >  $ L  &&  $ N  <=  $ R  ;  }  function  SQR  (  $ A  )  {  return  $ A  *  $ A  ;  }  define  (  "COEF"  ,  $ _GET  [  "Coef"  ]  )  ;  $ Iter1  =  $ _GET  [  "Iter1"  ]  ;  $ Width  =  $ _GET  [  "Width"  ]  ;  $ Height  =  $ _GET  [  "Height"  ]  ;  header  (  "Content-type: image / png"  )  ;  $ Img  =  imagecreatetruecolor  (  $ Width  ,  $ Height  )  ;  $ Iter2  =  0.01  /  (  $ Width  /  300  )  ;  $ Yy  =  -  1  ;  for  (  $ Y  =  -  1  ;  $ Y  <  1  ;  $ Y  =  $ Y  +  $ Iter2  )  {  $ Yy  + +;  $ Xx  = -  1  ;  for  (  $ X  =  -  2  ;  $ X  <  1  ;  $ X  =  $ X  +  $ Iter2  )  {  $ Xx  + +;  $ Cx  =  $ X  ;  $ Cy  =  $ Y  ;  $ X  =  $ X  ;  $ Y  =  $ Y  ;  $ Ix  =  0  ;  $ Iy  =  0  ;  $ N  =  0  ;  while  (  (  SQR  (  $ Ix  )  +  SQR  (  $ Iy  )  <  4  )  and  (  $ N  <  $ Iter1  )  )  {  $ Ix  =  SQR  (  $ X  )  -  SQR  (  $ Y  )  +  $ Cx  ;  $ Iy  =  2  *  $ X  *  $ Y  +  $ Cy  ;  $ X  =  $ Ix  ;  $ Y  =  $ Iy  ;  $ N  + +;  }  if  (  BN  (  $ N  ,  0  ,  7  )  )  $ Col  =  imagecolorallocate  (  $ Img  ,  COEF  *  $ N  ,  0  ,  0  )  ;  elseif  (  BN  (  $ N  ,  7  ,  14  )  )  $ Col  =  imagecolorallocate  (  $ Img  ,  COEF  *  $ N  ,  COEF  *  $ N  ,  0  )  ;  elseif  (  BN  (  $ N  ,  14  ,  21  )  )  $ Col  =  imagecolorallocate  (  $ Img  ,  COEF  *  $ N  ,  0  ,  COEF  *  $ N  )  ;  elseif  (  BN  (  $ N  ,  21  ,  28  )  )  $ Col  =  imagecolorallocate  (  $ Img  ,  0  ,  COEF  *  $ N  ,  0  )  ;  elseif  (  BN  (  $ N  ,  28  ,  35  )  )  $ Col  =  imagecolorallocate  (  $ Img  ,  COEF  *  $ N  ,  COEF  *  $ N  ,  0  )  ;  elseif  (  BN  (  $ N  ,  35  ,  42  )  )  $ Col  =  imagecolorallocate  (  $ Img  ,  0  ,  COEF  *  $ N  ,  COEF  *  $ N  )  ;  elseif  (  BN  (  $ N  ,  42  ,  49  )  )  $ Col  =  imagecolorallocate  (  $ Img  ,  0  ,  0  ,  COEF  *  $ N  )  ;  elseif  (  BN  (  $ N  ,  49  ,  56  )  )  $ Col  =  imagecolorallocate  (  $ Img  ,  COEF  *  $ N  ,  0  ,  COEF  *  $ N  )  ;  elseif  (  BN  (  $ N  ,  56  ,  64  )  )  $ Col  =  imagecolorallocate  (  $ Img  ,  0  ,  COEF  *  $ N  ,  COEF  *  $ N  )  ;  imagesetpixel  (  $ Img  ,  $ Xx  ,  $ Yy  ,  $ Col  )  ;  }  }  imagepng  (  $ Img  )  ;  imagedestroy  (  $ Img  )  ;  ?> 

3.2. Оптимізація

Одним із способів зменшення обсягу обчислень при обчисленні загальної картини безлічі може служити перевірка, чи потрапляє точка в область головної кардіоїда. Формула кардіоїда в полярних координатах виглядає наступним чином:

\ Rho_c = {1 \ over 2} - {1 \ over 2} \ cos \ theta

Таким чином, для точки (X, y) \! необхідно обчислити


\ Rho = \ sqrt {\ left (x - {1 \ over 4} \ right) ^ 2 + y ^ 2} ,
\ Theta = \ hbox {atn} _2 \ left (y, x - {1 \ over 4} \ right) ,
\ Rho_c = {1 \ over 2} - {1 \ over 2} \ cos \ theta .

Якщо \ Rho \ le \ rho_c то точка (X, y) \! потрапляє всередину безлічі і зафарбовується чорним кольором, а ітеративні обчислення можна пропустити.

На практиці найбільше зменшення обсягу обчислень дає трасування кордону: якщо є деяка замкнута крива, не перетинає вісь абсцис, кожна точка якої йде за межу bail-out за однакове число ітерацій або навпаки належить безлічі Мандельброта, то будь-яка точка всередині цієї кривої буде володіти тим же властивістю, і отже вся область всередині кордону зафарбовується однаковим кольором.


4. Взаємодія з безліччю Жюліа

Фрагмент множини Мандельброта, що лежить в районі його межі
Фрактал Жюліа
Збільшення на кордоні множини Мандельброта формує зображення, аналогічне безлічі Жюліа

Безліч Мандельброта спочатку було побудовано як каталог множин Жюліа : кожній точці на комплексній площині відповідає своє безліч Жюліа. Точки, що лежать всередині множини Мандельброта, точно відповідають зв'язковим множинам Жюліа, а точки зовні - незв'язних.

Звідси зрозуміло, що цікаві варіанти безлічі Жюліа відповідають крапкам, що лежать на кордоні множини Мандельброта. Точки глибоко всередині утворюють прості геометричні фігури, а зовнішні виглядають як пил, навколишнє кольорові плями. Деякі програми, наприклад, Fractint, дозволяють користувачеві прямо на екрані вказати точку, для якої необхідно побудувати відповідне безліч Жюліа, спрощуючи пошук красивих зображень.

Безліч Мандельброта і саме містить структури, що нагадують безліч Жюліа: для будь-якого c \! область множини Мандельброта близько c \! нагадує центр безлічі Жюліа з параметром c \! . Якщо сильно збільшити безліч Мандельброта в граничній точці c і те ж саме виконати з безліччю Жюліа для цього ж значення c і в цій же точці, то картини будуть асимптотично прагнути один до одного при все більших збільшеннях.


5. Варіації множини Мандельброта

Найчастіше під назвою "Безліч Мандельброта" розуміється тільки безліч, описане вище. Однак будь-яка функція комплексної змінної має відповідне безліч Мандельброта, яке також характеризується наявністю або відсутністю зв'язного безлічі Жюліа. Наприклад, можна покласти f c (z) = z 3 + c. Тоді для кожного значення c перевіряється зв'язність безлічі Жюліа функції f c, і при наявності зв'язності вважається, що c належить безлічі Мандельброта. В описаному випадку зв'язність можна перевірити тим же способом, що і для f c (z) = z 2 + c.

Ці твердження можна узагальнити і на безлічі Жюліа, визначувані більше, ніж двома числами. Наприклад, безліч Жюліа, яке визначається трьома дійсними числами, має відповідне тривимірне безліч Мандельброта.

Розглядаються і багатовимірні варіації множини Мандельброта. Так, тривимірний аналог отримав назву лампочка Мандельброта.


6. Застосування множини Мандельброта в мистецтві

Пошук красивих зображень множини Мандельброта - цікаве хобі для дуже багатьох людей. Вони збирають колекції таких зображень, причому кожне з них може бути описано невеликою кількістю параметрів, наприклад, просто координатами центру.

Є велика кількість програм для малювання фракталів, але, незважаючи на це, багато людей пишуть свої програми для більшої гнучкості при експериментах.

7. Математичні факти про безліч Мандельброта

Безліч Мандельброта є зв'язковим, хоча в це й важко повірити, дивлячись на хитрі системи мостів, що з'єднують різні його частини.

Число ітерацій дуже близько до логарифму електричного потенціалу, який виникає, якщо зарядити безліч Мандельброта. Точніше, межа \ Ln (\ ln (| z_n |) / 2 ^ n) + const збігається з цим потенціалом.


Література

  • Бенуа Мандельброт, Річард Л. Хадсон (Не) слухняні ринки: фрактальна революція у фінансах = The Misbehavior of Markets. - М .: "Вильямс", 2005. - С. 400. - ISBN 5-8459-0922-8

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Безліч
Безліч
Нескінченна безліч
Канторової безліч
Щільне безліч
Рахункове безліч
Універсальне безліч
Безліч Жюліа
Нечітке безліч
© Усі права захищені
написати до нас
Рейтинг@Mail.ru