Введение к работе
Актуальность темы исследования. В настоящее время, когда информация становится жизненно важном ресурсом, когда информационная деятельность определяется как приоритетная в процессе развития цивилизации и когда эта деятельность во всем своем широчайшем спектре в значительной степени опирается на современные достижения компьютерной техники, становится очевидной необходимость всестороннего фундаментального исследования основных понятий информатики, процессов представления, обработки, хранения и передачи информации. При этом на первый план выдвигаются задачи нахождения эффективных алгоритмов обработки и анализа информации, генерации новых знаний и принятия на их основе наиболее рациональных решений.
При решении задач оптимизации и управления проблема построения математических моделей долгое время находилась на заднем плане. В то же время для сложных процессов управления данная проблема становится весьма трудной и при этом, возможно, определяющей. От того, насколько удачно выбрана или построена модель, зачастую зависит весь успех дела. При составлении математической модели действуют две противоречивые тенденции. С одной стороны, исследователь стремится дать наиболее полное описание, учитывающее все действующие факторы, с тем, чтобы обеспечить адекватность модели действительности. С другой стороны, модель не должна быть чересчур громоздкой, так как иначе даже при современных технических средствах ее невозможно будет обеспечить необходимой информацией, провести анализ с достаточной степенью точности и получить обозримые результаты. Широко распространено мнение, что построение модели - это искусство. Можно сказать, что модель есть плод искусства умелого компромисса между возможностями и потребностями исследователя.
Традиционно было принято рассматривать только такие задачи, в которых система соотношений является непротиворечивой. Однако практика решения прикладных задач (экономических, технических и др.) показала, что моделирование сложных процессов и явлений - многошаговая процедура. При этом первоначальное описание (математическая модель) объекта, представляющее собой систему уравнений, неравенств и других соотношений, связывающих параметры или характеристики объекта, может быть противоречивым, т.е. соответствующая система может не иметь решений, может быть несовместной. Эта несобственность (противоречивость) модели может быть вызвана неточностью данных, чрезмерным упрощением действительных связей, абсолютизацией некоторых требований и другими причинами. Более того, противоречивая модель может быть адекватным отражением действительных противоречий, а способы ее корректировки -отражением действительных процедур разрешения реальных противоречий. В этих случаях на последующих шагах "отладки" модели предпринимаются те или иные процедуры корректировки или уточнения соотношений модели и ее структуры. Противоречивость можно считать одним из факторов плохой формализуемости. Существуют различные причины плохой формализуемости задачи выбора решения в моделях оптимизации, среди которых можно назвать:
плохую определенность ограничений и критериальных функций;
противоречивость, несогласованность друг с другом ограничений и целей;
неточность информации;
- переопределенность требований.
В связи с этим возникла необходимость развития теории таких моделей, методов их коррекции, алгоритмического и программного обеспечения.
В 1993 году появилась публикация американского математика профессора Дж.Б. Розена (J.b.Rosen) с учениками, послужившая началом развития нового научного направления - Structured Total Least Norm Approach. В этой работе была впервые поставлена и решена задача структурной коррекции переопределенной системы. Рассматривалась СЛАУ вида Ах = Ь, в которой вектор правой части Ъ содержит неточные данные (ошибки измерения), левая часть системы - матрица А - задана неточно в силу недостаточной априорной информации. Кроме того, матрица А обладает определенной структурой.
Параллельно с зарубежными исследованиями аналогичные работы, по с упором на несобственные задачи математического программирования (ЗМП), проводились и в России научной школой Института математики и механики УрО РАН под руководством академика РАН И.И. Еремина (А.А. Ватолин, В.Д. Мазуров, Л.Д. Попов и др.), а впоследствии и научной группой Вычислительного центра им. А.А. Дородницына РАН и Mill У под руководством В.А. Горелика (В.И. Ерохин, В.А. Кондратьева, О.В. Муравьева, P.P. Ибатуллин, Р.В. Печенкин и др.).
В последние годы исследования методов коррекции несовместных СЛАУ и неравенств и их приложений в различных областях ведутся весьма интенсивно. При этом особое внимание уделяется задачам структурной коррекции, которые, с одной стороны, в наибольшей степени отвечают потребностям практики, а с другой стороны, представляют наиболее сложный математический объект, трудно поддающийся аналитическому исследованию.
В работах В.А. Горелика, В.И. Ерохина, Р.В. Печенкина осуществлено развитие подхода структурной коррекции к несовместным СЛАУ с матрицами специального вида (блочной, матрицами Теплица и Вандермонда) и методов их оптимальной коррекции по квадратичному и минимаксному критериям. Получен метод решения задачи оптимальной матричной коррекции несовместных систем линейных алгебраических уравнений, обладающих блочной структурой, с использованием квадратичного и минимаксного критериев. Сформулирован критерий оптимальной коррекции несовместной системы с матрицей Теплица и Вандермонда при наличии ошибок только в левой части и предложен метод коррекции с использованием штрафных функций норм векторов невязок. В работах В.А. Горелика, О.А. Клименко рассмотрена задача коррекции данных несовместных линейных систем комбинаторного типа. Предложен метод решения задачи оптимальной коррекции несовместных систем линейных уравнений и неравенств комбинаторного типа с использованием квадратичного и минимаксного критериев. Для обоих критериев разработаны алгоритмы коррекции с учетом структуры задачи. Рассмотрено приложение матриц и систем комбинаторного типа и их коррекции в задачах распознавания на примере задачи кластеризации.
В качестве одной из разновидностей структурных ограничений можно рассматривать матрицы блочного типа. Они широко используются для моделирования многих дескриптивных и оптимизационных прикладных задач. Задачи блочной коррекции можно рассматривать как обобщения на случай линейных систем с блочной структурой задач многопараметрической (матричной)
коррекции несовместных систем линейных алгебраических уравнений и неравенств и несобственных задач линейного программирования общего вида. Они характеризуются дополнительными ограничениями на матрицу коррекции. В большинстве исследований исходная задача матричной коррекции данных сводится к некоторой задаче математического программирования. Исключениями могут служить работы В.А. Горелика, В.И. Ерохина, Р.В. Печенкина, И.А. Золтоева, в которых намечаются подходы к разработке соотвествующих численных методов и алгоритмов матричной коррекции данных на основе TLN (Total Least Norm -алгоритм обобщенной наименьшей нормы) и метода Ньютона.
Необходимо отметить, что в блочных задачах математического программирования особую актуальность приобрели методы декомпозиции, позволяющие отчасти решить проблему размерности. В то же время, указанные выше подходы приводят к задачам коррекции, которые по своей структуре не поддаются декомпозиции. Кроме того, не рассматривались системы неравенств с блочной структурой.
Таким образом, актуальная научная проблема заключается в разработке математического аппарата исследования структурных задач оптимальной матричной коррекции несовместных систем линейных алгебраических уравнений и неравенств блочного типа и построении эффективных численных методов и алгоритмов решения таких задач, реализующих идеи декомпозиции.
Объектом исследования является теория коррекции несовместных систем линейных алгебраических уравнений и неравенств.
Предметом исследования составляют вопросы структурной матричной коррекции несовместных систем линейных алгебраических уравнений и неравенств блочного типа с различными матричными и векторными нормами в качестве критерия минимальности коррекции.
Цель исследования состоит в развитии подхода структурной коррекции к несовместным система линейных алгебраических уравнений и неравенств с матрицами блочного типа и разработка декомпозиционных методов их оптимальной коррекции (по квадратичному и минимаксному критерию).
В основу исследования положена гипотеза о том, что несовместная система АхкЪ является результатом неточно заданных исходных данных и что задачу коррекции системы можно свести к задаче оптимизации и получить такие оптимальные решения, чтобы гарантировать совместность и структурный вид скорректированной системы, при условии что поправка минимальна.
Для реализации поставленной цели и на основе сформулированной гипотезы потребовалось решить следующие задачи:
-
Постановки задач коррекции несовместных систем линейных уравнений и неравенств блочного типа с различными критериями минимальности коррекции.
-
Разработку методов матричной коррекции несовместных систем линейных уравнений и неравенств, обладающих блочной структурой.
-
Разработку вычислительных алгоритмов для поиска оптимального решения задач коррекции несовместных систем линейных уравнений и неравенств с матрицами блочного типа.
-
Исследование условия неразрешимости задач коррекции блочных систем линейных алгебраических уравнений по минимаксному критерию.
-
Применение методов коррекции систем блочного типа к задачам обработки информации.
Методологическую основу работы составляют современные методы линейной алгебры, математического анализа, теории оптимизации, анализа и обработки данных.
Научная новизна:
Постановки новых задач коррекции несовместных систем линейных алгебраических уравнений и неравенств с блочной структурой.
Новые методы решения задач оптимальной матричной коррекции несовместных блочных систем линейных алгебраических уравнений и неравенств с использованием квадратичного и минимаксного критериев, основанные на декомпозиционных схемах.
Алгоритмы, реализующие разработанные методы.
Практическая значимость результатов. Предложенные в работе методы и алгоритмы построения и анализа решений задач коррекции несовместных блочных систем линейных алгебраических уравнений и неравенств могут быть использованы в задачах обработки зашумленных данных, анализа моделей информационных процессов, прогнозирования и управления, относящихся к области исследования специальности 05.13.17 - теоретические основы информатики. Разработанные методы решения таких задач позволяют эффективно строить квадратичные и минимаксные аппроксимации для противоречивых моделей.
Проведенные вычислительные эксперименты показывают работоспособность предлагаемых методов и алгоритмов.
Основные положения, выносимые на защиту:
Формализация задач оптимальной коррекции структурных систем линейных алгебраических уравнений и неравенств с матрицами блочного типа при наличии ошибок в данных обеих частей системы;
Сведение проблемы коррекции несовместных систем линейных алгебраических уравнений и неравенств, обладающей блочной структурой, при квадратичном критерии оптимальности к задаче условной оптимизации дифференцируемой функции, а при минимаксном критерии - к задачам линейного программирования;
Построение декомпозиционных методов для решения задач коррекции обеих частей систем линейных уравнений и неравенств и при наличии ошибок только в левой части.
Апробация результатов исследования. Основные результаты, полученные в диссертации, докладывались на следующих конференциях:
-
На научно-практической конференции министерства высшего и среднего специального образования Республики Узбекистан. Ташкент, 2010 г.,
-
На всероссийской конференции «Математика, информатика и методика их преподавания». Москва, 2011 г.,
-
На научно-практической конференции молодых ученых «Интеграция научных исследований в рамках реализации приоритетных направлений науки», МЛІ У (Москва, 2011г.),
а также на научно-методических семинарах кафедры теоретической информатики и дискретной математики Московского педагогического государственного университета и отдела Имитационных систем и исследования операций Вычислительного центра им. А. А. Дородницына РАН.
Публикации. Материалы, составляющие основное содержание диссертации, опубликованы в 6 печатных работах, из них 3 статьи в журналах включенных в перечень ВАК РФ [1-3], 1 статья в сборнике ВЦ РАН [4], 2 статьи в сборниках конференций [5, 6].
Структура и объем диссертации. Работа состоит из введения, трех глав, заключения и списка литературы, содержащего 104 источников. Объем диссертации составляет 72 страниц.
