Издательство СО РАН

Издательство СО РАН

Адрес Издательства СО РАН: Россия, 630090, а/я 187
Новосибирск, Морской пр., 2

soran2.gif

Baner_Nauka_Sibiri.jpg


Яндекс.Метрика

Поиск по журналу

Сибирский журнал вычислительной математики

2019 год, номер 2

1.
Точные алгоритмы поиска кластера наибольшего размера для двух целочисленных задач 2-кластеризации

А.В. Кельманов1,2, А.В. Панасенко1,2, В.И. Хандеев1,2
1Институт математики им. С.Л. Соболева Сибирского отделения Российской академии наук, Новосибирск, 630090, Россия
kelm@math.nsc.ru
2Новосибирский национальный исследовательский государственный университет, Новосибирск, 630090, Россия
a.v.panasenko@math.nsc.ru
Ключевые слова: евклидово пространство, 2-кластеризация, наибольшее подмножество, NP-трудность, целочисленная задача, псевдополиномиальная разрешимость, Euclidean space, 2-clustering, largest subset, NP-hardness, exact algorithm, pseudo- polynomial-time solvability
Страницы: 121-136

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

DOI: 10.15372/SJNM20190201
Добавить в корзину
Товар добавлен в корзину


2.
Автоматизированная система идентификации условий проведения гомогенных и гетерогенных реакций в задачах многоцелевой оптимизации

К.Ф. Коледина1,2, С.Н. Коледин2, И.М. Губайдуллин1,2
1Институт нефтехимии и катализа Российской академии наук, Уфа, Россия, 450075
koledinakamila@mail.ru
2Уфимский государственный нефтяной технический университет, Уфа, Россия, 450062
koledinsrg@gmail.com
Ключевые слова: автоматизированная система идентификации условий проведения гомогенных и гетерогенных реакций, кинетическая модель, многоцелевая оптимизация, островная модель распараллеливания, декомпозиция автоматизированной системы, automated system for identification conditions for carrying out homogeneous and heterogeneous reactions, kinetic model, multipurpose optimization, island model of parallelization, decomposition of automated system
Страницы: 137-151

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

DOI: 10.15372/SJNM20190202
Добавить в корзину
Товар добавлен в корзину


3.
Метод получения аналитических решений краевых задач на основе определения дополнительных граничных условий и дополнительных искомых функций

И.В. Кудинов, Е.В. Котова, В.А. Кудинов
Самарский государственный технический университет, Самара, Russia, 443100
totig@yandex.ru
Ключевые слова: нестационарная теплопроводность, аналитическое решение, интегральный метод теплового баланса, дополнительные граничные условия, дополнительные искомые функции, фронт температурного возмущения, координатные функции, бесконечная скорость распространения теплоты, transient thermal conductivity, analytical solution, integral method of heat balance, additional boundary conditions, additional desired function, front of temperature perturbations, coordinate functions, infinite velocity of propagation of heat
Страницы: 153-165

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

DOI: 10.15372/SJNM20190203
Добавить в корзину
Товар добавлен в корзину


4.
Двухсеточные методы для новой смешанной конечно-элементной аппроксимации полулинейных параболических интегро-дифференциальных уравнений

С. Лиу1, Т. Хоу2
1Institute of Computational Mathematics, Yongzhou 425100, Hunan, China
liuchunmei0629@163.com
2School of Mathematics and Statistics, 132013, Jilin, China
270854140@qq.com
Ключевые слова: полулинейные параболические интегро-дифференциальные уравнения, новый смешанный метод конечных элементов, априорная оценка ошибки, двухсеточный, пространство квадратично интегрируемых функций, semilinear parabolic integro-differential equations, a new mixed finite element method, a priori error estimate, two-grid, space of square integrable functions
Страницы: 167-185

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

DOI: 10.15372/SJNM20190204
Добавить в корзину
Товар добавлен в корзину


5.
Рандомизированные алгоритмы метода Монте-Карло для задач со случайными параметрами (метод “двойной рандомизации”)

Г.А. Михайлов1,2
1Институт вычислительной математики и математической геофизики Сибирского отделения Российской академии наук, Новосибирск, Россия, 630090
gam@sscc.ru
2Новосибирский национальный исследовательский государственный университет, Новосибирск, Россия, 630090
Ключевые слова: вероятностная модель, статистическое моделирование, случайный параметр, рандомизированный алгоритм, метод двойной рандомизации, случайная среда, метод расщепления, статистическая ядерная оценка, probabilistic model, statistic modeling, random parameter, randomized algorithm, double randomization method, random medium, splitting method, statistic kernel estimator
Страницы: 187-200

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

DOI: 10.15372/SJNM20190205
Добавить в корзину
Товар добавлен в корзину


6.
Адаптивный аналог метода Ю.Е. Нестерова для вариационных неравенств с сильно монотонным оператором

Ф.С. Стонякин
Крымский федеральный университет им. В.И. Вернадского, Симферополь, Россия, 295007
fedyor@mail.ru
Ключевые слова: вариационное неравенство, сильно монотонный оператор, адаптивный метод, условие Липшица, качество решения, variational inequality, strongly monotone operator, adaptive method, Lipschitz condition, solution quality
Страницы: 201-211

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

DOI: 10.15372/SJNM20190206
Добавить в корзину
Товар добавлен в корзину


7.
Численные методы, равномерно сходящиеся относительно параметра для одного класса параметризованных сингулярно возмущенных задач

Д. Шакти, Дж. Мохапатра
National Institute of Technology, Rourkela, 769008, India
514ma6002@nitrkl.ac.in
Ключевые слова: параметризованная задача, сингулярные возмущения, граничный слой, обратный метод Эйлера, монотонная гибридная схема, parameterized problem, singular perturbation, boundary layer, backward Euler method, monotone hybrid scheme
Страницы: 213-228

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

DOI: 10.15372/SJNM20190207
Добавить в корзину
Товар добавлен в корзину


8.
Чувствительность функционалов к данным наблюдений в задаче вариационного усвоения для модели термодинамики моря

В.П. Шутяев1,2, Е.И. Пармузин1
1Институт вычислительной математики Российской академии наук, Москва, Россия, 119333
victor.shutyaev@mail.ru
2Федеральное государственное бюджетное учреждение науки «Морской гидрофизический институт РАН», Севастополь, Россия, 299011
Ключевые слова: вариационное усвоение данных наблюдений, оптимальное управление, сопряженные уравнения, ковариационные матрицы, чувствительность функционалов, температура поверхности моря, variational data assimilation, optimal control, adjoint equations, covariance matrices, sensitivity of functionals, sea surface temperature
Страницы: 229-242

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

DOI: 10.15372/SJNM20190208
Добавить в корзину
Товар добавлен в корзину