Авторефераты по всем темам  >>  Авторефераты по техническим специальностям

На правах рукописи

ЛЕ Ньят Зюи

МЕТОДЫ КОРРЕКЦИИ НЕСОВМЕСТНЫХ СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ И НЕРАВЕНСТВ С БЛОЧНОЙ СТРУКТУРОЙ И ИХ ПРИМЕНЕНИЕ К ЗАДАЧАМ ОБРАБОТКИ ИНФОРМАЦИИ

05.13.17 - теоретические основы информатики

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 2012

Работа выполнена на кафедре теоретической информатики и дискретной математики математического факультета Московского педагогического государственного университета

Научный консультант: доктор физико-математических наук, профессор Горелик Виктор Александрович

Официальные оппоненты: Цурков Владимир Иванович доктор физико-математических наук, профессор, заведующий отделом сложных систем Вычислительного центра им. А.А. Дородницына РАН.

Кондратьева Виктория Александровна кандидат физико-математических наук, доцент кафедры Информационные системы и дистанционные технологии факультета Автоматизация и управление Московского государственного технического университета МАМИ.

Ведущая организация: Московский государственный университет им. М.В. Ломоносова.

Защита диссертации состоится л21 мая 2012 г. в 17 часов на заседании диссертационного совета Д 212.154.32 при Московском педагогическом государственном университете по адресу: 107140, г. Москва, ул. Краснопрудная, д. 14, математический факультет МПГУ, ауд. 401.

С диссертацией можно ознакомиться в библиотеке Московского педагогического государственного университета по адресу: 119991, г. Москва, ул.

Малая Пироговская, д. 1.

Автореферат разослан л ___ апреля 2012 г.

Ученый секретарь диссертационного совета Муравьева Ольга Викторовна

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

Противоречивость можно считать одним из факторов плохой формализуемости.

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

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

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

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

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

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

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

Параллельно с зарубежными исследованиями аналогичные работы, по с упором на несобственные задачи математического программирования (ЗМП), проводились и в России научной школой Института математики и механики УрО РАН под руководством академика РАН И.И. Еремина (А.А. Ватолин, В.Д. Мазуров, Л.Д. Попов и др.), а впоследствии и научной группой Вычислительного центра им. А.А. Дородницына РАН и МПГУ под руководством В.А. Горелика (В.И. Ерохин, В.А. Кондратьева, О.В.

Муравьева, Р.Р. Ибатуллин, Р.В. Печенкин и др.).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. На научно-практической конференции министерства высшего и среднего специального образования Республики Узбекистан. Ташкент, 2010 г., 2. На всероссийской конференции Математика, информатика и методика их преподавания. Москва, 2011 г., 3. На научно-практической конференции молодых ученых Интеграция научных исследований в рамках реализации приоритетных направлений науки, МПГУ (Москва, 2011г.), а также на научно-методических семинарах кафедры теоретической информатики и дискретной математики Московского педагогического государственного университета и отдела Имитационных систем и исследования операций Вычислительного центра им. А.А. Дородницына РАН.

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

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

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

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

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

Рассмотрим задачу матричной коррекции несовместных систем линейных алгебраических уравнений Ax = b, x и задачу коррекции несовместных систем неравенств Ax b, x 0, где матрица A RM N имеет следующую блочную структуру:

A A 0 L 0 A = 0 A2 O M, M O L 0 L 0 AK K K 0 k = M A0 Rm N, Ak Rm nk, k =1,K,K,, = N.

mk nj k=0 j=Введем в эти задачи дополнительные требования совместности A0 x = b0, x и A0 x b0, x 0 и неизменимости матрицы A0.

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

k Hk Rm nk Задача 1.1. Требуется найти матрицы, такие, что система A b A + H1 0 L 0 x1 b 0 A2 + H2 O M M = (1) M M O O b xK K 0 L 0 AK + H K имеет неотрицательное решение и выполнено требование минимальности суммы квадратов евклидовых норм матриц коррекции K H min.

k E k =k Hk Rm nk Задача 1.2. Требуется найти матрицы, такие, что система A b A + H1 0 L 0 x1 b 0 A2 + H2 O M M (2) M M O O b xK K 0 L 0 AK + H K имеет неотрицательное решение и выполнено условие K H min.

