Диадическая трансформация

xy plot, где x  =  x ₀  ∈ [0, 1] рационально, а y  =  x _n для всех  n .

Двоично - преобразование (также известное как диадическая карта , битовый сдвиг карта , 2 х  моды 1 карта , Бернулли карта , удваивая карту или карту пилообразной ^{[1] [2]} ) является отображением (то есть, рекуррентное соотношение )

${\ Displaystyle T: [0,1) \ к [0,1) ^ {\ infty}}$

${\ Displaystyle х \ mapsto (x_ {0}, x_ {1}, x_ {2}, \ ldots)}$

производится по правилу

${\ displaystyle x_ {0} = x}$

${\ Displaystyle \ forall п \ geq 0, x_ {n + 1} = (2x_ {n}) {\ bmod {1}}}$. ^[3]

Эквивалентно, диадическое преобразование также может быть определено как итерированное отображение функции кусочно-линейной функции

${\ displaystyle T (x) = {\ begin {cases} 2x & 0 \ leq x <{\ frac {1} {2}} \\ 2x-1 & {\ frac {1} {2}} \ leq x <1. \ end {case}}}$

Карта сдвига битов имени возникает потому, что, если значение итерации записано в двоичной системе счисления, следующая итерация получается путем сдвига двоичной точки на один бит вправо, и если бит слева от новой двоичной точки является "один", заменив его нулем.

Диадическое преобразование представляет собой пример того, как простая одномерная карта может вызвать хаос . Эта карта легко обобщается на несколько других. Важным из них является бета-преобразование , определяемое как . Эта карта была тщательно изучена многими авторами. Он был введен Альфредом Реньи в 1957 году, а инвариантная мера для него была дана Александром Гельфондом в 1959 году и снова независимо Биллом Парри в 1960 году. ^{[4] [5] [6]}${\ Displaystyle Т _ {\ бета} (х) = \ бета х {\ bmod {1}}}$

Связь с процессом Бернулли [ править ]

Отображение T  : [0,1) → [0,1) сохраняет меру Лебега .${\ Displaystyle х \ mapsto 2x {\ bmod {1}}}$

Отображение может быть получено как гомоморфизм на процессе Бернулли . Позвольте быть набор всех полубесконечных строк букв и . Это можно понять как подбрасывание монеты, выпад орла или решки. Точно так же можно записать пространство всех (полубесконечных) строк двоичных битов. Слово «бесконечный» квалифицируется как «полу-», так как можно также определить другое пространство, состоящее из всех двойных бесконечных (двусторонних) строк; это приведет к карте Бейкера . Квалификация «полу-» опускается ниже. ${\displaystyle \Omega =\{H,T\}^{\mathbb {N} }}$${\displaystyle H}$${\displaystyle T}$${\displaystyle \Omega =\{0,1\}^{\mathbb {N} }}$${\displaystyle \{0,1\}^{\mathbb {Z} }}$

Это пространство имеет естественную операцию сдвига , задаваемую

${\displaystyle T(b_{0},b_{1},b_{2},\cdots )=(b_{1},b_{2},\cdots )}$

где - бесконечная строка двоичных цифр. Учитывая такую ​​строку, напишите${\displaystyle b_{0},b_{1},\cdots }$

${\displaystyle x=\sum _{n=0}^{\infty }{\frac {b_{n}}{2^{n+1}}}.}$

В результате получается действительное число в единичном интервале . Сдвиг индуцирует гомоморфизм , также называемый , на единичном интервале. Поскольку легко увидеть, что для дважды бесконечной последовательности бит индуцированный гомоморфизм является отображением Бейкера .${\displaystyle x}$${\displaystyle 0\leq x\leq 1.}$${\displaystyle T}$${\displaystyle T}$${\displaystyle T(b_{0},b_{1},b_{2},\cdots )=(b_{1},b_{2},\cdots ),}$${\displaystyle T(x)=2x{\bmod {1}}.}$${\displaystyle \Omega =2^{\mathbb {Z} },}$

Тогда диадическая последовательность - это просто последовательность

${\displaystyle x,\,T(x),\,T^{2}(x),\,T^{3}(x),\cdots }$

То есть, ${\displaystyle x_{n}=T^{n}(x)}$

Набор Кантора [ править ]

Обратите внимание, что сумма

${\displaystyle y=\sum _{n=0}^{\infty }{\frac {b_{n}}{3^{n+1}}}}$

дает функцию Кантора , как принято определять. Это одна из причин, почему набор иногда называют набором Кантора .${\displaystyle \{H,T\}^{\mathbb {N} }}$

Скорость потери информации и чувствительная зависимость от начальных условий [ править ]

