Методы коррекции несовместных систем линейных уравнений и неравенств с блочной структурой и их применение к задачам обработки информации тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат физико-математических наук Ле Ньят Зюи

• Ле Ньят Зюи
• кандидат физико-математических наук
• 2012

Оглавление диссертации кандидат физико-математических наук Ле Ньят Зюи

Содержание

ВВЕДЕНИЕ

ГЛАВА 1. Коррекция и декомпозиция несовместных блочных систем линейных алгебраических уравнений и неравенств с квадратичными критериями

1.1. Постановки задач блочной коррекциии

1.2. Коррекция и декомпозиция несовместных блочных СЛАУ

1.3. Коррекция несовместных систем неравенств

1.4. Выводы к первой главе

ГЛАВА 2. Коррекция и декомпозиция несовместных блочных СЛАУ и

неравенств с минимаксными критериями

2.1. Постановки минимаксной задачи коррекции

2.2. Решение задач коррекции СЛАУ с минимаксными критериями

2.2.1. Редукция задач коррекции с минимаксными критериями к задачам условной минимизации

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

2.2.3. Условия неразрешимости задач коррекции системы линейных уравнений с минимаксными критериями

2.3. Решение задач коррекции систем неравенств с минимаксными критериями

2.3.1. Сведение задач минимаксной коррекции к задачам условной оптимизации

2.3.2. Решение вспомогательных задач методом декомпозиции

2.4. Выводы ко второй главе

ГЛАВА 3. Численные методы коррекции и декомпозиции несовместных СЛАУ и неравенств с блочной структурой и их применение к анализу и обработке данных

3.1. Алгоритмы коррекции несовместных СЛАУ и неравенств по минимуму взвешенной евклидовой нормы

3.1.1. Алгоритмы решения задачи коррекции несовместных СЛАУ

с квадратичными критериями

3.1.2. Алгоритмы решения задачи коррекции несовместных систем неравенств с квадратичными критериями

3.1.3. Вычислительные эксперименты

3.2. Алгоритмы решения задач минимаксной коррекции несовместных СЛАУ и неравенств

3.2.1. Алгоритмы решения задачи коррекции несовместных СЛАУ

с минимаксными критериями

3.2.2. Алгоритмы решения задачи коррекции несовместных систем

неравенств с минимаксными критериями

3.2.3. Вычислительные эксперименты

3.3. Выводы к третьей главе

ЗАКЛЮЧЕНИЕ

ЛИТЕРАТУРА

Введение диссертации (часть автореферата) на тему «Методы коррекции несовместных систем линейных уравнений и неравенств с блочной структурой и их применение к задачам обработки информации»

ВВЕДЕНИЕ

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

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

При решении задач оптимизации и управления проблема построения математических моделей долгое время находилась на заднем плане. В то же время для сложных процессов управления данная проблема становится весьма трудной и при этом, возможно, определяющей. От того, насколько удачно выбрана или построена модель, зачастую зависит весь успех дела. При составлении математической модели операции действуют две противоречивые тенденции. С одной стороны, исследователь стремится дать наиболее полное описание, учитывающее все действующие факторы, с тем, чтобы обеспечить адекватность модели действительности. С другой стороны, модель не должна быть чересчур громоздкой, так как иначе даже при современных технических средствах ее невозможно будет обеспечить необходимой информацией, провести анализ с достаточной степенью точности и получить обозримые результаты. Широко распространено мнение, что построение модели - это искусство. Можно сказать, что модель есть плод искусства умелого компромисса между возможностями и потребностями исследователя [40].

Традиционно было принято рассматривать только такие задачи, в которых система соотношений является непротиворечивой. Однако практика решения прикладных задач (экономических, технических и др.) показала, что моделирование сложных процессов и явлений - многошаговая процедура. При этом первоначальное описание (математическая модель) объекта, представляющее собой систему уравнений, неравенств и других соотношений (в частности предикатных), связывающих параметры или

характеристики объекта, может быть противоречивым, т.е. соответствующая система может не иметь решений, может быть несовместной. Эта несобственность (противоречивость) модели может быть вызвана неточностью данных, чрезмерным упрощением действительных связей, абсолютизацией некоторых требований и другими причинами. Более того, противоречивая модель может быть адекватным отражением действительных противоречий, а способы ее корректировки - отражением действительных процедур разрешения реальных противоречий. В этих случаях на последующих шагах «отладки» модели предпринимаются те или иные процедуры корректировки или уточнения соотношений модели и ее структуры.

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

- плохую определенность ограничений и критериальных функций (их малую изученность, сложную структуру);

- противоречивость, несогласованность друг с другом ограничений и целей;

- неоднозначность решений;

- неустойчивость моделей (в частности, эволюция моделируемого объекта и наших знаний о нем);

- неточность информации;

- переопределенность требований.

В связи с этим возникла необходимость развития теории таких моделей, методов их коррекции, алгоритмического и программного обеспечения.

Период начала систематизированных и интенсивных исследований задач многопараметрической коррекции несовместных систем линейных алгебраических уравнений (СЛАУ) пришелся на 80-е годы прошлого века. При этом в России (СССР) и за рубежом примерно в одно и то же время были независимо получены с использованием разного математического аппарата близкие результаты.

