Что толку от Вашего изящного доказательства [трансцендентности] $\pi$ ? $К$ чему заниматься исследованием таких задач, если иррациональных чисел вообще не существует?
ЛЕОПОЛЬД КРОНЕКеР, из письма Фердинанду Линдеману
Одним из основных источников самонодобин, помимо стененных законов, являются итерации. Под итерациями мы здесь понимаем многократное применение какого-нибудь правила либо операции, т. е. многократное выполнение одного и того же действия. (Как видно из рис. 1 , даже одно повторение может привести к самоподобию.) В этой главе мы продолжим исследования некоторых странно притягательных последствий итераций – одной из наших излюбленных тем.

С понятием итерации тесно связано другое понятие – рекурсия. В наш век все возрастающей автоматизации и компьютеризации многие процессы и вычисления носят рекурсивный характер, а коль скоро рекурсивный алгоритм в действительности периодичен, то где-то «за сценой» ожидает своего часа самоподобие. Вспомним о рекурсивном вычислении золотого сечения ( $\sqrt{5}-1) / 2=0,618 \ldots$ по правилу: «прибавь единицу и возьми обратную величину». Начав с 1 , мы получим последовательность $1,1 / 2,2 / 3,3 / 5,5 / 8,8 / 13$ и т. д., т. е. последовательность дробей, сходящихся к золотому сечению. (Более того: погрешность, с которой эти дроби стремятся к золотому сечению, убывает в геометрической прогрессии, образуя асимптотически самоподобную последовательность погрешностей с коэффициентом подобия, равным квадрату золотого сечения.) Рекурсия является также одной из главных тем книги Хофштадтера «Гёдель, Эшер, Бах» [108].

Рис. 1. Итерации ведут к самоподобию (рисунок Sempé, (c)1985 New Yorker Magazine, Inc.).

Одним из самых ранних примеров итеративного алгоритма может служить алгоритм Евклида для нахождения наибольшего общего делителя (НОД) двух натуральных чисел: разделить большее число на меньшее, взять число, обратное остатку и итерировать до тех пор, пока остаток не станет равным нулю. Знаменатель последнего ненулевого остатка и есть НОД. Например, для чисел 182 и 78 имеем: $182 / 78=2+$ $+26 / 78 ; 78 / 26=3+0$. Следовате.ьно, НоД чисел 182 и 78 равен 26. (В основе метода Евклида лежит то простое обстоятельство, что целье числа в числителе и знаменателе последнего остатка ( 26 и 78 ) имеют такой же НОД, как и исходные целые числа ( 182 и 78 ).)

Еще одна древняя задача, решеемая с помощью рекурсивного алгоритма, реализована в знаменитой игре под названием ханойская башня: стопку дисков различной величины нужно перенести с одного колышка на другой по одному диску за один раз, следя за тем, чтобы диск бо́льших размеров не оказался поеерх диска меньших размеров. Tретий колышек служит своего рода «запасным аэродромом», без которого игра, конечно же, была бы невозможной. Если число дисков достаточно велико, то игра вслепую, методом проб и ошибок, не приводит к желаемому результату, однако простой рекурсивный алгоритм дает оптимальное решение, не требун никаких догадок.

Обратимся теперь к изобретенной Ньютоном простой итерационной схеме нахождения нулей функции. Алгоритм Ньютона позволяет установить для этих нулей области притяжения, которые представляют собой хитроумно переплетенные мультифракталы. Применяя итерационный метод Ньютона к болеє земным задачам, можно с высокой точностью вычислять обратные величины и корни с помощью одного лишь умножения. Например, величина $1 / z$ вычисляется из соотношения $x_{n+1}=2 x_{n}-z x_{n}^{2}$, а $z^{-1 / 2}$ – из соотношения $x_{n+1}=x_{n}\left(3-z x_{n}^{2}\right) / 2$. (Чтобы итерации сходились к нужному результату, необходимо, разумеется, выбирать подходящие начальные значения $x_{0}$.)

Эффективность итераций лежит в основе и таких замечательных алгоритмов, как быстрое преобразование Фурье (знаменитое БПФ) и менее известное преобразование Адамара [99]. Важно здесь то, что матрицы, описывающие эти преобразования, факторизуются в пряме произведение меньших матриц [230]. В частности, матрица Фурье или Адамара, состоящая из $2^{n}$ строк и $2^{n}$ столбцов, может быть итеративно факторизована в $n$ матриц $2 \times 2$; именно это итеративное разложение позволяет существенно уменьшить объем вычислений (в $2 n / 2^{n}$ раз). Неудивительно, что порожденные с помощью итераций матрицы Адамара, будучи представлены в виде графических образов или оптических масок, обнаруживают самоподобие.

Итерации преобразования пекаря напоминают детскую игру в «стулья с музыкой» с двоичными цифрами вместо детей, моделируя в то же время нелинейные преобразования в двумерных пространствах. Отображение «кошка Арнольда» дает еще одну порождающую хаос рекурсию для моделирования сохраняющих площадь преобразований. (Олицетворение нелинейного отображения – логистическую параболу-и ее двумерное обобщение (отображение Энона) мы рассмотрим в гл. 12.)

Однако надлежащим образом направляемая рекурсия порождает и красоту, будь то изящные узоры для вышивания, или цветы и деревья самых изысканных форм. В самой математике рекурсия также творит настоящие чудеса, позволяя, например, вычислить миллиард знаков числа $\pi$ всего лишь за 15 итераций. Этот вычислительный рекорд опирается на труды великого индийского математика Шринивасы Рамануджана ( $1887-1920$ ), поразительная интуиция которого выходит за рамки человеческого разумения.

Поиск нулей и встреча с хаосом
Около 300 лет назад Исаак Ньютон (1642-1727) предложил метод нахождения нулей функции $f(z)$ с помощью итераций, основанных на проведении касательных. Если известно приближенное значение $z_{n}$ решения уравнения $f(z)=0$, то следующее приближенное значение вычисляется по формуле
\[
z_{n+1}=z_{n}-\frac{f\left(z_{n}\right)}{f^{\prime}\left(z_{n}\right)},
\]

