Об обобщении характеризаций множеств решений интер- вальных линейных систем уравнений на комплексный случай

Вычислительные технологии

Том 14, № 1, 2009

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

В. С. Дронов

Алтайский государственный университет, Барнаул, Россия e-mail: planeswalker@rambler.ru

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

Ключевые слова: интервальная линейная система, множество решений, комплексный интервал, характеризация Бека, характеризация Рона.

1. Необходимые определения

Особенность методов интервального анализа в комплексном случае — наличие разнообразных определений комплексного интервала. В различных работах в качестве такого базового объекта выступают как круги на комплексной плоскости (круговые интервалы), так и прямоугольники (скажем, в [1]), либо более сложные объекты, например, круговые секторы (см., например, [2]), круговые кольца (см., в частности, [3]) и тому подобные объекты, так или иначе допускающие задание через интервальные параметры.

Под прямоугольным комплексным интервалом а + ¿5 здесь и далее будет пониматься прямоугольная область комплексной плоскости

{х = а + ¿Ь е С | а е а, Ь е 5},

где а, 5 — действительные интервалы (здесь и далее интервалы и интервальные объекты будут обозначаться жирным шрифтом).

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

Полярным комплексным интервалом (р, в) (в терминах [4]) будем называть сектор комплексной плоскости

{х е С | х = ,р е р,в е в}.

© Институт вычислительных технологий Сибирского отделения Российской академии наук, 2009.

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

Далее рассматривается система уравнений вида Ах = Ь, где А — интервальная (в любом из приведенных выше пониманий интервала) матрица размерности т х п, а Ь — интервальный вектор длины т. Как известно, для данной системы нет однозначного понятия "решения" [6]. Как и в вещественном случае, объединенным множеством решений данной системы будем называть множество

~адт(А, Ь) = {х е Сп | (ЗА е А)(ЗЬ е Ь)(Ах = Ь)},

допусковым множеством решений системы будем называть множество

(А, Ь) = {х е Сп | (УА е А)(ЗЬ е Ь)(Ах = Ь)}.

В общем случае, множеством АЕ-решений данной системы назовем

(А, Ь) = {х е Сп | (УА е Ау)(УЬ е Ь7)(ЗА е А3)(ЗЬ е Ь3)((А + А)х = (Ь + Ь))},

где Ау, А3, и Ь3 — векторы дизъюнктивных разложений А = + А3 и Ь = + Ь3, элементы которых нулевые, если неопределенность соответствующего элемента не совпадает с указанной, и равны элементам исходной матрицы (вектора) в противном случае [6].

Известно, что для различных множеств решения в действительном случае существуют характеризации множеств решений — характеризация Оеттли—Прагера [7] для объединенного множества решений, характеризация Бека [8] для объединенного множества решений, характеризация Рона для множеств АЕ-решений. Использование тех или иных инструментов интервального анализа, выработанных для действительного случая, ограничивается свойствами данных объектов, и, как будет показано ниже на примере характеризации Бека, прямой перенос на комплексный случай возможен не всегда. Далее рассматривается возможность обобщения характеризаций на случай комплексных интервалов.

2. Характеризация Бека

В действительном случае для объединенного множества решений известна характеризация Бека — равенство

Ь) = {х е Ега | Ах П Ь = 0} = {х е Ега | 0 е Ах - Ь}.

Утверждение 1. Для полярных комплексных интервалов в приведенном выше смысле аналог данной характеризации неверен.

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

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

Доказательство. Если x £ Suni(A, b), то найдутся A £ A и b £ b такие, что AX = b, т. е. Ax П b = 0. Обратно, если Ax П b = 0, то существует b такой, что b £ b, b £ Ax, причем непременно найдутся A £ A и X £ x такие, что b = AX, и, следовательно,

X £ "M«¿(A, b).

В силу определения арифметических операций над интервалами из того, что Ax П b = 0, следует, что 0 £ Ax — b. Обратно, из того, что 0 £ Ax — b, так как Ax не содержит в силу условий "лишних" точек, а операция сложения интервалов определена так, что ноль лежит только в разности интервалов, имеющих непустое пересечение, следует Ax П b = 0. Таким образом, Ax П b = 0 ^ 0 £ Ax — b.

Лемма доказана.

3. Характеризация Рона

В действительном случае для множества AE-решений системы имеет место следующая эквивалентность, называемая характеризацией Рона:

x £ (A, b) ^^ | (mid A)x — mid b| < (rad A3 — rad Av) |x| + (rad b3 — rad bv), где mid и rad — операторы взятия средней точки и радиуса действительного интервала.

Теорема 1. Если на множестве комплексных интервалов операции сложения и умножения на скаляр определены таким образом, что ab + c = (ab + с | a £ a, с £ c}, mid x и rad x — однородные относительно умножения на скаляр функционалы на множестве комплексных интервальных векторов, причем

1) включение a С b эквивалентно неравенству |mid a — mid b| < rad b — rad a;

2) mid (a ± b) = mid a ± mid b, rad (a ± b) = rad a + rad b, то справедлив полный аналог характеризации Рона:

x £ (A, b) ^^ |(mid A)x — mid b| < (rad A3 — rad Av)|x| + (rad b3 — rad bv).

Доказательство. По определению множества AE-решений

(A, b) = (x £ Cn | (VA £ Av)(Vb £ bv)(3A £ A3)(3b £ b3) ((A + A)x = ( b + b))}.

В силу условий на операции сложения и умножения на скаляр это эквивалентно