Отличительной чертой хаотической динамики является потеря информации при моделировании. Если мы начнем с информации о первых s битах начальной итерации, то после m смоделированных итераций ( m  <  s ) у нас останется только ( s  -  m ) бит информации. Таким образом, мы теряем информацию со скоростью один бит за итерацию. После sитераций, наша симуляция достигла нулевой фиксированной точки, независимо от истинных значений итераций; таким образом, мы полностью потеряли информацию. Это иллюстрирует чувствительную зависимость от начальных условий - отображение из усеченного начального условия экспоненциально отклонилось от отображения от истинного начального условия. А поскольку наша симуляция достигла фиксированной точки, почти для всех начальных условий она не будет качественно правильно описывать динамику как хаотическую.

Эквивалентной концепции потери информации является концепция получения информации. На практике какой-то реальный процесс может генерировать последовательность значений { x _n } с течением времени, но мы можем наблюдать эти значения только в усеченной форме. Предположим, например, что x ₀ = 0,1001101, но мы наблюдаем только усеченное значение 0,1001. Наш прогноз для x ₁ равен 0,001. Если мы подождем, пока реальный процесс не сгенерирует истинное значение x ₁ 0,001101, мы сможем наблюдать усеченное значение 0,0011, которое более точно, чем наше предсказанное значение 0,001. Итак, мы получили выигрыш в информации в один бит.

Связь с картой палатки и логистической картой [ править ]

Диадическое преобразование топологически полусопряжено с картой палатки единичной высоты . Напомним, что карта палатки с единичной высотой имеет вид

${\displaystyle x_{n+1}=f_{1}(x_{n})={\begin{cases}x_{n}&\mathrm {for} ~~x_{n}<1/2\\(1-x_{n})&\mathrm {for} ~~1/2\leq x_{n}\end{cases}}}$

Сопряжение явно задается формулой

${\displaystyle S(x)=\sin \pi x}$

так что

${\displaystyle f_{1}=S^{-1}\circ T\circ S}$

То есть, это стабильно при итерациях, так как${\displaystyle f_{1}(x)=S^{-1}(T(S(x))).}$

${\displaystyle f_{1}^{n}=f_{1}\circ \cdots \circ f_{1}=S^{-1}\circ T\circ S\circ S^{-1}\circ \cdots \circ T\circ S=S^{-1}\circ T^{n}\circ S}$

Он также сопряжен с хаотическим  случаем r = 4 логистической карты . Г  = 4 случай логистического отображения является ; это связано с картой сдвига бит в переменной x следующим образом:${\displaystyle z_{n+1}=4z_{n}(1-z_{n})}$

${\displaystyle z_{n}=\sin ^{2}(2\pi x_{n}).}$

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

${\displaystyle \theta \mapsto 2\theta {\bmod {2}}\pi .}$

Периодичность и непериодичность [ править ]

Из-за простой природы динамики, когда итерации рассматриваются в двоичной системе счисления, легко классифицировать динамику на основе начального условия:

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

Если х ₀ является рационально образ х ₀ содержит конечное число различных значений в пределах [0, 1) и вперед орбиту из х ₀ в конечном счете периодическим с периодом , равным периоду двоичного разложения х ₀ . В частности, если начальным условием является рациональное число с конечным двоичным расширением k битов, то после k итераций итерации достигают фиксированной точки 0; если начальное условие - рациональное число с k- битным переходным процессом ( k  ≥ 0), за которым следует q- битная последовательность (q  > 1), который повторяется бесконечно, то после k итераций итерации достигают цикла длины  q . Таким образом, возможны циклы любой длины.

Например, прямая орбита 24 ноября:

${\displaystyle {\frac {11}{24}}\mapsto {\frac {11}{12}}\mapsto {\frac {5}{6}}\mapsto {\frac {2}{3}}\mapsto {\frac {1}{3}}\mapsto {\frac {2}{3}}\mapsto {\frac {1}{3}}\mapsto \cdots ,}$

который достиг цикла периода 2. В пределах любого подинтервала [0,1), независимо от того, насколько они малы, следовательно, существует бесконечное количество точек, орбиты которых в конечном итоге периодичны, и бесконечное количество точек, орбиты которых никогда не бывают периодический. Эта чувствительная зависимость от начальных условий характерна для хаотических карт .

Периодичность через битовые сдвиги [ править ]

Периодические и непериодические орбиты можно легче понять, работая не с картой напрямую, а с картой битового сдвига, определенной в пространстве Кантора .${\displaystyle T(x)=2x{\bmod {1}}}$${\displaystyle T(b_{0},b_{1},b_{2},\cdots )=b_{1},b_{2},\cdots }$ ${\displaystyle \Omega =\{0,1\}^{\mathbb {N} }}$