где $f^{\prime}\left(z_{n}\right)$ – производная от функции $f(z)$ в точке $z=z_{n}$. Формула (1) имеет смысл, если угловой коэффициент касательной $f^{\prime}\left(z_{n}\right)$ отличен от нуля.
Для $f(z)=z^{2}-1$ из формулы (1; получаем
\[
z_{n+1}=\frac{1}{2}\left(z_{n}+\frac{1}{z_{n}}\right) .
\]

Неудивительно, что при начальном значении $z_{0}$ с положительной вещественной частью итерации $z_{n}$ сходятся к положительному корню уравнения $z^{2}-1=0$, а именно, к $z=1$. Аналогично, при начальном значении $z_{0}$ с отрицательной вещественной частью итерации сходятся к отрицательному корню $z=-1$.

Что же произойдет в случае чисто мнимого начального значения $z_{0}=i r_{0}$, где $r_{0}
eq 0$ – число вецественное? Оказывается, при таком начальном значении итерации вообще не сходятся: они, фигурально выражаясь, никак не могут решить, куда же им двигаться, и скачут вдоль мнимой оси в соответствии с отображением
\[
r_{n+1}=\frac{1}{2}\left(r_{n}-\frac{1}{r_{n}}\right) .
\]

Например, золотое сечение $0,618 \ldots$ последовательно отображается при итерациях в $-0,5 ; 0,75 ;-0,291(6) ; 1,566845 \ldots$ и т. д. Но некоторые $r_{0}$ ведут себя совершенно иначе. Таково, например, начальное значение $r_{0}=1+\sqrt{2}$, которое отображается в 1,0 и (тоже своего рода неподвижная точка, хотя и весьма удаленная).

Как можно привнести порядок в это хаотическое отображение? Воспользуемся тригонометрической подстановкой
\[
r=-\operatorname{ctg}(\pi \alpha),
\]

которая переводит отображение (3) в необычайно простое соотношение
\[
\alpha_{n+1}=2 \alpha_{n} \bmod 1,
\]

где «mod1» означает вычитание целой и сохранение только дробной части, лежащей в полуоткрытом интервале $[0,1)$. Например, $2,618 \bmod 1=0,618$.

При переходе на новую переменную $\alpha$ хаотическое отображение переменной $r$ становится вполне «прозрачным». Если записать $\alpha_{n}$ в виде двоичной дроби, то знаки в $\alpha_{n+1}$ будут теми же, что и в $\alpha_{n}$, только сдвинутыми на один знак влево. Единица, оказавшаяся левее двоичной запятой, отбрасывается. Таким образом, периодическая двоичная дробь $\alpha_{0}$ порождает периодические орбиты (т.е. периодические последовательности итераций). Например, $\alpha_{0}=1 / 3=0,(01)$ отображается в число $0,(10)=2 / 3$, которое отображается обратно в $\alpha_{2}=0,(01)=\alpha_{0}$. (Действительно, $r_{0}=-\operatorname{ctg}(\pi / 3)=-1 / \sqrt{3}$ отображается по формуле (3) в число $r_{1}=1 / \sqrt{3}$, которое отображается назад в $r_{2}=-1 / \sqrt{3}=r_{0}$.)

Аналогичным образом, предпєриодические двоичные дроби, которые начинаются как непериодические и заканчиваются периодическим “хвостом”, такие, например, как, $\alpha_{0}=5 / 6=0,1(10)$, порождают предпериодические орбиты:
\[
r_{0}=\sqrt{3}, \quad r_{1}=\frac{1}{\sqrt{3}}, \quad r_{2}=-\frac{1}{\sqrt{3}}, \quad r_{3}=r_{1} \quad \text { и т. Д. }
\]

Конечные двоичные дроби представляют собой не что иное, как частный случай предпериодических дзоичных дробей – с периодическим хвостом (0). Куда же приводят из итерации? Многократный сдвиг влево и взятие дробных частей (остатков по $\bmod 1$ ) рано или поздно приводит к $\alpha=0$, что соответствует $r=\infty$. Например, $\alpha_{0}=7 / 8=$ $=0,111$ отображается в дробь $0,11=3 / 4$, а та – в $0,1=1 / 2$, которая, в свою очередь, отображается в 0 . Более того, соответствующее значение $r_{0}=-\operatorname{ctg}(7 \pi / 8)=1+\sqrt{2}$, как мы уже заметили, отображается в 1,0 и $\infty$.

Приведенные выше соображения показывают, что любое иррациональное $\alpha_{0}$ дает апериодическую орбиту вдоль мнимой оси на плоскости $z$. Таким образом, простое отображение, задаваемое ньютоновыми итерациями для функции $z^{2}-1=0$ приводит в случае начальных значений, расположенных на мнимой оси, к весьма странным последствиям. По соответствующим значениям $\alpha$ все числа можно разделить на три группы:
1) периодические двоичные рациональные числа;
2) предпериодические двоичные рациональные числа;
3) иррациональные числа.

Периодические и предпериодические двоичные рациональные числа $\alpha_{0}$ сходятся к неподвижной точке или порождают периодические орбиты. В отличие от них несчетное множество иррациональных чисел $\alpha_{0}$ порождает апериодические орбиты: одно и то же значение никогда не встречается дважды, и ни одна итерация $\alpha_{n}$ не бывает рациональной. Как ни удивительно, но простое отображение (5) позволяет даже проводить некую тонкую границу между иррациональными числами различного типа – имеется в виду не обычное теоретико-числовое разделение иррациональных чисел на алгебраические (например, $\sqrt{2}$ ) и трансцендентные (например, $\pi$ ), а разделение чисел на нормальные и ненормальные, включая числа Лиувилля.

Нормальное число (в данной системе счисления) определяется как число, в записи которого любая возможная группа цифр встречается с равной вероятностью. Например, судя по первым 100 миллионам знаков, число $\pi$ нормально в десятичной системе счисления [270]. Это означает, что где-то в десятичной записи числа $\pi$ встречается, скажем, восемь семерок подряд. Более того, еуществует достаточно большая вероятность, что такая «великолепная восьмерка» встретится среди первых $10^{8}$ знаков числа $\pi$ (или любого другого нормального десятичного числа). Самые современные даннье по этому вопросу можно почерпнуть в книге Клее и Вагона [130]. Итерации нормальных чисел по формуле (5) порождают хаотические орбиты.

Некоторое представление о том, сколь необычными свойствами обладает такой объект как нормальное число, можно составить, исходя из следующих соображений. Все содержание «Британской энциклопедии» можно закодировать одним-единственным десятичным числом (длиной примерно в $10^{10}$ знаков), и в записи любого нормального числа непременно окажется блок цифр, совпадающий с «кодом» «Британской энциклопедии». Более того, этот блок встретится там бесконечно много раз! (Только не спрашивайте меня где!)

Существуют ли ненормальные иррациональные числа? Оказывается, любая система счисления может похвастаться бесконечным множеством таких чисел! Например, канторовы числа (см. гл. 7) ненормальны в троичной системе, потому что они не содержат единиц. В последующих главах мы познакомимся с постоянной Морса-Туэ 0,01101001… и «кроличьей постоянной» $0,10110101 \ldots$; в двоичной записи этих двух постоянных вы не найдете трех единиц подряд, сколько бы ни искали. Значит, они никак не могут оказаться нормальными двоичными числами.

Известны, однако, еще более необычные ненормальные числа, такие, как двоичное число
\[
L=\sum_{k=1}^{\infty} 2^{-k}=0,110001000000000000000001000 \ldots
\]

и другие числа Лиувилля ${ }^{1}$, которье иррациональны, но очень близки к рациональным числам.
${ }^{1}$ Названные так в честь Жозефа Лиувилля (1809-1882), продемонстрировавшего первое трансцендентное число, прототипом которого является число $L$. Доказательства трансцендентности чисел $е$ и $\pi$ были предложены позднее соответственно Шарлем Эрмитом (1822-1901) и Фердинандом Линдеманом (1852-1939).

