«В.А. ГОРЕЛИК, В.И. ЕРОХИН, Р.В. ПЕЧЕНКИН ЧИСЛЕННЫЕ МЕТОДЫ КОРРЕКЦИИ НЕСОБСТВЕННЫХ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ И СТРУКТУРНЫХ СИСТЕМ УРАВНЕНИЙ ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР ИМ. А.А ДОРОДНИЦЫНА РАН МОСКВА 2006 УДК ...»

РОССИЙСКАЯ АКАДЕМИЯ НАУК

ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР им. А.А. Дородницына

В.А. ГОРЕЛИК, В.И. ЕРОХИН, Р.В. ПЕЧЕНКИН

ЧИСЛЕННЫЕ МЕТОДЫ КОРРЕКЦИИ

НЕСОБСТВЕННЫХ ЗАДАЧ ЛИНЕЙНОГО

ПРОГРАММИРОВАНИЯ И СТРУКТУРНЫХ

СИСТЕМ УРАВНЕНИЙ

ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР ИМ. А.А ДОРОДНИЦЫНА РАН

МОСКВА 2006 УДК 512.643:519.85 Ответственный редактор чл. – корр. РАН Ю.Н. Павловский Монография посвящена исследованиям по многопараметрической (матричной) коррекции несовместных систем линейных алгебраических уравнений (СЛАУ) и несобственных задач линейного программирования (ЛП). Рассматриваются вопросы, связанные с задачей коррекции несовместных систем со структурными ограничениями. Приведены результаты вычислительных экспериментов.

Поддержано грантом РФФИ № 04-01-10025-Г.

Рецензенты А.А. Белолипецкий, В.С. Молоствов Научное издание c Вычислительный центр им. А.А. Дородницына Российской академии наук, Оглавление Введение 1 Матричная коррекция несобственных задач ЛП по минимуму евклидовой нормы 1.1 Коррекция несовместной СЛАУ с условием неотрицательности по минимуму взвешенной евклидовой нормы.................... 1.2 Достаточные условия собственности скорректированных по минимуму взвешенной евклидовой нормы несобственных задач ЛП 1-го и 3-го рода в канонической форме......... 1.3 Вычислительные примеры............ Выводы.......................... 2 Матричная коррекция несовместных СЛАУ и несобственных задач ЛП в обобщенных матричных нормах 2.1 Необходимые сведения о векторных и матричных нормах..................... 2.2 Обобщения задачи о решении СЛАУ относительно неизвестной матрицы с минимальной евклидовой нормой на гёльдеровы матричные нормы и ·, - нормы................ 2.3 Задачи матричной коррекции несовместных СЛАУ по минимуму · p, · LR и ·, - норм.... p 2.4 Методы матричной коррекции несовместных СЛАУ с условием неотрицательности по минимуму · LR, · LR, · LR и · LR -норм............ 1,1, 2.4.1 Матричная коррекция по минимуму · LR и · LR - норм несовместных СЛАУ с 1, условием неотрицательности решения. 2.4.2 Матричная коррекция по минимуму · LR и · LR - норм несовместных СЛАУ с, условием неотрицательности решения. 2.5 Вычислительные примеры............ Выводы.......................... 3 Оптимальная коррекция несовместных систем с матрицами блочной структуры 3.1 Постановки задач блочной коррекции...... 3.2 Решение задач блочной коррекции с квадратичными критериями............... 3.2.1 Редукция квадратичных критериев к задачам безусловной минимизации.... 3.3 Дифференцируемость целевой функции.... 3.3.1 Вычислительные эксперименты..... 3.4 Решение задач блочной коррекции с минимаксными критериями................. 3.4.1Редукция задач минимаксной коррекции к задачам условной оптимизации.... 3.5 Условия неразрешимости задач с минимаксными критериями................... 4 Коррекция несовместных систем с матрицами 4.1 Алгоритм обобщенной наименьшей нормы... 4.2 Модификация алгоритма обобщенной наименьшей нормы для систем с неточно заданной левой частью и фиксированной правой частью.. 4.3 Вычислительные эксперименты......... Данная монография является продолжением монографии В.А. Горелика и В.И. Ерохина "Оптимальная матричная коррекция несовместных систем линейных алгебраических уравнений по минимуму евклидовой нормы" [1] и вместе с ней подводит некоторые итоги исследований по многопараметрической (матричной) коррекции несовместных систем линейных алгебраических уравнений (СЛАУ) и несобственных задач линейного программирования (ЗЛП), которые проводились в ВЦ РАН и МПГУ исследовательской группой в составе В.А. Горелика, В.И. Ерохина, Р.Р. Ибатуллина, В.А. Кондратьевой, О.В. Муравьевой и Р.В. Печенкина [2-14]. Относительно истории вопроса и библиографической справки по данной тематике, как в России, так и за рубежом мы отсылаем к предыдущей монографии. В данной работе результаты монографии [1] развиты по следующим направлениям.

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

• Во – вторых, рассмотрены задачи коррекции СЛАУ и ЗЛП по минимуму обощенных (неевклидовых) матричных норм (гл. 2).

• В – третьих, рассмотрены задачи коррекции несовместных СЛАУ с определенной структурой, которая должна сохраниться после коррекции, что не сводится к комбинациям фиксированных (некорректируемых) строк и столбцов матрицы, рассмотренных [1]. В данной работе приведены два класса таких структур: блочные системы (гл. 3) и теплицевы системы (гл. 4), однако полученные результаты могут быть распространены и на системы с матрицами других структур (вандермондовы, разреженные).

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

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

В виду большого разнообразия форм, в которых могут быть представлены указанные ограничения (а, следовательно, и формулировки задач ЛП), введем некоторые обозначения без их привязки к конкретной форме записи задач ЛП. Так, пусть M - допустимое множество некоторой задачи ЛП, которую обозначим через L, а M - допустимое множество соответствующей двойственной задачи ЛП, которую обозначим через L. Как известно, один из основных результатов теории двойственности заключается в том, что задачи L, L разрешимы тогда и только тогда, когда множества M и M одновременно не пусты [16]. Разрешимые задачи L, L называют также собственными [18]. Если задачи L, L неразрешимы, их называют несобственными и различают следующие три случая:

При этом считают, что в случае (1.1) L - несобственная задача 1-го рода, L - несобственная задача 2-го рода, в случае(1.2) L - несобственная задача 2-го рода, L - несобственная задача 1-го рода, и в случае (1.3) L и L - несобственные задачи 3-го рода [18].

1.1 Коррекция несовместной СЛАУ с условием неотрицательности по минимуму взвешенной Пусть X+ (A, b) = {x |Ax b, x 0} - множество решений системы где A Rmn, x Rn, b Rm, b = 0. Наше основное предположение заключается в том, что X+ (A, b) = и система (1.4) нуждается в матричной коррекции. Теперь рассмотрим задачу ЛП в канонической форме, допустимая область которой является пустой и формально задается несовместной системой (1.4). Для полноты описания указанной задачи необходимо ввести в рассмотрение вектор c Rn и записать условие Согласно приведенной выше классификации указанная задача является несобственной задачей 1-го или 3-го рода.

Рассмотрим подход к коррекции исследуемой задачи ЛП, заключающийся в коррекции ее допустимой области. Очевидно, что указанный подход не единственный. Кроме того, он порождает следующий важный вопрос по существу проблемы коррекции несобственной задачи ЛП – не станет ли исследуемая задача после подобной коррекции несобственной задачей 2-го рода? Ведь непустота допустимой области в общем случае не гарантируют конечности оптимального значения целевой функции.

Ответом на поставленный вопрос являются достаточные условия ограниченности множеств X+ (A + H, b + h) и X+ (A + H, b), а также достаточные условия собственности скорректированных по минимуму взвешенной евклидовой нормы задач ЛП в канонической форме, рассмотренные в данной главе. При их выполнении коррекция соответствующей несовместной системы линейных алгебраических уравнений с условием неотрицательности может рассматриваться не только как коррекция допустимой области несобственной задачи ЛП 1-го или 3-го рода в канонической форме, но и как коррекция самой задачи ЛП, гарантирующая ее собственность (разрешимость) после такой коррекции. Более того, в силу известного факта теории двойственности – существования взаимного соответствия между задачей ЛП в основной форме (прямая задача) и задачей ЛП в канонической форме, указанные достаточные условия ограниченности множеств X+ (A + H, b + h) и X+ (A + H, b) и отвечающие им матричные коррекции могут быть использованы для "исправления" несобственных задач ЛП 2-го и третьего рода в основной форме. При этом коррекции следует подвергать ограничения двойственной задачи, являющейся несобственной задачей ЛП 1-го или 3-го рода в канонической форме.

Займемся теперь обоснованием данного утверждения. Введем некоторые вспомогательные обозначения. Пусть A Rmn - некоторая матрица. Символом A(0) будем обозначать матрицу, получаемую из A обнулением некоторых ее столбцов, а символом M (A)- множество всех матриц вида A(0) вместе с присоединенной к нему матрицей A. Таким образом, множество M (A) содержит 2n элементов. В дополнение к матрице A(0) будем рассматривать матрицу A(0), составленную из тех столбцов A, которые подверглись обнулению в A(0). Очевидно, что при A(0) = A матрица A(0) не существует. Будем считать, что в этом случае в приводимых ниже выкладках автоматически опускаются соответствующие формулы и условия с ее участием.

Пусть Q Rnn - произвольная симметричная матрица.

Как известно, (см., например, [33]), все ее собственные значения являются вещественными. Условимся некоторое собственное значение матрицы Q обозначать как (Q). Минимальное собственное значение матрицы Q будем обозначать как min(Q). Множество собственных векторов матрицы Q, соответствующих собственному значению min (Q) будем обозначать как Xmin (Q), множество нормированных (имеющих единичную евклидову норму) векторов матрицы Q, соответствующих собственному значению min (Q) будем обозначать как Xmin(Q). Соответствующие множества собственных векторов, относящихся к произвольному (Q), будем обозначать как X(Q, ) и X(Q, ). Для множества (набора) собственных значений матрицы Q будем использовать обозначение eigenvals(Q). Для кратности некоторого собственного значения (Q) будем использовать обозначение k(, Q). Напомним, что для вещественной симметричной матрицы геометрическая кратность собственного значения, определяемая как ранг системы собственных векторов, относящихся к данному собственному значению, совпадает с алгебраической кратностью, т.е. с кратностью соответствующего корня характеристического многочлена матрицы. Пусть для произвольной матрицы A Rmn Обозначим символом D (A) множество всех матриц вида D A(0) вместе с присоединенной к нему матрицей AT A.

