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

Содержание к диссертации

Введение

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

1.1. Постановки задач 27

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

1.3. Псевдообращение, классический метод наименьших квадратов и задача о минимальной по евклидовой норме матрице, разрешающей систему Ах = Ь при фиксированных х и Ъ 32

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

1.5. Дополнительные сведения о задачах ZMal (A,b) и Zflx{b] (A,b), альтернативные формулировки необходимых и достаточных условий существования решения 51

1.6. Использование взвешенной евклидовой нормы в задачах Zlolal(A,b) и Z/jx{h](A,b) 78

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

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

2.1. Коррекция несовместной СЛАУ с условием неотрицательности по минимуму взвешенной (с помощью левого и правого умножения на невырожденные матрицы) евклидовой нормы 110

2.2. Достаточные условия собственности скорректированных по минимуму взвешенной (с помощью левого и правого умножения на невырожденные матрицы) евклидовой нормы несобственных задач ЛП 1-го и 3-го рода в канонической форме 126

2.3. Задача минимизации квадратичной формы на единичной сфере с условием неотрицательности и ее использование для решения задач коррекции несовместных СЛАУ с условием неотрицательности по минимуму евклидовой нормы 128

2.4. Обобщение задач С (А,Ъ) на случай фиксированных строк и столбцов при коррекции матрицы (расширенной матрицы) несовместной СЛАУ с условием неотрицательности решения 148

2.5. Коррекция несовместных систем линейных неравенств и несобственных задач линейного программирования в формах, отличных от канонической 157

2.6. Коррекция несобственной задачи ЛП в общей форме с произвольными фиксированными коэффициентами по минимуму взвешенной с произвольными положительными весами евклидовой нормы 160

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

3.1. Необходимые сведения о векторных и матричных нормах 166

3.2. Обобщения задачи о решении СЛАУ относительно неизвестной матрицы с минимальной евклидовой нормой на гёльдеровы матричные нормы и ||| -нормы 175

3.3. Задачи матричной коррекции несовместных СЛАУ по минимуму ||| ,|-|Г и ||-| норм 179

3.4. Регуляризация решений изначально несовместных СЛАУ при матричной коррекции их коэффициентов по минимуму ЦІ i - нормы 190

3.5. Оптимальная матричная коррекция несовместных СЛАУ с условием неотрицательности по минимуму |-| -нормы 203

3.6. Достаточные условия собственности скорректированных по минимуму |-| -нормы несобственных задач ЛП 1-го и 3-го рода в канонической форме 205

3.7. Практические методы матричной коррекции несовместных СЛАУ с условием и п'-я и \\LR неотрицательности по минимуму и -норм п »f, и lit, 207

3.8. Альтернативная техника матричной коррекции несовместных СЛАУ с условием неотрицательности решения по минимуму взвешенной с произвольными положительными весами У -нормы 214

4. Задачи матричной коррекции специального вида. Практические приложения задач матричной коррекции 220

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

4.2. Условия невырожденности матриц и смежные вопросы 236

4.3. Минимаксная матричная коррекция матричной игры 255

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

4.5. Матричная коррекция несовместных систем линейных алгебраических уравнений с матрицами Теплица (Ганкеля) по минимуму ||| ,||| и ||| -норм 260

4.6. Идентификация сигнала в виде суммы экспонент с помощью методов матричной коррекции несовместных систем линейных алгебраических уравнений с матрицами Теплица (Ганкеля) 276

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

Заключение 287

Литература

• Сингулярное разложение, задача о матричной аппроксимации, наилучшей в смысле минимума евклидовой нормы, и задача ZMol (А, Ь)
• Достаточные условия собственности скорректированных по минимуму взвешенной (с помощью левого и правого умножения на невырожденные матрицы) евклидовой нормы несобственных задач ЛП 1-го и 3-го рода в канонической форме
• Регуляризация решений изначально несовместных СЛАУ при матричной коррекции их коэффициентов по минимуму ЦІ i - нормы
• Минимаксная матричная коррекция матричной игры

Введение к работе

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

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

Одним из принципиально новых методов моделирования является предлагаемый академиком Ю.И. Журавлевым и его учениками, в частности, К.В. Рудаковым, алгебраический подход с использованием эвристических информационных моделей (см., например, [104,138]). Указанный подход наиболее перспективен для решения прикладных задач в тех предметных областях, для которых нет адекватных математических моделей, однако его существенной особенностью является применимость для строго определенного класса разрешимых задач, т. е. задач с внутренне непротиворечивой информацией.

Общие причины возникновения несовместных (несобственных) линейных моделей хорошо известны. Так, ими могут быть ошибки, допущенные исследователем при попытке в рамках некоторой прикладной задачи построить формальное описание исследуемого объекта. Например, при описании химико-технологического процесса исследователь не знает о протекании некоторых побочных химических реакций или имеет неверные сведения о схеме этих реакций, их кинетических и термодинамических константах и пр. Заметим, что моделирование, по признанию академиков П.С Краснощекова, А.А. Петрова и многих других ученых (см., например, [113, 128-129]) является скорее искусством, чем точной наукой, особенно в нетрадиционных для естествознания областях. Отбросим указанные грубые ошибки моделирования. Тогда для описательных линейных моделей (систем линейных алгебраических уравнений) в качестве источника их несовместности можно указать погрешности (шум) в экспериментальных данных, неопределенность, присутствующую в экспериментальных данных, ошибки округления, возникающие при вычислениях в арифметике с конечной разрядностью. Названные проблемы могут быть значительно усилены высокой размерностью исследуемой линейной модели [159]. Для оптимизационных линейных моделей (задач ЛП) источником несобственности могут быть как перечисленные выше причины, так и объективные внутренние противоречия исследуемого объекта. Наиболее выпуклые, яркие примеры для последнего случая легко взять из экономики или техники. Например, при рассмотрении задачи о максимизации выпуска некоторой продукции или ее производстве с минимальными затратами оказывается, что даже плановое задание невозможно выполнить из-за дефицита ресурсов. Достаточно злободневный технический пример - задача оптимального функционирования электроэнергетической системы в условиях дефицита мощности [105-107].

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

Как свидетельствуют обзоры и популярные статьи, посвященные TLS (см., например, [167, 170, 208] и [229]), интенсивные исследования метода и его активное использование при решении прикладных задач начались в конце 80-х годов после появления работ Бельгийского математика S. Van Haffel. Ее диссертация [230] и, в особенности, написанная в соавторстве с J. Vandewalle монография [232] до сих пор являются одними из наиболее часто цитируемых материалов по TLS. Заметим, что задача ZrLS является частным случаем из обширного класса задач матричной аппроксимации и известна достаточно давно. Работы [208] и [229] содержат интересные исторические сведения, свидетельствующие о том, что задача Z//s или близкие к ней задачи многократно переоткрывались и связаны с такими именами как Е. Beltrami (1873) С. Jordan (1874), Е. Schmidt [227] (1907), Н. Weyl [237] (1912), L. Mirsky [205], С. Eckart, G. Young [173] (1936). Задача Zr;s просто и элегантно решается с помощью сингулярного разложения матрицы [A b]. Как известно, соответствующая техническая база (универсальные вычислительные машины третьего поколения), позволяющая решать нетривиальные задачи линейной алгебры, появилась в начале 70-х годов прошлого века. В это же время появляются и соответствующие математические работы, закладывающие алгоритмическую базу для вычисления сингулярного разложения [181, 182], а затем и для решения задачи TLS [184,185].