Прикладные задачи, вызвавшие обозначенные исследования, были различными. В зарубежных исследованиях указанное направление развивалось в связи с задачей обработки экспериментальных данных с помощью так называемого обобщенного метода наименьших квадратов -Total Least Squares (TLS), который является обобщением классического метода наименьших квадратов (МНК) на случай, когда шум присутствует в наблюдениях как зависимых, так и независимых переменных. Предполагая, что погрешности всех переменных подчиняются нормальному закону распределения с одними и теми же средним и дисперсией, было получено статистическое обоснование TLS как метода, дающего оценки неизвестных параметров линейной модели, гарантирующего максимум функции правдоподобия. Как правило, системы линейных алгебраических уравнений, обрабатываемые с помощью TLS, это переопределенные системы полного

ранга. Для сравнения - системы, возникающие при коррекции несобственных задач линейного программирования в канонической форме - как правило, являются недоопределенными. Главная задача TLS - определить квазирешение исследуемой линейной системы. В то же время, можно показать, что указанное квазирешение - это точное решение модифицированной системы, подвергшейся матричной коррекции по минимуму евклидовой нормы. Интенсивные исследования метода и его активное использование при решении прикладных задач начались в конце 80-х годов после появления работ бельгийского математика S. Van Huffel [93].

В 1993 году появилась публикация американского математика профессора Дж.Б. Розена (J.b.Rosen) с учениками [95], послужившая началом развития нового научного направления - Structured Total Least Norm Approach. В этой работе была впервые поставлена и решена задача структурной коррекции переопределенной системы. Рассматривалась СЛАУ вида Лх = Ь, в которой вектор правой части Ъ содержит неточные данные (ошибки измерения), левая часть системы - матрица А - задана неточно в силу недостаточной априорной информации. Кроме того, матрица А обладает определенной структурой.

Дальнейшее развитие такой подход к решению задач структурной матричной коррекции получил в работах Дж.Б .Розена и его научной группы [96]-[98] и в работах бельгийских математиков под руководством профессора С. Ван Хаффел [101]-[103].

Изучение методов коррекции несобственных (не имеющих решения в классическом смысле) задач математического программирования является относительно новым направлением развития теоретической информатики. Предпосылки к исследованию проблем коррекции данных несобственных задач выпуклого программирования и противоречивых систем линейных алгебраических уравнений можно проследить в работах А.Н.Тихонова [81], [82]. Систематические же исследования в данной области (с введением соответствующей терминологии) были начаты в 80-х годах (ХХ-века) И.И. Еремиными [44]-[47], его учениками и коллегами: H.H. Астафьевым [2], A.A. Ватолиным [13]-[15], Л.Д. Поповым [72], [73] и другими. В перечисленных работах рассматриваются несобственные задачи линейного и выпуклого программирования, вводится классификация несобственных задач линейного программирования [48], строится и исследуется теория двойственности, вводятся и исследуются дискретные аппроксимации решений - комитетные конструкции, предлагаются различные постановки и методы решения задач полной и частичной (правая часть системы уравнений и неравенств) параметрической коррекции и их содержательная, в основном экономическая, интерпретация. В большинстве исследований рассматривается коррекция по вектору правой части ограничений и коэффициентам вектора целевой функции. Ф.П. Васильевым [9] рассматривались методы коррекции правой части ограничений двойственной пары задач линейного программирования, причем все вспомогательные задачи были также задачами линейного программирования.

В конце 90-х годов в ВЦ им. А.А. Дородницына РАН и Mill У появился другой центр исследования несовместных систем линейных алгебраических уравнений и несобственных задач линейного программирования под руководством профессора В.А. Горелика (В.И. Ерохин, В.А. Кондратьева, О.В. Муравьева, P.P. Ибатуллин, Р.В. Печенкин, И.А. Золтоева и др.) [19]—[31], [35]—[39]. Указанными авторами широко исследовалась коррекция несовместных систем линейных алгебраических уравнений с условием неотрицательности решения, показана их тесная связь с задачами матричной коррекции несобственных задач линейного программирования. В их работах рассмотрены несобственные задачи линейного программирования 1-го и 3-го рода в классификации [48], т.е. задачи линейного программирования с несовместными системами ограничений. В качестве вспомогательных, решены задачи коррекции несовместных систем линейных уравнений и неравенств.

В монографии В.А. Горелика и В.И. Ерохина [21] приведено систематизированное описание методов решения задач оптимальной многопараметрической (матричной) коррекции несовместных систем линейных алгебраических уравнений с критериями оптимальности, построенными с использованием евклидовой нормой. Исследованы задачи коррекции, в которых часть элементов матрицы коэффициентов системы или часть элементов расширенной матрицы зафиксированы (задачи с фиксированными строками, задачи с фиксированными столбцами и задачи с совокупностью фиксированных строк и столбцов). Предложены модификации для критерия оптимальности коррекции с помощью взвешивания элементов матрицы коррекции как посредством ее левого и правого умножения на невырожденные весовые матрицы, так и с использованием индивидуальных неотрицательных весов для каждого элемента. Анализируются необходимые и достаточные условия существования решения задач матричной коррекции, вид оптимальных матриц коррекции и вид множеств решений скорректированных систем. Сформулированы возможные обобщения и модификации постановок задач матричной коррекции, а также способы их регуляризации.

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