То есть гомоморфизм

${\displaystyle x=\sum _{n=0}^{\infty }{\frac {b_{n}}{2^{n+1}}}}$

это в основном утверждение, что набор Кантора может быть отображен в вещественные числа. Это сюръекция: каждое диадическое рациональное представление имеет не одно, а два различных представления в канторовом множестве. Например,

${\displaystyle 0.1000000\cdots =0.011111\cdots }$

Это просто двоичная версия известной проблемы 0.999 ... = 1 . Удвоенное представление справедливо в общем случае : для любой заданной конечной длиной исходной последовательности длины , один имеет${\displaystyle b_{0},b_{1},b_{2},\cdots ,b_{k-1}}$${\displaystyle k}$

${\displaystyle b_{0},b_{1},b_{2},\cdots ,b_{k-1},1,0,0,0,\cdots =b_{0},b_{1},b_{2},\cdots ,b_{k-1},0,1,1,1,\cdots }$

Начальная последовательность соответствует непериодической части орбиты, после чего итерация устанавливается на все нули (то есть все единицы).${\displaystyle b_{0},b_{1},b_{2},\cdots ,b_{k-1}}$

Выраженные в виде битовых строк, периодические орбиты карты могут быть рассмотрены рациональными числами. То есть после начальной "хаотической" последовательности периодическая орбита превращается в повторяющуюся строку длины . Нетрудно увидеть, что такие повторяющиеся последовательности соответствуют рациональным числам. Письмо${\displaystyle b_{0},b_{1},b_{2},\cdots ,b_{k-1}}$${\displaystyle b_{k},b_{k+1},b_{k+2},\cdots ,b_{k+m-1}}$${\displaystyle m}$

${\displaystyle y=\sum _{j=0}^{m-1}b_{k+j}2^{-j-1}}$

тогда очевидно, что

${\displaystyle \sum _{j=0}^{\infty }b_{k+j}2^{-j-1}=y\sum _{j=0}^{\infty }2^{-jm}={\frac {y}{1-2^{m}}}}$

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

Это явление заслуживает внимания, потому что нечто подобное происходит во многих хаотических системах. Например, геодезические на компактных многообразиях могут иметь периодические орбиты, которые ведут себя подобным образом.

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

Формулировка плотности [ править ]

Вместо того, чтобы смотреть на орбиты отдельных точек под действием карты, не менее целесообразно изучить, как карта влияет на плотности на единичном интервале. То есть представьте, что на единичный интервал посыпается пыль; в одних местах он плотнее, чем в других. Что происходит с этой плотностью при повторении?

Напишите как эта плотность, так что . Чтобы получить действие на эту плотность, нужно найти все точки и написать ^[7]${\displaystyle \rho :[0,1]\to \mathbb {R} }$${\displaystyle x\mapsto \rho (x)}$${\displaystyle T}$${\displaystyle y=T^{-1}(x)}$

${\displaystyle \rho (x)\mapsto \sum _{y=T^{-1}(x)}{\frac {\rho (y)}{|T^{\prime }(y)|}}}$

Знаменатель в приведенном выше является определителем Якоби преобразования, здесь это просто производная от и так далее . Кроме того, очевидно, что в прообразе есть только две точки , это и Собирая все вместе, получаем${\displaystyle T}$${\displaystyle T^{\prime }(y)=2}$${\displaystyle T^{-1}(x)}$${\displaystyle y=x/2}$${\displaystyle y=(x+1)/2.}$

${\displaystyle \rho (x)\mapsto {\frac {1}{2}}\rho \left({\frac {x}{2}}\right)+{\frac {1}{2}}\rho \left({\frac {x+1}{2}}\right)}$

Условно такие карты обозначаются так, чтобы в этом случае писать${\displaystyle {\mathcal {L}}}$

${\displaystyle \left[{\mathcal {L}}_{T}\rho \right](x)={\frac {1}{2}}\rho \left({\frac {x}{2}}\right)+{\frac {1}{2}}\rho \left({\frac {x+1}{2}}\right)}$

Карта является линейным оператором , как и (очевидно), и для всех функций на единичном интервале и для всех констант .${\displaystyle {\mathcal {L}}_{T}}$${\displaystyle {\mathcal {L}}_{T}(f+g)={\mathcal {L}}_{T}(f)+{\mathcal {L}}_{T}(g)}$${\displaystyle {\mathcal {L}}_{T}(af)=a{\mathcal {L}}_{T}(f)}$${\displaystyle f,g}$${\displaystyle a}$