Другое доказательство существования трансцендентных чисел дал Георг Кантор, показавший, что алгебраические числа (т.е. корни полиномов с рациональными коэффициентами) образуют счетное множєство. Поскольку континуум представляет В общем случае число Лиувилля $\beta$ определяется как иррациональное число, для которого существует такая пара рациональных чисел $p$ и $q$, что
\[
\left|\beta-\frac{p}{q}\right|<\frac{1}{q^{n}}
\]

при любом $n$. Чтобы число Лиувилля $L$ удовлетворяло неравенству (6), положим $q=2^{n !}$. Тогда суммарная погрешность аппроксимации составит $2^{-(n+1) !}+2^{-(n+2) !}+\ldots$, что (при $n>1$ ) меньше, чем $2^{-n ! n}=q^{-n}$. (При $n=1$ мы полагаем $q=4$ и видим, что $|L-3 / 4|<1 / 4$.) То, что для алгебраических иррациональных чисел в степени $n$ модуль разности в неравенстве (6) превосходит $1 / q^{n+1}$, доказывает существование таких чисел, как $L$, которые «выходят за пределы» множества алгебраических чисел, т.е. трансцендентных чисел.

Итерации нормальных двоичных чисел $\alpha_{0}$ по формуле (5), как следует из их определения, плотно заполняют единичный интервал, причем все подынтервалы одинаковой длины заполняются с равными вероятностями. Таким образом, стационарное распределение при итерациях, называемое инвариантным распределением, является в действительности плоским. Иначе обстоит дело с ненормальными числами. Например, итерации числа $L$ накапливаются в окрестности нуля и всех отрицательных степеней числа 2 (т.е. чисел $1 / 2,1 / 4,1 / 8$ и т.д.)

Итак, мы оказываемся перед лицом прелюбопытного факта: тончайшие различия (различия между рациональными и иррациональными, а среди иррациональных – между нормальными и ненормальными числами) приобретают решающее значение для конечной судьбы численных итераций. Принято думать, будто физика и, тем более, реальный мир в целом, не зависят от чисто математических дихотомий между рациональными и иррациональными или нормальными и ненормальными числами. В действительности же это не так. Хотя все в реальном мире может в принципе быть адекватно огисано с помощью рациональных чисел, однако математическая модель, проводящая различие между теми или иными классами чисел, может оказаться не только чрезвычайно полезной, но и ухватить истинный, возможно, скрытый, дух проблемы.

Говоря конкретнее, два различных начальных состояния физической системы, совершенно неразличимые посредством любого измере-

собой несчетное множество, должны существовать числа (более того, бесконечно много чисел), «выходящие за пределы» множества алгебраических иррациональных чисел, т.е. так называемые трансцендентные числа.

ния конечной точности, при эволюции системы во времени или в пространстве рано или поздно значительно разойдутся. Для этого необходимо лишь, чтобы соответствующее отображение, называемое отображением Пуанкаре (см. гл. 14), было бы достаточно немонотонным (например, таким, как отображение (5), которое обладает пилообразной немонотонностью). Мерой скорости расхождения служит так называемый показатель Ляпунова $\lambda=\ln \left(\alpha_{n+1} / \alpha_{n}\right)$ при $n \rightarrow \infty$. В нашем незатейливом примере, построенном на отображении (5), $\lambda=\ln 2 \approx 0,693$ (это если брать натуральный логарифм).

Хотя итерации, задаваемые отображением (5), могут показаться неестественно простыми, они верно передают сущность бесчисленных нелинейных задач, связанных с бифуркациями удвоения периода и тем самым следующих одной из двух наиболее протоптанных дорог к хаосу (см. гл. 12). (Другая дорога вымощена квазипериодичностью, которая моделируется так называемым отображением окружности, обсуждаемым в гл. 14.)

Странные множества Жюлиа
Метод Ньютона (1), примененный к кубическому уравнению $f(z)=z^{3}-1$, дает отображение
\[
z_{n+1}=\frac{2 z_{n}^{3}+1}{3 z_{n}^{2}},
\]

с которым мы уже сталкивались в гл. 1 на с. 71-73.
Это отображение ведет себя еще более странно, чем предыдущее. Во-первых, наивное предположение о том, что любое $z_{0}$ будет сходиться к ближайшему из трех корней, следует сразу отбросить по причине его несостоятельности. Например, начальное значение $z_{0}=-1$ сходится к 1 , наиболее удаленному от него корню.

На цветной вклейке 3 показаны тесно переплетенные области притяжения всех трех корней – совершенно безумное лоскутное одеяло (может, следовало бы сказать «мнимо безумное»?). Более того, можно доказать, что при отображении, задаваемом соотношением (1), две области притяжения (два цвета) не могут встретиться без того, чтобы при этой встрече не присутствова. третий. Это может показаться невозможным, да это и было бы невозможным – если бы не фрактальная природа границ, изображенных на вклейке 3, которая демонстрирует, помимо всего прочего, притягательное самоподобие, порождаемое ньютоновыми итерациями.

Почему же эти три области притяжения не выглядят попросту как три куска круглого пирога, т. е. как три сектора по $120^{\circ}$ каждый? В конце концов, итерации Ньютона для $z^{2}=1$ приводят к областям притяжения в виде двух полуплоскостей. То, что подобный исход недостижим для $z^{3}=1$, становится понятным, если мы обратим внимание на точку $z=-2^{-1 / 3}$, которая согласно уравнению (1) отображается в точку $z=0$. Окрестность точки $z=0$ содержит точки, принадлежащими всем трем областям притяжения (благодаря 120 -градусной осевой симметрии задачи). Таким образом, исходя из того, что отображение, обратное (1), непрерывно, точка $z=-2^{-1 / 3}$ должна быть также окружена точками, принадлежащими всем трем областям притяжения. Более того, ее бесконечно малая окрестность должна содержать уменьшенную копию «клеверного листа» в начале координат. Значит, ниже отрицательной вещественной полуоси существуют точки, принадлежащие области притяжения аттрактора $z_{1}=\omega=\exp (i \pi / 3)$, расположенного выше вещественной оси. Аналогично, вь-ше отрицательной вещественной полуоси существуют точки, сходящиеся к аттрактору $z_{2}=\omega^{2}$, расположенному ниже вещественной оси. Таким образом, области притяжения корней кубического уравнения никак не могут быть простыми секторами с ровными границами: каждая из областей притяжения «откусывает от пирога» другой области притяжения.

В общем случае для уравнения $z^{n}=1$ метод касательных Ньютона порождает в окрестности начала координат клеверный лист с $n$ лепестками. Поэтому прообраз началє координат, попадающий на границу между двумя аттракторами, перемешивает в этой точке все области притяжения, а при $n>2$ таке перемешивание не может не порождать фрактальной границы, поскольку в двумерном пространстве только граница соприкосновения двух аттракторов может быть гладкой. Кроме того, так как все граничные точки представляют собой прообразы начала координат, они являются граничными точками для всех $n$ областей притяжения. Столь необычные множества граничных точек принято называть множествами Жюлиа. По определению, множество Жюлиа $J$ рациональной функции $R(z)$ есть множество точек $z$, в которых значения функции $R(z)$ не нормальны. (Нормальными называются значения в точках $z$, в окрестности которых функция $R(z)$ равностепенно непрерывна.)