k E k =k k Hk Rm nk hk Rm Задача 1.3. Требуется найти матрицы и векторы, такие, что система A b A + H1 0 L 0 x1 b1 + h1 0 A2 + H O M M = (3) M M O O b + hK xK K 0 L 0 AK + H K имеет неотрицательное решение и выполнено условие K [H - hk ] min.

k E k =k k Hk Rm nk hk Rm Задача 1.4. Требуется найти матрицы и векторы, такие, что система A b A + H1 0 L 0 x1 b1 + h1 0 A2 + H2 O M M (4) M M O O b + hK xK K 0 L 0 AK + H K имеет неотрицательное решение и выполнено условие K [H - hk ] min.

k E k =Рассмотрена структура корректируемых матриц с блочной структурой. Описаны два подхода для решения рассмотренных задач (известный ранее сверхуЦснизу и новый снизу-вверх). Основной идеей, лежащей в основе подхода снизу-вверх, является возможность сведения исходных задач к вспомогательным задачам условной оптимизации и применения схемы декомпозиции.

Рассмотрим коррекцию задачи 1.1. Систему (1) при фиксированном x можно переписать как совокупность K систем линейных алгебраических уравнений с неизвестной матрицей H :

k (Ak + Hk )xk = bk Hk xk = bk - Ak xk. (5) Единственным решением уравнения (5) относительно неизвестной матрицы H, k обладающим минимальной евклидовой нормой при xk 0 будет матрица * + H = (bk - Ak xk )xk, (6) k + где xk - псевдообратный вектор-строка к вектору xk.

При использовании взвешенной евклидовой нормы (квадратичный критерий) будет справедлива формула bk - Ak xk * H =.

k xk Теорема 1.1. Задача коррекции 1.1 эквивалентна задаче математического программирования вида:

K bk - Ak xk f (x) = min, (7) x k =1 xk K A0k xk = b0, k =xk 0, k = 1,K, K, * а именно, если (xk, f (x)) - решение задачи (7), то матрицы коррекции H k вычисляются по формуле (6).

Задача 1.3 - поиск оптимальной расширенной матрицы коррекции, путем аналогичных преобразований может быть сведена к аналогиной задаче МП.

Теорема 1.2. Задача коррекции 1.3 эквивалентна задаче математического программирования вида:

~ K Ak zk g(z) = min, (8) z k =1 zk K ~ ~ A0k zk = b0, k =zk 0, k = 1,..., K, где xk nk ~ k Ak = [Ak - bk ] Rm (nk +1), zk = R+ +1, A0 = [A01 | K A0K ], A0k Rm nk, ~ ~ M 0 0 A0k = [A0k 1m ] Rm (nk +1), 1m = Rm, b0 = b0 + K 1m Rm, 0 0 1 * а именно, если (zk, g*(z*)) - решение задачи (8), то расширенные матрицы коррекции [Hk - hk] вычисляются по формуле ~ * * + [H - hk ]= -Ak zk zk.

k Обратимся к исследованию задачи 1.2, систему неравенств (2) перепишим как K систем линейных неравенств (Ak + Hk )xk bk. (9) Вводя дополнительные переменные yk, yk 0, k = 1,..., K, из (9) можно записать следующие равенства (Ak + Hk )xk + yk = bk Hk xk = bk - yk - Ak xk, yk 0. (10) k При фиксированном векторе xk Rn решение (10) относительно неизвестной матрицы H, обладающее минимальной евклидовой нормой существует при любом k xk 0 и задается формулой:

* + H = (bk - Ak xk - yk )xk, (11) k причем bk - Ak xk - yk * H =.

k xk Теорема 1.3. Задача коррекции 1.2 эквивалентна задаче математического программирования вида:

K bk - Ak xk - yk (x, y)= min, (12) x,y k =1 xk K A0k xk b0, k =xk 0, yk 0, k = 1,K, K, * * а именно, если (xk, yk, (x*, y*)) - решение задачи (12), тогда матрицы коррекции H k вычисляются по формуле (11).

Задача 1.4 - поиск оптимальной расширенной матрицы коррекции, путем аналогичных преобразований может быть сведена к задаче условной оптимизации.

Теорема 1.4. Задача коррекции 1.4 эквивалентна задаче математического программирования вида:

K bk - Ak xk - yk (x, y) = min, (13) x, y k =1 xk + K A0k xk b0, k =xk 0, yk 0, k = 1,K, K, * * а именно, если (xk, yk, (x*, y*)) - решение задачи (13), тогда расширенные матрицы коррекции [Hk - hk] вычисляются по формуле + [H - hk ]= (bk - Ak xk - yk )zk.