Очевидно, что множество D (A), так же, как и множество M (A), содержит 2n элементов. Для последующих выкладок окажутся полезными следующие модификации множеств X(D, ) и X(D, ). Пусть X D A(0), - подмножество множества X D A(0),, содержащее только те собственные векторы матрицы D A(0), которые имеют компоненты в позициях с номерами, совпадающими с номерам обнуленных столбцов в матрице A(0). Пусть X D A(0), - подмножество множества X D A(0),, содержащее нормированные собственные векторы матрицы D A(0), причем только те, которые имеют компоненты в позициях с номерами, совпадающими с номерам обнуленных столбцов в матрице A(0).

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

LRweighted LRweighted где L Rmm - некоторая невырожденная матрица, R = (rij 0) R(n+1)(n+1) - невырожденная матрица, такая что R = R1 = (rij 0) (например, диагональная матрица с положительными элементами), и R = (rij 0) Rnn - невырожденная матрица, такая что Пусть Теорема 1.1.1. Пусть дана несовместная линейная система вида (1.4). Тогда 1. Для оптимального значения целевой функции в задаче LRweighted Ctotal (A, b) справедлива формула 2. Задача Ctotal (A, b) имеет решение тогда и только тогда, когда существует такая матрица 3. Решение задачи Ctotal (A, b) (если оно существует) есть ное значение, соответствующее собственному вектору z, является минимальным при переборе всех собственных значений всех матриц из множества D A b с учетом выполнения условий (1.9)-(1.12).

Доказательство. Предположим, что для некоторой b+h, x 0. Систему (A + H) x = b+h подвергнем некоторым преобразованиям. В силу невырожденности матриц L и R можно записать Рассмотрим последнюю систему в приведенной выше цепочке эквивалентных систем линейных алгебраических уравнений.

С использованием леммы А.Н. Тихонова [19] из нее можно единственным образом определить матрицу, являющуюся (при фиксированном векторе x) решением указанной системы, обладающим минимальной евклидовой нормой. Пусть Тогда с учетом (1.7) и (1.20) можно записать Но тогда матрица будет (при фиксированном векторе x) единственным решением системы (A + H) x = b + h, обладающим минимальной взвешенной евклидовой нормой · E. В силу (1.22) соответствующим выбором вектора z величину · E можно минимизировать. Поскольку мы предположили, что матрицы R и R1 состоят из неотрицательных элементов, справедливо утверждение x 0 z 0, с учетом которого из (1.22) и получаем (1.8).

В соответствии с (1.8) введем в рассмотрение функцию и рассмотрим задачу условной минимизации Составим для задачи (1.25) функцию Лагранжа и запишем условия Куна-Таккера, являющиеся необходимыми условиями существования условного минимума:

Очевидно, что если глобальный минимум в задаче (1.25) существует, то соответствующую ему точку z следует искать среди точек z, удовлетворяющих условиям (1.26)-(1.29).

Пусть существуют матрица A 0 и вектор y Rn+1 такие, что выполняются условия (1.9)-(1.12). Предположим, что с точностью до порядка перестановки компонент для вектора z справедливо представление Заметим, что в силу (1.30) нулением тех столбцов, номера которых совпадают с индексами нулевых элементов вектора z. Сформируем вектор как В силу (1.11), (1.30)-(1.31) выполняются условия (1.27)-(1.29).

Кроме того, заметим, что в силу (1.24), (1.30) и (1.10), В то же время Подставив две приведенные выше формулы в (1.26), убеждаемся, что указанное условие превращается в тождество.