Множество Жюлиа рациональной функции обладает следующим удивительным свойством: если $z_{k}$ – периодический аттрактор, а $A_{k}$ область его притяжения, то $J=\partial A_{k}$ при всех $k$. Здесь $\partial A_{k}$ – граница области притяжения $A_{k}$, т.е. множество всех тех точек, в сколь угодно малой окрестности которых найдутся точки, лежащие как внутри, так и вне $A_{k}$. Следовательно, если точка $z$ принадлежит границе, скажем, области $A_{1}$, то можно смело заявить, что эта же точка принадлежит границам областей $A_{2}, A_{3}, \ldots$

Еще одно важное свойство множества Жюлиа $J$ заключается в том, что периодические репеллеры рациональной функции $R(z)$ плотны в $J$. Более того, если $z_{r}$ – периодический репеллер, то $J$ – замыкание множества всех прообразов точки $z_{r}$. Следовательно, динамика на множестве Жюлиа является хаотической, т.е. чувствительной к начальным условиям, в чем мы уже успели убедиться на стр. $314-316$, когда рассматривали множество Жюлиа функции $R(z)=(z+1 / z) / 2$. Множество Жюлиа всегда содержит несчетное множество точек, но оно не обязательно фрактально.

Множества Жюлиа, состоящие из репеллеров, чрезвычайно трудны для изображения из-за их хаотической чувствительности, требующей реально недостижимой числовой точности. Тому, кто все же решится на такое, может прийти на помощь другое свойство этих множеств для любого числа $z$ из множества $J$ обратная орбита $R^{-n}(z)$ плотна в $J$ при $n=1,2,3, \ldots$ Для точек в $J$ обратная орбита $R^{-n}(z)$ являетсн аттрактором, поэтому никаких проблем с расходимостью чисел не возникает. Но функция $R^{-1}(z)$, вооще говоря, многозначна, поэтому для равномерного покрытия всего множества Жюлиа требуются достаточно хитроумные алгоритмы. Они описаны в книге Пайтгена и Заупе «Наука о фрактальных образах» [196]. На рис. 2 показано пылевидное множество Жюлиа для отображения (1), построенное с помощью такого алгоритма.

Даже такой простой пример рационального отображения с тремя аттракторами и его множество Жюлиа, рассмотренные нами выше, имеют свои физические приложения. Рассмотрим, например, маятник, состоящий из подвешенного на конце нити железного шарика. Под маятником находятся три магнита, притягивающие шарик. После нескольких колебаний маятник замрет, а шарик зависнет точно над одним из трех магнитов. Но всегда ли шарик устремится к тому из аттракторов, который окажется ближайшим к его начальному положению? Отнюдь! Попробуйте, и вы убедитесь в этом сами. При различных начальных условиях шарик описывает весьма замысловатую траекторию, а его конечное положение представляется совершенно непредсказуемым. Более того, оно нередко не только кжется непредсказуемым, но в действительности таковым и является, если только начальное положение шарика не задано с какой-то сверхнеобыкновенной и совершенно нере-

Рис. 2. Пыль Жюлиа для итераций Ньютона [196].
альной точностью. Иначе говоря, области притяжения трех магнитов определяются фрактальными множествами – так же, как множество Жюлиа в итерациях Ньютона.

Мультифрактальное множество Жюлиа
В предыдущем разделе мы выяснили, что множества Жюлиа рациональных функций с более чем двумя аттракторами представляют собой фракталы. В действительносту такие множества мультифрактальны. По традиции такие множества принято анализировать путем построения их отдельных точек с помощью обратных численных итераций. Однако для анализа некоторых множеств Жюлиа можно воспользоваться аналитическими методами, несравненно более точными и сопряженными с существенно меньшим объемом вычислений. Убедительным тому примером может служить недавно произведенный Науэнбергом и Шельнхубером анализ мультифрактальных свойств множества Жюлиа, связанного с ньютоновым отображением (1) для отыскания корней кубического уравнения $z^{3}-1=0$ [183].

Прежде всего необходимо постролть носитель фрактального множества. Для исходного канторова множества носителем является единичный интервал: все его элементы «обитают» на единичном отрезке прямой. Что же касается нашего ньютоновского множества Жюлиа, то его носитель и сам обладает чрезвычайно сложной структурой – этакая бесконечное число раз вложенная в себя «паутина». Построить это «убежище для пауков» Науэнбергу и Шельнхуберу помогло одно немаловажное обстонсельство: один из трех прообразов отрицательной вещественной полуоси есть полубесконечный интервал $-\infty<z \leqslant-2^{-1 / 3}$, обозначенный на рис. 3А через $M_{0}$. Два других прообраза получаются из $M_{0}$ поворотами на $\pm 120^{\circ}$.

Два прообраза $M_{+}$и $M_{-}$множества $M_{0}$, не лежащие на отрицательной вещественной полуоси, определяются выражением
\[
M_{ \pm}=\xi \pm i\left(\xi^{1 / 2}-\xi^{2}\right), \quad 0 \leqslant \xi \leqslant 2^{-4 / 3} .
\]

Остальные четыре дугообразных прообраза второго порядка получаются при поворотах на углы $\pm 120^{\circ}$. Эти шесть дуг и три прямолинейных «шипа»на концах лепестков вместє образуют первое поколение носителя фрактала. Второе поколение состоит из $3 \cdot 9=27$ частей и т.д. На рис. ЗБ показан носитель на четвертой стадии построения (т. е. составленный из первых четырех поколений, полученных с помощью обратных итераций из центрального цветка). Уже на данном этапе отчетливо видна иерархическая («вложенная») структура этого фрактала Жюлиа.

Прообразы $x_{n}$ более высокого порядка точки $z=0$, лежащие на отрицательной вещественной полуоси, определяются соотношением
\[
x_{n+1}=\frac{x_{n}}{2}+x_{n} \operatorname{ch}\left[\frac{1}{3} \operatorname{ch}^{-1}\left(1-2 x_{n}^{-3}\right)\right] \text {, }
\]

где $x_{1}=-2^{-1 / 3}$. Асимптотический коэффициент подобия для $x_{n}$ равен $3 / 2$. Его можно вывести из производной прямой итерации: $d N / d z \rightarrow 2 / 3$ при больших $z$.

Прообразы $\zeta_{n}=\xi_{n}+i \eta_{n}$ точен $x_{n}$ на $M_{+}$определяются соотношением
\[
\xi_{n+1}=-x_{n} \operatorname{sh}^{2}\left[\frac{1}{3} \operatorname{sh}^{-1}\left(\left(-x_{n}\right)^{-3 / 2}\right)\right],
\]

