Самоподобие, всплески и квазикристаллы

Назовем сигналом любую информацию, переданную от одной системы другой. Окружающий нас мир наполнен сигналами и в нем нет абсолютно изолированных подсистем (излучают даже черные дыры). Например, сигналом является зависимость тока от времени в электрической цепи I(t), кардиограмма представляет собой пространственную развертку на бумаге временного ритма сердца. Профиль поверхности Земли или фотография - простейшие представители двумерных сигналов h(x,y) (h это или высота профиля или интенсивность снимка в точке с координатами x и y). Для удобства ограничимся рассмотрением только одномерных сигналов, которые будем обозначать f(x), где a<x<b (x это либо пространственная координата, либо время t). Границы этого интервала условны, a может быть равно -0-0 , a b = +0-0 . Величину ||f|| = принято называть энергией сигнала или его нормой. Все сигналы конечной энергии, т.е. функции f(x), удовлетворяющие условию ||f|| <0-0 , образуют пространство Гильберта L²[a,b]. В квантовой механике и ряде других случаев удобно работать с комплекснозначными функциями, тогда в определении нормы необходимо заменить f² на f*f. Мы считаем f(x) действительной.

Очевидно, что L²[a,b] это очень богатое пространство, но в нем всегда можно выбрать бесконечный счетный набор функций y _j(x), j=1,2,..., такой что , где d _jk=0 если j<> k, а d_jj=1. Таких наборов существует бесконечно много. При определенных условиях они образуют ортонормированный базис, т.е. любой сигнал конечной энергии можно представить в виде

, (1)

где c_j - это некоторые числовые коэффициенты. Легко видеть, что . Имея в руках сигнал f(x) и набор y _j(x) можно вычислить любой коэффициент c_j - эта процедура называется анализом, т.к. она определяет сколько y _j(x) содержится в f(x) . Наоборот, зная коэффициенты c_j, легко восстановить (без потери информации) начальный сигнал по формуле (1), и такая процедура называется синтезом.

При анализе сигнала мы заменяем функцию f(x), состоящую из непрерывной последовательности точек, на дискретную последовательность чисел c_j . Есть ли в этом экономия, или точнее, сжатие информации? Несмотря на кажущуюся положительность ответа, сжатия нет, т.к. необходимо задать бесконечную последовательность чисел (в математике существует много заключений кажущихся парадоксальными при работе с бесконечными последовательностями). С практической точки зрения бесконечностей просто не существует, так же как и непрерывных функций. Любой экспериментальный сигнал задается конечной последовательностью точек приближающих абстрактную функцию f(x) только с определенной точностью. Разрешая пренебрегать несущественными деталями, т.е. аппроксимировать сложный объект более простым, мы приходим к реальной возможности сжатия информации, а значит более высокой скорости передачи сигнала по линиям связи (или по сети нейронов живых существ). Действительно, условие конечности энергии

,

требует c_j->0 при j->0-0 . Разрешая пренебрегать некоторыми коэффициентами из условия, что и конечная сумма при каком-то N отличаются только на некоторое маленькое число x, мы и приходим к конечности реальной записи сигнала. Если при заданном e удается минимизировать N путем подбора функций базиса y _j(x), то это и будет оптимальным сжатием данного сигнала.