Ибатуллин P.P. [52] рассмотрел задачу коррекции всех данных для несовместных систем линейных уравнений с минимаксным критерием.

В последние годы исследования методов коррекции несовместных СЛАУ и неравенств и их приложений в различных областях ведутся весьма интенсивно [51], [56], [62]. При этом особое внимание уделяется задачам структурной коррекции, которые, с одной стороны, в наибольшей степени отвечают потребностям практики, а с другой стороны, представляют наиболее сложный математический объект, трудно поддающийся аналитическому исследованию.

В работах В.А. Горелика, В.И. Ерохина, Р.В. Печенкина [25] осуществлено развитие подхода структурной коррекции к несовместным СЛАУ с матрицами специального вида (блочной, матрицами Теплица и Вандермонда) и методов их оптимальной коррекции по квадратичному и минимаксному критериям. Получен метод решения задачи оптимальной матричной коррекции несовместных систем линейных алгебраических уравнений, обладающих блочной структурой, с использованием квадратичного и минимаксного критериев. Сформулирован критерий оптимальной коррекции несовместной системы с матрицей Теплица и Вандермонда при наличии ошибок только в левой части и предложен метод коррекции с использованием штрафных функций норм векторов невязок. Для плохо обусловленных систем со структурой Вандермонда сформулирован регуляризованный критерий коррекции, разработан численный алгоритм, реализующий поиск оптимального решения в различных нормах.

В.А. Горелик, И.А. Золтоева и Р.В. Печенкин [28] рассмотрели проблему оптимальной коррекции несовместной системы с матрицами разреженной структуры и ее применение к задачам многокритериальной оптимизации. Естественным требованием для таких систем является сохранение разреженной структуры, что вносит ограничение на структуру матрицы коррекции, но с другой стороны уменьшает размерность задачи, что приводит к построению более эффективных алгоритмов.

В работах В.А. Горелика, O.A. Клименко [31] рассмотрена задача коррекции данных несовместных линейных систем комбинаторного типа. Предложен метод решения задачи оптимальной коррекции несовместных систем линейных уравнений и неравенств комбинаторного типа с использованием квадратичного и минимаксного критериев. Для обоих критериев разработаны алгоритмы коррекции с учетом структуры задачи. Рассмотрено приложение матриц и систем комбинаторного типа и их коррекции в задачах распознавания на примере задачи кластеризации.

В качестве одной из разновидностей структурных ограничений можно рассматривать матрицы блочного типа. Они широко используются для моделирования многих дескриптивных и оптимизационных прикладных задач. Задачи блочной коррекции можно рассматривать как обобщения на случай линейных систем с блочной структурой задач многопараметрической (матричной) коррекции несовместных систем линейных алгебраических уравнений и неравенств и несобственных задач линейного

программирования общего вида. Они характеризуются дополнительными ограничениями на матрицу коррекции. В большинстве исследований исходная задача матричной коррекции данных сводится к некоторой задаче математического программирования. Исключениями могут служить работы В.А. Горелика, В.И. Ерохина, Р.В. Печенкина, И.А. Золтоева, в которых намечаются подходы к разработке соотвествующих численных методов и алгоритмов матричной коррекции данных на основе TLN (Total Least Norm -алгоритм обобщенной наименьшей нормы) и метода Ньютона [26], [28].

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

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

Объектом исследования является теория коррекции несовместных систем линейных алгебраических уравнений и неравенств.

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

Основной целью диссертации является развитие подхода структурной коррекции к несовместным система линейных алгебраических уравнений и неравенств с матрицами блочного типа и разработка декомпозиционных методов их оптимальной коррекции (по квадратичному и минимаксному критерию).

В основу исследования положена гипотеза о том, что несовместная система Ах^Ь является результатом неточно заданных исходных данных: неточно заданного вектора а, от которого параметрически зависит матрица блочного типа А = л(а), и что задачу коррекции системы можно свести к задаче оптимизации и получить такие оптимальные решения, чтобы гарантировать совместность и структурный вид скорректированной системы, при условии что поправка минимальна.

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

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

2. Разработку методов матричной коррекции несовместных систем линейных уравнений и неравенств, обладающих блочной структурой.

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

4. Исследование условия неразрешимости задач коррекции блочных систем линейных алгебраических уравнений по минимаксному критерию.

5. Применение методов коррекции систем блочного типа к задачам обработки информации.

Методологическую основу исследования составляют современные методы линейной алгебры, математического анализа, теории оптимизации, анализа и обработки данных.

Научная новизна:

• Постановки новых задач коррекции несовместных систем линейных алгебраических уравнений и неравенств с блочной структурой.

• Новые методы решения задач оптимальной матричной коррекции несовместных блочных систем линейных алгебраических уравнений и неравенств с использованием квадратичного и минимаксного критериев, основанные на декомпозиционных схемах.

• Алгоритмы, реализующие разработанные методы.

Практическая значимость результатов. Предложенные в работе

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

Проведенные вычислительные эксперименты показывают работоспособность предлагаемых методов и алгоритмов.

Основные положения, выносимые на защиту:

• Формализация задач оптимальной коррекции структурных систем линейных алгебраических уравнений и неравенств с матрицами блочного типа при наличии ошибок в данных обеих частей системы;