k Рассматриваются оба подхода для коррекции несовместных систем неравенств с блочной структурой. Для подхода сверху-снизу приведены формулы первых производных оптимизируемой функции задач (12), (13).

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

k Hk Rm nk Задача 2.1. Требуется найти матрицы, такие, что система (1) имеет неотрицательное решение и выполнено условие k maxK hij min, k =1,K, i, j k где hij - элемент матрицы коррекции H.

k k k Hk Rm nk hk Rm Задача 2.2. Требуется найти матрицы и векторы, такие, что система (3) имеет неотрицательное решение и выполнено условие k max h min, ij k =1,K,K i, j k где h - элемент расширенной матрицы коррекции [Hk - hk ].

ij k Hk Rm nk Задача 2.3. Требуется найти матрицы, такие, что система (1) имеет неотрицательное решение и выполнено условие K k hij min.

k =1 i, j k k Hk Rm nk hk Rm Задача 2.4. Требуется найти матрицы и векторы, такие, что система (3) имеет неотрицательное решение и выполнено условие K hijk min.

k =1 i, j k Hk Rm nk Задача 2.5. Требуется найти матрицы, такие, что система (2) имеет неотрицательное решение и выполнено условие k max{max{hij }} min.

k =1,K,K i, j k k Hk Rm nk hk Rm Задача 2.6. Требуется найти матрицы и векторы, такие, что система (4) имеет неотрицательное решение и выполнено условие max{max{hijk }} min.

k =1,K,K i, j k Hk Rm nk Задача 2.7. Требуется найти матрицы, такие, что система (2) имеет неотрицательное решение и выполнено условие K k max hij min.

i, j k =k k Hk Rm nk hk Rm Задача 2.8. Требуется найти матрицы и векторы, такие, что система (4) имеет неотрицательное решение и выполнено условие K k ij max h min.

i, j k =При решении задач минимаксной коррекции часто используются векторные нормы , и гельдеровы нормы , , с использованием которых они 1 l1 l построены, исходные задачи сводятся к решению задач математического программирования.

Теорема 2.2. Задача коррекции 2.1 эквивалентна задаче математического программирования вида:

d min, (14) d,r, y k vk bk r - Ak yk, k vk -bk r + Ak yk, K -k (r ) A0k yk = b0, k =l vk 0, 0 yk 1, yk = 1, 1T vk d, l = 1,K,nk, k =1,K, K, mk k k k где r =, r > 0, yk = r xk, k = 1,K, K, i max xk i=1,K,nk yk k а именно, если (d,r, yk ) - решение задачи (14), то xk = и матрицы коррекции k r * H вычисляются по формуле k T H = (bk - Ak xk )sk, (15) k sk - вектор, двойственный к вектору xk относительно нормы .

Теорема 2.3. Задача коррекции 2.2 эквивалентна задаче математического программирования вида:

u min, (16) u,q, p ~ Ak pk, k ~ -Ak pk, k K -1 ~ ~ (qk ) A0k pk = b0, k =l 0, 0 pk 1, pk = 1, k 1T u, mk k l = 1,K,nk +1, k =1,K, K, xk nk ~ k где Ak =[Ak -bk] Rm (nk +1), zk = R+ +1, qk =, qk >0, pk = zkqk, i 1 max zk i=1,K,nk +~ ~ 0 A0k =[A0k 1m ]Rm (nk +1), b0 =b0 + K1m Rm, 0 pk а именно, если (u,qk, pk ) - решение задачи (16), тогда zk = и расширенные qk матрицы коррекции [Hk - hk] вычисляются по формуле ~ * * T [Hk - hk]= -Ak zk wk, (17) wk - вектор, двойственный к вектору zk относительно нормы Описывается метод декомпозиции на основе метода распределения ресурсов для решения задачи (16). Схему метода декомпозиции можно описать следующим образом.

Введем в рассмотрение K новых векторов tk, tk Rm, k = 1,K, K.

~ A0k pk = tk qk, k = 1,K, K, K ~ = b0.

tk k =При фиксированных значениях векторов tk, процесс декомпозиции на каждом шаге приводит к решению K локальных задач:

uk min, (18) ~ Ak pk, k ~ -Ak pk, k ~ A0k pk = tk qk, 1T uk, mk k l 0, 0 pk 1, pk = 1, k l = 1,K,nk +1.

