ФРАКТАЛЬНАЯ ГЕОМЕТРИЯ

Рекомендуемая литература
Р. Кроновер. Фракталы и хаос в динамических системах. Основы теории: Пер. с англ. Постмаркет, М., 2000.
М. Шредер. Фракталы, хаос, степенные законы. Миниатюры из бесконечного рая: Пер. с англ. НИЦ «Регулярная и хаотическая динамика», Ижевск, 2001.
Е. Федер. Фракталы: Пер. с англ. Мир, М., 1991.
Б. Мандельброт. Фрактальная геометрия природы: Пер. с англ. Институт компьютерных исследований, М., 2002.
M. F. Barnsley. Superfractals. Cambridge University Press, Cambridge, 2006.

Новая философия математики
Фрактал — это слово, изобретенное Бенуа Мандельбротом для того, чтобы объединить под одним заголовком обширный класс объектов, которые сыграли историческую роль в развитии чистой математики. Классическую математику XIX в. от современной математики отделяет великая революция идей. Корни классической математики лежат среди правильных геометрических структур Евклида и поступательной динамики Ньютона. Современная математика начинается с канторовой теории множеств и заполняющей пространство кривой Пеано. Исторически революция была вызвана открытием математических структур, не умещавшихся в рамках построений Евклида и Ньютона. Эти новые структуры рассматривались как «патологические» как некая «выставка чудовищ», вроде кубистской живописи и атональной музыки, перевернувших примерно в то же время установленные стандарты хорошего вкуса в искусстве. Математики же, сотворившие этих чудовищ, считали их важными свидетельствами того, что мир чистой математики содержит в себе необыкновенное изобилие возможностей, далеко выходящее за рамки тех простых структур, что можно наблюдать в Природе.
И тут, как отмечает Мандельброт, Природа сыграла с математиками шутку. Возможно, математикам XIX в. недоставало воображения — Природа же никогда таким недостатком не страдала. Как оказалось, окружающим нас и хорошо знакомым нам объектам всегда были присущи те самые патологические структуры, которые математики изобрели, чтобы избавиться от уз натурализма XIX в.

Бенуа Мандельброт

Б. Мандельброт
«Фрактальная геометрия природы»
Почему геометрию так часто называют «холодной» и «сухой»? Одна из причин — ее неспособность описать форму облака, горы, дерева или береговой линии. Облака не являются сферами, горы — конусами, береговые линии нельзя изобразить с помощью окружностей, кору деревьев не назовешь гладкой, а путь молнии — прямолинейным.
В более общем виде я заявляю, что многие формы Природы настолько неправильны и фрагментированы, что в сравнении с евклидовыми фигурами Природа демонстрирует не просто более высокую степень, но совершенно иной уровень сложности. Количество различных масштабов длины в естественных формах можно считать бесконечным для каких угодно практических задач.
Существование таких феноменов бросает нам вызов и побуждает заняться подробным изучением тех из форм, которые Евклид отложил в сторону из-за их «бесформенности» — исследовать, так сказать, морфологию «аморфного». Математики же пренебрегли этим вызовом и предпочли бежать от природы путем изобретения всевозможных теорий, которые никак не объясняют того, что мы видим или ощущаем.
Рискнув ответить на вызов, я задумал и разработал новую геометрию Природы, а также нашел для нее применение во многих разнообразных областях. Новая геометрия способна описать многие из неправильных и фрагментированных форм в окружающем нас мире и породить вполне законченные теории, определив семейство фигур, которые я называю фракталами.

Новая геометрия
С момента выхода книги Б. Мандельброта «Фрактальная геометрия природы» началось бурное развитие фрактальной геометрии. Фракталы обнаружили практически во всех естественных явлениях и процессах. «Сейчас анализ на фрактальных множествах развит в той же мере, что и анализ на гладких многообразиях», — говорит Р. Стричартц, профессор американского университета Корнелл. Идеи и достижения новой геометрии нашли самые разнообразные приложения. Фрактальные модели применяют в медицине для ранней диагностики раковых опухолей; в геологии и почвоведении; в материаловедении при изучении процессов разрушения изделий; в ядерной физике и астрономии для изучения элементарных частиц, распределения галактик во Вселенной, процессов на Солнце; в информатике для сжатия данных и улучшения трафика в сети Интернет; для анализа колебаний рыночных цен в экономике, сердечного ритма в кардиологии, погоды в метеорологии; в химии, искусствоведении… — перечень можно продолжать бесконечно.
Всем этим человечество обязано математику Бенуа Мандельброту. То, что новую науку со столь широкими приложениями создал один человек, выглядит невероятным. В наше время все значительные достижения науки и технологий являются плодами работы коллективов. Время одиночек–энциклопедистов прошло, специализация достигла такой степени, что одному человеку не под силу охватить даже основные идеи из разных областей. Для этого надо быть гением. Но многие так и считают: открыв фракталы, Б. Мандельброт совершил переворот в физике, утверждают авторы книги «От Ньютона до Мандельброта» (Штауффер Д., Стэнли Х.Е.).

Фракталы в интернете

Фрактальные картинки