В настоящее время обобщенный метод наименьших квадратов (TLS) представляет собой широко и мощно развивающееся научное направление. Описание всевозможных известных к настоящему времени модификаций TLS вполне может быть предметом самостоятельной специализированной публикации. Одним из таких направлений, тесно связанным с рассматриваемыми в данной диссертационной работе проблемами регуляризации задач матричной коррекции линейных систем, является RTLS -регуляризованный обобщенный метод наименьших квадратов. Заметим, что "технология" регуляризации TLS - в настоящее время в подавляющем большинстве предмет зарубежных исследований: [168, 180, 186, 190, 193, 194, 200, 214, 234, 238]. Задачи математического программирования, которые при этом возникают, и проблемы эффективной вычислительной реализации методов их решения, тесно перекликаются с более общей задачей минимизации квадратичной функции на сфере [191, 192], достаточно интересны сами по себе, и, видимо, представляют еще широкое поле для исследования. "Идеология" RTLS, в отличие от "технологии" - заслуга отечественных математиков: (см, например, [17, 39,146] и др.)

Задачи TLS и их модификации могут быть не только некорректными но и несобственными (см. приведенную выше схему). В зарубежной литературе подобные задачи (и метод их решения, связанный с ограничением линейного подпространства столбцов матрицы коррекции) получили название Nongeneric TLS (соответствующего русскоязычного термина пока нет). Складывается впечатление, что необходимость серьезного исследования Nongeneric TLS зарубежными учеными недооценивается (отечественные исследования автору неизвестны). "Практики" - специалисты, использующие TLS и его модификации в прикладных исследованиях (в основном, это задач обработки наблюдений, см., например, [167]), считают, что отсутствие решения при использовании TLS - очень редкая аномалия, нонсенс. Примерно также долгое время относились к проблеме зацикливания в симплекс-методе. Для решения задач Nongeneric TLS сейчас используется два подхода: получение приближенного решения с использованием техники регуляризации (т.е., несобственная задача рассматривается как некорректная и для решения используются методы, упомянутые выше). Другой подход -ограничение линейного подпространства, в котором должно находиться TLS-решение. Более детально об этом написано в главе 1, а сейчас просто заметим, что если регулярный TLS сводится к нахождению минимального собственного значения матрицы [A -b] [A -b] и соответствующего ему собственного вектора, то в качестве решения задачи Nongeneric TLS предлагается брать следующие по величине собственные значения и соответствующие векторы [231, 233]. Указанный подход не устраняет всех проблем.  

Это переход от евклидовой к другим матричным нормам - Total Least Norm (TLN) - метод обобщенной наименьшей нормы, и переход к исследованию линейных систем со специальной структурой - Structured TLS (STLS) и Structured TLN (STLN). Из многообразия задач со специальной структурой сразу же выделим задачи с аффинной [171] структурой. Это задачи с матрицами (расширенными матрицами) Теплица или Ганкеля, блочные задачи и т.д. В решении задач с аффинной структурой в Lt,L2,Lm нормах (STLS, STLN) [130, 131, 189 198, 201, 202, 203, 209, 210, 211, 213, 219-223, 234, 238 и др.] существуют как определенные достижения, так и определенные нерешенные проблемы. К достижениям можно отнести то, что с помощью известных к настоящему времени методов уже успешно решаются практические задачи обработки наблюдений. Известные проблемы лежат как в теоретической плоскости - это проблемы с обоснованием сходимости соответствующих вычислительных алгоритмов, так и в практической - это проблемы численной эффективности алгоритмов (т.е., повышения их быстродействия и снижения требований к используемой памяти).

Распространение обобщенного метода наименьших квадратов на задачи матричной аппроксимации СЛАУ общего вида, использующие в качестве критериев полиэдральные матричные нормы (TLN), не стало еще не столь мощным направлением, как TLS, STLS, STLN. Здесь следует упомянуть исследования, которые проделал G.A. Watson [235,236]. В данных работах для построения матричных аппроксимаций, оптимальных в смысле минимума полиэдральной нормы, предлагаются приближенные методы и вместо исходных, решаются "близкие" задачи (т.е., результаты о решении задачи TLN в точной постановке до настоящего времени неизвестны).

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

Как известно, систематические исследования несобственных задач линейного и выпуклого программирования (с введением соответствующей терминологии) были начаты 80-х годах (XX в.) И.И. Еремиными, его учениками и коллегами: Н.Н. Астафьевым, А.А. Ватолиным, Вл. Д. Мазуровым, Л.Д. Поповым, В.Д. Скариным, СП. Трофимовым, В.Н. Фроловым и другими (см., например, [2-А, 18-26, 60-64, 67-69, 119, 120, 142, 147, 148, 152-155] и др.). В указанных работах (более полный список которых до 1992 г., содержащий также прикладные, в основном экономические работы, можно найти в диссертации [26]) рассматриваются несобственные задачи линейного и выпуклого программирования, проводится классификация, строится и исследуется теория двойственности, вводятся и исследуются дискретные аппроксимации решений -комитетные конструкции, предлагаются различные постановки и методы решения задач полной или частичной (правая часть системы уравнений или неравенств) параметрической коррекции и их содержательная (в основном, экономическая) интерпретация.

Последнее направление представляет наибольший интерес в контексте данного исследования. В его рамках коррекция несобственных линейных моделей осуществляется на основе метода параметрического программирования [115]. При этом в большинстве исследований рассматривается коррекция по вектору правой части ограничений и коэффициентам вектора целевой функции [18, 23, 57, 65, 66, 68, 132-134, 139, 140, 142, 145, 154,164, и др.]. Такие задачи матричной коррекции конечно являются многопараметрическими, но не обладают максимально возможной общностью. Заметим, что исследование задач многопараметрической коррекции подобного типа, анализ проблем двойственности для несобственных задач математического программирования и изучение комитетных конструкций продолжаются и сейчас [5-11, 70-76, 108, 109, 121, 135-137, 156, 160,161,199, 204 и др.].

