Все выпуски

Предложено обобщение блочного клеточного автомата Марголуса на гексагональную сетку. Проведена статистическая обработка результатов вероятностных клеточно-автоматных вычислений для ряда модификаций схемы, решающей тестовую задачу диффузии вещества. Показано, что выбор блоков в виде гексагонов на 25% эффективнее, чем в виде Y-блоков. Показано, что алгоритмы имеют полиномиальную сложность, причем степень полинома для параллельных вычислителей лежит в пределах 0.6÷0.8, а для последовательных — в пределах 1.5÷1.7. Исследовалось влияние внедренных в поле клеточного автомата дефектных ячеек на скорость сходимости.

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

При решении задачи Неймана для колебаний круглой мембраны показана критичность требований к дискретизации условий для граничных КА-ячеек. Для квазиодномерной задачи «диффузия в полупространство» сравниваются КА-расчеты, проводимые по простой схеме и с использованием обобщенного блочно-поворотного механизма Марголуса. При решении смешанной задачи для классического случая колебания круглой мембраны с закрепленными концами показано, что одновременное применение метода Кранка–Николсон и учет членов второго порядка позволяет избежать ИГС-эффекта, наблюдаемого нами для более простой схемы. С точки зрения КА центральное место занимает уравнение диффузии, на пути решения которого на бесконечных временах находится решение краевой задачи для уравнения Лапласа, а путем введения вектор-переменной становится разрешимо волновое уравнение (по крайней мере скалярное).

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

Работа посвящена теоретическому обоснованию неявного итерационного полинейного рекуррентного метода решения систем разностных уравнений, которые возникают при аппроксимации двумерных эллиптических дифференциальных уравнений на регулярной сетке. Высокая эффективность этого метода практически подтверждена при решении сложных тестовых задач, а также задач течения и теплообмена вязкой несжимаемой жидкости. Однако теоретические положения, объясняющие высокую скорость сходимости и устойчивость метода, до сих пор оставались за кадром внимания, что и послужило причиной проведения настоящего исследования. В работе подробно излагается процедура эквивалентных и приближенных преобразований исходной системы линейных алгебраических уравнений (СЛАУ) как в матрично-векторной форме, так и виде расчетных формул метода. При этом для наглядности изложения материала ключевые моменты преобразований иллюстрируются схемами изменения разностных шаблонов, отвечающих преобразованным уравнениям. Конечная цель процедуры преобразований — получение канонической формы записи метода, из которого следует его корректность в случае сходимости решения. На основе анализа структур и элементных составов матричных операторов проводится оценка их норм и, соответственно, доказывается сходимость метода для произвольных начальных векторов.

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

Работа принадлежит направлению экспериментальной математики, исследующей свойства математических объектов вычислительными средствами компьютера. Базовым отображением служит экспоненциальное, топологические свойства (букеты Кантора) которого отличаются от свойств полиномиальных и рациональных функций на комплексной плоскости. Предметом исследования являются характер и особенности множеств Фату и Жюлиа, а также точек равновесия и орбит нуля трех итерированных комплекснозначных отображений: $f:z \to (1+ \mu) \exp (iz)$, $g : z \to \big(1+ \mu |z - z^*|\big) \exp (iz)$, $h : z \to \big(1+ \mu (z - z^* )\big) \exp (iz)$, где $z,\mu \in \mathbb{C}$, $z^* : \exp (iz^*) = z^*$. Для квазилинейного отображения g, не обладающего свойством аналитичности, было обнаружено два бифуркационных перехода: рождение новой точки равновесия (для него было найдено критическое значение параметра, а сама бифуркация представляет собой смешанный случай «вилки» и седлоузельного перехода) и переход к радикальной трансформации множества Фату. Выявлен нетривиальный характер сходимости к фиксированной точке, связанный с появлением «долин» на графике скоростей сходимости. Для двух других отображений существенна монопериодичность режимов, отмечен феномен «удвоения периода» (в одном случае по пути $39\to 3$, в другом — по пути $17\to 2$), причем обнаружено совпадение кратности периода и числа рукавов спирали множества Жюлиа в окрестности фиксированной точки. Приведен богатый иллюстративный материал, численные результаты экспериментов и сводные таблицы, отражающие параметрическую зависимость отображений. Сформулированы вопросы для дальнейшего исследования средствами традиционной математики.

В данной работе рассматривается проксимальный быстрый градиентный метод Монтейро – Свайтера (2013 г.), в котором используется один шаг метода Ньютона для приближенного решения вспомогательной задачи на каждой итерации проксимального метода. Метод Монтейро – Свайтера является оптимальным (по числу вычислений градиента и гессиана оптимизируемой функции) для достаточно гладких задач выпуклой оптимизации в классе методов, использующих только градиент и гессиан оптимизируемой функции. За счет замены шага метода Ньютона на шаг недавно предложенного тензорного метода Ю. Е. Нестерова (2018 г.), а также за счет специального обобщения условия подбора шага в проксимальном внешнем быстром градиентном методе удалось предложить оптимальный тензорный метод, использующий старшие производные. В частности, такой тензорный метод, использующий производные до третьего порядка включительно, оказался достаточно практичным ввиду сложности итерации, сопоставимой со сложностью итерации метода Ньютона. Таким образом, получено конструктивное решение задачи, поставленной Ю. Е. Нестеровым в 2018 г., об устранении зазора в точных нижних и завышенных верхних оценках скорости сходимости для имеющихся на данный момент тензорных методов порядка $p \geqslant 3$.