С точки зрения линейного оператора наиболее очевидный и актуальный вопрос: каков его спектр ? Одно собственное значение очевидно: при условии, что оно очевидно, равномерная плотность инвариантна относительно преобразования. На самом деле это наибольшее собственное значение оператора , собственное значение Фробениуса – Перрона . По сути, равномерная плотность есть не что иное, как инвариантная мера диадического преобразования.${\displaystyle \rho (x)=1,}$${\displaystyle {\mathcal {L}}_{T}\rho =\rho }$${\displaystyle {\mathcal {L}}_{T}}$

Чтобы изучить спектр более подробно, нужно сначала ограничиться подходящим пространством функций (на единичном интервале) для работы. Это может быть пространство функций , измеримых по Лесбегу , или, возможно, пространство функций, интегрируемых с квадратом , или, возможно, даже просто многочлены . Работать с любым из этих пространств на удивление сложно, хотя спектр можно получить. ^[7]${\displaystyle {\mathcal {L}}_{T}}$

Борельское пространство [ править ]

Если вместо этого работать с пространством Кантора и функциями, возникает огромное количество упрощений. Рекомендуется соблюдать некоторую осторожность, так как карта определяется на единичном интервале линии действительного числа , предполагая естественную топологию на вещественных числах. Напротив, карта определена в пространстве Кантора , которому по соглашению дается совсем другая топология, топология продукта . Существует потенциальное столкновение топологий; нужно соблюдать некоторую осторожность. Однако, как показано выше, существует гоморфизм множества Кантора в действительные числа; к счастью, он отображает открытые множества в открытые и, таким образом, сохраняет понятие непрерывности.${\displaystyle \Omega =\{0,1\}^{\mathbb {N} }}$${\displaystyle \rho :\Omega \to \mathbb {R} .}$${\displaystyle T(x)=2x{\bmod {1}}}$${\displaystyle T(b_{0},b_{1},b_{2},\cdots )=b_{1},b_{2},\cdots }$ ${\displaystyle \Omega =\{0,1\}^{\mathbb {N} }}$

Чтобы работать с множеством Кантора , необходимо предоставить для него топологию; по соглашению это топология продукта . Путем присоединения дополнительных множеств его можно расширить до борелевского пространства , то есть до сигма-алгебры . Топология - это цилиндрические наборы . Набор цилиндров имеет общий вид${\displaystyle \Omega =\{0,1\}^{\mathbb {N} }}$

${\displaystyle (*,*,*,\cdots ,*,b_{k},b_{k+1},*,\cdots ,*,b_{m},*,\cdots )}$

где битовые значения "безразлично", а конечное число явно определенных битовых значений, разбросанных в бесконечной строке безразличных битов. Это открытые наборы топологии. Каноническая мера на этом пространстве - это мера Бернулли для справедливого подбрасывания монеты. Если в строке безразличных позиций указан только один бит, размер равен 1/2. Если указаны два бита, размер равен 1/4 и так далее. Можно придумать: имея действительное число, можно определить меру${\displaystyle *}$${\displaystyle b_{k},b_{m},\cdots }$${\displaystyle 0<p<1}$

${\displaystyle \mu _{p}(*,\cdots ,*,b_{k},*,\cdots )=p^{n}(1-p)^{m}}$

если в последовательности есть орел и решка. Мера с предпочтительнее, так как она сохраняется на карте${\displaystyle n}$${\displaystyle m}$${\displaystyle p=1/2}$

${\displaystyle b_{0},b_{1},b_{2},\cdots \mapsto x=\sum _{n=0}^{\infty }{\frac {b_{n}}{2^{n+1}}}.}$

Так, например, отображается в интервал и отображается в интервал, и оба этих интервала имеют меру 1/2. Точно так же отображается на интервал, который все еще имеет меру 1/2. То есть приведенное выше вложение сохраняет меру.${\displaystyle (0,*,\cdots )}$${\displaystyle [0,1/2]}$${\displaystyle (1,*,\cdots )}$${\displaystyle [1/2,1]}$${\displaystyle (*,0,*,\cdots )}$${\displaystyle [0,1/4]\cup [1/2,3/4]}$

Альтернатива - написать

${\displaystyle b_{0},b_{1},b_{2},\cdots \mapsto x=\sum _{n=0}^{\infty }\left[b_{n}p^{n+1}+(1-b_{n})(1-p)^{n+1}\right]}$

который сохраняет меру. То есть отображает так, что мера на единичном интервале снова является мерой Лесбега.${\displaystyle \mu _{p}.}$

Оператор Фробениуса – Перрона [ править ]

