II. ИТОГИ НАУЧНЫХ ИССЛЕДОВАНИЙ
2.1. Важнейшие научные результаты
Автор результата: д.ф.-м.н., зав. лаб. ОФ ИМ СО РАН, Задорин А.И., (3812) 23-67-39
Предложен способ сплайн-интерполяции функций одной переменной с большими градиентами, основанный на выделении аддитивной составляющей, задающей основной рост. Показано, что формулы линейной и квадратической сплайн-интерполяции обладают равномерной точностью на априорно сгущающихся сетках.
Аннотация:
Известно, что при применении методов полиномиальной сплайн-интерполяции к функциям с большими градиентами могут возникать существенные погрешности. Однако, если известен вид составляющей, отвечающей за рост решения, то это можно учесть при построении сплайн-интерполяционной формулы. В случае произвольной сетки построена сплайн-интерполяционная формула, точная на погранслойной составляющей, первого порядка точности независимо от градиентов интерполируемой функции. Показано, что построенная формула может быть применена в случаях, когда интерполируемая функция является решением задачи с экспоненциальным или степенным пограничным слоем, распространена на случай функции двух переменных. Показано, что при использовании сетки, априорно сгущающейся в пограничном слое, линейная и квадратическая сплайн-интерполяции обладают равномерной точностью второго и третьего порядка, соответственно, по числу узлов. Показано, как на основе предложенной сплайн-интерполяции можно построить двухсеточный алгоритм решения нелинейной сингулярно-возмущенной краевой задачи. Предложенная сплайн-интерполяция в этом алгоритме необходима при интерполяции сеточного решения с крупной сетки на мелкую.
Результат опубликован:
Задорин А.И. Метод интерполяции для задачи с пограничным слоем // Сибирский журнал вычислительной математики, 2007, т. 10, № 3, с. 267- 275.
Задорин А.И. Метод интерполяции для функции двух переменных с погранслойной составляющей // Вычислительные технологии, 2008, т. 13, № 3, с. 45-53.
Задорин А.И. Метод интерполяции на сгущающейся сетке для функции с погранслойной составляющей // Журнал вычислительной математики и математической физики, 2008, т. 48, № 9, с. 1673-1684.
L.G. Vulkov, A.I. Zadorin Two-grid Interpolation Algorithms for Difference Schemes of Exponential Type for Semilinear Diffusion Convection-Dominated Equations. // American Institute of Physics, Conference proceedings, 2008, v. 1067, p. 284- 292.
Результат доложен:
Международная конференция “Вычислительные и информационные технологии в науке, технике и образовании “, Алматы, Казахский национальный университет, сентябрь, 2008, (пленарный доклад).
Международная конференция, посвященная 100-летию С.Л. Соболева, ИМ СО РАН, октябрь, 2008 (секционный доклад).
Ежегодная научная сессия ОФ ИМ СО РАН, 13 октября 2008 года.
2.2. Научная работа лабораторий
Лаборатория комбинаторных и вычислительных методов алгебры и логики
(заведующий – д.ф.-м.н. Ремесленников В.Н.)
В рамках плана научных работ лаборатории и гранта РФФИ выполнен цикл работ по созданию универсальной алгебраической геометрии для произвольных алгебраических систем. Написаны две работы. Первая из них посвящена доказательству так называемых «объединяющих теорем». В них формулируются и обосновываются различные подходы: алгебраический, геометрический, теоретико-модельный и логический к описанию алгебраических множеств, задаваемых системами уравнений над данной алгебраической системой, и их координатных алгебр. (Ремесленников В.Н., Даниярова Э.Ю.).
Один из языков при описании координатных алгебр есть язык предельных алгебр. Эти общие теоремы уже нашли применение к конкретным алгебраическим системам. Полностью описаны предельные моноиды для моноида натуральных чисел по сложению (Морарь П.В, Шевляков А.Н.).
Получен ряд результатов по частично коммутативным нильпотентным и свободным группам. Построена теория ортогональности для конечных графов, при помощи которой получен ряд структурных результатов для свободных частично-коммутативных групп. Исследована проблема универсальной эквивалентности для групп (Ремесленников В.Н., Казачков И.В., Данкен Э.).
Решена проблема Ремесленникова В.Н. о классификации частично-коммутативных нильпотентных групп ступени 2 с точностью до универсальной эквивалентности. Получен ряд результатов по описанию алгебраических множеств специального вида для этих групп (Мищенко А.А.).
Описаны порождающие элементы для групп автоморфизмов частично-коммутативных групп ступени нильпотентности 2. Доказана теорема о структуре этих групп (Трейер А.В.).
Развита теория делимости для известной полугруппы Томпсона (Есып Е.С.).
Было продолжено изучение алгебраической геометрии для свободной метабелевой алгебры Ли над полем и для свободной антикоммутативной алгебры (Э. Ю. Даниярова). Оказалось, что многие результаты, полученные ранее Данияровой Э.Я. для случая конечного поля, верны и для бесконечного поля, для бесконечного поля исследования будут продолжены в будущем.
Дано завершение классификации δ-однородных компактных односвязных римановых многообразий в совместной работе Берестовского В.Н. и Никонорова Ю.Г.
Получен ряд принципиально новых результатов по киллинговым векторным полям, по нормам Чебышева (Берестовский В.Н.).
Получены теоремы по описанию геодезических в группах Гейзенберга. В рамках интеграционного проекта получены результаты по геометриям Гильберта и их приложениям (Носков Г.А.).
В рамках исследований по инвариантам представлений классических алгебраических групп подготовлен и напечатан обзор об инвариантах представлений колчанов и их обобщений. Часть результатов этого сборника являются новыми, полученными в 2008 г. В первой части обзора описаны порождающие и определяющие соотношения для групп GL(n) и O(n). Во второй части представлены результаты по представлениям колчанов, а третья часть посвящена обобщениям представлений колчанов (Лопатин А.А., Зубков А.Н.).
В рамках исследований по гранту РФФИ и интеграционному проекту в лаборатории выполнялась специальная тема по генерической сложности алгоритмов. В рамках этой темы было доказано, что любая неразрешимая теория, например, формальная арифметика, является строго генерически неразрешимой, тем самым были усилены многие классические результаты об алгебраической неразрешимости теорий (Рыбалов А.Н., Мясников А.Г.).
Написан обзор «Вычислимость над алгебраическими системами» (Вестник ОмГУ, 2008, с.107-129) (Ашаев И.В.).
Лаборатория теоретико-вероятностных методов
(заведующий – д.ф.-м.н. Топчий В.А.)
Продолжено исследование многомерных симметрических случайных блужданий по решетке с ветвлением в нуле. Описана асимптотика средней численности частиц в нуле и вероятности наличия частиц в нуле для размерностей 1 и 2 при произвольном выборе интенсивностей переходов в нуле и на остальной решетке. Ранее аналогичные результаты были получены для размерностей больше 3 (Топчий В.А.).
Получены верхние оценки среднего времени вырождения популяции с постоянной биологической ёмкостью среды и для ветвящейся популяции с фиксированным надкритическим размножением и уничтожением частиц, не помещающихся на заданное число мест (Клоков С.А., Топчий В.А.).
Построена и исследована стохастическая модель динамики популяции с учетом ограниченности мест репродукции и различной длительности сезонов между размножением особей (Перцев Н.В., Логинов К.К.). Построена и исследована модель динамики двух конкурирующих популяций, развивающихся в условиях воздействия вредных веществ (Перцев Н.В., Царегородцева Г.Е.). Построена индивидуум-ориентированная модель распространения туберкулеза, учитывающая контакты индивидуумов и произвольные законы распределения длительностей различных стадий заболевания (Перцев Н.В., Пичугин Б.Ю.).
В рамках предложенного ранее подхода к определению оптимальной структуры тестов на основе математических моделей разработаны алгоритмы для решения одной задачи компьютерного тестирования. Усовершенствована версия автоматизированной тестирующей системы (Заозерская Л.А., Планкова В.А.).
Произведена обработка для выявления биофизических характеристик электроэнцефалограмм пациентов с венознососудистой дистонией вейвлет преобразованием Морле и получены новые пространственно-временные представления соответствующих ЭКГ. По полученным пространственно-временным представлениям можно проводить предварительную визуальную диагностику заболеваний (Гольтяпин В.В.).
Лаборатория математического моделирования в механике
(заведующий – д.ф.-м.н. Задорин А.И.)
Предложен способ сплайн-интерполяции функций одной переменной с большими градиентами, основанный на выделении составляющей решения, задающей основной рост. Исследован вопрос интерполяции функции с быстро растущей погранслойной составляющей. Построена формула, точная на погранслойной составляющей, доказан первый порядок точности построенной интерполяционной формулы независимо от градиентов решения. На основе предложенной интерполяции получена формула для вычисления производных. Показано, что данная интерполяция применима к функциям, соответствующих решению краевых задач с экспоненциальным и степенным пограничными слоями. В случае экспоненциального пограничного слоя получено обобщение построенной формулы на случай функции двух переменных (Задорин А.И.).
Предложен и исследован двухсеточный метод решения сингулярно возмущенной нелинейной краевой задачи. Рассмотрена сингулярно возмущенная краевая задача для нелинейного ОДУ второго порядка. Доказано, что схема А.М. Ильина для данной задачи обладает свойством равномерной сходимости с первым порядком по шагу сетки. Для разрешения нелинейной разностной схемы исследуются итерационные методы Ньютона и Пикара. Для уменьшения числа итераций предложено использовать двухсеточный метод, когда разностная схема выписывается и на грубой сетке. Тогда хорошее начальное приближение для итераций на исходной сетке находится на основе итераций на грубой сетке. Для интерполяции решения с грубой сетки на мелкую используется предложенная нами равномерно точная интерполяционная формула (Задорин А.И.).
Исследован численный метод решения краевой задачи для эллиптического уравнения с малым параметром при старших производных и сосредоточенным источником в полосе. На основе метода прямых эллиптическая задача сведена к системе ОДУ второго порядка на бесконечном интервале. Для сведения задачи к конечному интервалу применен метод выделения устойчивого многообразия решений, удовлетворяющих предельному условию на бесконечности. Равномерная сходимость разностной схемы достигается сгущением сетки у границ полосы и в окрестности линейного источника (Харина О.В.).
Построена разностная схема с учетом внутренних пограничных слоев для моделирования струйных течений в задачах тепло-массопереноса. В расчетах течений вязкой несжимаемой жидкости при больших числах Рейнольдса исследовано ускорение сходимости к стационарным решениям на основе введения искусственной «нелинейной вязкости» в разностную схему. При этом исходная схема обладает малой схемной вязкостью за счет введения одномерных интерполяций для внутренних пограничных слоев. Проведена разработка двумерных интерполяций для расчета внутренних пограничных слоев (Паничкин А.В.).
Разработана численная модель нестационарного отрывного обтекания разомкнутого контура. Рассматривается движение контура в идеальной несжимаемой жидкости из состояния покоя с постоянной скоростью. В этом случае движение жидкости нестационарно, циркуляция скорости вокруг контура меняется с течением времени, а с кромок контура сходят вихревые следы, обусловленные изменением циркуляции скорости. Для комплексной скорости, являющейся аналитической функцией, формулируется нелинейная начально-краевая задача. Контур и вихревые следы моделируются системой дискретных вихрей. Разработан алгоритм для определения эволюции вихревых следов с учетом локальных соотношений в точках их схода с контура. Получены формулы для расчета распределения давления по контуру на режиме отрывного нестационарного движения жидкости. Дополнительно к плану продолжались исследования по аэродинамике ортогональных ветроколес типа ротора Дарье (Горелов Д.Н.).
Лаборатория моделирования сложных систем
(заведующий – д.т.н. Чуканов С.Н.)
Предложена конструкция сферических гармоник, имеющих заданные нули на сфере. Для двумерной сферы оно приводит к почти однозначному представлению гармоник в виде определителя. Получены верхние и нижние границы для длин узловых множеств и для внутренних радиусов узловых областей; верхние границы точны. Дана точная оценка сверху числа общих нулей двух сферических гармоник на двумерной сфере. Кроме того, найдены средние значения мер Хаусдорфа пересечений узловых множеств нескольких гармоник разных степеней на сфере любой размерности (в частности, среднее количество общих нулей k гармоник на k-мерной сфере) (Гичев В.М.).
Разработан алгоритм формирования характеристик векторных полей динамических систем, инвариантных по отношению к аффинной группе преобразований вектора состояния, основанный на преобразовании Фурье функции 3D изображения, инвариантному к действию групп вращения, переноса и масштабирования. Преобразование Фурье функции 3D изображения основано на разложении в ряд сферических функций (Чуканов С.Н.).
Исходная основа результата 2008-го года – полученное ранее обобщение радиолокационного соотношения неопределённостей (СН) и его следствия. Одно из следствий обобщённого СН состоит в том, что минимум неопределённости измерения макроскопической величины достигается при её измерении в оптимальном интервале неопределённости. Интервал, как следствие СН, в отличие от определения интервала в математике, есть бесструктурное целое, квант. Величина кванта неопределённости не является фундаментальной константой, как в микромире, а определяется локальными макроскопическими параметрами физического и/или вычислительного процесса. Предложен адаптивный алгоритм минимизации неопределённости измерения, который приводит к расширению понятия и содержания измерения: измерение - это единый измерительно-вычислительный адаптивный процесс. Новизна понятия измерения состоит в пошаговой адаптации параметров измерителя к параметрам измеряемого объекта. Указанный алгоритм включает новый метод прямого построения адаптивной одномерной сетки, являющийся альтернативным по отношению к основанным на вариационном принципе методам (Терехов Л.С.).
Разработан алгоритм пакетной передачи информации в системе коротковолновой радиосвязи, предполагающей параллельную передачу информационных пакетов через сеть ретрансляторов малой мощности. Предложены алгоритмы маршрутизации пакетов в предлагаемой системе связи. Проведены вычислительные эксперименты по оценке характеристик ионосферного распространения радиоволн на радиолиниях дальностью от 100 до 2000 км, подтверждающие работоспособность предлагаемых способов передачи информации на магистральных радиолиниях КВ связи. Для радиолиний малой дальности предложены алгоритмы выбора оптимальных рабочих частот. Результаты исследований используются при разработках новой техники радиосвязи в Омском НИИ приборостроения (Зачатейский Д.Е.).
Продолжена разработка системы для решения задач нейросетевого управления (Мещеряков В.А.).
На основе метода чередования прямой и обратной задач оптимального управления динамической системой построены новые алгоритмы направленной оптимизации начальных векторов управления, состояния и управления-состояния для задач неавтономной динамики с однородными управлением и процессом (Нартов Б.К.).
Лаборатория методов преобразования и представления информации
(заведующий – д.т.н. Зыкин С.В.)
Разработаны методы формирования контекстов приложений и контекстов ограничений на данные при формировании гиперкубов для проведения аналитической обработки данных. Предложенные методы использованы для анализа эффективности лечения больных почечной недостаточностью в МСЧ № 10 г. Омска. Решена задача построения гиперкубического представления данных при наложении контекстных ограничений на исходное реляционное представление данных. В основе построения лежит формальное определение промежуточной и целевой моделей данных (Зыкин С.В., Полуянов А.Н.).
Разработан метод автоматического извлечения терминоподобных (доминантных) словосочетаний из текстов, представляющих предметную область. Метод базируется на следствиях из Ассоциативной модели реального текста и результатах исследований по автоматическому определению в естественно-языковых текстах наиболее тематически важных слов (доминант). На основании результатов по автоматическому выделению терминоподобных словосочетаний разработана структура базы знаний терминологической ИПС и собственно ИПС (Чанышев О.Г.).
Разработана промежуточная технология работы ситуационных центров, которая предполагает ориентацию на эффективное использование доступных ресурсов (Филимонов В.А.).
Разработан проект учебно-исследовательского комплекса «Ген-Гуру» (общая структура, функции, методы создания и эксплуатации) на основе использования строгого формального аппарата и способов мобилизации творческих возможностей человека. Разработаны модули маркетинговой информационной системы, предназначенные для анализа развития объекта сферы сервиса как аналога механического движения; цены и спроса с использованием лингвистической переменной (Филимонов В.А., Маренко В.А.).
Проведена реструктуризация базы данных ГИС «Археологические памятники Омской области» с целью обеспечения интерфейса с методами анализа данных. Проведена классификация археологических объектов по существенным паспортным параметрам. Формализовано описание системы анализа транспортных сетей (на примере сетей передачи данных и автомобильных сетей) на базе технологий ГИС, таксономии и имитационного моделирования (Пуртов А.М.).
Лаборатория дискретной оптимизации
(заведующий – д.ф.-м.н. Колоколов А.А.)
Предложен подход к построению верхних оценок среднего числа итераций для ряда алгоритмов целочисленного линейного программирования, основанных на использовании непрерывной оптимизации (отсечения, ветвей и границ, перебора L-классов), получены полиномиальные оценки указанного типа при решении задачи об упаковке множества (Заозерская Л.А., Колоколов А.А).
Построены алгоритмы решения задачи календарного планирования с критериями числа незавершенных в срок заданий и максимального запаздывания работ (Сервах В.В., Щербинина Т.А.).
Предложен полиномиальный алгоритм решения задачи построения циклических расписаний при отсутствии простоев между операциями (Сервах В.В., Романова А.А.).
Разработаны точные алгоритмы решения взвешенной задачи максимальной выполнимости на основе перебора L-классов и метода ветвей и границ, выполнена их программная реализация, проведены экспериментальные расчеты (Адельшин А.В., Кучин А.К.).
Исследованы свойства L-периодических расписаний при выпуске однотипных деталей (Сервах В.В., Межецкая М.А.).
Предложены алгоритмы, основанные на декомпозиции Бендерса, переборе
L-классов и ряде эвристических процедур, для решения двухстадийной задачи размещения предприятий, проведены экспериментальные исследования (Колоколов А.А., Леванова Т.В., Федоренко А.С.).
Разработан и реализован алгоритм ветвей и границ для решения минимаксной задачи размещения взаимосвязанных объектов на плоскости с запрещенными зонами. Проведен вычислительный эксперимент (Забудский Г.Г., Решетникова А.А.).
Построена модель целочисленного программирования для составления схемы разделения труда при проектировании технологической подготовки производства с заданным сетевым графиком выполнения работ (Забудский Г.Г., Алексеенко И.В.).
В рамках предложенного ранее подхода к определению оптимальной структуры тестов на основе моделей дискретной оптимизации разработаны алгоритмы перебора L-классов для решения одной задачи компьютерного тестирования. Усовершенствована версия автоматизированной тестирующей системы по одной из тем учебного курса «Экономико-математические методы» для студентов экономических специальностей. (Заозерская Л.А., Планкова В.А.).
Предложен гибридный генетический алгоритм для задачи балансировки производственной линии, проведен вычислительный эксперимент, показавший преимущество данного алгоритма на задачах большой размерности по сравнению с другими известными методами (Гущинская О.Н., Долгий А.Б, Еремеев А.В.).
Предложен гибридный алгоритм для задачи составления расписаний многопродуктового производства с использованием методов частично целочисленного программирования и генетического алгоритма, показавший пригодность к использованию на производстве (Борисовский П.А., Еремеев А.В., Флудас К.А., Муновар А.Ш., Калльрат И.).
Центр информационного обеспечения научных исследований
(заведующий – к.ф.-м.н. Алгазин В.А.)
Заказной интеграционный проект № 3 СО РАН «Развитие мультимедийных приложений в сети передачи данных Сибирского отделения РАН», рук. – академик РАН Ю.И. Шокин, руководитель от ОФ ИМ – В.А. Алгазин, исполнители - В.А. Алгазин, С.А. Хрущев, 2006 – 2009 гг.
Работы 2008г. были направлены на введение в эксплуатацию и настройку оборудования для проведения видеоконференций, полученного по Распоряжению Президиума СО РАН № 15000-140 от ИВТ и проведения настройки оборудования видеоконференций Polycom VSX 7800e Presenter MP.
В Омский научный центр СО РАН было передано оборудование для проведения видеоконференций. В список переданного оборудования входят:
групповой видеотерминал Huaweu ViewPoint 8066 с встроенной видеокамерой;
плазменный дисплей Pioneer PLD50;
внешняя видеокамера фирмы Sony;
В связи с ремонтом помещения Президиума ОНЦ СО РАН полученное оборудование, за исключением плазменной панели, было установлено в помещении библиотеки Омского филиала Института математики им. С.Л. Соболева СО РАН и была проведена его настройка. Для проведения видеоконференций СО РАН был предоставлен канал 10Мбит/с до ИВТ СО РАН. До конца года планируется развернуть систему видеоконференций на базе Huaweu ViewPoint 8066.
Проведена настройка оборудования видеоконференций Polycom VSX 7800e Presenter MP. Функциональность системы расширена за счёт активации возможности проведения многоточечной конференции. Также добавлена возможность трансляции с компьютера через ImageShare. Проведены опытные сеансы видеоконференций с Новосибирском (ИВТ СО РАН) и Самарой (Самарский государственный аэрокосмический университет имени академика С.П.Королева). Проведена видеоконференция заседания Президиума СО РАН с участием региональных центров СО РАН (Иркутск, Томск, Омск, Красноярск и др.). В Омске видеоконференция проводилась из ОФИМ.
|