Таким образом, мы показали, что если существует вектор z, удовлетворяющий условиям (1.10)-(1.11), то он же отвечает условиям Куна-Таккера задачи (1.25). Перебором среди указанных точек можно найти и точку минимума z функции f (z), т.е. решение задачи (1.25) существует. В силу (1.32) указанный перебор точек Куна-Таккера задачи (1.25) есть ни что иное, как поиск наименьшего собственного значения матрицы D([A b]0 ) (взятой из множества матриц D([A b]) такого, что соответствующий указанному собственному значению вектор z удовлетворяет условиям (1.9)-(1.12) или, что то же самое, условиям (1.17)-(1.18). Заметим, что в силу (1.10) z = 0, поэтому в соответствии с левой частью формулы (1.13) можно сформировать матрицу H h. А так как в отношении вектора z было сделано дополнительное предположение (1.12) (при условии (1.9)), то в соответствии с формулами (1.16)-(1.17) можно сформировать вектор x. Непосредственным использованием формул (1.9), (1.16) и левой части формулы (1.13) можно убедиться в выполнении условия (1.14). Действительно, во-первых, в силу неотрицательности элементов z, R и положительности yn+1 справедливо условие x 0. Во-вторых, В то же время в силу выкладок, приведенных для обоснования формулы (1.8), что завершает обоснование соотношения (1.13). Таким образом, достаточные условия существования решения задачи LRweighted Ctotal (A, b) обоснованы. Заметим, что в силу (1.8), (1.22), (1.24) и (1.32) справедливо условие (1.15). Следовательно, формулы (1.13)-(1.18) обоснованы.

и вектор x X+ (A + H, b + h ). Тогда, в силу (1.8), (1.20), (1.22) и (1.24) существует решение задачи (1.25) – вектор Но тогда существует также вектор Rn+1 такой, что для пары z, выполнены условия Куна-Таккера задачи (1.25), т.е. условия (1.26)-(1.29). Пусть для вектора z с точностью до порядка перестановки компонент справедливо представление, аналогичное (1.30), т.е.

Заметим, что в силу (1.34) вектор z можно нормировать, т.е.

где причем z 0 и в силу (1.24) Кроме того, для z и выполняются условия (1.26)-(1.29), т.е. z тоже является решением задачи (1.25). В силу условий (1.27)-(1.29) для вектора справедливо представление Подставляя (1.34) и (1.35) в (1.26), получаем соотношения где в матрице A подвергаются обнулению столбцы, соb ставляющие матрицу A L. Заметим, что в силу предb ставления (1.34) и тождества A 0 z A z, условие (1.37) можно переписать в виде откуда и следует выполнение условия (1.10). В то же время, дует условие (1.11). Сформируем теперь вектор y Rn+1 как y = ·. Несложно заметить, что указанный вектор существует, причем выполняется условие (1.12) и справедливы соотношения (1.9) и (1.16). Таким образом, необходимые условия существования решения задачи Ctotal (A, b) обоснованы.

ляются соответствующими матрицами Грамма столбцов матриц A 0, альтернативой условию (1.19) является услоb () вие = 0. Если предположить, что оно имеет место, то из (1.15) следует, что несовместная линейная система вида (1.4) может быть скорректирована с помощью матрицы с нулевой взвешенной нормой. В силу аксиомы невырожденности нормы это означает, что и сама матрица коррекции является нулевой, т.е. система (1.4) совместна (противоречие).

Замечание 1.1.1. Результаты, полученные в теореме 1.1.1 позволяют в качестве возможного варианта численного решения задачи Ctotal (A, b) рассматривать ее сведение к задачам математического программирования вида В строгом (формальном) смысле задачи (1.38) и (1.39) не эквивалентны, так как очевидным образом различаются их допустимые области. Тем не менее обе задачи разрешимы или не разрешимы одновременно, оптимальные значения их целевых функций совпадают, между аргументами существует соответствие. Все это позволяет в последующих выкладках игнорировать различия задач (1.38) и (1.39) (т.е. считать их эквивалентными).

решение - [H h ], а система (1.4) несовместна даже без учета условия x 0, то множество X+ (A + H, b + h ) состоит только из одного элемента – вектора x, определяемого формулами (1.16)-(1.18).

Доказательство. Пусть задача Ctotal (A, b) имеет решение - матрицу [H h ], но одновременно с условием (1.14) выполняется также условие где x = 0 - некоторый вектор. Тогда из условий (1.14) и (1.40) следует условие которое с учетом формул (1.13), (1.16)-(1.18) можно переписать в виде где Рассмотрим два случая:

1. Пусть = 0. Тогда условие (1.41) принимает вид откуда следует, что вектор x является решением несовместной в силу предположений данной теоремы системы Ax = b (противоречие).

2. Пусть = 0. Тогда из (1.41) следует условие а из (1.42) следует условие Решив систему (A + H) (x + x) = b + h относительно матрицы H h с минимальной взвешенной евклидовой нормой, оценим величину этой нормы. Проводя рассуждения, аналогичные использовавшимся при доказательстве теоремы 1.1.1, и учитывая (1.7), (1.16) - (1.18) и (1.43), имеем:

откуда в силу леммы А.Н. Тихонова и условий (1.8), (1.13), (1.22) и (1.44) имеем (противоречие).

Теорема 1.1.3. Пусть расширенная матрица коэффициентов A b Rm(n+1) несовместной системы вида (1.4), корректируется с помощью некоторой одноранговой R, а система (1.4) несовместна даже без учета условия x 0. Тогда для ограниченности множества X+ (A + H, b + h) достаточно, чтобы указанное множество содержало хотя бы один неотрицательный ограниченный по норме вектор x, а вектор d состоял только из положительных компонент.

В начале покажем, что условие d > 0 не противоречит существованию матрицы H h и вектора x с указанными выше свойствами. Действительно, откуда получаем, что для существования соответствующих [H h] и x требуется только выполнение условия (dT x) = 0, которое можно соблюсти при любом d подходящим выбором параметра. Установив корректность условия теоремы, займемся исследованием множества X+ (A + H, b + h). Рассмотрим два варианта.

1. X+ (A + H, b + h) состоит из одного элемента – вектора x. В этом случае теорема доказана в силу условия 2. X+ (A + H, b + h) содержит другие векторы кроме вектора x. Пусть, например, x+x X+ (A + H, b + h), где x Rn - некоторый вектор. В соответствии с определением множества X+ (A + H, b + h) вектор x + x является неотрицательным. В то же время вектор x ортогонален вектору d, что легко показать. Действительно, Но система Ax = b в силу исходных предположений несовместна, откуда и следует взаимная ортогональность векторов d и x. Но тогда, в силу положительности d вектор x должен иметь хотя бы одну отрицательную компоненту, и, в силу условия x + x 0, норма вектора x + x является конечной. А поскольку вектор x был выбран произвольно, это означает, что норма любого вектора из X+ (A + H, b + h) является конечной, что и означает ограниченность данного множества.

Пусть Можно показать, что справедлива следующая Теорема 1.1.4. Пусть дана несовместная линейная система вида (1.4). Тогда 1. Для оптимального значения целевой функции в задаче LRweighted Cf ix{b] (A, b) справедлива формула 2. Задача Cf ix{b} (A, b) имеет решение тогда и только тогда, когда существует такая матрица A(0) и такой вектор 3. Решение задачи Cf ix{b} (A, b) (если оно существует) есть а матрица A(0) такова, что ее собственное значение, соответствующее собственному вектору z, является минимальным при переборе всех собственных значений всех матриц из множества D(A) с учетом условий (1.48)-(1.51). При этом справедливо также условие (1.19).

Доказательство в целом аналогично доказательству теоремы 1.1.1.

Замечание 1.1.2. Результаты, полученные в теореме 1.1.4, позволяют в качестве возможного варианта численного решения задачи Cf ix{b] (A, b) рассматривать ее сведение к задачам математического программирования вида Теорема 1.1.5. Если задача Cf ix{b} (A, b) имеет решение – матрицу H, а система (1.4) несовместна даже без учета условия x 0, то множество X+ (A + H, b) состоит только из одного элемента – вектора x, определяемого формулами (1.55)-(1.56).

Доказательство в целом аналогично доказательству теоремы 1.1.2.

Теорема 1.1.6. Пусть расширенная матрица коэффециентов A Rmn несовместной системы вида (1.4), корректируется с помощью некоторой одноранговой матрицы H = cdT, где c Rm, d Rn, а система (1.4) несовместна даже без учета условия x 0. Тогда для ограниченности множества X+ (A + H, b) достаточно, чтобы указанное множество содержало хотя бы один неотрицательный ограниченный по норме вектор x, а вектор d состоял только из положительных компонент.

Доказательство теоремы аналогично доказательству теоремы 1.1.3.

1.2 Достаточные условия собственности скорректированных по минимуму взвешенной евклидовой нормы несобственных задач ЛП 1-го и 3-го рода в канонической форме Будем называть непустое множество X+ (A, b) ограниченным по направлению x, если и неограниченным по направлению x в противном случае.

Лемма 1.2.1. Пусть расширенная матрица коэффециентов A Rmn несовместной системы вида (1.4), корректируется с помощью некоторой одноранговой матрицы H = cdT, где c Rm, d Rn, а система (1.4) несовместна даже без учета условия x 0. Тогда для ограниченности множества X+ (A + H, b) достаточно, чтобы указанное множество содержало хотя бы один неотрицательный ограниченный по норме вектор x, а вектор d состоял только из положительных компонент.

Доказательство. Пусть для некоторой несовместной системы вида (1.4) задача Ctotal (A, b) имеет решение – некоторую матрицу Тогда множество X+ (A + H, b + h ) ограничено по направлению d, т.е. вдоль любого луча вида x () = x0 +d, где x0 Rn - произвольный вектор, принадлежащий X+ (A + H, b + h ), 0 - некоторое число, а вектор d Rn удовлетворяет условиям Заметим, что в силу сделанных предположений x () для любого 0. Рассмотрим матрицу Как было показано в первой главе, в силу леммы Тихонова [20] и сделанных допущений, справедливы условия Теперь несложно заметить, что при + имеем x () +, и, как следствие, что в силу теоремы 1.1.1 противоречит утверждению о разLRweighted решимости задачи Ctotal (A, b).

Лемма 1.2.2. Пусть для некоторой несовместной сиLRweighted стемы вида (1.4) задача Cf ix{b} (A, b) имеет решение – некоторую матрицу H R. Тогда множество X+ (A + H, b) ограничено по направлению d, т.е. вдоль любого луча вида x () = x0 + d, где x0 Rn - произвольный вектор, принадлежащий X+ (A + H, b), 0 - некоторое число, а вектор d Rn удовлетворяет условиям (1.58)-(1.60).

Доказательство. Рассмотрим матрицу H () = (b Ax ()) · x+ (). Повторяя рассуждения, использованные при доказательстве леммы 1.2.1, получаем:

что в силу теоремы 1.1.4 противоречит утверждению о разLRweighted решимости задачи Cf ix{b} (A, b) Поставим несобственной задаче линейного программирования 1-го или 3-го рода вида (1.4)-(1.5) в соответствие задачи матричной коррекции Ctotal (A, b) и Cf ix{b} (A, b).

Справедливы следующие утверждения:

Теорема 1.2.3. Если задача Ctotal (A, b) имеет решение – некоторую матрицу а система (1.4) несовместна даже без учета условия x 0, то задача ЛП является собственной.

Доказательство. В силу леммы 1.2.1 множество ограничено вдоль любого луча вида x () = x0 + d, где x0 Rn - произвольный вектор, принадлежащий указанному множеству, 0 - некоторое число, а вектор d Rn удовлетворяет условиям (1.58)-(1.60). Предположим теперь, что решение задачи (1.61) не ограничено. Это возможно, если существуют вектор x () такой, что где z, g Rn, g = 1 и cT g > 0. Но при доказательстве теоремы 1.1.2 было показано, что из несовместности системы Ax = b следует условие Ag = 0. Теперь, если мы допустим, что g 0, то x () оказывается частным случаем x (), т.е.

вдоль луча x () область X+ (A + H, b + h ) ограничена. Если же предположим, что условие g 0 не выполняется, то опять получаем ограниченность допустимой области вдоль луча x () в силу условия x () 0.

Теорема 1.2.4. Если задача Cf ix{b} (A, b) имеет решение – некоторую матрицу H, а система (1.4) несовместна даже без учета условия x 0, то задача ЛП является собственной.

Доказательство. В силу леммы 1.2.2 множество X+ (A + H, b) ограничено вдоль любого луча вида x () = x0 + d, где x0 Rn - произвольный вектор, принадлежащий указанному множеству, 0 - некоторое число, а вектор d Rn удовлетворяет условиям (1.58)-(1.60). Предположим теперь, что решение задачи (1.62) не ограничено. Это возможно, если существуют вектор x () такой, что где z, g Rn, g = 1 и cT g > 0. Но при доказательстве теоремы 1.1.5 было показано, что из несовместности системы Ax = b следует условие Ag = 0. Теперь, если мы допустим, что g 0, то x () оказывается частным случаем x (), т.е.

вдоль луча x () область X+ (A + H, b) ограничена. Если же предположим, что условие g 0 не выполняется, то опять получаем ограниченность допустимой области вдоль луча x () в силу условия x () 0.

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

Пример 1.3.1. Рассмотрим задачу со следующими ограничениями:

Последовательно получаем Пример 1.3.2. Рассмотрим задачу Пусть матрицы A, S, T, U и векторы b, d - такие же, как в примере 1.3.1, Последовательно получаем Глава посвящена задачам матричной коррекции несобственных задач ЛП с использованием показателей качества коррекции, основанных на евклидовой матричной норме и ее модификациях, а также задачам матричной коррекции несовместных систем линейных алгебраических уравнений с условием неотрицательности решения. Исследуемые несовместные системы тесно связаны с несобственными задачами ЛП 1-го и 3-го рода в канонической форме, а также с двойственными к ним (по своей формальной постановке) несобственными задачами ЛП 2-го рода в основной форме.

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

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

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

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

Функция (·) является векторной нормой, а функция (·) - аддитивной (обобщенной) матричной нормой, если для всех c R, x, y Rn, A, B Rmn выполняются следующие условия:

Условия (2.1) (неотрицательность). Условие (2.3) принято называть аксиомой абсолютной однородности, а условие (2.4) – неравенством треугольника.

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

Функцию (·), отвечающую условиям (2.1)-(2.5), принято называть мультипликативной матричной нормой или просто матричной нормой.

Если функция (·) является непрерывной и удовлетворяет условиям (2.1)-(2.3), то, следуя [33], будем называть ее векторной квазинормой.

Для произвольной векторной нормы (·) можно записать полезное для многих последующих выкладок свойство, вытекающее из условий (2.3) и (2.4):

Среди векторных норм наиболее употребительными являются так называемые нормы Гёльдера с показателем p 1.

Обычно их обозначают как · p. Определение векторной нормы Гёльдера с показателем p хорошо известно (см., например, [33]), но мы все же приведем его, так как оно часто будет использоваться в выкладках:

Гёльдеровой нормой с показателем p 1 для матрицы A Rmn будем называть величину, - нормой для матрицы A Rmn будем называть величину:

где (·) и (·) - некоторые векторные нормы. В общем случае · p и ·, - это обобщенные матричные нормы [33].

Отметим, что функцию ·, можно рассматривать как определенное расширение понятия подчиненной (индуцированной) матричной нормы [33], которая задается некоторой векторной нормой (x) и определяется для некоторой вещественной квадратной матрицы A как При этом в силу (2.9) выполняется весьма полезное соотношение, аналогичное свойству согласованности матричной и векторной норм:

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

Пример 2.1.1. Пусть (·) = · 2, (·) = · 2. Тогда A, = A 2,2 = max x 2 - спектральная норма [30] матx=0 рицы A. Заметим, что если матрица A - одноранговая, то (см., например, [23]) A 2,2 - ее спектральная и одновременно евклидова норма.

(см., например,[23]) 1. Тогда (как будет показано ниже) (см., например, [21, 33]) (см., например, [21, 33]) Функция где x, y Rn - некоторые векторы, (·) - некоторая векторная норма, называется векторной нормой, двойственной к норме (·) относительно скалярного произведения.

Норма (·) существует для любой нормы (·) [158].

Упорядоченную пару векторов x, y Rn называют двойственной парой по отношению к норме (·), если вектор y принадлежит множеству векторов, двойственных к x по отношению к норме (·) [158].

Заметим, что в силу (2.15) для произвольных x, y Rn и произвольной (·) справедливо неравенство Известно (см., например, [23]), что норма, двойственная к двойственной, совпадает с исходной, т.е.

Векторную норму, двойственную к векторной норме Гёльдера с показателем p будем обозначать как ·. Как известно (см., например, [23]), где q такое, что Векторные нормы Гёльдера – не единственные представители богатого семейства векторных норм. Дело в том, что указанные нормы могут быть подвергнуты определенным модификациям, в результате которых могут быть получены новые векторные нормы. Поскольку возможные потребности практики трудно предугадать, приведем три основополагающие теоремы [158], позволяющие конструировать новые векторные нормы из уже существующих:

Теорема 2.1.1. Если f (·) - квазинорма на пространстве Rn, то функция, построенная как двойственная к f (·) с использованием определения (2.15), является векторной нормой.

Теорема 2.1.2. Если 1 (x),..., n (x) и (x) - векторные нормы на Rn, то (x) = ([1 (x),..., n (x)]T ) - также векторная норма на Rn.

Теорема 2.1.3. Если (x) - векторная норма на Rn и T Rnn - невырожденная матрица, то (x) = (T · x) также векторная норма на Rn.

В качестве примера использования указанных теорем приведем следствие, получаемое из теоремы 2.1.3 и определения (2.9), которое показывает, как можно свести "взвешенную" ·, -норму к некоторой другой, "не взвешенной" ·, -норме: Пусть A Rmn, L Rmm, R Rnn - некоторые матрицы, причем rank L = m, rank R = n. Рассмотрим функцию В силу теоремы 2.1.3, где (·) - векторная норма на Rn, (·) - векторная норма на Несложно заметить, что с помощью данного следствия можно получить "взвешенные" варианты приведенных выше примеров 2.1.1 – 2.1.3. В частности, для наиболее простого, но часто встречающегося в практических приложениях случая, когда L и R - диагональные матрицы вида где =., r =. - некоторые векторы, такие что i > 0 i = 1,..., m, j > 0 j = 1,..., n, в соответствии с (2.20)-(1.23) получаем Вектор y Rn, удовлетворяющий условию для некоторого вектора x = 0, x Rn, называется двойственным к вектору x относительно нормы (·).

Известно (см., например, [33]), что для любой векторной нормы (·) и любого ненулевого вектора двойственный к нему вектор существует. Для последующих выкладок нам потребуется строить векторы, двойственные к заданным относительно некоторых Гёльдеровых норм.

Используя (2.15) и (2.24), несложно показать, что вектор y Rn, являющийся двойственным к некоторому заданному вектору x = 0, x Rn относительно нормы (·), может быть найден как решение следующей задачи условной максимизации:

В дальнейшем нам потребуется вектор y, двойственный к вектору x относительно нормы ·. В этом случае задача (2.25) принимает вид Условие (2.27) с учетом (2.7) и (2.19) можно переписать в виде Попробуем решить задачу (2.26), (2.28) методом множителей Лагранжа. Очевидно, что функция Лагранжа в данном случае имеет вид Теперь в соответствии с классической схемой метода множителей Лагранжа, следует выписать необходимые условия условного экстремума в виде условий Но, как нетрудно заметить, в общем случае (т.е. при произвольном p 1) при yi = 0 соответствующая частная производная yi L (y, ) (в классическом смысле) не определена.

Более того, поскольку векторная норма · получается из (2.7) предельным переходом вида при использовании наиболее важных для практических приложений норм · 1 и · в формуле (2.29) и последующих выкладках также необходимо делать предельные переходы.

Для преодоления указанных трудностей рассмотрим сначала частный случай: пусть все компоненты вектора x отличны от нуля и выполняется условие 1 < p < +.

Определим функцию sign () как Очевидно, что если = 0, то с учетом (2.31) можно записать С учетом (2.31) и (2.32) условия (2.30) принимают вид Решая систему условий (1.28), (2.33), получаем, что компоненты вектора y, двойственного к вектору x относительно нормы ·, единственным образом определяет формула:

Теперь оставим в силе условие 1 < p < +, но откажемся от предположения о том, что все компоненты вектора x = 0 отличны от нуля. Учитывая (2.31), несложно заметить, что в силу (2.34) из условия xi = 0 следует условие yi = 0. Но нулевые компоненты векторов x и y (с одинаковыми индексами) не меняют значения скалярного произведения y T x и норм y p и · x. Таким образом, формула (2.34) справедлива и в этом случае. Но возникает вопрос, будет ли в рассматриваемом случае вектор, двойственный к вектору x относительно нормы ·, единственным. Покажем это, расp суждая “от противного”. Пусть y Rn и z Rn - два вектора, таких что y = z, причем оба вектора являются двойственными к вектору x = 0, x Rn относительно нормы ·. За- p метим, что векторы y и z не могут быть линейно зависимы.

Пусть это не так и существует число = 0 такое, что z = y.

Поскольку оба вектора y и z являются двойственными к вектору x, имеем y T x = z T x = 1 y T x = y T x = 1, y = z, т.е. получаем противоречие с условием y = z.

Обратимся теперь к неравенству Минковского [13], которое справедливо при 1 < p < + и для линейно независимых векторов y и z является строгим:

В силу хорошо известного свойства |yi + zi | |yi | + |zi | при p > 1 имеем |yi + zi |p (|yi | + |zi |)p, и, таким образом, из (2.7) и (2.35) следует, что условие которое противоречит условию (2.16).

Итак, нами доказана Лемма 2.1.4. Вектор y Rn, двойственный к некоторому вектору x = 0, x Rn относительно нормы ·, где 1 < p < +, является единственным и определяется формулами (2.31), (2.34).

Обратимся теперь к исследованию единственности и способов построения вектора, двойственного к вектору x = 0, x Rn относительно норм · 1 и ·. Предельный переход p 1 в формуле (2.34) приводит к формуле где k - число компонент вектора x, для которых выполняется условие |xi | = x. Непосредственная проверка формулы (2.37) показывает, что она действительно определяет вектор y, удовлетворяющий условию y T x = y 1 · x = 1. В то же время, если k > 1, можно дополнительно (по отношению к формуле (2.37)) обнулить 1 t < k компонент вектора y, а оставшиеся ненулевыми компоненты вычислить по формуле Проверка (2.37), модифицированной с помощью (2.38), показывает, что по-прежнему выполняется условие y T x = y 1 · x = 1. Таким образом, вектор, двойственный к некоторому вектору x = 0, x Rn относительно нормы · = ·, в общем случае не является единственным.

Пример 2.1.6. Пусть Векторы y и z являются двойственными к вектору x относительно нормы ·. Предельный переход p в формуле (2.34) приводит к формуле Непосредственная проверка формулы (2.39) показывает, что она действительно определяет вектор, удовлетворяющий условию y T x = y · x 1 = 1. В то же время формулу (2.39) можно модифицировать следующим образом:

sign(xi ) в противном случае.

Проверка (2.40) показывает, что по-прежнему выполняется условие y T x = y · x 1 = 1. Таким образом, вектор, двойственный к некоторому вектору x = 0, x Rn относительно нормы · = · 1, в общем случае не является единственным.

Пример 2.1.7. Пусть Векторы y и z являются двойственными к вектору x относительно нормы · 1.

Замечание 2.1.1. Несложно заметить, что привлекая некоторые дополнительные условия (и тем самым, модифицируя классическое определение), можно добиться единственности вектора, двойственного к заданному относительно норм · 1 и ·. Для этого на множестве двойственных векторов достаточно выбрать вектор, минимальный по двойственной норме (или по любой другой норме · g, где 1 < g < +).

При p = 1 такой "модифицированный двойственный" к заданному вектору относительно · -нормы вектор будет задаваться формулой (2.37), а при p = "модифицированный двойственный" к заданному вектору относительно · 1 -нормы вектор будет задаваться формулой (2.39).

Лемма 2.1.5. Для произвольных векторов b Rm и y Rn справедливо соотношение Доказательство. В силу (2.7) и (2.8) Лемма 2.1.6. Для произвольных векторов b Rm и y Rn справедливо соотношение Доказательство. Из (2.9) и (2.15) следует, что Лемма 2.1.6 позволяет, в частности, подвести обоснование под приведенный выше пример 2.1.3. Действительно, пусть (·) = ·. Заметим (см., например, [23]), что в этом случае где A Rmn, c Rm, d Rn. Тогда, в силу леммы 2.1.6, Лемма 2.1.7. Для произвольной матрицы A Rmn и произвольного вектора x Rn справедливо неравенство Доказательство. Обозначим через ai,• строку матp (2.7) и (2.8), Лемма 2.1.8. Для произвольной матрицы A Rmn имеет место неравенство Доказательство. В силу (2.7) и (2.9) Пусть все элементы матрицы A являются неотрицательными числами, а все компоненты вектора x – единицы. В этом результат получается, если вектор x составлен из чисел 1.

Легко убедиться, что при любом другом выборе вектора x, отвечающего условию x = 1, справедливо неравенство Ax 1 < A 1, из чего, в силу (2.8) и (2.45) следует, что для любой матрицы с неотрицательными элементами Теперь заметим, что равенство (2.46) справедливо и для любой матрицы с неположительными элементами в силу аксиомы абсолютной однородности матричной нормы.

Рассмотрим теперь общий случай. Пусть матрица A содержит положительные, отрицательные и, возможно, нулевые элементы. Тогда она может быть представлена в виде A = A+ + A, где A+ – матрица, составленная из неотрицательных элементов, A – матрица, составленная из неположительных элементов. Используя неравенство треугольника и соотношения, полученные для неотрицательных (неположительных) матриц, имеем A,1 A+,1 + A,1 = A+ 1 + A 1 = A 1, что и требовалось доказать.

2.2 Обобщения задачи о решении СЛАУ относительно неизвестной матрицы с минимальной · 2 нормой на гёльдеровы Пусть дана система линейных алгебраических уравнений где A Rmn - неизвестная матрица, x Rn и b Rm заданные векторы, причем Первоначально рассмотрим следующие две задачи (их в определенном смысле можно считать базовыми):

Задача 2.1. Найти матрицу A, являющуюся решением системы (2.47)-(2.48) и имеющую минимальную · p - норму.

Задача 2.2. Найти матрицу A, являющуюся решением системы (2.47)-(2.48) и имеющую минимальную ·, - норму.

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

Теорема 2.2.1. Задача 2.2 разрешима, и, в частности, имеет решение из класса одноранговых матриц, задаваемое формулой где y Rn - вектор, двойственный к вектору x относительно нормы ·. При этом При 1 < p < + задача 2.2 имеет единственное решение.

Доказательство.

1. Покажем, что матрица A, задаваемая формулой (2.49), является решением системы (2.47)-(2.48). Действительно, в силу (2.24) и (2.49) 2. Покажем справедливость формулы (2.50). Действительно, в силу (2.24), (2.49) и (2.41) (лемма 2.1.5) 3. Покажем, что для любой матрицы A Rmn, являющейся решением системы (2.47)-(2.48), выполняется условие Действительно, в силу (2.43) (лемма 2.1.7) Теперь заметим, что из (2.50) и (2.51) как раз и следует, что матрица A имеет минимальную · p - норму.

4. Единственность одноранговой матрицы A, задаваемой формулой (2.49) при 1 < p < +, следует из единственности вектора y (лемма 2.1.4).

5. Покажем, что при 1 < p < + нет матриц, построенных по формулам, отличным от формулы (2.49), являющихся решением задачи 2.2. Доказательство проведем "от противного". Пусть C = (cij ) Rmn - вторая матрица, являющаяся решением задачи 2.2. Мы считаем, что C = A. Поставим матрице A = a ij Rmn в соответствие вектор r = (r i ) Rm·n по следующему правилу:

Аналогично, матрице C поставим в соответствие вектор Очевидно, что из C = A следует r = s.

Вектору x Rn поставим в соответствие матрицу X Rmm·n В силу выполненных построений Кроме того, в силу (2.7) (2.8), Покажем, что векторы r и s не могут быть линейно зависимы. Действительно, пусть имеет место противное, а именно, пусть существует число = 0 такое, что s = r. Но тогда из условия (2.52) следует, что = 1, r = s и, в силу взаимно однозначного соответствия между r и A с одной стороны, и между s и C - другой стороны, A = C (противоречие). Но раз векторы r и s линейно независимы и выполнено условие 1 < p < +, можно использовать неравенство Минковского (см. доказательство леммы 2.1.4).

Сформируем вектор w = (wi ) = r+s Rm·n и соответствующую ему матрицу U = (uij ) Rmn по правилу wm·(i1)+j = uij, i = 1, 2,..., m, j = 1, 2,..., n.. Несложно заметить, что Но в силу выполнения неравенства Минковского как строгого неравенства, имеем где y Rn+1 - вектор, двойственный к вектору z относительно нормы (·). При этом В силу (2.61) (лемма 2.3.1) где z Rn+1 - некоторый вектор. Заметим, что в силу теоремы Вейерштрасса нижняя грань в задаче A b z inf всегда достигается, так как A b z - непрерывz)= ная действительная функция, а множество {z |(z) = 1} Rn+1 компактно, а это и есть обоснование (2.68).