Обозначим совокупность всех открытых множеств на множестве Кантора через и рассмотрим множество всех произвольных функций . Сдвиг вызывает прямой переход вперед.${\displaystyle {\mathcal {B}}}$${\displaystyle {\mathcal {F}}}$${\displaystyle f:{\mathcal {B}}\to \mathbb {R} .}$${\displaystyle T}$

${\displaystyle f\circ T^{-1}}$

определяется Это снова некоторая функция Таким образом, отображение индуцирует другую карту на пространстве всех функций То есть, учитывая некоторые , один определяет${\displaystyle \left(f\circ T^{-1}\right)(x)=f(T^{-1}(x)).}$${\displaystyle {\mathcal {B}}\to \mathbb {R} .}$${\displaystyle T}$${\displaystyle {\mathcal {L}}_{T}}$${\displaystyle {\mathcal {B}}\to \mathbb {R} .}$${\displaystyle f:{\mathcal {B}}\to \mathbb {R} }$

${\displaystyle {\mathcal {L}}_{T}f=f\circ T^{-1}}$

Этот линейный оператор называется передаточным оператором или оператором Рюэля – Фробениуса – Перрона . Наибольшее собственное значение - это собственное значение Фробениуса – Перрона , и в данном случае оно равно 1. Соответствующий собственный вектор является инвариантной мерой: в данном случае это мера Бернулли . Опять же, когда${\displaystyle {\mathcal {L}}_{T}(\rho )=\rho }$${\displaystyle \rho (x)=1.}$

Спектр [ править ]

Чтобы получить спектр , необходимо предоставить подходящий набор базисных функций для пространства. Один из таких вариантов - ограничиться набором всех многочленов . В этом случае оператор имеет дискретный спектр , а собственные функции (что любопытно) являются полиномами Бернулли ! ^[8] (Это совпадение названий, по-видимому, не было известно Бернулли.)${\displaystyle {\mathcal {L}}_{T}}$${\displaystyle {\mathcal {F}}.}$${\displaystyle {\mathcal {F}}}$

Действительно, легко проверить, что

${\displaystyle {\mathcal {L}}_{T}B_{n}=2^{-n}B_{n}}$

где - многочлены Бернулли . Это следует из того, что многочлены Бернулли подчиняются тождеству${\displaystyle B_{n}}$

${\displaystyle {\frac {1}{2}}B_{n}\left({\frac {y}{2}}\right)+{\frac {1}{2}}B_{n}\left({\frac {y+1}{2}}\right)=2^{-n}B_{n}(y)}$

Обратите внимание, что ${\displaystyle B_{0}(x)=1.}$

Другой базис обеспечивается базисом Хаара , а функции, охватывающие пространство, являются вейвлетами Хаара . В этом случае находится непрерывный спектр , состоящий из единичного диска на комплексной плоскости . Задано в единичном диске, так что функции${\displaystyle z\in \mathbb {C} }$${\displaystyle |z|<1}$

${\displaystyle \psi _{z,k}(x)=\sum _{n=0}^{\infty }z^{n}\exp i\pi (2k+1)2^{n}x}$

подчиниться

${\displaystyle {\mathcal {L}}_{T}\psi _{z,k}=z\psi _{z,k}}$

для целого числа Это полный базис, в котором каждое целое число может быть записано в форме . Полиномы Бернулли восстанавливаются путем установки и${\displaystyle k\in \mathbb {Z} .}$${\displaystyle (2k+1)2^{n}.}$${\displaystyle k=0}$${\displaystyle z={\frac {1}{2}},{\frac {1}{4}},\cdots }$

Полную основу можно дать и другими способами; они могут быть записаны в терминах дзета-функции Гурвица . Еще одна полная основа - это функция Такаги . Это фрактальная функция, не дифференцируемая в никуда. Собственные функции явно имеют вид

${\displaystyle {\mbox{blanc}}_{w,k}(x)=\sum _{n=0}^{\infty }w^{n}s((2k+1)2^{n}x)}$

где где - треугольная волна . Опять же${\displaystyle s(x)}$

${\displaystyle {\mathcal {L}}_{T}{\mbox{blanc}}_{w,k}=w\;{\mbox{blanc}}_{w,k}}$

Все эти различные основы могут быть выражены как линейные комбинации друг друга. В этом смысле они эквивалентны.

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

См. Также [ править ]

• Процесс Бернулли
• Схема Бернулли
• Модель Гилберта – Шеннона – Ридса , случайное распределение перестановок, заданное путем применения карты удвоения к набору из n равномерно случайных точек на единичном интервале

Примечания [ править ]

Ссылки [ править ]