Содержание к диссертации
Введение
1 Оптимальная коррекция несовместных систем с матрицами блочной структуры 20
1.1 Постановки задач блочной коррекции 21
1.2 Решение задач блочной коррекции с квадратичными критериями 25
1.2.1 Редукция квадратичных критериев к задачам безусловной минимизации 25
1.2.2 Дифференцируемость целевой функции 34
1.2.3 Вычислительные эксперименты 36
1.3 Решение задач блочной коррекции с минимаксными критериями 41
1.3.1 Некоторые общие свойства задач матричной коррекции 41
1.3.2 Редукция задач минимаксной коррекции к задачам условной оптимизации 50
1.3.3 Условия неразрешимости задач с минимаксными критериями 53
1.3.4 Вычислительные эксперименты 56
Коррекция несовместных систем с матрицами Теплица 62
2.1 Алгоритм Обобщенной Наименьшей Нормы 65
2.1.1 Описание алгоритма Обобщенной Наименьшей Нормы 65
2.1.2 Модификация алгоритма Обобщенной Наименьшей Нормы при коррекции левой и правой части системы 71
2.1.3 Вычислительный эксперимент 76
2.2 Модификация алгоритма Обобщенной Наименьшей нормы для однородной системы 78
2.2.1 Редукция исходной задачи 78
2.2.2 Методы решения вспомогательных задач 83
2.2.3 Вычислительные эксперименты 86
2.3 Модификация алгоритма Обобщенной Наименьшей Нормы для систем с неточно заданной левой частью и фиксирован ной правой частью 92
Коррекция несовместных систем с матрицами Вандермонда 104
3.1 Метод де Прони и его модификации 104
3.2 Нелинейная коррекция и регуляризация несовместных систем с матрицами Вандермонда 115
3.2.1 Редукция исходной задачи 115
3.2.2 Регуляризация нелинейного алгоритма Обобщенной Наименьшей Нормы 119
3.2.3 Вычислительные эксперименты 123
3.3 Алгоритмы коррекции систем с матрицами Вандермонда с использованием штрафных функций 129
3.4 Минимаксная коррекция дискретизированных интегральных уравнений Фредгольма I рода 132
3.4.1 Переход от интегрального уравнения Фредгольма к системе линейных алгебраических уравнений 132
3.4.2 Формулировка минимаксного критерия и переход к задаче линейного программирования 134
3.4.3 Вычислительные эксперименты 137
Заключение 145
Литература
- Решение задач блочной коррекции с квадратичными критериями
- Некоторые общие свойства задач матричной коррекции
- Описание алгоритма Обобщенной Наименьшей Нормы
- Нелинейная коррекция и регуляризация несовместных систем с матрицами Вандермонда
Введение к работе
Актуальность темы. Широко используемой основой для моделирования многих дескриптивных и оптимизационных прикладных задач являются системы линейных алгебраических уравнений (СЛАУ) Ах = Ъ. Такого рода системы встречаются в различных областях, причем они могут рассматриваться как самостоятельные объекты (например, если они описывают линейные процессы или линейные регрессионные модели), или как вспомогательные (например, в случае линеаризации нелинейных моделей или дискретизации непрерывных процессов). При этом различные проблемы моделирования часто приводят к тому, что СЛАУ являются несовместными. В частности, к важным несовместным задачам относятся несобственные задачи линейного программирования с несовместными системами ограничений. Причины возникновения несовместных (несобственных) линейных моделей хорошо известны. Ими могут быть ошибки, допущенные исследователем при попытке в рамках некоторой прикладной задачи построить формальное описание исследуемого объекта, или противоречивость требований лица, принимающего решение (ЛПР); например, при рассмотрении задачи о максимизации выпуска продукции (планирование ее производства) часто оказывается, что плановое задание невозможно выполнить из-за дефицита ресурсов, т.е. потребности и возможности несба-лансированы.
Совместность или несовместность линейных моделей, заданных системами уравнений и неравенств, - это фундаментальные свойства, связанные с теоремами об альтернативах - классической основой теорем существования решений задач оптимизации [3, 4], и возможным инструментом их эффективного численного решения, развитым в работах академика РАН Ю.Г. Евтушенко и А.И. Голикова [11, 12].
Рис. 0.1. Схема коррекции модели.
Одним из принципиально новых методов моделирования является предлагаемый академиком РАН Ю.И. Журавлевым и его учениками алгебраический подход с использованием эвристических информационных моделей (см., например, [ ]), член-корреспондентом РАН В.Л. Матросовым (статистическое обоснование алгебраического подхода [53]), член-корреспондентом РАН К.В. Рудаковым (общая теория проблемно-
ориентированного алгебраического синтеза корректных алгоритмов [53]). Указанный подход наиболее перспективен для решения прикладных задач в тех предметных областях, для которых нет адекватных математических моделей.
Моделирование вооруженных конфликтов является задачей, в которой понятие "противоречивой информации" полностью отражает реальный характер процесса ведения боевых действий. Подходы к решению этой задаче рассматриваются в работе Белолипецкого А.А. [ ].
Очевидно, что несовместная (несобственная) модель не позволяет получить содержательную информацию об исследуемом процессе или явлении непосредственно. Требуется исправление модели, ее коррекция (см. рис. 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) с учениками [ ], послужившая началом развития нового научного направления - Structured Total Least Norm Approach. В этой работе была впервые поставлена и решена задача структурной коррекции переопределенной системы. Рассматривалась СЛАУ, в которой вектор правой части Ъ содержит неточные данные (ошибки измерения), левая часть системы - матрица А - задана неточно в силу недостаточной априорной информации. Кроме того, матрица А обладает определенной, а именно, теплицевой структурой. Результатом работы алгоритма [80] является расширенная матрица коррекции (вектор коррекции правой части и матрица коррекции левой части), обладающая такой же структурой, что и исходная матрица.
Дальнейшее развитие такой подход к решению задач структурной матричной коррекции получил в работах Дж.Б. Розена и его научной группы [73]-[75], [80], [81] и в работах бельгийских математиков под руковод-
ством профессора С. Ван Хаффел (S. Van Haffel) [68]-[70].
В последние годы исследования в области методов коррекции несовместных СЛАУ и их приложениям в различных областях ведутся весьма интенсивно. При этом особое внимание уделяется задачам структурной коррекции, которые, с одной стороны, в наибольшей степени отвечают потребностям практики, а с другой стороны, представляют наиболее сложный математический объект, трудно поддающийся аналитическому исследованию. Поэтому тема настоящей диссертации, посвященная методам коррекции несовместных СЛАУ со структурными ограничениями, является актуальной. Несмотря на интенсивное развитие этого направления, проблема разработки математического аппарата и алгоритмов решения задач структурной коррекции решена далеко не полностью.
Так, все известные результаты неприменимы к коррекции линейных систем, матрицы которых имеют блочную структуру, а большинство методов коррекции несовместных систем типа Теплица и Вандермонда не учитывают возможную неустойчивость задач, что требует регуляризации алгоритмов коррекции.
Таким образом, проблема заключается в разработке математического аппарата исследования структурных задач оптимальной матричной коррекции несовместных систем линейных алгебраических уравнений и построении устойчивых и эффективных численных методов решения указанных задач.
Объектом исследования является теория коррекции несовместных систем линейных алгебраических уравнений.
Предмет исследования диссертационной работы составляют вопросы
структурной матричной коррекции несовместных систем линейных алгебраических уравнений с матричными нормами в качестве критерия качества коррекции.
Основной целью диссертации является развитие подхода структурной коррекции к несовместным СЛАУ с матрицами специального вида (с блочной, теплицевой и вандермондовой структурами) и методов их оптимальной коррекции (по квадратичному и минимаксному критериям рис. 0.3).
Структурная
противоречивая
неустойчивая модель
Структурная коррекция
Совместная
непротиворечивая
устойчивая модель
с аналогичной структурой
Рис. 0.3. Схема структурной коррекции.
В основу исследования была положена гипотеза о том, что несовместная система Ах ~ Ъ является результатом неточно заданных исходных данных, а именно, неточно заданного вектора а, от которого параметрически зависит матрица А = А(а) (параметрическая зависимость матрицы А от вектора а и обуславливает в конечном счете структуру системы), и что задачу коррекции системы можно свести к задаче оптимизации и получить такие оптимальные значения вектора а* и вектора х*7 чтобы гарантировать совместность и структурный вид скорректированной системы, а именно, А{а*)х* = 6, при условии что поправка \\а — а*\\ минимальна.
В соответствии с целью исследования были поставлены следующие конкретные задачи:
Разработать метод матричной коррекции несовместной системы линейных алгебраических уравнений, обладающей блочной структурой.
Развить методы матричной коррекции линейных алгебраических уравнений, имеющих структуру
Теплица,
Вандермонда.
Разработать на основе методов матричной коррекции вычислительные алгоритмы, позволяющие эффективно реализовывать поиск оптимального решения.
Провести анализ особенностей использования различных норм (критериев малости коррекции систем).
Исследовать область применимости методов и алгоритмов оптимальной структурной коррекции, возможность их регуляризации в случае некорректности исходной задачи.
Методологическую основу работы составляют современные методы линейной алгебры, математического анализа и теории оптимизации. Научная новизна:
Получен метод решения задачи оптимальной матричной коррекции несовместных блочных систем линейных алгебраических уравнений при использовании квадратичного и минимаксного критериев.
Сформулирован критерий оптимальной коррекции несовместной системы с матрицей Теплица и Вандермонда при наличии ошибок только в левой части и предложен метод коррекции с использованием штрафных функций норм векторов невязок.
Для плохо обусловленных систем со структурой Вандермонда сформулирован регуляризованный критерий коррекции, разработан численный алгоритм, реализующий поиск оптимального решения в различных нормах.
Практическая значимость. Предложенные в работе методы исследования и коррекции несовместных структурных систем линейных алгебраических уравнений могут быть использованы для решения многих прикладных задач в сфере планирования и управления, например, параметрической идентификации линейных (в том числе динамических) систем или численного анализа и коррекции противоречивых линейных моделей экономики с блочной структурой.
В частности, с помощью вычислительных экспериментов показана эффективность решения плохо обусловленных систем, являющихся результатом дискретизации интегральных уравнений Фредгольма I рода, с помощью методов минимаксной матричной коррекции.
Основные положения, выносимые на защиту:
проблему коррекции несовместной СЛАУ, обладающей блочной
структурой, при квадратичном критерии оптимальности можно све
сти к задаче безусловной оптимизации дифференцируемой функции,
а при минимаксном критерии к последовательности задач линейного
14 программирования (ЛП);
оптимальное корректирование структурных СЛАУ с матрицами Теплица и Вандермонда можно осуществлять как при наличии ошибок в обеих частях системы, так и при наличии ошибок только в левой части, в последнем случае для достижения совместности целесообразно использование метода штрафных функций;
регуляризация плохо обусловленной структурной системы может быть выполнена при помощи добавлении регуляризующего слагаемого в функционал задачи оптимальной структурной коррекции, выполнять данную регуляризующую процедуру возможно при использовании различных норм (в зависимости от характера ошибок в исходных данных);
решение плохообусловленной СЛАУ, матрица которой есть результат дискретизации интегрального уравнения Фредгольма I рода, можно получить без использования процедуры регуляризации в классическом смысле при помощи метода минимаксной коррекции.
Апробация результатов исследования. Основные результаты, полученные в диссертации, докладывались на следующих конференциях:
1. на 36 - ой региональной молодежной школе-конференции "ПРОБЛЕ
МЫ ТЕОРЕТИЧЕСКОЙ И ПРИКЛАДНОЙ МАТЕМАТИКИ"
Екатеринбург, 2005 г. Институт математики и механики УрО РАН,
2. на 2 - ой московской конференции "ДЕКОМПОЗИЦИОННЫЕ МЕ
ТОДЫ В МАТЕМАТИЧЕСКОМ МОДЕЛИРОВАНИИ"
15 Москва, 2004 г. ВЦ РАН,
3. на Всероссийской конференции "АЛГОРИТМИЧЕСКИЙ АНАЛИЗ
НЕУСТОЙЧИВЫХ ЗАДАЧ" (ААНЗ-2004)
Екатеринбург, 2004 г. Институт математики и механики УрО РАН,
4. на международной конференции "INTERNATIONAL CONFERENCE
IN APPLIED MATHEMATICS"
Slovak University of technology, 2003,
а также на научно - методических семинарах кафедры теории информатики и дискретной математики МП ГУ. Внедрение результатов.
Запатентован алгоритм "Коррекция несовместных систем уравнений на основе минимаксного критерия". Свидетельство об отраслевой регистрации разработки в отраслевом фонде алгоритмов и программ. (Алгоритм зарегистрирован в Национальном информационном фонде неопубликованных документов)
Результаты диссертационной работы вошли в состав проекта НИР Отдела Имитационных систем ВЦ им. А.А. Дородницына РАН (в рамках Программы поддержки ведущих научных школ НШ - 2094.2003.1).
Содержание и структура работы. Диссертация состоит из введения, трех глав, заключения и списка литературы.
Во введении обосновывается актуальность темы исследования, определяется цель работы, выдвигается гипотеза, положенная в основу исследования, формулируются задачи, которые необходимо было решить для
реализации поставленных целей и проверки выдвинутой гипотезы, указывается методологическая основа исследования, расскрывается научная новизна и практическая значимость диссертационной работы, выдвигаются основные положения, выносимые на защиту, представленно основное содержание работы.
В первой главе рассмотрена задача коррекции несовместной СЛАУ, которая имеет вид:
Ао
В качестве совместной системы, аппроксимирующую данную, строится система, полученная минимальным изменением параметров (по норме матрицы, корректирующей данную, и по норме расширенной матрицы, корректирующую обе части системы).
Коррекция левой части системы:
Коррекция обеих частей системы:
Элементы матриц Щ и векторов hi удовлетворяют естественному требованию "малости", которые формализованы в виде ряда условий, каждое из которых представляет собой критерий оптимальности коррекции:
1=1
mm,
mm,
Ь{Н{Н{
Ьг[Нг -ЫЩ 2
г=1 Е
max <^ max <^ l/if-l > > —> min, max <^ max <^ I/if-1 > > —> min.
k=l,...,K I ij I' y J J Ы,..Д I *j I J J >
В разделе 1.2.1 показан процесс редукции квадратичных критериев к задаче безусловной оптимизации, с помощью представления псевдорешения (решения полученного при помощи процедуры псевдообращения) в параметрическом виде.
Для полученной задачи безусловной оптимизации в разделе 1.2.2 выведены формулы первых и вторых производных оптимизируемой функции.
В разделе 1.2.3 показаны результаты вычислительных экспериментов при использовании квадратичных критериев, без ограничений на вектор ж и с ограничением на вектор х (х > 0), в обоих случаях наблюдалась квадратичная сходимость.
В разделе 1.3.2 показан процесс редукции задачи минимаксной коррекции СЛАУ блочного вида к серии задач ЛП. С помощью специальной
замены переменных минимаксная задача сводится к следующей задаче:
u= max \m&x<5ul\(bk — Аі~Ах)і\> > ^ mm,
к=1,...,К І і I ' 'J J Дж,4
которая в свою очередь сводится к последовательности задач Л П.
В разделе 1.3.3 приведено условие неразрешимости при использовании минимаксного критерия для решения задачи коррекции блочных систем. В разделе 1.3.4 представлены результаты вычислительного эксперимента для задач блочной коррекции с минимаксным критерием.
Во второй главе рассмотрен метод решения систем с теплицевой структурой. В основу метода положен алгоритм Обобщенной Наименьшей Нормы. Основной идеей, лежащей в основе методов коррекции систем со структурой Теплица, является возможность построения корректирующей теплицевой матрицы Е(а*) параметрически зависящей от вектора а, такой что, выполняется важное равенство
А(а) + Е(а*) = А(а + а*),
где А, Е - матрицы Теплица.
Это равенство позволяет заменять величину нормы матрицы коррекции Е(а) на равную ей величину нормы соответствующим образом взвешенного вектора а, что позволяет свести исходные задачи матричной коррекции при структурных ограничениях к соответствующим задачам условной оптимизации.
В разделе 2.1 рассмотрен основной алгоритм TLN, алгоритм для решения систем с матрицами Теплица. На его основе в разделе 2.1.2 строится модификация, заключающаяся в рассмотрении самостоятельной поправки [3 к вектору правой части Ъ.
В разделе 2.2 приводится модификация алгоритма TLN для решения однородной системы, которая также обладает структурой Теплица.
В разделе 2.3 сформулирован критерий оптимальности коррекции для теплицевых систем с неточно заданной левой частью. Данный критерий использует метод штрафных функций, а именно, вектор невязки г(а,х) вводится в штрафное слагаемое С||г(о;,ж)||. В пределе при С —> оо для корректируемой системы гарантируется нулевой вектор невязки.
Все предложенные алгоритмы протестированы на модельных примерах, результаты вычислительных экспериментов полностью подтвердили гипотезу о существовании точных матрицы А и вектора Ъ таких, что система Ах = Ъ совместна, и приведенные теоретические выкладки.
В третьей главе рассмотрен метод решения систем со структурой Вандермонда. Коррекция систем, обладающих данной структурой, осложняется тем, что структура матриц Вандермонда не позволяет осуществлять линейную коррекцию (коррекцию путем сложения исходной матрицы и матрицы поправок)
А(а) + Е(а*) ф А(а + а*),
где А, Е - матрицы Вандермонда.
В результате этого, единственно возможным методом коррекции, обеспечивающим исходную структуру матрицы, является подход, основанный на нелинейном методе коррекции (Нелинейный алгоритм Обобщенной Наименьшей Нормы).
В разделе 3.1 описана задача определения параметров экспоненциального сигнала и показано, что путем декомпозиции, исходная задача
определения параметров сигнала может быть разделена на две последовательные задачи, одна из которых приводит к решению однородной системы с матрицей Теплица, а вторая задача приводит к решению системы с матрицей Вандермонда. Как показали вычислительные эксперименты, обе задачи оказываются плохо обусловленными и решение их классическими методами структурной коррекции не приводит к приемлемым результатам. Результаты тестирования методов решения плохо обусловленных систем стали причиной модификации метода коррекции структурных задач с матрицами Вандермонда.
В разделе 3.2 приводится решение задачи идентификации сигнала в общей постановке, когда для определения показателей сигнала не приходится последовательно решать системы с матрицами Теплица и Вандермо-да, а задача заключается в решении системы типа Вандермонда
f(oin,ti)
f(pLn,t2)
J v^nj I'm/
ДаїЛ) f(oti,t2)
f{pL\,tm)
где f - некоторый функционал, зависящий от а и t: bi - результат измерений. Часто такие системы оказываются не только переопределенными, но и плохо обусловленными.
В разделе 3.2.1 для решения такого типа систем предлагается использовать модификацию Нелинейного алгоритма Обобщенной Наименьшей Нормы, заключающуюся в добавлении регуляризующего слагаемого А||ж|| для устранения эффекта неустойчивости. В разделе 3.3 предлагаетсся модификация для коррекции с использованием штрафных функций, что поз-
воляет решать задачи матричной коррекции с матрицами Вандермонда в точной постановке, а именно с помощью использования штрафных функций удалось выполнить ограничение по совместности скорректированной системы.
Решение задач блочной коррекции с квадратичными критериями
Пусть дана несовместная система линейных алгебраических уравнений Ах = Ъ, (1.1) которая, возможно, дополняется условием неотрицательности решения х 0, (1.2) где х Є M.N, Ъ Є Шм, А Є ММхДГ, причем матрица имеет следующую блочную структуру: возможно, дополненные условием (1.2); становятся совместными, а элементы матриц НІ и векторов hi удовлетворяют естественному для прикладных задач требованию "малости", которые будут формализованы в виде самостоятельных задач.
В задачах 1.1, 1.3 требуется найти минимальные матрицы коррекции Нь, k = 1,..., К, а в задачах 1.2, 1.4 минимальные рассширенные матрицы коррекции [НІ — hi], k = 1,..., К, где при і = 1,..., К Li Є ШПіХті, Ri Є М(ПіХПі) или Ri Є м(Пі+1)х ("-І+1) _ невырожденные матрицы, символом \\-\\Е обозначена евклидова матричная норма. Щ- - элемент матрицы кор hi Hh рекции [Hk], h\j - элемент расширенной матрицы коррекции
Структура корректируемых матриц в системах (1.5),(1.6) может быть интерпретирована следующим образом. Имеется система, состоящая из К подсистем (например, корпорация из К предприятий). Система в целом должна удовлетворять некоторым условиям устойчивости (гомеостаза) или координации функционирования подсистем. Эти условия связывают все переменные, записываются в виде (1.4) и не могут быть подвергнуты коррекции, т.е. являются жесткими. Коэффициенты же подсистем могут корректироваться. При этом случай (1.5) может быть интерпретирован как корррекция технологических коэффициентов подсистем, а случай (1.6) -как одновременная коррекция технологических коэффициентов и ресурсов подсистем. Задачи 1.1-1.4 означают, что требуется найти минимальные по взвешенной норме (с учетом весовых коэффициентов) матрицы коррекции, обеспечивающие совместность всех условий исследуемой системы.
Постановки задач 1.1-1.4 могут быть дополнены требованием коррекции матрицы AQ (ИЛИ части ее коэффициентов), однако такие задачи имеют другую содержательную интерпретацию, а главное, требуют для своего решения подхода, отличного от принятого в настоящей работе, основанного на использовании явного параметрического представления для множества решений системы (1.4). Поэтому в данной работе указанные задачи не рассматриваются.
Замечание. Задачи блочной коррекции 1.1-1.4 можно рассматривать как обобщения на случай линейных систем с блочной структурой задач многопараметрической (матричной) коррекции несовместных систем линейных алгебраических уравнений и несобственных задач линейного программирования общего вида по минимуму евклидовой нормы, исследованных в работах [7],[14],[20],[33],[28], т.к. они характеризуются дополнительными ограничениями на матрицу коррекции. Блочные матрицы могут также быть пред-ставленны в параметрическом виде А(а): т.е. представляют собой класс задач с параметризованной структурой, однако в данной главе такая параметризация в явном виде не используется. В второй и третьих главах рассматриваются два других класса такого типа задач и там, в алгоритмах решения задач, вид параметризации используется явно.
Некоторые общие свойства задач матричной коррекции
Цель данного раздела, показать как задачи минимаксной коррекции 1.3- 1.4 max \ max \ IhfA — min, к=1,...,К І і,з І J ) max \ max \ \Ш\ — min, к=і,...,к І ij Iі ylJ J можно редуцирвать к задачам условной минимизации.
Для того чтобы редуцировать задачи 1.3 - 1.4 к задачам условной минимизации необходимо воспользоваться двумя важными вспомогательными утверждения, позволяющих свести эти задачи к задачам условной минимизации (с ограничениями в виде линейных неравенств) в пространствах М.п и, соответственно, Mn+1. \\ p,i нормой для матрицы А Є Mmxn будем называть величину и ли А Ф(Лх) \\А \\ , = max—-—, (1.54) где tp () и г\) () - некоторые векторные нормы. В общем случае - это обобщенная (аддитивная) матричная норма . Отметим, что функцию - можно рассматривать как определенное расширение понятия подчиненной (индуцированной) матричной нормы [ ], которая задается некоторой векторной нормой и определяется для некоторой вещественной квадратной матрицы А как і ли А Ф (Ах) L4I =тах х О if(x) При этом, в силу (1.54), выполняется весьма полезное соотношение, аналогичное свойству согласованности матричной и векторной норм: Ф{Ах) \\А\\ ф -ф) УА є Штхп и Уж є Шп. (1.55)
В силу произвольности используемых векторных норм, \\ ф - норма оказывается весьма гибким инструментом для конструирования возможных показателей качества матричной коррекции несовместных систем линейных алгебраических уравнений и несобственных задач линейного программирования. Соответствующим выбором норм (/?() и ifj(-) можно получить многие употребительные матричные и обобщенные матричные нормы. В частности, если (/?() = Ці, ф(-) = Цоо , то (см., например, [38]) \\А\\ Р,Ф = ll lkoo = max \a,ij\. (1.56) 1-І Функция I т I р (у) = max-L-—і (1.57) x O If [Xj где ж, у Є Шп - некоторые векторы, f(-) - некоторая векторная норма, называется векторной нормой, двойственной к норме (/?() относительно скалярного произведения. Норма f(-) существует для любой нормы f(-) [57].
Упорядоченную пару векторов ж, у Є Шп называют двойственной парой по отношению к норме (/?() , если вектор у принадлежит множеству векторов ж, двойственных к по отношению к норме (/?() [ ].
Заметим, что в силу (..57) для произвольных ж, у Є Шп и произвольной (/?() справедливо неравенство \yTx\ ip (y)-ip(x). (1.58) Вектор у Є Шп , удовлетворяющий условию yTx = ip (y)-ip(x) = l (1.59) для некоторого вектора х Ф" 0, х Є Мп, называется двойственным к вектору ж относительно нормы (/9(-) . В контексте настоящей работы интерес представляют векторные нормы НЕ I ЛУ 1 / Х } г=1 Л г=1,2,...п ж — гдах 13 j Как известно (см., например, [ ]), указанные нормы являются взаимно двойственными.
Задача 1.5 может рассматриваться как обобщение задачи А.Н. Тихонова о решении (с минимальной евклидовой нормой) системы линейных алгебраических уравнений относительно неизвестной матрицы, а приводимая ниже теорема - как обобщение соответствующей леммы А.Н. Тихонова [55].
Таким образом, доказательство теоремы закончено.
Следствие 1.3.1. Решение системы (1.62), имеющее минимальную i,oo -норму существует и имеет вид (1.64), где у Є Шп - вектор, двойственный к вектору х относительно нормы i . При этом А ,,611 maxay = Y- f. (1.67) 1,00 «J \\x\\l Замечание. В силу леммы 1.3.2 вектор у Є Шп , двойственный к вектору х относительно нормы Ці, в общем случае не является единственным, что влечет неединственность матричного решения системы (1.62) с минимальной 1,00 - НОрМОЙ.
Снова рассмотрим систему линейных алгебраических уравнений вида (1.62), но теперь с традиционных позиций: матрицу А и вектор Ъ будем считать заданными, а вектор х - неизвестным. Обозначим через Х(А, Ь) множество векторов ж, являющихся решениями системы (1.62). Приводимые ниже задачи связаны с несовместностью системы (1.62), т.е., имеют содержательный смысл при условии X(A,b) = 0. Задача 1.6. Для заданного вектора х Є Шп найти матрицу [Н — h]: где Н Є Щтхп7 h Є Mm, обладающую минимальной \\ ф - нормой, и такую, что система (А + Н)х = b + h совместна, т.е. х Є Х{А + Н\Ь + К) ф 0. Задача 1.7. Для заданного вектора х Є Мп, ж ф 0 , найти матрицу Н Є Mmxn, обладающую минимальной Ц , - нормой, и такую, что система (Л + Н)х = Ь совместна, т.е. х Є Х{А + Н, 6)0. Лемма 1.3.4. Задача 1.6 разрешима, и, в частности, имеет решение из класса одноранговых матриц, задаваемое формулой ф(Ь — Ах) т [Н(х) -h(x)] = (b- Ах) у где у Є Жа+1 - вектор, двойственный к вектору тельно нормы (р(-) .
Описание алгоритма Обобщенной Наименьшей Нормы
Данная глава посвящена оптимальной матричной коррекции несовместных однородных и неоднородных линейных систем специального вида с матрицами (расширенными матрицами) Теплица или Ганкеля. Указанные линейные системы достаточно распространены. Они возникают, например, при анализе и параметрической идентификации линейных динамических систем с одним входом и одним выходом, когда соответствующие непрерывные входные и выходные сигналы заменяются дискретными наборами значений, а соответствующие системы линейных дифференциальных уравнений первого порядка, описывающие поведение исследуемых систем, превращаются в системы линейных разностных уравнений специального вида [47].
Несмотря на свою распространенность, матрицы Теплица определяются в литературе неоднозначно. Возможно, это обусловлено тем обстоятельством, что системы линейных алгебраических уравнений, являющиеся дискретными моделями линейных динамических систем, остаются эквивалентными при перестановках строк соответствующих расширенных матриц, а перестановка их столбцов просто заставляет менять порядок компонент вектора решения, что в контексте исследования данной динамической системы также допустимо интерпретировать как сохранение эквивалентно сти модели.
В настоящей работе матрицей Теплица будем называть прямоугольную вещественную матрицу А следующего вида:
Определение (2.1) закрепилось в литературе по спектральному анализу и идентификации динамических систем и встречается в справочнике В.В. Воеводина и Ю.А. Кузнецова [ ], хотя, например, в известных монографиях Р. Хорна и Ч. Джонсона [ ], а также Дж. Голуба и Ч. Ван Лоуна [13] матрица Теплица определяется как
Для полноты изложения приведем также оказавшееся фактически более устойчивым к различным интерпретациям определение матрицы Ган-келя [8],[57]:
Несложно убедиться что системы линейных уравнений с соответствующими матрицами и очевидным образом согласованными правыми частями являются моделями одного и того же линейного объекта. Поэтому в дальнейшем будем рассматривать только матрицы вида (2.1). Как несложно заметить, все полученные результаты могут быть адаптированы к таким задачам, в которых фигурируют матрицы вида (2.2) и (2.3).
Обозначим символом ТТО;П множество всех вещественных матриц размера тхп, имеющих тёплицеву структуру в соответствии с определением (2.1). Постановки основных задач настоящей главы имеет вид:
Задача 2.1. Дана несовместная система линейных алгебраических уравнений вида Ах = Ь, где А Є ТТО;П, Ь Є Mm, х Є W1. При этом в общем случае Ъ ф 0. Требуется найти матрицу Е Є ТТО;П и вектор [З Є Жт такие, что система (A + Е )х = b + [3 совместна и выполнено условие II [я 0 ] = min II [я Р]\\Р Задача 2.2. Дана несовместная система линейных алгебраических уравнений вида Ах = 0, где А Є ТТО;П, х Є Rn. Требуется найти такую матрицу Е Є ТТО;П, чтобы система (А + Е )х = 0 имела нетривиальное решение и было выполнено условие 11 ГН II 11 7V 11 \\Е \\ = mm \\Е\\ р Х(А+Е,О) 0 р Заметим, что любое нетривиальное решение системы {А + Е )х = 0 может быть нормировано, поэтому при описании алгоритма, решающего задачу 2.2 в точной постановке, добавляется также условие ж2 = 1-
Нелинейная коррекция и регуляризация несовместных систем с матрицами Вандермонда
Следовательно матрица Вандермонда А{а+а ) - есть результат нелинейной коррекции, коррекции при которой сохраняется исходная структура Вандермонда, которой обладает матрица А(а). Таким образом, задачу 3.2 следует рассматривать как задачу нелинейной коррекции, как естественное обобщение линейных задач коррекции.
Подобные системы Вандермонда, матрицы которых параметрически зависят от некоторого вектора, возникают при анализе временных рядов, идентификации динамических систем по входным и выходным сигналам (пример такой задачи был рассмотрен в разделе 3.1). В настоящем разделе также будет рассмотрено решение прикладной задачи, которая заключается в идентификации временного ряда, подверженного шуму (погрешностям наблюдения) и представляющего собой сумму показательных функций. Хорошо известно (см., например, [ ]), что рассмотренная задача может быть плохо обусловленной в том смысле, что даже при, казалось бы, достаточно больших отношениях амплитуды полезного сигнала к амплитуде шума возможны значительные ошибки в определении параметров полезного сигнала (амплитуд и коэффициентов, стоящих под знаком экспоненты).
В разное время предлагались различные алгоритмы и методы, направленные на то, чтобы даже при наличии шума решить задачу идентификации сигнала в виде суммы экспонент как можно более точно. Одна из последних попыток подобного рода, по-видимому, была предпринята в работе [ і], в которой рассматривалась близкая к теме диссертации задача деконволюции - нахождения одной из функций, стоящей под знаком интеграла свертки при наличии шума в левой и правой частях интегрального уравнения свертки. В данном разделе предлагается дополнить предложенный в работе [ ] алгоритм обобщенной наименьшей нормы для задач со специальной структурой (Total Least Norm for Strucured problems - STLN) регуляризацией, которая позволяет получать стабильное, регулярное решение.
Рассмотрим временной ряд вида п 3=1 где у - подверженный ошибкам вектор измерений, і = 1,2, ...,m. Измерения сделаны через равные промежутки времени At, поэтому, приняв начало отсчета времени за ноль, имеем ti = і At. Модель, используемая для определения неизвестных параметров Xj и х,-, очевидно, может быть записана в виде ехр(скі, ti) exp(ai,t2) exp(abm) exp(an, i) exp(an,t2) exp(an,tm) X\ 2/1 X x2 2/2 xn Ут (3.7)
Если известно начальное приближение для вектора а, то задача заключается в нахождении вектора амплитуд х и уточнении значения вектора а. Очевидно что данная задача попадает в класс задач 3.2.
Как было показано в работе [76], для решения задачи 3.2, эффективнее оказывается использование метода Regularized Structured Nonlinear Total Least Norm - регуляризованного структурного нелинейного алгоритма обобщенной наименьшей нормы (RSNTLN). Суть данного метода заключается в минимизации функционала вида где r(a,x) - вектор невязки, a - начальное приближение для вектора а, Л - параметр регуляризации Тихонова, предотвращающий неприемлемый рост нормы вектора х.
Минимизация целевого функционала (3.8) осуществляется с помощью линеаризации вектора невязки г(а,х): подробно данная процедура описана в [ 1 ]. Ниже приведен листинг алгоритма RSNTLN. При этом А(а) - матрица левой части уравнения (3.7), J (а) - якобиан вектора А(а) ж, - - векторная норма Гёльдера с показателем р: 1п - диагональная - единичная матрица размером п х п.