Пусть H h Rm(n+1) - некоторая матрица, такая, что X(A + H, b + h) =.

Пусть где x Rn - некоторый вектор такой, что x X (A + H, b + h), t R - некоторый параметр.Тогда для любого t = 0 выполняется и, как следствие, Доказательство проведем "от противного". Пусть Тогда в силу леммы 2.3.1 существует задаваемая формулой (2.60) одноранговая матрица [H() h()] такая, что X (A + H(), b + h()) =, [H() h()], = total (A, b).

Предположим теперь, что существует некоторая матрица такая, что Пусть x X (A + H, b + h) и z(x, t) - вектор, определяемый соотношением (2.74) при условии t = 0. Тогда, по определению ·, - нормы, Но тогда в силу (2.75) (противоречие).

Предположим, что Рассмотрим вектор где x Rn - произвольный вектор, R - произвольное число. Построим матрицу H (x (, x)) h (x (, x)) по формуле (2.60) и рассмотрим функцию В силу теоремы 2.3.5 матрица H (x (, x)) h (x (, x)) является минимальным по H, - норме решением уравнения откуда, в частности, следует, что Из (2.77), (2.79) и непрерывности векторных норм (·) и (·) следует, что (, x) непрерывна при любых значениях x и.

В силу (2.68), но при этом Заметим, что несмотря на последнее соотношение, матрица H (x (0, 0)) h (x (0, 0)) существует:

где y - вектор, двойственный к вектору z относительно нормы (·). Заметим, что в силу (2.70) и (2.76) Таким образом, существуют матрицы, сколь угодно близкие по значению H, - нормы к матрице корректирующие систему (2.47), но их норма в силу условия (2.76) больше нормы H (x (0, 0)) h (x (0, 0)).

Покажем, что т.е. другими словами, что матрица H (x (0, 0)) h (x (0, 0)) уже не корректирует систему Ax = b. Действительно, в силу (2.76) и (2.80)-(2.81), Таким образом, оказалось, что несовместная система Ax = b имеет решение – вектор (противоречие).

5. Обоснование формул (2.71)-(2.73) Предположим, что total (A, b) = 0. В этом случае оказывается, что несовместная система Ax = b может быть скорректирована с помощью некоторой матрицы, имеющей нулевую ·, - норму. Но тогда, в силу аксиомы невырожденности матричной нормы, сама матрица коррекции является нулевой, что противоречит несовместности системы Ax = b.

Убедимся в справедливости формулы (2.73). В силу левой части (2.72) и левой части (2.73) имеем:

Теперь заметим, что правая часть формулы (2.72) справедлива в силу условия а также условия справедливого в силу (2.68)-(2.69) и леммы 2.3.1.

Замечание 2.3.1. Примером векторной нормы, для которой условие (2.70) может не выполняться, является · -норма. Для того, чтобы в этом убедиться, достаточно проанализировать формулу (2.40). Таким образом, при использовании нормы в задаче total (A, b), условие (2.69) в общем случае не является необходимым условием существования решения.

Теорема 2.3.6. Если несовместная система вида (2.47) такова, что rank A < n, то задача total (A, b) не имеет решения.

Доказательство. Покажем сначала, что из условия rank A < n не может следовать условие total (A, b) > 0.

Предположим противное, а именно: пусть total (A, b) > 0, но rank A < n. Из последнего условия следует, что система Ax = 0 имеет нетривиальные решения. Пусть x - такое решение, а именно, пусть Ax = 0, 0 < (x) < +. Положим Тогда в силу теоремы 3.3. (противоречие).

Таким образом, если rank A < n, то total (A, b) = 0 Но, как было показано при доказательстве теоремы 2.3.5, условие total (A, b) = 0 несовместно с утверждением о том, что задача total (A, b) имеет решение.

Теорема 2.3.7. Если задача total (A, b) имеет решение, то для любой матрицы H h такой, что X (A + H, b + h) =, rank [H, h] = 1, множество X (A + H, b + h) состоит только из одного элемента.

Доказательство. Пусть задача total (A, b) имеет решение. Тогда в силу теоремы 2.3.1 выполняется условие total (A, b) > 0. Пусть [H, h] Rm(n+1) и x Rn - такие матрица и вектор, что выполняются условия rank [H, h] = В силу последнего предположения Допустим теперь, что существует вектор x = 0, x Rn такой, что Из (2.83) и (2.84) следует, что Для дальнейших выкладок придется конкретизировать вид можно записать H = cd, h = c, где c Rm, d Rn T некоторые векторы, R - некоторое число. Условие (2.83) позволяет однозначно определить вектор c:

откуда Теперь рассмотрим два случая:

1. dT x = 0. Тогда из условий (2.85) и (2.86) получаем т.е. вектор является решением несовместной системы (2.47) (противоречие).

2. dT x = 0 Hx = 0. Таким образом, условие (2.85) влечет выполнение условия Заметим, что из условия (2.85) следует, что (x µ · x) X (A + H, b + h) для произвольного числа µ R. Рассмотрим теперь вектор и займемся исследованием величины В силу (2.87) и (1.3), (2.4) и (1.6), Но из последнего соотношения следует, что что в силу теоремы 2.3.5 противоречит допущению о существовании решения задачи total (A, b).

Теорема 2.3.8.

где x Rn. Достижимость inf (bAx) является необходиx) мым и достаточным условием существования решения задачи f ix{b} (A, b).

Если решение задачи f ix{b} (A, b) существует, то где y Rn - вектор, двойственный к вектору x относительно нормы (·).

Перед доказательством теоремы 2.3.8 докажем вспомогательную лемму.

Лемма 2.3.9. Пусть выполняются условия где H Rmn - некоторая матрица, вид и способы построения которой не конкретизируются.

Тогда Доказательство. Предположим противное, а именно: пусть 0 X (A + H, b). Тогда (A + H) · 0 b b = 0 X (A, b) X (A, b) = (противоречие).

Доказательство теоремы 2.3.8.

1. Обоснование формулы (2.88) Формула (2.88) следует из (2.63) (лемма 3.3.2).

достигается, т.е.

Заметим, что несовместность системы (2.47) в сочетании со сделанным предположением позволяют заключить, что x = 0. Тогда в силу леммы 2.3.2 существует одноранговая матрица H (x ) такая, что Предположим теперь, что существует такая матрица H, что Рассмотрим теперь функцию f (x) = (x). Поскольку в силу леммы 2.3.9 0 X A + H, b функция f (x) определена для откуда получаем, что существует вектор x X (A + H, b), x = 0 такой, что Теперь заметим, что для произвольной матрицы H такой, что X (A + H, b) =, справедливо условие Объединяя (2.93)-(2.96), получаем (противоречие).

Доказательство проведем "от противного". Пусть задача f ix{b} (A, b) имеет решение, т.е. существует матрица т.е.

Используя (2.96), (2.98), определение · -нормы и формулу (2.88), получаем, что (противоречие).

4. Обоснование формул (2.89)-(2.91) Предположим, что f ix{b} (A, b) = 0. В этом случае оказывается, что несовместная система (1.1.1) может быть скорректирована с помощью некоторой матрицы, имеющей нулевую ·, -норму. Но тогда, в силу (3.1.1b), сама матрица коррекции является нулевой, что противоречит несовместности системы (2.47). Убедимся в справедливости формулы (2.91).

В силу левой части (2.90) имеем:

Теперь заметим, что правая часть формулы (2.90) справедлива в силу условия а также условия справедливого в силу (2.88), (2.92), левой части (2.90) и леммы 2.3.2.

Теорема 2.3.10. Если несовместная система вида (2.47) такова, что rank A < n, то задача f ix{b} (A, b) не имеет решения.

Доказательство. Покажем сначала, что из условия rank A < n не может следовать условие f ix{b} (A, b) > 0.

Предположим противное, а именно: пусть f ix{b} (A, b) > 0, но rank A < n. Из последнего условия следует, что система Ax = 0 имеет нетривиальные решения. Пусть x - такое решение, а именно, пусть Ax = 0, 0 < (x) < +. В силу теоремы 2.3.8, (противоречие).

Таким образом, если rank A < n, то f ix{b} (A, b) = 0 Но, как было показано при доказательстве теоремы 2.3.8, условие f ix{b} (A, b) = 0 несовместно с утверждением о том, что задача f ix{b} (A, b) имеет решение.

Теорема 2.3.11. Если задача f ix{b} (A, b) имеет решение, то для любой матрицы H такой, что X (A + H, b) =, rank H = 1, множество X (A + H, b) состоит только из одного элемента.

Доказательство. Пусть задача f ix{b} (A, b) имеет решение. Тогда в силу теоремы 2.3.8 выполняется условие f ix{b} (A, b) > 0. Пусть H Rmn и x Rn - такие матрица и вектор, что выполняются условия rank H = 1, X (A + H, b) = В силу последнего предположения Допустим теперь, что существует вектор x = 0, x Rn такой, что Из (2.99) и (2.100) следует уже имевшее место при доказательстве теоремы 2.3.7 условие (2.85).

Для дальнейших выкладок придется конкретизировать вид матрицы H. В силу условия rank H = 1 можно записать H = cdT, где c Rm, d Rn - некоторые векторы. Условие (2.99) позволяет однозначно определить вектор c:

откуда Теперь рассмотрим два случая:

1) dT x = 0. Тогда из условий (2.85) и (2.101) получаем т.е. вектор является решением несовместной системы (2.47) (противоречие).

2) dT x = 0 Hx = 0. Таким образом, условие (2.85) влечет уже имевшее место при доказательстве теоремы 2.3.7 условие (2.87).