Матричная коррекция впервые была рассмотрена в работах А.А. Ватолина [19, 21, 22, 24-26, 63]. В частности, им были рассмотрены задачи: Vx - задача коррекции расширенной матрицы коэффициентов несовместной СЛАУ по минимуму евклидовой нормы; V[ - модификация задачи Vx с запретом на коррекцию отдельных столбцов матрицы коэффициентов исследуемой системы; V" - модификация задачи Vx с взвешенной с помощью левого и правого умножения на невырожденные матрицы евклидовой нормой и дополнительным ограничением в виде системы линейных неравенств, V2 - задача коррекции всех коэффициентов двойственной пары задач ЛП в стандартной форме по минимуму евклидовой нормы, К, - задача коррекции всех коэффициентов смешанной системы линейных уравнений и неравенств по минимуму аддитивной матричной нормы с ограничениями в виде условий принадлежности множеств решений скорректированной системы и множеств оптимальных матриц коррекции заданным линейным подпространствам.

Для задач VX,VX \К ,V2 были получены: значение нижней грани квадрата евклидовой нормы матрицы коррекции, достаточные условия существования решения (оптимальной матрицы коррекции), вид оптимальной матрицы коррекции и вид вектора х - решения скорректированной линейной системы (задачи ЛП). В то же время, такие важные вопросы, как необходимые условия существования решения, условия единственности решения и вид множества решений скорректированной линейной системы (задачи ЛП) для указанных задач, остались не исследованы.

Исследования А.А. Ватолина в конце 90-х годов (XX в.) были продолжены (а также продолжаются в настоящее время) в ВЦ им. А.А. Дородницына РАН и МПГУ В.А. Гореликом и его учениками: В.А. Кондратьевой, О.В. Муравьевой, P.P. Ибатуллиным, Р.В. Печенкиным и другими: [40-56, ПО, 112, 124-127, 130-131, 187-189]. Указанными авторами с использованием леммы А.Н. Тихонова, свойств евклидовой нормы и методов математического анализа были уточнены некоторые результаты А.А. Ватолина (в частности, для задач Vx, V были получены необходимые и достаточные условия существования решения) и рассмотрены новые модификации задачи Vx, дополняющие указанную задачу новыми условиями - фиксированным вектором правой части и ограничениями в виде совместной подсистемы линейных алгебраических уравнений. На основе решений указанных задач с использованием условий Куна-Таккера удалось получить решения проблем матричной коррекции несобственных задач ЛП в канонической и стандартной форме по минимуму евклидовой нормы в виде сведения указанных задач к задачам вычисления собственных значений и соответствующих собственных векторов некоторого конечного набора вспомогательных квадратных симметричных матриц. Кроме того, с привлечением математической техники, отличной от вышеназванной (с использованием некоторых специфических свойств одноранговых матриц и чебышевской матричной нормы), удалось получить решение задачи минимаксной коррекции матрицы коэффициентов несобственной задачи ЛП в канонической форме в виде сведения ее к задаче линейного программирования. Начата разработка регуляризованных методов коррекции несовместных систем линейных алгебраических уравнений со специальной структурой в различных матричных нормах (RSTLN) и применение указанных методов к обработке временных рядов и идентификации сигналов [49, 50, 53, 89, 94, 131, 189, 210, 211]. Возникающие в подобных задачах СЛАУ, как правило, плохообусловлены. Это свойство передается соответствующим проблемам матричной коррекции и заставляет прибегать к различным методам регуляризации (например, описанным в работах [31, 32, 39]). В отношении достижений и нерешенных проблем в данном случае можно высказать те же комментарии, что и при анализе всей совокупности исследований, посвященных STLS и STLN.

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

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

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

Все вышесказанное и обуславливает актуальность данного диссертационного исследования.

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

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

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

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

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

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

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

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

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

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

Внедрение и апробация результатов исследования. Основные результаты, полученные в диссертации, докладывались на Международной конференции "Математика. Образование. Экология. Тендерные проблемы" (Воронеж, 2000 г.), XII Байкальской международной конференции "Методы оптимизации и их приложения" (Иркутск, 2001 г.), XIII Байкальской международной школе-семинаре "Методы оптимизации и их приложения" (Иркутск, 2005 г.), Международной конференции "Некорректные и обратные задачи" (Новосибирск, 2002 г.), Международной научно-технической конференции "Методы и средства измерения в системах контроля и управления" (Пенза, 2002 г.), 4-й Московской международной конференции по исследованию операций (ORM2004) (Москва, 2004 г.), Международной конференции по вычислительной математике МКВМ-2004 (Новосибирск, 2004 г.), Международной конференции "Дискретный анализ и исследование операций (DAOR-2000) (Новосибирск, 2000 г.), Российской конференции "Дискретный анализ и исследование операций (DAOR 02, DAOR 04)" (Новосибирск, 2002, 2004 гг.), Всероссийской конференции "Математическое программирование и приложения" (Екатеринбург, 2003 г.), Всероссийской конференции "Алгоритмический анализ неустойчивых задач" (Екатеринбург, 2004 г.), 1-й Московской конференции "Декомпозиционные методы в математическом моделировании" (Москва, 2001 г.), 2-й Московской конференции "Декомпозиционные методы в математическом моделировании и информатике" (Москва, 2004 г.), Воронежском зимнем симпозиуме "Математическое моделирование в естественных и гуманитарных науках" (Воронеж, 2000 г.), научном семинаре по исследованию операций ВЦ им. А.А. Дородницына РАН, научном семинаре отдела Имитационных систем ВЦ им. А.А. Дородницына РАН, научных конференциях преподавателей и сотрудников Борисоглебского гос. пед. института, научных семинарах каф. прикладной математики и информатики Борисоглебского гос. пед. института.

Основные результаты диссертации опубликованы в 20 печатных работах, в том числе - одной монографии. Еще 20 публикаций по теме диссертации - тезисы различных конференций.

Результаты диссертационной работы вошли в состав проекта «Исследование и оптимизация сложных управляемых систем при нечетких или некорректных данных» (поддержан ФАП, 2005 г., (рук. проф. Тараканов А.Ф., исполнители Тараканов А.Ф., Ерохин В.И) и в тематику НИР Отдела Имитационных систем ВЦ им. А.А. Дородницына РАН (поддержка Программы поддержки ведущих научных школ).

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

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

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

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

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

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

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

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

Глава состоит из шести параграфов. Большая часть материала главы (§§ 1-4) фактически посвящена задачам матричной коррекции несовместных систем линейных алгебраических уравнений с условием неотрицательности решения, хотя общий круг рассматриваемых в главе вопросов достаточно широк, и затрагивает, в частности, проблемы коррекции несовместных систем линейных неравенств и несобственных задач ЛП в различных формах (§ 5) и наиболее общую (по своей постановке) проблему матричной коррекции несобственной задачи ЛП в общей форме с произвольными фиксированными (некорректируемыми) коэффициентами по минимуму взвешенной с произвольными индивидуальными положительными весами евклидовой нормы.

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

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

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

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

Различия в постановках задач заключаются в том, что в одном случае коррекции подвержены все коэффициенты исследуемой системы (т.е., корректируется расширенная матрица системы), а во втором случае корректируется только левая часть системы - ее матрица коэффициентов. Для указанных задач получены следующие результаты: необходимые и достаточные условия существования решения, вид оптимальных матриц коррекции, вид вектора х , являющегося решением скорректированной системы. При этом сами задачи матричной коррекции сведены к задачам минимизации дробно-квадратичных функций с условием неотрицательности или квадратичных функций на единичной сфере с условием неотрицательности. Получены также достаточные условия, при выполнении которых допустимые области скорректированных систем а) содержат единственную точку; Ь) ограничены. Как несложно заметить, указанные условия являются также достаточными для собственности соответствующих изначальной несобственных задач ЛП 1-го и 3-го рода в канонической форме, а также изначально несобственных задач ЛП 2-го рода в основной форме.