и, как следует из формулы (1), $\eta_{n+1}= \pm\left(\xi_{n+1}^{1 / 2}-\xi_{n+1}^{2}\right)$. Длины $l_{n}$ дуг на $M_{+}$между $\xi_{n}$ и $\xi_{n+1}$ асимптотически убывают как $l_{n} \sim(2 / 3)^{n / 2}$. Самая большая дуга имеет длину $l_{1}=0,3834$.

Чтобы вычислить фрактальные размерности $D_{q}$, сосредоточим внимание на одном из трех лепестков центрального цветка (рис. 3B). В первом поколении лепесток состоит всего лишь из двух больших дуг.

Рис. 3. (А) Построение цветка Жюлиа: прообразы первого поколения. (Б) Носитель «цветочного» множества Жюлиа на четвертом этапе его построения. (B) Лепесток Жюлиа: первые три шага построения [183].

В качестве следующего шага рассмотрим бесконечную последовательность меньших дуг, концы которых, лежащие на двух больших дугах, определяются прообразами первого порядка точек $x_{n}$ на отрицательной вещественной полуоси. Заметим, что каждая дуга порождает последовательность двойных дуг. На рис. 3В (внизу) показан результат третьего шага построения: каждая меньшая дуга покрылась бесконечной последовательностью еще меньших двойных дуг.

Интересующее нас множество Жюлиа, а именно, множество общих граничных точек трех областей притяжения, состоит из точек ветвления носителя. (Аналогичным образом обстоит дело с исходным канторовым множеством, которое состоит из концевых точек остающихся интервалов.) Фрактальные размерности $D_{q}$ нашего множества Æюлиа определяются выражением
\[
2 \sum_{m} p_{m}^{q} l_{m}^{\tau}=1, \quad \tau=(1-q) D_{q}
\]
(см. гл. 9), где суммирование проводится по последовательным поколениям построения носителя, а множитель 2 отражает то обстоятельство, что каждая материнская дуга порождает двух сестер-близнецов двойную дугу. Выбрав три прообраза с одинаковыми весами, получим $p_{m}=(1 / 3)^{m}$. Длины дуг $l_{m}$ вычисляются по формулам (1)-(3).

Из всех размерностей проще всего вычисляется $D_{\infty}$, потому что при $q \rightarrow \infty$ показатель $\tau$ стремитея к $-\infty$, и вклад в сумму (4) дает лишь наибольшая длина $l_{m}$. Наибольшей из $l_{m}$ является $l_{1} \approx 0,3834$. Следовательно, при $p_{1}=1 / 3$ мы получаем
\[
D_{\infty}=\frac{\ln p}{\ln l_{1}}=1,146 \ldots
\]

При $q= \pm \infty$ коэффициент 2 в соотношении (4) становится несущественным. Другая предельная размерность $D_{-\infty}$ вычисляется столь же легко. На этот раз главным слагаемым в сумме (4) является наименьшая длина $l_{m}$, т.е. $l_{m}$ при $m \rightarrow \infty$. Учитывая, что при больших $m$ и $p_{m}=(1 / 3)^{m}$ длина изменяется по закону $l_{m} \sim(2 / 3)^{m / 2}$, получаем из соотношения (4)
\[
D_{-\infty}=\lim _{m \rightarrow \infty} \frac{\ln 3}{\frac{1}{2} \ln \frac{3}{2}}=5,419 \ldots
\]

Заметим, что в отличие от размерности Хаусдорфа $D_{0}$ предельная размерность $D_{-\infty}$ не имеет простого геометрического смысла. И поэтому то, что ее величина превосходит 2 (евклидову размерность пространства вложения для фрактала Жюлиа), не составляет никакого противоречия.

Интересно отметить, что при изложенном выше подходе численное значение размерности $D_{-\infty}$ определяется простым аналитическим фактом, а именно тем, что $l_{m} \sim(2 / 3)^{m / 2}$. В отличие от аналитического метода численные методы при $q=-\infty$ оказываются бессильными, так как в этом случае компьютеру пришлось бы работать целую вечность, исследуя наиболее редко заселенные области множества Жюлиа, которые и характеризуются размерностью $D_{-\infty}$. Учитывая это обстоятельство, обычно возникает искушение оценить значение размерности $D_{-\infty}$ по $D_{q}$ при больших $q$. Однако такой подход наталкивается на обескураживающе медленную сходимость. Другие размерности, в том числе размерность Хаусдорфа $D_{0}$, можно также определить с помощью элементарных вычислений. Для получения хороших приближений достаточно в сумме (4) явно учесть лишь несколько длин $l_{m}$. Что до остальных слагаемых, то для них вполне подойдет приближенное значение $l_{m}=0,1986(2 / 3)^{m / 2}$. Такой подход дает для размерности Хаусдорфа величину $D_{0}=1,429 \ldots$, намного более точную, чем те, что получены «числодробительными» методами, на основании обработки миллиона точек множества Жюлиа. Заметим, что $D_{0}<2$ – вполне подобающее значение для двумерной пыли. Что же касается такой важной характеристики, как информационная размерность (см. гл. 9)
\[
D_{1}=\frac{\sum_{m} p_{m} \ln p_{m}}{\sum_{m} p_{m} \ln l_{m}},
\]

то для хорошей оценки $D_{1} \approx 1,2$ достаточно учесть только две длины: $l_{1} \approx 0,38$ и $l_{2} \approx 0,18$.

Красота кусочно-линейных отображений
На рис. 4 вы видите результат применения кусочно-линейного «пилообразного» отображения $\widetilde{b}=8 b \bmod 1$ к локальной яркости $0 \leqslant b \leqslant 1$ фотографии человеческого лица и пос.едующем квантовании $\tilde{b}$ в 0 (если $\widetilde{b}>b$ ) или в 1 (если $\tilde{b} \leqslant b$ ) [225]. На рис. 5 показан красивый узор, образующийся при итерации другой простой кусочно-линейной функции $[193]$.

(1)
Рис. 4. Пилообразное отображение «Карен», из первых опытов автора в компьютерной графике [225].
Такие отображения представляют собой полезные математические модели детерминированной диффузии [234]. В то время как традиционная (термодинамическая) диффузия является типичным случайным процессом, кусочно-линейные отображения, аналогичные представленному на рис. 6 , обусловливают внешне случайное движение частицы при том, что ее дрейф является в действительности строго детерминированным процессом. Этот дрейф может служить еще одним примером хаотического движения, сильно зависящего от точного (хотя и не всегда точно определяемого) начального значения координаты. Как и при обычной диффузии, пространственная корреляция между двумя первоначально близкими частицами со временем убывает до нуля [89]. В результате среднеквадратичное смещение $\overline{x^{2}}$ возрастает со временем линейно, как и при обычной диффузии:
\[
\overline{x^{2}}=2 D t \text { при } t \gg 1,
\]

где $D$ – коэффициент диффузии, пропорциональный ширине $\delta$, на которую итерированная функция «высовывается» из единичного квадрата.

Рис. 5. Вышитый узор в свете дробно-линейного преобразования [193].
Преобразование пекаря и цифровой вариант игры в «стулья с музыкой»