Заметим, что из условия (2.85) следует, что (x µ · x) X (A + H, b) для произвольного числа µ R. Рассмотрим теперь вектор z(µ) = xµ · x Rn и займемся исследованием величины В силу (2.87) и (2.3), (2.4) и (2.6) Но из последнего соотношения следует, что что в силу теоремы 2.3.8 противоречит допущению о существовании решения задачи f ix{b} (A, b).

2.4 Методы матричной коррекции несовместных СЛАУ с условием неотрицательности по называть величины где L Rmm, R Rnn - некоторые невырожденные матрицы.

В обширном семействе аддитивных матричных норм · LR, · LR, · LR и · LR -нормы занимают особое положение.

Например, соответствующие векторные нормы · 1 и ·, с использованием которых они построены, часто используются при решении прикладных задач. Так · -норма и ее "взвешенные" варианты используются в задачах, требующих "гарантированного результата" (см., например, [24]).

Другая область применения у · 1 - нормы и ее "взвешенных" модификаций. Это, например, задачи оценивания неизвестных параметров по экспериментальным данным, содержащим случайные выбросы [24].

Другая сторона · и · 1 -норм и их "взвешенных" вариантов – полиэдральность [33]. Как известно, задачи, требующие минимизации · и · 1 -норм, могут быть сведены к задачам линейного программирования [25]. А.А. Ватолиным было показано, что задачи матричной коррекции несобственных задач ЛП, а также несовместных систем линейных алгебраических уравнений и неравенств с показателями качества коррекции в виде · LR и · LR -норм, могут быть сведены к конечному набору задач линейного программирования [26, 27]. А.А. Гореликом и Р.Р. Ибатуллиным было показано, что задачи коррекции несовместных систем линейных алгебраических уравнений с условием неотрицательности по минимуму · -нормы, а также несобственные задачи линейного программирования с указанным показателем качества коррекции, могут быть сведены к задаче ЛП [3, 11].

Мы рассмотрим все задачи матричной коррекции несовместных систем линейных алгебраических уравнений с условием неотрицательности, в которых корректируется расширенная матрица коэффициентов минимуму · LR, · LR, · LR 1, и · LR -норм, и все аналогичные задачи, в которых корректируется только левая часть исследуемой системы – ее матрица коэффициентов.

Ниже будет показано, что каждая задача матричной коррекции по минимуму · LR или · LR - нормы требует решения одной задачи ЛП, а каждая задача матричной коррекции по минимуму · LR или · LR - нормы требует решить n или n + 1 задач ЛП.

Матричная коррекция по минимуму · LR и · LR - норм несовместных СЛАУ с условием rank(R) = n, R, R1 0. Заметим, что последнее условие заметно сужает класс возможных матриц R, но все же он не является пустым. Например, в него входят диагональные матрицы с положительными диагональными элементами, а также матрицы, полученные из указанных диагональных матриц перестановками строк или столбцов. Пусть Несложно заметить, что с учетом принятых допущений где 1 - вектор соответствующей размерности, все компоненты которого - единицы.

Рассмотрим следующие задачи:

Дополнительно оговорим, что во всех четырех задачах L Rmn, rank(L) = m, R, R1 0. В задачах (2.104), (2.105) z Rn+1, R R(n+1)(n+1), rank(R) = n+1. В задачах (2.106), (2.107) x Rn, R Rnn, rank(R) = n.

Предположим, что решения задач (2.104))-(2.107) существуют. Пусть z Rn+1 - решение задачи (2.104) или (2.105), x Rn - решение задачи (2.106) или (2.107). Тогда, в силу теорем 2.3.5 и 2.3.8, и в силу замечания 2.2.1 существуют решения следующих задач матричной коррекции:

Решив задачи (2.104)-(2.107), можно построить решения задач (2.108)-(2.111). Каким же образом могут быть решены задачи (2.104)-(2.107)? Ответ содержится в приводимых ниже леммах 2.4.1-2.4.4, формулировки которых получены с использованием условий 2.4.1-2.4.2 и стандартных способов сведения минимизации · 1 и · - норм к задачам ЛП.

Лемма 2.4.1. Решение задачи (2.104) может быть получено из решения задачи ЛП следующего вида:

где R, u Rn+1, qi - строка с номером i матрицы L[A b]R.

Доказательство. Пусть, u Rn+1, qi - решение задачи (2.112), причем такое, что, где. Если указанное решение задачи (2.112) существует, то задача (2.108) разрешима, и, в частности, имеет следующее решение:

где y Rn+1 - вектор, двойственный к вектору z относительно нормы R1 z 1, Лемма 2.4.2. Решение задачи (2.105) может быть получено из решения задачи ЛП следующего вида:

где d Rm, u Rn+1, qi - строка с номером i матрицы L[A b]R.

Доказательство. Пусть d, u - решение задачи (2.113), причем такое, что zn+1 > 0, где z = Ru. Если указанное решение задачи (2.113) существует, то задача (2.109) разрешима, и, в частности, имеет следующее решение:

где y Rn+1 - вектор, двойственный к вектору z относительно нормы R1 z 1, Лемма 2.4.3. Решение задачи (2.106)) может быть получено из решения задачи ЛП следующего вида:

где, Rn, qi - строка с номером i матрицы LAR, i компонента с номером i вектора Lb.

Доказательство. Пусть, u, - решение задачи (2.114), причем такое, что > 0. Если указанное решение задачи (2.114) существует, то задача (2.110)) имеет решение, которое, в частности, может быть построено по следующим формулам:

где y Rn - вектор, двойственный к вектору x относительно Лемма 2.4.4. Решение задачи (2.107) может быть получено из решения задачи ЛП следующего вида:

где d Rm, u Rn+1, qi - строка с номером i матрицы L[A b]R.

Доказательство. Пусть d, u, - решение задачи (2.115), причем такое, что > 0, где z = Ru. Если указанное решение задачи (2.115) существует, то задача (2.111) имеет решение, которое, в частности, может быть построено по следующим формулам:

где y Rn - вектор, двойственный к вектору x относительно нормы R1 x 1. При этом LH R 1,1 = 1T d.

Матричная коррекция по минимуму · LR и · LR - норм несовместных СЛАУ с условием rank(R) = n, R, R1 0. Пусть также выполняется условие (2.102). Несложно заметить, что с учетом принятых допущений Рассмотрим следующие задачи:

Так же, как и в предыдущем параграфе, во всех четырех задачах L Rmm, rank(L) = m, R, R1 = 0. В задачах (2.117), (2.118) z Rn+1, R R(n+1)(n+1), rank(R) = n + 1. В задачах (2.119), (2.120) x Rn, R Rnn, rank(R) = n. Предположим, что решения задач (2.117)-(2.120) существуют. Пусть z Rn+1 - решение задачи (2.117) или (2.118), x Rn - решение задачи (2.119) или (2.120). Тогда, в силу теорем 2.3. и 2.3.8, и в силу замечания 2.2.1 существуют решения следующих задач матричной коррекции:

Решив задачи (2.117)-(2.120), можно построить решения задач (2.121)-(2.124). Схема решения упомянутых задач содержится в приводимых ниже леммах 2.4.5-2.4.8, формулировки которых получены с использованием условий (2.102), (2.116) Лемма 2.4.5. Решение задачи (2.117) может быть получено из решения совокупности задач ЛП следующего вида:

где d Rm, u Rn+1 - строка с номером i матрицы L[A b]R.

d, u - решение задачи (2.125) с номером k, z = Ru. Если существуют такие k, d и u, что zn+1, то задача (2.121) имеет решение, которое, в частности, может быть построено как где y Rn+1 - вектор, двойственный к вектору z относительно нормы R1 z, Лемма 2.4.6. Решение задачи (2.118) может быть получено из решения совокупности задач ЛП следующего вида:

где Rm, u Rn+1, qi - строка с номером i матрицы L[A b]R.

, u - решение задачи (2.126) с номером z = Ru. Если существуют такие k, d и u, что zn+1, то задача (2.122) имеет решение, которое, в частности, может быть построено как где y Rn+1 - вектор, двойственный к вектору z относительно нормы R1 z, Лемма 2.4.7. Решение задачи (2.119) может быть получено из решения совокупности задач ЛП следующего вида:

где d Rm, u Rn, R, qi - строка с номером i матрицы LAR, i компонента с номером i вектора Lb.

Доказательство. Пусть k k = = min {k }, d,, u - решение задачи (2.127) с номером k. Если существуют такие k, d, u и, что > 0, то задача (2.123) имеет решение, которое, в частности, может быть построено как где y Rn - вектор, двойственный к вектору x относительно нормы R1 x, Лемма 2.4.8. Решение задачи (2.120) может быть получено из решения совокупности задач ЛП следующего вида:

где R, u Rn, qi - строка с номером i матрицы LAR, i компонента с номером i вектора Lb.

, u - решение задачи (2.128) с номером k. Если существуют такие k, d, u и, что > 0, то задача (2.124) имеет решение, которое, в частности, может быть построено как где y Rn - вектор, двойственный к вектору x относительно нормы R1 x, Рассмотрим задачу со следующими данными:

Вспомогательная задача (2.112) принимает вид:

Расширенная матрица коррекции [H h ] и вектор x имеют вид:

0.000000 0.000000 1.142857 0.000000 0.571428 0. 0.000000 0.000000 0.571428 0.000000 0.285714 0. 0.000000 0.000000 0.571428 0.000000 0.285714 0. 0.000000 0.000000 1.142857 0.000000 0.571428 0. Проверки, показывающие, что задача решена правильно:

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

Указанные нормы можно также назвать векторными нормами на множестве матриц.

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

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

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

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

Проблема коррекции всех коэффициентов (матричная коррекция) несовместных систем линейных алгебраических уравнений и связанные с ней задачи - обобщенный метод наименьших квадратов, несобственные задачи линейного программирования - широко исследовались в последние годы в различных постановках (см., например, [27],[28],[17],[11]) и, в том числе, с учетом фиксации (освобождения от коррекции) различных комбинаций строк и столбцов матриц (расширенных матриц) коэффициентов исследуемых линейных систем [1]. Однако все ранее известные результаты неприменимы к СЛАУ с блочной структурой.

3.1 Постановки задач блочной коррекции Пусть дана несовместная система линейных алгебраических уравнений которая, возможно, дополняется условием неотрицательности решения где x RN, b RM, A RM N, причем матрица имеет следующую блочную структуру:

nk = N. Для последующих выкладок окажется полезM, ным ввести в соответствии с (3.3) блочные представления для векторов x и b:

где xk Rnk, k = 1, 2,..., K, bk Rmk, k = 0, 1,..., K. Подсистему будем полагать совместной, т.е. X (A0, b0 ) =, где здесь и везде далее X (A, b ) = {x Rn | A x b } - множество решений СЛАУ с матрицей A и вектором правой части b.

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

Задача 3.1.

Задача 3.2.

Задача 3.3.

Задача 3.4.

В задачах 3.1, 3.3 требуется найти минимальные матрицы коррекции Hi, i = 1,..., K, а в задачах 3.2, 3.4 минимальные рассширенные матрицы коррекции Hi hi, i = 1,..., K, где при i = 1,..., K Li Rni mi, Ri R(ni ni ) или Ri R(ni +1)(ni +1) - невырожденные матрицы, символом · E обозначена евклидова матричная норма. hk - элемент матij рицы коррекции [Hk ], hk - элемент расширенной матрицы коррекции Hk hk.

Структура корректируемых матриц в системах (3.5),(3.6) может быть интерпретирована следующим образом. Имеется система, состоящая из K подсистем (например, корпорация из K предприятий). Система в целом должна удовлетворять некоторым условиям устойчивости (гомеостаза) или координации функционирования подсистем. Эти условия связывают все переменные, записываются в виде (3.4) и не могут быть подвергнуты коррекции, т.е. являются жесткими.

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

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

Задачи блочной коррекции 3.1-3.4 можно рассматривать как обобщения на случай линейных систем с блочной структурой задач многопараметрической (матричной) коррекции несовместных систем линейных алгебраических уравнений и несобственных задач линейного программирования общего вида по минимуму евклидовой нормы, исследованных в работах [27],[28],[1],[17],[11], так как они характеризуются дополнительными ограничениями на матрицу коррекции. Блочные матрицы могут также быть представленны в параметрическом виде A(), т.е. представляют собой класс задач с параметризованной структурой, однако в данной главе такая параметризация в явном виде не используется. В четвертой главе рассматривается другой класс такого типа задач и там, в алгоритмах решения задач, вид параметризации используется явно.

3.2 Решение задач блочной коррекции с 3.2.1 Редукция квадратичных критериев к задачам Заметим, что подсистема (3.4) в соответствии со структурой вида (3.3) матрицы A является недоопределенной системой линейных алгебраических уравнений и в общем случае имеет бесконечное множество решений X(A0, b0 ). Для последующих выкладок окажется полезной следующая параметризация X(A0, b0 ) (см., например, [15]):

где I - единичная матрица порядка N, A+ RN m0 - матрица, псевдообратная (обобщенная обратная по Муру - Пенроузу [22]) к матрице A и x RN - произвольный вектор. Заметим, что любой вектор x, построенный по формуле (3.7), является решением подсистемы (3.4), и наоборот, для любого решения подсистемы (3.4) справедливо представление (3.7).

Запишем также блочные представления матриц A0, P и векторов x и x, естественным образом связанные с представлением (3.3):

i = 1,..., K.

Рассмотрим коррекцию подсистемы с номером 1 i K системы (3.1). В рамках задачи 3.1 систему (3.5) можно переписать как совокупность K систем линейных алгебраических уравнений с неизвестной матрицей Hi :

Поскольку в силу сделанных выше предположений матрицы Li и Ri являются квадратными и невырожденными, эквивалентные преобразования системы (3.11) можно продолжить следующим образом:

Согласно лемме А.Н. Тихонова [31] решение уравнения (3.12) относительно неизвестной матрицы Li Hi Ri, обладающее минимальной евклидовой нормой, существует при любом xi = 0, единственно и задается формулой причем где символом · обозначена евклидова векторная норма. Из формул (3.13)-(3.14) в свою очередь следует, что единственным решением уравнения (3.11) относительно неизвестной матрицы Hi, обладающим минимальной взвешенной евклидовой нормой при некотором xi = 0 будет матрица для взвешенной евклидовой нормы которой будет справедлива формула (3.14). Таким образом, задачу 3.1 можно свести к задаче Выполнив некоторые преобразования формулы (3.14) с использованием формул (3.7)-(3.8) и представлений (3.10), получим где Но тогда задача (3.16) может быть представлена в виде Заметим, что задача (3.22), конечно, не является в строгом смысле задачей безусловной минимизации в силу условий вида Тем не менее можно показать, что любой численный метод минимизации, снабженный дополнительными проверками во вспомогательных процедурах типа одномерного поиска и гарантирующий убывание f (x) на каждой итерации, не приведет к точкам разрыва f (x) при условии, что стартовая точка f (x) будет допустимой. Но это означает, что в процессе минимизации f (x) может рассматриваться как непрерывная функция, а сама задача минимизации может считаться безусловной.

Итак, задача 3.1 сведена к задаче (3.22). Предположим, что x RN - точка минимума задачи (3.22). Тогда, вычислив, в соответствии с (3.7), вектор x RN по формуле можно в соответствии с (3.15) построить оптимальные в контексте задачи 3.1 матрицы коррекции Hi, где i = 1,..., K, по формуле При этом, в силу приведенных выше выкладок т.е. вектор x принадлежит множеству решений скорректированной системы вида (3.5).

Обратимся к исследованию задачи 3.2. В рамках задачи 3.2 систему (3.6) можно переписать как совокупность систем линейных алгебраических уравнений с неизвестной матрицей [Hi hi ]:

Поскольку в силу сделанных выше предположений матрицы Li и Ri являются квадратными и невырожденными, эквивалентные преобразования системы (3.11) можно продолжить следующим образом:

Согласно лемме А.Н. Тихонова [31] решение уравнения (3.25) относительно неизвестной матрицы, обладающее минимальной евклидовой нормой, существует при любом векторе xi, единственно, и задается формулой причем Из формул (3.26)-(3.27) в свою очередь следует, что единственным решением уравнения (3.11) относительно неизвестной матрицы [Hi hi ], обладающим минимальной взвешенной евклидовой нормой при некотором xi будет матрица для взвешенной евклидовой нормы которой будет справедлива формула (3.27). Таким образом, задачу 3.2 можно свести к задаче Выполнив некоторые преобразования формулы (3.27) с использованием формул (3.7)-(3.8) и представлений (3.10), получим где при i = 1,..., K, для i и Ai справедливы формулы (3.18) и (3.19) соответственно, Но тогда задача (3.34) может быть представлена в виде Заметим, что задача (3.34) очень похожа на задачу (3.22).

Так, целевые функции обеих задач имеют один и тот же вид. Отличие заключается в том, что задача (3.34) в строгом смысле является задачей безусловной минимизации. Приведем обоснование этого утверждения: в силу (3.7)-(3.10) и (3.31)-(3.33) Но в силу невырожденности матриц Ri левая часть тождества (3.35) отлична от нуля при любых значениях xi. Следовательно, правая часть тождества (3.35) отлична от нуля при любых значениях xi, откуда, в свою очередь, следует непрерывность функции f (x) на RN.

Итак, задача 3.2 сведена к задаче (3.34). Предположим, что x RN - точка минимума задачи (3.34). Тогда, вычислив, в соответствии с (3.7), x RN по формуле можно, в соответствии с (3.28), построить оптимальные в контексте задачи 3.2 матрицы коррекции [Hi h ], где i = 1,..., K, по формуле При этом в силу приведенных выше выкладок, т.е. x принадлежит множеству решений скорректированной системы вида (3.6).

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

Теорема 3.2.1. Если rank A < N, то минимум в задачах 3.1 и 3.2 не достигается.

Доказательство. Пусть rank A < N. Следовательно, В то же время пусть инфинум в задаче 3.1 или 3.2 достигается. Тогда в силу приведенных выше выкладок инфинум достигается и в задаче (3.22) или (3.34). Пусть x RN - некоторая точка минимума задачи (3.22). Заметим, что f (x ) > 0, так как при f (x ) = 0 оказывается, что все матрицы коррекции Hi имеют нулевую евклидову норму, а значит, в силу аксиомы невырожденности сами являются нулевыми, что противоречит предположению о несовместности системы (3.1). В то же время, используя (3.9), (3.10), (3.19)-(3.22) и (3.37), можно показать, что где x RN - произвольный вектор, не являющийся точкой разрыва функции f (x). Действительно, и поэтому Теперь заметим, что в силу невырожденности матриц Ri и условия z = Учитывая (3.39), (3.40) и неотрицательность функции f (y), получаем соотношение (3.38). Аналогичным образом, предполагая, что y RN - некоторая точка минимума задачи (3.34), с одной стороны, имеем f (y ) > 0, а с другой стороны, используя (3.9), (3.10), (3.19), (3.31)-(3.34) и (3.37), убеждаемся в том, что где y RN - произвольный вектор. Действительно, Но подматрица Ri R(ni +1)ni матрицы Ri R(ni +1)(ni +1) имеет полный столбцевой ранг (в противном случае матрица Ri не существовала бы). Учитывая это условие, а также условие z = 0, заключаем, что Учитывая (3.42), (3.43) и неотрицательность функции (x), получаем соотношение (3.41). Но условие f (x ) > 0 противоречит (3.38), а условие f(x ) > 0 противоречит (3.41).

В то же время пусть минимум в задаче 3.1 или 3.2 достигается. Тогда в силу приведенных выше выкладок минимум достигается и в задаче (3.22) или (3.34). Пусть x RN - некоторая точка минимума задачи (3.22). Используя (3.9), (3.10), (3.19)-(3.22) и (3.36), можно показать, что Аналогичным образом, предполагая, что x RN - некоторая точка минимума задачи (3.34) и используя (3.9), (3.10), (3.19), (3.20), (3.31)-(3.34) и (3.36), можно показать, что т.е. в обоих случаях получаем противоречие.

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

В силу (3.34) Трудоемкость построения формулы для i (x) сравнительно невелика. Несколько больше технически выкладок приходится проделать при выводе формулы для 2 i (x), однако принципиальных математических сложностей в обоих случаях нет. Применяя стандартные правила дифференцирования векторно-матричных выражений, получаем где Перейдем к дифференцированию функции f (x). Как уже отмечалось выше, указанная функция определена на всем множестве RN. Соответственно существуют и ее частные производные требуемого порядка. В силу аналогии между формулами (3.34) и (3.35), существуют соответствующие аналогии и в формулах для вычисления градиента и матрицы Гессе функций f (x) и f (x). Так, для f(x), 2 f (x), i (x) и i (x) справедливы формулы (3.44)-(3.68), в которых по-прежнему можно использовать объекты, определенные формулами (3.50)-(3.53), а вместо pi (x), Gi, gi и si (x) следует использовать Полученные формулы для градиента и матрицы Гессе были использованы при проведении вычислительных экспериментов с использованием метода Ньютона.