Береговая линия Норвегии
При изучении географии вы, конечно, помните, что каждая из стран имеет свою площадь территории и длину границы, в частности, если страна омывается каким-либо морем или океаном, то она имеет морскую границу определенной длины. Задумывались ли вы когда-либо, как эту длину границы определяют? В 1977 г. Бенуа Мандельброт поставил перед собой следующий вопрос: чему равна длина береговой линии Великобритании? Оказалось, что корректно ответить на этот «детский вопрос» не удается. В 1988 г. норвежский ученый Енс Федер решил выяснить, чему равна длина береговой линии Норвегии. Обратите внимание на то, что побережье Норвегии сильно изрезано фиордами. Другие ученые задавали себе аналогичные вопросы о длинах береговых линий побережий Австралии, Южной Африки, Германии, Португалии и других стран.
Мы можем измерить длину береговой линии только приблизительно. По мере того как мы уменьшаем масштаб, нам приходится измерять все больше маленьких мысов и бухт — длина береговой линии увеличивается, и объективного предела уменьшению масштаба (и, тем самым, увеличению длины береговой линии) просто не существует; мы вынуждены признать, что эта линия имеет бесконечную длину.

Измерение длины береговой линии
Измеренная длина береговой линии как функция длины шага
Тот же график в дважды логарифмическом масштабе. Обратите внимание: точки могут быть хорошо аппроксимированы прямой.

А что же все-таки делать с длиной береговой линии? Отказаться ее измерять, потому что она неизмерима?
Нет, это не выход. Просто, приводя длину береговой линии, следует всегда указывать, по картам какого масштаба она измерялась, каким способом. Без указания масштаба карт всякие данные о длине береговой линии теряют смысл. К сожалению, даже в источниках, претендующих на сугубую солидность, можно встретить страшные нелепости. Например, известный сайт ЦРУ «The World Factbook». Здесь для каждой страны и океана приведены данные по береговой линии, но способ измерения не указан. В результате береговая линия Канады оказывается больше 200 тыс. км, Северного Ледовитого океана — 45,4 тыс. км, Атлантического — 111,9 тыс. км (данные приведены с точностью до километра). Береговая линия двух из трех океанов, омывающих Канаду, в сумме меньше береговой линии одной только Канады. Для Норвегии приведена цифра 21 925 км и дано примечание: «Материк 3419 км, большие острова 2413 км, длинные фьорды, многочисленные маленькие острова и мелкие изгибы (в буквальном переводе зазубрины) береговой линии 16 093 км». В сумме получается как раз указанная общая длина береговой линии. Но вот почему берега фьордов — не часть береговой линии материка, почему длина зазубрин приплюсована к длине береговой линии материка, какие острова считать большими — обо всем этом приходится только догадываться. Совершенно бесспорные данные в этой таблице приведены только для Андорры, Австрии, Ботсваны, Венгрии, Свазиленда и подобных им стран, выхода к морю не имеющих, — написано: «0 км».

Данные собранные Ричардсоном
Длина береговых линий как функция выбранного шага δ (км).

Фрактальная размерность
Как объяснить то, что все результаты измерений в дважды логарифмическом масштабе укладываются на прямую?
Имеем
где a и b — некоторые константы. Потенцируя, получим
С одной стороны, константа b есть тангенс угла наклона прямой, причем, как следует из графиков, она не положительна. С другой стороны она имеет важный физический смысл — чем она больше по модулю, тем быстрее растет длина побережья с уменьшением длины шага, и, следовательно, более изрезанным выглядит побережье. В дальнейшем мы увидим, что константа b тесно связана с одной из важнейших характеристик фрактальных кривых — фрактальной размерностью.

Парадокс Шварца
Рассмотри равнобедренный прямоугольный треугольник ABC с катетами равными 1. Понятно, что длина кратчайшего пути из A в C равна корню из 2. Предположим, что по условию, задачи мы можем передвигаться только по вертикали или горизонтали. Тогда длина пути из A в B затем в C, обозначенного зеленым цветом, равна 2. Если мы выберем синий или красный путь, то его длина по прежнему будет равна 2. Более того, мы можем выбрать путь из A в С , состоящий из вертикальных и горизонтальных отрезков, сколь угодно близкий к гипотенузе AC, но его длина по прежнему будет равна 2, что очевидно больше, чем длина самой гипотенузы. Как можно объяснить это несоответствие?

Самоподобие
Нередко то, что мы наблюдаем в природе, интригует нас бесконечным повторением одного и то же узора, увеличенного или уменьшенного во сколько угодно раз. Например, у дерева есть ветви. На этих ветвях есть ветки поменьше и т. д. Теоретически, элемент «разветвление» повторяется бесконечно много раз, становясь все меньше и меньше. То же самое можно заметить, разглядывая фотографию горного рельефа. Попробуйте немного приблизить изображение горной гряды — вы снова увидите горы. Приблизьте картинку еще — вы по-прежнему будете различать нечто, напоминающее горы, благодаря вашей способности различать тип объекта на рисунке. Кратко можно сказать, что самоподобный объект «выглядит» неизменным и после увеличения, и после уменьшения его размеров. Так проявляется характерное для фракталов свойство самоподобия.
Многие законы природы не зависят (или почти не зависят) от масштаба. То, что скейлинг (изменение масштаба) обычно имеет предел (постоянную Планка — когда объекты становятся слишком малыми, или скорость света — когда объекты движутся слишком быстро), не умаляет полезности «размышлений в терминах самоподобия» — так это не создает сколь-нибудь серьезных препятствий для применения этого понятия в реальном мире. Так, в турбулентных потоках крупные вихри порождают меньшие, те, в свою очередь, — еще меньшие и так почти до бесконечности.