Пекари месят тесто, раскатывая его, складывая и вновь раскатывая – бесконечная, на первый взгляд, последовательность итераций до тех пор, пока не добиваются достаточно однородной смеси ингредиентов.

На рис. 7 вы видите математически облагороженный вариант операций раскатывания и складывания теста, известный под названием преобразование пекаря. Это полезная модель для всевозможных процессов перемешивания, в том числе хаотического перемешивания жидкостей. В арифметическом смысле точка $(x, y)$ в единичном квадрате переходит в точку $(2 x, y / 2)$ при раскатывании и в точку $\left(\langle 2 x\rangle_{1}, y / 2+\right.$ $+\lfloor 2 x\rfloor / 2$ ) при последующем разрезании раскатанного теста пополам и помещении правой половины над левой половиной. (Эта операция математически проще, чем складывание.) Здесь, как и ранее, угловые

Рис. 6. Дробно-линейное отображение для моделирования детерминированной диффузии [89].

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

Рис. 7. Отображение пекаря: рецепт хаотического теста. Сначала «раскатываем» единичный квадрат, затем отрєзаем его правую половину и помещаем ее над левой половиной.

Если $x$ и $y$ выразить в двоичной форме, то преобразование пекаря значительно упрощается: цифры в записи координаты $x$ сдвигаются на один знак влево, цифры в записи координаты $y$ сдвигаются на один знак вправо, а самая левая цифра координаты $x$ становится самой левой цифрой координаты $y$. Двоичные цифры в $x$ и $y$ играют в своего рода «стулья с музыкой» ${ }^{1}$. Например, пара координат
\[
\begin{array}{l}
x_{1}=0,10110001 \ldots, \\
y_{1}=0,01110100 \ldots
\end{array}
\]

отображается в пару
\[
\begin{array}{l}
x_{2}=0,0110001 \ldots, \\
y_{2}=0,101110100 \ldots,
\end{array}
\]

которая, в свою очередь, переходит в пару
\[
\begin{array}{l}
x_{3}=0,110001 \ldots, \\
y_{3}=0,0101110100 \ldots
\end{array}
\]

и т.д. Таким образом, любая конечная дробь $x$ асимптотически стремится к началу координат $(0,0)$, которое становится аттрактором для таких значений $x$.

Периодические двоичные значения $x$ сходятся к периодическим орбитам. Например, координаты $x=1 / 3=0,(01), y=2 / 3=0,(10)$ сходятся к периодической орбите с периодом 2. Напротив, нормальные двоичные числа порождают хаотические орбиты, на которых даже первоначально близкие точки вскоре разбегаются и следуют по своим независимым орбитам (рис. 8). И хаотические, и нехаотические потоки обсуждаются в статье Оттино «Перемешивание жидкостей» [187].

Иногда пекарь после каждой итерации отбрасывает какую-то часть теста. В этом случае то, что остаетсғ, постепенно превращается в одном направлении в канторову пыль. Такое обобщенное преобразование пекаря представляет собой простую модель фазовых пространств нелинейных динамических систем – пространств, которые сжимаются по некоторым направлениям и потому обзаводятся странными аттракторами – такими, как множества Жюлиа, рассмотренные нами на c. 319-326.
${ }^{1}$ Игра, в которой могут принимать участие любое число желающих. Играющие ходят под музыку вокруг выстроенных в круг стульев, число которых на единицу меньше числа участников. Музыка внезапно прекращается, и играющие бросаются занимать свободные стулья. Проигрывает тот, кому не хватило стула. – Прим. перев.

Рис. 8. Хаотическая орбита точки при преобразовании пекаря; начальная точка находилась вблизи периодической точки ( $x_{0}=2 / 3, y_{0}=1 / 3$ ) с периодом 2.

Среди родственных преобразсваний можно назвать отображение «подкова Смейла» [246] (рис. 9) и отображение Энона (рис. 10), описывающих характерные особенности диссипативных физических систем со странными аттракторами.

Рис. 9. Подкова Смейла. Пространство растягивается в одном направлении, сжимается в другом, а затем складывается вдвое. Пара точек, оказавшихся после нескольких итераций рядом, могли находиться очень далеко друг от друга в начале процесса.

Где же в отображении Энона таится самоподобие? Взгляните на рис. 10 Г и на аттрактор Энона пос.е $10^{4}$ итераций, представленный на Рис. 10. Отображение Энона. (А) Исходный эллипс. (Б) Сохраняющий площадь изгиб: $x^{\prime}=x, y^{\prime}=1-a x^{2}+y$. (В) Сжатие по оси $x: x^{\prime \prime}=b x^{\prime}, y^{\prime \prime}=y^{\prime}$. (Г) Поворот на $90^{\circ}: x^{\prime \prime \prime}=y^{\prime \prime}, y^{\prime \prime \prime}=-x^{\prime \prime}[234]$.

рис. 11. Хотя странные аттракторы и вправду странны во многих отношениях, они все-таки демонстрируют самоподобный порядок в своих хаотических орбитах.

Рис. 11. Самоподобность аттрактора Энона. (А) Аттрактор целиком. (Б) Увеличение части аттрактора, выделенной квадратом на рис. (А). (В) Еще одно увеличение. Отметьте сходство штриховых узоров на рис. (Б) и (В), подтверждающее самоподобность аттрактора Энона [64].
Кошка Арнольда
Среди двумерных отображений нельзя обойти молчанием сохраняющее площадь отображение «кошка Арнольда», описывающее гамильтоновы нелинейные системы:
\[
\begin{array}{l}
x_{n+1}=x_{n}+y_{n} \bmod 1, \\
y_{n+1}=x_{n}+2 y_{n} \bmod 1,
\end{array}
\]

изображенное на рис. $12 \mathrm{~A}$ и 12 Б. Запись $\bmod 1$, как и ранее, означает, что рассматриваются только дроби из полуоткрытого единичного интервала $[0,1)$. Искажение картинки, порождаемое этим преобразованием, напоминает о плохо отрегулированном телевизоре. Отображение «кошка Арнольда» имеет два собственных значения $\lambda_{1}$ и $\lambda_{2}$, которые, соответственно, равны квадрату величины, обратной золотому сечению $\gamma$, и числу, обратному этому квадрату: $\lambda_{1}=(3+\sqrt{5}) / 2>1$ и $\lambda_{2}=\lambda_{1}^{-1}=(3-\sqrt{5}) / 2<1$. Поскольку одно собственное значение больше единицы, а другое меньше то все неподвижные точки отображения являются гиперболическими. Это означает, что кошка Арнольда растягивает по одному направлению (соответствующему собственному значению $\lambda_{1}$ ) и сжимает по другому, перпендикулярному первому, направлению (соответствующему значению $\lambda_{2}$ ). Таким образом, неподвижные точки отображения не являются ни репеллерами, ни аттракторами, а и теми и другими, в зависимости от направления, по которому мы к ним приближаемся. С точки зрения геометрии гиперболические неподвижные точки представляют собой седловые точки: мяч катится с горы по направлению $\kappa$ седловой точке (горному перевалу), а затем движется от седловой точки к долине. Перевал сначала притягивает, а затем отталкивает низвергающийся с гор по направлению к нему поток воды, т. е. сначала выступает в роли аттрактора, а затем репеллера.