Здесь вводятся новые переменные uk, соответствующие tk.

Задача (18) при фиксированном l является задачей линейного программирования (ЗЛП), т.е. ее решение сводится к нахождению минимума из минимумов ЗЛП при l = 1,K,nk +1.

Итеративный метод осуществляет на каждом шаге перераспределение общего ~ ресурса b0. При этом все оптимальные значения имеют тенденцию выравниваться и стремиться к минимальному значению задачи (16) в процессе итераций. В данном случае задача координации соответствует определенным правилам перераспределения ресурсов. Процесс повторяется до тех пор, пока не выполняется неравенство maxK uk [i]- minK uk [i] , k =1,K, k =1,K, где i - номер итерации, а - заданная точность.

Теорема 2.4. Задача коррекции 2.3 эквивалентна задаче математического программирования вида:

K,vk ) min, (19) (ek k =k vk bk r - Ak yk, k vk -bk r + Ak yk, K -k (r ) A0k yk = b0, k =l vk 0, 0 yk 1, yk = 1, l = 1,K,nk, k =1,K, K.

Здесь ek - вектор-столбец размерности mk, состоящий из единиц, yk * k а именно, если (vk, r, yk) - решение задачи (19), то xk = и матрицы коррекции k r * H вычисляются по формуле (15).

k Теорема 2.5. Задача коррекции 2.4 эквивалентна задаче математического программирования вида:

K, ) min, (20) (ek k k =~ Ak pk, k ~ -Ak pk, k K -1 ~ ~ (qk ) A0k pk = b0, k =l 0, 0 pk 1, pk = 1, k l = 1,K,nk +1, k =1,K, K, pk а именно, если (,qk, pk) - решение задачи (20), тогда zk = и расширенные k qk матрицы коррекции [Hk - hk] вычисляются по формуле (17).

Граница существования решения задач минимаксной коррекции СЛАУ определяется следующей теоремой.

N Теорема 2.6. Задачи 2.1Ц2.4 не имеют решения, если существует вектор z R, z > 0, такой что выполняется условие Az = 0.

Доказываются теоремы, которые показывают, что решение задач коррекции систем неравенств 2.5Ц2.8 эквивалентно решению задач условной минимизации (в том числе к серии задач линейного программирования).

Теорема 2.7. Задача коррекции 2.5 эквивалентна задаче математического программирования u min (21) u,x, y при ограничениях - u 1m (1T xk ) bk - yk - Ak xk, nk k u 1m (1T xk ) bk - yk - Ak xk, nk k K A0k xk b0, k=u 0, xk 0, yk 0, k = 1,K, K, * а именно, если (u, xk, yk ) - решение задачи (21), то матрицы коррекции H k вычисляются по формуле + H = (bk - yk - Ak xk )xk, k + где xk - вектор, двойственный к вектору xk относительно нормы .

Зафиксируем u = u > 0 достаточно большим, чтобы обеспечить выполнимость ограничений задачи (21). Тогда решение u u задачи (21) может находиться методом одномерной минимизации на отрезке [0,u]. При этом на каждом шаге итерации проверяем совместность ограничений задачи (21), что эквивалентно решению ряда вспомогательных задач линейного программирования:

T ck xk max, (22) - u 1m 1T + Ak bk - yk nk k [xk ] - - yk (bk ), - u 1m 1T - Ak nk k K A0k xk b0, k =xk 0, yk 0, k = 1,K, K, где ck - вектор-столбец размерности nk, состоящий из нулевых, u - фиксированные значения из отрезка [0,u].

Очевидно, что часть ограничений задачи (22) имеет блочно-диагональную структуру. Применим метод разложения КорнаиЦЛиптака для решения (22).

Вводятся m0 - мерные вектор-столбцы tk, k = 1,K, K, удовлетворяющие условию K b0. (23) tk k =Сформулируем K задач линейного программирования:

T ck xk max, A0k xk tk, - u 1m 1T + Ak bk - yk nk k [xk ] - - yk (bk ), (24) - u 1m 1T - Ak nk k xk 0, yk 0.

Введем вектор t = (t1,K,tK ) и M - множество векторов t таких, что выполняется (23) t и задачи (24) имеют решения.

k Обозначим через M, k = 1,K, K - ограниченные многогранники в пространствах x, y k Rn :

- u 1m 1T + Ak bk - yk nk k k M = (xk, yk )| [xk ] - u 1m 1T - Ak x, y - - yk xk, yk 0.

(bk ), nk k Введем функцию Лагранжа K L(x,t,) =,tk - A0k xk ), (k k =k mгде xk M, k R+, k = 1,K, K.

x, y m Выбираются значения и t, ,t R+ - границы изменения переменных k, tk, 0 k , - t tk t, k = 1,K, K.

Введем два множества M и :

t K M = | -t t t, b0 , t t tk k =1 = { | 0 k , k [1: K]} и функционал (t,) вида K K (t,) = max L(x,t,) =,tk )+ max (- k A0k, xk ).

