автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Методы коррекции несовместных систем со структурными ограничениями

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

ПЕЧЕНКИН Руслан Викторович

МЕТОДЫ КОРРЕКЦИИ НЕСОВМЕСТНЫХ СИСТЕМ СО СТРУКТУРНЫМИ ОГРАНИЧЕНИЯМИ

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

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

Москва — 2006 6 /¿« ,л ч г* Г О- -/¿г

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

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

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

ГОРЕЛИК Виктор Александрович.

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

БЕЛОЛИПЕЦКИЙ Александр Алексеевич.

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

МОЛОСТВОВ Виталий Серафимович.

Московский городской педагогический университет.

Защита состоится "'ХД " рисл^А -А. 2006 г. в 14 ч. ° 0 мин. на заседании Диссертационного совета К 212.154.11 при Московском педагогическом государственном университете по адресу: 107140, г. Москва, ул. Краснопрудная, д.14, математический факультет МПГУ, ауд 301.

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

Автореферат разослан "_"_ 2006.

Учёный секретарь Диссертационного совета

ЧИКАНЦЕВА Н.И.

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

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

Ах « Ъ.

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

Совместность или несовместность линейных моделей, заданных системами уравнений и неравенств, - это фундаментальные свойства, связанные с теоремами об альтернативах - классической основой теорем существования решений задач оптимизации, и возможным инструментом их эффективного численного решения, развитым в работах академика РАН Ю.Г. Евтушенко и А.И. Голикова.

Одним из принципиально новых методов моделирования является предлагаемый академиком РАН Ю.И. Журавлевым, член-корреспондентом РАН В.Л. Матросовым и член-корреспондентом РАН К.В. Рудаковым алгебраический подход с использованием эвристических информационных моделей. Такой подход наиболее перспективен для решения прикладных задач в тех предметных областях, для которых нет адекватных математических моделей. Однако его существенной особенностью является применимость для строго определенного класса разрешимых задач, т. е. задач с внутренне непротиворечивой информацией.

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

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

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

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

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

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

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

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

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

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

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

В основу исследования была положена гипотеза о том, что несовместная система Ах ~ Ъ является результатом неточно заданных исходных данных, а именно, неточно заданного вектора а, от которого параметрически зависит матрица А = А (а) (параметрическая зависимость матрицы А от вектора а и обуславливает в конечном счете структуру системы), и что задачу коррекции системы можно свести к задаче оптимизации и получить такие оптимальные значения вектора а* и вектора а;*, чтобы гарантировать совместность и структурный вид скорректированной системы, а именно, Л(а*)а;* = Ь, при условии что поправка ||а — а*]] минимальна.

В соответствии с целью исследования были поставлены следующие конкретные задачи:

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

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

• Теплица,

• Вандермонда.

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

4. Провести анализ особенностей использования различных норм (критериев малости коррекции систем).

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

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

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

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

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

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

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

• проблему коррекции несовместной СЛАУ, обладающей блочной структурой, при квадратичном критерии оптимальности можно свести к задаче безусловной оптимизации дифференцируемой функции, а при минимаксном критерии к последовательности задач линейного программирования (ЛП);

• оптимальное корректирование структурных СЛАУ с матрицами Теплица и Вандермонда можно осуществлять как при наличии ошибок в обеих частях системы, так и при наличии ошибок только в левой части, в последнем случае для достижения совместности целесообразно использование метода штрафных функций;

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

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

Апробация результатов исследования. Основные результаты, получен-

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

1. на 36 - ой региональной молодежной школе-конференции "ПРОБЛЕМЫ ТЕОРЕТИЧЕСКОЙ И ПРИКЛАДНОЙ МАТЕМАТИКИ" Екатеринбург, 2005 г. Институт математики и механики УрО РАН,

2. на 2 - ой московской конференции "ДЕКОМПОЗИЦИОННЫЕ МЕТОДЫ В МАТЕМАТИЧЕСКОМ МОДЕЛИРОВАНИИ"

Москва, 2004 г. ВЦ РАН,

3. на Всероссийской конференции "АЛГОРИТМИЧЕСКИЙ АНАЛИЗ НЕУСТОЙЧИВЫХ ЗАДАЧ" (ААНЗ-2004)

Екатеринбург, 2004 г. Институт математики и механики УрО РАН,

4. на международной конференции "INTERNATIONAL CONFERENCE IN APPLIED MATHEMATICS" Slovak University of technology, 2003,

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