Второй параграф также содержит сведения, являющиеся одним из "мостиков" между задачами коррекции несовместных систем линейных алгебраических уравнений с условием неотрицательности и проблемами коррекции несобственных задач ЛП 1-го и 3-го рода в канонической форме. К указанным сведениям относятся, Во-первых, две леммы, устанавливающие ограниченность допустимых множеств, получаемых в результате решения рассмотренных в § 1 задач вдоль определенных лучей, выходящих из допустимой области. Во-вторых (и это главный результат данного параграфа), к указанным сведениям относятся две теоремы, устанавливающие достаточные условия собственности изначально несобственных, но скорректированных по минимуму евклидовой нормы задач ЛП 1-го или 3-го рода.

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

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

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

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

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

Шестой параграф содержит исследование задачи матричной коррекции несобственной задачи ЛП с произвольным видом несобственности (т.е., 1-го, 2-го или 3-го рода), представленной в общей форме. Точнее, рассматривается задача одновременной матричной коррекции пары взаимодвойственных задач в общей форме. В роли показателя качества коррекции используется евклидова матричная норма, взвешенная с индивидуальными для каждого корректируемого элемента положительными весами. Кроме того, допускаются (с определенными оговорками) запреты на коррекцию отдельных, произвольно выбранных коэффициентов исследуемой задачи ЛП.

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

Для рассматриваемой проблемы матричной коррекция приведены необходимые формулы и преобразования, (во многом опирающиеся на результаты § 6 первой главы) позволяющие свести указанную проблему к задаче минимизации дифференцируемой функции при условии неотрицательности части ее переменных. При этом с использованием методов дифференцирования псевдообратных матриц, являющихся специальным частным случаем методов, изложенных в работе [183], получены формулы для частных производных указанной функции, позволяющие использовать для ее минимизации градиентные методы. 

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

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

Глава состоит из восьми параграфов. Первый параграф является вводным. В нем приводятся необходимые сведения о векторных и матричных нормах. В частности, дается определение не столь распространенной в матричном анализе .м/ -нормы. Кроме того, рассматриваются необходимые в последующих выкладках двойственные векторные нормы и двойственные пары векторов. Выводятся формулы для построения вектора у, двойственного к заданному ненулевому вектору х относительно - - векторной нормы, двойственной к норме Гёльдера с показателем р. При 1 р +оо показана единственность вектора у. При /? = 1,оо вектор у не является единственным и для него приведены соответствующие параметрические представления.

Главный результат второго параграфа - обобщение леммы А.Н. Тихонова [144] о решении с минимальной евклидовой нормой СЛАУ относительно неизвестной матрицы на .с ;) и Н-Н , -нормы, где 11-11 - норма Гёльдера (на множестве матриц) с показателем 1 /? +со, взвешенная с помощью левого и правого умножения на невырожденные матрицы. Указанный результат имеет принципиальное значение для всей третьей главы, так как с его помощью непосредственно решаются задачи матричной коррекции несовместных систем линейных алгебраических уравнений по минимуму некоторой \\.\\ё и .м/ -нормы при заданном ненулевом векторе х. Заметим, что результаты, полученные при исследовании коррекции несовместных систем линейных алгебраических уравнений по минимуму спектральной нормы [46], позволяют переформулировать лемму А.Н. Тихонова для спектральной нормы. При этом можно показать, что, во-первых, матрица, являющаяся решением СЛАУ с минимальной спектральной нормой - не единственна, т.е., можно говорить о множестве или семействе матриц. Во-вторых, указанное семейство матриц содержит одноранговую матрицу, являющуюся решением исследуемой системы и минимальную по евклидовой норме (т.е., матрицу, описываемую леммой А.Н. Тихонова). В настоящей работе показано, что аналогичный результат справедлив и в отношении .с" и ІНІр,,,, -норм (. -норма в указанном контексте аналогична евклидовой норме, а \\\м -норма - спектральной).

Третий параграф посвящен исследованию задач матричной коррекции несовместных систем линейных алгебраических уравнений по минимуму . , ."г и \\-\\ ч, -норм, являющихся обобщениями первых двух задач матричной коррекции, рассмотренных в § 4 первой главы. Для указанных задач с использованием полученного в § 2 обобщения леммы А.Н. Тихонова, найдены необходимые условия существования решения, вид оптимальных матриц коррекции и множеств решений скорректированных систем. Кроме того, показано, что полнота столбцевого ранга матрицы коэффициентов корректируемой системы является необходимым условием существования решений рассматриваемых задач матричной коррекции. Получен также важный результат, облегчающий переход от задач коррекции систем линейных алгебраических уравнений к задачам коррекции несобственных задач ЛП - достаточные условия единственности решения скорректированной системы.

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

В четвертом параграфе рассматриваются вопросы регуляризации решений изначально несовместных систем линейных алгебраических уравнений в процессе их матричной коррекции по минимуму .м/ -нормы. Указанная проблема требует некоторых пояснений. Как было показано в § 3, задачи оптимальной матричной коррекции сами могут быть несобственными или приближаться к таковым. На практике это означает, что решения скорректированных систем велики или неограниченны по норме. Подобная ситуация, возникающая в задачах матричной коррекции по минимуму евклидовой нормы, рассматривалась ранее в главе 2. Там были указаны некоторые методы ее преодоления -Nongeneric TLS и регуляризации задачи коррекции по Тихонову. К сожалению, для задач матричной коррекции в нормах, отличных от евклидовой, трудно предложить методы регуляризации, подобные Nongeneric TLS, поскольку при рассмотрении отношения двух векторных норм вместо отношения Рэлея, трудно найти аналог собственным значениям матрицы. По этой же причине затруднена и регуляризация по Тихонову - при ее классическом воплощении необходимо решать задачу минимизации отношения векторных норм с ограничением на величину знаменателя указанного отношения. В настоящей работе предложено два подхода к регуляризации исследуемых задач, близких к регуляризации по Тихонову (но не совпадающих с ней). Оба подхода предполагают, что матрица коррекции исследуемой системы является одноранговой. При этом первый способ регуляризации сводится к нахождению условного экстремума с ограничением в форме равенства, а второй - к минимаксной задаче без ограничений.

Пятый параграф посвящен исследованию задач оптимальной матричной коррекции несовместных систем линейных алгебраических уравнений с условием неотрицательности по минимуму некоторой .м/ -нормы. Результаты, полученные в указанном параграфе являются обобщением соответствующих результатов, полученных для задач матричной коррекции несовместных систем линейных алгебраических уравнений с условием неотрицательности по минимуму евклидовой нормы и представленных в § 1. главы 2 - это необходимые и достаточные условия задач матричной коррекции, вид оптимальных матриц коррекции и множеств решений скорректированных систем. Кроме того, приведены утверждения, характеризующие достаточные условия единственности решений соответствующих скорректированных систем. Указанные утверждения являются следствиями теорем, рассмотренных в § 3 главы 3, и важны для проблем коррекции допустимой области несобственных задач ЛП 1-го или 3-го рода в канонической форме (или допустимой области двойственной задачи для несобственной задачи ЛП 2-го рода в основной форме), поскольку являются достаточными условиями собственности соответствующих скорректированных задач ЛП.