Следует заметить что задачи 3.1-3.2 при наличии ограничения на вектор решения x эквивалентны задаче условной минимизации квадратичной функции, ограничение положительности решения с учетом введенных обозначений имеет 3.3.1 Вычислительные эксперименты В настоящем разделе представленные выше теоретические результаты иллюстрируются вычислительным примером, характеризующим сходимость по аргументу и по целевой функции алгоритмов решения вспомогательных задач (3.22), (3.34).

Было рассмотрено некоторое количество модельных несовместных систем малой размерности с блочной структурой.

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

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

Результаты расчетов представлены в приведенных ниже табл. 3.1 - 3.2.

Таблица 3.1. Результаты решения задачи (3.1) Таблица 3.2. Результаты решения задачи (3.2) Результаты решения задач 3.1-3.2 для того же примера с дополнительным условием (3.2) представлены в табл. 3. - 3.4. В первом столбце указанных таблиц приведен вектор x, являющийся решением соответствующей вспомогательной задачи - (3.22),(3.34). При численной реализации решения задач 3.1-3.2 был дополнительно рассмотрен случай наличия ограничений на вектор x. В качестве ограничения рассмотренно наиболее распространенное ограничение неотрицательности решения x 0.

Решение задач 3.1-3.2 производились с помощью процедуры fmincon оптимизационного пакета системы Matlab.

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

В соответствии с (3.7), указанная система для обеспечения условия (3.2) x 0 имела вид Таблица 3.3. Результаты решения задачи 3.1 при ограничении Очевидно, что условие (3.2) приводит к существенному изменению матриц коррекции и вектора решения скорректированных систем.

Таблица 3.4. Результаты решения задачи 3.2 при ограничении 0.00000000 0.95301576 0.15622483 0. Приведем теперь результаты исследования сходимости по аргументу и по целевой функции численных алгоритмов решения вспомогательных задач (3.22),(3.34). При решении задач (3.22) и (3.34) без ограничений методом Ньютона (при удачном выборе начального приближения) в обоих случаях наблюдалась квадратичная сходимость, что иллюстрирует приводимый ниже рис. 3.1. Представленные на них данные получены в ходе решения задач 3.1 и 3.2 для рассматриваемой в настоящем разделе несовместной системы.

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

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

Рис. 3.1. Сходимость по аргументу и по целевой функции для задачи (3.22) без ограничений и для задачи (3.34) без ограничений 3.4 Решение задач блочной коррекции с 3.4.1 Редукция задач минимаксной коррекции к Теорема 3.4.1. Задачи 3.3 - 3.4 эквивалентны задаче оптимизации дробной функции, сводящейся при x 0 к последовательности решений серии задач ЛП.

Доказательство. Рассмотрим коррекцию подсистемы с номером 1 k K системы (3.3). Cистему (3.5) можно переписать как совокупность k систем линейных алгебраических уравнений с неизвестной матрицей Hk :

Решение уравнения (3.54) относительно неизвестной матрицы Hk, обладающее минимальной нормой существует при любом xk = 0 и задается формулой где yk – вектор, двойственный к вектору xk относительно нормы · 1. Для величины Hk 1, будет справедлива формула Пусть k = bk Ak xk, Ak = Ak Pk. Тогда, выполнив некоb торые преобразования формул (3.55)–(3.56), получим Полученная задача оптимизации дробной функции (3.57) эквивалентна исходной. В общем виде она также сложна в вычислительном плане, однако при x 0 ее можно существенно упростить. Если обозначить компоненты векторов bk Ak xk через (bk Ak xk )i, то формулу (3.57) с учетом неотрицательности xk можно переписать в виде где 1nk – вектор - столбец размерности nk, состоящий из единиц, T - знак транспонирования, здесь и далее i = 1, 2... mk.

Таким образом, очевидно, что задача 3.3 минимизации равносильна следующей задаче:

Пусть Тогда задача (3.58) сводится к задаче:

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

при ограничениях где c = [0, 0,... 0]N, u - текущее (фиксированное) значение целевой функции исходной задачи.

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

Если учесть, что для расширенной матрицы справедливо:

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

Пусть в отличие от (3.59) С учетом (3.63) задача (3.62) сводится к задаче вида (3.60), а затем к последовательности задач ЛП вида (3.61) (отличие в дополнительном слагаемом).

Таким образом, доказательство теоремы закончено.

Замечание. После того как найден вектор x – решение задачи (3.60), необходимо восстановить искомое решение x = x + P x, после чего можно сформировать матрицы коррекции Hk по формуле (3.55).

При этом вектора невязки rk = (Ak + Hk )xk bk скорректированных подсистем и невязка нулевой подсистемы r0 = (A0 + H0 )x b0 теоретически будут равны нулевому вектору.

3.5 Условия неразрешимости задач с Изложенные в настоящем разделе методы минимаксной матричной коррекции несовместных систем линейных алгебраических уравнений с блочными матрицами коэффициентов имеют границы применимости. Этот факт выглядит достаточно естественно, если учесть, что подобные границы применимости ранее были установлены для задач оптимальной матричной коррекции блочных систем с критериями качества коррекции, построенными с использованием евклидовой нормы. Также хорошо известно (см., например, [1]), что неразрешимыми могут быть и обычные (не блочные) задачи матричной коррекции несовместных систем линейных алгебраических уравнений.

Теорема 3.5.1. Задачи 3.3 и 3.4 не имеют решения, если существует вектор z RN, z 0, такой что выполняется условие Доказательство. Поскольку задачи 3.3 и 3.4 очень близки по своим постановкам и методам решения, рассмотрим только одну из них - задачу 3.3. Предположим противное, а именно: пусть вектор z с указанными выше свойствами существует, но задача 3.3 имеет решение - набор оптимальных матриц коррекции H1, H2,..., HK, построенных по формуле (3.55) с использованием вектора где x получен в результате решения задачи (3.59). В соответствии с приведенными выкладками где u - оптимальное значение целевой функции в задаче (3.60).

По аналогии с (3.10) введем в рассмотрение блочные представления векторов x и z :

где x, z Rnk, k = 1, 2,..., K. С учетом блочного представления z можно, в частности, переписать условие (3.65) в виде Введем также в рассмотрение вектор w = x + z, где скалярный параметр, и с его использованием построим по формуле (3.55) альтернативные матрицы коррекции Теперь заметим, что поскольку x 0 и zk 0, то для любого > 0 справедливо неравенство x 1 < x + zk 1, в силу которого из (3.66) и (3.68) следует, что 3.5.1 Вычислительные эксперименты Численное решение задач 3.3,3.4 также производилось в системе Matlab. При этом использовалась стандартная функция linprog, реализующая поиск решения задачи линейного программирования.

Результаты расчетов представлены в приведенных ниже табл. 3.5 - 3.6. Первый столбец указанных таблиц содержит дополнительную информацию - в нем приведен вектор x, приведены также вектора невязок rk. В качестве критерия остановки процедуры одномерной минимизации был использован критерий: while u = |ui ui1 |, = 1010.

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

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

A построена с помощью следующего преобразования Ak = Ak nk I 1nk 1Tk, где Ak - соответствующие блоки матрицы рассмотренной в разд. 3.3.1.

Результат применения предлагаемого метода коррекции для системы Ax = b представлен в табл. 3.7 и на рис.3.4 - 3.5.

Характерной особенностью итерационного процесса является lg| x x*| Рис. 3.2. Иллюстрация cходимости по аргументу для задачи 3. и для задачи 3.4 для системы из разд. 3.3. lg|uu*| Рис. 3.3. Иллюстрация сходимости по целевой функции для задачи 3.3 и для задачи 3.4 для системы из разд. 3.3. Рассмотренный класс задач решения несовместных СЛАУ, обладающих блочной структурой, является интересным в том плане, что структура системы определена не физическим процессом, а постановкой задачи экономической оптимизации системы, где каждый блок представляет собой отдельную подсистему. Блочная структура в этом случае является отlg| x x*| Рис. 3.4. Иллюстрация cходимости по аргументу для задачи 3. и сходимости по целевой функции, неразрешимая задача из разд.

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

Представленый метод решения СЛАУ с блочной структурой позволяет получать матрицу коррекции системы аналогичной блочной структуры. В том случае, если априорно известно, что ошибкам подвержена и правая часть системы, данный метод позволяет получить минимальную по норме Рис. 3.5. Изменение значения целевой функции 3.3 и изменение значения x, неразрешимая задача из разд. 3. расширенную матрицу коррекции.

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

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

Таблица 3.7. Результаты решения задачи 3.3, неразрешимая задача из разд. 3. Глава Коррекция несовместных систем с матрицами Теплица Данная глава посвящена оптимальной матричной коррекции несовместных однородных и неоднородных линейных систем специального вида с матрицами (расширенными матрицами) Теплица или Ганкеля. Указанные линейные системы достаточно распространены. Они возникают, например, при анализе и параметрической идентификации линейных динамических систем с одним входом и одним выходом, когда соответствующие непрерывные входные и выходные сигналы заменяются дискретными наборами значений, а соответствующие системы линейных дифференциальных уравнений первого порядка, описывающие поведение исследуемых систем, превращаются в системы линейных разностных уравнений специального вида [30].

В настоящей работе матрицей Тёплица будем называть прямоугольную вещественную матрицу A следующего вида:

Обозначим символом Tm,n множество всех вещественных матриц размера m n, имеющих тёплицеву структуру в соответствии с определением (4.1). Постановки основных задач настоящей главы имеет вид:

Задача 4.1. Дана несовместная система линейных алгебраических уравнений вида Ax = b, где A Tm,n, b Rm, x Rn. При этом в общем случае b = 0. Требуется найти матрицу E Tm,n и вектор Rm такие, что система (A + E )x = b + совместна и выполнено условие Задача 4.2. Дана несовместная система линейных алгебраических уравнений вида Ax = b, где A Tm,n, b Rm, x Rn. При этом в общем случае b = 0. Требуется найти матрицу E Tm,n такую, что система (A + E )x = b совместна и выполнено условие Замечание 4.0.1. В дальнейшем изложении под матрицей E также подразумевается теплицева матрица E(), где вектор - вектор, определяющий (параметризующий) матрицу E.

Понятие малости матрицы коррекции, малости нормы E заменено понятием малости нормы вектора - вектора, через который определяется матрица E. Структура матриц Теплица такая, что, зная размеры m n и вектор N 1, можно однозначно построить матрицу E().

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

4.1 Алгоритм обобщенной наименьшей нормы Настоящий раздел посвящен описанию алгоритма, известного под названием "алгоритм обобщенной наименьшей нормы" – "Total Least Norm Algorithm" (или сокращенно TLN - алгоритм) [35], доставляющего решение задаче 4.1.