На первый взгляд все очень просто, но неискушенного исследователя ожидает множество неясностей и неприятностей. Например, последовательность функций y _j(x) надо как-то упорядочить (требование однозначности разложения по базису ограничивает выбор y _j(x). Любую функцию из L²[a,b]. можно взять в качестве одного из элементов базиса, подобрав остальные с помощью процедуры ортогонализации. Тогда только один коэффициент в формуле (2) будет отличен от нуля. Однако это не решение проблемы, т.к. подбор функций базиса трудоемок, а передача информации о базисе на приемное устройство для последующего синтеза эквивалентна передаче начального сигнала. При необходимости передачи большого набора сигналов различной природы невыгодность этой процедуры очевидна вдвойне.

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

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

Наиболее известным представителем этого семейства является базис Фурье-гармоник, которые появляются как собственные функции простейшего дифференциального оператора второго порядка с определенными граничными условиями. Разложение (гармонический анализ) произвольного сигнала заданного на интервале [0, 2П ] в ряд Фурье (1) имеет максимально простой вид в комплексной форме

, .

Сама функция f(x) действительна, для этого c_j должны удовлетворять некоторому простому ограничению. Если в этом ряду присутствуют только два члена, образующие синус или косинус по формуле e^if =cosf +isinf , то мы имеем оптимальную кодировку чистого тона музыкального инструмента (это связано с тем, что соответствующий базис появляется как решение уравнения колебания струны). В случае непрерывного базиса, например при a=-0-0 , b=+0-0 , имеем разложение в Фурье-интеграл

СИНТЕЗ,

АНАЛИЗ

Недостатком базиса Фурье является нелокальность его элементов в координатной развертке - реально они оккупируют всю действительную ось. Однако они полносью локализованы в частотном спектре. Иногда удобным оказывается свойство универсальности базисов ортогональных полиномов - их применимость к функциям произвольной гладкости (степень гладкости - это, условно, число производных существующих для данной функции). В частности, полиномы Чебышева очень просты и обладают уникальными аппроксимационными свойствами. Для численных методов важно иметь функции с компактным носителем, т.к. в этом случае матрицы операторов в соответсвующих базисах имеют меньший размер.

Для задач интерполяции широко применяются сплайны - кусочно-гладкие функции, построенные из полиномов. По своей природе они очень близки к всплескам и до появления последних удельный вес сплайнов в прикладных задачах был значительно выше. Однако, их основной недостаток (присущий и всплескам Добеши) - это наличие корреляции между степенью сплайна (чем выше степень, тем больше размер носителя) и степенью гладкости аппроксимируемой функции. Упомянутая up-функция является атомарной (имеет конечный носитель) и универсальной (бесконечно дифференцируемой), что дает ей преимущества в приближении гладких функций.

Принцип неопределенности Гейзенберга гласит: чем сильнее функция f(x) локализована в пространстве (т.е. чем компактнее колокол, накрывающий ее), тем шире ее спектр, т.е. Фурье-образ c(p) размазан в пространстве частот p. И наоборот: чем меньше носитель функции c(p),, тем большая часть x-пространства оккупирована f(x). С ряда точек зрения хороши функции локализованные и в x-пространстве, и в частотном спектре, что и приводит к всплескам.

Непрерывное всплеск-преобразование определяется с помощью произвольной функции y (x), имеющей конечную энергию и нулевое среднее значение, и выглядит так:

, АНАЛИЗ (2)

, СИНТЕЗ (3)

где Cy - некоторая постоянная. В квантовой механике функция называется когерентным состоянием аффинной группы. В отличие от Фурье-преобразования, в котором координата x заменяется на одну частотную переменную p, здесь x заменяется на две переменные a и b. В определенном смысле b является аналогом координаты x, а параметр a - аналогом обратной частоты 1/p, т.е. c(a,b) содержит информацию о пространственных (или временных) и частотных свойствах сигнала одновременно. Это и позволяет изучить сигнал более детально, чем с помощью Фурье-анализа.

Описание дискретного всплеск-преобразования требует более сложной математики, опирающейся на кратно-разрешающий анализ. Попробуем объяснить основные элементы последнего на простом примере. Возьмем только что построенный магазин и назовем его пол пространством Гильберта L²[a,b].. Новоявленный коммерсант имеет в распоряжении товар в виде мячей (функции f(x)) и стеллажи из полок (набор элементов базиса) с круглыми отверстиями (это как бы отдельные элементы базиса). Размеры отверстий одинаковы по горизонтали и меняются по вертикали как 2^j (j=0,+/- 1,...). Отверстия на нижних полках меньше верхних. Задача: разложить товар по полкам оптимальным способом. Решение очевидно - если мяч меньше отверстия, то он провалится до подходящей полки. Ниже его класть уже неэкономно, т.к. это потребует более материалоемких полок. Процедура такой ситообразной раскладки и называется кратно-разрешающим анализом. Глядя в бинокль, микроскоп или кинокамеру и пытаясь уловить максимально четкое и крупное изображение интересующих объектов, и во многих других случаях наблюдатель, не сознавая этого, проводит подобный анализ, и даже удивительно, почему он так долго не был математически аксиомизирован.

Формально он звучит следующим образом. Разобъем пространство Гильберта L² на совокупность вложенных друг в друга подпространств (полок) ...V_{-1 с}V_{0 с} V_{1 с} ..., таких что самое полное пространство V0-0 и есть L² (основание магазина), а V_-0-0 =0 (нет товара, который удержался бы на самой верхней полке). Наложим два основных требования на эту разбивку: 1) если f(x) с-V_j, то f(2x) с-V_j+1 (процедура перекладывания мяча на ближайшую нижнюю полку при уменьшении его диаметра в два раза); 2) в подпространстве V₀ существует такая функция f (x), что ее трансляции f (x-k), k=0,+/-1,+/- 2,... образуют базис V₀ (требование, чтобы полки заполняли по горизонтали все доступное пространство без пропусков и перекрытий). Этот простой набор предпосылок достаточен для построения полной теории всплесков.