Шестой параграф специально посвящен исследованию достаточных условий собственности скорректированных по минимуму .р#-нормы несобственных задач ЛП 1-го и 3-го рода в канонической форме. Полученные результаты являются обобщениями на случай -м/ -нормы соответствующий достаточных условий собственности задач ЛП, скорректированных по минимуму евклидовой нормы, представленных в § 2 второй главы.

Проблематика седьмого параграфа - задачи матричной коррекции несовместных систем линейных алгебраических уравнений с условием неотрицательности и показателями качества коррекции специального вида - .f", У Л-Н и \\.\&кх -норм. Указанные задачи представляют собой важный частный случай задач матричной коррекции, и поэтому заслуживают отдельного рассмотрения. Во-первых, упомянутые выше матричные нормы тесно связаны с весьма употребительными в прикладных задачах (в основном - задачах оценивания неизвестных параметров по подверженным шуму и ошибкам экспериментальным данным) полиэдральными векторными нормами Ц-Ц,, ю и их "взвешенными" модификациями.

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

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

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

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

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

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

Интервальной матрицей принято называть множество матриц, удовлетворяющих некоторой системе поэлементных двухсторонних ограничений [162]. Интервальную матрицу называют невырожденной, если все матрицы указанного множества являются невырожденными. Известно, что в общем случае проверка невырожденности интервальной матрицы является NP-трудной [206]. В настоящей работе, используя математический аппарат, разработанный для задач оптимальной матричной коррекции несовместных систем линейных алгебраических уравнений, удалось получить новые достаточные условия невырожденности интервальных матриц, сводящиеся к определению . , -нормы так называемой центральной матрицы. Кроме того, удалось выделить класс интервальных матриц, для которого указанные условия являются также необходимыми, и подкласс интервальных матриц, для которого указанные условия могут быть проверены за полиномиальное время. Был также проведен вычислительный эксперимент по проверке чувствительности предложенных необходимых и достаточных условий невырожденности интервальной матрицы к погрешностям в задании ее центральной матрицы, который показал, высокую численную устойчивость указанных условий.

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

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

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

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

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

Для решения рассматриваемой задачи матричной коррекции в работе предложен алгоритмический подход, основанный на "векторизации" задачи и ее линеаризации. Линеаризация осуществляется стандартным образом, а "векторизация" основана на взаимно однозначном соответствии, существующем между вектором порядка N и матрицей Теплица с размерами (N-n + \)xn. Указанный подход конкретизирован и доведен до уровня работающего вычислительного алгоритма в трех вариантах, соответствующих использованию в роли показателя качества матричной коррекции взвешенных с неотрицательными весами .f, .(2 и Ц.Ц матричных норм.

Вычислительные алгоритмы матричной коррекции по минимуму взвешенных Н-Н?,, 11-Ц -норм на каждой итерации требуют решения вспомогательных задач ЛП. Вычислительный алгоритм матричной коррекции по минимуму взвешенной евклидовой нормы на каждой итерации требует нахождения нормального решения недоопределенной СЛАУ и минимизации квадратичной функции при наличии ограничений в виде системы линейных алгебраических уравнений. Эффективные вычислительные алгоритмы решения обеих вспомогательных задач, основанные на ортогональных разложениях матриц, хорошо известны [117]. Однако с целью лучшей "читаемости" и компактности записи соответствующих формул, решения обеих вспомогательных задач представлены в терминах соответствующих псевдообратных матриц.

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

Результаты вычислительных экспериментов оказались вполне ожидаемыми. Так, в зависимости от выбора стартовой точки наблюдалась сходимость как в точку глобального минимума, та и в точки локального минимума, а при минимизации взвешенной Ц.Ц -нормы наблюдалось в том числе и "заедание" итераций без их продвижения к какую либо точку локального минимума. Сходимость к точке останова при минимизации взвешенных норм Н.Нс, и 11-111 как по аргументу, так и по целевой функции оказалась сверхлинейной. Сходимость к точке останова при минимизации взвешенной евклидовой нормы как по аргументу, так и по целевой функции оказалась близка к линейной.

Шестой параграф является иллюстрацией практического использования задач матричной коррекции, рассмотренных в предыдущем параграфе, для решения задач параметрической идентификации сигнала, представляющего собой сумму показательных функций. Параграф содержит краткое описание метода де Прони и его модификаций [114, 123], в рамках которого и происходит сведение задачи параметрической идентификации динамического сигнала к задаче матричной коррекции однородной СЛАУ с матрицей Теплица или Ганкеля. Кроме того, приводятся результаты оценивания параметров известного модельного примера К. Ланцоша [114] с помощью методов матричной коррекции, изложенных в § 5, по минимуму ll-llc,, l.f2 и \\.\\ст -норм, а также результаты, полученные для данной задачи с помощью других методов и другими исследователями. Сравнение результатов оказывается в пользу рассматриваемых в настоящей работе методов.

Седьмой параграф посвящен дополнительному исследованию задач матричной коррекции систем линейных алгебраических уравнений со специальной структурой по минимуму взвешенной евклидовой нормы. Он продолжает линию использования метода Ньютона, начатую в § 6 первой главы. Материал параграфа перекликается также с результатами, полученными в § 6 второй главы. Результаты исследования оказываются достаточно интересными. Так, удается выделить большой класс матриц со специальной структурой, к которому, в частности, принадлежат и матрицы Теплица (Ганкеля), для которого задачу матричной коррекции по минимуму взвешенной (с индивидуальными для каждого коэффициента неотрицательными весами) евклидовой нормы удается свести к задаче минимизации дифференцируемой функции. Для указанной целевой функции с использованием методов дифференцирования псевдообратных матриц, являющихся специальным частным случаем методов, изложенных в работе [183], удается в терминах некоторых параметрических матриц и матриц, обратных к ним, получить формулы для частных производных первого и второго порядка, которые и открывают путь к реализации задачи, заявленной в указанном параграфе в качестве основной - к использованию метода Ньютона для решения задач матричной коррекции несовместных систем линейных алгебраических уравнений со специальной структурой по минимуму взвешенной евклидовой нормы.  

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

Введем и поясним некоторые дополнительные обозначения. Пусть D є Е"х" -некоторая симметричная матрица. Как известно, (см., например, [158]), все ее собственные значения являются вещественными. Условимся некоторое собственное значение матрицы D обозначать как A(D). Минимальное собственное значение матрицы D будем обозначать как ЯШІ11( ). Множество собственных векторов матрицы D, соответствующих собственному значению Xmin(D) будем обозначать как Xmin(D), множество нормированных (имеющих единичную евклидову норму) векторов матрицы D, соответствующих собственному значению A,nill(D) будем обозначать как ХШІП(Д). Соответствующие множества собственных векторов, относящихся к произвольному X(D), будем обозначать как Х( Д X) и Х( Д Я). Для множества (набора) собственных значений матрицы D будем использовать обозначение eigenvals(D). Для кратности некоторого собственного значения X(D) будем использовать обозначение к (Я, D). Напомним, что для вещественной симметричной матрицы геометрическая кратность собственного значения, определяемая как ранг системы собственных векторов, относящихся к данному собственному значению, совпадает с алгебраической кратностью, т.е., с кратностью соответствующего корня характеристического многочлена матрицы.

Кроме того, нам потребуются обозначения, связанные с сингулярным разложением матриц. Пусть U є R"K" - некоторая матрица ранга г. Пусть q = min{w, п}. Соответствующие обозначения, которые мы собираемся обсудить, оказываются наиболее "нагруженными" при выполнении условия \ r q, (1.2.1) которое и будет пока предполагаться. Как известно (см., например, [158]), для матрицы U возможно представление вида U = VI,WT, (1.2.2) где V є Ш "х " - ортогональная матрица, составленная из собственных векторов матрицы UU1, W є R" " - ортогональная матрица, составленная из собственных векторов матрицы UTU, 1 = ( Гц) е М "х", причем ан - 0 для всех/ Ф j, о-,, сг22 ... а,.,. Jr+Ur+] = ... = am = 0. (1.2.3) Заметим, что при выполнении условия г - q соотношение (1.2.3) принимает вид 7„ 722 ... rw 0. (1.2.4)