Рис. 12. (А) Кошка Арнольда; (Б) итерированное отображение «кошка Арнольда».

Отображения с гиперболическими неподвижными точками являются неотъемлемым признаком хаотического движения в консервативных (сохраняющих энергию) физических системах, известных под названием гамильтоновых систем [8]. Например, $(x, y)=(0,4 ; 0,2)$ неподвижная точка однократно итерированного отображения «кошка Арнольда», т.е. она принадлежит орбите с длиной периода 2. Эта точка переходит в точку $(0,6 ; 0,8)$, которая, в свою очередь, отображается в исходную точку $(0,4 ; 0,2)$. Преобразование исходной точки $(0,4 ; 0,2)$ в направлении, соответствующем собственному значению $\lambda_{2}(\Delta x / \Delta y=-(\sqrt{5}+1) / 2=-1 / \gamma)$, является сжимающим. Действительно, первые четные итерации $x_{2 n}$ начальной точки ( $x_{0}=0,4+$ $\left.+1 / 100 \gamma, y_{0}=0,2-1 / 100\right)$, начиная с $x_{2}$, имеют следующие приближенные значения: 0,$402 ; 0,4003 ; 0,40005 ; 0,400007 ; 0,400001 ; 0,4000002$.

Следовательно, точка $(0,4 ; 0,2)$, если приближаться к ней с направления, соответствующего собственному значению $\lambda_{2}$, действует как аттрактор. Но если мы продвинемся по этой сходящейся последовательности несколько дальше, воспользовавшись 12-разрядным калькулятором, который вносит небольшую погрешность в направлении $\lambda_{1}$, то эти небольшие погрешности приведут нас в конце концов к расходимости, о чем свидетельствуют последующие итерации: 0,$4000005 ; 0,400003 ; 0,40002 ; 0,4002 ; 0,401 ; 0,407 ; 0,45 ; 0,75$ и т. д. до полного хаоса. Дело в том, что в силу двойственной (аттракторнорепеллерной) природы гиперболических неподвижных точек любое вычисление (равно как и любая физическая система, моделируемая кошкой Арнольда) рано или поздно демонстрирует хаотическое движение, за исключением редких начальных условий нулевой меры. Такие начальные условия, конечно же, не могут быть реализованы физически, так как они соответствуют неустойчивым состояниям равновесия (например, поставленный на острие карандаш).

Одно из преимуществ кошки Арнольда состоит в том, что итерации этого отображения легко анализировать. В матричной форме отображение (1) (кошка Арнольда) задается матрицей
\[
T=\left(\begin{array}{ll}
1 & 1 \\
1 & 2
\end{array}\right),
\]

которая переводит вектор-столбец $\left(x_{n}, y_{n}\right)$ в вектор-столбец $\left(x_{n+1}, y_{n+1}\right)$, где все $x$ и $y$ берутся по модулю 1 .

Зная рекуррентное соотношение для чисел Фибоначчи $F_{n}=F_{n-1}+$ $+F_{n-2}, F_{1}=F_{2}=1$, нетрудно с помощью индукции доказать, что $n$-я итерация отображения Арнольда имеет следующий вид:
\[
T^{n}=\left(\begin{array}{cc}
F_{2 n-1} & F_{2 n} \\
F_{2 n} & F_{2 n+1}
\end{array}\right) .
\]

Это преобразование наследует свойство $T$ сохранять площадь. (Действительно, определитель матрицы $T^{n}$, т. е. $F_{2 n-1} F_{2 n+1}-F_{2 n}^{2}$, равен 1.) Так как $T^{n}$ – симметричная матрица, ее собственные значения $\left(\lambda_{1}^{(n)}=\right.$ $=\lambda_{1}^{n}>1$ и $\lambda_{2}^{(n)}=\lambda_{2}^{n}<1$ ) всегда вещественны.

Неподвижные точки отображения $T^{n}$ соответствуют орбитам с длиной периода $n$ (вместо $n$ подойдет любое его кратное). Например, при $n=2$
\[
T^{2}=\left(\begin{array}{ll}
2 & 3 \\
3 & 5
\end{array}\right) .
\]

Чтобы найти неподвижные точки с периодом 2 , необходимо решить уравнения
\[
\begin{array}{l}
2 x+3 y=x \bmod 1, \\
3 x+5 y=y \bmod 1 .
\end{array}
\]

Исключая $y$, мы, помимо решения $x=y=0$ (длина периода равна 1), получаем уравнение $5 x=0 \bmod 1$, т. е. $x=k / 5$, где $k$ – целое число. Так как $0<x<1$, для $k$ допустимы только значения $1,2,3,4$, каждое из которых дает решение. Соответствующие значения $y$ представимы в виде $y=k^{\prime} / 5$, где $k^{\prime}=-2 k \bmod 5$. Эти четыре периодические точки с длиной периода 2 образуют две орбиты, а именно: $(2 / 5,1 / 5) \rightarrow$ $\rightarrow(3 / 5,4 / 5)$, с которой мы уже встречались, и $(1 / 5,3 / 5) \rightarrow(4 / 5,2 / 5)$.

Заинтересованному читателю мы рекомендуем произвести анализ полной структуры орбит кошки Арнольда, что, на наш взгляд, весьма поучительно.

Миллиард знаков для $\pi$
Итерации принадлежат к числу наиболее мощных математических инструментов. Для вычисления числа $\pi$ с помощью ряда ГрегориЛейбница
\[
\frac{\pi}{4}=1-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}+\ldots
\]

с точностью лишь до трех десятичных знаков требуется учесть 500 членов ряда, между тем как рекурсия, использующая арифметикогеометрическое среднее, позволяет с каждым шагом удваивать количество правильных знаков $[27,130]$. А есть еще итеративные алгоритмы, основанные на работах Рамануджана, позволяющие с каждой итерацией увеличивать количество десятичных знаков в 4 и даже в 5 раз [28]. Тринадцать итераций такого алгоритма уже дали более 134 миллионов знаков числа $\pi$, а вычислив еще две итерации, мы довели бы точность $\pi$ до более чем двух миллиардов знаков. При этом относительная погрешность составляет $10^{-10^{9}}$ (а не просто $10^{-9}$ ). Поразительная точность!

Никому, разумеется, не нужно знать число $\pi$ с такой сверхъестественной точностью. Самые точные измерения в физике, использующие эффект Мёссбауэра, производятся с точностью, скажем, до 14 десятичных знаков. Такая точность соответствует погрешности в 1 секунду за 3 миллиона лет. Тридцать девять знаков в десятичной записи числа $\pi$ достаточно для того, чтобы вычислить длину окружности известной

Вселенной с точностью до диаметра атома водорода. Однако вычисление знаков числа $\pi$ стало своего рода эталонным тестом для суперкомпьютеров и сверхбыстрых алгоритмов. Излишне говорить, что такие вычисления производятся не на карманных калькуляторах, поскольку те не обладают ни необходимым объемом памяти, ни достаточно вместительным дисплеем.