Из взятых аксиом следует, что функции базиса V₁ получаются из базиса V₀ , f (x-k), простым двухкратным сжатием его элементов, f (2x-k). Так как любой элемент из V₀ принадлежит и V₁ , то, следовательно, f (x) можно разложить в сумму f (2x-k)

, (4)

где h_k - некоторые коэффициенты. Это функциональное уравнение самоподобия или скейлинговое уравнение и является "уравнением колебаний" для дискретного всплеск-преобразования.

Его формальное решение конечной энергии легко находится в виде интеграла Фурье, но анализ свойств возникающих функций далеко не прост. Разные типы всплесков появляются при наложении разных дополнительных ограничений на f (x). В случае Хаара-Добеши число коэффициентов h_k конечно, а скейлинговые функции f (x) имеют компактный носитель (т.е. конечную длину). Они самоподобны в том смысле, что конечная комбинация сжатых в два раза и сдвинутых на целые числа относительно друг друга функций f (2x-k) равна начальной функции f (x). Простейший пример - уравнение f (x)=f (2x)+f (2x-1) имеет решение в виде ступеньки: f (x)=1 для 0<= x<1 и f (x)=0 для остальных x. Отметим, что в случае up-функции и подобных ей, на левую часть уравнения (4) должен действовать дифференциальный оператор с постоянными коэффициентами.

Где же спрятаны сами всплески? В разложении пространства V₁ на две части: V₀ и всего остального, что не входит в него - W₀. Формально это записывается так: V₁= V₀₊ W₀. Элементы базиса этого дополняющего подпространства W₀ и называются всплесками. Так как они принадлежат V₁, их тоже можно разложить по функциям f (2x-k). Оказывается, что это разложение имеет вид

.

Упомянутая ступенчатая функция порождает всплеск Хаара: y_H(x)=f (2x)-f (2x-1), имеющий форму изломанной ступеньки, y _H(x)=1 для 0<= x<1/2,y_H(x)=-1 для 1/2<= x<1, и y_H(x)=0 для остальных x. Сам полный ортонормированный базис всплесков имеет вид

y_jk=2^j/2y (2^jx-k), j,k=0,+/- 1,+/- 2,...

Он нумеруется не одним, а двумя индексами j и k. Кажется, что число функций в этом базисе в четыре раза больше, чем в записи (1), т.к. в последнем фигурируют только положительные целочисленные индексы. На самом деле их ровно столько же, просто использована другая нумерация бесконечной последовательности чисел. Всплески Добеши D_2n(x) определяются 2n ненулевыми действительными коэффициентами в скейлинговом уравнении, такими, что при фиксированном n зануляется максимальное число моментов , m=0,1,...,M.

При n=1 имеем M=0 и D₂(x)=y _H(x)

В заключение этого пункта упомянем, что в теории дискретных Фурье-преобразований хорошо известны быстрые алгоритмы (FFT), позволяющие проводить необходимые алгебраические операции при минимальном расходе компьютерных ресурсов. В теории всплесков были найдены аналоги таких преобразований, которые оказались даже быстрее чем FFT.

Типы всплесков (самолет, вертолет, волнолет...)

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