• Сведение проблемы коррекции несовместных систем линейных алгебраических уравнений и неравенств, обладающей блочной структурой, при квадратичном критерии оптимальности к задаче условной оптимизации дифференцируемой функции, а при минимаксном критерии - к задачам линейного программирования;

• Построение декомпозиционных методов для решения задач коррекции обеих частей систем линейных уравнений и неравенств и при наличии ошибок только в левой части.

Апробация результатов исследования. Основные результаты, полученные в диссертации, докладывались на следующих конференциях:

1. На научно-практической конференции министерства высшего и среднего специального образования Республики Узбекистан. Ташкент, 2010 г.,

2. На всероссийской конференции «Математика, информатика и методика их преподавания». Москва, 2011 г.,

3. На научно-практической конференции молодых ученых «Интеграция научных исследований в рамках реализации приоритетных направлений науки», Mill'У (Москва, 2011г.),

а также на научно-методических семинарах кафедры теоретической информатики и дискретной математики Московского педагогического государственного университета и отдела Имитационных систем и исследования операций Вычислительного центра им. A.A. Дородницына РАН.

Публикации. Материалы, составляющие основное содержание диссертации, опубликованы в 6 печатных работах, из них 3 статьи в журналах включенных в перечень ВАК РФ [34], [57], [59], 2 статьи в сборниках конференций [32], [58], 1 статья в сборнике ВЦ РАН [33].

Структура и объем диссертации. Работа состоит из введения, трех глав, заключения и списка литературы, содержащего 104 источников. Полный объем диссертации составляет 72 страниц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

В §1.1 сформулированы задачи коррекции несовместных систем линейных алгебраических уравнений и неравенств с блочной структурой для квадратичного критерия малости коррекции, когда ошибки присутствуют в левой части и обеих частях системы. Рассмотренная задача коррекции имеет вид:

А о

о

А о

л

'•. о

о Аг

х,

Ь1

Коррекция левой части системы:

ап

О

а2+н2

А +Н1 о

о

Коррекция обеих частей системы:

ап

О А,

О

+ #*

х,

А+н 1 о

о

А+Н г

О А,

О

ио

ъх

Ък + Ик

Элементы матриц Нк и векторов кк удовлетворяют следующим условиям:

к

к=1

—> Ш1П .

4=1

Рассмотрена структура корректируемых матриц с блочной структурой. Описаны два подхода для решения рассмотренных задач (известный ранее «сверху-снизу» и новый «снизу-вверх»).

В §1.2 предложен и обоснован новый подход «снизу-вверх» решения задачи коррекции несовместных блочных СЛАУ. Исходные задачи сведены к вспомогательным задачам условной оптимизации. Применен метод декомпозиции для решения вспомогательных задач.

В §1.3 рассмотрены оба подхода для коррекции несовместных систем неравенств с блочной структурой. Для подхода «сверху-снизу» приведены формулы первых производных оптимизируемой функции.

Вторая глава посвящена исследованию решений задачи коррекции несовместных систем линейных алгебраических уравнений и неравенств с блочной структурой для минимаксного критерия.

В §2.1 рассматривается несовместные системы линейных уравнений и неравенств с матрицами блочной структуры. В качестве их коррекции рассматриваются совместные системы

4 +Я,

о л2+н2

О Ак+Нк

и

А1 +Н1

О А2+Н2

О

О

О Ак+Нк

6, +/г,

Ък +ИК

где малость корректирующих матриц нк и векторов ик оцениваются минимаксными критериями:

пах У |/г*| -1.....К*-* I

шах

к=]

-» Ш1П, шах

пах V

Ай-

—» ГП1П ,

к=1 >,] к=1 /,_/ д^НН^ т'п' да* НН^ М-*т1п:

К К

тах|/г^ -> тт, тахй,* —» гат,

к=1

Иу, Ьу - элементы матрицы коррекции Нк, [нк -¡гк].

Приведены фундаментальные определения и соотношения, на основе которых сведены исходные задачи к вспомогательным задачам линейного и нелинейного программирования в разделах 2.2, 2.3.

В §2.2 показан процесс редукции задачи минимаксной коррекции СЛАУ блочного вида к задачам математического программирования. Приводятся методы декомпозиции для решения вспомогательных задач условной минимизации, а также условия неразрешимости задач коррекции системы линейных уравнений с минимаксными критериями.

В §2.3 описываются алгоритмы, разработанные для решения задач коррекции систем неравенств с минимаксными критериями.

Алгоритмы матричной коррекции основы на сведении исходной задачи к задаче условной минимизации (в том числе к серии задач линейного и нелинейного программирования), для решения которой можно использовать методы декомпозиции.

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

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

Заключение содержит основные результаты и выводы диссертационной работы.

О

О

Заключение диссертации по теме «Теоретические основы информатики», Ле Ньят Зюи

3.3. Выводы к третьей главе

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

ЗАКЛЮЧЕНИЕ

В работе рассмотрены задачи матричной коррекции несовместных СЛАУ и неравенств, которые помимо несовместности обладают дополнительным свойством, а именно, определенной структурой, связанной с природой задачи. Все задачи коррекции рассматривались в двух постановках: коррекции подвергается матрица коэффициентов системы СЛАУ и неравенств (матрица А), или расширенная матрица (левая и правая часть системы [А -б]). Для такого рода задач предложены методы минимальной коррекции матрицы (расширенной матрицы) системы с сохранением структуры матрицы. Ограничением на матрицу коррекции является требование блочной структуры, т.к. скорректированная матрица должна обладать блочной, структурой, аналогичной исходной матрице системы.

