Метод клеточных уравнений

Саратовский государственный технический университет имени Гагарина Ю.А.

 

 

 

 

 

 

 

 

 

 

 

Реферат

 

На тему: метод клеточных уравнений

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Выполнил: Кузьмин Д.С.

Проверил: Зоркин А.Я.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Саратов 2015

 

Математические модели типа «клеточных автоматов» в последнее время широко применя-ются для моделирования систем типа «реакция-диффузия». Кроме того, модели клеточных авто-матов применяются при моделировании процессов в нанотехнологиях, при моделировании до-рожного движения. Математические модели теории перколяции («просачивания») также можно отнести к моделям типа клеточных автоматов.

 

Рассмотрим процедуру построения подобной модели из общих соображений, а затем обсудим свойства получаемых моделей.

 

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

 

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

 

1. Заселиться может только незаселенная клетка (рефрактерные клетки не заселяются).
2. Через время t1  возбуждение клетки переходит в состояние рефрактерности.
3. Через время t2  рефрактерные клетки переходят в состояние покоя.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис. 1. «Двухрукавная спиральная волна». Момент t = 1

 

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

 

Так, при t1 ≈ t2 и начальной конфигурации, показанной на рис. 1, точка, которая сосед-ствует и с двумя возбужденными участками, и с двумя рефрактерными, будет являться центром образующейся в системе спиральной волны. (Читателю предлагается подумать, почему в системе формируется двухрукавная спиральная волна.)

 

Описанный клеточный автомат (Н. Винера и А. Розенблюта) строился из некоторых со-ображений экологического характера. Однако ему можно придать ряд истолкований, включая качественную модель распространения возбуждения в коре головного мозга или протекания ре-акции Белоусова–Жаботинского [Лоскутов, Михайлов, 1989; Ахромеева и др., 1992]. Развитие спиральной волны, возникшей при эволюции системы, в два момента времени показано на рис. 2 и 3.

 

Авторы феноменологической модели исследования реакции Белоусова–Жаботинского [Ахромеева и др., 1992; Oono, Kohomoto, 1962] предположили, что сосредоточенная (точеч-ная) модель обладает автокаталитической кинетикой, а причиной сложного пространственно-временного поведения оказываются диффузионные процессы.

• одномерном случае система разбивается на одинаковые клетки. Состояние n-й клетки

 

• момент времени t (время в данной модели, конечно, дискретно) определяется неотрицательной функцией A(n, t). Значение A(n, t + 1) определяется по предыдущему состоянию по следующим

правилам:

Предварительный этап (1) моделирует диффузию. Второй этап схематично описывает протекание химической реакции, функция F задается как

 

1, x ≥ 1, 5;

 

F (x) =   0, 0, 5 ≤ x < 1, 5; (3)

M,   x < 0, 5.

 

По  замыслу авторов,  множитель α определяет  величину  коэффициента  диффузии системы,

0 ≤ α ≤ 1.

 

Для читателей, знакомых с основами применения численных методов для решения уравне-ний в частных производных, должно быть очевидным сходство предварительного этапа (1) с яв-ной разностной схемой для решения уравнения диффузии, при этом α играет роль удвоенного параболического числа Куранта.

 

Как известно, эта схема устойчива при α ≤ 1, более того, она становится монотонной (т. е. все коэффициенты перед A(j, t) в правой части становятся неотрицательными). Таким образом, становится ясным смысл ограничения 0 ≤ α ≤ 1: значения A_(n, t) становятся неотрицательными и не могут возрастать неограниченно на каждом шаге (см. также Приложение 1).

 

При α = 0 диффузия в системе отсутствует, и правила перехода определяются уравне-нием (2), т. е. дискретным отображением. Нарисовав график итераций этого отображения, видим, что при M > 1 существует единственный устойчивый цикл периода 3:

 

0 → M → 1 → 0 → . . .

 

• зависимости от M, α в автомате (1–2) могут существовать циклы с периодом 3 (очевидно,

 

• случае малых α), волновые процессы и «турбулентные режимы» [Oono, Kohomoto, 1962]. Далее мы вернемся к двумерному обобщению данного автомата.

 

Интересно, что определение клеточного автомата является весьма общим, и в класс «кле-точных автоматов» могут быть включены и объекты, изучаемые в других разделах. В соответ-ствии с [Лоскутов, Михайлов, 1989] под клеточными автоматами понимаются сети элементов, меняющих свое состояние в последовательные дискретные моменты времени по определенному закону в зависимости от того, каким было состояние рассматриваемого элемента и его соседей

 

• предыдущий дискретный момент времени.

 

Под соседями для элемента j, в свою очередь, понимаются фиксировано заданные элементы некоего множества θ(j).

 

Для клеточного автомата определяется закон перехода

для детерминированного автомата или функция вероятности перехода элемента

 

 

Здесь W  — вероятность перехода j-го элемента из состояния a(j, t)

в момент времени t

 

состояние a(j, t + 1) в следующий момент времени при определенных состояниях соседей. Такие клеточные автоматы называются вероятностными.

 

Конечно, наибольший интерес представляют не переименованные в «автоматы» числен-ные аппроксимации, а прямые модели, предпочтительно точно решаемые в целых числах. Так,

 