• сплайны (как частный случай, соответствующий полиномиальным на интервалах решениям скейлингового уравнения);
• всплески Мейера (некомпактны, но бесконечно дифференцируемы);
• койфлеты (дополнительные ограничения на всплески типа Добеши);
• всплески Баттла-Лемарье (строятся на основе сплайнов);
• базисы Вильсона (построены исходя из идей физики твердого тела);
• локальные косинусные базисы и всплески Мальвара (основаны на обобщенном преобразовании Габора с широким произволом выбора анализирующих функций для разных участков сигналов);
• всплеск-пакеты;
• биортогональные всплески (можно иметь симметричные всплески, что невозможно для случаев Добеши);
• комплексные всплески Добеши (решается скейлинговое уравнение с комплексными коэффициентами);
• мульти-всплеки, как матричные обобщения обычных всплесков (имеют несколько скейлинговых функций);
• всплески с целочисленным коэффициентом растяжения большим чем 2 (в этом случае имеется одна скейлинговая и несколько всплесковых функций);
• дробные коэффициенты растяжения (компактный носитель невозможен), и т.д.

Существует концепция реперов (фреймов) - переполненных неортогональных базисов, которые применяются вполне успешно в ряде случаев. Эти объекты хорошо известны в квантовой физике как когерентные состояния. Предложено даже отказаться от афинной группы x->ax+b и строить всплески "второго поколения", пытаясь сохранить только локальность функций базиса в обычном и частотном пространствах. Перечисленные системы изначально ориентированы на одномерные сигналы на всей оси или на интервале и, естественно, существуют их обобщения на многомерные случаи и на искривленные пространства (например, для сферы), однако здесь формализм значительно менее развит. Для описания свойств и приложений всего этого множества всплесков написана не одна книга.

Немного о приложениях (далеко ли можно улететь на волнолетах)

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

1. Распознавание речи (ниже дается описание по одной из работ С. Маеса). Физический механизм производства звука голосовыми связками определяет базовые характеристики этого класса сигналов. В рамках модуляционной модели речь представляется в виде суммы

,

где A_k(x)- мгновенная амплитуда k-й первичной гармонической компоненты речи, F _k(x)- ее мгновенная фаза, а n(x) - вклад шума и ошибок моделирования. Длительное произношение односложного звука близко к чистым музыкальным тонам, т.е. Фурье-анализ описывает оптимально этот процесс (F _k(x)=w_kx, A_k и w _k - константы). Однако в живой речи происходит быстрый переход от тона к тону, с характерными шумами, высотой голоса и т.д., что приводит к необходимости распознавания зависимости от времени x амплитуд и фаз первичных компонент и, на основе этого, определения какое слово было произнесено. Причем схема должна быть достаточно жесткой, нечуствительной к специфическим шумам, национальности или диалекту говорящего и т.д.

