Введение к работе
Актуальность темы исследования. Как известно, моделирование сложных процессов и явлений - многошаговая процедура. Первоначальное описание информационной модели, имеющее вид системы уравнений или неравенств, связывающих параметры или характеристики объекта, может быть противоречивым, т.е. соответствующая система может не иметь решения, быть несовместной. Эта противоречивость может быть вызвана неточностью или неопределенностью исходных данных, чрезмерным упрощением действительных связей, абсолютизацией некоторых требований и т.д. Противоречивость можно считать одним из факторов плохой формализуемости, которая является частым атрибутом реальных задач. В современной математике уже не ставится под сомнение содержательность проблемы коррекции несовместных моделей. Несовместная модель может быть показателем сложности информационных процессов, а способы ее корректирования - отражением действительных процедур разрешения реальных проблем. Виды и способы коррекции могут быть различными и определяться внешними причинами, к которым, прежде всего, относятся содержательные особенности решаемой прикладной задачи.
Матричная коррекция несовместных систем линейных алгебраических уравнений (СЛАУ), как научное направление, изначально развивалось в связи с задачей обработки экспериментальных данных с помощью обобщенного метода наименьших квадратов, являющегося усовершенствованием метода наименьших квадратов на случай, когда шум присутствует в наблюдениях как зависимых, так и независимых переменных. Наиболее известными в этой области являются работы американских математиков под руководством профессора Дж.Б.Розена. В нашей стране исследования с упором на несобственные задачи математического программирования проводились научной школой под руководством академика РАН И.И. Еремина и научной группой Вычислительного центра им. А.А. Дородницына Российской академии наук и Mill'У под руководством профессора В.А. Горелика.
В последние годы исследования в области методов коррекции несовместных СЛАУ ведутся весьма интенсивно. При этом особое внимание уделяется задачам структурной коррекции, которые, с одной стороны, в наибольшей степени отвечают потребностям практики, а с другой стороны, представляют наиболее сложный математический объект, трудно поддающийся аналитическому исследованию.
В работах В.А. Горелика, В.И. Ерохина и Р.В. Печенкина осуществлено развитие подхода структурной коррекции к несовместным СЛАУ с матрицами специального вида (блочной, матрицами Теплица и Вандермонда) и методов их оптимальной коррекции по квадратичному и минимаксному критериям. Получен метод решения задачи оптимальной матричной коррекции несовместных систем линейных алгебраических уравнений, обладающих блочной структурой с использованием квадратичного и минимаксного критериев. Сформулирован критерий оптимальной коррекции несовместной системы с матрицей Теплица и Вандермонда при наличии ошибок только в левой части
4 и предложен метод коррекции с использованием штрафных функций норм векторов невязок. Для плохо обусловленных систем со структурой Вандер-монда сформулирован регуляризованный критерий коррекции, разработан численный алгоритм, реализующий поиск оптимального решения в различных нормах. В.Л. Матросов, В.А. Горелик, С.А. Жданов, О.В. Муравьева применили методы коррекции к задачам распознавания. В.А. Горелик, И.А. Золтоева и Р.В. Печенкин рассмотрели проблему оптимальной коррекции несовместной системы с матрицами разреженной структуры и ее применение к задачам многокритериальной оптимизации. Естественным требованием для таких систем является сохранение разреженной структуры, что вносит ограничение на структуру матрицы коррекции, но с другой стороны уменьшает размерность задачи, что приводит к построению более эффективных алгоритмов.
В качестве одной из разновидностей структурных ограничений можно рассматривать матрицы комбинаторного типа, в строках которых элементы записаны так, что представляют подмножества данного множества или сочетания из всех его элементов.
В последние десятилетия изменилось соотношение дискретной и классической математики. Изменилась и роль комбинаторики - с помощью современных мощных компьютеров стало возможным делать переборы, ранее требовавшие сотни лет. Широкое распространение получили комбинаторные методы и комбинаторные устройства, связь, управление и функционирование которых основаны на комбинировании сигналов по принципу перестановок, размещений и сочетаний. Математические модели процессов и явлений, функционирующих на комбинаторных принципах, как правило, содержат много переменных величин и поэтому описываются системами с большим числом уравнений и неравенств. Кроме того матрицы этих систем содержат значительное количество нулей, т.е. являются разреженными. Очевидно, что такая особенность структуры матриц комбинаторного типа должна учитываться при подборе методов решения соответствующих задач. Любой канал связи содержит шумы, приводящие к неточности информационных сигналов, получаемых на выходе. Устройства и системы, работающие на комбинаторных принципах, не являются исключением. Поэтому системы уравнений и неравенств, описывающие работу таких устройств могут оказаться несовместными. Как правило, исследование структур, функционирующих по законам комбинаторики, осуществляется с помощью графов. В данной работе предлагается использовать системы уравнений и неравенств комбинаторного типа, позволяющие получить сведения не только о результатах работы таких структур, но и факторах существенно на нее влияющих, определять границы устойчивости и т.п. Ранее задачи коррекции исходных данных несовместных систем комбинаторного типа не рассматривались.
Проблема заключается в разработке математического аппарата исследования структурных задач оптимальной матричной коррекции несовместных систем линейных алгебраических уравнений и неравенств комбинаторного типа и построении устойчивых и эффективных численных методов решения таких задач.
Объектом исследования является теория коррекции несовместных систем линейных алгебраических уравнений и неравенств.
Предмет исследования составляют вопросы структурной матричной коррекции несовместных систем линейных алгебраических уравнений и неравенств комбинаторного типа с матричными и векторными нормами в качестве критерия минимальности коррекции.
Основная цель - развитие подхода структурной коррекции к несовместным системам линейных алгебраических уравнений и неравенств с матрицами комбинаторного типа и разработка методов их оптимальной коррекции (по квадратичному и минимаксному критерию).
В основу исследования была положена гипотеза о том, что несовместная система Ах & b является результатом неточно заданных или противоречивых исходных данных: вектора а, от которого параметрически зависит матрица комбинаторного типа А, и что задачу коррекции можно свести к задаче оптимизации и получить такие оптимальные решения, чтобы гарантировать совместность и структурный вид скорректированной системы, при условии, что поправка минимальна.
Для достижения поставленной цели и проверки гипотезы решались следующие задачи:
Определение понятия матрицы комбинаторного типа и исследование особенностей ее структуры и свойств.
Исследование вопроса совместности системы линейных неравенств с матрицами комбинаторного типа.
Постановка и решение проблемы коррекции систем уравнений и неравенств с матрицами комбинаторного типа.
Разработка вычислительных алгоритмов для поиска оптимального решения задач коррекции несовместных систем линейных уравнений и неравенств с матрицами комбинаторного типа.
Применение методов коррекции систем комбинаторного типа к задачам принятия решений и распознавания.
Методологическую основу работы составляют современные методы линейной алгебры, математического анализа, теории оптимизации, анализа и обработки данных.
Научная новизна
введено понятие матрицы комбинаторного типа и исследованы свойства комбинаторных систем линейных уравнений и неравенств;
предложен метод решения задачи оптимальной коррекции несовместных систем комбинаторного типа с использованием квадратичного и минимаксного критериев;
предложен метод коррекции кооперативных игр с пустым ядром на основе нового понятия Ср-ядра;
рассмотрено приложение матриц и систем комбинаторного типа и их коррекции в задачах распознавания на примере задачи кластеризации.
Практическая значимость. Предложенные в работе методы исследования и коррекции несовместных систем линейных алгебраических уравнений
6 и неравенств комбинаторного типа могут быть использованы для разработки и анализа моделей информационных процессов и структур и решения на их основе многих прикладных задач в сфере планирования и управления. В работе эти методы использованы для коррекции пустых ядер отношений предпочтения в задачах принятия решений и построения разделяющих гиперплоскостей пересекающихся классов в различных подпространствах признакового пространства.
Вычислительные эксперименты показали работоспособность предлагаемых методов и алгоритмов.
Основные положения, выносимые на защиту:
формализация задач оптимальной коррекции структурных систем линейных алгебраических уравнений и неравенств с матрицами комбинаторного типа при наличии ошибок данных в обеих частях системы;
модификация алгоритма обобщенной наименьшей нормы (TLN) для решения задач коррекции обеих частей и при наличии ошибок только в левой части и комбинация его с методом штрафных функций;
конкретизация методов исследования и коррекции несовместных СЛАУ и систем неравенств комбинаторного типа для решения несобственных задач принятия решений и распознавания.
Апробация результатов исследования. Основные результаты, полученные в диссертации, докладывались на следующих конференциях:
на X Международной научно-практической конференции «Информационные и коммуникационные технологии в образовании» Борисоглебск, 2009 г.,
на Всероссийской научно-практической конференции «Математика, информатика, естествознание в экономике и в обществе» Москва, 2009 г.,
на XVII Международной научной конференции студентов, аспирантов и молодых ученых «Ломоносов - 2010» Москва, 2010 г.,
на VI Московской международной конференции по Исследованию Операций (ORM2010), Москва, 2010,
а также на научно-методических семинарах кафедры информатики Северо-Восточного государственного университета (г. Магадан) и кафедры теоретической информатики и дискретной математики Московского педагогического государственного университета (г. Москва).