(k k k xkM xkM x, y x, y k =1 k =Итак, имеем задачу о нахождении седловой точки функции (t,):

min(t,) max, t M. (25) t Задача (25) может решаться методом фиктивной игры. Тогда первый (минимизирующий) игрок на каждом шаге итеративного процесса решает задачу K,tk ) min, t M, (26) t (k k =где k - фиксированы.

Задача (26) может быть представлена как m0 независимых подзадач:

K s (s,tk ) min, t M, s [1: m0], t k k =где s - фиксированы.

k Второй (максимизирующий) игрок в процессе итераций решает следующую задачу:

T ck xk max, (27) A0k xk tk, - u 1m 1T + Ak bk - yk nk k [xk ] - - yk (bk ), - u 1m 1T - Ak nk k xk 0, yk 0, где tk - фиксированы.

Задача (27) рассматривается как K независимых подсистем. Таким образом, указанный подход осуществляет декомпозицию задачи (22) на K + m0 подзадач, имеющих меньшие размерности.

Теорема 2.8. Задача коррекции 2.6 эквивалентна задаче математического программирования ~ u min (28) ~ x,y,u при ограничениях ~ - u 1m (1T xk +1) bk - yk - Ak xk, nk k ~ u 1m (1T xk +1) bk - yk - Ak xk, nk k K A0k xk b0, k=~ u 0, xk 0, yk 0, k = 1,K, K, ~ а именно, если (u, xk, yk ) - решение задачи (28), то расширенные матрицы коррекции [Hk - hk] вычисляются по формуле T [H - hk ]= (bk - yk - Ak xk )wk, k xk где wk - вектор, двойственный к вектору относительно нормы .

Теорема 2.9. Решение задачи 2.7 может быть получено из решения задачи математического программирования следующего вида:

1T u min K при ограничениях - uk 1m (1T xk ) bk - yk - Ak xk, nk k uk 1m (1T xk ) bk - yk - Ak xk, nk k K A0k xk b0, k=xk, yk 0, k = 1,K, K, T K u = (u1,K,uK ) R, u 0.

Теорема 2.10. Решение задачи 2.8 может быть получено из решения задачи математического программирования следующего вида:

~ 1T u min K при ограничениях ~ - uk 1m (1T xk +1) bk - yk - Ak xk, nk k ~ uk 1m (1T xk +1) bk - yk - Ak xk, nk k K A0k xk b0, k= xk, yk 0, k = 1,K, K, T ~ ~ ~ ~ u = (u1,K,uK ) RK, u 0.

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ 1. Сформулированы задачи коррекции несовместных систем линейных алгебраических уравнений с матрицами блочного типа с новыми критериями минимальности коррекции и новые задачи коррекции блочных несовместных систем неравенств.

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

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

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

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

Основное содержание диссертационной работы отражено в следующих публикациях:

1. Горелик В.А., Ле Ньят Зюи. Метод декомпозиции в задачах минимаксной коррекции несовместных систем уравнений с матрицами блочной структуры // Вестник Тверского государственного университета. Серия:

Прикладная математика, 2011. № 4. С. 83Ц92. - 0.7 п.л. (авторский вклад - 50%).

2. Ле Ньят Зюи. Метод декомпозиции в задачах коррекции несовместных систем линейных неравенств с матрицами блочной структуры // Журнал вычислительной математики и математической физики, 2011. Т. 51. № 10. С.

1796-1805. - 0.5 п.л.

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

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

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

(авторский вклад - 50%).

6. Ле Ньят Зюи. Коррекция несовместных систем линейных неравенств с матрицами блочной структуры по минимаксному критерию // Сборник материалов Всероссийской конференции Математика, информатика и методика их преподавания. М.: МПГУ, 2011. С. 66-68. - 0,2 п.л.

Авторефераты по всем темам  >>  Авторефераты по техническим специальностям