ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2015, том 55, № 3, с. 372-384
удк 519.612
РАДИУСЫ СОВМЕСТНОСТИ И НЕСОВМЕСТНОСТИ СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ И НЕРАВЕНСТВ1)
© 2015 г. О. В. Муравьева
(119991 Москва, ул. Малая Пироговская, 1, стр. 1, МПГУ) e-mail: muraveva@tidm.ru Поступила в редакцию 14.01.2014 г.
Во многих разделах теоретической информатики возникают задачи, которые сводятся к совместности или несовместности систем линейных уравнений и неравенств: задачи линейного программирования, задачи машинного обучения, задачи многокритериальной оптимизации и т.д. Возможны разные меры устойчивости свойства совместности и несовместности и разные информационные составляющие (все параметры, матрица коэффициентов, вектор ограничений). В настоящей статье рассматривается изменение всех параметров и важное для приложений дополнительное ограничение — неотрицательность допустимых точек. Библ. 7.
Ключевые слова: матричная коррекция, несовместные системы линейных уравнений и неравенств, устойчивость систем линейных уравнений и неравенств.
БОТ: 10.7868/80044466915030126
ВВЕДЕНИЕ
Пусть система линейных уравнений
Ах = Ь, А е х п, Ь е Кт, х е Кп,
совместна. Рассматривается задача минимального изменения параметров, при котором система становится несовместной. Параметры задачи — расширенная матрица системы ограничений [—Ь, А] (квадратными скобками обозначена матрица размерности (т + 1) х п, полученная приписыванием слева к матрице А е 1Кт х п вектор-столбца Ь е 1Кт (со знаком минус)). Будем рассматривать также систему линейных уравнений с условием неотрицательности и системы линейных неравенств.
В [1] приведены необходимые и достаточные условия устойчивости совместных систем линейных уравнений и неравенств к изменению параметров. Устойчивость определяется как свойство сохранения совместности при малых изменениях параметров, т.е. элементов расширенной матрицы [—Ь, А].
Теорема (см. [1]). Заданы матрица А е 1Кт х п и вектор Ь е 1Кт.
1. Совместная система линейных уравнений Ах = Ь устойчива тогда и только тогда, когда гапк(А) = т.
2. Совместная система линейных неравенств Ах < Ь устойчива тогда и только тогда, когда совместна система Ах < Ь.
3. Совместная система Ах < Ь, х > 0, устойчива тогда и только тогда, когда совместна система Ах < Ь, х > 0.
Для устойчивых систем найдем количественную характеристику устойчивости.
Радиусом совместности системы линейных уравнений Ах = Ь будем называть величину
Я = М{Ф(-Н, Н) : {X : (А + Н)х = Ь + Н} = 0}.
В качестве критерия величины изменения параметров будем рассматривать евклидову или спектральную норму матрицы коррекции Н = [—к, Н]:
ф(-н, Н) = ||Н1,
1) Работа выполнена в рамках государственного задания Министерства образования и науки РФ, № гос. рег. 01201153729.
IIHI = IIHI« = YYhij или H = IIHI2 = max |\He\j.
4 iNI j = 1
' ' j
Большинство приведенных результатов справедливы для каждой из двух рассматриваемых норм, в этом случае используется обозначение без индекса ||-||. Норма вектора во всех случаях евклидова ||e|| = ||е||2 = л/(e, e).
Рассмотрим устойчивость к изменению параметров свойства совместности системы линейных уравнений с условием неотрицательности решения Ax = b, x > 0 (разд. 1), совместность системы линейных неравенств Ax < b и Ax < b, x > 0 (разд. 2), а также обратные задачи устойчивости свойства несовместности систем линейных уравнений (разд. 3) и неравенств (разд. 4).
1. РАДИУСЫ СОВМЕСТНОСТИ СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ
Значение радиуса совместности системы линейных уравнений по критериям в виде евклидовой и спектральной нормы матрицы приведены, соответственно, в [2] и [3].
Теорема 2. Если {x: Ax = b} ф 0, то радиус совместности имеет вид
inf{ || [-h, H]||2 : {х : (A + H)x = b + h} = 0} = ^in(AAT),
где ^^(AA1) — минимальное собственное значение матрицы AAт.
Получим решение для задачи с условием неотрицательности. Рассмотрим совместную систему
Ax = b, x > 0, A e Rm x ", b e Rm, x e R", Теорема 3. Если {x: Ax = b, x > 0} ф 0, то радиус совместности имеет вид
inf{||[-h, H]||2 : {х : (A + H)x = b + h,x> 0} = 0} = min {^min(BBT)},
BV > 0
где B, B — подматрицы матрицы B = [—b, A], составленные из столбцов с разными номерами так, что каждый столбец входит в одну из подматриц; ^min(BB) — минимальное из собственных значении матрицы BB , для которых существует единичный собственный вектор в' такой, что B e > 0.
Лемма 1 (теорема Фаркаша). Система Ax = b, x > 0 совместна тогда и только тогда, когда несовместна система ATy > 0, (b, y) < 0.
Лемма 2 (лемма Тихонова). Система Hx = d при заданныхx e IR", x ф 0, d e IRm имеет решение с минимальной матричной нормой (евклидовой или спектральной)
h* = d-x_, ||h*|| = lid—u.
Лемма 3. При заданной матрице C e Rm x " справедливо соотношение
min ||y - Ce\\2 = min {^(CfC)},
У > 0 e : INI = 1 be' > 0
где C, C — подматрицы матрицы C, составленные из строк с разными номерами так, что каждая
строка входит в одну из подматриц; Xmin(C C) — минимальное из собственных значений матрицы C C,
для которых существует единичный собственный вектор в' такой, что C^e' > 0.
Доказательство. Минимум достигается, так как допустимое множество {y х в e Rm + " : y > 0, ||e|| = 1} замкнуто, целевая функция непрерывна, множество значений в ограничено и множество Y(M) = {y e Rm : ||y e Ce|| < M} ограничено. Найдем минимум по переменным в, y, используя функцию Лагранжа:
L( e, уД) = ||y - Ce|| 2 - МП eil2 - 1).
Условия экстремума имеют вид
е, у, Х) = 0, I = 1, ..., п,
де
Ц-(е, у, Х)> 0, I = 1, ..., т, уЩ1 (е, У, Х) = 0, I = 1, ..., т,
или, в данном случае,
СТСе - Сту - Хе = 0,
у - Се > 0,
У (У- Се)1 = 0, I = 1, ..., т.
Пусть I = {1, ..., т}, I = {/ е I: = 0} или, как видно из второго неравенства, I — это множество индексов, для которых (Се); = (с,, е) < 0 (е1 есть ¡-я строка матрицы С). При этом матрица С разбивается (по строкам) на две подматрицы: С — подматрица, состоящая из строк с номерами, принадлежащими Г, и С, состоящая из остальных строк. Согласованное обозначение для разбиения вектора у: у е К 11, у= 0, у е -11, у> 0. Из третьего условия имеем
у = Се.
Подставляя его в первое условие, получаем
СтСе - Сту - С у - Хе = 0, С Се - С1 Се - Хе = 0, (СТС - СтС) е = Хе.
Или, что то же самое,
С'Се = Хе.
т т
Действительно, элемент матрицы С С — С С, стоящий на пересечении ,-й строки иу-го столбца равен соответствующему элементу матрицы СС:
(стС - СтС), = (С) - (с, С) = (с, С) = (СтС)„,
где с', с , с — столбец, соответственно, матрицы С, С, С.
Итак, из условия минимума функции Лагранжа по вектору е следует, что е является собственным вектором некоторой подматрицы СТС, при этом выполняются условия Се < 0, Се > 0. Имеем
||у - Се||2 = ||Се||2 = (ССе, е) = (Хе, е) = Х, т.е. значение задачи равно Х.
Условие Се < 0 является условием оптимальности, и если его не проверять, то соответствующее собственное значение не будет минимальным значением функции. Условие Се > 0 обеспечивает допустимость решения.
РАДИУСЫ СОВМЕСТНОСТИ И НЕСОВМЕСТНОСТИ Лемма 4. Пусть система Cx > 0, x Ф 0, несовместна. Тогда
inf{||HI2 : {х : (C + H)x > 0, x Ф 0 }Ф0} = min (^min(CTC)},
H
C e > 0
где С, С — подматрицы матрицы С, составленные из строк с разными номерами так, что каждая строка входит в одну из подматриц; ^¡п( С С) — минимальное из собственных значений матрицы С С, для которых существует единичный собственный вектор в1 такой, что Се > 0.
Доказательство. Введем дополнительные переменные у е К™ и запишем систему (С + Н)х > 0, х Ф 0, в виде (С + Н)х — у = 0, х Ф 0, у > 0, или Нх = у — Сх, х Ф 0, у > 0. По лемме 2 имеем
min{ ||Hl : Hx = y - Cx, x Ф 0} = Ц--^.
H
Пусть e = x/||x||. Получим
inf{||HI : (C + H) x > 0, x Ф 0} = inf{||HI : Hx = y - Cx, x Ф 0, y > 0} =
H, x x, y
= inf I I y - C2x- 2 = inf ||y - Cell2.
x ^ 0, y > 0 ||x|| y > 0, e : ||e|| = 1
Из предшествующей леммы следует доказываемое утверждение.
Доказательство теоремы. При (с, х) = 0, х Ф 0, выполняется условие тД ||А|| ; (с + Н, х) > 0} = 0.
н
Если одно из неравенств в системе заменить на строгое, значение задачи не изменится: тД || 2 : {х : (С + Н)х > 0, х Ф 0 }Ф0} = тДЦН2 : {х : (С1 + )х > 0, (с2 + Н2)(х > О)}ф0},
Н Н
где с2 — одна из строк матрицы С, С1 — подматрица С, полученная вычеркиванием строки с2. Утверждение теоремы следует из леммы 1 и леммы 3 при С = Вт. Пример 1. Система линейных уравнений
(
1 0 0 1 )
( \
V x2)
( \ 0
2 )
совместна и устойчива, радиус совместности Я = 1.
Система линейных уравнений с такими же коэффициентами при условии неотрицательности
(
1 0
V 0 1 )
( \
V x2 )
( Л 0
V 2 )
, x1 > 0, x2 > 0,
совместна, но неустойчива, радиус совместности Я+ = 0. Возмущенные системы вида
(
\
1 6
V 0 1 )
( Л
V x2)
( Л 0
V 2 )
(
\
, x 1 > 0 , x 2 > 0 , и
1 0
V 0 1 )
( Л
V x2
( Л -6
V 2 )
, x1 > 0, x2 > 0,
при любом б > 0 несовместны. В обозначениях теоремы 3 первой возмущенной системе соответствуют подматрицы
( ( ( \
B = 0 , B = 0 1 , ^min (BBT) = 0, e = 1
V1) V -2 0 ) V 0 )
Коррекции правой части системы уравнений соответствуют подматрицы
B = 0 , B = 0 1 , ^min (BBB) = 0, e = 1
V -2 ) V 1 0 ) V 0 )
Пример 2. Рассмотрим систему линейных уравнений с коэффициентами
A= 1 2 1 , b = 4
V 2 1 3 ) V 5 )
Обе системы Ах = Ь и Ах = Ь, х > 0, совместны и устойчивы. Решением является, например, х = = (2, 1, 0), строки матрицы А линейно независимы, гапк(А) = 2. Радиус совместности системы без условия неотрицательности:
Я = тЩ-к, Я]||2 : {х : (А + Н)х = Ь + к} = 0} = ^т1п(АА'Т) = 1.9377. Сингулярное разложение матрицы А:
С V
A = USV =
Матрица коррекции
(
-0.5019 -0.8649 V -0.8649 05019 )
V 4.2500 0 0 Ч
H = -Ru v2
V 0 1.3920 0)
-0.5251 0.0998 -0.8452 -0.4397 -0.8821 0.1690 V -0.7286 0.4604 0.5071 )
0.1202 -1.0620 0.5543 V -0.0697 0.6163 -0.3217)
где u2(v2) — второй столбец матрицы U(V). Скорректированная матрица
A = A + H =
( 1.1202 0.9380 1.5543 ^ 1.9303 1.6163 2.6783
имеет ранг 1, система Ax = b несовместна.
Найдем радиус совместности системы с условием неотрицательности
R+ = inf{||
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.