В качестве критериев малости нормы матрицы коррекции были использованы квадратичный и минимаксный критерии. Приведены примеры и вычислительные эксперименты применения разработанных методов и алгоритмов к анализу и обработке данных.

Получены следующие результаты:

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

2. Для задачи коррекции системы линейных уравнений с матрицами блочного типа рассмотрены различные случаи коррекции: коррекция левой части и коррекция обеих частей системы. В качестве критерия минимальности коррекции использовались два критерия -квадратичный и минимаксный критерии. Для обоих случаев и обоих критериев разработан новый подход к решению задач коррекции, учитывающий блочную структуру и позволяющий применить схемы декомпозиции.

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Ле Ньят Зюи, 2012 год

ЛИТЕРАТУРА

1. Алберт А. Регрессия, псевдоинверсия и рекуррентное оценивание. М.: Наука, 1997. 224 с.

2. Астафьев H.H. О мере несовместности системы линейных уравнений с требованием неотрицательности // Дискретный анализ и исследование операций: М-ый Российской конф. - Новосибирск: Изд-во Ин-та Математики СО РАН. 2004. С. 120.

3. Ашманов С.А. Линейное программирование. М.: Наука, 1982. 134 с.

4. Бакушинский А.Б., Гончарский A.B. Некорректные задачи. Численные методы и приложения. М.: Изд-во Московского университета, 1989. 199с.

5. Беллман Р. Введение в теорию матриц. М.: Наука, 1969. 367 с.

6. Беллман Р. Динамическое программирование // И.М. Андреевой, A.A. Корбута, И.В. Романовского, И.Н. Соколовой; пер с англ. - М.: Изд-во Иностранной Литературы, 1960. 400 с.

7. Белолипецкий A.A., Горелик В.А. Экономико-математические методы. М.: Изд-во "Академика", 2010. 368 с.

8. Васильев Ф.П. Численные методы решения экстремальных задач. М.: Наука, 1988. 552 с.

9. Васильев Ф.П., Иваницкий А.Ю. Линейное программирование. М.: Изд-во "Факториал Пресс", 2003. 352 с.

10. Васильев Ф.П., Стукалов A.C. Аппроксимация равновесной задачи по аргументу // Журн. вычисл. матем. и матем. физ. 2004. Т. 44. № 11. С. 1972-1982.

11. Васильев Ф.П. Регуляризация некоторых методов минимизации высокого порядка при неточных исходных данных // Журн. вычисл. матем. и матем. физ. 1985. Т. 25. № 4. С. 492-499.

12.Васильев Ф.П., Морозов В.В., Ячимович М. Оценка скорости сходимости метода регуляризации для задачи линейного программирования // Журн. вычисл. матем. и матем. физ. 1989. Т. 29. № 4. С. 631-635.

13. Ватолин A.A. Метод аппроксимации несобственной задачи выпуклого программирования. В кн.: Несобственные задачи оптимизации. Свердловск: УНЦ АН СССР. 1982. С. 67-74.

14 .Ватолин A.A. Апроксимация несобственных задач линейного программирования по критерию евклидовой нормы // Журн. вычисл. матем. и матем. физ. 1984. Т. 24. № 12. С. 1907-1908.

15. Ватолин A.A. О коррекции расширенной матрицы несовместной системы линейных неравенств и уравнений // Комбинаторные, алгебраические и вероятностные методы дискретного анализа. Горький. 1989. С. 40-54.

16. Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984. 319 с.

17. Гантмахер Ф.Р. Теория матриц. М.: Наука, 1988. 552 с.

18. Голуб Дж., ВанЛоун Ч. Матричные вычисления. М.: Мир, 1999. 548 с.

19. Горелик В.А. Матричная коррекция задачи линейного программирования с несовместной системой ограничений // Журн. вычисл. матем. и матем. физ. 2001. Т. 41. № 11. С. 1697-1705.

20. Горелик В.А. Методы коррекции данных в задачах многокритериальной оптимизации // Труды VI Московской международной конференции по исследованию операций (ORM2010) / Отв. ред. П.С. Краснощеков, A.A. Васин. -М.: МАКС Пресс, 2010. С. 180-181.

21 .Горелик В.А., Ерохин В.И. Оптимальная матричная коррекция несовместных систем линейных алгебраических уравнений по минимуму евклидовой нормы. М.: ВЦ РАН, 2004. 193 с.

22. Горелик В.А., Ерохин В.И. Оптимальная (по минимуму полиэдральной нормы) матричная коррекция несовместных систем линейных алгебраических уравнений и несобственных задач линейного программирования // Моделирование, декомпозиция и оптимизация сложных динамических процессов. М.: ВЦ РАН, 2004. С. 35-63.

23 .Горелик В.А., Ерохин В.И., Муравьева О.В. Некоторые задачи аппроксимации матриц коэффициентов несовместных систем линейных уравнений и несобственных задач линейного программирования // Моделирование, декомпозиция и оптимизация сложных динамических процессов. М.: ВЦ РАН, 2001. С. 57-88.