• [Тоффоли, Марголус, 1991] приведено описание «чисто аналогового» клеточного автомата (на треугольной или гексагональной решетке), являющегося прямой имитацией плоских движений жидкости. Модель позволяет получить гидродинамические течения (при не слишком больших числах Маха) без решения уравнений Навье-Стокса.

 

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

 

Среди всех возможных классов клеточных автоматов большинство результатов получено для одномерных так называемых правильных суммирующих автоматов.

Автомат называется правильным, если для него выполнено следующее условие:

 

F (A(n − r, t), . . . , A(n + r, t)) = F (A(n + r, t), . . . , A(n − r, t)

Кроме того, если F (0, 0, . . . , 0) = 0, то автомат называется законным. Если

По классификации С. Вольфрама [Wolfram, 2002] одномерные и двумерные правильные суммирующие автоматы делятся по своему поведению на четыре класса.

 

Класс 1. За конечное число шагов автоматы достигают пространственно-однородного состояния. Конечное состояние не зависит от времени и от начальных условий.

 

ПРИМЕР 1. Рассмотрим следующий клеточный автомат: каждый элемент может находиться в двух состояниях: 0 и 1. Правила перехода имеют вид:

 

1,   A(n − 1, t) + A(n, t) + A(n + 1, t) = 3;

A(n, t + 1) =

0,   A(n − 1, t) + A(n, t) + A(n + 1, t)    3.

 

 

Класс 2. Автомат генерирует локализованные структуры, стационарные или периодиче-ские по времени.

 

ПРИМЕР 2. Как и в примере 1, считаем, что каждый элемент сети может находиться в двух состояниях: 0 и 1.

Класс 3. Автомат из этого класса порождает непериодические конфигурации клеток, «за-бывая» при этом о начальных условиях, — обладает так называемым «турбулентным» пере-мешиванием. Примеры автоматов такого класса приведены ниже, в параграфе, посвященном модификации клеточного автомата «игра „Жизнь“».

 

Класс 4. Динамика клеточного автомата существенно зависит от начальных данных. Под-бирая начальные условия, можно группировать самые различные последовательности сменяю-щих друг друга состояний. Известно несколько «кандидатов» на роль автомата класса 4, твердо установлено, что таким автоматом является игра Дж. Конвея «Жизнь».

Игра Дж. Конвея «Жизнь» и двумерный клеточный автомат У. Ооно–М. Кохомото

 

Игра «Жизнь» была предложена в 1970 г. Дж. Конвеем в качестве математического развле-чения. В настоящее время достаточно велик интерес математиков к этой игре: доказано, что она является клеточным автоматом класса 4. Согласно существующим гипотезам, автоматы данного класса могут осуществлять универсальные вычисления, подобно машине Тьюринга [Тоффоли, Марголус, 1991], и применяться при моделировании развития турбулентности и возникновения диссипативных систем в экологии, биологии, экономике и т. д.

 

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

 

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

 

Правила перехода для каждого элемента крайне просты: элемент aij может находиться в со-стоянии покоя (0) или активности (1). Из состояния покоя в активное в следующем поколении элемент переходит, если рядом с ним в текущем поколении оказалось ровно три активных эле-мента. Состояние активности сохраняется, если среди ближайших соседей находятся два или три активных элемента. Правила перехода на следующий слой могут быть записаны в канонической форме B3/S2,3.

 

В первой части записи правила послойного перехода (B от слова Born — рождение) указы-вается то число соседей в окрестности Мура, при котором происходит рождение новой клетки. S (save) — число соседей, при котором клетка остается активной.

 

Динамика автомата «Жизнь» не является хаотической, а скорее «регулярна». В нем воз-можны локализованные циклы (конфигурации «мельница» или «семафор»), движущиеся кон-фигурации — «планеры». Существуют также и различные динамические структуры (например, в случае «столкновения» «планера» с «мельницей») и «неэлементарные» начальные конфигу-рации типа «паровоза» и «ружья», «стреляющего» «планерами». Описание эволюции таких структур приведено, например, в [Ахромеева и др., 1992].

 

Простейшими являются стационарные, то есть не зависящие от времени, структуры. Их примеры показаны на рис. 4

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис. 4. Стационарные структуры в игре «Жизнь». Структура в верхнем левом углу состоит из четырех клеток

 

С помощью этих стационарных структур можно получить множество других. В самом деле, если мы имеем такую структуру, то конфигурация, полученная поворотом на 90◦, также является стационарной. Четыре конфигурации справа в нижнем ряду рисунка показывают, как можно достраивать определенные структуры до любых размеров. Важно подчеркнуть, что эти структуры локализованы. Будучи разделеными двумя покоящимися клетками, они не влияют друг на друга. Можно считать, что стационарные структуры повторяют себя на каждом шаге по времени. Но есть и другие конфигурации, повторяющие себя через N шагов, для краткости будем называть их N -циклами. Примеры циклов периода 2 показаны на рис. 5

 

 

 

 

 

 

 

 

 

Рис. 5. 2-циклы в три последовательных момента времени (сверху вниз). Цикл в третьей колонке — семафор

 

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