Теорема Пифагора
Вот доказательство теоремы Пифагора, предложенное одиннадцатилетним Эйнштейном, и блистательно иллюстрирующее идею самоподобия.
Высота, проведенная из прямого угла, делит большой треугольник на два меньших, подобных друг другу и большому треугольнику. Учитывая, что площади подобных фигур относятся как квадраты соответствующих линейных размеров, получим соотношение для площадей
где k — некоторый отличный от нуля множитель, один и тот же во всех трех соотношениях. Учитывая, что
получим

Самоподобие «простых» объектов
Разделим отрезок прямой на N равных частей. Тогда каждую часть можно считать копией всего отрезка, уменьшенной в r раз. Очевидно, N и r связаны соотношением N=r1. Если квадрат разбить на N равных квадратов каждый из которых является копией всего квадрата, уменьшенной в r раз, то соотношение запишется как N = r2. Если куб разбить на N равных кубов, то соотношение примет следующий вид: N = r3. Заметим, что размерность d объекта, будь то одномерный отрезок, двумерный квадрат или трехмерный куб, появляется как степень r в соотношении между N, числом равных подобъектов, и коэффициентом подобия r. А именно:
Рассмотренные множества обладают целой размерностью. Зададимся вопросом, возможно ли такое построение, при котором показатель d не является целым, то есть такое, что при разбиении исходного множества на N непересекающихся подмножеств, полученных масштабированием оригинала с коэффициентом r значение d не будет выражаться целым числом. Ответ, как мы убедимся — решительное да! Такое множество называют самоподобным фракталом. Величину d называют фрактальной (дробной) размерностью или размерностью подобия.

Кривая Коха
Кривая, придуманная Гельгом фон Кохом в 1904 году, является фракталом размерности d ≈ 1,2618.
Пусть K0 — начальный отрезок. Уберем среднюю треть и добавим два новых отрезка такой же длины, как показано на рисунке. Назовем полученное множество К1. Повторим данную процедуру многократно, на каждом шаге заменяя среднюю треть двумя новыми отрезками. Обозначим через Kn фигуру, полу- получившуюся после n-го шага. Интуитивно ясно, что последовательность кривых {Kn} сходится к некоторой предельной кривой K. Мы проведем строгое математическое исследование сходимости таких последовательностей кривых и других позже. Пока что предположим, что кривая K существует, и рассмотрим некоторые ее свойства.

Свойства кривой Коха
Если взять копию K, уменьшенную в три раза (r=3), то все множество K можно составить из N = 4 таких копий. Следовательно, отношение самоподобия выполняется при указанных N и r, а размерность фрактала будет:
Еще одно важное свойство кривой Коха — ее бесконечная длина. Пусть исходный отрезок K0 имеет единичную длину. Тогда длина кривой K1 равна 4/3. Длина кривой K2 равна 16/9. Продолжая таким образом имеем, что кривая Kn после n-го шага имеет длину 4n/3n. Следовательно, длина предельной кривой K равна бесконечности:
Тот же факт можно доказать с использованием идеи самоподобия. Очевидно, что кривая K состоит из четырех кусков каждый из которых в три раза меньше самой кривой. Следовательно, если бы кривая K имела конечную длину, скажем L>0, то должно было бы выполняться соотношение
откуда следует, что L=∞.

Треугольник Серпинского
Еще один пример простого самоподобного фрактала — треугольник Серпинского, придуманный польским математиком Вацлавом Серпинским в 1915 году.
Пусть начальное множество S0 — равносторонний треугольник вместе с областью, которую он замыкает. Разобьем S0 на четыре меньшие треугольные области, соединив отрезками середины сторон исходного треугольника. Удалим внутренность маленькой центральной треугольной области. Назовем оставшееся множество S1. Затем повторим процесс для каждого из трех оставшихся маленьких треугольников и получим следующее приближение S2. Продолжая таким образом, получим последовательность вложенных множеств Sn, чье пересечение и образует ковер S.

Свойства треугольника Серпинского
Из построения видно, что весь ковер представляет собой объединение N=3 существенно непересекающихся уменьшенных в два раза копий; коэффициент подобия r=2 (как по горизонтали, так и по вертикали). Следовательно, S — самоподобный фрактал с размерностью:
Очевидно, что суммарная площадь частей, выкинутых при построении, в точности равна площади исходного треугольника. На первом шаге мы выбросили 1/4 часть площади. На следующем шаге мы выбросили три треугольника, причем площадь каждого равна 1/16 площади исходного. Рассуждая таким образом, мы убеждаемся, что полная доля выкинутой площади составила:
Следовательно, мы можем утверждать, что оставшееся множество S имеет нулевую площадь.

Упражнения 1
Определите размерность подобия фракталов, которые строятся, как указано на рисунках. Вычислите длины и площади.
Постройте самоподобное множество размерности 1, отличное от отрезка.
(а)
(б)
(в)
(г)
(д)
(е)
(ж)