Одним из наиболее поразительных достижений Рамануджана по праву считается следующая формула:
\[
\frac{1}{\pi}=\frac{\sqrt{8}}{9801} \sum_{n=0}^{\infty} \frac{(4 n) ![1103+26390 n]}{(n !)^{4}\left(396^{4 n}\right)} .
\]

Даже при учете только самого первого члена суммы точность вычисления $\pi$ превосходит $3 \cdot 10^{-8}$. Каждый последующий член дает еще восемь десятичных знаков (т.е. увеличивает точность в 100 миллионов раз).

Очень быстро сходящиеся приближения $\pi$ основаны на одной из основополагающих работ Рамануджана, в которой он установил тесную взаимосвязь между приближением (1) и теорией преобразований эллиптических интегралов [208]. Один из рекурсивных алгоритмов, проистекающих из этой свнзи, сводитсн к следующему. Пусть $\alpha_{0}=6-4 \sqrt{2}$ и
\[
y_{n+1}=\frac{1-\left(1-y_{n}^{4}\right)^{1 / 4}}{1+\left(1-y_{n}^{4}\right)^{1 / 4}}, \quad y_{0}=\sqrt{2}-1 .
\]

Тогда
\[
\alpha_{n+1}=\left(1+y_{n+1}\right)^{4} \alpha_{n}-2^{2 n+3} y_{n+1}\left(1+y_{n+1}+y_{n+1}^{2}\right)
\]

приближается к $\frac{1}{\pi}$ с погрешностью меньшей, чем $16 \cdot 4^{n+1} \exp \left(-2 \pi \cdot 4^{n+1}\right)$. Уже первое приближение $\alpha_{1}$ дает 9 правильных знаков в $\pi$, второе же $\alpha_{2}$ дает уже 40 правильных знаков. Число знаков $n$-го приближения $\alpha_{n}$ превышает $2 \cdot 4^{n}$; оно асимптотически увеличивается в четыре раза с каждой итерацией и после 15 шагов превышает 1 миллиард.

Существует даже пятикратный алгоритм, который увеличивает число правильных знаков с каждым шагом в пять раз [28].

Насколько случаен первый миллиард знаков $\pi$ ? Грегори и Дэвид Чудновски из Колумбийского университета обнаружили, что цифры числа $\pi$ более случайны, чем последовательности цифр, порождаемые стандартными генераторами псевдослучайных чисел; поскольку такие генераторы основаны на алгоритмах с конечным числом состояний, они
в конечном счете периодичны. В частности, при воспроизведении броуновского движения цифры числа $\pi$ порождают случайные блуждания, которые, по-видимому, удовлетворяют закону повторного логарифма (чего не скажешь об обычных генераторах псевдослучайных чисел).

Даже если это так, не существует строго математического доказательства нормальности числа $\pi$ (напомним, что в записи нормального числа любые группы цифр встречаются асимптотически равновероятно). Более того, сам факт, что $\pi$ можно определить такими компактными и быстро сходящимися формулами, как (1), внушает специалистам подозрение в ненормальности числа $\pi$ при некотором подходящим образом выбранном основании.

Кустарники и цветы от итераций
Итерирование простых правил принадлежит к числу наиболее сильнодействующих рецептов для порождения не только математических фракталов, но и интересных биологических форм [203]. Излюбленным примером такого рода процессов является так называемый «черепаший алгоритм» для рисования линиями.

Состояние «рисующей черепахи» определяется тройкой чисел $(x, y, \alpha)$, где декартовы координаты $(x, y)$ указывают положение черепахи, а угол $\alpha$, называемый курсом черепахи, указывает, в какую сторону черепаха «смотрит». Если заданы величина шага $d$ и приращение угла $\delta$, то черепаха откликается на команды, обозначаемые следующими символами:
$\mathrm{F}$ Ход вперед на один шаг длины $d$. Такое движение переводит исходное состояние черепахи в новое состояние $\left(x^{\prime}, y^{\prime}, \alpha\right)$, где $x^{\prime}=x+$ $+d \cos \alpha$ и $y^{\prime}=y+d \sin \alpha$. Черепаха оставляет за собой след, вычерчивая отрезок прямой, соединяющий точку $(x, y)$ с точкой $\left(x^{\prime}, y^{\prime}\right)$.
f Ход вперед на один шаг длины $d$ без вычерчивания линии.
+ Поворот вправо (по часовой стрелке) на угол $\delta$. В результате такого хода черепаха переходит в состояние $(x, y, \alpha+\delta)$.
– Поворот влево на угол $\delta$. Состояние черепахи меняется на $(x, y, \alpha-\delta)$.
Пусть $
u$ – упорядоченная последовательность команд, $\left(x_{0}, y_{0}, \alpha_{0}\right)$ начальное состояние черепахи, $d$ и $\delta$ – фиксированные параметры. Картина (совокупность линий), которую черепаха нарисует в ответ на последовательность команд $
u$ называется черепашьей интерпретацией $
u$.

На рис. 13 показан пример черепашьей графики – фрактальная картина «Острова и озера», которую черепаха «нарисовала», начав с единичного квадрата, заданного последовательностью команд $\mathbf{F}-\mathbf{F}-\mathbf{F}-\mathbf{F}$. В соответствии с вышеприведенными правилами, черепаха интерпретирует такую последовательность хоманд как последовательность прямолинейных отрезков, соединенных «голова к хвосту».

Рис. 13. Вложенные друг в друга «Острова и озера», изображенные с помощью черепашьего алгоритма [161].

При дальнейшей разработке черепашьего алгоритма Линденмайер ввел специальные обозначения для представления теоретико-графовых деревьев, используя последовательности со скобками [148]. Целью такого нововведения было получение инструмента для формального описания ветвящихся структур, встречающихся во многих растениях от водорослей до деревьев. Это расширение черепашьей интерпретации использует два дополнительных символа:
[ Запомнить текущее состояние черепахи $(x, y, \alpha)$ для последующего восстановления.

Вернуться к состоянию до парной открывающей скобки ([), и продолжить выполнение команд, стоящих справа от закрывающей скобки (]). Обратите внимание на возможность появления скобок внутри скобок.

Примером последовательности команд со скобками и ее интерпретации черепахой может служить куст на ветру, изображенный на рис. 14.
Рис. 14. «Куст на ветру» (обратите внимание на его самоподобие) [203].
На цветных вклейках $7 \mathrm{~A}-7 \mathrm{E}$ показаны шесть напоминающих растения структур, которые создал указанным выше способом Прусинкевич [203]. Добавляя к своим конструкциям цвет, Прусинкевич получил захватывающе красивые и вполне реалистичные цветы и кустарники, в чем читатель может убедиться сам, взглянув на вклейку 7 , воспроизводимую с любезного разрешения автора.

Используя другой подход к кодированию образов, известный под названием системы итерированных функций, Барнсли создал изображения подсолнухов, папоротников и лесов с помощью поразительно малого набора параметров (см. гл. 1, с. 56-58).