Фракталы
Под обобщающим названием "фракталы" на деле скрывается несколько различных вещей. Не претендуя дать исчерпывающий или полный ответ, можно сказать, что фракталами называются: во-первых, кривые и поверхности, во-вторых, системы итеративных функций, а в-третьих, множества на комплексной плоскости. Всех их объединяет свойство самоподобия.
(c) Компьютерная газета
Фрактальные кривые и поверхности. Введение во фрактальную геометрию принято начинать провокационным вопросом: "Чему равна протяженность побережья Великобритании?", или, применительно к нашим условиям, "Чему равна длина берега Минского моря?". Вопрос простой, и на ум немедленно приходит, что достаточно обойти берег с землемерным циркулем (шагомером), подсчитывая обороты циркуля (шаги), чтобы получить ответ.
Прекрасно, а вы можете предсказать, каким будет ответ, если вымерить берег 25-сантиметровой линейкой? Измеренная длина окажется несколько большей, поскольку с помощью укороченной линейки можно точнее "обойти" мелкие детали берега, через которые большой циркуль просто "перешагивал". Если взять сантиметровую линейку, полученная длина будет еще больше.
А теперь представьте, что подобным образом измеряется длина правильной окружности. "Проходить" по окружности линейкой все уменьшающегося размера - все равно, что вписывать в нее сначала правильный треугольник, потом квадрат, потом шестиугольник и так далее. Чем больше число сторон у такого многоугольника, тем меньше длина его стороны (шага измерения) и тем больше полученное число. Но этот ответ будет все меньше и меньше отличаться от одного-единственного числа - истинной длины окружности.
В каждом курсе математики рассматриваются протяженные ряды чисел, сумма которых, тем не менее, "сходится" к единственному числу, устремляясь к величине, которую дала бы сумма бесконечного ряда. Измеряя длину окружности все уменьшающейся линейкой, мы сталкиваемся именно с таким случаем. Естественно, мы никогда не получим "истинной" длины окружности, но можем подобраться к ней сколь угодно близко. Тут все ясно.
Парадокс с длиной побережья состоит в том, что такой вещи, как "истинная" длина, для него НЕ СУЩЕСТВУЕТ даже теоретически. (То есть, теоретически длина бесконечна.) Просто линия побережья отличается от окружности тем, что представляет собою ФРАКТАЛЬНУЮ кривую. Это означает, что она содержит бесконечное количество деталей. Рассматривая фрактальную кривую с большим и большим увеличением, вы просто будете видеть все больше и больше деталей. При сколь угодно большом увеличении мельчайшего фрагмента кривой вы не увидите гладкой линии, только новые изгибы и извивы. Бесконечное количество деталей при любой степени увеличения есть основная отличительная черта фрактальных кривых и поверхностей.
Фрактальную кривую легко смоделировать на компьютере. Начнем с прямой линии, нарисованной от левого до правого края экрана. Выберем на ней несколько случайных точек и сместим каждую из них случайным образом вверх или вниз на случайное же расстояние, не превышающее, скажем, 10% длины исходной линии. Заменим исходную линию ломаной, соединив полученные точки. Для каждой из прямых линий, составляющих ломаную, повторим только что описанную процедуру. И будем продолжать, пока не достигнем предела разрешающей способности экрана.
В конечном счете, на дисплее окажется кривая, чрезвычайно напоминающая настоящую линию берега. Если взять в качестве отправного пункта не линию, а участок плоскости, то точно таким же образом можно построить фрактальную поверхность. Самые впечатляющие изображения гор и облаков, практически неотличимые от настоящих, синтезируются специалистами по компьютерной графике именно при помощи фракталов. Самые лучшие генераторы пейзажей для компьютерных игр, когда можно сколь угодно близко рассматривать переплетение трав или скалы (от горы до песчинки), тоже используют фрактальную геометрию.
Системы итеративных функций. Функцией называют математическую формулу, которая из исходных значений производит результат по строго определенному правилу. Например, функция 2*Х+5 выдаст 9, если Х равен двум, и 11, когда Х=3. Что же произойдет, если, задавшись единственным исходным значением, мы вновь применим ту же самую функцию к полученному результату? В случае нашего примера будет сгенерирован ряд неограниченно возрастающих чисел: из 1 получится 7, из 7 выйдет 19, из 19 - 43 и так далее. Эта функция не очень-то интересна.
Интересно станет, если взять функцию с двумя переменными. А если договориться, что эти переменные будут обозначать координаты на плоскости, то результат вычислений можно будет нарисовать (и посмотреть) на экране компьютера. Получив в качестве исходных данных координаты единственной точки, функция двух переменных выдаст координаты другой, та - третьей, и так без конца. Однако обыкновенно бесконечная цепь все же разрывается, когда на "энном" шаге функция начинает выдавать те же самые координаты, что и исходные. Точка с такими координатами называется "аттрактором" функции.
Иногда вместо повторения одного и того же результата функция "ходит по кругу", повторяя некоторую последовательность точек. Скажем, 1 дает 2, 2 дает 3, 3 дает 1 и т.п. В таком случае говорят об "орбите". Бывает и иначе: точки начинают сосредотачиваться в небольшой области, не выходя за ее пределы. Тогда говорят об "области аттрактора".
Рассмотрим пример. Обозначим координаты исходной точки (Х1,У1), а координаты следующей точки (Х2,У2) будем вычислять по таким формулам: Х2=1+У1-1.4*Х1*Х1 и У2=0.3*Х1. Если начать вычисление этой системы итеративных функций для исходной точки (0,0), то получится такой ряд результатов (1,0) (-0.4,0.3) (1.076, -0.12) (-0.7408864,-0.036)...
Эти значения кажутся случайными. Трудно представить, чтобы они вдруг привели к повторению одной и той же пары координат. Да, у этой функции нет аттрактора, более того, у нее нет ни орбиты, ни области. Самое замечательное, что эти точки не такие случайные, какими кажутся. Если наблюдать за результатами работы функции по изображению на дисплее компьютера, то после нескольких тысяч итераций можно заметить, что точки сливаются в форму, отчетливо напоминающую лошадиное копыто. Ни одна из точек не выходит за "копыто", и ни одна из точек никогда не повторяется. Это называется "странным аттрактором".
Приведенный пример - аттрактор Хенона, по имени открывшего его математика. Линия "копыта", образованная близко лежащими отдельными точками, мелко изгибается, но никогда не касается сама себя. Если увеличить часть линии, которая кажется прямой, то окажется, что на поверку она состоит из множества отдельных линий, каждая из которых состоит из других линий. Чем больше увеличение, тем больше деталей видно. Это - фрактал.
Такого же широкого применения, как фрактальные кривые, системы итеративных функций, насколько мне известно, пока не нашли. Правда, очень впечатляет идея сжатия с их помощью изображений. Есть даже опытная технология. Представляете, целая картина с неограниченным числом деталей может быть сведена к десятку-другому уравнений. Степень сжатия - десятки тысяч раз! Однако идея пока остается в стадии разработки, поскольку еще не удалось разработать эффективный способ автоматического построения функций по изображению без привлечения человека-математика.
Множества на комплексной плоскости. Множества на комплексной плоскости представляют собою специальный случай систем итеративных функций двух переменных. Дело в том, что пару чисел, с которыми оперирует система итеративных функций, можно рассматривать не только в качестве координат точки на плоскости, но и в роли комплексного числа. Можно сказать иначе - в роли точки на комплексной плоскости.
Комплексные числа представляют собою ухищрение, при помощи которого "латаются" некоторые из "дыр", обнаруженные в алгебре при манипуляции обычными числами. Комплексные числа состоят из двух частей: "действительной" и "мнимой". Для них операции сложения и умножения выполняются способом, отличным от обычного, что привносит интересные возможности при вычислении функций. Так, например, комплексные числа с мнимой частью, равной нулю, не отличаются от обыкновенных, то есть [2, 0]x[3, 0]=[6, 0], но на этом сходство кончается, так как [2, 1]x[3, 2]=[4, 7].
Одно из самых известных множеств на комплексной плоскости - множество Мандельброта, названное по имени математика. Формулы для вычисления следующей точки множества на основании текущей таковы. Сначала положим [Х1,У1]=[Х0,У0], потом будем вычислять по формуле [Х2,У2]=[Х1,У1]х[Х1,У1]+[Х0,У0]. Не забудьте, вычисления проводятся по правилам комплексной арифметики! Если производить расчеты для точки [2, 3], то получим ряд комплексных чисел [-3, 15], [-214, -87]... все более отдаляющихся от нулевой точки [0, 0].
Если, ограничившись некоторой областью плоскости, например, от [-4, -4] до [4, 4], просчитывать каждую точку области с небольшим шагом, то выяснится, что число итераций, после которого точка "убежит" из этой области, в каждом случае разное. Договорившись, что для любой точки делается не более N просчетов, можно раскрасить выбранную область в N цветов, положив цвет исходной точки равный количеству итераций до "убегания" ее из области.
Вот так строится цветное изображение знаменитого множества Мандельброта. Насколько мне известно, подобные изображения имеют лишь эстетическую ценность, правда, ими иногда пользуются профессиональные художники, чтобы подстегнуть свою фантазию. Если повторять построение для все меньшей области, увеличивая тем самым изображение, можно увидеть, как каждый раз открываются все новые и новые детали. Правильно, это тоже фрактал.
Самоподобие. Характернейшей особенностью фракталов является то, что, рассматривая их с любой степенью увеличения, мы всегда можем наблюдать не одинаковые, но очень похожие формы. Если говорить о горном ландшафте, то скальная гряда выглядит рядом зубцов. Абрис отдельного осколка тоже слагают зубцы. Контуры песчинки образуются теми же зубцами. А в множестве Мандельброта основными "строительными" элементами являются преимущественно круги и дуги.
Это свойство фракталов нетрудно понять, вспомнив, что процедура их расчета состоит в повторном применении одних и тех же формул. Такая их особенность, вкупе с идеей о сжатии информации, дает некоторым ученым возможность предполагать, что фрактальные механизмы могут использоваться матушкой-природой на уровне генного кода. Действительно, почему бы и нет? Ведь переплетение ветвей дерева является отличным примером фрактала...
Евгений Щербатюк
(c) Компьютерная газета
Фрактальные кривые и поверхности. Введение во фрактальную геометрию принято начинать провокационным вопросом: "Чему равна протяженность побережья Великобритании?", или, применительно к нашим условиям, "Чему равна длина берега Минского моря?". Вопрос простой, и на ум немедленно приходит, что достаточно обойти берег с землемерным циркулем (шагомером), подсчитывая обороты циркуля (шаги), чтобы получить ответ.
Прекрасно, а вы можете предсказать, каким будет ответ, если вымерить берег 25-сантиметровой линейкой? Измеренная длина окажется несколько большей, поскольку с помощью укороченной линейки можно точнее "обойти" мелкие детали берега, через которые большой циркуль просто "перешагивал". Если взять сантиметровую линейку, полученная длина будет еще больше.
А теперь представьте, что подобным образом измеряется длина правильной окружности. "Проходить" по окружности линейкой все уменьшающегося размера - все равно, что вписывать в нее сначала правильный треугольник, потом квадрат, потом шестиугольник и так далее. Чем больше число сторон у такого многоугольника, тем меньше длина его стороны (шага измерения) и тем больше полученное число. Но этот ответ будет все меньше и меньше отличаться от одного-единственного числа - истинной длины окружности.
В каждом курсе математики рассматриваются протяженные ряды чисел, сумма которых, тем не менее, "сходится" к единственному числу, устремляясь к величине, которую дала бы сумма бесконечного ряда. Измеряя длину окружности все уменьшающейся линейкой, мы сталкиваемся именно с таким случаем. Естественно, мы никогда не получим "истинной" длины окружности, но можем подобраться к ней сколь угодно близко. Тут все ясно.
Парадокс с длиной побережья состоит в том, что такой вещи, как "истинная" длина, для него НЕ СУЩЕСТВУЕТ даже теоретически. (То есть, теоретически длина бесконечна.) Просто линия побережья отличается от окружности тем, что представляет собою ФРАКТАЛЬНУЮ кривую. Это означает, что она содержит бесконечное количество деталей. Рассматривая фрактальную кривую с большим и большим увеличением, вы просто будете видеть все больше и больше деталей. При сколь угодно большом увеличении мельчайшего фрагмента кривой вы не увидите гладкой линии, только новые изгибы и извивы. Бесконечное количество деталей при любой степени увеличения есть основная отличительная черта фрактальных кривых и поверхностей.
Фрактальную кривую легко смоделировать на компьютере. Начнем с прямой линии, нарисованной от левого до правого края экрана. Выберем на ней несколько случайных точек и сместим каждую из них случайным образом вверх или вниз на случайное же расстояние, не превышающее, скажем, 10% длины исходной линии. Заменим исходную линию ломаной, соединив полученные точки. Для каждой из прямых линий, составляющих ломаную, повторим только что описанную процедуру. И будем продолжать, пока не достигнем предела разрешающей способности экрана.
В конечном счете, на дисплее окажется кривая, чрезвычайно напоминающая настоящую линию берега. Если взять в качестве отправного пункта не линию, а участок плоскости, то точно таким же образом можно построить фрактальную поверхность. Самые впечатляющие изображения гор и облаков, практически неотличимые от настоящих, синтезируются специалистами по компьютерной графике именно при помощи фракталов. Самые лучшие генераторы пейзажей для компьютерных игр, когда можно сколь угодно близко рассматривать переплетение трав или скалы (от горы до песчинки), тоже используют фрактальную геометрию.
Системы итеративных функций. Функцией называют математическую формулу, которая из исходных значений производит результат по строго определенному правилу. Например, функция 2*Х+5 выдаст 9, если Х равен двум, и 11, когда Х=3. Что же произойдет, если, задавшись единственным исходным значением, мы вновь применим ту же самую функцию к полученному результату? В случае нашего примера будет сгенерирован ряд неограниченно возрастающих чисел: из 1 получится 7, из 7 выйдет 19, из 19 - 43 и так далее. Эта функция не очень-то интересна.
Интересно станет, если взять функцию с двумя переменными. А если договориться, что эти переменные будут обозначать координаты на плоскости, то результат вычислений можно будет нарисовать (и посмотреть) на экране компьютера. Получив в качестве исходных данных координаты единственной точки, функция двух переменных выдаст координаты другой, та - третьей, и так без конца. Однако обыкновенно бесконечная цепь все же разрывается, когда на "энном" шаге функция начинает выдавать те же самые координаты, что и исходные. Точка с такими координатами называется "аттрактором" функции.
Иногда вместо повторения одного и того же результата функция "ходит по кругу", повторяя некоторую последовательность точек. Скажем, 1 дает 2, 2 дает 3, 3 дает 1 и т.п. В таком случае говорят об "орбите". Бывает и иначе: точки начинают сосредотачиваться в небольшой области, не выходя за ее пределы. Тогда говорят об "области аттрактора".
Рассмотрим пример. Обозначим координаты исходной точки (Х1,У1), а координаты следующей точки (Х2,У2) будем вычислять по таким формулам: Х2=1+У1-1.4*Х1*Х1 и У2=0.3*Х1. Если начать вычисление этой системы итеративных функций для исходной точки (0,0), то получится такой ряд результатов (1,0) (-0.4,0.3) (1.076, -0.12) (-0.7408864,-0.036)...
Эти значения кажутся случайными. Трудно представить, чтобы они вдруг привели к повторению одной и той же пары координат. Да, у этой функции нет аттрактора, более того, у нее нет ни орбиты, ни области. Самое замечательное, что эти точки не такие случайные, какими кажутся. Если наблюдать за результатами работы функции по изображению на дисплее компьютера, то после нескольких тысяч итераций можно заметить, что точки сливаются в форму, отчетливо напоминающую лошадиное копыто. Ни одна из точек не выходит за "копыто", и ни одна из точек никогда не повторяется. Это называется "странным аттрактором".
Приведенный пример - аттрактор Хенона, по имени открывшего его математика. Линия "копыта", образованная близко лежащими отдельными точками, мелко изгибается, но никогда не касается сама себя. Если увеличить часть линии, которая кажется прямой, то окажется, что на поверку она состоит из множества отдельных линий, каждая из которых состоит из других линий. Чем больше увеличение, тем больше деталей видно. Это - фрактал.
Такого же широкого применения, как фрактальные кривые, системы итеративных функций, насколько мне известно, пока не нашли. Правда, очень впечатляет идея сжатия с их помощью изображений. Есть даже опытная технология. Представляете, целая картина с неограниченным числом деталей может быть сведена к десятку-другому уравнений. Степень сжатия - десятки тысяч раз! Однако идея пока остается в стадии разработки, поскольку еще не удалось разработать эффективный способ автоматического построения функций по изображению без привлечения человека-математика.
Множества на комплексной плоскости. Множества на комплексной плоскости представляют собою специальный случай систем итеративных функций двух переменных. Дело в том, что пару чисел, с которыми оперирует система итеративных функций, можно рассматривать не только в качестве координат точки на плоскости, но и в роли комплексного числа. Можно сказать иначе - в роли точки на комплексной плоскости.
Комплексные числа представляют собою ухищрение, при помощи которого "латаются" некоторые из "дыр", обнаруженные в алгебре при манипуляции обычными числами. Комплексные числа состоят из двух частей: "действительной" и "мнимой". Для них операции сложения и умножения выполняются способом, отличным от обычного, что привносит интересные возможности при вычислении функций. Так, например, комплексные числа с мнимой частью, равной нулю, не отличаются от обыкновенных, то есть [2, 0]x[3, 0]=[6, 0], но на этом сходство кончается, так как [2, 1]x[3, 2]=[4, 7].
Одно из самых известных множеств на комплексной плоскости - множество Мандельброта, названное по имени математика. Формулы для вычисления следующей точки множества на основании текущей таковы. Сначала положим [Х1,У1]=[Х0,У0], потом будем вычислять по формуле [Х2,У2]=[Х1,У1]х[Х1,У1]+[Х0,У0]. Не забудьте, вычисления проводятся по правилам комплексной арифметики! Если производить расчеты для точки [2, 3], то получим ряд комплексных чисел [-3, 15], [-214, -87]... все более отдаляющихся от нулевой точки [0, 0].
Если, ограничившись некоторой областью плоскости, например, от [-4, -4] до [4, 4], просчитывать каждую точку области с небольшим шагом, то выяснится, что число итераций, после которого точка "убежит" из этой области, в каждом случае разное. Договорившись, что для любой точки делается не более N просчетов, можно раскрасить выбранную область в N цветов, положив цвет исходной точки равный количеству итераций до "убегания" ее из области.
Вот так строится цветное изображение знаменитого множества Мандельброта. Насколько мне известно, подобные изображения имеют лишь эстетическую ценность, правда, ими иногда пользуются профессиональные художники, чтобы подстегнуть свою фантазию. Если повторять построение для все меньшей области, увеличивая тем самым изображение, можно увидеть, как каждый раз открываются все новые и новые детали. Правильно, это тоже фрактал.
Самоподобие. Характернейшей особенностью фракталов является то, что, рассматривая их с любой степенью увеличения, мы всегда можем наблюдать не одинаковые, но очень похожие формы. Если говорить о горном ландшафте, то скальная гряда выглядит рядом зубцов. Абрис отдельного осколка тоже слагают зубцы. Контуры песчинки образуются теми же зубцами. А в множестве Мандельброта основными "строительными" элементами являются преимущественно круги и дуги.
Это свойство фракталов нетрудно понять, вспомнив, что процедура их расчета состоит в повторном применении одних и тех же формул. Такая их особенность, вкупе с идеей о сжатии информации, дает некоторым ученым возможность предполагать, что фрактальные механизмы могут использоваться матушкой-природой на уровне генного кода. Действительно, почему бы и нет? Ведь переплетение ветвей дерева является отличным примером фрактала...
Евгений Щербатюк
Компьютерная газета. Статья была опубликована в номере 36 за 1999 год в рубрике разное :: мелочи жизни