L-системы
Понятие L-систем, тесно связанное с самоподобными фракталами, появилось в 1968 году благодаря Аристриду Линденмайеру. Изначально L-системы были введены при изучении формальных языков, а также использовались в биологических моделях селекции. С их помощью можно строить многие известные самоподобные фракталы, включая снежинку Коха и треугольник Серпинского. Некоторые другие классические построения, например кривые Пеано, также укладываются в эту схему. И конечно, L-системы открывают путь к бесконечному разнообразию новых фракталов, что и послужило причиной их широкого применения в компьютерной графике для построения фрактальных деревьев и растений.
Для графической реализации L-систем в качестве подсистемы вывода используется так называемая тертл-графика (turtle — черепаха). При этом точка (черепашка) движется по экрану дискретными шагами, как правило, прочерчивая свой след, но при необходимости может перемещаться без рисования. В нашем распоряжении имеются три параметра (x,y,α), где (х,у) — координаты черепашки, α — направление, в котором она смотрит. Черепашка обучена интерпретировать и выполнять последовательность команд, задаваемых кодовым словом, буквы которого читаются слева направо. Кодовое слово представляет собой результат работы L-системы и может включать следующие команды и интерпретаторы:

Команды и интерпретаторы

Графическая интерпретация
Размер шага и величина приращения по углу θ задаются заранее и остаются неизменными для всех перемещений черепашки. Если начальное направление движения α (угол, отсчитываемый от положительного направления оси X) не указано, то полагаем α равным нулю.
Формально, L-система состоит из алфавита, слова инициализации, называемого аксиомой или инициатором, и набора порождающих правил, указывающих, как следует преобразовывать слово при переходе от уровня к уровню (от итерации к итерации). К примеру, можно заменять букву F при помощи порождающего правила newf = F-F++F-F, что соответствует L-системе для кривой Коха. Остальные символы не обновляются, а просто остаются на тех местах, где они встретились. Обновление букв в данном слове предполагается одновременным, то есть все буквы слова одного уровня обновляются раньше любой буквы следующего уровня.
L-система, соответствующая кривой Коха, задается следующим образом:
θ = π/3;
аксиома: axiom=F;
порождающее правило: newF = F+F--F+F.
Графическое представление аксиомы F — отрезок. На первом шаге каждая буква F в слове—инициаторе заменяется на F+F--F+F. Графическое представление — в точности первый шаг построения кривой Коха. Повторяя этот процесс, на втором шаге получим:
F+F--F+F+F+F--F+F--F+F--F+F+F+F--F+F.
Несложно заметить, что графическая реализация есть второй шаг построения кривой Коха и т.д.
Следующая программа предназначена для графической реализации L-систем.

Примеры L-систем
Снежинка Коха
axiom=F++F++F
newF=F-F++F-F
Θ=π/3
Цветок
axiom=F[+F+F][-F-F][++F][--F]
newF=FF[++F][+F][F][-F][--F]
Θ=π/16
Куст
axiom=F
newF=-F+F+[+F-F-]-[-F+F+F]
Θ=π/8
Остров
axiom=F+F+F+F
newF=F+F-F-FFF+F+F-F
Θ=π/2
Снежинка
axiom=[F]+[F]+[F]+[F]+[F]+[F]
newF=F[++F][-FF]FF[+F][-F]FF
Θ=π/3
Сорняк
axiom=F
newF=F[+F]F[-F]F
Θ=π/7

Упражнения 2
Чему равно слово на выходе следующей L-системы после двух итераций:
axiom=F;
newF=FF-[F]+[F];
Θ=π/4.
Изобразите найденное в предыдущем пункте слово графически.
Напишите псевдокод для L-систем, реализующих правила на рисунках (а) и (б) (положить axiom = F).
Постройте L-системы для фракталов из упражнения 1 пункты (a) – (д). Отобразите результат работы L-систем в графике.
Придумайте и реализуйте на компьютере три новые L-системы, результатом работы которых были бы ваши собственные варианты следующих фигур: снежинка, остров (с границей без разрывов), куст или сорняк.
(а)
(б)

Множество Кантора
Классическое множество Кантора, или пыль Кантора, названо по имени Георга Кантора, который описал его в 1883 году. Существование пыли Кантора отмечалось до этого Генри Смитом (Henry Smith) в 1875 году или еще ранее. Это множество хорошо известно студентам из курса математического анализа как пример множества нулевой меры Лебега, чья мощность равна мощности континуума. Фрактальные свойства пыли Кантора имеют огромное значение, особенно учитывая тот факт, что многие известные фракталы являются близкими родственниками этого множества.
Построение классической пыли Кантора начинается с выбрасывания средней трети (не включая концы) единичного отрезка. То есть исходное множество есть отрезок [0,1], и первый шаг состоит в удалении открытого интервала [1/3,2/3]. На следующем и всех остальных шагах мы выкидываем среднюю треть (не включая концы) всех отрезков текущего уровня. Таким образом, мы получаем убывающую последовательность множеств:
Предельное множество C, которое представляет собой пересечение множеств {Cn}, называется классическим канторовым множеством.

Свойства канторова множества
Канторово множество есть самоподобный фрактал размерности d = ln(2)/ln(3) ≈ 0,6309, так как соотношение самоподобия N = rd выполняется при N = 2 и r = 1/3.
Канторово множество не содержит интервалов положительной длины. Это очевидно из построения.
Сумма длин интервалов, удаленных при построении множества C, в точности равна 1. Доказательство аналогично тому, что было проведено при вычислении площади треугольника Серпинского.
Классическое канторово множество представляет собой пример компактного, совершенного и вполне разрывного множества. Более того, можно утверждать, что топологически классическое множество Кантора определяется как компактное, совершенное и вполне разрывное множество. Это означает, что любое компактное, совершенное и вполне разрывное множество гомеоморфно канторову множеству.