Следуя традициям, вместо ан будем писать от. Величины ег,. принято называть сингулярными числами матрицы U, а представление (1.2.2) - ее сингулярным разложением. В последующих выкладках окажется полезным специальное обозначение ег iiin (U) для минимального сингулярного числа матрицы U. Как несложно заметить, в силу соотношения (1.2.2), UTU = WkW\ (1.2.5) UUT=VMVT, (1.2.6) где Л = diag(o-12, а\,..., а), 0,..., 0) є Ж"х", М = diag 2, а\,..., G), 0,..., 0) є К"ш", т.е., ненулевые собственные значения матриц UTU и UUT - это квадраты ненулевых сингулярных чисел матрицы U. В частности, АЛи1и) = (уии). (1.2.7) Для последующих выкладок нам будет полезна еще одна (эквивалентная выражению (1.2.2)) форма представления сингулярного разложения матрицы U : / = w,T, (1.2.8) где v, - столбцы матрицы V, wt - столбцы матрицы W. Для полноты изложения заметим, что если числа 7,,а"2,...,сг,. различны, то векторы v,. и wi определяются с точностью до знака. Если же для некоторого номера 1 к г имеем сгк = сгк+1 = ... = ак+ , где р 1, то векторы vk,vk+i,...,vk+ и wr,wk+],...,wr+ определены не однозначно, а с точностью до соответствующего линейного подпространства. То же самое верно в отношении векторов v,.+1,...,v()I и wr+],...,wn, соответствующих нулевым сингулярным числам матрицы U .

Сингулярное разложение тесно связано с двумя важнейшими матричными нормами: евклидовой и спектральной благодаря важному свойству унитарной инвариантности (см., например, [158]). Поскольку существуют разные подходы к введению понятия спектральной матричной нормы и изложению ее свойств, уточним, что в настоящей работе определением спектральной матричной нормы \\U\\2 матрицы U є R "x" считается формула Ш =тахИ. (1.2.9) ХФО Ы Утверждение 1.2.1. Евклидова матричная норма является унитарно-инвариантной. Утверждение 1.2.2. Спектральная матричная норма является унитарно-инвариантной. Поскольку мы условились иметь дело только с вещественными матрицами, утверждения 1.2.1 и 1.2.2 сводятся к утверждениям о неизменности евклидовой и спектральной нормы некоторой матрицы при умножении ее (слева или справа) на произвольную ортогональную матрицу.

Достаточные условия собственности скорректированных по минимуму взвешенной (с помощью левого и правого умножения на невырожденные матрицы) евклидовой нормы несобственных задач ЛП 1-го и 3-го рода в канонической форме

Пусть А є Ж" х", Ъ є W, х,х є Ж", х Ф 0, х є Х+ (А,Ь) Будем называть непустое множество Х+ (А,Ь) ограниченным по направлению х, если \/хєХ+(А,Ь)Зу 0\у у=ї(х0+ух)еХ+(А,Ь) (2.2.1) и неограниченным по направлению х в противном случае. Лемма 2.2.1. Пусть для некоторой несовместной системы вида (2.1.1) задача Є1шаҐ8Ш{АЬ) имеет решение - некоторую матрицу [я -/г ]єК "х("+1). Тогда множество Х+(А + Н ,b + h ) ограничено по направлению d, т.е. вдоль любого луча вида х(а) = х +ad, где xeR" - произвольный вектор, принадлежащий Х+(А + H ,b + h ), а О - некоторое число, а вектор d є К" удовлетворяет условиям d О, (2.2.2) И = 1» С2-2-3) Ad = 0. (2.2.4) Доказательство. Заметим, что в силу сделанных предположений х(а) 0 для (а) любого а 0. Рассмотрим матрицу Г#(а) И(а) = (Ь-Ах(а)У . Как было х 1 показано в первой главе, в силу леммы Тихонова [144] и сделанных допущений, справедливы условия х{а)е X+(A + H(a),b + h(a)), I N? II Il2 b-Ax(a)\\ \\b-Ax0\\ ці ii.u. -п.имн = \JL = 1 И- №- v v -!/ II / \ll2 1 / \ll2 і x(a) +l \\x(a)\\ +l Теперь несложно заметить, что при а -» +оо имеем р(«) - +00, и, как следствие, [Я(а) -А(а)] - 0Ф [я(а) -й(а)]- 0= і[я(а) -A(a)]R-»0, что в силу теоремы 2.1.1 противоречит утверждению о разрешимости задачи с Ги,ыЫ,ь).

Лемма 2.2.2. Пусть для некоторой несовместной системы вида (2.1.1) задача С щ 8 ""1 (А,Ь) имеет решение - некоторую матрицу Я єМ "х". Тогда множество ХЛ\А + Н ,Ь) ограничено по направлению d, т.е. вдоль любого луча вида х{а) = х +ad, где xeR" - произвольный вектор, принадлежащий Х+(А + Н ,Ь), а 0 - некоторое число, а вектор d є Ж" удовлетворяет условиям (2.2.2)-(2.2.4).

Доказательство. Рассмотрим матрицу H(a) = (b-Ах{а)Ух+ (or). Повторяя рассуждения, использованные при доказательстве леммы 2.2.1, получаем: x(a)eX+(A + H(a),b), Я(а). =й-Лх(а)-л:(а) = р-Лх-х(аг) , а +оо= л;(а)- +аз= Я(аг). - 0оЯ(а)- 0 ІЯ(а)Я- 0, что в силу теоремы 2.1.4 противоречит утверждению о разрешимости задачи

Поставим несобственной задаче линейного программирования 1-го или 3-го рода вида (2.1.1)-(2.1.2) в соответствие задачи матричной коррекции C lw,i sh":d (А,Ь) и C f ,}ghM {А, Ъ). Справедливы следующие утверждения:

Теорема 2.2.1. Если задача c e,shted (А, Ь) имеет решение - некоторую матрицу \Н -h 1, а система (2.1.1) несовместна даже без учета условия х О, то задача ЛП (Л + Я )х = & + /? , x 0, cTx- max (2.2.5) является собственной.

Доказательство. В силу леммы 2.2.1. множество ХАА + H\b + h ) ограничено вдоль любого луча вида х(а) = х+ші, где хєМ" - произвольный вектор, принадлежащий указанному множеству, а О - некоторое число, а вектор d є №" удовлетворяет условиям (2.2.2)-(2.2.4). Предположим теперь, что решение задачи (2.2.5) неограничено. Это возможно, если существуют вектор х(/?) такой, что х{р) = z + fig є Х+ (А + Н\Ъ + h ) V/? О, где z,geW, g = l и clg 0.