Для решения этой задачи было предложено изучать особенности всплеск-образа f(x), т.е. функцию c(a,b), определенную в (2). При квазинепрерывном всплеск-преобразовании используется непрерывный параметр b и дискретный набор точек a_j=2 ^ja₀. На плоскости с координатами (a,b) чистые тона имеют вид периодического горного хребта конечной ширины по параметру a и бесконечной длины по координате b. Процедура перехода от одной суммы нескольких тонов к другой выглядит как слияние или расщепление этих горных кряжей вдоль координаты a. Для упрощения вычисления всплеск-преобразования используется метод стационарной фазы, затем отбрасывается все, кроме скелетного очертания гребней этих хребтов (это устраняет зависимость результата от вида y (x). По характеру колебаний высоты отдельного хребта восстанавливается структура фаз F _k(x), а по высоте отдельного хребта находятся амплитуды A_k.

Однако эта схема чувствительна к шуму и к интерференции близких по частотам тонов. Во избежания этого приходится не ограничиваться только информацией о вершинах хребтов, а применять процедуру "синхронного сжатия" хребта в линию путем специального усреднения значений всплеск-образа c(a,b) по a около максимумов. Это дает нечуствительный к шуму механизм определения мгновенных фаз. Для определения мгновенных амплитуд применяют еще одну аналогичную оптимизационную процедуру, используя уже известную информацию о F _k(x). При этом для получения превосходных результатов отнюдь не приходится отказываться от методов и техники, разработанных независимо от всплеск-анализа.

2. Программа Марра. Структура фоточувствительных полей, образованных клетками ганглии в ретине глаза, имеют форму всплеска. Это указывает на то, что первый этап обработки изображения проходит уже в глазах. Основное предположение Марра - о кодировке контуров и краев изображений с помощью нулей всплеск-преобразования. В качестве анализирующей функции было предложено использовать вторую производную от гауссовой функции двух переменных, имеющую форму мексиканской шляпы (всплеск Марра). Максимально полная реализация этой программы достигается в рамках комплексных всплесков Добеши. Приложения этой программы очевидны, т.к. создание эффективного искусственного глаза не нуждается в рекламе. Проблема распознавания образов хотя и аналогична проблеме распознавания речи, но значительно сложнее ее из-за большего объема информации записанного в объемном изображении по сравнению с аудио сигналом (при стереозвуке, однако, ситуация повторяется).

3. Физика - относительно мало прямых приложений (основная часть, из известных автору, была предложены А. Арнеодо с сотрудниками). Турбулентность - строгие результаты по гипотезе мультифрактальности Фриша-Паризи. Анализ фрактальных свойств ДНК человека - подтверждение наличия корреляций в интронных (некодирующих) последовательностях нуклеотидов, в кодирующих последовательностях расположение нуклеотидов аналогично случайному броуновскому блужданию. Анализ динамики роста фрактальных структур, шершавых поверхностей, облаков, обработка сейсмических сигналов и данных атмосферных событий. Подчеркнем также, что общая процедура перенормировок и ренормализационная группа составляют один из базовых элементов квантовой теории поля и, поэтому, применение всплесков в строгом подходе к решетчатым моделям, найденное еще в 1986 г., неудивительно.

4. Математика - мощный прорыв в развитии гармонического анализа. Характеризация большого класса функциональных пространств через простые ограничения на коэффициенты разложения по всплескам, построение оптимальных базисов для них; анализ функции Римана - решение старой проблемы и значительное продвижение вперед в описании спектра сингулярностей; эффективная характеризация сильно осциллирующих сигналов (чириканье птиц (chirps), излучение гравитационных волн при коллапсе и проч.), выделение этих сигналов на фоне других и т.д. В численныом анализе - большой прогресс в решении дифференциальных уравнений в частных производных и интегральных уравнений. Cтатистика - важный новый способ устранения шумов специфического типа, достигающийся разложением сигнала в ряд по всплескам и отбрасыванием энергетически несущественных коэффициентов. Предсказание - всплески будут важны в теории чисел. Это уже имеет место через анализ функции Римана (старые работы Харди-Литтлвуда и новые Джаффара и Мейера) и квазикристаллические всплески, но нужны более широкие приложения.

Самоподобные системы и всплески на квазикристаллах

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

Прежде всего это фракталы. Линия одномерна, плоскость двумерна, любая объемная фигура - трехмерна. А какова размерность пыли на забытой книге ? Пытаясь ответить на этот вопрос можно придти к системам, чья размерность будет измеряться нецелым числом - к фракталам. Таково было начальное определение фракталов, данное Мандельбротом. Позднее выяснилось, что есть "толстые" фракталы, у которых размерности все-таки целочисленны. Поэтому более универсальным свойством фракталов является их самоподобие - наличие некоторой масштабной симметрии. Например, это кривые, вид которых не меняется при рассмотрении в лупы определенной кратности.

Мультифракталы - "фракталы во фракталах" в том смысле, что характерный коэффициент растяжения зависит от точки, относительно которой происходит растяжка.

q-Pазностные уравнения и специальные функции построенные как их решения. Здесь возникают интересные обобщения элементарных функций, которые по ряду критериев все еще достаточно просты. Существует набор фундаментальных ``классических" требований, которые можно сохранить только на решениях q-разностных уравнений.

Остановимся подробнее на самоподобии в теории чисел: в последовательностях цифр, в алгебраических уравнениях, в цепных дробях и т.д. Например, ``золотое сечение" t ==1,618 определяется как решение (большее чем 1) простейшего квадратичного уравнения t ²=t +1, которое и является "уравнением самоподобия". Переписав его в виде 1=1/t + 1/t², мы видим, что оно определяет разбиение отрезка единичной длины на два с длинами 1/t и 1/t ², пропорциональное отношение которых и есть t . Такое сечение отрезка называется золотым, т.к. оно встречается в большом количестве случаев и считается эстетически наиболее оптимальным. С этим числом связана последовательность целых чисел Фибоначчи 1, 1, 2, 3, 5, 8, 13, 21, ..., часто встречающаяся в Природе. Она порождена рекуррентным соотношением F_n+2=F_n+1+F_n с начальными условиями F₁=F₂=1. Для больших n, .

Число t является представителем специального класса иррациональных чисел, называемых алгебраческими целыми. Последние определяются как корни алгебраических уравнений xⁿ+a_n-1x^n-1+...+a₀=0, где все a_k - целые числа. Дробные числа не входят в этот класс и с некоторых точек зрения они обладают более сложными свойствами, чем алгебраические целые.

Золотому сечению посвящено много статей и книг. Для демонстрации его красоты обычно приводят ряд простых построений из геометрии, различные субъективные эстетические и философские аргументы. Иногда вспоминают, что его разложение в цепную дробь состоит только из единиц. Однако автор не видел в популярной литературе описания трех основных характеристик, демонстрирующих абсолютную уникальность и истинную красоту t в мире чисел. Во-первых, t входит в определение конечных групп Кокстера H₂, H₃, H₄, которые напрямую связаны с квазикристаллами, содержащими локальные оси симметрии 5 и 10-го порядков или икосаэдрические структуры. Хотя H₂ и имеет обобщение на правильные многоугольники на плоскости, ассоциированные с другими иррациональными числами, никаких других аналогов групп H₃, H₄ нет. Во-вторых, t есть минимальное число, около которого скапливается бесконечное количество чисел Пизо - важного подкласса алгебраических целых больше единицы, для которых другие решения определяющего уравнения лежат внутри единичного круга на комплексной плоскости. В-третьих, t есть минимальный представитель подкласса чисел Пизо, для которых все корни определяющего алгебраического уравнения действительны. Перечисленные свойства раскрывают глубокую симметрию, заложенную в t , и дают законное право этому числу оказаться характерной шкалой растяжения для процессов идущих по самоподобной схеме в силу каких-либо внешних условий.

В работе S. Lacey, R. Box, ``A Fast Easy Sort", BYTE (April 1991) стр. 315 описана сортировка по самоподобной схеме. Суть ее в том, что при упорядочении большого списка каких-либо предметов, отличающихся одной характеристикой (например, весом), необходимо проводить сравнение и перестановку (если пара неупорядочена) не ближайших соседей, а предметов отстояших друг от друга на расстоянии L/b<sup>j</sup>, где L - общее число предметов, а j=1,2,... - порядковый номер просмотра списка. Самоподобность этой схемы очевидна. Максимально быстрая сортировка достигается при b" 1,3. Например, при b =1,15 растет общее число проводимых сравнений, а при b =1,45 появляется чувствительность к структуре списков и антиупорядоченные списки сортируются слишком долго. В виду соревновательного характера процесса и привкуса квазикристаллографии в этой схеме, можно предположить, что оптимальный фактор b равен единственному действительному корню кубического уравнения b <sup>3</sup>=b +1, определяющему минимальное число Пизо в Природе. Самое маленькое целое число большее 1 равно 2, оно тоже занимает выделенное положение с точки зрения чисел Пизо - это первая точка, около которой находится бесконечно много точек накопления чисел Пизо! Все перечисленное указывает, что b = 1,3, t =1,62 и 2 должны быть выделенными масштабирующими факторами самоподобных систем. При этом надо учитывать, что самоподобие может иметь место не только в физическом, но и в ``информационном пространстве", описывающем свойства системы (распределения вероятностей, оптимальную упаковку информации, и т.п.).

В чем состоит самоподобие кристаллов и квазикристаллов ? В том, что есть такие точки в пространстве, относительно которых при увеличении расстояния до любой другой точки решетки в q (не обязательно целое число) раз, попадаешь опять в точку решетки, а не мимо нее. Алгебраические целые специального типа (числа Пизо, Салема, бета-числа) играют важную роль для построения квазикристаллов. Среди важных общих характеристик таких систем укажем свойство Б. Делоне - атомы не могут находиться произвольно близко друг к другу и, наоборот, нет слишком больших пустот, и свойство И. Мейера (того же самого, его ранние работы по гармоническому анализу оказались по сути теорией определенного класса квазикристаллов) - вспомогательная решетка, построенная из векторов соединяющих произвольные атомы, отличается от начальной решетки только на конечное число заданных векторов. Помимо пентагональных и декагональных квазикристаллов с осями симметрии 5-го и 10-го порядка, самоподобных относительно растяжений в раз, были найдены структуры с осями 8-го и 12-го порядков. В определенных точках эти квазикристаллы как бы инвариантны относительно поворотов на углы 2П/8 и 2П /12. Для них коэффициентами растяжения самоподобия служат числа Пизо и соответственно. Отметим, что периодические решетки допускают только оси симметрии 2, 3, 4 и 6-го порядков.

Наконец, самоподобные системы десятилетия - всплески. Обычные всплески с диадическим, целочисленным или дробным коэффициентами растяжки построены на кристаллических решетках. На линии - это просто решетка целых чисел, но в высших размерностях появляются существенно более сложные конструкции. Недавно были построены простейшие всплески - аналоги всплесков Хаара - на простейших квазикристаллах (Ж.-П. Газо, И. Патера и автор, 1995). Коэффициент растяжения для них принадлежит специальному классу алгебраических целых, называемых бета-числами, к которым относятся и числа Пизо. Область применения таких всплесков пока неясна.

Решетка целых чисел строится по школьной схеме - надо отложить на числовой оси все точки, координаты которых задаются разложениями в десятичной системе исчисления без дробной части, например, 13=1* 10¹+3* 10⁰ и т.д. Вместо 10 в роли базы может выступать любое другое целое число - это даст тот же результат. Если в качестве базы взять комплексное число с целыми действительной и мнимой частями, это приведет к периодическим решеткам на плоскости.

Для того, чтобы получить квазипериодические решетки на линии, характерные квазикристаллам, надо откладывать на числовой оси точки соответствующие ``целым частям" в системе исчислений c иррациональной базой. Например, положительные "t -целые", определяющие решетку Фибоначчи, задаются суммой a_nt ⁿ+...+a_1t +a₀, где a_k равно либо нулю либо единице, но два соседних коэффициента a_k и a_k+1 не могут быть одновременно равны единице. Аналогичная конструкция существует и для точек на плоскости.

Аналог всплеска Хаара для золотого сечения определяется как несимметрично изломанная ступенька: для 0<= x <1/t , при 1/t <= x <1 и psi t =0 для остальных x. Ортонормированный базис всплесков имеет вид t ^{j/2psi t} (t^jx-b_k), где b_k - некоторая подрешетка t -целых чисел.

Квазикристаллы - очень интересные объекты не только для физики твердого тела. Задолго до их экспериментального открытия, они интенсивно обсуждались в теории машин Тьюринга с точки зрения классификации алгоритмов построения паркетов по типам сложности. Так Хао Ванг поставил проблему: найти алгоритм определения покрывается ли плоскость без пробелов и перекрытий копиями данного конечного набора различных паркетин. Он же показал, что эта проблема решаема машиной Тьюринга, если плоскость замощается набором паркетин периодическим образом. Однако его ученик Р. Бержер доказал, что в общем случае проблема неразрешима, т.е. не существует алгоритма, который за конечное число шагов ответит на поставленный вопрос. При этом он построил пример набора паркетин, которые замощают плоскость, но только непериодическим образом. Первоначально такие паркеты были составлены из огромного количества независимых элементов. Постепенно это число уменьшалось и в 1974 г. Р. Пенроуз предложил свои знаменитые примеры, составленные всего из двух элементов - ромбов с ребрами одинаковой длины и углами раствора П /5 и 2П /5. Эти две фигуры покрывают плоскость только квазипериодическим образом.

Почему же компьютер не может решить проблему распознания таких структур, а человек справляется с нею ? Считается, что дело в теореме о неполноте любой достаточно богатой формальной системы аксиом (например, аксиом арифметики), доказанной К. Геделем в тридцатых годах. Эта теорема допускает наличие правильных утверждений, которые не могут быть доказаны на основе взятых аксиом. Проблема с машиной Тьюринга в том, что она не выходит за рамки предложенного алгоритма и ряд утверждений ей не по плечу. Как работает сознание человека неизвестно, но сам факт доказательства теоремы Геделя предполагает, что существует принципиальное отличие от схемы в машине Тьюринга.

Заключение, Эпилог и Послесловие

Теория всплесков не является фундаментальной физической теорией, но она дает удобный инструмент для решения многих практических задач. Если называть гладкие функции ``хорошими", то Фурье-методы позволяют экономно раскладывать хорошие функции по базису хороших функций, а всплески позволяют экономно раскладывать ``плохие" функции (в смысле негладких, скачкообразных, читай, фрактальных) по базису плохих функций. Если отбросить вопросы удобства представления и интерпретации, то эти способы записи сигналов эквивалентны.

Мнение, что всплески позволяют раскрыть внутреннюю природу сигнала, является достаточно распространенным. Однако это верно лишь отчасти. По мнению ряда физиков, работающих со всплеск-анализом, простым ``прикладыванием" соответствующих формул серьезную задачу не решить - надо быть экспертом в самой проблеме, проработать с ней не один год и уметь отличать внутренние свойства объекта от артефактов, порожденных спецификой использованного метода анализа. А так совершенно неважно с помощью какой техники решается взятая задача - лишь бы решалась.

В настоящее постреволюционное время изыскание финансирования научных исследований в России в значительной степени дело самих исследователей. В области фундаментальных наук, к которым относится и математический аппарат теории всплесков, важную роль играет Российский Фонд Фундаментальных Исследований, действующий уже пять лет и финансирующий научные проекты отобранные на конкурсной основе. Так, пользуясь случаем, автор хотел бы выразить благодарность этому фонду за частичную поддержку его исследований в этой области в рамках гранта РФФИ 97-01-00281.

Автор признателен так же В.В. Алексеенко за просмотр рукописи и конструктивную критику, Г. Башилову за стимулирующее предложение написать статью для Computerra о всплесках (нечто подобное получившейся работе задумывалось еще два года назад, но исполнение постоянно отодвигалось в будущее), В.Б. Приезжеву за обсуждение самоподобных систем, Ю.А. Фаркову за указание на ряд неточностей по математической терминологии, Б.Б. Хаббард за сообщение некоторых деталей из ее книги о всплесках.

В обзоре частично использовались результаты открытой дискуссии по приложениям всплесков, проводившейся автором на конференции ``Всплески и физика" (Монреаль, март 1996 г.). Все недостатки данной статьи целиком и полностью лежат на математически настроенном физике, написавшем ее.

Некоторые литературные источники.

К сожалению, в отечественной литературе нет адекватного отражения теории всплесков, в частности нет переводов базовых книг И. Добеши (1992) и И. Мейера (1990), содержащих полное изложение математического аппарата.

Педагогическое сравнение Фурье и всплеск анализов в теории сигналов: J.S. Walker, Fourier analysis and wavelet analysis, Notices of Amer. Math. Soc., 44 (6), (1997) 658.

Хороший математический обзор: R.A. DeVore, B.J. Lucier, Wavelets, Acta Numerica (ed. A. Iserles), Cambridge, 1992.

Удачно статус всплесков на 1995 г. отражен в короткой заметке W. Sweldens, Wavelets: What Next, Proc. IEEE, 84 (1996). 680. Анализ временных метеорологических рядов: Н.М. Астафьева, Вейвлет-анализ: основы теории и примеры применения, Успехи Физических Наук, 166 (11), (1996) 1145.

Примеры компрессии изображений: A. Grossmann et B. Torresani, Les ondelettes, http://cptsx1.univ-mrs.fr/~torresan/universalis/ondel.html.

Современная история всплесков со множеством куръезных фактов изложена в книге B.B. Hubbard, The World According to Wavelets, AK Peters Ltd., Wellesley, MA, 1996.

Некоторые cамоподобные системы (без всплесков) обсуждаются в легко читаемой книге M. Schroeder, ``Fractals, Chaos, Power Laws", W.H. Freeman and Company, 1991.

Только что появилась новая книга об анализе самоподобных функций с помощью теории всплесков Y. Meyer, Wavelets, vibrations and scalings, CRM monograph series, v. 9, AMS, 1998.

Детальное обсуждение квазикристаллов, теоремы Геделя, машины Тьюринга и многих других понятий: R. Penrose, Shadows of the Mind, Oxford University Press, 1994.

Красивые изображения квазикристаллов легко найти в WWW-мире.