Мощность канторова множества
Теорема. Мощность множества Кантора С равна мощности континуума [0,1].
Два множества обладают равной мощностью, если существует взаимно однозначное соответствие между точками этих множеств.
Таким образом, нам необходимо установить взаимно однозначное соответствие между точками из С и точками отрезка [0,1]. Для этого нам потребуется рассмотреть двоичное (по основанию 2), а также троичное (по основанию 3) представления точек отрезка [0,1].
Для того чтобы избежать двусмысленности в случае, когда точка имеет два двоичных или троичных представления, мы будем всегда выбирать то представление, которое заканчивается всеми нулями в двоичном или в троичном представлениях.
Заметим, что точка попадает в множество Кантора С тогда и только тогда, когда в ее троичном представлении отсутствуют единицы, то есть когда в нем присутствуют только нули и двойки. Тогда искомое соответствие точек из С с точками отрезка [0,1] осуществляется заменой всех двоек в троичном представлении x на единицы. Полученное таким образом двоичное представление определяет некоторое вещественное число y. Например, если x=0,220200020… (в троичной системе), то полагаем y=0,110100010… (в двоичной системе). Описанная процедура определяет взаимно однозначное соответствие между точками x из C и y из [0,1].

Упражнения 3
Можно ли утверждать, что каждая точка канторовой пыли является концом какого-то из отрезков, возникающих при ее построении, то есть имеет вид k|3n? Обосновать ответ.
Является ли треугольник Серпинского множеством Кантора? Обосновать ответ.
Определите фрактальную размерность (размерность подобия) модифицированного множества Кантора, в котором на каждом шаге выбрасывается центральная пятая часть каждого интервала.
Определите размерность фрактала, состоящего из таких точек отрезка [0,1], в десятиричном представлении которых x=0,x0x1x2… отсутствуют цифры 3 и 7.
Определите размерность фрактала на плоскости, состоящего из точек единичного квадрата (х, у), причем в системе счисления с основанием 5 в записи числа x=0,x0x1x2… отсутствуют цифры 2 и 4, а в записи числа y=0,y0y1y2… отсутствуют цифры 0, 1 и 3. Изобразить полученное множество.

Кривая Пеано
Снежинку Коха и другие непрерывные кривые на плоскости, полученные с помощью L-систем, объединяет то, что их размерность удовлетворяет неравенству: 1 < d < 2. Возникает вопрос, существует ли кривая размерности d=2? Этот вопрос примечателен не только тем, что ответ на него положительный, но и тем, что он был разрешен Джузеппе Пеано еще в 1890 году. Пеано построил непрерывную функцию, чья область определения — отрезок, а область значений — квадрат на плоскости. Соответствующая линия называется кривой Пеано или кривой, заполняющей плоскость. Кривая Пеано не является фракталом в определении Мандельброта, но тем не менее интересна как пример функции, отображающей множество заданной размерности на множество большей размерности.

Построение кривой Пеано
Пусть S — единичный квадрат. Первый шаг построения состоит в том, чтобы разбить S на девять равных частей и занумеровать их. Непрерывная кривая P1:[0,1]→S, которая проходит через все квадраты, строится так, как показано на рисунке (а) сплошной линией со стрелками.
Далее, каждый из этих девяти квадратов разбивается на девять равных подквадратов, которые нумеруются аналогично тому, как это было сделано на первой итерации. Получаем кривую P2:[0,1]→S, которая проходит через девять подквадратов таким образом, что ее начальная и конечная точки ложатся на кривую предыдущего уровня. Это позволяет нам занумеровать подквадраты числами от 0 до 8 внутри каждого квадрата (рис. (б)).
Повторим описанную процедуру бесконечно, каждый раз разбивая квадраты на девять подквадратов, строя кривую через все подквадраты так, чтобы ее концы ложились на линию предыдущего уровня, и занумеровывая их.
(а)
(б)

Теорема. Последовательность непрерывных отображений Pn:[0,1]→S сходится к непрерывному сюръективному отображению P:[0,1]→S, которое называется кривой Пеано.
В процессе построения отображений Pn мы разбивали единичный квадрат S на все более мелкие квадраты и нумеровали их. Таким образом, каждой точке A из S соответствует некоторая (возможно не единственная) бесконечная последовательность цифр от 0 до 8: A↔x1x2x3…
Из построения очевидно, что если x=0,x1x2x3… — девятичное представление точки x из единичного отрезка, то P1(x) принадлежит подквадрату первого уровня с номером x1, P2(x) принадлежит подквадрату второго уровня с номером x2 и т.д. Таким образом, Pn(x) сходится к точке пересечения вложенных подквадратов с номерами x1x2x3… Это доказывает сюръективность отображения Пеано.
Чтобы доказать непрерывность отображения P, достаточно заметить, что сходимость Pn→P равномерная, следовательно, по теореме о равномерной сходимости из стандартного курса математического анализа, предельное отображение также непрерывно.

Кривые, заполняющие плоскость

Упражнения 4
Найдите L-систему, реализующую кривую Пеано. Изобразите, используя компьютерную программу для визуализации L-систем.
Найдите образы точек x=0,4444…, y=0,2222… (в девятиричной системе) при отображении Пеано.
Найдите четыре представления Пеано для точек (1/3,7/9) и (2/3,7/9).
Определите все точки единичного квадрата, представление Пеано которых единственно. Какие точки имеют два различных представления? Какие точки имеют четыре различных представления?
Найдите геометрическое место точек единичного квадрата, в представлении Пеано которых отсутствует цифра 5. Является ли это множество фракталом? Если да, то какова его размерность?
Найдите L-системы, реализующие кривые Гильберта, Госпера и Серпинского. Изобразите, используя программу для визуализации L-систем.