Но при доказательстве теоремы 2.1.2 было показано, что из несовместности системы Ах = b следует условие Ag = О. Теперь, если мы допустим, что g 0, то х(/?) оказывается частным случаем х(а), т.е., вдоль луча х(/?) область ХАА + H ,b + h ) ограничена. Если же предположим, что условие g 0 не выполняется, то опять получаем ограниченность допустимой области вдоль луча (/?) в силу условия х(/3) 0.

Теорема 2.2.2. Если задача C { 8h"!d (A,b) имеет решение - некоторую матрицу Н , а система (2.1.1) несовместна даже без учета условия х 0, то задача ЛП (Л + Я )х = М 0,стх- -тах (2.2.6) является собственной.

Доказательство. В силу леммы 2.2.2. множество Х+ у А + Н \b) ограничено вдоль любого луча вида х(а) = х +ad, где хєМ" - произвольный вектор, принадлежащий указанному множеству, а 0 - некоторое число, а вектор d є Ж" удовлетворяет условиям (2.2.2)-(2.2.4). Предположим теперь, что решение задачи (2.2.6) неограничено. Это возможно, если существуют вектор x(fi) такой, что х{0) = z + pgzX+{A + Н\Ь) V/? О, где z,geR", \\g\\ = l и cTg 0.

Но при доказательстве теоремы 2.1.5 было показано, что из несовместности системы Ах - b следует условие Ag = 0. Теперь, если мы допустим, что g 0, то x(fi) оказывается частным случаем х(а), т.е., вдоль луча х(/?) область Х+(А + Н ,Ь) ограничена. Если же предположим, что условие g 0 не выполняется, то опять получаем ограниченность допустимой области вдоль луча x(fi) в силу условия х(/?) 0.

Рассмотрим задачу математического программирования вида f(x) = xTQx mm,x 0,xTx = \, (2.3.1) где xeR", QeWx" - симметричная матрица. В настоящем параграфе мы проведем детальное теоретическое и вычислительное исследование указанной задачи, а также покажем, что она может служить инструментом для решения задач матричной коррекции С%Ґ (А,Ь)яС% (А,Ь).

Несложно заметить, что при выборе в задачах С Г К "Ы (А,Ь) и С иы (А,Ь) единичных матриц соответствующих размерностей в качестве весовых матриц L, R и R, мы получим задачи матричной коррекции, исследовавшиеся в работах [21, 40, 43, 46, 56, 112]. Обозначим указанные задачи как С1оЫ(А,Ь) и Сfix{b] (А,Ь), а оптимальные значения их целевых функций как кШа1 (А,Ь) и Kflx[h] (A,b) . Существует и второй, более содержательный способ перехода от задач C ; Jeish";d {А,Ь) и С ЛЫ (А,Ъ) к задачам С1ош1(А,Ь) и Cflx{b](A,b). Он заключается в том, что в силу теорем 2.1.1 и 2.1.4 "взвешенные" задачи С Г "Ш{А,Ь) и С шы (А,Ь) сводятся к "не взвешенным" задачам С1О1О1(А,Ь\ И CMbAA,b), В которых матрицы А, А и векторы Ь, Ъ определяются по формулам (2.1.4), (2.1.42), (2.1.43). Сами же задачи Ctotal(A,b) и C/il{/), (A,b), как будет показано ниже, сводятся к задаче (2.3.1).

Регуляризация решений изначально несовместных СЛАУ при матричной коррекции их коэффициентов по минимуму ЦІ i - нормы

Рассмотрим в начале три вспомогательные задачи: Задача А: у/ф - Ах) - inf . Данная задача разрешима в силу известного следствия теоремы Вейерштрасса, так как ц/{Ъ - Ах) - непрерывная функция, удовлетворяющая условию ц/{Ь - Ах) - +оо при р(х) - +оо. Таким образом, Argmin \y/{b - Ах)] Ф 0 , и, в силу несовместности системы х (1.1.1) и свойств (3.1.1а), (3.1.1b), тт{у/ф-Ах)} = 9 0. (3.4.1) Вышесказанное обосновывает корректность постановки другой задачи: Задача В: (x)-»min, х є Argmin {у/ф-Ах)} . Х X

Минимальное значение целевой функции в данной задаче (обозначим его символом 77) достигается либо в силу теоремы Вейерштрасса (если Argmin\у/ф-Ах)} - замкнутое х и ограниченное множество), либо в силу следствия из данной теоремы (в противном случае). Очевидно, что ] 0, однако мы сделаем дополнительное предположение относительно параметра в, которое позволит в последующих рассуждениях не рассматривать случай т/ = 0. Так, дополнительно предположим, что 9 у/(Ь). (3.4.2) Тогда действительно г/ О, так как в противном случае можно показать, что в = ц/ф).

Заметим, что 0 = i//(b) А = 0. Это, в силу условий (3.1.1а), (3.1.1b) следует из соотношений i//(b - Ах) у/(Ь) + цг(Ах) i//(b) + Л / ср{х), справедливых, в свою очередь, в силу соотношений (3.1.3) и (3.1.8). Данный случай является достаточно специальным, и в настоящей работе рассматриваться не будет.

Итак, мы обосновали выполнение условий rj О и в О, что, в свою очередь, делает возможным ввести в рассмотрение величину к = - 0. (3.4.3)

Последняя вспомогательная задача была подробно исследована при доказательстве теоремы 3.3.4: Задача С: у/(Ь- Ах) - inf. р(х) Пусть MyHb-Axi=r причем теперь мы не делаем никаких специальных предположений о достижимости . у/(Ъ - Ах) inf р(х) Задачи А, В и С полезны тем, что позволяют ввести в рассмотрение величины АГ и у, необходимые для последующих выкладок. Заметим , что у к в силу постановки задачи С. Обратимся теперь к рассмотрению основных задач данного параграфа: Задача N0: q (x) - min при условии 4 -r S. (3.4.5) где S 0 - некоторое число. . i/zib-Ax) Задача N]: ср{х) - mm, — у + о, где о 0 - некоторое число. q (x) \щ(Ь-Ах) . .1 Задача N2: max — -, р {х) \ - mm. [ к + є J

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

Задача N3:. Для некоторых заданных параметров М 0 и 8 0 найти такие вектор хєШ." и матрицу Я el , что xeX(A + H,b), \\Н\\ у + 8, (x)-»min, р(х) М.

Пусть Х0,Х,,Х2 - множества решений задач Л ,Л ,]У2, а ф0,ф],ф1 соответствующие оптимальные значения целевых функций.