24. Горелик В.А., Ерохин В.И., Печенкин Р.В. Матричная коррекция несовместных линейных систем с матрицами Теплица (Ганкеля) // Моделирование, декомпозиция и оптимизация сложных динамических процессов. М.: ВЦ РАН, 2003. С. 41-73.

25. Горелик В.А., Ерохин В.И., Печенкин Р.В. Численные методы коррекции несобственных задач линейного программирования и структурных систем уравнений. М.: ВЦ РАН, 2006. 154 с.

26. Горелик В.А., Ерохин В.И., Печенкин Р.В. Оптимальная матричная коррекция несовместных систем линейных алгебраических уравнений с блочными матрицами коэффициентов // Дискрет, анализ и исслед. опер. 2005. Сер. 2. Т. 12. № 2. С. 3-22.

27. Горелик В.А., Ерохин В.И., Печенкин Р.В. Минимаксная матричная коррекция несовместимых систем линейных алгебраических уравнений с блочными матрицами коэффициентов // Изв. РАН. Теория и системы управления. 2006. № 5. С. 52-62.

28. Горелик В.А., Золтоева H.A., Печенкин Р.В. Методы коррекции несовместных линейных систем с разрешенными матрицами // Дискрет, анализ и исслед. опер. Сер. 2. 2007. Т. 14. № 2. С. 62-75.

29. Горелик В.А., Ибатуллин P.P. Коррекция системы ограничений задачи линейного программирования с минимаксным критерием // Моделирование, декомпозиция и оптимизация сложных динамических процессов. М.: ВЦ РАН, 2001. С. 89-107.

30. Горелик В.А., Кондратьева В.А. Параметрическое программирование и несобственные задачи линейной оптимизации // Моделирование,

декомпозиция и оптимизация сложных динамических процессов. М.: ВЦ РАН, 1999. С. 57-82.

31. Горелик В.А., Клименко O.A. Методы коррекции несовместных линейных систем уравнений и неравенств комбинаторного типа и их применение к задачам классификации [Электронный ресурс] // Наука и образование: электронное научно-техническое издание / Моск. гос. техн. ун-т им. Н.Э. Баумана. 2010. № 7.

32. Горелик В.А., Jle Нъят Зюи. Коррекция несовместных систем линейных неравенств с матрицами блочной структуры // Доклады научно-практической конференции министерства высшего и среднего специального образования Республики Узбекистан. Ташкент, 2010. С. 342-353.

33. Горелик В.А., Ле Нъят Зюи. Некоторые результаты по проблематике коррекции несовместных систем уравнений и неравенств с матрицами блочной структуры // Моделирование, декомпозиция и оптимизация сложных динамических процессов. М.: ВЦ РАН, 2011. С. 51-67.

34. Горелик В.А., Ле Нъят Зюи. Метод декомпозиции в задачах минимаксной коррекции несовместных систем уравнений с матрицами блочной структуры // Вестник Тверского государственного университета. Серия: Прикладная математика, 2011. № 4. С. 83-92.

35.Горелик В.А., Муравьева О.В. Необходимые и достаточные условия существования минимальной матриц в задаче коррекции несовместной системы линейных уравнений // Моделирование, декомпозиция и оптимизация сложных динамических процессов. М.: ВЦ РАН, 2000. С. 14-20.

36. Горелик В.А., Муравьева О.В. Задача аппроксимации с коррекцией всех данных // Моделирование, декомпозиция и оптимизация сложных динамических процессов. М.: ВЦ РАН, 2000. С. 21-32.

37. Горелик В.А., Муравьева О.В. Коррекция несовместной системы линейных уравнений с дополнительными ограничениями // Декомпозиционные методы в математическом моделировании. Тезисы докладов 1-й Московской конференции. М.: ВЦ РАН, 2001. С. 36-37.

38. Горелик В.А., Муравьева О.В. Устойчивость решения системы линейных неравенств // Декомпозиционные методы в математическом моделировании и информатике. Тез. докл. 2-ой Московской конференции. М.: ВЦ РАН, 2004. С. 40.

39. Горелик В.А., Муравьева О.В. Матричная коррекция данных в задачах оптимизации и классификации // Моделирование, декомпозиция и оптимизация сложных динамических процессов. М.: ВЦ РАН, 2004. С. 94-120.

40. Горелик В.А., Ушаков НА. Исследование операций. М.: Машиностроение, 1986.

41. Демьянов В.Ф., Малоземов В.Н. Введение в минимакс. М.: Наука, 1972. 368 с.

42.Джеймс Ортега, Вернер Рейнболдм. Итерационные методы решения нелинейных систем уравнений со многими неизвестными // Э.В. Вершкова, Н.П. Жидкова, И.В. Коновальцева; пер с англ. -М.: Мир, 1975. 600 с.

43. Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. М.: Наука, 1982. 432 с.

44. Еремин И.И. Двойственность в линейной оптимизации. Екатеринбург: Изд-во УрО РАН, 2001. 179 с.

45. Еремин И.И. Двойственность для несобственной задачи линейного программирования и методы их коррекции. В кн.: Несобственные задачи оптимизации. Свердловск: УНЦ АН СССР, 1982. С. 3-10.

46. Еремин И.И, Противоречивые модели оптимального планирования. М.: Наука, 1988. 160 с.