Eap(A, b) = ( x £ Cn | (VA £ Av)(Vb £ bv)(3A £ A3)(3b £ b3)(Ax — b = b — Ax)} = = ( x £ Cn | (VA £ Av)(Vb £ bv)(Ax — b £ b3 — A3x)} = = ( x £ Cn | Avx — bv С b3 — A3x}.

Далее, согласно условию 1 на включение интервалов, последнее условие означает Imid (b3 — A3x) — mid (Avx — bv) I < rad (b3 — A3x) — rad (Avx — bv).

В силу однородности функционалов относительно умножения на скаляр x и условия 2 это эквивалентно

|mid (b3 - A3x) - mid (Avx - bv)| < rad b3 + rad A3 - |x| — rad Av - |x| — rad bv

Теорема доказана.

Фактически, доказательство данной теоремы существенно опиралось на характе-ризацию, полученную С.П. Шарым в [6], и следствием этого является применимость классических характеризаций для прочих множеств решений.

Утверждение 2. Для множеств AE-решений в случае круговых комплексных интервалов верен полный аналог характеризации Рона.

Доказательство. Рассмотрим для кругового комплексного интервала а = (c, r) функционалы mid а = c и rad а = r. Дальнейшее следует из теоремы 1 и свойств операций над круговыми комплексными интервалами.

Утверждение 3. Для объединенных множеств решений ИСЛАУ в случае круговых комплексных интервалов верен полный аналог характеризации Оеттли—Прагера:

x G Suni(A, b) ^^ |(mid A) x — mid b | < rad A |x| + rad b.

Данное утверждение — частный случай теоремы 1 для объединенного множества решений (матрица A3 и вектор b3 совпадают с A и b соответственно).

Утверждение 4. Для объединенных множеств решений ИСЛАУ в случае круговых комплексных интервалов верен полный аналог характеризации Бека:

Su„i(A, b) = {x G Cn | Ax П b = 0} = {x G Cn | 0 G Ax - b}.

Данное утверждение прямо следует из леммы и свойств операций над круговыми комплексными интервалами.

Обратимся теперь к рассмотрению характеризаций множеств решений комплексных ИСЛАУ в прямоугольной арифметике. Недостатком прямоугольных комплексных интервалов а + ib = {x = a + ib G C | a G а, b G b} является несоответствие "естественного" определения радиуса условиям теоремы 1. В силу того что прямоугольный комплексный интервал имеет два интервальных параметра, а не один, как в случае круговых, приведение его к соответствующему виду затруднительно. Однако условие непустоты пересечения прямоугольных комплексных интервалов может быть записано в виде

(а + ib) П (c + id) = 0 ^^ (а П c = 0) Л (b П d = 0),

т. е. сводится к проверке пересечения двух действительных интервалов. Определив для прямоугольного комплексного интервала Z = а + ib функционалы mid rZ — как взятие среднего элемента а, mid cZ как взятие среднего элемента b, rad rZ и rad rZ — как взятие радиусов соответствующих интервалов, можно заметить, что данные функционалы линейны, а условие 2 теоремы 1 выполняется в силу свойств действительных интервалов. В этом случае можно ввести векторные операторы mid cZ = (mid rZ, mid cZ)т и rad CZ = (rad r Z, rad cZ )т.

Теорема 2. Для прямоугольных комплексных интервалов имеет место следующий аналог характеризации Рона:

x G (A, b) ^^ |(midCA) x - midCb| < (radCA3 - radCAv)|x| + (radCb3 - radCbv).

Доказательство теоремы 2 полностью аналогично доказательству теоремы 1 с учетом указанного выше.

Утверждение 5. Для объединенных множеств решений ИСЛАУ в случае прямоугольных комплексных интервалов верен аналог характеризации Оеттли—Прагера, т. е.

x G EUni(A, b) ^^ |(mid cA)x - mid cb |< (rad с A) |x| + rad с b.

Утверждение 6. Для объединенных множеств решений ИСЛАУ в случае прямоугольных комплексных интервалов верен полный аналог характеризации Бека, т. е.

Suni(A, b) = {x G Cn | Ax П b = 0} = {x G Cn | 0 G Ax - b}.

Доказательство утверждений 5 и 6 аналогично доказательству утверждений 3 и 4 с учетом теоремы 2.

Список литературы

[1] Алефред Г., ХЕРЦВЕРГЕР Ю. Введение в интервальные вычисления. М.: Мир, 1987.

[2] Klatte P., Ullrich Ch. Complex sector arithmetic // Computing. 1980. Vol. 24. P. 139-148.

[3] Petkoyic M.S., Mitrovic Z.M., Petkoyic L.B. Arithmetic of circular rings // Interval Mathematics 1985. N.Y.: Springer Verlag, 1986. P. 133-142. (Lecture Notes in Computer Science. Vol. 212).

[4] Candau Y., Raissi T., Ramdani N., Ibos L. Complex interval arithmetic using polar form // Reliable Computing. 2006. N 12. P. 1-20.

[5] Rokne J., Lancaster P. Complex interval arithmetic // Communications of the ACM. 1971. Vol. 14. P. 111-112.

[6] Shary S.P. A new technique in systems analysis under interval uncertainty and ambiguity // Reliable Computing. 2002. Vol. 8, N 5. P. 321-418.

[7] Oettli W., Prager W. Compatibility of approximate solution of linear equations with given error bounds for coefficients and right-hand sides // Numer. Math. 1964. Vol. 6. P. 405-409.

[8] Beeck H. Uber die Struktur und Abschatzungen der Losungsmenge von linearen Gleichungssystemen mit Intervallkoeffizienten // Computing. 1972. Vol. 10. P. 231-244.

Поступила в редакцию 18 апреля 2008 г.