close

Вход

Забыли?

вход по аккаунту

?

Об испанской версии формального подхода к внешнему оцениванию множеств решений интервальных линейных систем.

код для вставкиСкачать
Вычислительные технологии
Том 16, ќ 3, 2011
Об испанской версии ормального подхода
к внешнему оцениванию множеств решений
интервальных линейных систем?
С. П. Шарый
Институт вычислительных технологий СО АН, Новосибирск, оссия
e-mail:
sharyit.ns.ru
Исследуется версия ормального (алгебраического) подхода к внешнему оцениванию множеств решений интервальных линейных систем уравнений, в основу
которой положена известная из математического анализа теорема Миранды. ассматриваются способы ее численной реализации, условия применимости и качество
оценивания. Представлены результаты численных экспериментов и рекомендации
по практическому использованию предлагаемой методики.
Ключевые слова: интервальные линейные уравнения, множество решений, внешняя оценка, теорема Миранды, ормальный (алгебраический) подход.
1. Постановка задачи и вводные сведения
Предметом рассмотрения в работе являются интервальные системы линейных алгебраических уравнений (ИСЛАУ) вида
?
a11 x1 + a12 x2 + . . . + a1n xn = b1 ,
?
?
?
?
? a21 x1 + a22 x2 + . . . + a2n xn = b2 ,
?
?
?
?
?
..
.
..
.
.
..
.
(1)
..
.
an1 x1 + an2 x2 + . . . + ann xn = bn
с интервальными коэициентами
1, 2, . . . , n,
..
aij
и интервальными правыми частями
bi , i, j =
или, кратко,
Ax = b,
где
A = ( aij )
интервальная
(2)
n Ч n-матрица, b = ( bi )
Системы (1) (2) мы понимаем как семейства точечных линейных систем
же структуры с матрицами
A?A
и векторами
n-вектор.
Ax = b той
интервальный
b ? b.
Множеством решений интервальной линейной системы уравнений будем называть
множество
?(A, b) =
x ? Rn | (? A ? A)(? b ? b)( Ax = b ) ,
образованное всевозможными решениями точечных систем
Ax = b
(3)
A?A
и b?b
(см., например, [1 3?). Часто его называют также объединенным множеством реше-
ний, поскольку для интервальных уравнений существуют другие множества решений
?
абота выполнена при инансовой поддержке Президентской программы Ведущие научные шко-
лы оссии (грант ќ НШ-6068.2010.9).
100
Об испанской версии ормального подхода к внешнему оцениванию...
101
[4 8?, более адекватные тем или иным конкретным практическим ситуациям. В данной
работе они не рассматриваются, и поэтому мы называем (3) сокращенным термином
множество решений.
Известно, что множество решений
?(A, b)
является многогранным (полиэдраль-
ным) множеством, в общем случае невыпуклым, но его пересечение с каждым из ортанn
тов пространства R выпукло. Точное и полное описание множества решений практически невозможно в силу его огромной трудоемкости, а, с другой стороны, в большинстве
реальных постановок задач в этом нет необходимости. Чаще достаточно знать какие-то
оценки множества решений либо его приближенное описание с помощью более простых
множеств, имеющих меньшую конструктивную сложность.
Далее интервальная
n Ч n-матрица A предполагается
неособенной, т. е. содержащей
A
только неособенные (невырожденные) точечные матрицы
множество решений
?(A, b)
с
det A 6= 0,
в силу чего
системы (1) (2) ограничено. В данной работе мы будем
решать задачу его внешнего покоординатного оценивания, т. е. нахождения наиболее
точных оценок для
? = 1, 2, . . . , n. Это
min{ x? | x ? ?(A, b) }
снизу и для
max{ x? | x ? ?(A, b) }
сверху,
равносильно отысканию для множества решений объемлющего пря-
моугольного параллелепипеда (так называемого бруса) со сторонами, параллельными
координатным осям (рис. 1):
Найти (по-возможности, меньший) брус в
Rn
со сторонами,
параллельными координатным осям, содержащий множество
решений
?(A, b)
интервальной системы уравнений
(4)
Ax = b.
Подобная постановка задачи часто возникает при анализе чувствительности статических систем, описываемых линейными алгебраическими уравнениями (см. пример в
разделе 2).
Наша система обозначений следует неормальному международному стандарту на
обозначения в интервальном анализе [9?. В частности, множество всех замкнутых интервалов вещественной оси обозначено
IR, интервалы и интервальные величины выделены
x2
6
Внешняя оценка множества решений
Множество решений
C
@
PP
C @
PP
PP C @
@
PPC
C
CC
C
C
C
@ C
@ C
@
@CC
-
x1
ис. 1. Внешнее оценивание множества решений интервальным вектором-брусом
102
С. П. Шарый
буквами жирного шрита
A, B , C ,
...,
x, y , z ,
тогда как неинтервальные (точечные)
величины специально не выделяются.
x и сверху x означает нижний и верхний конец интервала x, а нераx ? 0 (x ? 0) эквивалентно x ? 0 и x ? 0 (x ? 0 и x ? 0 соответственно).
Черта снизу
венство
Кроме того, нам понадобятся
1
rad x = (x ? x)
2
радиус интервала,
|x| = max{ |x|, |x| } абсолютное значение (модуль) интервала,
min{ |x|, |x| }, если 0 6? x,
мигнитуда интервала (наименьшее
hxi =
расстояние точек интервала до нуля).
0,
иначе
Абсолютное значение и мигнитуда интервала являются, как видим, в некотором смысле
антиподами.
Интервальный вектор определяется как вектор, столбец или строка с интервальными компонентами. Его геометрическим образом является прямоугольный параллеn
лепипед в R со сторонами, параллельными координатным осям, который, как уже
упоминалось, часто называют брусом. Для интервалов, интервальных векторов и матриц естественно определено отношение теоретико-множественного включения ?. К
интервальным векторам и матрицам операции взятия нижнего и верхнего концов, абсолютного значения будут применяться покомпонентно и поэлементно. Например,
матрица тех же размеров, что и
рация
h·i
A,
составленная из модулей элементов
A.
|A|
Но опе-
в применении к матрицам будет иметь в соответствии с традицией особый
смысл.
Компарантом
матрицу того же
1
A = ( aij ) ? IRnЧn мы
размера, обозначаемую hAi, такую, что
h aij i, если i = j,
ij -й элемент hAi :=
?| aij |, если i 6= j.
интервальной матрицы
называем точечную
В частности, для точечной матрицы операция взятия компаранта это принудительное
назначение нужных знаков для элементов матрицы, положительных для диагональных элементов и отрицательных для внедиагональных.
Наконец, если
оболочкой
щий
S.
S
S
непустое ограниченное множество в
Rn ,
то его интервальной
называется наименьший по включению интервальный вектор, содержа-
Интервальная оболочка это интервальный объект, наилучшим образом при-
ближающий извне (т. е. объемлющий) рассматриваемое множество. Кроме того, через
IS будем обозначать множество всех интервальных векторов-брусов x ? IRn , содержащихся в
S,
т. е.
IS = { x ? IRn | x ? S }.
Посредством
IR помимо множества вещественных интервалов будем обозначать так-
же классическую интервальную ариметику алгебраическую систему, образованную
интервалами вещественной оси с операциями сложения, вычитания, умножения и деления, определенными по представителям, т. е. в соответствии с ундаментальным
принципом
x ? y = { x ? y | x ? x, y ? y }
для
? ? { + , ? , · , / }.
1 В англоязычной терминологии сomparison matrix, см. [3, 10?.
Об испанской версии ормального подхода к внешнему оцениванию...
103
Иными словами, результирующий интервал любой операции есть множество, образованное всевозможными результатами этой операции между элементами интерваловоперандов. азвернутые ормулы для интервальных сложения, вычитания, умножения
и деления выглядят следующим образом [1 3, 7, 11?:
x + y, x + y ,
x ? y = x ? y, x ? y ,
x · y = min{x y, x y, x y, x y}, max{x y, x y, x y, x y} ,
x/y = x · 1/y, 1/y
для y 6? 0.
x+y =
Для интервальных векторов и матриц ариметические операции являются аналогами соответствующих операций для точечного случая. В частности, сумма (разность) двух интервальных матриц одинакового размера есть интервальная матрица
того же размера, образованная поэлементными суммами (разностями) операндов. Если
X = ( xij ) ? IRmЧl и Y = ( y ij ) ? IRlЧn , то произведение матриц X и Y есть матрица
Z = ( z ij ) ? IRmЧn такая, что
z ij :=
l
X
xik y kj .
k=1
Z = { XY | X ? X, Y ? Y }, т. е. результат умножения
интервальных матриц X и Y есть интервальная оболочка множества результатов произведений XY по представителям X ? X и Y ? Y .
Отметим, что при этом
2. Практическая иллюстрация постановки
Задачи внешнего оценивания множеств решений интервальных систем уравнений естественно возникают в самых различных математических моделях, и многочисленные
примеры на эту тему заинтересованный читатель может увидеть в тематических подборках статей на сайте Интервальный анализ и его приложения [12?. ассмотрим
более подробно в качестве практического примера, приводящего к нашей постановке,
задачу расчета режимов электроэнергетических сетей. Одной из основных рабочих моделей подобных сетей являются системы линейных уравнений узловых потенциалов
(см. [13?)
Y U = J,
где
Y
токов,
квадратная матрица узловых проводимостей,
U
(5)
J
вектор-столбец задающих
вектор-столбец искомых узловых потенциалов. Узловые проводимости элементы матрицы
Y
образуются как суммы проводимостей ветвей сети, сходящихся
в рассматриваемом узле. После решения системы (5) относительно
U
величины токов в
ветвях сети (необходимые, например, при выборе проводов и пр.) определяются согласно закону Ома для участка цепи. Иногда при описании этого метода говорят также об
узловых напряжениях.
В реальных электрических сетях в результате изменения токов нагрузки и коммутационных переключений в электрической схеме коэициенты системы (5) и элементы
ее вектора правой части изменяются, в силу чего их нельзя больше считать имеющими
104
С. П. Шарый
определенные вещественные значения. Эта ситуация достаточно адекватно описывается
интервальной системой линейных алгебраических уравнений
Y U = J,
где
Y
интервальная матрица,
J
(6)
интервальный вектор, образованные интервалами
возможных значений узловых проводимостей и задающих токов соответственно [14?.
При этом нам нужно найти границы изменения решения
U
в условиях, когда элементы
матрицы системы и компоненты правой части изменяются в пределах предписанных
им интервалов. Таким образом, возникающая задача является задачей внешнего оценивания множества решений ИСЛАУ (6), причем требуются его внешние оценки именно
вдоль координатных осей как имеющие ясный содержательный смысл границ изменений напряжения сети в конкретных узлах. Именно такова задача (4).
Строго говоря, коэициенты исходной системы (5) элементы матрицы
Y
свя-
заны между собой и изменяются в пределах предписанных им интервалов из
Y
не
независимо друг от друга, а связанным образом. Это вносит дополнительную специику в постановку задачи, уменьшая множество решений и делая его оценивание более
трудным. Но в первом приближении, когда рассматривается простейшая модель, для
практики вполне достаточно получение оценок множества решений интервальной линейной системы (6) без учета каких-либо связей.
3. Теорема Миранды и основы интервальной техники
В математическом анализе хорошо известна теорема Больцано Коши.
Теорема Больцано Коши
[15?. Если ункция F : R ? R непрерывна на интерX ? R и на его концах принимает значения разных знаков, то внутри интервала
X существует нуль ункции F , т. е. точка x? ? X , в которой F (x?) = 0.
вале
Часто ее называют теоремой Больцано (см., например, [16?), так как именно он первым обнаружил сормулированное свойство непрерывных ункций. Далее в работе
используется многомерное обобщение этого результата, опубликованное более чем столетием позже в заметке [17?.
Теорема Миранды.
?
F : Rn ? Rn , F (x) = F1 (x), F2 (x), . . . , Fn (x)
n
ункция, непрерывная на брусе X ? R со сторонами, параллельными координатным
осям, и для любого i = 1, 2, . . . , n имеет место либо
Fi X 1 , . . . , X i?1 , X i , X i+1 , . . . , X n ? 0 и Fi X 1 , . . . , X i?1 , X i , X i+1 , . . . , X n ? 0,
Пусть
либо
Fi X 1 , . . . , X i?1 , X i , X i+1 , . . . , X n ? 0
и
Fi X 1 , . . . , X i?1 , X i , X i+1 , . . . , X n ? 0,
т. е. области значений каждой компоненты ункции
F,
т. е.
на соответствующих про-
X имеют разные знаки. Тогда
точка x? ? X , в которой F (x?) = 0.
тивоположных гранях бруса
нуль ункции
F (x)
на брусе
X
существует
Характерной особенностью теоремы Миранды является специальная орма множества, на котором утверждается существование нуля ункции: оно должно быть брусом
со сторонами, параллельными координатным осям, т. е. интервальным вектором. Кроме
того, для конструктивного применения теоремы Миранды нужно уметь находить или
как-то оценивать области значений ункций на подобных множествах.
Об испанской версии ормального подхода к внешнему оцениванию...
105
Удобное средство для решения этой задачи предоставляют методы интервального
анализа. Задача о вычислении области значений ункции на брусах эквивалентна задаче оптимизации, но в интервальном анализе она принимает специическую орму
задачи о вычислении так называемого интервального расширения ункции [2, 3, 7, 11?.
Определение.
D непустое подмножество пространства Rn . Интерm
вальная ункция f : ID ? IR называется интервальным продолжением вещественm
ной ункции f : D ? R , если f (x) = f (x) для всех x ? D . Интервальная ункm
ция f : ID ? IR
называется интервальным расширением вещественной ункции
m
f : D ? R , если
1) f (x) интервальное продолжение для f (x),
?
??
2) f (x) монотонна по включению, т. е. x ? x
? f (x? ) ? f (x?? ) на ID .
Таким образом, если f (x) интервальное расширение ункции f (x), то для области
значений f на брусе X ? D получаем следующую внешнюю (с помощью объемлющего
Пусть
множества) оценку:
{ f (x) | x ? X } = { f (x) | x ? X } ? f (X).
Эективное построение интервальных расширений ункций важнейшая задача
интервального анализа, поиски различных решений которой продолжаются и в настоящее время. Самым первым результатом в этом направлении является приведенная
ниже теорема, которую часто называют основной теоремой интервальной ариметики.
Теорема
x =
брусе
[1 3, 7, 11?. Если для рациональной ункции f (x) = f (x1 , x2 , . . . , xn ) на
(x1 , x2 , . . . , xn ) ? IRn определен результат f? (x) подстановки вместо ее
аргументов интервалов
x1 , x2 ,
...,
xn
и выполнения всех действий над ними по пра-
вилам интервальной ариметики, то
{ f (x) | x ? x } ? f? (x),
т. е.
f? (x)
содержит множество значений ункции
f (x)
Видно, что по отношению к рациональной ункции
f? (x),
x.
f (x) интервальная
на
ункция
о которой идет речь в основной теореме интервальной ариметики, является
интервальным расширением. Оно называется естественным интервальным расшире-
нием, и его вычисление не представляет никаких трудностей.
Использование естественного интервального расширения подчас дает слишком широкие внешние оценки областей значений ункций, но оказывается, что если в выражение для рациональной ункции
f
каждая переменная входит не более одного раза в
первой степени, то естественное интервальное расширение дает точную область значений ункции [1 3, 7, 11?. Это условие выполнено, в частности, для линейных ункций,
f (x) = f (x1 , x2 , . . . , xn ) = ?1 x1 + ?2 x2 + · · · + ?n xn с некоторыми постоянными
эициентами ?1 , ?2 , . . . , ?n .
Если F (x) = Ax ? b для n Ч n-матрицы A = (aij ) и n-вектора b = (bi ), то в
когда
ко-
ка-
честве немедленного следствия теоремы Миранды и основной теоремы интервальной
ариметики получаем следующее условие существования решения системы линейных
n
уравнений Ax = b в интервальном брусе X ? IR : если для каждого i = 1, 2, . . . , n
справедливо
106
С. П. Шарый
aii X i +
X
aij X j ? bi ? 0
X
aij X j ? bi ? 0
и
aii X i +
j6=i
X
aij X j ? bi ? 0
(7)
X
aij X j ? bi ? 0,
(8)
j6=i
или
aii X i +
и
aii X i +
j6=i
j6=i
где все ариметические операции являются операциями интервальной ариметики, то
брус
X
содержит решение системы линейных уравнений
Ax = b.
Заметим, что выписанные пары соотношений (7) и (8) являются взаимнодополнительными: неравенства (7) имеют место при
Если же
aii 6= 0
для какого-то
i,
aii ? 0,
а неравенства (8) при
aii ? 0.
то выполняется лишь одна пара неравенств, а другая
ложна.
Для дальнейшего преобразования выписанных соотношений (7) (8) к более удобному виду имеет смысл выйти из классической интервальной ариметики
интервальную ариметику Каухера
KR,
IR в полную
более широкую алгебраическую систему, об-
ладающую хорошими алгебраическим свойствами (см. оригинальную диссертацию [18?
или изложение основ этой ариметики в [6 8, 19 21?).
4. Полная интервальная ариметика Каухера
KR
получается из интервальной ариметики
IR
с помощью алгебраического и поряд-
кового пополнения. Элементами полной интервальной ариметики
вещественных чисел
[ ?, ? ],
KR
не обязательно связанные соотношением
являются пары
? ? ?,
так что
IR ? KR. Обычные интервалы из IR называются при этом правильными, а интервалы
[ ?, ? ], для которых ? > ?, неправильными. Если a = [ ?, ? ], то ? левый конец
интервала a, и он обозначается a или inf a, а ? правый конец интервала a, и он обозначается a или sup a. Правильные и неправильные интервалы переходят друг в друга
в результате операции дуализации
dual [ x, x ] := [ x, x ],
которая меняет местами концы интервала, переворачивая его. Хотя может показаться,
что неправильные интервалы вроде
[2, 1]
не имеют ясного содержательного смысла,
ниже мы укажем одну из возможных интерпретаций таких интервалов и операций над
ними (м. (15)). В общем случае любой элемент
x ? KR
можно мыслить как обычное
множество точек из правильной проекции
pro x :=
x,
dual x,
если
если
x
x
правильный,
неправильный.
Правильность или неправильность интервала влияет при этом на способ его вступления
в ариметические и прочие операции.
Теоретико-множественное упорядочение интервалов по включению на
но распространяется и на
KR.
Именно, для интервалов
x?y
Например,
[3, 1] ? [2, 2] = 2.
??
x?y
и
x, y ? KR
x ? y.
IR естествен-
полагают
(9)
Об испанской версии ормального подхода к внешнему оцениванию...
Сложение и умножение на число определяются в
x + y :=
? · x :=
Всякий элемент
x ? KR
opp x,
значаемый
x + y, x + y ,
(
[ ? x, ? x ],
[ ? x, ? x ],
KR
если
107
следующим образом:
? ? 0,
(10)
иначе.
имеет, следовательно, единственный противоположный, обо-
причем из соотношения
x + opp x = 0
следует, что
opp x = [ ?x, ?x ].
Таким образом, относительно операции сложения ариметика
KR
является комму-
тативной группой, изоморной аддитивной группе стандартного линейного простран2
ства R .
Чтобы выписать явные ормулы для умножения, выделим в
KR
следующие под-
множества:
P := { x ? KR | (x ? 0) & (x ? 0) }
Z := { x ? KR | x ? 0 ? x }
?P := { x ? KR | ?x ? P }
нульсодержащие интервалы,
неположительные интервалы,
dual Z := { x ? KR | dual x ? Z }
В целом
неотрицательные интервалы,
интервалы, содержащиеся в нуле.
KR = P ? Z ? (?P) ? (dual Z), и умножение
в интервальной ариметике Ка-
ухера может быть описано с помощью табл. 1 [18, 20?. Из нее, в частности, видно, что это
умножение допускает нетривиальные делители нуля. Например,
[ ?1, 2 ] · [ 5, ?3 ] = 0.
Интервальное умножение в ариметике Каухера оказывается коммутативным и ассоциативным [18, 20?, как и в классической интервальной ариметике, но группу по
умножению в
KR образуют лишь интервалы x, удовлетворяющие
условию
x x > 0, т. е.
не содержащие нуль и не содержащиеся в нуле интервалы.
Любой интервал
что
x x > 0),
x ? KR, не содержащий
нуля и не содержащийся в нем (т. е. такой,
имеет единственный алгебраически обратный, который обозначим
При этом из соотношения
x · inv x = 1
следует
1 1
inv x =
,
.
x x
Т а б л и ц а 1. Умножение в полной интервальной ариметике KR
·
y?P
y?Z
y ? ?P
y ? dual Z
x?P
[ x y, x y ]
[ x y, x y ]
[ x y, x y ]
[ x y, x y ]
x?Z
[ x y, x y ]
x ? ?P
[ x y, x y ]
[ x y, x y ]
[ x y, x y ]
[ x y, x y ]
x ? dual Z
[ x y, x y ]
0
[ x y, x y ]
[ max {x y, x y},
min {x y, x y} ]
[ min {x y, x y},
[ x y, x y ]
max {x y, x y} ]
0
inv x.
108
С. П. Шарый
Взаимосвязь сложения и умножения в ариметике Каухера выражается следующими соотношениями:
если
x
правильный, то
x · (y + z) ? x · y + x · z
если
x
неправильный, то
субдистрибутивность,
x · (y + z) ? x · y + x · z
(11)
супердистрибутивность.
(12)
В нашей работе важную роль будут играть операции
x ? y := sup ? { x, y } = min{x, y}, max{x, y} ,
x ? y := inf ? { x, y } = max{x, y}, min{x, y} (13)
(14)
взятие соответственно верхней и нижней грани относительно порядка ?.
ется решеткой относительно этих операций, тогда как
IR
x правилен,
_
x=
x,
операции взятия минимума. Если интервал
KR
явля-
была неполна относительно
то он представляется в виде
x?x
а если
x
неправилен, то
^
x=
x.
x?dual x
В общем случае для результата любой ариметической операции
имеет место представление
x?y =
ИИ
x
x
y
? ? { +, ?, · , / } в KR
(x ? y),
(15)
y
где
И
x
:=
x
?
?
?
?
?
?
?
_
,
если
x
правильный,
если
x
неправильный, x?x
^
,
x?dual x
так называемая условная операция взятия экстремума по включению, зависящая от
x, выписанного справа сверху ее символа. Она является либо
максимумом, либо минимумом по включению ? в зависимости от того, правилен
или неправилен x. При этом экстремум берется по всем x из правильной проекции
интервала x. Представление (15), впервые полученное в [18?, выражает связь между
результатом интервальной операции x ? y и результатами точечных операций x ? y для
x ? pro x и y ? pro y . Формулу (15) можно даже взять за основу для определения
интервального параметра
ариметических операций в полной интервальной ариметике (см. [22?).
Операции взятия нижней и верхней граней по включению (13) (14) обладают рядом
полезных свойств, на которые мы будем опираться в дальнейшем в работе. Во-первых,
несложными выкладками можно убедиться, что для любого скаляра
??R
? (x ? y) = (?x) ? (?y),
(16)
? (x ? y) = (?x) ? (?y).
(17)
Далее, справедливы следующие дистрибутивные свойства сложения по отношению к
операциям взятия нижней и верхней граней (см. [18, 20?):
x + (y ? z) = (x + y) ? (x + z),
(18)
x + (y ? z) = (x + y) ? (x + z).
(19)
Об испанской версии ормального подхода к внешнему оцениванию...
109
Для умножения точные дистрибутивности в общем случае не имеют места, но, как
показывается в [23?,
x · (y ? z) = xy ? xz,
x · (y ? z) ? xy ? xz,
если
x
(20)
правильный интервал, и
x · (y ? z) ? xy ? xz,
x · (y ? z) = xy ? xz,
если
x
(21)
неправильный. Существует, тем не менее, важный частный случай дистрибу-
тивностей максимума и минимума по умножению, относящийся к операндам и результату этой интервальной ариметической операции:
_ _
x·y =
x ·y =
(xy)
x?x
x·y =
^
x
правильный,
(22)
x?x
x
x?dual x
если
·y =
^
(xy)
если
x
неправильный.
(23)
x?dual x
Обоснование этих равенств нетрудно получается из представления (15) и соотношений (16), (17). Отличие равенств (22) (23) от предшествующих включений (20) (21)
можно понять, приняв во внимание тот акт, что (22) (23) получаются при взятии
максимума или минимума по точечным представителям из целого интервала, т. е. при
весьма специальных условиях на эти экстремумы.
езультаты композиции основных инволюций на множестве
дественного отображения,
?( · )
умножения на
(?1),
KR,
т. е. id( · ) тож-
opp( · ) взятия алгебраически
противоположного элемента, dual( · ) дуализации, описаны в табл. 2. Ее анализ показывает, что множество инволюций ариметки
KR
образует относительно операции
композиции так называемую четверную группу Клейна [24?. В частности, для любого
x ? KR
?opp x = dual x.
(24)
Нетрудно обосновывается также следующее важное соотношение:
inv (dual x) = 1/x,
справедливое для всех интервалов
x ? KR,
(25)
удовлетворяющих
x x > 0.
Наконец, отме-
тим, что
dual (x + y) = dual x + dual y,
dual (xy) = dual x · dual y.
Т а б л и ц а 2. Композиция инволюций в ариметике KR
?
id
opp
dual
id
id
opp
dual
id
dual
opp
opp
opp
dual
id
dual
dual
opp
id
(26)
110
С. П. Шарый
Интервальные матрично-векторные операции в полной интервальной ариметике
Каухера определяются аналогично операциям над векторами и матрицами с элементами из
IR.
Сумма (разность) двух интервальных матриц одинакового размера есть
интервальная матрица того же размера, образованная поэлементными суммами (разmЧl
lЧn
ностями) операндов. Если X = ( xij ) ? KR
и Y = ( y ij ) ? KR
, то произведение
mЧn
матриц X и Y есть матрица Z = ( z ij ) ? KR
такая, что
z ij :=
l
X
xik y kj .
k=1
Произведением скалярного интервала x ? KR на интервальную матрицу Y = ( y ij ) ?
KRmЧn назовем интервальную матрицу из KRmЧn , обозначаемую xY и такую, что
(xY )ij = x y ij .
Подобным же образом определяется и произведение интервальной мат-
рицы на интервал-скаляр.
В работе будем пользоваться следующим терминологическим соглашением: интервальный вектор или матрица называются правильными, если их компонентами (элементами) являются только правильные интервалы, т. е. принадлежащие IR.
n
n
На многомерных интервальных пространствах IR и KR топология может быть
определена двумя способами. Стандартный способ введение обычной метрики
dist (x, y) := max{kx ? yk, kx ? yk},
где
k·k
некоторая векторная норма на
Rn .
x, y ? KRn ,
(27)
IRn
эта метрика сов-
Для пространства
падает с хаусдоровым расстоянием между интервальными векторами как брусами в
Rn , порождаемым нормой k · k. Но иногда бывает полезно работать с векторнозначным
n
n
расстоянием мультиметрикой, которая вводится на IR и KR как
?
?
Dist (x, y) := ?
dist ( x1 , y 1 )
..
.
dist ( xn , y n )
?
?
n
? ? R+ .
(28)
Те же конструкции очевидным образом переносятся на множества интервальных матmЧn
mЧn
риц IR
и KR
.
5. Оценки решений линейных систем
Продолжим преобразование соотношений (7) (8). Пусть рассматриваемая система ли-
Ax = b с матрицей A = (aij ) и правой частью b = (bi )
индекса i, и потому имеет место первая пара (7) из со-
нейных алгебраических уравнений
такова, что
aii ? 0
для данного
отношений (7) (8). асписывая определение неотрицательности и неположительности
интервалов, нетрудно вывести, что оно эквивалентна неравенствам
aii X i +
X
aij X j
j6=i
!
? bi ? 0
и
aii X i +
X
aij X j
j6=i
!
? bi ? 0,
которые, в свою очередь, означают, что
aii · dual X i +
X
j6=i
aij X j
!
? bi ? 0
и
aii · dual X i +
X
j6=i
aij X j
!
? bi ? 0
(29)
Об испанской версии ормального подхода к внешнему оцениванию...
111
в силу очевидных соотношений
X i = dual X i
С учетом знака
aii
и
X i = dual X i .
(30)
и определения (10) справедливы равенства
aii · dual X i = aii · dual X i
и
aii · dual X i = aii · dual X i ,
поэтому неравенства (29) равносильны следующим:
aii · dual X i +
X
aij X j
j6=i
!
? bi ? 0
aii · dual X i +
и
X
aij X j
j6=i
ассмотрим теперь случай
aii ? 0,
!
? bi ? 0.
(31)
при котором имеет место вторая пара (8) из
соотношений (7) (8). Их можно переписать в виде неравенств
aii X i +
X
aij X j
j6=i
!
? bi ? 0
aii X i +
и
X
aij X j
j6=i
!
? bi ? 0,
или
aii · dual X i +
X
aij X j
j6=i
!
? bi ? 0
aii · dual X i +
и
X
aij X j
j6=i
!
принимая во внимание те же очевидные соотношения (30). Поскольку
? bi ? 0,
(32)
aii ? 0, то в силу
(10) справедливы равенства
aii · dual X i = aii · dual X i
и
aii · dual X i = aii · dual X i ,
следовательно, (32) равносильно
aii · dual X i +
X
j6=i
aij X j
!
? bi ? 0
и
aii · dual X i +
X
aij X j
j6=i
!
? bi ? 0.
Как видно, эти соотношения совпадают с (31), которые были получены для
Поэтому в целом, вне зависимости от знака элемента
метике
KR
aii ,
aii ? 0.
в полной интервальной ари-
имеем следующее предложение.
Предложение 1.
X = ( X 1 , X 2 , . . . , X n )? удовлетворяет
!
X
aii · dual X i +
aij X j ? bi ? 0, i = 1, 2, . . . , n,
Если брус
условиям
(33)
j6=i
то он содержит решение системы линейных уравнений
A = ( aij )
и
n-вектором
правой части
Ax = b
с
n Ч n-матрицей
b = (bi ).
Заметим, что необходимым условием существования телесного бруса
что
rad X j > 0
для
j = 1, 2, . . . , n,
X , т. е.
такого,
который удовлетворяет Предложению 1, является
неравенство нулю всех диагональных элементов:
aii 6= 0, i = 1, 2, . . . , n.
Действительно,
112
С. П. Шарый
akk = 0,
если какое-то
то в левой части соответствующего включения (33) будем иметь
выражение
X
akj X j ? bk ,
j6=k
которое является правильным интервалом, или вещественным числом. Его включение
akj 6= 0
в нулевой интервал, согласно определению (9), невозможно, если
одного
стемы
хотя бы для
j = 1, 2, . . . , n. Указанному условию удовлетворяют, в частности, линейные сиAx = b с неособенными матрицами A (такими, что det A 6= 0), в каждой строке
которых должны находиться ненулевые элементы. С другой стороны, если в исходной
системе уравнений матрица
A
неособенна, то ясно, что путем перестановки уравнений
или же перенумерацией переменных (это сответствует перестановке строк и/или столбцов в матрице
A)
нетрудно сделать все диагональные элементы ненулевыми.
6. Оценки для интервальных линейных систем
Ax = b. Коль скоро она
является семейством точечных систем Ax = b с A ? A и b ? b, а множество решений
?(A, b) есть объединение решений всех точечных систем Ax = b, то, основываясь на
Предложении 1, можно получить достаточный признак того, что брус X содержит
Перейдем далее к интервальной линейной системе уравнений
множество решений интервальной линейной системы:
nЧn
Предложение 2.
n
IR
Пусть
A ? IR
интервальная матрица,
i ? {1, 2, . . . , n}
!
интервальные векторы. Если для каждого
чение
aii · dual X i +
X
aij X j
j6=i
то брус
X
уравнений
содержит множество решений
b ? IRn
и
X ?
имеет место вклю-
? bi ? 0,
?(A, b)
интервальной линейной системы
Ax = b.
Доказательство.
i ? {1, 2, . . . , n} по определению
KR и в силу (18) и (22) имеем
X
aii · dual X i +
aij X j ? bi =
Для всякого иксированного
интервальных ариметических операций в
j6=i
_
=
aii
aii ?aii
=
_
!
· dual X i +
j6=i
( aii · dual X i ) +
aii ?aii
=
_
aii ?aii
=
X
?
?
_
aij ?aij
X _
?
aij ? X j ?
( aij X j ) ?
j6=i aij ?aij
_
_
aii · dual X i +
aij ?aij bi ?bi
j6=i
_
_
aij ?aij bi ?bi
j=1,...,n
_
bi
aij X j ? bi
j6=i
aii · dual X i +
X
j6=i
!
=
bi ?bi
bi ?bi
X
bi
!
_
aij X j ? bi
!
!
.
=
=
(34)
Об испанской версии ормального подхода к внешнему оцениванию...
113
Следовательно, если
aii · dual X i +
X
aij X j
j6=i
!
? bi ? 0,
!
? bi ? 0
то включение (33)
aii · dual X i +
X
aij X j
j6=i
aij ? aij и bi ? bi , i, j = 1, 2, . . . , n, т. е. для всех точечных
линейных систем, содержащихся в Ax = b. В противном случае максимум по отношению включения ? от выражений, стоящих в левой части (33), не был бы включен в
должно выполняться для всех
нуль. Как следствие, принимая во внимание результат Предложения 1, можно утверждать, что брус
A?A
и
X
действительно содержит все решения точечных систем
b ? b.
Ax = b
с
Напомним теперь следующее определение.
Определение.
Формальное решение интервальной системы уравнений
?
F1 ( a1 , . . . , al , x1 , . . . , xn ) = b1 ,
?
?
?
?
? F2 ( a1 , . . . , al , x1 , . . . , xn ) = b2 ,
?
?
?
?
?
..
.
.. ..
.
.
..
.
..
.
(35)
Fm ( a1 , . . . , al , x1 , . . . , xn ) = bm
с интервальными параметрами
x = ( x1 , x2 , . . . , xn )? ,
..
.
a1 ,
...,
al , b 1 ,
...,
bm
это интервальный вектор
обращающий систему в равенство после подстановки в нее и
выполнения всех операций по правилам интервальной ариметики и прочих операций,
входящих в выражения для
Fi .
Таким образом, ормальное решение интервальных систем это объект, соответствующий обычному математическому понятию решения уравнения, но рассматриваемому в экзотической алгебраической системе интервальной ариметике, в качестве
которой могут выступать в зависимости от рассматриваемой задачи либо классическая
интервальная ариметика
IR, либо полная интервальная ариметика Каухера KR, ли-
бо какая-то другая интервальная алгебраическая система.
Отметим, что согласно традиции неизвестная переменная в интервальных уравнениях вида (35), как и в других встречающихся ниже уравнениях, специально не выделяется, а тип решения подчеркивается дополнительными характеристиками. В частности,
если все компоненты ормального решения являются правильными интервалами, то
будем называть его правильным ормальным решением интервальной системы уравнений.
Заменяя в ормулах (33) включение на равенство и привлекая понятие ормального
решения, можно придать результату Предложения 2 следующий менее общий, но более
удобный в вычислительном отношении вид (Предложение 3).
114
С. П. Шарый
Предложение 3.
параметров
A = (aij )
Пусть интервальный оператор
S : KRn ? KRn ,
b = (bi ), действует по правилу
?
X
a11 · dual x1 +
a1j xj ? b1
?
j6=1
?
X
?
? a22 · dual x2 +
a2j xj ? b2
?
?
j6=2
x 7? ?
..
..
..
..
?
.
.
.
.
?
?
X
? a · dual x +
anj xj ? bn
nn
n
зависящий от
и
j6=n
т. е. задается покомпонентно как
Si (A, b, x) = aii · dual xi +
X
aij xj ? bi ,
?
?
?
?
?
?
?,
?
?
?
?
?
i = 1, 2, . . . , n.
(36)
j6=i
Правильное ормальное решение интервальной системы уравнений
S(A, b, x) = 0
содержит множество решений
?(A, b)
(37)
интервальной линейной системы уравнений
Ax = b.
Например, для интервальной линейной системы Хансена [25?
[2, 3] [0, 1]
[1, 2] [2, 3]
x=
[0, 120]
[60, 240]
,
(38)
множество решений которой изображено на рис. 2, соответствующая система уравнений
(36) (37) имеет вид
(
[2, 3] · dual x1 + [0, 1] x2 ? [0, 120] = 0,
[1, 2] x1 + [2, 3] · dual x2 ? [60, 240] = 0,
x2
200
?100
100
x1
ис. 2. Множество решений интервальной системы Хансена (38)
Об испанской версии ормального подхода к внешнему оцениванию...
115
или, что равносильно,
(
[2, 3] · dual x1 + [0, 1] x2 = [120, 0],
[1, 2] x1 + [2, 3] · dual x2 = [240, 60].
Ее ормальное решение есть интервальный вектор
([?120, 90], [?60, 240])?,
который
является наименьшим по включению брусом, содержащим множество решений, т. е.
оптимальной (наилучшей) внешней оценкой множества решений системы (38). В общем
случае рассматриваемый подход дает, конечно, не столь точные оценки, и вопрос о
качестве оценивания будет подробно рассмотрен ниже в разделе 9.
Итак, нахождение внешней оценки множества решений исходной ИСЛАУ свелось
к нахождению ормального решения специальной интервальной системы уравнений.
Задача нахождения ормального решения это уже не задача оценивания или приближения, а, по существу, традиционная математическая задача решения некоторого
уравнения, хотя и рассматриваемая в непривычной алгебраической системе
KR.
Соот-
ветствующий общий подход к задачам оценивания множеств решений, сводящий исходную постановку к задаче нахождения ормального решения некоторой вспомогательной интервальной системы уравнений, называется, как известно, ормальным подходом
[7, 19, 26? (иногда его называют также ормально-алгебраическим подходом, можно
также встретить термин алгебраический подход). Это весьма общая методика, которая может реализовываться различными конкретными способами в зависимости от
конструкции вспомогательной интервальной системы уравнений и численного метода
поиска ее ормального решения. Отличительной особенностью ормального подхода
является его универсальность: как общая теоретическая схема подхода, так и соответствующие численные методы с равным успехом применимы к задачам внутреннего и
внешнего интервального оценивания даже более общих, чем объединенное, множеств
решений (см. [5 8, 27, 28?).
Для решения рассматриваемой задачи (4) ормальный подход применяется с середины 1990-х годов (см. [19, 21, 26?), и его традиционной основой служили следующие
классические результаты, которые мы приводим в современной и несколько расширенной ормулировке.
Лемма.
Пусть
?
неособенная диагональная матрица. Множество решений ин-
тервальной линейной системы уравнений
Ax = b
с
A ? IRnЧn
и
b ? IRn
совпадает с
множеством решений интервальной системы
x = Gx + h,
где
(39)
G = I ? ?A, h = ?b.
Теорема Апостолатоса Кулиша
[29 31?. Если матрица
G ? IRnЧn
такова,
что спектральный радиус матрицы, составленной из модулей ее элементов, меньше
единицы, т. е.
?(|G|) < 1,
то интервальная линейная система уравнений
имеет единственное правильное ормальное решение в
n
IR
x = Gx + h
. Оно может быть найдено
с помощью итерационного процесса
x(k+1) := Gx(k) + h,
x(0) и является внешней интервальной оценкой мно{ x ? Rn | (?G ? G)(?h ? h)( x = Gx + h ) } рассматриваемой интер-
при любом начальном векторе
жества решений
k = 0, 1, 2, . . .
вальной системы.
116
С. П. Шарый
Аналитические выражения, которые составлены из символов переменных, констант,
четырех ариметических операций (сложения, вычитания, умножения и деления) и элементарных ункций, будем называть элементарными ункциональными выражения-
ми. Обобщением теоремы Апостолатоса Кулиша на системы нелинейных уравнений
является теорема Алеельда Херцбергера.
Теорема Алеельда Херцбергера
[1?. Пусть в интервальной системе урав-
нений
x = G(a, x)
отображение
G : IRn ? IRn ,
(40)
действующее по правилу
x 7? G(a, x),
является
P -сжи-
мающим, т. е.
Dist G(a, x), G(a, y) ? P · Dist (x, y),
с такой неотрицательной матрицей
нент
Gi (a, x)
P,
что
?(P ) < 1,
и выражения для компо-
являются элементарными ункциональными выражениями, определен-
ными для рассматриваемых значений аргументов
a
и
x.
Тогда правильное ормаль-
ное решение интервальной системы уравнений (40) существует, единственно и является внешней интервальной оценкой ее множества решений
?(G, a) = {x ? Rn |
(?a ? a)(x = G(a, x))}.
езультат Предложения 3 дает еще один, отличный от теоремы Апостолатоса Кулиша, способ сведения внешней задачи (4) к нахождению ормального решения некоторой специальной интервальной системы уравнений. Он не является абсолютно новым
и ранее уже был получен в работе испанских математиков М.А. Сайнца, Э. арденьеса
и Л. Джорбы [28?, но в несколько другой орме и с помощью длинных и малоочевидных рассуждений, использующих технику так называемого модального интервального
анализа. Выше мы привели другой, прозрачный вывод этого акта. Будем называть
впредь результат Предложения 3 испанской версией ормального подхода к внешнему
оцениванию множеств решений интервальных линейных систем.
Путем перестановки уравнений (эквивалентной перестановке строк матрицы
компонент в векторе правой части
b)
A
и
результату Предложения 3 можно придать слеx? является правильным ормальным ре-
дующую орму: если интервальный вектор
шением интервальной системы уравнений
?
a11 ? 1 (x1 ) + a12 ? 1 (x2 ) + . . . + a1n ? 1 (xn ) = b1 ,
?
?
?
?
? a21 ? 2 (x1 ) + a22 ? 2 (x2 ) + . . . + a2n ? 2 (xn ) = b2 ,
?
?
?
?
?
.
..
.
..
..
.
.
..
.
..
(41)
an1 ? n (x1 ) + an2 ? n (x2 ) + . . . + ann ? 2 (xn ) = bn ,
? i : KR ? KR, i = 1, 2, . . . , n, таковы, что
? i (xj ) равно xj для одного из j ? {1, 2, . . . , n} и dual xj
для всех остальных индексов j ,
для каждого индекса j ? {1, 2, . . . , n} равенство ? i (xj ) = xj выполняется в точности для одного i,
?
?
то x ? ?(A, b), т. е. x есть внешняя интервальная оценка множества решений системы Ax = b. Именно в таком виде результат о внешнем оценивании Предложения 3
в которой отображения
для каждого
i
значение
игурирует в работах [27, 28?.
Об испанской версии ормального подхода к внешнему оцениванию...
117
7. Вычисление ормальных решений
На эективность развиваемого здесь подхода основное влияние имеет способ нахождения ормальных решений интервальных систем уравнений вида (36) (37).
В работе [27?, где впервые была рассмотрена эта система уравнений, для вычисления ее ормального решения предлагается стационарный итерационный метод типа Якоби, основанный на выделении из матрицы ИСЛАУ диагональной компоненты.
Недостаток этого метода линейная сходимость (подобная сходимости геометрической прогрессии), которая для некоторых интервальных линейных систем может быть
весьма медленной. Фактически для оценивания объединенного множества решений подобный способ ничем не лучше традиционных интервальных стационарных итерационных алгоритмов, не использующих выход в интервальную ариметику Каухера (см.
[1, 3, 11, 32?). Таким, к примеру, является популярный метод Кравчика [3, 7?.
Кроме того, в [27? рассматривается возможность сведения задачи нахождения ормального решения интервальных систем к оптимизационной задаче минимизации невязки. Этот путь весьма невыгоден, так как получающаяся целевая ункция является
негладкой, и ее глобальные свойства трудно поддаются исследованию. Соответственно,
выбор оптимизационных методов в этой ситуации весьма узок, а их сходимость в общем
случае проблематична.
Мы пойдем другим путем и воспользуемся техникой погружения интервального пространства в евклидово пространство двойной размерности [7, 8, 19?. Ее назначение соn
стоит в том, чтобы перейти из нелинейного интервального пространства KR в линейное пространство, только в котором и применимы многие математические концепции,
составляющие основу современных вычислительных методов (в частности, диеренцирование и выпуклость). Этот переход может быть осуществлен с помощью любого
n
2n
взаимно-однозначного отображения KR ? R
так называемого погружения, и его
конкретный выбор обычно диктуется соображениями удобства и наиболее аккуратного сохранения свойств рассматриваемых объектов при переходе в новое пространство.
n
2n
так, чтобы оно являлось
В частности, имеет смысл задавать погружение KR ? R
n
2n
изоморизмом аддитивных групп пространств KR и R .
n
2n
Отображение sti : KR ? R , задаваемое правилом
sti ( x1 , x2 , . . . , xn )? = (?x1 , ?x2 , . . . , ?xn , x1 , x2 , . . . , xn )? ,
n
называют стандартным погружением интервального пространства KR в линейное
2n
пространство R
[7, 19, 26?. Оно особенно удобно потому, что частичный порядок по
n
включению в KR переводится им в покомпонентный порядок на линейном простран2n
стве R . Иными словами,
x?y
где для
u, v ? R2n
в
KRn
неравенство
?
u ? v
sti (x) ? sti (y)
понимается как
в
R2n ,
ui ? vi , i = 1, 2, . . . , 2n.
Легко
также убедиться в том, что
sti (µx + ?y) = µ sti (x) + ? sti (y).
n
Интересующему нас отображению S : KR ?
2n
ставляет такое отображение S : R
? R2n , что
KRn
S = sti ? S ? sti ?1 ,
стандартное погружение сопо-
(42)
118
С. П. Шарый
которое будем называть индуцированным. Наиболее важное практическое следствие погружения состоит в том, что нахождение ормального решения уравнения (36) (37)
n
в KR может быть заменено на решение индуцированного уравнения S(x) = 0 в при2n
вычном евклидовом пространстве R .
Индуцированное отображение
b
S,
очевидно, непрерывно по
x
и по параметрам
A
и
в силу непрерывности стандартного погружения sti, операции дуализации и интер-
вальных ариметических операций сложения, вычитания и умножения в
KR.
Напомним следующее определение.
Определение
[33 35?. Пусть евклидово пространство
p
q
порядком 4. Отображение
F : R ? R
Rq
упорядочено частичным
называется порядково выпуклым относи-
тельно 4, если
F (?u + (1 ? ?)v) 4 ?F (u) + (1 ? ?)F (v)
для любых
u, v ? Rp
и
? ? [0, 1].
Наиболее важное свойство индуцированного отображения
nЧn
R
Предложение 4.
2n
Если
A ? IR
S
дает Предложение 4.
2n
, то индуцированное отображение
, определенное посредством (42), является порядково выпуклым в
R
2n
S : R
?
относитель-
но покомпонентного упорядочения векторов ?.
Доказательство.
? ? [0, 1]
Пусть
x? , x?? ? KRn .
Тогда для всякого
i = 1, 2, . . . , n
и любого
в силу (26) и субдистрибутивности умножения по сложению (11) справедлива
следующая цепочка преобразований:
Si ?x? + (1 ? ?)x?? =
X
= aii dual ?x?i + (1 ? ?)x??i +
aij ?x?i + (1 ? ?)x??i ? bi ?
j6=i
= ? aii dual x?i + (1 ? ?) aii dual x??i +
X
j6=i
=?
aii dual x?i
+
X
aij x?i
? bi
j6=i
X
??
??
+ (1 ? ?) aii dual xi +
aij xi ? bi =
j6=i
= ? Si (x? ) + (1 ? ?) Si (x?? ).
Следовательно, по определению порядка ? на
Si ?x? + (1 ? ?)x??
Si ?x? + (1 ? ?)x??
Если векторы
x? , x?? ? R2n
?aij x?i + (1 ? ?)aij x??i ? bi =
KR
? ? Si (x? ) + (1 ? ?) Si (x?? ),
(43)
? ? Si (x? ) + (1 ? ?) Si (x?? ).
(44)
таковы, что
x? = sti (x? )
и
x?? = sti (x?? ),
sti ?1 (x? ) = x?
и
sti ?1 (x?? ) = x?? ,
то
и поэтому
S ?x? + (1 ? ?)x?? = sti S ?x? + (1 ? ?)x?? .
Об испанской версии ормального подхода к внешнему оцениванию...
119
Привлекая определение стандартного погружения, с учетом (43) (44) получим соотношения
Si ?x? + (1 ? ?)x?? = ? Si ?x? + (1 ? ?)x?? ? ?? Si (x? ) ? (1 ? ?) Si (x?? ) =
= ? Si (x? ) + (1 ? ?) Si (x?? ) при 1 ? i ? n,
Si ?x? + (1 ? ?)x?? = Si ?x? + (1 ? ?)x?? ? ? Si (x? ) + (1 ? ?) Si (x?? ) =
= ? Si (x? ) + (1 ? ?) Si (x?? )
при
n + 1 ? i ? 2n.
Это и требовалось доказать.
Порядковая выпуклость индуцированного отображения S влечет существование его
2n
субдиеренциала ?S всюду в R
[33?. Можно показать и большее: S является полиэдральным отображением, т. е. таким, что его граик склеен из кусков гиперплоскостей. Следовательно, для нахождения решений индуцированного уравнения S(x) = 0
R2n имеет смысл применить субдиеренциальный метод Ньютона, развитый ра-
в
нее для задач подобного сорта и успешно зарекомендовавший себя (см., в частности,
[7, 19, 21, 36?):
Субдиеренциальный метод Ньютона
для решения уравнения (36) (37)
Выбираем некоторое начальное приближение x(0) ? R2n .
Если (k ? 1)-е приближение x(k?1) ? R2n , k = 1, 2, . . . , уже найдено,
то вычисляем какой-нибудь субградиент D (k?1) отображения S в точке
x(k?1) и полагаем
?1
x(k) := x(k?1) ? ? D (k?1)
S( x(k?1) ),
где ? ? ]0, 1] некоторая константа.
Нетривиальным моментом реализации субдиренциального метода Ньютона является выбор начального приближения. Вычислительные эксперименты показывают,
что он сходится из любого начального приближения, но количество итераций до сходимости при этом возрастает. Эмпирическим путем было установлено [19, 21?, что для
алгоритма, вычисляющего ормальное решение уравнения в рекуррентном виде (40),
наиболее выгодный выбор начального приближения это решение средней системы
уравнений
(mid A) x = mid b.
еализация и численные эксперименты (см. раздел 10) показывают, что в рассматриваемом случае субдиеренциальный метод Ньютона работает хорошо, причем при
? = 1
он в большинстве случаев находит ормальные решения уравнения (36) (37)
за небольшое конечное число итераций. В частности, метод по своей эективности
качественно превосходит стационарные итерационные методы типа Якоби, предложенные для решения аналогичной задачи в [27?. К примеру, для системы Хансена (38)
точное ормальное решение уравнения (36) (37) вычисляется субдиеренциальным
методом Ньютона всего за три итерации.
120
С. П. Шарый
8. Условия существования правильного ормального решения
К сожалению, даже когда множество решений ИСЛАУ непусто, ормальное решение
уравнения (36) (37) часто не существует или не является правильным. В последнем
случае оно не может быть проинтерпретировано согласно Предложению 3. Например,
для интервальной линейной системы
[1, 2] [2, 3]
[2, 3] [0, 1]
x=
[60, 240]
[0, 120]
,
(45)
которая получена перестановкой местами уравнений в системе Хансена (38) и имеет то
же самое множество решений (см. рис. 2), ормальным решением вспомогательной си?
стемы (36) (37) является неправильный интервальный вектор ([90, ?120], [240, ?60])
(субдиеренциальный метод Ньютона успешно находит его за четыре итерации). Исследуем это затруднение более тщательно.
Прежде всего отметим, что если какой-нибудь из диагональных элементов матрицы
A содержит
нуль, то ормальное решение уравнения (36) (37) не может быть пра-
вильным. Покажем, что в этом случае соответствующие выражения (36) будут правильными интервалами, которые не могут включаться в нуль.
?
Пусть x искомое ормальное решение. Воспользуемся представлением (34):
aii · dual x?i +
X
aij x?j ? bi
=
_
aii · dual x?i +
aij ?aij bi ?bi
j=1,...,n
j6=i
i = 1, 2, . . . , n.
_
Если какой-либо из
aii
X
!
aij X j ? bi ,
j6=i
является нульсодержащим интервалом, то соот-
ветствующее ему выражение в правой части выписанного равенства содержит
_
_
0 · dual x?i +
aij ?aij bi ?bi
j6=i
X
aij x?j ? bi
j6=i
!
=
X
aij x?j ? bi ,
j6=i
т. е. правильный интервал, который может быть равен нулю (имеющему нулевой радиус) в уравнении (37) лишь в исключительных случаях, когда равны нулю радиусы
P
суммы
aij x?j и компоненты правой части bi . Не будем выписывать строгую ормуj6=i
лировку этих условий, так как они неизбежно должны носить апостериорный харак?
тер, т. е. использовать знание вычисленного ормального решения x , что неизбежно снижает их практическую ценность. Впредь условимся (не вполне строго) считать,
что отсутствие нульсодержащих диагональных элементов в матрице исходной системы
(1) (2) является необходимым условием существования правильных ормальных решений системы (36) (37).
Итак, еномен системы (45) получает следующее объяснение: в исходной интервальной системе Хансена (38) диагональные элементы не содержат нулей, а система
(45) этим свойством уже не обладает.
Но отсутствие нульсодержащих элементов по диагонали матрицы ИСЛАУ не является достаточным условием правильности ормальных решений вспомогательных
систем (36) (37), и рассматриваемый вопрос требует дальнейшего исследования. ассмотрим в качестве примера интервальную линейную систему
[1, 2] [2, 3]
[2, 3]
1
x=
[60, 240]
[0, 120]
,
(46)
Об испанской версии ормального подхода к внешнему оцениванию...
которая получена из (45) заменой нульсодержащего элемента
[0, 1]
на
1
на месте
121
(2, 2).
Для нее ормальным решением вспомогательной системы (36) (37) является тот же
?
неправильный интервальный вектор ([90, ?120], [240, ?60]) .
Для целей дальнейшего анализа представим матрицу интервальной линейной системы уравнений
Ax = b
в виде суммы диагональной и внедиагональной частей, т. е.
как
A = C + D,
C
где
=
(cij )
(47)
матрица, в которой диагональ нулевая,
диагональные элементы совпадают с соответствующими
cij = aij
при всех
i 6= j ; D
=
diag {d1 , d2 , . . . , dn }
cii = 0, i = 1, 2, . . . , n, а внеэлементами матрицы A, т. е.
диагональная интервальная матри-
ца, элементы которой равны соответствующим диагональным элементам матрицы
т. е.
S
di = aii , i = 1, 2, . . . , n.
A,
Тогда введенный в Предложении 3 интервальный оператор
может быть записан как
S(x) = Cx + D·dual x ? b,
а уравнение (36) (37) примет вид
Cx + D·dual x ? b = 0.
В силу сказанного выше будем всюду далее предполагать, что
i = 1, 2, . . . , n.
?
Пусть x D неособенна, т. е. 0 6? di ,
ормальное решение этой интервальной системы уравнений, так что
Cx? + D·dual x? ? b = 0.
?
Добавим к обеим частям данного равенства по величине opp (D·dual x ), алгебраически
?
противоположной к D · dual x (что равносильно переносу этого члена с противоположным знаком в другую часть равенства). В результате получим
opp (D·dual x? ) = Cx? ? b,
откуда, умножая обе части на
?1
и учитывая, что
?opp (·) = dual (·),
будем иметь
dual (D·dual x? ) = b ? Cx? .
Наконец, опираясь на (26), приходим к соотношению
(dual D)·x? = b ? Cx? .
(48)
A не содержат нулей, то для (dual D)
inv (dual D), т. е. такая, что ее произве?1
Коль скоро inv dual (·) = (·) , то эта ал-
Если диагональные элементы в матрице
существует алгебраически обратная матрица
дение на
dual D
дает единичную матрицу.
гебраически обратная матрица совпадает с обычной обратной интервальной матрицей
D ?1 = diag{1/d1 , 1/d2 , . . . , 1/dn },
и потому, домножая на нее обе части равенства (48),
приходим к следующей равносильной орме записи уравнения (36) (37):
x = D?1 (b ? Cx).
(49)
Системы уравнений подобного вида, в которых неизвестная переменная выделена в одной из частей в чистом виде, называются системами уравнений в рекуррентном виде
122
С. П. Шарый
(про операторные уравнения в аналогичной орме говорят, что они являются уравнениями второго рода). Именно такой вид имеют интервальные системы уравнений в теоремах Апостолатоса Кулиша и Алеельда Херцбергера, на которые опиралась традиционная версия ормального подхода к внешнему оцениванию множеств решений.
?
В случае, когда x есть правильное ормальное решение интервальной системы
уравнений в рекуррентном виде (49), беря радиус от обеих частей равенства
x? = D ?1 b ? Cx? ,
получим
Но
rad (U V ) ? |U | · rad V
rad x? = rad D?1 b ? Cx? .
для любых правильных интервальных матриц
U
и
V
согла-
сованных размеров, для которых имеет смысл их произведение (см. [1, 3, 7?). Поэтому
rad D?1 b ? Cx? ? |D ?1 | · rad b ? Cx? = |D?1 | · rad b + rad (Cx? ) .
Если все компоненты вектора свободных членов
rad b > 0,
b
имеют ненулевую ширину, т. е.
то справедливо неравенство
rad x? > |D?1 | · rad Cx? ? |D?1 | |C| · rad x? .
Оно означает, в частности, что
имеет при
rad x? > 0.
(50)
Иными словами, если уравнение (36) (37)
rad b > 0 правильное ормальное решение, то это решение
Rn , все компоненты которого имеют ненулевую ширину.
является телес-
ным брусом в
Напомним теперь следующий акт из теории неотрицательных матриц. Если
неотрицательная
n Ч n-матрица, ?(A)
ее спектральный радиус и
?
A
положительное
вещественное число, то
?(A) < ? ??
?(A) ? ? ??
?v ? Rn v > 0 & Av < ?v ,
?v ? Rn v > 0 & Av ? ?v .
Доказательство может быть найдено, например, в книге . Хорна и Ч. Джонсона [37?
либо в англоязычных источниках [3, 10?. С другой стороны, неявным образом этот
акт обосновывается в доказательстве Х. Виландта теоремы Перрона Фробениуса о
неотрицательных матрицах, которое воспроизводится во многих пособиях по теории
матриц, например, в классической работе Ф. антмахера [38?.
?
В рассматриваемом случае для положительного вектора y = rad x и для неотрица?1
?1
тельной матрицы |D | |C| имеет место |D | |C| y < y . Следовательно, в силу выше?1
отмеченных свойств неотрицательных матриц спектральный радиус матрицы |D | |C|
должен быть строго меньше
1:
? |D?1 | |C| < 1.
(51)
Это необходимое условие существования правильного ормального решения систем
rad b > 0 и
поскольку D
не содержащих нуля диагональных элементах в A.
?1
?1
Отметим, что
диагональная матрица, то |D | |C| = |D C|, и
?1
выведенное условие равносильно ? |D C| < 1.
(49) и (36) (37) при
Полученным результатам можно придать несколько другую орму, для чего нам
понадобятся следующие определения.
Об испанской версии ормального подхода к внешнему оцениванию...
Определение
123
n Ч n-матрица A называется M-матрицей, если
A = sI ? P , где s ? R, P неотрицательная матрица и
[10, 39?. Точечная
она представима в виде
s > ?(P ).
Определение
[3, 7?. Интервальную
n Ч n-матрицу A ? IRnЧn
станем называть
интервальной M-матрицей, если M-матрицами являются все содержащиеся в ней
точечные матрицы.
Определение
A ? RnЧn называется H-матрицей, если ее компаnЧn
рант является M-матрицей. Матрица A ? IR
называется интервальной H-матрицей, если каждая вещественная матрица A ? A является H-матрицей.
[3, 7?. Матрица
Ясно, что у M -матрицы внедиагональные элементы неположительны. Нетрудно также показать, что диагональные элементы M -матрицы обязаны быть положительными.
Вообще M -матрицы относительно просто описываемый подкласс всех положительно
обратимых матриц, т. е. матриц, имеющих неотрицательную обратную матрицу [39?.
H -матрицы это специальный класс матриц, у которых диагональ доминирует над
остальной, внедиагональной, частью матрицы в спектральном смысле [3, 7, 10?. Класс
H -матриц включает в себя в качестве собственного подмножества все матрицы, удовлетворяющие традиционному условию диагонального преобладания, но не исчерпывается ими. Другой пример H -матриц неособенные треугольные матрицы, верхние или
нижние [3?. Для H -матриц удается сохранить многие хорошие свойства M -матриц, в
частности, оценку на обратную матрицу.
Для любого интервала
x ? IR
такого, что
0 6? x,
справедливо
1
= hxi?1 ,
x
D имеет место
?1 D = hDi?1 .
в силу чего для диагональной матрицы
соотношение
?1
(50) это позволяет сделать вывод о том, что hDi
|C| y < y для
?
n
?1
положительного вектора y = rad x ? R . В силу неотрицательности hDi
обе части
При
rad b > 0 с учетом
полученного неравенства можем домножить на эту матрицу, прийдя к
В выражении
hDi ? |C| y > 0.
носильно
вектора
hDi ? |C| нетрудно
hAiy > 0 для какого-то
(52)
увидеть компарант матрицы
y > 0,
hDiy > |C| y , т. е.
A,
поэтому (52) рав-
что является одним из признаков
H -матриц (см. подробности, к примеру, в [3, 7?). Мы обосновали Предложение 5.
Предложение 5.
ные элементы
A
Если в интервальной линейной системе
Ax = b
диагональ-
не содержат нулей и все компоненты правой части имеют нену-
левую ширину, т. е.
rad b > 0,
то для существования правильного ормального ре-
шения системы интервальных уравнений (36) (37) необходимо, чтобы
A
являлась
H-матрицей.
С другой стороны, справедливо Предложение 6.
Предложение 6.
Для существования правильного ормального решения систе-
мы интервальных уравнений (36) (37) достаточно, чтобы в интервальной линейной
системе
Ax = b
матрица
Доказательство.
A
являлась H-матрицей.
Действительно, для H -матрицы
A ? IRnЧn
жит нулей, и потому в представлении (47) диагональная матрица
диагональ не содер-
D
неособенна. Тогда
124
С. П. Шарый
равносильной ормой записи системы (36) (37) является рекуррентный вид (49), который можно представить как
x = G(A, b, x)
G : IRn ? IRn , действующим по правилу x 7? D ?1 (b ? Cx), где
матрица A связана с C и D посредством соотношения (47).
Если A H -матрица, то для нее выполнено условие (51). Следовательно, поскольку
с отображением
Dist G(A, b, x), G(A, b, y) = Dist D ?1 (b ? Cy), D ?1 (b ? Cy) ?
? D?1 · Dist b ? Cx, b ? Cy ? D?1 |C| · Dist (x, y),
рассматриваемое отображение
G является |D?1 | |C|-сжимающим. Требуемое утвержде-
ние вытекает теперь из теоремы Алеельда Херцбергера, ормулировка которой при-
ведена в разделе 6.
С учетом сказанного ситуация с правильностью/неправильностью ормальных решений рассмотренных конкретных систем (38) и (45),(46) получает еще одно, наиболее глубокое, объяснение: матрица системы Хансена (38) является интервальной H матрицей, тогда как в системах (45) и (46) матрицы таковыми уже не являются.
Как приводить ИСЛАУ общего вида к системам с H -матрицами? Для этой цели
служит процедура предобуславливания [3, 7? домножение слева матрицы и правой
?, в силу чего
(?A) x = ?b. Множество
части решаемой ИСЛАУ на специально подобранную точечную матрицу
Ax = b получается интервальная система
?(?A, ?b) предобусловленной системы может сделаться при этом более широким, чем исходное множество решений ?(A, b), но матрица ?A новой системы будет
иметь лучшие свойства сравнительно с A. В частности, если A сильно неособенна, то
?1
при ? = (mid A) , называемом предобуславливанием обратной средней, ?A является
вместо системы
решений
H -матрицей [3, 7?.
9. Качество оценивания
Полученное представление уравнений (36) (37) в рекуррентном виде (49) позволяет
ответить на вопросы о соотношении результата Предложения 3 с другими версиями
ормального подхода к внешнему оцениванию множеств решений, а также о качестве
этого оценивания. Сравнивая уравнение в рекуррентном виде (49), равносильное системе (36) (37), с уравнениями (39) (40) из теорем Апостолатоса Кулиша и Алеельда Херцбергера, можем видеть, что испанская версия ормального подхода,
представленная в Предложении 3, является, по существу, удачно скомпонованной вариацией известного ранее варианта ормально-алгебраического подхода из [19, 21, 26?,
в которую неявно встроена процедура приведения системы к рекуррентному виду.
Оценки близости ормального решения интервальной линейной системы в рекуррентном виде
x = Gx + h
к оптимальной (точной) оценке ее множества решений были
исследованы многими авторами, из которых отметим Д. ея [32? и А. Ноймайера [3?.
Пользуясь методикой, развитой в [3?, покажем, что для ормального решения интервальной системы (36) (37) или равносильной ей системы (49) справедлив следующий
результат.
Об испанской версии ормального подхода к внешнему оцениванию...
Предложение 7.
125
A ? IRnЧn интервальная H-матрица, D, C диагоn
?
нальная и внедиагональная части A соответственно и b ? IR . Если x ормальное
Пусть
решение интервальной линейной системы (36) (37)
S(A, b, x) = Cx + D · dual x ? b = 0,
то справедливо следующее неравенство для расстояния
x?
до интервальной оболочки
?(A, b) множества решений интервальной линейной системы Ax = b:
Dist ?, x? ? 2 (I ? |D?1 C|)?1 |D?1 C| · rad ( ?).
Доказательство.
A = C +D
матрица
(53)
Прежде всего из условия теоремы следует, что в представлении
?1
неособенна и ?(|D C|) < 1. Покажем, что справедливо вклю-
D
чение
x? ? ? + D ?1 C( ? ? x? ).
В правой части этого включения второе слагаемое является произведением трех интервальных матриц (размером
nЧn, nЧn и nЧ1), требующим, вообще говоря, расстановки
скобок из-за неассоциативности интервального матричного умножения. Но так как пер?1
вый из сомножителей диагональная матрица D , делать это необязательно.
?1
?
Ясно, что x = D
b ? Cx? в силу уравнения (49). Заиксируем индекс i ?
{1, 2, . . . , n} и возьмем какое-нибудь значение ? ? x?i . Поскольку результаты интервальных матрично-векторных операций являются интервальными оболочками множеств точечных результатов соответствующих операций, взятых по представителям, то ? =
D? ?1 (b? ? C? x?) i для некоторых C? ? C , D? ? D , x? ? x? и b? ? b. Преобразуем это выраже?1
ние далее, учитывая, что в условиях теоремы из ?(|D C|) < 1 следует обратимость
?1
матриц (I + D? C?) для любых C? ? C и D? ? D :
D? ?1 (b? ? C? x?) = (I + D? ?1 C?)?1 D? ?1 b? ? (I + D? ?1 C?)?1 D? ?1 b? + D? ?1 (b? ? C? x?) =
= (I + D? ?1 C?)?1 D? ?1 b? ? (I + D? ?1 C?)?1 D? ?1 b? + D? ?1 b? ? D? ?1 C? x? =
= (I + D? ?1 C?)?1 D? ?1 b? ? (I + D? ?1 C?)?1 D? ?1 b?+
+(I + D? ?1 C?)(I + D? ?1 C?)?1 D? ?1 b? ? D? ?1 C? x? =
= (I + D? ?1 C?)?1 D? ?1 b? + D? ?1 C?(I + D? ?1 C?)?1 D? ?1 b? ? D? ?1 C? x? =
= (I + D? ?1 C?)?1 D? ?1 b? + D? ?1 C? (I + D? ?1 C?)?1 D? ?1 b? ? x? .
Интервализуя полученное выражение по
C? ? C , D? ? D , x? ? x? , b? ? b
и учитывая
принадлежность
A??1 b? = C? + D?
для любых
A? = C? + D? ? A
и
?1
b? ? b,
b? = (I + D? ?1 C?)?1 D? ?1 b? ? ?
получим включение
D? ?1 (b? ? C? x?) ? ? + D ?1 C( ? ? x? ).
i = 1, 2, . . . , n и для любых ? ? x?i
? ? ? + D ?1 C( ? ? x? ) i ,
Поэтому для любого индекса
т. е. действительно
x? ? ? + D ?1 C( ? ? x? ).
справедливо включение
126
С. П. Шарый
Из полученного включения в силу свойств расстояния
Dist
следует:
Dist ?, x? ? Dist ?, ? + D ?1 C( ? ? x? ) =
= Dist 0, D?1 C( ? ? x? ) = |D?1 C( ? ? x? )| ? |D?1 C| | ? ? x? |.
Но для любых интервальных векторов
u, v
из
IRn
имеет место оценка [3?
|u ? v| ? Dist (u, v) + 2 rad u.
Значит,
Dist ?, x?
и потому
? |D ?1 C| · Dist ( ?, x? ) + 2 rad ( ?) ,
(I ? |D ?1 C|) · Dist ?, x?
Матрица
матрица
? 2 |D?1 C| · rad ( ?).
(54)
(55)
(I ? |D?1 C|) обратима, коль скоро ?(|D?1 C|) < 1, и, кроме того, обратная
(I ? |D?1 C|)?1 неотрицательна, в чем легко убедиться из ее разложения в
матричный ряд Неймана
?1
(I ? |D C|)
?1
=
?
X
|D?1 C|k ,
k=0
в котором все члены неотрицательны. Следовательно, можно домножить обе части
?1
?1
неравенства (55) слева на неотрицательную матрицу (I ? |D C|) , получая доказы-
ваемое неравенство (53).
Следствие.
нормы
Если в условиях Предложения 7 для некоторой абсолютной матричной
k · k величина ? := kD?1 Ck такова,
что
? < 1, то
для согласованной абсолютной
векторной нормы справедливо неравенство
kDist ?, x? k ?
2?
· krad ( ?)k.
1??
(56)
Действительно, при доказательстве Предложения 7 мы установили оценку (54)
Dist ?, x?
? |D?1 C| Dist ( ?, x? ) + 2 rad ( ?) .
Беря норму от обеих частей этого неравенства между неотрицательными векторами и
пользуясь условиями согласования векторных и матричных норм, получим
Dist ?, x? ? kD?1 Ck · Dist ?, x? + 2 rad ( ?) ?
?1
? ? kD Ck ·
Dist ?, x
+ 2 krad ( ?)k ,
откуда имеем
При
I ? kD?1 Ck · Dist ?, x? ? 2 kD?1 Ck·krad ( ?)k.
kD ?1 Ck = ? < 1
это влечет оценку (56).
Оценка (56) означает, что точность испанской версии ормального подхода совершенно такая же, как традиционной, т. е. имеет первый порядок в зависимости от
размеров множества решений. Тот же первый порядок точности внешнего оценивания
Об испанской версии ормального подхода к внешнему оцениванию...
127
множеств решений ИСЛАУ имеют, как известно, большинство быстрых (полиномиально сложных) методов внешнего оценивания множеств решений ИСЛАУ [3, 7?.
В заключение раздела приведем аналог известного результата об оптимальном (наилучшем) оценивании множеств решений ИСЛАУ с M -матрицами.
nЧn
Если A ? IR
интервальная M-матрица, то для любого
n
Предложение 8.
вектора
b ? IR
правильное ормальное решение интервальной линейной системы
(36) (37) существует и совпадает с интервальной оболочкой
решений интервальной линейной системы
Доказательство.
Оно основано на следующем свойстве умножения на неотрица-
тельный правильный интервал: если
a ? IR
ax = a? x,
a?, a? ? a.
для некоторых
Тогда для неотрицательного интервала
_
h
[ax, ax] =
a?a
для каких-то значений
и
a ? 0,
то
ax = a? x
(57)
Действительно,
ax = [ax, ax]
ax =
?(A, b) множества
Ax = b.
для точечного
a?0
a ? 0.
в силу (22) имеем
min (ax), max (ax)
a?a
a?a
i
=
a? x, a? x
a?, a? ? a.
Переходя к доказательству основного результата Предложения 8, заметим, что существование правильного ормального решения для системы (36) (37) вытекает из
Предложения 6. Далее, если
диагональ
D
A интервальная
положительна,
M -матрица, то в представлении (47) ее
?
ормальное решение x
интервальной системы
и
(36) (37) удовлетворяет уравнению (49), т. е.
Следовательно,
x? = D ?1 b ? Cx? = D?1 b + (?C)x? .
x? = D?1 b + (?C)x? =
= D? ?1 b + (?C)x?
в силу (57), поскольку
= D? ?1 b + (?C)x? =
= D? ?1 b + (?C?)x?
D ?1 ? 0, =
снова в силу (57), так как
(?C) ? 0
D? ? D и C? ? C . Это означает, что вектор x? является решением точечной
системы A?x = b с A? = C? + D? ? A и потому принадлежит множеству решений ?(A, b).
?
Аналогичными рассуждениями можно показать, что вектор x также лежит в ?(A, b)
?
?
?
?
и поэтому x = [x , x ] ? ?(A, b). Но, с другой стороны, x ? ?(A, b) по Предложе?
нию 3, значит брус x действительно является наименьшей по включению внешней
оценкой для множества решений ?(A, b).
для каких-то
128
С. П. Шарый
10. Численные примеры
Данный раздел посвящен сравнению испанской версии ормального подхода с другими методами внешнего оценивания множеств решений ИСЛАУ. При этом мы используем термин испанская версия расширительно, для обозначения вычислительной процедуры, основанной на Предложении 3 и использующей для нахождения ормального
решения системы (36) (37) субдиеренциальный метод Ньютона (чего испанские авторы в своих работах [27, 28?, конечно, не рассматривали).
Ее естественными конкурентами, областью применимости которых также служат
интервальные линейные системы с H -матрицам, являются:
процедура Хансена Блика она [4, 40 43?, имеющая трудоемкость
4n3 +O(n2);
интервальный итерационный метод аусса Зейделя [3, 7?, трудоемкость выполO(n2 );
нения одного шага которого составляет
традиционная версия ормального (алгебраического) подхода [19, 21, 26?, в которой каждый шаг субдиеренциального метода Ньютона требует решения точечной
3
системы линейных уравнений и, следовательно, имеет трудоемкость O(n ). В этот список не включен интервальный метод аусса, также имеющий трудоемкость выполнения
O(n3 ),
но характеризующийся невысоким качеством внешних оценок.
Интервальный метод аусса Зейделя является, на первый взгляд, самым быстрым из рассматриваемых, но в действительности количество шагов, которые он может
выполнить до сходимости, в значительной степени зависит от свойств матрицы интервальной системы. Это число невелико для матриц с сильно выраженным диагональным
преобладанием и становится большим или даже очень большим, когда преобладания
почти нет. По этой причине полная трудоемкость интервального итерационного метода
аусса Зейделя является величиной очень непостоянной. В данном смысле процедура
Хансена Блика она и субдиеренциальный метод Ньютона в ормальном подходе (традиционной или испанской версии) демонстрируют гораздо более благоприятное
поведение. Их трудоемкость почти не зависит (или слабо зависит) от свойств решаемой системы, что существенно для многих алгоритмов, в которых задача оценивания
множеств решений ИСЛАУ используется как вспомогательная.
ассмотрим в качестве первого примера систему уравнений
[2, 3] [?1.9, 1]
[1, 2]
[2, 3]
!
[0, 2]
[1, 4]
x=
!
,
(58)
множество решений которой показано на рис. 3. Оптимальная (точная) внешняя интер?
вальная оценка ее множества решений есть брус ([?2, 1.9662], [?1, 4]) .
Матрица системы (58) является H -матрицей, но она весьма близка к границе множества H -матриц. Так, интервальная матрица
[2, 3] [?2, 1]
[1, 2] [2, 3]
отличающаяся от матрицы в (58) на
0.1
!
,
в левой границе элемента на месте
(1, 2),
уже
не является H -матрицей. По этой причине пример (58), будучи пессимистическим,
весьма труден для рассматриваемых методов внешнего оценивания множеств решений
ИСЛАУ. Вместе с тем он хорошо демонстрирует трудности худшего случая, которые
быстро нарастают при увеличении размерности задачи.
Об испанской версии ормального подхода к внешнему оцениванию...
129
4
3.5
3
2.5
2
1.5
1
0.5
0
?0.5
?1
?3
?2
?1
0
1
2
3
ис. 3. Множество решений системы уравнений (58) и его наилучшая внешняя интервальная
оценка
Процедура Хансена Блика она в применении к (58) дает ответ
[?38, 58]
[?10, 60]
!
.
(59)
При использовании традиционной версии ормального подхода согласно [19, 21, 26?
задача сводится к нахождению ормального решения системы
(dev diag A)x = (dev diag A ? A)x + b,
где
diag A
диагональ матрицы
A
(обозначенная через
D
(60)
в представлении (47) и в
последующих выкладках) и
dev x :=
отклонение интервала
x,
x,
x,
если
|x| ? |x|,
иначе, т. е. наиболее удаленная от нуля точка интервала
x.
Искомое
ормальное решение равно
[?23.3846, 25.1154]
[?24.6154, 25.3846]
!
(61)
и находится субдиеренциальным методом Ньютона за одну итерацию. Испанская
версия ормального подхода дает тот же ответ за три итерации, но не требует приведения исходной ИСЛАУ к виду (60).
130
С. П. Шарый
Что касается интервального метода аусса Зейделя, то он сходится к тому же
интервальному вектору (61), но делает это существенно медленнее. Запущенный из
?
начального бруса ([?40, 40], [?40, 40]) , он выдает за 40 итераций ответ
[?25.2629, 27.0925]
[?26.5925, 27.2629]
!
.
На каждой итерации субдиеренциального метода Ньютона нужно решать точеч2n
ную систему линейных уравнений в R , и потому можно считать, что трудоемкость
3
одной его итерации составляет O(n ). Но этих итераций требуется немного. Как правило, их количество не превышает порядка решаемой интервальной системы уравнений,
а в реальности является даже существенно меньшим. Трудоемкость одной итерации
2
интервального метода аусса Зейделя равна O(n ), но в случае плохой матрицы
ИСЛАУ сходимость может потребовать значительного количества итераций. В подобных случаях полные трудозатраты интервального метода аусса Зейделя превышают
трудозатраты субдиеренциального метода Ньютона.
ассмотрим теперь работу перечисленных в начале раздела методов совместно с
предобуславливанием обратной средней матрицей. Это популярная модиикация, которая рекомендуется многими специалистами для постоянного применения, так как
вкупе с традиционными методами внешнего оценивания множеств решений (интервальным методом аусса, итерационными методами и т. п.) она обеспечивает квадратичную
точность внешнего оценивания относительно ширины решаемой интервальной системы
[3, 44?, а не первый порядок, как в (53) и ей аналогичных оценках. Напомним, что предобуславливание обратной средней встроено в известный интервальный итерационный
метод Кравчика [3, 7?.
После предобуславливания исходной системы (58) обратной средней матрицей получаем систему
[0.7870, 1.2130] [?0.5560, 0.5560]
[?0.2889, 0.2889] [0.5054, 1.4946]
!
[0.0649, 0.9820]
[?0.0723, 1.4441]
x=
!
.
В применении к ней процедура Хансена Блика она дает ответ
[?3.2462, 5.4770]
[?1.4352, 5.9869]
!
,
который весьма близок к оптимальным внешним оценкам. Но предобуславливание обратной средней и результат о квадратичной сходимости внешних оценок работают хорошо в случае не слишком широких интервалов в системе уравнений. Если рассматривается ИСЛАУ с широкими и очень широкими интервальными данными в матрице,
то в действие вступают нелинейные эекты, предобуславливание обратной средней
матрицей оказывается не лучшим, и ситуация качественно меняется [7?.
Для иллюстрации этого утверждения рассмотрим в качестве примера систему уравнений
[2, 300] [?1.9, 1]
[1, 2]
[2, 300]
!
x=
[0, 2]
[1, 4]
!
,
(62)
в которой сильно увеличены верхние границы диагональных элементов. Ее множество
решений отличается от множества решений системы (58) весьма незначительно (лишь
Об испанской версии ормального подхода к внешнему оцениванию...
131
нижней границей куска из первого квадранта), а оптимальные (точные) покоординатные оценки множества решений совершенно такие же:
[?2, 1.9662]
[?1, 4]
.
Но после предобуславливания обратной средней процедура Хансена Блика она дает в применении к получившейся системе ответ
[?32.1299, 49.1483]
[?8.5763, 50.9130]
!
очень широкий интервал, что несколько лучше ответа, получаемого с помощью ормального (алгебраического) подхода
[?48.1424, 49.1483]
[?48.4105, 50.9130]
!
,
который и традиционная, и испанская версии получают всего за три итерации. К тому
же пределу сходится из достаточно широкого начального приближения интервальный
итерационный метод аусса Зейделя, но так же медленно, как и в случае исходной
системы без предобуславливания (58).
11. Некоторые итоги и выводы
Испанская версия ормального (алгебраического) подхода к внешнему оцениванию
множеств решений интервальных систем уравнений, сводящая исходную задачу к нахождению правильного ормального решения системы уравнений (36) (37) или (41),
является равносильной версией подхода, развитого ранее в работах [19, 21, 26?, и имеет
ту же серу применимости интервальные линейные системы с H -матрицами.
Имея те же характеристики трудоемкости выполнения, испанская версия несколько более трудна для реализации и использует в среднем немного больше итераций для
сходимости. Однако в отличие от традиционной она не требует специального приведения исходной интервальной системы с специальному рекуррентному виду.
Список литературы
[1? Алеельд ., Херцбергер Ю. Введение в интервальные вычисления. М.: Мир, 1987.
[2? Калмыков С.А., Шокин Ю.И., Юлдашев З.Х. Методы интервального анализа. Новосибирск: Наука, 1986.
[3? Neumaier A. Interval Methods for Systems of Equations. Cambridge Univ. Press, 1990.
[4? Задачи линейной оптимизации с неточными данными / М. Фидлер, Й. Недома, Я. амик,
И. он, К. Циммерманн. М.; Ижевск: Изд-во ХД, 2008.
[5? Shary S.P. Algebrai approah to the interval linear stati identiation, tolerane and ontrol
problems, or One more appliation of Kauher arithmeti // Reliable Comput. 1996. Vol. 2,
No. 1. P. 333.
132
С. П. Шарый
[6? Шарый С.П. Алгебраический подход к анализу линейных статических систем с интервальной неопределенностью // Изв. АН. Теория и системы управления. 1997. ќ 3.
С. 5161.
[7? Шарый С.П. Конечномерный интервальный анализ. Электронная книга, доступная на
http://www.ns.ru/interval/Library/InteBooks/SharyBook.pdf
[8? Shary S.P. A new tehnique in systems analysis under interval unertainty and
ambiguity // Reliable Comput. 2002. Vol. 8, No. 5. P. 321418 (электронная версия
http://www.ns.ru/interval/shary/Papers/ANewTeh.pdf).
[9? Kearfott R.B., Nakao M., Neumaier A. et al. Standardized notation in interval
analysis // Тр. XIII Байкальской междунар. школы-семинара Методы оптимизации и их
приложения. Т. 4. Интервальный анализ. Иркутск: ИСЭМ СО АН, 2005. С. 107113
(электроная версия http://www.ns.ru/interval/INotation.pdf).
[10? Berman A., Plemmons R.J. Nonnegative Matries in the Mathematial Sienes. New York:
Aad. Press, 1979.
[11? Moore R.E., Kearfott R.B., Cloud M.J. Introdution to Interval Analysis. Philadelphia:
SIAM, 2009.
[12? Интервальный анализ и его приложения. Веб-сайт http://www.ns.ru/interval
[13? Бессонов Л.А. Теоретические основы электротехники. Электрические цепи. М.: Высшая школа, 1996.
[14? Манусов В.З., Моисеев С.М., Перков С.Д. Интервальный анализ в линейных задачах электротехники // Инормационно-оперативный материал (интервальный анализ).
Красноярск, 1988. (Препр. ВЦ СО АН ССС. ќ 6. С. 2931.)
[15? Фихтенгольц .М. Курс диеренциального и интегрального исчисления. Т. 1. М.:
Наука, 1966.
[16? Шилов .Е. Математический анализ. Функции одного переменного. Ч. 1, 2. М.: Наука,
1969.
[17? Miranda C. Un' osservatione su un teorema di Brouwer // Bollet. Unione Mat. Ital. Serie II.
1940. Vol. 3. P. 57.
[18? Kauher E. Uber
metrishe und algebraishe Eigenshaften einiger beim numerishen
Rehnen auftretender Raume. Dr. Naturwissen. Dissertation. Univ. Karlsruhe, 1973.
[19? Шарый С.П. Алгебраический подход во внешней задаче для интервальных линейных
систем // Вычисл. технологии. 1998. Т. 3, ќ 2. С. 67114.
[20? Kauher E. Interval analysis in the extended interval spae IR // Fundamentals of Numerial
Computation (Computer-oriented numerial analysis) / Еds. G. Alefeld, R.D. Grigorie.
Comput. Suppl. 2. Wien: Springer, 1980. P. 3349.
[21? Shary S.P. Algebrai approah in the outer problem for interval linear equations // Reliable
Comput. 1997. Vol. 3, No. 2. P. 103135.
[22? Gardenes
E., Trepat A. Fundamentals of SIGLA, an interval omputing system over the
ompleted set of intervals // Computing. 1980. Vol. 24. P. 161179
[23? Gardenes
E., Trepat A., Mielgo H. Present perspetive of the SIGLA interval system //
Freiburger Intervall-Berihte. 1982. No. 82/9. P. 165.
[24? Клейн Ф. Лекции об икосаэдре и решении уравнений пятой степени. М.: Наука, 1989.
[25? Hansen E. On linear algebrai equations with interval oeients // Topis in Interval
Analysis / Ed. E. Hansen. Oxford: Clarendon Press, 1969. P. 3546.
Об испанской версии ормального подхода к внешнему оцениванию...
133
[26? Шарый С.П. Алгебраический подход во внешней задаче для интервальных линейных
систем // Фундамент. и прикл. математика. 2002. Т. 8, ќ 2. C. 567610 (электронная
версия http://www.ns.ru/interval/shary/Papers/FunPriMath.pdf).
[27? Sainz M.A., Gardenes
E., Jorba L. Formal solution to systems of interval linear or nonlinear equations // Reliable Comput. 2002. Vol. 8. P. 189211.
[28? Sainz M.A., Gardenes
E., Jorba L. Interval estimations of solution sets to real-valued
systems of linear or non-linear equations // Reliable Comput. 2002. Vol. 8. P. 283305.
[29? Apostolatos N., Kulish U. Grundz
uge einer Intervallrehnung f
ur Matrizen und einige
Anwendungen // Eletron. Rehenanl. 1968. Bd 10. S. 7383.
[30? Mayer O. Uber
die in der Intervallrehnung auftretenden R
aume und einige Anwendungen.
PhD Dissertation. Univ. Karlsruhe, 1968.
[31? Шарый С.П. О сравнении теорем Апостолатоса Кулиша и Майера Варнке в интервальном анализе // Сиб. журн. вычисл. математики. 2009. Т. 12, ќ 3. С. 351359.
[32? Gay D.M. Solving interval linear equations // SIAM J. Numer. Anal. 1982. Vol. 19, No. 4.
P. 858870.
[33? Акилов .П., Кутателадзе С.С. Упорядоченные векторные пространства. Новосибирск: Наука, 1978.
[34? Обэн Ж.-П. Нелинейный анализ и его экономические приложения. М.: Мир, 1988.
[35? окаеллар . Выпуклый анализ. М.: Мир, 1973.
[36? Neumaier A. On Shary's algebrai approah for linear interval equations // SIAM J. Matrix
Analysis and Appl. 2000. Vol. 21. P. 11561162.
[37? Хорн ., Джонсон Ч. Матричный анализ. М.: Мир, 1989.
[38? антмахер Ф.. Теория матриц. М.: Наука, 1988.
[39? Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.
[40? Bliek C. Computer Methods for Design Automation. PhD Thesis. Cambridge: Massahusetts
Institute of Tehnology, MA, July 1992.
[41? Hansen E.R. Bounding the solution of interval linear equations // SIAM J. Numer. Anal.
1992. Vol. 29, No. 5. P. 14931503.
[42? Rohn J. Cheap and tight bounds: The reent result by E. Hansen an be made more eient //
Interval Comput. 1993. No. 4. P. 1321.
[43? Neumaier A. A simple derivation of Hansen Bliek Rohn Ning Kearfott enlosure for
linear interval equations // Reliable Comput. 1999. Vol. 5, No. 2. P. 131136.
[44? Miller W. On an interval-arithmeti matrix method // BIT. 1972. Vol. 12. P. 213219.
Поступила в редакцию 26 июля 2010 г.,
с доработки 29 ноября 2010 г.
?йдем другим путем и воспользуемся техникой погружения интервального пространства в евклидово пространство двойной размерности [7, 8, 19?. Ее назначение соn
стоит в том, чтобы перейти из нелинейного интервального пространства KR в линейное пространство, только в котором и применимы многие математические концепции,
составляющие основу современных вычислительных методов (в частности, диеренцирование и выпуклость). Этот переход может быть осуществлен с помощью любого
n
2n
взаимно-однозначного отображения KR ? R
так называемого погружения, и его
конкретный выбор обычно диктуется соображениями удобства и наиболее аккуратного сохранения свойств рассматриваемых объектов при переходе в новое пространство.
n
2n
так, чтобы оно являлось
В частности, имеет смысл задавать погружение KR ? R
n
2n
изоморизмом аддитивных групп пространств KR и R .
n
2n
Отображение sti : KR ? R , задаваемое правилом
sti ( x1 , x2 , . . . , xn )? = (?x1 , ?x2 , . . . , ?xn , x1 , x2 , . . . , xn )? ,
n
называют стандартным погружением интервального пространства KR в линейное
2n
пространство R
[7, 19, 26?. Оно особенно удобно потому, что частичный порядок по
n
включению в KR переводится им в покомпонентный порядок на линейном простран2n
стве R . Иными словами,
x?y
где для
u, v ? R2n
в
KRn
неравенство
?
u ? v
sti (x) ? sti (y)
понимается как
в
R2n ,
ui ? vi , i = 1, 2, . . . , 2n.
Легко
также убедиться в том, что
sti (µx + ?y) = µ sti (x) + ? sti (y).
n
Интересующему нас отображению S : KR ?
2n
ставляет такое отображение S : R
? R2n , что
KRn
S = sti ? S ? sti ?1 ,
стандартное погружение сопо-
(42)
118
С. П. Шарый
которое будем называть индуцированным. Наиболее важное практическое следствие погружения состоит в том, что нахождение ормального решения уравнения (36) (37)
n
в KR может быть заменено на решение индуцированного уравнения S(x) = 0 в при2n
вычном евклидовом пространстве R .
Индуцированное отображение
b
S,
очевидно, непрерывно по
x
и по параметрам
A
и
в силу непрерывности стандартного погружения sti, операции дуализации и интер-
вальных ариметических операций сложения, вычитания и умножения в
KR.
Напомним следующее определение.
Определение
[33 35?. Пусть евклидово пространство
p
q
порядком 4. Отображение
F : R ? R
Rq
упорядочено частичным
называется порядково выпуклым относи-
тельно 4, если
F (?u + (1 ? ?)v) 4 ?F (u) + (1 ? ?)F (v)
для любых
u, v ? Rp
и
? ? [0, 1].
Наиболее важное свойство индуцированного отображения
nЧn
R
Предложение 4.
2n
Если
A ? IR
S
дает Предложение 4.
2n
, то индуцированное отображение
, определенное посредством (42), является порядково выпуклым в
R
2n
S : R
?
относитель-
но покомпонентного упорядочения векторов ?.
Доказательство.
? ? [0, 1]
Пусть
x? , x?? ? KRn .
Тогда для всякого
i = 1, 2, . . . , n
и любого
в силу (26) и субдистрибутивности умножения по сложению (11) справедлива
следующая цепочка преобразований:
Si ?x? + (1 ? ?)x?? =
X
= aii dual ?x?i + (1 ? ?)x??i +
aij ?x?i + (1 ? ?)x??i ? bi ?
j6=i
= ? aii dual x?i + (1 ? ?) aii dual x??i +
X
j6=i
=?
aii dual x?i
+
X
aij x?i
? bi
j6=i
X
??
??
+ (1 ? ?) aii dual xi +
aij xi ? bi =
j6=i
= ? Si (x? ) + (1 ? ?) Si (x?? ).
Следовательно, по определению порядка ? на
Si ?x? + (1 ? ?)x??
Si ?x? + (1 ? ?)x??
Если векторы
x? , x?? ? R2n
?aij x?i + (1 ? ?)aij x??i ? bi =
KR
? ? Si (x? ) + (1 ? ?) Si (x?? ),
(43)
? ? Si (x? ) + (1 ? ?) Si (x?? ).
(44)
таковы, что
x? = sti (x? )
и
x?? = sti (x?? ),
sti ?1 (x? ) = x?
и
sti ?1 (x?? ) = x?? ,
то
и поэтому
S ?x? + (1 ? ?)x?? = sti S ?x? + (1 ? ?)x?? .
Об испанской версии ормального подхода к внешнему оцениванию...
119
Привлекая определение стандартного погружения, с учетом (43) (44) получим соотношения
Si ?x? + (1 ? ?)x?? = ? Si ?x? + (1 ? ?)x?? ? ?? Si (x? ) ? (1 ? ?) Si (x?? ) =
= ? Si (x? ) + (1 ? ?) Si (x?? ) при 1 ? i ? n,
Si ?x? + (1 ? ?)x?? = Si ?x? + (1 ? ?)x?? ? ? Si (x? ) + (1 ? ?) Si (x?? ) =
= ? Si (x? ) + (1 ? ?) Si (x?? )
при
n + 1 ? i ? 2n.
Это и требовалось доказать.
Порядковая выпуклость индуцированного отображения S влечет существование его
2n
субдиеренциала ?S всюду в R
[33?. Можно показать и большее: S является полиэдральным отображением, т. е. таким, что его граик склеен из кусков гиперплоскостей. Следовательно, для нахождения решений индуцированного уравнения S(x) = 0
R2n имеет смысл применить субдиеренциальный метод Ньютона, развитый ра-
в
нее для задач подобного сорта и успешно зарекомендовавший себя (см., в частности,
[7, 19, 21, 36?):
Субдиеренциальный метод Ньютона
для решения уравнения (36) (37)
Выбираем некоторое начальное приближение x(0) ? R2n .
Если (k ? 1)-е приближение x(k?1) ? R2n , k = 1, 2, . . . , уже найдено,
то вычисляем какой-нибудь субградиент D (k?1) отображения S в точке
x(k?1) и полагаем
?1
x(k) := x(k?1) ? ? D (k?1)
S( x(k?1) ),
где ? ? ]0, 1] некоторая константа.
Нетривиальным моментом реализации субдиренциального метода Ньютона является выбор начального приближения. Вычислительные эксперименты показывают,
что он сходится из любого начального приближения, но количество итераций до сходимости при этом возрастает. Эмпирическим путем было установлено [19, 21?, что для
алгоритма, вычисляющего ормальное решение уравнения в рекуррентном виде (40),
наиболее выгодный выбор начального приближения это решение средней системы
уравнений
(mid A) x = mid b.
еализация и численные эксперименты (см. раздел 10) показывают, что в рассматриваемом случае субдиеренциальный метод Ньютона работает хорошо, причем при
? = 1
он в большинстве случаев находит ормальные решения уравнения (36) (37)
за небольшое конечное число итераций. В частности, метод по своей эективности
качественно превосходит стационарные итерационные методы типа Якоби, предложенные для решения аналогичной задачи в [27?. К примеру, для системы Хансена (38)
точное ормальное решение уравнения (36) (37) вычисляется субдиеренциальным
методом Ньютона всего за три итерации.
120
С. П. Шарый
8. Условия существования правильного ормального решения
К сожалению, даже когда множество решений ИСЛАУ непусто, ормальное решение
уравнения (36) (37) часто не существует или не является правильным. В последнем
случае оно не может быть проинтерпретировано согласно Предложению 3. Например,
для интервальной линейной системы
[1, 2] [2, 3]
[2, 3] [0, 1]
x=
[60, 240]
[0, 120]
,
(45)
которая получена перестановкой местами уравнений в системе Хансена (38) и имеет то
же самое множество решений (см. рис. 2), ормальным решением вспомогательной си?
стемы (36) (37) является неправильный интервальный вектор ([90, ?120], [240, ?60])
(субдиеренциальный метод Ньютона успешно находит его за четыре итерации). Исследуем это затруднение более тщательно.
Прежде всего отметим, что если какой-нибудь из диагональных элементов матрицы
A содержит
нуль, то ормальное решение уравнения (36) (37) не может быть пра-
вильным. Покажем, что в этом случае соответствующие выражения (36) будут правильными интервалами, которые не могут включаться в нуль.
?
Пусть x искомое ормальное решение. Воспользуемся представлением (34):
aii · dual x?i +
X
aij x?j ? bi
=
_
aii · dual x?i +
aij ?aij bi ?bi
j=1,...,n
j6=i
i = 1, 2, . . . , n.
_
Если какой-либо из
aii
X
!
aij X j ? bi ,
j6=i
является нульсодержащим интервалом, то соот-
ветствующее ему выражение в правой части выписанного равенства содержит
_
_
0 · dual x?i +
aij ?aij bi ?bi
j6=i
X
aij x?j ? bi
j6=i
!
=
X
aij x?j ? bi ,
j6=i
т. е. правильный интервал, который может быть равен нулю (имеющему нулевой радиус) в уравнении (37) лишь в исключительных случаях, когда равны нулю радиусы
P
суммы
aij x?j и компоненты правой части bi . Не будем выписывать строгую ормуj6=i
лировку этих условий, так как они неизбежно должны носить апостериорный харак?
тер, т. е. использовать знание вычисленного ормального решения x , что неизбежно снижает их практическую ценность. Впредь условимся (не вполне строго) считать,
что отсутствие нульсодержащих диагональных элементов в матрице исходной системы
(1) (2) является необходимым условием существования правильных ормальных решений системы (36) (37).
Итак, еномен системы (45) получает следующее объяснение: в исходной интервальной системе Хансена (38) диагональные элементы не содержат нулей, а система
(45) этим свойством уже не обладает.
Но отсутствие нульсодержащих элементов по диагонали матрицы ИСЛАУ не является достаточным условием правильности ормальных решений вспомогательных
систем (36) (37), и рассматриваемый вопрос требует дальнейшего исследования. ассмотрим в качестве примера интервальную линейную систему
[1, 2] [2, 3]
[2, 3]
1
x=
[60, 240]
[0, 120]
,
(46)
Об испанской версии ормального подхода к внешнему оцениванию...
которая получена из (45) заменой нульсодержащего элемента
[0, 1]
на
1
на месте
121
(2, 2).
Для нее ормальным решением вспомогательной системы (36) (37) является тот же
?
неправильный интервальный вектор ([90, ?120], [240, ?60]) .
Для целей дальнейшего анализа представим матрицу интервальной линейной системы уравнений
Ax = b
в виде суммы диагональной и внедиагональной частей, т. е.
как
A = C + D,
C
где
=
(cij )
(47)
матрица, в которой диагональ нулевая,
диагональные элементы совпадают с соответствующими
cij = aij
при всех
i 6= j ; D
=
diag {d1 , d2 , . . . , dn }
cii = 0, i = 1, 2, . . . , n, а внеэлементами матрицы A, т. е.
диагональная интервальная матри-
ца, элементы которой равны соответствующим диагональным элементам матрицы
т. е.
S
di = aii , i = 1, 2, . . . , n.
A,
Тогда введенный в Предложении 3 интервальный оператор
может быть записан как
S(x) = Cx + D·dual x ? b,
а уравнение (36) (37) примет вид
Cx + D·dual x ? b = 0.
В силу сказанного выше будем всюду далее предполагать, что
i = 1, 2, . . . , n.
?
Пусть x D неособенна, т. е. 0 6? di ,
ормальное решение этой интервальной системы уравнений, так что
Cx? + D·dual x? ? b = 0.
?
Добавим к обеим частям данного равенства по величине opp (D·dual x ), алгебраически
?
противоположной к D · dual x (что равносильно переносу этого члена с противоположным знаком в другую часть равенства). В результате получим
opp (D·dual x? ) = Cx? ? b,
откуда, умножая обе части на
?1
и учитывая, что
?opp (·) = dual (·),
будем иметь
dual (D·dual x? ) = b ? Cx? .
Наконец, опираясь на (26), приходим к соотношению
(dual D)·x? = b ? Cx? .
(48)
A не содержат нулей, то для (dual D)
inv (dual D), т. е. такая, что ее произве?1
Коль скоро inv dual (·) = (·) , то эта ал-
Если диагональные элементы в матрице
существует алгебраически обратная матрица
дение на
dual D
дает единичную матрицу.
гебраически обратная матрица совпадает с обычной обратной интервальной матрицей
D ?1 = diag{1/d1 , 1/d2 , . . . , 1/dn },
и потому, домножая на нее обе части равенства (48),
приходим к следующей равносильной орме записи уравнения (36) (37):
x = D?1 (b ? Cx).
(49)
Системы уравнений подобного вида, в которых неизвестная переменная выделена в одной из частей в чистом виде, называются системами уравнений в рекуррентном виде
122
С. П. Шарый
(про операторные уравнения в аналогичной орме говорят, что они являются уравнениями второго рода). Именно такой вид имеют интервальные системы уравнений в теоремах Апостолатоса Кулиша и Алеельда Херцбергера, на которые опиралась традиционная версия ормального подхода к внешнему оцениванию множеств решений.
?
В случае, когда x есть правильное ормальное решение интервальной системы
уравнений в рекуррентном виде (49), беря радиус от обеих частей равенства
x? = D ?1 b ? Cx? ,
получим
Но
rad (U V ) ? |U | · rad V
rad x? = rad D?1 b ? Cx? .
для любых правильных интервальных матриц
U
и
V
согла-
сованных размеров, для которых имеет смысл их произведение (см. [1, 3, 7?). Поэтому
rad D?1 b ? Cx? ? |D ?1 | · rad b ? Cx? = |D?1 | · rad b + rad (Cx? ) .
Если все компоненты вектора свободных членов
rad b > 0,
b
имеют ненулевую ширину, т. е.
то справедливо неравенство
rad x? > |D?1 | · rad Cx? ? |D?1 | |C| · rad x? .
Оно означает, в частности, что
имеет при
rad x? > 0.
(50)
Иными словами, если уравнение (36) (37)
rad b > 0 правильное ормальное решение, то это решение
Rn , все компоненты которого имеют ненулевую ширину.
является телес-
ным брусом в
Напомним теперь следующий акт из теории неотрицательных матриц. Если
неотрицательная
n Ч n-матрица, ?(A)
ее спектральный радиус и
?
A
положительное
вещественное число, то
?(A) < ? ??
?(A) ? ? ??
?v ? Rn v > 0 & Av < ?v ,
?v ? Rn v > 0 & Av ? ?v .
Доказательство может быть найдено, например, в книге . Хорна и Ч. Джонсона [37?
либо в англоязычных источниках [3, 10?. С другой стороны, неявным образом этот
акт обосновывается в доказательстве Х. Виландта теоремы Перрона Фробениуса о
неотрицательных матрицах, которое воспроизводится во многих пособиях по теории
матриц, например, в классической работе Ф. антмахера [38?.
?
В рассматриваемом случае для положительного вектора y = rad x и для неотрица?1
?1
тельной матрицы |D | |C| имеет место |D | |C| y < y . Следовательно, в силу выше?1
отмеченных свойств неотрицательных матриц спектральный радиус матрицы |D | |C|
должен быть строго меньше
1:
? |D?1 | |C| < 1.
(51)
Это необходимое условие существования правильного ормального решения систем
rad b > 0 и
поскольку D
не содержащих нуля диагональных элементах в A.
?1
?1
Отметим, что
диагональная матрица, то |D | |C| = |D C|, и
?1
выведенное условие равносильно ? |D C| < 1.
(49) и (36) (37) при
Полученным результатам можно придать несколько другую орму, для чего нам
понадобятся следующие определения.
Об испанской версии ормального подхода к внешнему оцениванию...
Определение
123
n Ч n-матрица A называется M-матрицей, если
A = sI ? P , где s ? R, P неотрицательная матрица и
[10, 39?. Точечная
она представима в виде
s > ?(P ).
Определение
[3, 7?. Интервальную
n Ч n-матрицу A ? IRnЧn
станем называть
интервальной M-матрицей, если M-матрицами являются все содержащиеся в ней
точечные матрицы.
Определение
A ? RnЧn называется H-матрицей, если ее компаnЧn
рант является M-матрицей. Матрица A ? IR
называется интервальной H-матрицей, если каждая вещественная матрица A ? A является H-матрицей.
[3, 7?. Матрица
Ясно, что у M -матрицы внедиагональные элементы неположительны. Нетрудно также показать, что диагональные элементы M -матрицы обязаны быть положительными.
Вообще M -матрицы относительно просто описываемый подкласс всех положительно
обратимых матриц, т. е. матриц, имеющих неотрицательную обратную матрицу [39?.
H -матрицы это специальный класс матриц, у которых диагональ доминирует над
остальной, внедиагональной, частью матрицы в спектральном смысле [3, 7, 10?. Класс
H -матриц включает в себя в качестве собственного подмножества все матрицы, удовлетворяющие традиционному условию диагонального преобладания, но не исчерпывается ими. Другой пример H -матриц неособенные треугольные матрицы, верхние или
нижние [3?. Для H -матриц удается сохранить многие хорошие свойства M -матриц, в
частности, оценку на обратную матрицу.
Для любого интервала
x ? IR
такого, что
0 6? x,
справедливо
1
= hxi?1 ,
x
D имеет место
?1 D = hDi?1 .
в силу чего для диагональной матрицы
соотношение
?1
(50) это позволяет сделать вывод о том, что hDi
|C| y < y для
?
n
?1
положительного вектора y = rad x ? R . В силу неотрицательности hDi
обе части
При
rad b > 0 с учетом
полученного неравенства можем домножить на эту матрицу, прийдя к
В выражении
hDi ? |C| y > 0.
носильно
вектора
hDi ? |C| нетрудно
hAiy > 0 для какого-то
(52)
увидеть компарант матрицы
y > 0,
hDiy > |C| y , т. е.
A,
поэтому (52) рав-
что является одним из признаков
H -матриц (см. подробности, к примеру, в [3, 7?). Мы обосновали Предложение 5.
Предложение 5.
ные элементы
A
Если в интервальной линейной системе
Ax = b
диагональ-
не содержат нулей и все компоненты правой части имеют нену-
левую ширину, т. е.
rad b > 0,
то для существования правильного ормального ре-
шения системы интервальных уравнений (36) (37) необходимо, чтобы
A
являлась
H-матрицей.
С другой стороны, справедливо Предложение 6.
Предложение 6.
Для существования правильного ормального решения систе-
мы интервальных уравнений (36) (37) достаточно, чтобы в интервальной линейной
системе
Ax = b
матрица
Доказательство.
A
являлась H-матрицей.
Действительно, для H -матрицы
A ? IRnЧn
жит нулей, и потому в представлении (47) диагональная матрица
диагональ не содер-
D
неособенна. Тогда
124
С. П. Шарый
равносильной ормой записи системы (36) (37) является рекуррентный вид (49), который можно представить как
x = G(A, b, x)
G : IRn ? IRn , действующим по правилу x 7? D ?1 (b ? Cx), где
матрица A связана с C и D посредством соотношения (47).
Если A H -матрица, то для нее выполнено условие (51). Следовательно, поскольку
с отображением
Dist G(A, b, x), G(A, b, y) = Dist D ?1 (b ? Cy), D ?1 (b ? Cy) ?
? D?1 · Dist b ? Cx, b ? Cy ? D?1 |C| · Dist (x, y),
рассматриваемое отображение
G является |D?1 | |C|-сжимающим. Требуемое утвержде-
ние вытекает теперь из теоремы Алеельда Херцбергера, ормулировка которой при-
ведена в разделе 6.
С учетом сказанного ситуация с правильностью/неправильностью ормальных решений рассмотренных конкретных систем (38) и (45),(46) получает еще одно, наиболее глубокое, объяснение: матрица системы Хансена (38) является интервальной H матрицей, тогда как в системах (45) и (46) матрицы таковыми уже не являются.
Как приводить ИСЛАУ общего вида к системам с H -матрицами? Для этой цели
служит процедура предобуславливания [3, 7? домножение слева матрицы и правой
?, в силу чего
(?A) x = ?b. Множество
части решаемой ИСЛАУ на специально подобранную точечную матрицу
Ax = b получается интервальная система
?(?A, ?b) предобусловленной системы может сделаться при этом более широким, чем исходное множество решений ?(A, b), но матрица ?A новой системы будет
иметь лучшие свойства сравнительно с A. В частности, если A сильно неособенна, то
?1
при ? = (mid A) , называемом предобуславливанием обратной средней, ?A является
вместо системы
решений
H -матрицей [3, 7?.
9. Качество оценивания
Полученное представление уравнений (36) (37) в рекуррентном виде (49) позволяет
ответить на вопросы о соотношении результата Предложения 3 с другими версиями
ормального подхода к внешнему оцениванию множеств решений, а также о качестве
этого оценивания. Сравнивая уравнение в рекуррентном виде (49), равносильное системе (36) (37), с уравнениями (39) (40) из теорем Апостолатоса Кулиша и Алеельда Херцбергера, можем видеть, что испанская версия ормального подхода,
представленная в Предложении 3, является, по существу, удачно скомпонованной вариацией известного ранее варианта ормально-алгебраического подхода из [19, 21, 26?,
в которую неявно встроена процедура приведения системы к рекуррентному виду.
Оценки близости ормального решения интервальной линейной системы в рекуррентном виде
x = Gx + h
к оптимальной (точной) оценке ее множества решений были
исследованы многими авторами, из которых отметим Д. ея [32? и А. Ноймайера [3?.
Пользуясь методикой, развитой в [3?, покажем, что для ормального решения интервальной системы (36) (37) или равносильной ей системы (49) справедлив следующий
результат.
Об испанской версии ормального подхода к внешнему оцениванию...
Предложение 7.
125
A ? IRnЧn интервальная H-матрица, D, C диагоn
?
нальная и внедиагональная части A соответственно и b ? IR . Если x ормальное
Пусть
решение интервальной линейной системы (36) (37)
S(A, b, x) = Cx + D · dual x ? b = 0,
то справедливо следующее неравенство для расстояния
x?
до интервальной оболочки
?(A, b) множества решений интервальной линейной системы Ax = b:
Dist ?, x? ? 2 (I ? |D?1 C|)?1 |D?1 C| · rad ( ?).
Доказательство.
A = C +D
матрица
(53)
Прежде всего из условия теоремы следует, что в представлении
?1
неособенна и ?(|D C|) < 1. Покажем, что справедливо вклю-
D
чение
x? ? ? + D ?1 C( ? ? x? ).
В правой части этого включения второе слагаемое является произведением трех интервальных матриц (размером
nЧn, nЧn и nЧ1), требующим, вообще говоря, расстановки
скобок из-за неассоциативности интервального матричного умножения. Но так как пер?1
вый из сомножителей диагональная матрица D , делать это необязательно.
?1
?
Ясно, что x = D
b ? Cx? в силу уравнения (49). Заиксируем индекс i ?
{1, 2, . . . , n} и возьмем какое-нибудь значение ? ? x?i . Поскольку результаты интервальных матрично-векторных операций являются интервальными оболочками множеств точечных результатов соответствующих операций, взятых по представителям, то ? =
D? ?1 (b? ? C? x?) i для некоторых C? ? C , D? ? D , x? ? x? и b? ? b. Преобразуем это выраже?1
ние далее, учитывая, что в условиях теоремы из ?(|D C|) < 1 следует обратимость
?1
матриц (I + D? C?) для любых C? ? C и D? ? D :
D? ?1 (b? ? C? x?) = (I + D? ?1 C?)?1 D? ?1 b? ? (I + D? ?1 C?)?1 D? ?1 b? + D? ?1 (b? ? C? x?) =
= (I + D? ?1 C?)?1 D? ?1 b? ? (I + D? ?1 C?)?1 D? ?1 b? + D? ?1 b? ? D? ?1 C? x? =
= (I + D? ?1 C?)?1 D? ?1 b? ? (I + D? ?1 C?)?1 D? ?1 b?+
+(I + D? ?1 C?)(I + D? ?1 C?)?1 D? ?1 b? ? D? ?1 C? x? =
= (I + D? ?1 C?)?1 D? ?1 b? + D? ?1 C?(I + D? ?1 C?)?1 D? ?1 b? ? D? ?1 C? x? =
= (I + D? ?1 C?)?1 D? ?1 b? + D? ?1 C? (I + D? ?1 C?)?1 D? ?1 b? ? x? .
Интервализуя полученное выражение по
C? ? C , D? ? D , x? ? x? , b? ? b
и учитывая
принадлежность
A??1 b? = C? + D?
для любых
A? = C? + D? ? A
и
?1
b? ? b,
b? = (I + D? ?1 C?)?1 D? ?1 b? ? ?
получим включение
D? ?1 (b? ? C? x?) ? ? + D ?1 C( ? ? x? ).
i = 1, 2, . . . , n и для любых ? ? x?i
? ? ? + D ?1 C( ? ? x? ) i ,
Поэтому для любого индекса
т. е. действительно
x? ? ? + D ?1 C( ? ? x? ).
справедливо включение
126
С. П. Шарый
Из полученного включения в силу свойств расстояния
Dist
следует:
Dist ?, x? ? Dist ?, ? + D ?1 C( ? ? x? ) =
= Dist 0, D?1 C( ? ? x? ) = |D?1 C( ? ? x? )| ? |D?1 C| | ? ? x? |.
Но для любых интервальных векторов
u, v
из
IRn
имеет место оценка [3?
|u ? v| ? Dist (u, v) + 2 rad u.
Значит,
Dist ?, x?
и потому
? |D ?1 C| · Dist ( ?, x? ) + 2 rad ( ?) ,
(I ? |D ?1 C|) · Dist ?, x?
Матрица
матрица
? 2 |D?1 C| · rad ( ?).
(54)
(55)
(I ? |D?1 C|) обратима, коль скоро ?(|D?1 C|) < 1, и, кроме того, обратная
(I ? |D?1 C|)?1 неотрицательна, в чем легко убедиться из ее разложения в
матричный ряд Неймана
?1
(I ? |D C|)
?1
=
?
X
|D?1 C|k ,
k=0
в котором все члены неотрицательны. Следовательно, можно домножить обе части
?1
?1
неравенства (55) слева на неотрицательную матрицу (I ? |D C|) , получая доказы-
ваемое неравенство (53).
Следствие.
нормы
Если в условиях Предложения 7 для некоторой абсолютной матричной
k · k величина ? := kD?1 Ck такова,
что
? < 1, то
для согласованной абсолютной
векторной нормы справедливо неравенство
kDist ?, x? k ?
2?
· krad ( ?)k.
1??
(56)
Действительно, при доказательстве Предложения 7 мы установили оценку (54)
Dist ?, x?
? |D?1 C| Dist ( ?, x? ) + 2 rad ( ?) .
Беря норму от обеих частей этого неравенства между неотрицательными векторами и
пользуясь условиями согласования векторных и матричных норм, получим
Dist ?, x? ? kD?1 Ck · Dist ?, x? + 2 rad ( ?) ?
?1
? ? kD Ck ·
Dist ?, x
+ 2 krad ( ?)k ,
откуда имеем
При
I ? kD?1 Ck · Dist ?, x? ? 2 kD?1 Ck·krad ( ?)k.
kD ?1 Ck = ? < 1
это влечет оценку (56).
Оценка (56) означает, что точность испанской версии ормального подхода совершенно такая же, как традиционной, т. е. имеет первый порядок в зависимости от
размеров множества решений. Тот же первый порядок точности внешнего оценивания
Об испанской версии ормального подхода к внешнему оцениванию...
127
множеств решений ИСЛАУ имеют, как известно, большинство быстрых (полиномиально сложных) методов внешнего оценивания множеств решений ИСЛАУ [3, 7?.
В заключение раздела приведем аналог известного результата об оптимальном (наилучшем) оценивании множеств решений ИСЛАУ с M -матрицами.
nЧn
Если A ? IR
интервальная M-матрица, то для любого
n
Предложение 8.
вектора
b ? IR
правильное ормальное решение интервальной линейной системы
(36) (37) существует и совпадает с интервальной оболочкой
решений интервальной линейной системы
Доказательство.
Оно основано на следующем свойстве умножения на неотрица-
тельный правильный интервал: если
a ? IR
ax = a? x,
a?, a? ? a.
для некоторых
Тогда для неотрицательного интервала
_
h
[ax, ax] =
a?a
для каких-то значений
и
a ? 0,
то
ax = a? x
(57)
Действительно,
ax = [ax, ax]
ax =
?(A, b) множества
Ax = b.
для точечного
a?0
a ? 0.
в силу (22) имеем
min (ax), max (ax)
a?a
a?a
i
=
a? x, a? x
a?, a? ? a.
Переходя к доказательству основного результата Предложения 8, заметим, что существование правильного ормального решения для системы (36) (37) вытекает из
Предложения 6. Далее, если
диагональ
D
A интервальная
положительна,
M -матрица, то в представлении (47) ее
?
ормальное решение x
интервальной системы
и
(36) (37) удовлетворяет уравнению (49), т. е.
Следовательно,
x? = D ?1 b ? Cx? = D?1 b + (?C)x? .
x? = D?1 b + (?C)x? =
= D? ?1 b + (?C)x?
в силу (57), поскольку
= D? ?1 b + (?C)x? =
= D? ?1 b + (?C?)x?
D ?1 ? 0, =
снова в силу (57), так как
(?C) ? 0
D? ? D и C? ? C . Это означает, что вектор x? является решением точечной
системы A?x = b с A? = C? + D? ? A и потому принадлежит множеству решений ?(A, b).
?
Аналогичными рассуждениями можно показать, что вектор x также лежит в ?(A, b)
?
?
?
?
и поэтому x = [x , x ] ? ?(A, b). Но, с другой стороны, x ? ?(A, b) по Предложе?
нию 3, значит брус x действительно является наименьшей по включению внешней
оценкой для множества решений ?(A, b).
для каких-то
128
С. П. Шарый
10. Численные примеры
Данный раздел посвящен сравнению испанской версии ормального подхода с другими методами внешнего оценивания множеств решений ИСЛАУ. При этом мы используем термин испанская версия расширительно, для обозначения вычислительной процедуры, основанной на Предложении 3 и использующей для нахождения ормального
решения системы (36) (37) субдиеренциальный метод Ньютона (чего испанские авторы в своих работах [27, 28?, конечно, не рассматривали).
Ее естественными конкурентами, областью применимости которых также служат
интервальные линейные системы с H -матрицам, являются:
процедура Хансена Блика она [4, 40 43?, имеющая трудоемкость
4n3 +O(n2);
интервальный итерационный метод аусса Зейделя [3, 7?, трудоемкость выполO(n2 );
нения одного шага которого составляет
традиционная версия ормального (алгебраического) подхода [19, 21, 26?, в которой каждый шаг субдиеренциального метода Ньютона требует решения точечной
3
системы линейных уравнений и, следовательно, имеет трудоемкость O(n ). В этот список не включен интервальный метод аусса, также имеющий трудоемкость выполнения
O(n3 ),
но характеризующийся невысоким качеством внешних оценок.
Интервальный метод аусса Зейделя является, на первый взгляд, самым быстрым из рассматриваемых, но в действительности количество шагов, которые он может
выполнить до сходимости, в значительной степени зависит от свойств матрицы интервальной системы. Это число невелико для матриц с сильно выраженным диагональным
преобладанием и становится большим или даже очень большим, когда преобладания
почти нет. По этой причине полная трудоемкость интервального итерационного метода
аусса Зейделя является величиной очень непостоянной. В данном смысле процедура
Хансена Блика она и субдиеренциальный метод Ньютона в ормальном подходе (традиционной или испанской версии) демонстрируют гораздо более благоприятное
поведение. Их трудоемкость почти не зависит (или слабо зависит) от свойств решаемой системы, что существенно для многих алгоритмов, в которых задача оценивания
множеств решений ИСЛАУ используется как вспомогательная.
ассмотрим в качестве первого примера систему уравнений
[2, 3] [?1.9, 1]
[1, 2]
[2, 3]
!
[0, 2]
[1, 4]
x=
!
,
(58)
множество решений которой показано на рис. 3. Оптимальная (точная) внешняя интер?
вальная оценка ее множества решений есть брус ([?2, 1.9662], [?1, 4]) .
Матрица системы (58) является H -матрицей, но она весьма близка к границе множества H -матриц. Так, интервальная матрица
[2, 3] [?2, 1]
[1, 2] [2, 3]
отличающаяся от матрицы в (58) на
0.1
!
,
в левой границе элемента на месте
(1, 2),
уже
не является H -матрицей. По этой причине пример (58), будучи пессимистическим,
весьма труден для рассматриваемых методов внешнего оценивания множеств решений
ИСЛАУ. Вместе с тем он хорошо демонстрирует трудности худшего случая, которые
быстро нарастают при увеличении размерности задачи.
Об испанской версии ормального подхода к внешнему оцениванию...
129
4
3.5
3
2.5
2
1.5
1
0.5
0
?0.5
?1
?3
?2
?1
0
1
2
3
ис. 3. Множество решений системы уравнений (58) и его наилучшая внешняя интервальная
оценка
Процедура Хансена Блика она в применении к (58) дает ответ
[?38, 58]
[?10, 60]
!
.
(59)
При использовании традиционной версии ормального подхода согласно [19, 21, 26?
задача сводится к нахождению ормального решения системы
(dev diag A)x = (dev diag A ? A)x + b,
где
diag A
диагональ матрицы
A
(обозначенная через
D
(60)
в представлении (47) и в
последующих выкладках) и
dev x :=
отклонение интервала
x,
x,
x,
если
|x| ? |x|,
иначе, т. е. наиболее удаленная от нуля точка интервала
x.
Искомое
ормальное решение равно
[?23.3846, 25.1154]
[?24.6154, 25.3846]
!
(61)
и находится субдиеренциальным методом Ньютона за одну итерацию. Испанская
версия ормального подхода дает тот же ответ за три итерации, но не требует приведения исходной ИСЛАУ к виду (60).
130
С. П. Шарый
Что касается интервального метода аусса Зейделя, то он сходится к тому же
интервальному вектору (61), но делает это существенно медленнее. Запущенный из
?
начального бруса ([?40, 40], [?40, 40]) , он выдает за 40 итераций ответ
[?25.2629, 27.0925]
[?26.5925, 27.2629]
!
.
На каждой итерации субдиеренциального метода Ньютона нужно решать точеч2n
ную систему линейных уравнений в R , и потому можно считать, что трудоемкость
3
одной его итерации составляет O(n ). Но этих итераций требуется немного. Как правило, их количество не превышает порядка решаемой интервальной системы уравнений,
а в реальности является даже существенно меньшим. Трудоемкость одной итерации
2
интервального метода аусса Зейделя равна O(n ), но в случае плохой матрицы
ИСЛАУ сходимость может потребовать значительного количества итераций. В подобных случаях полные трудозатраты интервального метода аусса Зейделя превышают
трудозатраты субдиеренциального метода Ньютона.
ассмотрим теперь работу перечисленных в начале раздела методов совместно с
предобуславливанием обратной средней матрицей. Это популярная модиикация, которая рекомендуется многими специалистами для постоянного применения, так как
вкупе с традиционными методами внешнего оценивания множеств решений (интервальным методом аусса, итерационными методами и т. п.) она обеспечивает квадратичную
точность внешнего оценивания относительно ширины решаемой интервальной системы
[3, 44?, а не первый порядок, как в (53) и ей аналогичных оценках. Напомним, что предобуславливание обратной средней встроено в известный интервальный итерационный
метод Кравчика [3, 7?.
После предобуславливания исходной системы (58) обратной средней матрицей получаем систему
[0.7870, 1.2130] [?0.5560, 0.5560]
[?0.2889, 0.2889] [0.5054, 1.4946]
!
[0.0649, 0.9820]
[?0.0723, 1.4441]
x=
!
.
В применении к ней процедура Хансена Блика она дает ответ
[?3.2462, 5.4770]
[?1.4352, 5.9869]
!
,
который весьма близок к оптимальным внешним оценкам. Но предобуславливание обратной средней и результат о квадратичной сходимости внешних оценок работают хорошо в случае не слишком широких интервалов в системе уравнений. Если рассматривается ИСЛАУ с широкими и очень широкими интервальными данными в матрице,
то в действие вступают нелинейные эекты, предобуславливание обратной средней
матрицей оказывается не лучшим, и ситуация качественно меняется [7?.
Для иллюстрации этого утверждения рассмотрим в качестве примера систему уравнений
[2, 300] [?1.9, 1]
[1, 2]
[2, 300]
!
x=
[0, 2]
[1, 4]
!
,
(62)
в которой сильно увеличены верхние границы диагональных элементов. Ее множество
решений отличается от множества решений системы (58) весьма незначительно (лишь
Об испанской версии ормального подхода к внешнему оцениванию...
131
нижней границей куска из первого квадранта), а оптимальные (точные) покоординатные оценки множества решений совершенно такие же:
[?2, 1.9662]
[?1, 4]
.
Но после предобуславливания обратной средней процедура Хансена Блика она дает в применении к получившейся системе ответ
[?32.1299, 49.1483]
[?8.5763, 50.9130]
!
очень широкий интервал, что несколько лучше ответа, получаемого с помощью ормального (алгебраического) подхода
[?48.1424, 49.1483]
[?48.4105, 50.9130]
!
,
который и традиционная, и испанская версии получают всего за три итерации. К тому
же пределу сходится из достаточно широкого начального приближения интервальный
итерационный метод аусса Зейделя, но так же медленно, как и в случае исходной
системы без предобуславливания (58).
11. Некоторые итоги и выводы
Испанская версия ормального (алгебраического) подхода к внешнему оцениванию
множеств решений интервальных систем уравнений, сводящая исходную задачу к нахождению правильного ормального решения системы уравнений (36) (37) или (41),
является равносильной версией подхода, развитого ранее в работах [19, 21, 26?, и имеет
ту же серу применимости интервальные линейные системы с H -матрицами.
Имея те же характеристики трудоемкости выполнения, испанская версия несколько более трудна для реализации и использует в среднем немного больше итераций для
сходимости. Однако в отличие от традиционной она не требует специального приведения исходной интервальной системы с специальному рекуррентному виду.
Список литературы
[1? Алеельд ., Херцбергер Ю. Введение в интервальные вычисления. М.: Мир, 1987.
[2? Калмыков С.А., Шокин Ю.И., Юлдашев З.Х. Методы интервального анализа. Новосибирск: Наука, 1986.
[3? Neumaier A. Interval Methods for Systems of Equations. Cambridge Univ. Press, 1990.
[4? Задачи линейной оптимизации с неточными данными / М. Фидлер, Й. Недома, Я. амик,
И. он, К. Циммерманн. М.; Ижевск: Изд-во ХД, 2008.
[5? Shary S.P. Algebrai approah to the interval linear stati identiation, tolerane and ontrol
problems, or One more appliation of Kauher arithmeti // Reliable Comput. 1996. Vol. 2,
No. 1. P. 333.
132
С. П. Шарый
[6? Шарый С.П. Алгебраический подход к анализу линейных статических систем с интервальной неопределенностью // Изв. АН. Теория и системы управления. 1997. ќ 3.
С. 5161.
[7? Шарый С.П. Конечномерный интервальный анализ. Электронная книга, доступная на
http://www.ns.ru/interval/Library/InteBooks/SharyBook.pdf
[8? Shary S.P. A new tehnique in systems analysis under interval unertainty and
ambiguity // Reliable Comput. 2002. Vol. 8, No. 5. P. 321418 (электронная версия
http://www.ns.ru/interval/shary/Papers/ANewTeh.pdf).
[9? Kearfott R.B., Nakao M., Neumaier A. et al. Standardized notation in interval
analysis // Тр. XIII Байкальской междунар. школы-семинара Методы оптимизации и их
приложения. Т. 4. Интервальный анализ. Иркутск: ИСЭМ СО АН, 2005. С. 107113
(электроная версия http://www.ns.ru/interval/INotation.pdf).
[10? Berman A., Plemmons R.J. Nonnegative Matries in the Mathematial Sienes. New York:
Aad. Press, 1979.
[11? Moore R.E., Kearfott R.B., Cloud M.J. Introdution to Interval Analysis. Philadelphia:
SIAM, 2009.
[12? Интервальный анализ и его приложения. Веб-сайт http://www.ns.ru/interval
[13? Бессонов Л.А. Теоретические основы электротехники. Электрические цепи. М.: Высшая школа, 1996.
[14? Манусов В.З., Моисеев С.М., Перков С.Д. Интервальный анализ в линейных задачах электротехники // Инормационно-оперативный материал (интервальный анализ).
Красноярск, 1988. (Препр. ВЦ СО АН ССС. ќ 6. С. 2931.)
[15? Фихтенгольц .М. Курс диеренциального и интегрального исчисления. Т. 1. М.:
Наука, 1966.
[16? Шилов .Е. Математический анализ. Функции одного переменного. Ч. 1, 2. М.: Наука,
1969.
[17? Miranda C. Un' osservatione su un teorema di Brouwer // Bollet. Unione Mat. Ital. Serie II.
1940. Vol. 3. P. 57.
[18? Kauher E. Uber
metrishe und algebraishe Eigenshaften einiger beim numerishen
Rehnen auftretender Raume. Dr. Naturwissen. Dissertation. Univ. Karlsruhe, 1973.
[19? Шарый С.П. Алгебраический подход во внешней задаче для интервальных линейных
систем // Вычисл. технологии. 1998. Т. 3, ќ 2. С. 67114.
[20? Kauher E. Interval analysis in the extended interval spae IR // Fundamentals of Numerial
Computation (Computer-oriented numerial analysis) / Еds. G. Alefeld, R.D. Grigorie.
Comput. Suppl. 2. Wien: Springer, 1980. P. 3349.
[21? Shary S.P. Algebrai approah in the outer problem for interval linear equations // Reliable
Comput. 1997. Vol. 3, No. 2. P. 103135.
[22? Gardenes
E., Trepat A. Fundamentals of SIGLA, an interval omputing system over the
ompleted set of intervals // Computing. 1980. Vol. 24. P. 161179
[23? Gardenes
E., Trepat A., Mielgo H. Present perspetive of the SIGLA interval system //
Freiburger Intervall-Berihte. 1982. No. 82/9. P. 165.
[24? Клейн Ф. Лекции об икосаэдре и решении уравнений пятой степени. М.: Наука, 1989.
[25? Hansen E. On linear algebrai equations with interval oeients // Topis in Interval
Analysis / Ed. E. Hansen. Oxford: Clarendon Press, 1969. P. 3546.
Об испанской версии ормального подхода к внешнему оцениванию...
133
[26? Шарый С.П. Алгебраический подход во внешней задаче для интервальных линейных
систем // Фундамент. и прикл. математика. 2002. Т. 8, ќ 2. C. 567610 (электронная
версия http://www.ns.ru/interval/shary/Papers/FunPriMath.pdf).
[27? Sainz M.A., Gardenes
E., Jorba L. Formal solution to systems of interval linear or nonlinear equations // Reliable Comput. 2002. Vol. 8. P. 189211.
[28? Sainz M.A., Gardenes
E., Jorba L. Interval estimations of solution sets to real-valued
systems of linear or non-linear equations // Reliable Comput. 2002. Vol. 8. P. 283305.
[29? Apostolatos N., Kulish U. Grun
Документ
Категория
Без категории
Просмотров
5
Размер файла
412 Кб
Теги
оценивания, версия, решение, множества, система, подход, внешнему, линейный, формальное, испанском, интервальных
1/--страниц
Пожаловаться на содержимое документа