Системы итерированных функций
Системы итерированных функций (СИФ) — одно из наиболее замечательных и глубоких достижений в построении фракталов. Математические аспекты были разработаны Джоном Хатчинсоном в 1981 г., а сам метод стал широко известен благодаря Майклу Барнсли. Подход на основе СИФ предоставляет хорошую теоретическую базу для математического исследования многих классических фракталов, а также их обобщений.
Следует иметь в виду с самого начала, что результат применения СИФ, называемый аттрактором, не всегда является фракталом. Это может быть любой компакт, включая интервал или квадрат. Тем не менее, изучение СИФ важно для фрактальной теории, так как с их помощью можно получить удивительное множество фракталов.

План исследования СИФ
Для того чтобы дать математически строгое описание СИФ нам понадобятся некоторые базовые понятия метрической геометрии, которые мы изложим в следующем порядке:
Определение метрики и метрического пространства.
Формулировка теоремы о сжимающих отображениях.
Определение метрики Хаусдорфа на множестве непустых компактов.
Определение СИФ.
Определение аттрактора СИФ.
Примеры аттракторов.
Упражнения.

Метрика
Метрикой (расстоянием) на множестве X называется вещественная функция
удовлетворяющая следующим аксиомам:
d(x, у) ≥ 0 для всех х, у из X.
d(x, у) = 0 тогда и только тогда, когда х = у.
d(x, у) = d(y, x).
d(x, z) ≤ d(x, y) + d(y, z) для всех х, у, z из X.
Метрическим пространством называется пара (X,d).
Метрическое пространство (X,d) называется полным, если любая последовательность Коши из X сходится к некоторой точке из X.

Теорема о сжимающих отображения
Пусть (X,d) — метрическое пространство. Преобразование T : X → X называется сжимающим отображением (или сжатием), если существует такое число s, 0 < s < 1, что:
для любых x, y из X. Число s называется коэффициентом сжатия.
Теорема. Пусть (X,d) — полное метрическое пространство и T : X → X — сжимающее отображение. Тогда T имеет в точности одну неподвижную точку, то есть существует такая точка x* из X, что T(x*) = x*. Кроме того, для любой начальной точки x
Иными словами, орбита любой точки x0=x, x1=T(x0), x2=T(x1), x3=T(x2) … сходится к x*.

Метрика Хаусдорфа
Одним из основных математических аспектов теории фракталов является вопрос о сходимости некоторой последовательности множеств к фракталу. Наша первая задача — разобраться с понятием предела последовательности множеств. Для этого необходимо определить подходящую метрику на интересующих нас множествах. Метрика, которой мы будем пользоваться, называется метрикой Хаусдорфа.
Метрика Хаусдорфа определяется на множестве K всех непустых компактных подмножеств полного метрического пространства (X,d) (как правило, в качестве X выступает евклидово пространство Rn). Таким образом, «точки» из K суть компактные множества из X.
Пусть E — непустой компакт из (X,d) и ε ≥ 0. Тогда ε-оболочкой множества E называется множество
Расстоянием по Хаусдорфу между двумя непустыми компактами E и F будем называть следующую величину:
Известно, что множество K, снабженное метрикой dH, является полным метрическим пространством.

Определение СИФ
Пусть (X,d) — полное метрическое пространство. Для чтобы построить систему итерированных функций введем в рассмотрение совокупность сжимающих отображений
Эти m отображений используются для построения одного сжимающего отображения на пространстве K всех непустых компактов из X
Это преобразование ставит в соответствие «точкам» из K, также «точки» из K, причем под точками здесь понимаются компактные множества.
Таким образом, системой итерированных функций называют совокупность введенных выше отображений Tj вместе с индуцированным ими отображением T, действующим на K.

Аттрактор СИФ
Теорема. Преобразование T:K→K, определенное соотношением (*), является сжатием на полном метрическом пространстве K.
Следовательно, по теореме о сжимающих отображениях T обладает единственной неподвижной точкой E* из K, т.е T(E*)=E*. Это непустое компактное множество E*, мы будем называть аттрактором СИФ. Аттрактор часто (но не всегда!) оказывается фрактальным множеством.
Теорема о сжимающих отображениях позволяет с высокой точностью получать изображение аттрактора на экране компьютера. Начиная с произвольного (возможно одноточечного) множества E0 , мы находим орбиту этого множества при действии трансформации T, т.е. E0 , E1=T(E0), E2=T(E1), … . Из теоремы о сжимающих отображениях следует, что орбита сходится к аттрактору E*. Таким образом, мы можем построить множество En сколь угодно близкое к E*.

Пример
Рассмотрим три аффинных преобразования на R2.
Несложно проверить, что аттрактором для данной СИФ является треугольник Серпинского с вершинами в точках (0,0), (1,0) и (1/2,√3/2). На рисунках можно увидеть, как произвольное исходное множество, под действием оператора T, сходится к аттрактору.
Следующая программа позволяет строить аттракторы СИФ, состоящих из аффинных преобразований.

Примеры аффинных СИФ