• Запатентован алгоритм "Коррекция несовместных систем уравнений на основе минимаксного критерия". Свидетельство об отраслевой регистрации разработки в отраслевом фонде алгоритмов и программ. (Алгоритм зарегистрирован в Национальном информационном фонде неопубликованных документов).

Результаты диссертационной работы вошли в состав проекта НИР Отдела Имитационных систем ВЦ им. А.А. Дородницына РАН (в рамках Программы поддержки ведущих научных школ НШ - 2094.2003.1).

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

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

В первой главе рассмотрена задача коррекции несовместной СЛАУ, которая имеет вид:

At 0 0

0 Аз

0

0 0 Ак

Ьо h Ъг

Ьк

(1-2)

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

Л0

Ai+Hi 0 0

0 Ai + Hi

0

0 0 Ак + Нк

_ " ь0 1

Xl _ h

- . . ьк .

(1.3)

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

А0

А1 + Й1 0 0

0 А2 + Н2

0

0 0 Ак + Нк

XI - Ьо - Ь + к!

. Хк . _ Ьк + Ьк .

(1.4)

Элементы матриц Л{ и векторов /ц удовлетворяют естественному требованию "малости", которые формализованы в виде ряда условий, каждое из которых представляет собой критерий оптимальности коррекции:

к

£|

1=1

\\ЦЩЩ\Е

к

1=1

^таэс^ -С тазе {|Л^|>>

ктахк.{шах{|^|}}

тт,

тт,

тт,

тт,

(1.5)

(1.6)

(1.7)

(1.8)

В задачах 1.5, 1.7 требуется найти минимальные матрицы коррекции Щ, к = 1,..., К, а в задачах 1.6, 1.8 минимальные рассширенные матрицы коррекции [Н{ — /ц], к - 1,../£", где при г = 1,..., К Ь, <Е Кп<хт% В{ б к(п*хп<) или В4 6 - невырожденные матрицы, символом

11*11 обозначена евклидова матричная норма. Н^ - элемент матрицы коррекции [Нк3, Щ - элемент расширенной матрицы коррекции \Нк ~ А*]. В основу методов коррекции положена следующая параметризация

Х(А0,Ь0У.

Х{Аа, Ьо) — {х — х + РАх},

(1.9)

где х = АцЬо, Р ~ I — Лд Ло, I - единичная матрица порядка Лг, Л^ £ д^Ухто. псевдообратная матрица к матрице А и Ах € - произвольный вектор. Блочные представления матриц Ло, Р и векторов ж и х естественным образом связанны с блочным представлением системы:

(1.10)

где В1 6 Е"4*™«, е х{ = ВгЪ0, х{ = х{ + Р<Дх, г = 1 ,...,К.

Рассмотрим коррекцию подсистемы с номером 1 < г < К системы (1.2). В рамках задачи (1.5) систему (1.3) можно переписать как совокупность К систем линейных алгебраических уравнений с неизвестной матрицей Щ:

' В! ■ ' Р1' ' XI '

л+ = , р= , X = , х =

.¿К. .Хк .

(Л, + Я») Xi — Ъi^^' ЩX, = —

(1.11)

Поскольку матрицы Ь^ и являются квадратными и невырожденными справедливы следующие соотношения:

Щщ = к- Щ^Ги • R^1xi = £<(&» - (1.12)

Единственным решением уравнения (1.11) относительно неизвестной матрицы Щ, обладающим минимальной взвешенной евклидовой нормой при некотором Хг ф 0 будет матрица

Щ = (Ь, - ЛгО(ДГ1®<)+ЯГ1- (1-13)

При использовании взвешенной евклидовой нормы (квадратичный критерий) будет справедлива формула

Иг ИР II Н^ф-ЛжОЦ 1

Таким образом, задачу (1.5) можно свести к задаче

ц^г^.ц *"Ч|*=1.....к

С использованием формул (1.9) и представлений (1.10) задача (1.15) может быть представлена в виде

/(Ах) = £ ~ ^Х|122 - ¿>(Лх) -» . шт . (1.16)

Получены аналитические выражения для производных целевой функции (1.16) задачи оптимальной коррекции

т?(рг(Ах) — 2(АДж -и- <рг(Ах)рх(Ах)) ■ в^Ах), ХГ2уч(Ах) = 2{П~р1(Ах)У(р^Ах)~(Ч(р^Ах))т р^Ах)-(р^Ах)С^-в^Ах), где = АТЛи и = АТ~Ьи р^Ах) = 0{Ах + С\ = Р?Ри д, = Р'[Чи з4(Дг) = + 2д[Ац + АхТО{Ах)~1.

При использовании минимаксного критерия задача минимизации (1.7) равносильна следующей задаче:

Г [ К^-ЛЛа:^ П .

тах <. тах < -тр-г--т , п \—г > > —» пип, (1.171

.....< \ + / / Д-

которую, в свою очередь, можно записать как:

и —+ тт

Ах,и

-и • 1ТОЬ . {\1кхк + (Р^Дх)) < Ьк - АкАх (1 18ч

и, 1т, • + 11(РкАх)) >Ьк- АкАх 11хк + 11(РкАх)>0 и > 0, к = 1 ,...,К ■ ' ,

■ Данная задача не является задачей линейного программирования, но, зафиксировав и = й > 0 достаточно большим, чтобы обеспечить выполнимость ограничений задачи (1.18), можно с помощью любого метода одномерной минимизации найти значение и* < и, которое будет оптимальным значением целевой функции задачи (1.18). При этом на каждом шаге такой одномерной минимизации требуется проверять совместность ограничений задачи (1.18), что эквивалентно задаче линейного программирования:

(1.19)

при ограничениях

и ' W ' (1 ltxk) - Ьк u-lm„-(ljkxk) + bk , х

где с = [0,0,... 0]jyt к = 1,..., К, и - текущее (фиксированное) значение целевой функции исходной задачи.

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

Границы существования решения задач квадратичной и минимаксной коррекции определяют следующие доказанные теоремы. Теорема. Если rank (А) < N то минимум в задачах 1.5 и 1.6 не достигается.

Теорема. Задачи 1.7 и 1.8 не имеют решения, если существует вектор z € z > 0 , такой, что выполняется условие

Az = 0.

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

А(а) + Е(а*) = А(а + а*),

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

Задача коррекции обеих частей системы обладающей структурой Теплица формулируется следующим образом: дана несовместная система линейных алгебраических уравнений вида Ах « Ь, где А имеет теплицеву структуру, Ь е Кт, а; €Е", При этом в общем случае Ь ф 0. Требуется

с • Ах —* тin, Ах

-Ak-u- 1т„ ■ (1* Р*) -Рк

Ах 1 <

найтпи теплицеву матрицу Е* £ и вектор ß* б Кт такие, что система (А + Е*)х = Ь + ß* совместна и выполнено условие

|| [Е* ЯНР= min \\{Е ß]L- (2.3)

Ul л- Jiip Х(А+ЕШ№ р

Задачу (2.3) в своей исходной постановке можно рассматривать как задачу безусловной минимизации

||г(а,*,'/?)||„+ \\Wpa\\p+ ||/3||Р-> min (2.4)

а, х, ß

где г(а, х, ß). = b+ß—(A + Е(а)) х,р — 1,2, оо, Wp £ RNxN - диагональная матрица, согласовывающая (путем взвешивания) векторную норму ||а||р с матричной нормой ||£(а)||р. Действительно, уменьшение значения первой компоненты выражения, стоящей под знаком нормы (2.4), свидетельствует о том, что решаемая система в процессе поиска минимального значения становится все более совместной (т.к. уменьшается вектор невязки). Уменьшение нормы вектора' Wv а и ß непосредственно влечет за собой уменьшение значения выражения ||[£ ß\\\ в задаче (2.3). Суть предложенной модификации состоит в том, что в процессе приближения к решению на каждом шаге корректируется не только левая часть СЛАУ, но и правая часть, что вполне естественно и, как показывают вычислительные эксперименты, более эффективно.

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

в||„+ С||г(а,яг)||р (2.5)

где С - коэффициент штрафа. Штрафная функция Ф(<а, х, С) = С||г(а, х) ||р при фиксированном р удовлетворяет требованиям, накладываемым к внешним штрафным функциям, а именно:

К, Г О, [а, я] € о

Ф(а, х, С) = | -Д. оо, (а, х] С, С - оо,

где О - допустимая область, т.е. те векторы [с*, х], которые приводят систему А(а)х — Ъ к совместности (¡¡г(а, ж)||р = О О- [а, х] 6 С). Для произвольной последовательности С„ -+ оо последовательности ап и х„ решений задачи (2.5) при соответствующем Сп. Некоторые подпоследовательности этих последовательностей обозначаются как {Сп'}| и {х„'}.

Корректное решение (реализация) задачи коррекции левой части системы с матрицей Теплица (2.5) требует рассмотрения двух подмножеств множества всех задач коррекции.

Первое подмножество S\: Задачи коррекции левой части, доя которых решение существует, т.е. G = {(а, ж)| г(а, х) — 0} ф 0 и G - ограниченно, а следовательно, в силу непрерывности г(а, х) компактно и выполняются условия (А+Е*)х* — Ьсовместнаи ||.Е*|| = min ||£*||,

где (а*,®*) € G.

Второе подмножество Sj: Задачи коррекции левой части, для которых решения не существует, т.е. $ G = {(а,х)\ г(а,х) — 0} ^ 0 и G -ограниченно, такого что выполняются условия (А + Е*)х* — Ъ совместна и ||В*|| = min ||Ü7*||, где (а*,х*) € G. В этом случае множество G может иметь одну из следующих структур:

1. G = {(а, х)| г(а,х) = 0} = 0,

2. G = {(а, х)| г(а, х) = 0} ф 0, но G - неограниченно.

Задачи, принадлежащие второму подмножеству, есть пример нестабильных (нерегулярных) задач, в которых при небольшом изменении элементов матрицы А, норма решения ||а;|| изменяется значительно. В этом случае наблюдается явление [|а;|| —> оо при ||^(а)|| —> 0. Справедлива следующая теорема, которая позволяет утверждать что существует такой вектор а*, что матрица Е(а*) обладает минимальной р нормой среди всех матриц Е(а), таких что система (Л + Е(а))х ~ Ъ совместна.

Предельная теорема 1. Пусть G = {(а,х)| г(а,а:) = 0} ^ 0 uG - ограничено (задача коррекции левой части системы относится к множеству Si). Тогда для любой последовательности {С„} —> оо:

1. справедливо равенство

lim ( min í||Ир а\\р + С„||г(а,x)|Ú 1 = \\WP а% = ||^||р,(2.6)

где G - компакт, такой, что G С G.

2. Э {Сп'} —* оо, такая, что подпоследовательности {xr¿} —* х*, {ап'} ~> а* Решений задач (2.6). Иными словами, [а* ж*] является точкой сгущения последовательности {[<>;„ при этом вектор [а* х*], принадлежащий допустимому множеству G, есть точное решение исходной задачи коррекции левой части системы, т. е.

(А + Е(а*)) х* = Ъ, Е* = Е{а*).

Для решения задач коррекции класса ¿¡2 требуется использование стабилизирующего слагаемого (предельная теорема 2). Пусть Gm — { х\ ||:r||р < М}, где М 6 (0, оо). Множество Greg = G П Gm есть регулярная областью решения задачи коррекции.

Предельная теорема 2. Пусть &гед ^ 0, Тогда для любой последовательности Сп —* оо 3 регуляризующий параметр А такой, что справедливо равенство

lim < min

С„-чх> l(a,x)e(iri,sr

(Ц^аЦр + АЦхЦр + СпЦгКх)

min

r(a,x) = 0,

Il*[|„ < м

p'

и В {Cn<} —> оо, такая, что подпоследовательность {xn<} —> х*, а подпоследовательность {ап>} —+ а*. Иными словами, [а* х*] является точкой сгущения последовательности {[ап а;п]}> вектор [а* х*\, принадлежащий регулярной области Greg, есть регуляризованпое решение задачи корреции левой части Теплицевой системы.

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

А(а) + Е(а*)^А{а + а*),

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

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

/(ai.ii) /(<* bh) f(ai,tm)

f(an,ti)

f[&n,t 2)

" " Гbi 1

22 h

X

. хп .

где / - некоторый функционал, зависящий от а, и Ь{ - результат измерений. Часто такие системы оказываются не только переопределенными, но и плохо обусловленными. Задача коррекции системы с матрицей Вандермонда формулируется следующим образом:

Дана несовместная система линейных алгебраических уравнений вида А(а)х = Ь, где а£М", Л(а) е Кт,п, Ъ е гбМ". Матрица А имеет структуру Вандермонда и параметрически определяется через вектор а (где вектор а - некий вектор, приводящий систему А(а)х — Ъ к несовместности). При этом в общем случае Ь ф 0. Требуется найти вектор а* е Кп такой, что система

А(а + а*)х — Ь, совместна и выполнено условие

а'

а

= гшп

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

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

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

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

В заключении приведены основные результаты:

1. Для задачи коррекции СЛАУ с блочной структурой рассмотрены два случая коррекции, коррекция левой части системы и коррекция обеих частей. В качестве критерия коррекции использовались два критерия: £2 - норма матрицы (квадратичный критерий), - норма (минимаксный критерий).

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

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

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

2. Для СЛАУ со структурой Теплица в случае коррекции обеих частей системы предложена модификация алгоритма Обобщенной Наименьшей Нормы, которая состоит в ведении вектора поправок правой ча-

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

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

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

5. Рассмотрен метод коррекции систем, полученных с помощью дискретизации ядра уравнения Фредгольма I рода. Данный метод демонстрирует эффект, когда коррекция обеих частей по минимаксному критерию приводит к стабильному, приемлемому по норме и структуре решению, т.е. представляет собой альтернативу методам решения СЛАУ с использованием регуляризующих критериев.

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

1. Горелик B.A.j Ерохин В.И., Печенкии Р.В. Оптимальная матричная коррекция несовместных блочных систем линейных алгебраических уравнений с минимаксным критерием П Известия РАН, Теория и системы управления, 2006, № 5, С. 575-588. - 1.8 п.л. (авт. вклад - 30%)

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

3. Матросов В.Л., Горелик В.А., Жданов С.А., Печенкии Р.В. Приме. нение техники регуляризации и методов решения несовместных систем со структурными ограничениями в задаче Ланцоша // Научные труды Московского педагогического государственного университета. Серия: Естественные науки. - М,: Прометей, 2004. - С. 279-287. - 0.8 п.л. (авт. вклад - 25%)

4. Печенкин Р.В., Волков В.В. Коррекция несовместных систем уравнений на основе минимаксного критерия. Свидетельство об отраслевой регистрации разработки в отраслевом фонде алгоритмов и программ. № 6103 от 05.05.2006 // Алгоритм зарегистрирован в Национальном информационном фонде неопубликованных документов 11.05.2006, № 50200600621. - (авт. вклад - 70%)

5. Печенкин Р.В., Волков В.В. Расширение нелинейного регуляризо-ванного алгоритма обобщенной наименьшей нормы с использованием различной техники регуляризаци // Проблемы теоретической и прикладной математики: Труды 36-й Региональной молодёжной конференции. Екатеринбург: УрО РАН, 2005. С. 92-96. - 0.4 п.л. (авт. вклад - 70%)

6. Горелик В.А., Ерохин В.И., Печенкин Р.В. Вычислительные аспекты решения задачи коррекции несовместных систем на основе минимаксного критерия. // Моделирование, декомпозиция и оптимизация

сложных динамических процессов. - М.: ВЦ РАН, 2005. С. 64-76. - 1.3 п.л. (авт. вклад - 30%)

7. Горелик В.А., Ерохин В.И., Печенкин Р.В. Использование h и норм в регуляризованном структурном нелинейном алгоритме обобщенной наименьшей нормы. // Моделирование, декомпозиция и оптимизация сложных динамических процессов. - М.: ВЦ РАН, 2004. С. 64-77. - 1.3 п.л. (авт. вклад - 30%)

8. Горелик В.А., Ерохин В.И., Печенкин Р.В. Идентификация сигнала в виде суммы экспонент с помощью методов матричной коррекции несовместных линейных систем с матрицами Теплица // Моделировав ние, декомпозиция и оптимизация сложных динамических процессов. - М.: ВЦ РАН, 2003. С. 74-88. - 1.4 п.л. (авт. вклад - 30%)

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

. 30%)

10. Pechenkin R. The Signal Identification Problem Using Regularized SNTLN Algorithm // Journal of Electrical Engineering, Vol. 55. No. 12/s. 2004. P. 3-7. 0.4 п.л. (авт. вклад - 100%)

11. Pechenkin R. The Total least Norm Algorithm Modified by Considering the Error on The Right-Hand Side of Overdetermined Linear Systems. Journal of Electrical Engineering, vol. 51, NO. 12/s, 2003, P. 6-9. - 0.3 п.л. (авт. вклад - 100%)

Подл, киеч. 13.09.2006 Объем 1 п.д. Заказ №. 131 Тир 100 экз.

Типография МИГУ

Введение

1 Оптимальная коррекция несовместных систем с матрицами блочной структуры

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

1.2 Решение задач блочной коррекции с квадратичными критериями

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

1.2.2 Дифференцируемость целевой функции.

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

1.3 Решение задач блочной коррекции с минимаксными критериями.

1.3.1 Некоторые общие свойства задач матричной коррекции.

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

1.3.3 Условия неразрешимости задач с минимаксными критериями.

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

2 Коррекция несовместных систем с матрицами Тёплица

2.1 Алгоритм Обобщенной Наименьшей Нормы.

2.1.1 Описание алгоритма Обобщенной Наименьшей Нормы

2.1.2 Модификация алгоритма Обобщенной Наименьшей Нормы при коррекции левой и правой части системы

2.1.3 Вычислительный эксперимент

2.2 Модификация алгоритма Обобщенной Наименьшей нормы для однородной системы.

2.2.1 Редукция исходной задачи.

2.2.2 Методы решения вспомогательных задач.

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

2.3 Модификация алгоритма Обобщенной Наименьшей Нормы для систем с неточно заданной левой частью и фиксированной правой частью.

3 Коррекция несовместных систем с матрицами Вандермонда

3.1 Метод де Прони и его модификации.

3.2 Нелинейная коррекция и регуляризация несовместных систем с матрицами Вандермонда.

3.2.1 Редукция исходной задачи.

3.2.2 Регуляризация нелинейного алгоритма

Обобщенной Наименьшей Нормы.

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

3.3 Алгоритмы коррекции систем с матрицами Вандермонда с использованием штрафных функций.

3.4 Минимаксная коррекция дискретизированных интегральных уравнений Фредгольма I рода.

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

3.4.2 Формулировка минимаксного критерия и переход к задаче линейного программирования.

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

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

Совместность или несовместность линейных моделей, заданных системами уравнений и неравенств, - это фундаментальные свойства, связанные с теоремами об альтернативах - классической основой теорем существования решений задач оптимизации [3, 4], и возможным инструментом их эффективного численного решения, развитым в работах академика РАН Ю.Г. Евтушенко и А.И. Голикова [И, 12].

Рис. 0.1. Схема коррекции модели.

Одним из принципиально новых методов моделирования является предлагаемый академиком РАН Ю.И. Журавлевым и его учениками алгебраический подход с использованием эвристических информационных моделей (см., например, [36]), член-корреспондентом РАН B.JI. Матросовым (статистическое обоснование алгебраического подхода [53]), член-корреспондентом РАН К.В. Рудаковым (общая теория проблемноориентированного алгебраического синтеза корректных алгоритмов [53]). Указанный подход наиболее перспективен для решения прикладных задач в тех предметных областях, для которых нет адекватных математических моделей.

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

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

Матричная коррекция несовместных СЛАУ, как научное направление, изначально развивалась в связи с важной и широко распространенной прикладной проблемой - задачей обработки экспериментальных данных с помощью так называемого обобщенного метода наименьших квадратов -Total Least Squares (TLS) [84]-[87]. TLS является обобщением классического метода наименьших квадратов (МНК) на случай, когда шум присутствует в наблюдениях как зависимых, так и независимых переменных. Если принять гипотезу, что погрешности всех переменных имеют нормальное распределение с нулевым средним значением и одной и той же дисперсией, то TLS получает статистическое обоснование как метод, дающий оценки неизвестных параметров линейной модели, гарантирующие максимум функции правдоподобия. Системы линейных алгебраических уравнений, обрабатываемые с помощью TLS - это, как правило, переопределенные системы полного ранга. Для сравнения, системы, возникающие при коррекции несобственных задач линейного программирования (ЛП) в канонической форме, как правило, являются недоопредеденными (но не имеющими положительного решения х > 0). Причины, приводящие модель (систему) к несовместности, и требуемый (желаемый) результат схематически изображены на рис. 0.2.

Параллельно с зарубежными исследованиями аналогичные работы, но с упором на несобственные задачи математического программирования, проводились и в России научной школой Института математики и механики УрОРАН под руководством академика РАН И.И. Еремина [7], [33]-[35], а впоследствии и научной группой Вычислительного центра им. А.А. Дородницына РАН и МПГУ под руководством профессора В.А. Горелика (В.И. Ерохин, В.А. Кондртатьева, И.О. Муравьева, P.P. Иба-тулин) [14, 20, 29, 37, 40, 48].

Рис. 0.2. Схема построения модели, входные факторы - требования, и желаемый результат

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

Дальнейшее развитие такой подход к решению задач структурной матричной коррекции получил в работах Дж.Б. Розена и его научной группы [73]-[75], [80], [81] и в работах бельгийских математиков под руководством профессора С. Ван Хаффел (S. Van Haffel) [68]-[70].

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

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

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

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

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

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

Рис. 0.3. Схема структурной коррекции.

В основу исследования была положена гипотеза о том, что несовместная система Ах & b является результатом неточно заданных исходных данных, а именно, неточно заданного вектора а, от которого параметрически зависит матрица А = А(а) (параметрическая зависимость матрицы А от вектора а и обуславливает в конечном счете структуру системы), и что задачу коррекции системы можно свести к задаче оптимизации и получить такие оптимальные значения вектора а* и вектора х*, чтобы гарантировать совместность и структурный вид скорректированной системы, а именно, А(а*)х* — Ъ, при условии что поправка Ца - а*|| минимальна.

В соответствии с целью исследования были поставлены следующие конкретные задачи:

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

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

• Теплица,

• Вандермонда.

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

4. Провести анализ особенностей использования различных норм (критериев малости коррекции систем).

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

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

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

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

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

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

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

• проблему коррекции несовместной СЛАУ, обладающей блочной структурой, при квадратичном критерии оптимальности можно свести к задаче безусловной оптимизации дифференцируемой функции, а при минимаксном критерии к последовательности задач линейного программирования (ЛП);

• оптимальное корректирование структурных СЛАУ с матрицами Теплица и Вандермонда можно осуществлять как при наличии ошибок в обеих частях системы, так и при наличии ошибок только в левой части, в последнем случае для достижения совместности целесообразно использование метода штрафных функций;

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

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

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

1. на 36 - ой региональной молодежной школе-конференции "ПРОБЛЕМЫ ТЕОРЕТИЧЕСКОЙ И ПРИКЛАДНОЙ МАТЕМАТИКИ" Екатеринбург, 2005 г. Институт математики и механики УрО РАН,

2. на 2 - ой московской конференции "ДЕКОМПОЗИЦИОННЫЕ МЕТОДЫ В МАТЕМАТИЧЕСКОМ МОДЕЛИРОВАНИИ"

Москва, 2004 г. ВЦ РАН,

3. на Всероссийской конференции "АЛГОРИТМИЧЕСКИЙ АНАЛИЗ НЕУСТОЙЧИВЫХ ЗАДАЧ" (ААНЗ-2004)

Екатеринбург, 2004 г. Институт математики и механики УрО РАН,

4. на международной конференции "INTERNATIONAL CONFERENCE IN APPLIED MATHEMATICS"

Slovak University of technology, 2003, а также на научно - методических семинарах кафедры теории информатики и дискретной математики МПГУ. Внедрение результатов.

• Запатентован алгоритм "Коррекция несовместных систем уравнений на основе минимаксного критерия". Свидетельство об отраслевой регистрации разработки в отраслевом фонде алгоритмов и программ. (Алгоритм зарегистрирован в Национальном информационном фонде неопубликованных документов) [52].

Результаты диссертационной работы вошли в состав проекта НИР Отдела Имитационных систем ВЦ им. А.А. Дородницына РАН (в рамках Программы поддержки ведущих научных школ НШ - 2094.2003.1).

Содержание и структура работы. Диссертация состоит из введения,

Выводы

В данной главе был рассмотрен подход для решения СЛАУ со структурой Вандермонда, основанный на нелинейной коррекции системы А(а)х ~ Ь. Необходимость нелинейного метода коррекции возникает в силу того, что для матриц с такой структурой не выполняется условие, выполняемое для матриц с Теплицевой структурой, а именно,

А(а) + Е{а*) = А{а + а*), где А, Е - матрицы Теплица.

А{&) + Е{а*) ^А{а + а*), где А,Е- матрицы Вандермонда.

Критерий малости величины ||а*|| является тем не менее обоснованным, т.к. отражает требуемое по постановке задачи структурной коррекции незначительное изменение исходной системы.

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

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

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

Заключение

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

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

Методы коррекции систем, позволяющие корректировать только левую часть системы (матрицу А) или расширенную матрицу (левую и правую часть системы [А 6]), рассмотрены для всех классов задач.

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

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

1. Для задачи коррекции СЛАУ с блочной структурой рассмотрены два случая коррекции, коррекция левой части системы и коррекция обеих частей. В качестве критерия коррекции использовались два критерия малости матрицы коррекции (расширенной матрицы): - норма матрицы (квадратичный критерий), I^ - норма (минимаксный критерий) .

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

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

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

2. Для СЛАУ со структурой Теплица в случае коррекции обеих частей системы предложена модификация алгоритма Обобщенной Наименьшей Нормы, которая состоит в ведении вектора поправок правой части системы и регуляризующего слагаемого, что в конечном счете приводит к более точному решению.

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

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

5. Рассмотрен метод коррекции систем, полученных с помощью дискретизации ядра уравнения Фредгольма I рода. Данный метод демонстрирует эффект, когда коррекция обеих частей по минимаксному критерию приводит к стабильному, приемлемому по норме и структуре решению, т.е. представляет собой альтернативу методам решения СЛАУ с использованием регуляризующих критериев.

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

1. Адамар Ж. Задача Коши для линейных уравнений с частными производными гиперболического типа. -М.: Наука, 1978. - 351 с.

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

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

4. Ашманов С. А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. М.: Наука, 1991. - 448 с.

5. Белолипецкий А.А. Некоторые математические модели вооруженных конфликтов. М.: ВЦ РАН, 1991. 145 с.

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

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

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

9. Воскобойников Ю.Е. Численная реализация и сравнение четырех способов выбора параметра регуляризации в устойчивых алгоритмах де-конволюции // Научный вестник НГТУ, № 4., 2004.

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

11. И. Голиков А.И., Евтушенко Ю.Г. Применение теорем об альтернативах к нахождению нормальных решений линейных систем // Известия ВУЗов, Математика. 2001. - Т. 475, № 12. - С. 21-31.

12. Голиков А.И., Евтушенко Ю.Г Теоремы об альтернативах и их применение в численных методах // Журн. вычислит, математики и матем. физики. 2003. - Т. 43, № 3. - С. 354-375.

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

14. Горелик В.А. Матричная коррекция задачи линейного программирования с несовместной системой ограничений // Журн. вычисл. матем. и матем. физ., Т. 41, № И, 2001, с. 1607 1705.

15. Горелик В.А. Приближенное нахождение максимина с ограничениями, связывающими переменные. // Журн. вычисл. матем. и матем. физ., № 2, 1972, с. 510 517.

16. Горелик В.А., Горелов М.А., Кононепко А.Ф. Анализ конфликтных ситуаций в системах управления. М.: Радио и Связь, 1991.

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

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

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

20. Горелик В.А., Ерохин В.И., Печенкин Р.В. Использование li и норм в регуляризованном структурном нелинейном алгоритме обобщенной наименьшей нормы. // Моделирование, декомпозиция и оптимизация сложных динамических процессов. М.: ВЦ РАН, 2004. С. 64-77.

21. Горелик В.А., Ерохин В.И., Печенкин Р.В. Вычислительные аспекты решения задачи коррекции несовместных систем на основе минимаксного критерия. // Моделирование, декомпозиция и оптимизация сложных динамических процессов. М.: ВЦ РАН, 2005. С. 64-76.

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

23. Горелик В.А., Ерохин В.П., Печенкин Р.В. Оптимальная матричная коррекция несовместных блочных систем линейных алгебраических уравнений с минимаксным критерием // Известия РАН, ТиСУ, 2006, № 5, С. 575-588.

24. Горелик В.А., Ерохин В.П., Печенкин Р.В. Вычислительные методы решения несовместных СЛАУ и несобственных задач ЛП. // М.: ВЦ РАН, 2006. в печати.

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

26. Ерохин В.И. Оптимальная матричная коррекция несовместных систем линейных алгебраических уравнений и несобственных задач линейного программирования: Дисс. . : д-ра физ.-мат. наук: 05.13.17 Москва, 2005.

27. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. М.: Мир, 1985. 509 с.

28. Денис Дж. Шнабелъ Р. Численные методы безусловной минимизации. М.: Мир, 1998. 440 с.

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

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

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

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

33. Журавлев Ю.И. Об алгебраическом подходе к решению задач распознавания или классификации. Проблемы кибернетики. М.: Наука, 1978, вып. 33, с. 5-68.

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

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

36. Колмогоров А.Н., Фомин С.В. Элементы теории функций и функционального анализа. М.: Наука, 1968. 320 с.

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

38. Ланцош К. Практические методы прикладного анализа. М.: Физмат-гиз, 1961. 524 с.

39. Лоусон Ч., Хенсон Р. Численное решение задач метода наименьших квадратов. М.: Наука, 1986. 232 с.

40. Льюнг Л. Идентификация систем. М.: Наука, 1991. 432 с.

41. Мазуров В.Д. Метод допустимых коррекций. В кн.: Несобственные задачи оптимизации. УНЦ АН СССР. Свердловск. 1982. С. 11-22.

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