Главная – Журналы – Сибирский журнал вычислительной математики 2019 номер 2

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

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

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

В данной статье представлена двухсеточная схема для полулинейного параболического интегро-дифференциального уравнения с использованием нового смешанного метода конечных элементов. Градиент в методе принадлежит пространству квадратично интегрируемых функций, а не классическому пространству H (div;Ω). Скорость и давление аппроксимируются парой P ₀²- P ₁, которая удовлетворяет условию inf-sup. Вначале мы решаем исходную нелинейную задачу на грубой сетке нашей двухсеточной схемы. Затем для линеаризации дискретизованных уравнений мы дважды используем ньютоновскую итерацию на мелкой сетке. Показано, что алгоритм помогает достичь асимптотически оптимальной аппроксимации, когда размеры сеток удовлетворяют соотношению h = O ( H ⁶ |ln H |²). В результате решение такого большого класса нелинейных уравнений не намного сложнее, чем решение одного линеаризованного уравнения. Представлен численный эксперимент для подтверждения теоретических результатов двухсеточного метода.

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

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

В данной статье для решения класса параметризованных сингулярно возмущенных задач (СВЗ) предложена взвешенная конечно-разностная схема. В зависимости от выбора весового параметра схема автоматически преобразуется из обратной схемы Эйлера в монотонную гибридную схему. Рассматриваются три вида неоднородных сеток: стандартная сетка Шишкина (S-сетка), сетка Бахвалова-Шишкина (B-S-сетка) и адаптивная сетка. Показана равномерная сходимость этих методов по отношению к параметру возмущения для всех трех видов сеток. Скорость сходимости имеет первый порядок для обратной схемы Эйлера и второй порядок для монотонной гибридной схемы. Кроме того, предлагаемый метод обобщается для параметризованной задачи с граничными условиями смешанного типа и показана его равномерная сходимость. Приводятся результаты численных экспериментов для демонстрации эффективности предлагаемых схем, которые свидетельствуют об оптимальности оценок.

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