Примеры аффинных СИФ

Сжатие изображений
Рассмотрим задачу, обратную к нахождению аттрактора СИФ. Пусть в нашем распоряжении имеется некоторое изображение или его часть, например листка, дерева и т. п. Необходимо найти совокупность сжимающих аффинных отображений, для которых данное множество является аттрактором. Решение обратной задачи имеет большое значение для такой области прикладных исследований, как сжатие изображений, широко использующееся при передаче изображений в реальном времени. Проиллюстрируем сказанное на примере передачи телевизионного сигнала высокой четкости (HDTV). Из-за того что стандартные кабели, подводящие сигнал к пользовательским телеприемникам, не могут передавать данные достаточно быстро, частота обновления экрана не удовлетворяет стандарту HDTV — она ниже требуемой. По некоторым оценкам, для достижения приемлемой частоты регенерации требуется сжатие данных порядка 1000:1. Было опробовано множество алгоритмов, некоторые из которых претендуют на успешное решение проблемы.
Один привлекательный способ сжатия изображения заключается в том, чтобы разбить исходное изображение на компоненты и считать их аттракторами некоторых СИФ. Так как каждое аффинное преобразование определяется всего лишь шестью коэффициентами, то полное изображение, в принципе, может быть закодировано достаточно малым числом аффинных коэффициентов. Тогда по кабелю можно передавать коэффициенты, а изображение (совокупность аттракторов) восстанавливать по ним, выполняя алгоритм СИФ.

Рассмотрим гипотетический пример. Пусть нам требуется передать изображение ковра Серпинского размером 512 х 512. Не применяя сжатия, придется послать 262144 бит информации, нуль или единицу для каждого пикселя. С другой стороны, если бы мы передали всего лишь 18 аффинных коэффициентов трех аффинных преобразований, связанных с ковром Серпинского, мы смогли бы полностью восстановить оригинал в приемной части. Можно сказать, что в этом случае мы достигли бы сжатия 262144 : 18 = 14563 : 1.
Оставляя на время в стороне вопрос об отыскании аффинных отображений для аттрактора, соответствующего исходному изображению, обратимся к главному математическому аспекту проблемы. Следующая теорема, называемая теоремой коллажа, позволяет оценить расстояние между исходным и восстановленным изображениями без непосредственного восстановления, что существенно сокращает объем вычислений, необходимых для оценки качества восстановления.
Восстановление изображений

Теорема коллажа
Теорема. Обозначим E0 — исходное изображение; T — сжатие на пространстве непустых компактов, определяемое формулой (*); s = max{s1,s2,…,sm} < 1 — коэффициент сжатия T; E* — неподвижную точку T, т.е восстановленное изображение. Тогда
Многократно применяя неравенство треугольника, получим

Упражнения 5
Постройте СИФ, аттрактор которой есть в точности квадрат.
Используя теорему коллажа, оцените расстояние Хаусдорфа между отрезком [0,1] и аттрактором СИФ, определяемой сжатиями: T1(x)=0,51x-0,01 и T2(x)=0,47x+0,53.
Найдите СИФ, порождающие аттракторы, изображенные на рисунках.

Комплексная динамика
Вероятно, нельзя привести пример такого компьютерного эксперимента, который впечатлением от результатов превосходил бы то чувство удивления и восхищения, которое вызывает графическое построение множеств Жюлиа и множества Мандельброта на плоскости.
Множество Жюлиа названо в честь французского математика Гастона Жюлиа (1893-1978), который одновременно с Пьером Фату (1878-1929) в 1917-1919гг. написал основополагающие статьи по итерированию функций комплексного переменного. Еще раз мы видим впечатляющий пример математических исследований, которые далеко опередили свое время в том смысле, что потребовалось более пятидесяти лет, прежде чем компьютерная графика достигла уровня, позволяющего наблюдать эти математические объекты.

Множества Жюлиа
Рассмотрим полином одного комплексного переменного
Множество Жюлиа функции f, обозначаемое J(f), определяется как
Таким образом, множество Жюлиа функции f есть граница множества точек z, стремящихся к бесконечности при итерировании f(z).
Наряду с множеством Жюлиа часто рассматривают и заполняющее множество Жюлиа, состоящее из точек, орбиты которых ограничены, в отличие от границы этого множества, которое и является настоящим множеством Жюлиа. Заполняющие множества более привлекательны визуально и именно по этой причине наиболее часто реализуются программно.

Множества Жюлиа квадратичных полиномов
В первую очередь и в основном, мы будем изучать множества Жюлиа квадратичных полиномов
где c — комплексная константа. Такой подход не является ограниченным, как это может показаться, так как рассмотрение произвольного квадратичного полинома может быть сведено к указанному выше частному случаю простой заменой переменных (см. упр. 7).
Простейшее множество Жюлиа соответствует случаю f(z)=z2. Несложно заметить, что f n(z)→∞ тогда и только тогда, когда |z| > 1. Границей этого множества, то есть множеством Жюлиа, является единичная окружность {z : |z| = 1}, которая фракталом не является, хотя в общем случае множество Жюлиа есть фрактал.
Следующая программа позволяет строить множества Жюлиа.