47. Еремин И.И. Линейная оптимизация и системы линейных неравенств. М.: Издательский центр "Академия", 2007. 256 с.

48. Еремин ИМ., Мазуров В.Д., Астафьев H.H. Несобственные задачи линейного и выпуклого программирования. М.: Наука, 1983. 336 с.

49. Ерохин В.И. Свойства оптимальной одноранговой коррекции матриц коэффициентов несовместных неоднородных линейных моделей // Дискрета, анализ и исслед. операций. Сер. 2. 2002. Т. 9. № 1. С. 33-60.

50.Ерохин В.И, Красников A.C. Матричная коррекция двойственной пары несобственных задач линейного программирования с блочной структурой // Журн. вычисл. матем. и матем. физ. 2008. Т. 48. № 1. С. 80-89.

51. Золтоева И.А. Методы коррекции данных для формализации и решения задач многокритериальной оптимизации: Дисс. ... канд. физ.-мат. наук: 05.13.17.-М., 2007.

52. Ибатуллин P.P. Методы коррекции и аппроксимации несобственных задач оптимизации и управления с минимаксным критерием: Дисс. ... канд. физ.-мат. наук: 05.13.17. -М., 2002.

53. Икрамов Х.Д. Задачник по линейной алгебре. М.: Наука, 1975. 320 с.

54. Клименко O.A. Методы коррекции данных несовместных линейных систем комбинаторного типа: Дисс. ... канд. физ.-мат. наук: 05.13.17. -М., 2010.

55. Кондратьева В.А. Несобственные задачи линейной оптимизации и параметрическое программирование: Дисс. ... канд. физ.-мат. наук: 05.13.17.-М., 2000.

56. Красников A.C. Матричная коррекция противоречивых данных в линейных оптимизационных моделях: Дисс. ... канд. физ.-мат. наук: 05.13.17.-М., 2010.

57. Jle Нъят Зюи. Метод декомпозиции в задачах коррекции несовместных систем линейных неравенств с матрицами блочной структуры. // Журн. вычисл. матем. и матем. физ. 2011. Т. 51. № 10. С. 1796-1805.

58. Ле Нъят Зюи. Коррекция несовместных систем линейных неравенств с матрицами блочной структуры по минимаксному критерию // Сборник

материалов Всероссийской конференции "Математика, информатика и методика их преподавания". М.: Mill У, 2011. С. 66-68.

59. Jle Ньят Зюи. Коррекция несовместных систем линейных неравенств с матрицами блочной структуры по минимаксному критерию // Вестник Моск. ун-та. Сер. 15. Вычислит, матем. и киберн. 2011. № 4. С. 18-25.

60.Лоран П.-Ж. Аппроксимация и оптимизация // Ю.С. Завьялова, P.A. Звягиной, Б.И Квасова, В.И. Шмырева; пер с франц. - М.: Мир, 1975. -496 с.

61. Лэсдон Л. С. Оптимизация больших систем // Т.Н. Первозванской., Г.В. Шалабина; пер с англ. - М.: Наука, 1975. 432 с.

62. Матросов В.Л., Горелик В.А., Жданов С.А., Муравьева О.В. Применение методов коррекции несобственных задач линейного программирования к задаче классификации // Научные труды Московского педагогического государственного университета. Серия: естественные науки. - М.: Прометей, 2005. С. 55-60.

63. Матросов B.R., Горелик В.А., Жданов С.А., Муравьева О.В., Уголъникова Б.З. Теоретические основы информатики. Учебное пособие. М.: Mill У, 2005. 420с.

64. Матросов B.JI., Горелик В.А., Муравьева О.В. Некоторые приложения методов матричной коррекции к задачам обработки данных // Сборник материалов Всероссийской конференции "Математика, информатика и методика их преподавания". М.: МШ У, 2011. С. 68-72.

65. Мауэр И. Штрафная константа в блочном программировании // Изв. АН ЭССР, Физика, математика. 1971. Т. 20. № 4. С. 401-405.

66. Мину. М. Математическое программирование. М.: Наука, 1990. 486 с.

67. Муравьева О.В. Матричная коррекция данных для несовместных систем линейных уравнений и ее применение в задачах оптимизации и классификации: Дисс. ... канд. физ.-мат. наук: 05.13.17. — М., 2002.

68. Муравьева О.В. Возмущение и коррекция систем линейных неравенств // Управление большими системами. Выпуск 28. М.: ИПУ РАН, 2010. С.40-57.

69. Первозванский A.A., Гайцгори В.Г. Декомпозиция, агрегирование и приближенная оптимизация. М.: Наука, 1979. 344 с.

70. Печенкин Р.В. Методы коррекции несовместных систем со структурными ограничениями: Дисс. ... канд. физ.-мат. наук: 05.13.17. -М., 2006.

71. Полак Э. Численные методы оптимизации // Ф.И. Ерешко; пер с англ. -М.: Мир, 1974. 376 с.

72. Попов Л.Д. О методах аппроксимации для несобственной задачи выпуклого программирования второго и третьего рода. В кн.: Параметрическая оптимизация и методы аппроксимации несобственных задач математического программирования. Свердловск: УНЦ АН СССР, 1985. С. 89-107.

73 .Попов Л Д. Об одном методе декомпозиции в несобственном линейном программировании. В кн.: Нерегулярная двойственность в

