ВУЗ: Омский государственный технический университет
Категория: Книга
Дисциплина: Методы оптимальных решений
Добавлен: 12.02.2019
Просмотров: 13101
Скачиваний: 114
166
данных. Предположим, что все возмущения, заслуживающие внимания, могут ( быть
сведены к общему виду
(
)
ij
i
j
ij
a
ω ω ε
=
. Согласованность имеет место, если
1
ij
ε
=
.
Например,
(
)
(
) (
)
1
i
j
ij
i
j
j
i
ij
a
a
ω ω
ω ω
ω ω
+
=
+
.
Теперь получим некоторые элементарные, однако существенные результаты для
согласованных матриц. Начнем с выражения
(
)
max
1
n
ij
j
i
j
a
λ
ω ω
=
=
∑
,
которое является
i
-й компонентой
max
A
ω λ ω
=
, и определим
(
)
2
1
1
n
i
i
n
µ
λ
=
= −
−
∑
.
Тогда из
1
n
i
i
n
λ
=
=
∑
следует, что
(
) (
)
max
1
n
n
µ
λ
=
−
−
;
max
1
λ
λ
≡
, и так как
(
)
max
1
ij
j
i
j i
a
λ
ω ω
≠
− =
∑
,
находим, что
(
)
(
)
max
1
ij
j
i
ji
i
j
i j n
n
n
a
a
λ
ω ω
ω ω
≤ < ≤
− =
+
∑
,
поэтому
(
)
(
)
(
)
max
1
1
1
1
1
1
1
ij
j
i
ji
i
j
i j n
n
n
a
a
n
n
n
n n
λ
µ
ω ω
ω ω
≤ < ≤
−
=
=
−
+
+
−
−
−
−
∑
.
Подставляя
(
)
,
0
ij
i
j
ij
ij
a
ω ω ε ε
=
>
, приходам к уравнению
(
)
( )
1
1
1
1
1
ij
ij
i j n
n n
µ
ε
ε
≤ < ≤
= − +
+
−
∑
.
Заметим, что при
1
ij
ε
→
, т. е. при достижении согласованности,
0
µ
→
. Кроме
того,
µ
выпукла по
ij
ε
, поскольку
( )
1
ij
ij
ε
ε
+
выпукло (и имеет минимум при
1
ij
ε
=
)
и сумма выпуклых функций выпукла. Поэтому
µ
мало или велико в зависимости от
того, близка или далека величина
ij
ε
от единицы соответственно (т. е. близки или
далеки мы от согласованности). Наконец, если напишем
1
ij
ij
ε
δ
= +
, то при
1
ij
δ
> −
имеем
(
)
2
2
1
1
1
1
ij
ij
i j n
ij
n n
δ
µ
δ
δ
≤ < ≤
=
−
−
+
∑
.
Теорема 7.14.
max
n
λ
≥
.
Доказательство.
(
)
2
max
1
1
1
1
1
ij
i j n
ij
n
n
n n
δ
λ
δ
≤ < ≤
−
=
−
−
+
∑
,
что
0
≥
, так как
(
)(
)
1
ij
i
j
ij
a
ω ω
δ
=
+
, при
1
ij
δ
> −
.
167
Теорема 7.15. Положительная обратносимметричная матрица согласована тогда
и только тогда, когда
max
n
λ
=
.
Доказательство. Если
A
согласованна, то
0
ij
δ
=
и
max
n
λ
=
. Наоборот, используя
полученный выше результат, отмечаем, что
max
n
λ
=
,
0
ij
δ
=
при любом выборе
i
и
j
, следовательно, матрица
A
– согласованна.
Таким образом, для достижения согласованности желательно, чтобы
µ
было
близко к нулю, или, что то же самое,
max
λ
было близко к своей нижней границе
n
.
Интересно отметить, что
(
) (
)
max
1
n
n
λ
−
−
можно интерпретировать в терминах ста-
тистической среднеквадратичной ошибки. Действительно, допустим, что
1
ij
δ
<
(и,
следовательно,
(
)
3
1
ij
ij
δ
δ
+
) мало по сравнению с
2
ij
δ
). Это разумное допущение для
«несмещенного» суждения, которое ограничено «естественной» наибольшей нижней
границей – 1 для
ij
δ
(так как
ij
a
должно быть больше нуля) и будет стремиться к
симметричной оценке около нуля в интервале
(
)
1,1
−
. Теперь
0
µ
→
при
0
ij
δ
→
.
Умножение на 2 даёт дисперсию
ij
δ
. Поэтому
2
µ
и есть эта дисперсия.
Малые возмущения элементов положительной обратносимметричной матрицы
вызывают малые возмущения в собственных значениях от их исходной величины.
Вообще говоря, это неверно для положительных матриц. Докажем этот факт для
max
λ
.
Теорема 7.16. Пусть
,
max
ij
i j
δ
δ
=
, тогда
2
2
max
1
1
1
2
ij
i j n
n
n
n
λ
δ
δ
≤ < ≤
−
− <
≤
∑
.
Доказательство очевидно.
Таким образом, если возмущение (или ошибка в суждении) мало, и число срав-
ниваемых элементов также мало (например, менее десяти), то отклонение
max
λ
от
n
также мало. Отметим вновь, что для того, чтобы остаться вблизи согласованности,
нужно, чтобы
n
было мало. Например,
0,1
δ
=
,
7
n
=
дает
max
0,04
n
λ
− <
, а
0,9
δ
=
,
7
n
=
дает
max
2, 43
n
λ
− <
.
3амечание. Неотрицательная матрица
( )
ij
A
a
=
с
, 1
1
i i
a
+
=
и
0
ij
a
=
– для осталь-
ных
i
,
j
имеет все собственные значения равными нулю, но та же самая матрица с
1
n
a
, замененным на
ε
, где
0
ε
>
мало, имеет максимальное собственное значение
1
max
n
λ
ε
=
, которое стремится к единице при увеличении
n
. Поэтому, хотя
max
λ
из-
меняется непрерывно с коэффициентом
ε
, ее величина становится большой даже
для малых
ε
(этот факт сообщил мне А. Лауб из Массачусетского технологического
института).
В [168] отмечено, что, используя свойство обратной симметричности
1
ij
ji
a
a
=
из
равенства
ij
jk
ik
a a
a
=
, имеем
1
ij
jk ki
a a a
=
. Следовательно, согласованность для обрат-
носимметричной матрицы значит, что все контуры длины три имеют единичную ин-
тенсивность.
Предполагая
1
ij
δ
<
и рассматривая треугольные контуры, находим
168
(
)(
)
(
)
1
1
1
1
ij
jk ki
ij
jk
ik
ij
jk
ik
a a a
δ
δ
δ
δ
δ
δ
= +
+
−
≈ +
+
−
,
и, поскольку
max
1
n
ij
j
λ
ε
=
=
∑
, имеем
2
max
, ,
ij
jk ki
i j k
a a a
n
λ
=
∑
.
Для
i
j
≠
,
j k
≠
,
i k
≠
эта сумма становится равной
(
) (
)(
)
2
max
1
2
n
n
n n
n
λ
− +
−
−
,
так как, подставляя
1
pp
a
=
,
1
pq
qp
a
a
−
=
, имеем
(
)
2
2
1
n
n n
+
−
членов, величина кото-
рых равна единице. Усредняя по количеству членов, т. е.
(
)(
)
1
2
n n
n
−
−
в результа-
те получаем
(
) (
) (
)
max
2
1 1
n n
n
n
λ
−
−
− +
, что справедливо при
3
n
≥
. В любом слу-
чае предметом нашего внимания является разность
max
n
λ
−
.
Теперь проверим гипотезу о согласованности. Полная согласованность может
быть сформулирована в виде нулевой гипотезы:
0
:
0
H
µ
=
,
и мы проверяем ее по отношению к односторонней альтернативе
1
:
0
H
µ
>
.
Соответствующая тестовая статистика будет
max
1
n
m
n
λ
−
=
−
,
где
max
λ
– максимальное наблюдаемое собственное значение матрицы, элементы
которой
ij
a
содержат случайную ошибку. Установление статистической меры для со-
гласованности требует нахождения распределения статистики
m
. Несмотря на то,
что её специфическая форма выходит за рамки материала этой главы, заметим, что
m
соответствует неотрицательному вероятностному распределению, дисперсия ко-
торого есть удвоенное среднее
x
, и представляется совершенно аналогичным рас-
пределению
2
x
, если предположить, что все
ij
δ
, есть
(
)
2
0,
N
σ
на интервале
(
)
1,1
−
.
Для нашей цели при неизвестном распределении используем общепринятое отноше-
ние
(
)
0
2
x
x
µ
−
при
0
0
µ
=
, т. е. используем
2
x
в качественном тесте для под-
тверждения нулевой гипотезы, когда тестовая статистика, допустим,
1
≤
. Поэтому
при
2
x
>
. можно измерять несогласованность.
Более подходящий метод проверки статистики
m
заключается в используемом
нами сравнении ИС с СИ.
Замечание. Заметим, что для матриц
( )
ij
A
a
=
,
(
)
i
j
W
ω ω
=
имеем
(
)
(
)
max
A W
n
ω
λ
ω
−
=
−
,
откуда видно, что аппроксимация
( )
ij
a
посредством
(
)
i
j
ω ω
тем лучше, чем ближе
max
λ
к
n
.
Возвращаясь к представлению
(
)
ij
i
j
i
j
ij
a
ω ω
ω ω δ
=
+
,
находим, что
(
)
2
2
1
ij
ij
i
j
a
δ
ω ω
=
−
.
169
Таким образом, заменив
ij
a
на
i
j
ω ω
, получим
2
ij
δ
, сведя тем самым к нулю величи-
ну
(
) (
)
max
2
1
n
n
λ
−
−
.
Следовательно, всякий раз, когда
1
ij
δ
<
, аппроксимация любого
ij
a
величиной
i
j
ω ω
приближает нас к согласованности (см. также обсуждение метода наимень-
ших квадратов, которое будет проведено позже).
Теорема 7.17. Если положительная матрица
A
согласованна, то каждая строка
является положительным кратным любой заданной строки.
Доказательство. Без ограничения общности будем считать, что каждая строка
является положительным множителем
i
-й строки. Из отношения
jk
ik
ij
a
a a
=
следу-
ет, что, зафиксировав
j
и положив
1, 2,
,
k
n
=
…
,
j
-я строка будет равна
i
-й стро-
ке, умноженной на положительную постоянную
( )
1
ij
a
.
Замечание. Очевидно, что обратное утверждение этой теоремы неверно. Матри-
ца единичного ранга может и не быть согласованной. Например, в матрице
1 2
2 4
элемент
21
a
не равен
11
12
a a
.
Таким образом, согласованная матрица при
1
ii
a
=
имеет следующий общий вид:
1
1
2
1
1
1
2
2
2
2
1
2
i
i
i
i
in
i
i
i
i
i
in
i
i
in
i
in
in
in
a a
a a
a a
a a
a a
a a
a a
a a
a a
…
…
…
…
…
…
…
.
Так как матрица
(
)
i
j
A
ω ω
=
имеет вид транспонированной по отношению к при-
веденной матрице, она согласованна.
Теорема 7.18. Если
A
– положительная и согласованная матрица, то
1
ii
a
=
и
1
ij
ji
a
a
=
.
Доказательство. Из определения следует, что
ii
ij
ji
a
a a
=
и, следовательно,
1
ii
a
=
для всех
i
. Также из
ii
ij
ji
a
a a
=
следует,, что
1
ij
ii
ji
ji
a
a a
a
=
=
.
Теорема 7.19. Положительная матрица
A
согласованна в том и только в том
случае, если она единичного ранга и элементы её главной диагонали равны едини-
це.
Доказательство. Если
A
согласованна, то
1
ii
a
=
. Также
(
)
1
1
1
1
1
ij
j
i
i
j
a
a
a
a a
=
=
и
i
-я строка есть первая строка, умноженная на
(
)
1
1
i
a
, и, следовательно, ранг
A
равен единице. Наоборот, если ранг
A
равен единице и
1
ii
a
=
для всех
i
, то каж-
дая строка является кратной первой строке, т. е.
1
ij
i
j
a
c a
=
,
1
jk
j
k
a
c a
=
,
1 1
ik
k
a
c a
=
,
1
jj
j
j
a
c a
=
,
(
)
1
1
1
1
ij
jk
i j
j
k
i j
j
ik
i
j
j ik
jj ik
ik
a a
c c a a
c c a
a c
c a a
a a
a
=
=
=
=
=
,
170
и матрица
A
согласованна.
Перейдем к иллюстрации понятия согласованности на языке теории графов.
Определение 7.3. Интенсивность суждений, относящихся к пуль из
i
в
j
(на-
зываемая интенсивностью пути), равна произведению интенсивностей, соответст-
вующих дугам этого пути.
Следующая теорема вносит ясность относительно связи, существующей между
интенсивностями путей и согласованностью. Напомним, что перекрывающее дерево
с
n
вершинами имеет
1
n
−
ребер. Оно является связным графом, включающим все
вершины и не имеющим контуров. Поэтому имеется единственный путь между любой
парой вершин.
Теорема 7.20. Необходимым и достаточным условием существования единст-
венной положительной согласованной матрицы является то, что объекты (как вер-
шины) и соединяющие их суждения (как дуги) формируют перекрывающее дерево.
Доказательство. Необходимость. Если объекты формируют контур, то имеется не
единственный путь между двумя вершинами в контуре, что дает два различных зна-
чения для одного и того же элемента. Все объекты должны образовывать дерево,
иначе суждения для связывания изолированных объектов были бы произвольными,
что нарушило бы единственность матрицы.
Достаточность. Для каждой дуги перекрывающего дерева мы используем интен-
сивность вдоль единственного пути для получения интенсивностей между объектами
i
и
j
. Это определяет матрицу
( )
ij
A
a
=
.
Для доказательства согласованности матрицы
A
рассмотрим любую строку, на-
пример
i
-ю. Для любой пары вершин
j
и
k
нужно показать, что
jk
a
, определенная
произведением дуг на пути
jk
, дана величиной
ik
ij
a a
, где
ik
a
и
ij
a
– соответст-
вующие произведений интенсивностей дуг на путях, соединяющих
i
с
k
и
i
с
j
.
Рассмотрим два случая:
1.
i
лежит на пути между
j
и
k
. В этом случае
jk
ji ik
ik
ij
a
a a
a a
=
=
.
2.
i
не лежит между
j
и
k
, тогда:
а)
i
,
j
и
k
образуют путь; в этом случае путь, определяющий
jk
a
, дается вели-
чиной
ik
ij
a a
, если
j
находится между
i
и
k
и обратной величиной
ij
ik
a a
, т. е.
ik
ij
a a
, если
k
находится между
i
и
j
, так как путь должен проходить от
j
к
k
, а
не от
k
к
j
;
б)
i
,
j
и
k
образуют вилку в
m
(см. рис. 7.1). Тогда
jk
im mk
jm mi im mk
ji ik
ik
ij
a
a a
a a a a
a a
a a
=
=
=
=
.
Рис. 7.1
Теорема 7.21. Если
A
– согласованная матрица, то
1
k
k
A
n A
−
=
.
Доказательство. Из теоремы Сильвестра имеем
( )
( )
(
)
(
)
1
i
n
j i
i
i
i
j
j i
A
I
f A
f
λ
λ
λ λ
≠
=
≠
−
=
−
∏
∑
∏
.