Упражнения 6
Покажите, что множество Жюлиа произвольного квадратичного полинома g(z)=a2z2+a1z+a0 подобно множеству Жюлиа полинома f(w)=w2+c, где c=-a12+ a1+a2a0. Используйте коммутативность диаграммы
где T(z)=a2z+a1.
Используя программу, постройте множества Жюлиа следующих квадратичных полиномов: f(z)=z2-1, f(z)=z2-0.2+0.75i, f(z)=z2-0.1244+0.7560i, f(z)=z2-0.1194+0.6289i. Сравните результаты с множествами Жюлиа, изображенными на рисунках.

Примеры множеств Жюлиа

Множество Мандельброта
Мы уже убедились в том, что множества Жюлиа функции f(z)=z2+c обладают большим разнообразием. Действительно, для каждого нового значения c мы получаем впечатляющие изображения. Тем не менее, на самом деле существуют всего два типа множеств Жюлиа. Каждое множество Жюлиа функции f(z)=z2+c либо связно, либо вполне несвязно. Конечно, они могут выглядеть совершенно различным образом, даже принадлежа к одному и тому же типу. Некоторые связные множества Жюлиа выглядят как простые замкнутые кривые, которые являются фракталами, как это имеет место в случае 0<|c|<1/4 (проверьте, используя программу). Существуют также связные множества Жюлиа, которые не являются простыми замкнутыми кривыми, как, например, в случае c=−1. С другой стороны, все вполне несвязные множества Жюлиа обладают тем свойством, что они представляют собой «канторову пыль». Это мы наблюдаем на рисунках.
f(z)=z2-1.2i
f(z)=z2+0.5
f(z)=z2+0.31+0.04i

Множество Мандельброта (см. рисунок) M для полинома fс(z)=z2+c определяется как множество всех значений параметра c, для которых орбита точки 0 ограничена, то есть
Теорема. Пусть M — множество Мандельброта. Тогда для каждой точки c∈M соответствующее ей множество Жюлиа J(fc) связно, а для с∉М соответствующее множество Жюлиа J(fc) вполне несвязно и является на самом деле канторовым множеством.

Упражнения 7
Покажите, что множество Мандельброта симметрично относительно вещественной оси. Для этого покажите, что отображения
топологически сопряжены. Затем исследуйте орбиты точки 0 при этих двух отображениях.
Используя программу, постройте изображения множеств Жюлиа и Мандельброта для функций f(z)=zn+c при различных n. Проверьте выполнение условий предыдущей теоремы при n≠2.

Проблема Кэли
В 1879 году сэр Артур Кэли поставил задачу итерирования комплексных функций, которая позднее стимулировала исследования Гастона Жюлиа по проблемам теории множеств, названных теперь его именем. Проблема Кэли заключается в исследовании сходимости классического алгоритма Ньютона нахождения кубических корней, но при условии, что вещественные числа заменяются на комплексные.
Метод Ньютона для нахождения вещественного корня f(x) заключается в следующем. Выберем начальное приближение x0, вычислим точки
и найдем предел limn→∞ xn. Предполагается, что f, f’, и f’’ существуют и непрерывны в окрестности нуля функции, скажем, при x=c, то есть f(c)=0, причем f’(c)≠0. Заметим, что точка c является сверхпритягивающей неподвижной точкой для функции
то есть g(c)=c и g’(c)=0. Таким образом, если x0 находится достаточно близко к c, то limn→∞xn=c.

Для f(x)=х3-1 единственный вещественный ноль функции равен 1, и итерации Ньютона принимают вид:
Кэли предложил исследовать поведение этих итераций для комплексных zn:
Имеются три кубических корня из 1:
Областью притяжения для корня wk назовем множество
Кэли поставил задачу описания областей A(w1), A(w2) и A(w3).

Как и в случае вещественных итераций, если начальная точка z0 находится достаточно близко к корню wk , то ньютоновские итерации сходятся к этому корню. Таким образом, каждая область A(wk) содержит окрестность wk . Но какую часть комплексной плоскости занимает A(wk) и какова ее геометрия? Ответ на этот вопрос крайне нетривиален.
Перед исследованием проблемы Кэли для кубических корней рассмотрим соответствующую задачу для квадратных корней. В этом случае f(z)=z2-1 и ньютоновские итерации имеют вид:
Если z0 лежит в правой полуплоскости, то zn→1 при n→∞, а если z0 лежит в левой полуплоскости, то zn→-1 при n→∞ (см. упр. 8). Таким образом, за исключением начальных точек z0, которые равноудалены от двух корней, zn сходится к корню, ближайшему к zn . Если z0 лежит на мнимой оси, то в этом случае итерации не сходятся (см. упр. 8).
По аналогии со случаем z2-1 можно предположить, что в случае z3-1 итерированные значения zn сходятся к кубическому корню, ближайшему к z0, если такой ближайший корень существует. Таким образом, ответ на вопрос Кэли предположительно выглядит так, как показано на рисунке. Как ни странно, это предположение оказывается неверным в силу следующей теоремы.
A(w2)
A(w3)
A(w1)

Теорема. Границы всех областей притяжения A(wk) совпадают.
Теорема говорит нам о том, что ответ на вопрос Кэли отличается от того, что изображено на предыдущем рисунке. В произвольной окрестности каждой граничной точки любой из областей A(wk) должны находиться точки, принадлежащие всем трем областям. Правильное изображение трех областей притяжения изображено на рисунке.
Иными словами, мы получили ответ на следующий вопрос: как закрасить плоскость тремя красками, чтобы на границе каждой цветной области существовали точки двух других цветов, которые были бы расположены произвольно близко?