математическом программировании. Свердловск: УрО РАН, 1990. С. 42-45.

74. Реклейтис Г., Рейеиндран А., Рэгсдел К. Оптимизация в технике: В 2-х кн. Кн. 1. Пер. с англ. М.: Мир, 1986. 350 с.

75. Реклейтис Г., Рейеиндран А., Рэгсдел К. Оптимизация в технике: В 2-х кн. Кн. 2. Пер. с англ. М.: Мир, 1986. 320 с.

76. Решетников В.Н., Сотников А.Н. Информатика — что это? М.: Радио и связь, 1989.

77. Романовский И.В. Алгоритмы решения экстремальных задач. М.: Наука, 1977. 352 с.

78. Сингх М., Титли А. Системы: декомпозиция, оптимизация и управление //

A.B. Запорожца; пер с англ. -М.: "Машиностроение", 1986. 496 с.

79. Сухарев А.Г., Тимохов A.B., Федоров В.В. Курс методов оптимизации: Учеб. пособие. 2-е изд. - М.: ФИЗМАТЛИТ, 2005. - 368 с.

80. Танаев B.C. Декомпозиция и агрегирование в задачах математического программирования. Мн.: Наука и техника, 1987. 183 с.

81. Тихонов А.Н., Арсенин В.Я. Методы решения некорректных задач. М.: Наука, 1986. 288с.

82. Тихонов А.Н. О приближенных системах линейных алгебраических уравнений. // Журн. Вычис. матем. и матем. физики, 1980. Т. 20. № 6. С.1373-1383.

83. Форсайт. Дж., Молер. К. Численное решение систем линейных алгебраических уравнений. М.: Мир, 1969.

84. Хемминг Р. В. Численные методы для научных работников и инженеров //

B.Л. Арлазарова., Г.С. Разиной., A.B. Ускова; пер с англ. - М.: Наука, 1972.400 с.

85. Хорн Р., Джонсон Ч. Матричный анализ. М.: Мир, 1989. 655 с.

86. Цурков В.И. Декомпозиция в задачах большой размерности. М.: Наука, 1981.352 с.

87. Цурков В.И. Динамические задачи большой размерности. М.: Наука, 1988. 288 с.

88. Цурков В.И. Декомпозиция в оптимизации систем с эллиптическими уравнениями // Журн. Вычис. матем. и матем. физики, 1980. Т. 20. № 5. С. 1310-1319.

89. Цурков В.И. Декомпозиция в классическом вариационном исчислении // Журн. Вычис. матем. и матем. физики, 1979. Т. 19. № 6. С. 1396-1413.

90. Цурков В.И. Метод декомпозиции на основе агрегирования в блочном программировании // Журн. Вычис. матем. и матем. физики, 1979. Т. 19. № 2. С. 343-355.

91 .Цурков В.И. Разложение на основе агрегирования управлений в динамическом программировании / Журн. Вычис. матем. и матем. физики, 1981. Т. 21. №4. с. 853-864. 92. Цурков В.И. Двухэтапная задача стохастического программирования блочного типа // Журн. Вычис. матем. и матем. физики, 1978. Т. 18. № 2.

C. 360-369.

93. Черников С.Н. Линейные неравенств. М.: Наука, 1968. 488 с.

94. Golub G.H., Van Loan C.F. An analysis of the total least squares problem // SIAM Journal on Numerical Analysis. 1980. Vol. 17. № 3. P. 883-893.

95. Rosen J.B., Park H., Glick J. Total least norm problems: formulation and solution // illUMSI research report. Minniapolis (Mn): Uni. of Minnesota Supercomput. inst., 1993, 93/223, 18p.

96. Rosen J.B., Park H., Glick J. Total least norm for linear and nonlinear structured problems, Recent advances in total least squares techniques and errors-in-variables modeling. Ed. S. Van Huffel, SIAM, pp. 203-214, 1997.

97. Rosen J.B., Park H., Glick J. Total least norm formulation and solution for structured problems. // SIAM Journal on Matrix Anal. Appl. 1996. Vol. 17. № 1. P. 110-128.

98. Rosen J.В., ParkH., Glick J. Structured total least norm for nonlinear problems // SIAM Journal on Matrix Anal. Appl. 1998. Vol. 20. № 1. P. 14-30.

99. Sanders. J. A nonlinear decomposition principle. - «Operation Reseach», v. 13, №2, 1965.

100. Van Huffel S. On the significance of nongeneric total least squares problems // SIAM Journal on Matrix Anal. Appl. 1992. Vol. 13. № 1. P. 20-35.

101. Van Huffel S., Vandewale J. The Total Least Squares problems: Computational Aspects and Analysis. Philadelphia PA: SIAM Publishing. Vol. 35. № 4. 1993. P. 660-662.

102. Van Huffel S., Vandewalle J. Analysis and solution of the nongeneric total least squares problem // SIAM Journal on Matrix Analysis and Applications. 1988. Vol. 9. № 2. P. 360-372.

103. Van Huffel S., Vandewalle J. The total least squares problem: Computational Aspects and Analysis. Philadelphia: SIAM Publishing, 1991.

104. Vatolin A.A. Parametric approximation of inconsistent systems of linear equations and inequalities. Seminarber., Humboldt-Univ. Berlin, Sekt. Math., 1986. P. 145-154.