Покажем, что справедливы следующие теоремы: Теорема 3.4.1. Пусть несовместной системе линейных уравнений вида (1.1.1) поставлены в соответствие задачи А,В,С,N0,N], причем последние две задачи рассматриваются при произвольном значении параметра 8 0 . Тогда задачи N0, JV, разрешимы и имеют место соотношения Хо=Х]Ф0,фо=ф] О. Доказательство. 1. Покажем, что ограничению (3.4.5) задачи N0 удовлетворяет непустое множество точек для любого числа 8 О. Действительно, пусть х є К" - некоторый вектор такой, что р(х) = 1, шф-а -Ах) п „ . -ц/ф-Ах) ,гдеО а +GO,еслиinf (р{а х) х р(х) Г = достигается на векторе а х, ,. шф-а-Ах) lim 1 в противном случае. а +т (р(а х) Положим 1 . . ц/ф - Ах) —, если ml достигается, г = -J а х р(х) О-в противном случае, и рассмотрим вспомогательную функцию -8, если г = г , Аг) = \шф-т-]-Ах) 1 Гр=: у-8, если г т . р(т -х) Несложно убедиться, что функция /(г) непрерывна на луче гє[г ,+оо[ и существует число т 0 такое, что /(т") 0. Этого достаточно, чтобы для некоторого f, где г т г , выполнялось условие /(r) = 0oyv =у + 8, где х = т ] -х - и есть искомое решение уравнения (3.4.5). Заметим, что этот вектор ненулевой и его норма ограничена, т.е., О ср(х) +оо. 2. Поскольку целевая функция задачи N0, будучи векторной нормой, является непрерывной, причем на допустимой области, задаваемой ограничением (3.4.5), возможное ее неограниченное возрастание, ее минимум достигается в силу известного следствия из теоремы Вейерштрасса.

Минимаксная матричная коррекция матричной игры

Рассмотрим семейство матриц A AcAi=[Ac-AA,Ac + AA] = {AeWK"\Ac-AA A Ac + AA}, (4.2.1) где Ас,ААе W", АА 0 и знаки " " и " " трактуются как знаки поэлементных операций. Объект А д , задаваемый формулой (4.2.1), в литературе по интервальным вычислениям принято называть интервальной матрицей. При этом Ас называют центральной матрицей, а, АА - матрицей радиуса. Интервальную матрицу к А д называют невырожденной (см., например, [169]), если каждая матрица АеА!АК является невырожденной, что эквивалентно, например, отсутствию нетривиальных решений іеі" у однородного уравнения Ах = 0 VAeA . В противном случае интервальную матрицу А д называют вырожденной.

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

Чл =&-ДАА+Д ] гДе K beRn b- содержится в некотором интервальном векторе х . д = [хс - Ах, хс + Л J, где хс, Av є R", Ах О [228].

Наряду с исследованием невырожденности интервальной матрицы А д общего вида (4.2.1) представляет интерес исследование невырожденности интервальной матрицы специального (достаточно простого) вида А АсЄ=[Ас-єЕ,Ас + ЕІ (4.2.2) где seR, є 0, ЕеШ"х" - матрица, все элементы которой - единицы. Несложно заметить, для всякой А , д найдется такое число є, (которое мы в дальнейшем будем назвать радиусом интервальной матрицы А , е) что будет справедливо условие А; с А7

Как известно, (см., например, [206]), задача проверки невырожденности интервальной матрицы является NP-трудной. В работе [218], посвященной проверке положительной определенности симметричной интервальной матрицы, было показано, что проверка невырожденности интервальной матрицы вида (4.2.2) для произвольного рационального є 0 и некоторой симметричной положительно определенной матрицы с неотрицательными рациональными элементами Ас также является NP-трудной. В связи с этим становится актуальной проблема получения некоторых относительно простых и практичных в вычислительном плане критериев ("verifiable conditions"), способных выполнять роль достаточных условий невырожденности интервальных матриц. Одной из последних работ, посвященных указанной теме, является, по-видимому, работа [215]. Эта работа содержит как обзор классических результатов, так и новейшие результаты, полученные авторами статьи и другими исследователями. Это - четыре формулировки достаточных условий невырожденности и пять формулировок достаточных условий вырожденности интервальных матриц, которые представлены в приведенной ниже таблице 4.2.1. Формулировки всех критериев цитируются по статье [215], однако в таблице указаны также ссылки на оригинальные работы. Некоторые результаты были получены независимо разными авторами, ряд ранее известных результатов обоснован авторами работы [215] с использованием другой техники. Мы не приводим здесь всех деталей, за которыми можно обратиться к работе [215].

Заметим, что и достаточные условия невырожденности, и достаточные условия вырожденности интервальных матриц, приведенные в работе [215], не содержат в явном виде формулы или алгоритма, по которым для некоторой заданной матрицы Ас можно было бы построить соответствующую матрицу А или єЕ так, чтобы интервальная матрица вида (4.2.1) или (4.2.2) обладала заданным свойством невырожденности или вырожденности.

Попытка устранить указанный недостаток и предпринята в настоящем параграфе. Введем некоторые обозначения. Так, для матрицы, составленной из абсолютных величин матрицы A = (a,j) будем использовать закрепившееся в интервальном анализе обозначение [ А = ( а01). Опять же в рамках установившихся традиций, запись вида х будем считать записью вектора, к которому применена поэлементная операция вычисления абсолютной величины. Неравенства вида " "," "," "," ", примененные к матричным и векторным объектам, будем считать поэлементными. Символом р(А) будем обозначать спектральный радиус матрицы А; символами ЯтЫ (А) и Ятах (А) -обозначать соответственно минимальное и максимальное собственное значение симметричной матрицы А. Для вектора, составленного из собственных значений матрицы А будем использовать обозначение eigenvalues ). Символом / будем обозначать единичную матрицу, символом Е - матрицу, все элементы которой являются единицами. Для элемента с индексами i,j матрицы, задаваемой некоторой формулой, будем использовать обозначение (...),.,.. Например, запись (ДТ1),, означает элемент с индексами i,j матрицы А 1. Запись вида (...); будет обозначать столбец с номером j матрицы (...), а запись (...),. - соответственно строку с номером / матрицы (...). Символом СОПС1У4 = Л- ЬГ для невырожденной матрицы А будем обозначать ее число обусловленности, определенное с использованием некоторой подчиненной нормы -.

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

Матричная коррекция данных для несовместных систем линейных уравнений и ее применение в задачах оптимизации и классификацииМуравьева Ольга Викторовна

Методы коррекции несовместных систем линейных уравнений и неравенств с блочной структурой и их применение к задачам обработки информацииЛе Ньят Зюи

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

О выделении полиномиальных подклассов в задаче целочисленного линейного программированияЧирков, Александр Юрьевич

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

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

Методы коррекции несовместных систем со структурными ограничениямиПеченкин Руслан Викторович

Оптимальная многопараметрическая коррекция хаотических динамических системТалагаев Юрий Викторович

Методы коррекции данных несовместных линейных систем комбинаторного типаКлименко, Оксана Александровна

Интервальный подход к регуляризации неточно заданных систем линейных уравненийГолодов Валентин Александрович