ВУЗ: Омский государственный технический университет
Категория: Книга
Дисциплина: Методы оптимальных решений
Добавлен: 12.02.2019
Просмотров: 13074
Скачиваний: 111
156
содержащему блок – диагональную матрицу с неприводимыми матрицами
(
)
1,
,
i
A i
k
= …
на диагонали. При этом, по крайней мере, одна из матриц с двойным
индексом в каждой строке, в которой они появляются – ненулевая (см. [52, 53]).
Доказательство теоремы проводится в предположении, что если матрица приво-
дима и может быть представлена в виде, данном в определении приводимой матри-
цы, или же ее диагональные блоки приводимы, то она вновь может быть представ-
лена в такой форме. В свою очередь, если какой-либо из ее диагональных блоков
приводим, он вновь представляется в соответствии со стандартной формой приво-
димой матрицы. В результате после соответствующей перестановки индексов, полу-
чим матрицу, все элементы которой над диагональными блоками равны нулю; все
диагональные блоки неприводимы. Кроме того, соответствующей перестановкой ин-
дексов все строки, диагональные блоки которых только ненулевые матрицы, могут
быть расположены так, чтобы распасться на части, как уже было показано выше.
Отметим, что каждый; из «изолированных» блоков
1
,
,
k
A
A
…
достижим в графо-
теоретическом смысле, из узлов, соответствующих строкам с двумя индексами, но
не наоборот. Заметим также, что все матрицы с двумя индексами в каждом столбце
могут быть просто записаны в виде строки блоков
1
2
,
,
,
k
R R
R
…
,
Q
, где
Q
, конечно,
уже не является неприводимым. Приведенная выше форма является единственной с
точностью до перестановок блочных индексов.
Можно было бы закончить и транспонированной формой, в которой блоки
1
2
,
,
,
k
R R
R
…
,
Q
образуют последний столбец нашей матрицы. Действительно, это та
форма, которая будет использоваться позже, при рассмотрении «стохастических»
матриц приоритетов.
Процесс построения нормальной формы матрицы приоритетов – прямой. Начина-
ем с любого элемента и заполняем в его столбце ненулевые приоритеты воздействий
как компоненты собственного вектора всех тех элементов, которые имеют воздейст-
вие на него. Каждый из этих элементов, в свою очередь, входит в примыкающие
столбцы со входящими ненулевыми приоритетами воздействий всех других элемен-
тов на них. Процесс продолжается до тех пор, пока еще есть новые элементы, кото-
рые влияют на это множество. Следует удостовериться в том, что новых элементов
больше нет. Так получаем блок для неприводимого множества. Начиная с другого
элемента, процесс повторяется для следующего блока и т. д.
7.3. СУЩЕСТВОВАНИЕ И ЕДИНСТВЕННОСТЬ
ГЛАВНЫХ СОБСТВЕННЫХ ВЕКТОРОВ
Как указывалось ранее, сначала будет представлена общая теорема существова-
ния и единственности при решении задачи о собственном значении для неотрица-
тельной неприводимой матрицы (более общей, чем положительная обратносиммет-
ричная матрица). Это фактически и есть теорема, доказанная Фробениусом, который
обобщил результат Перрона для положительной матрицы. Затем следует обсуждение
и доказательство теоремы Перрона. Доказательство теоремы Фробениуса может
быть найдено в [53].
Теорема 7.3. (Перрон–Фробениус). Пусть
0
A
≥
– неприводимая матрица. То-
гда:
1.
A
имеет действительное положительное простое (т. е. не кратное) собствен-
ное значение
max
λ
, которое по модулю не меньше любого другого собственного зна-
чения матрицы
A
(некоторые из которых могут быть комплексными числами).
157
2. Собственный вектор
A
, соответствующий собственному значению
max
λ
, имеет
положительные компоненты и, по существу (с точностью до постоянного множите-
ля), единственен.
3. Число
max
λ
(иногда называемое корнем Перрона матрицы
A
) удовлетворяет
условию
( )
( )
max
1
0
0
1
max min
min max
i
i
i n
x
x
i n
i
i
Ax
Ax
x
x
λ
≤ ≤
≥
≥
≤ ≤
=
=
;
0
x
≥
– произвольно.
Следствие. Пусть
0
A
≥
неприводима и пусть
0
x
≥
произвольно. Тогда корень
Перрона удовлетворяет условию
( )
( )
max
1
1
min
max
i
i
i n
i n
i
i
Ax
Ax
x
x
λ
≤ ≤
≤ ≤
≤
≤
,
Теорема 7.4. (Перрон). В этой теореме утверждается то же, что и в предыду-
щей, с той разницей, что матрица
0
A
>
(и, следовательно, неприводима) и модуль
max
λ
строго превосходит модули всех других собственных значений.
Краткое доказательство теоремы Перрона может быть получено как результат
доказательства
следующих
полезных
фактов
о
положительных
(
)
n n
×
-
матрицах [25]. Последовательность этих фактов такова: пусть
A
– положительная
(
)
n n
×
-матрица,
max
λ
– ее наибольшее собственное значение.
1.
max
λ
ограничено сверху и снизу соответственно максимальной и минимальной
строчными суммами матрицы
A
.
Следовательно, если
A
– стохастическая матрица, т. е. если её строчные суммы
равны единице, то
max
1
λ
=
.
2. Для стохастической матрицы
A
lim
k
k
A
e
υ
→∞
=
,
где
υ
– положительный вектор-строка,
(
)
1
2
, , ,
n
υ
υ υ
υ
=
…
,
1
1
n
i
i
υ
=
=
∑
и
(
)
1,1,
,1
T
e
=
…
.
3. Для положительной матрицы
A
существует положительное число
λ
, ненуле-
вая вектор-строка
υ
и ненулевой вектор-столбец
ω
, такие, что
lim
k
k
k
A
ωυ
λ
→∞
=
.
4.
λ
есть наибольшее собственное значение
A
и называется главным собствен-
ным значением, а
ω
и
υ
– главные собственные векторы, единственные с точно-
стью до постоянного множителя.
5.
ω
ортогонален всем не главным собственным векторам-столбцам, а
υ
– всем
не главным собственным векторам-строкам.
б. Если
1
λ
– наибольшее собственное значение
A
, причем
i
j
λ λ
≠
,
i
j
≠
,
,
1,
,
i j
n
= …
, и если
i
ω
– правый собственный вектор, соответствующий
i
λ
, то
1
lim
k
T
k
k
A e
c
e A e
ω
→∞
=
.
Эту важную теорему, сформулированную в таком виде, очень легко доказать. Но
ее можно и обобщить.
158
7. Теорема верна и в случае, когда
0
A
≥
,
0
p
A
>
для некоторого
0
p
≥
при тех
же прочих условиях.
Теорема 7.5.
1.
max
1
1
max
1
1
min
max
;
min
max
.
n
n
ij
ij
j
j
i
i
n
n
ij
ij
i
i
j
j
a
a
a
a
λ
λ
=
=
=
=
≤
≤
≤
≤
∑
∑
∑
∑
Неравенство имеет место, когда суммы не одинаковы.
2.
( )
1/
max
lim
k
k
k
tr A
λ
→∞
=
.
3.
1
1
max
0
0
max min
min max
n
n
ij
j
ij
j
j
j
i
u
u
i
i
i
a u
a u
u
u
λ
=
=
>
>
=
=
∑
∑
.
4.
1
1
max
0
0
max min
min max
n
n
ij i
ij i
i
i
j
u
u
j
j
j
a u
a u
u
u
λ
=
=
>
>
=
=
∑
∑
.
Доказательство. Компоненты вектора
Ae
представляют собой суммы строк мат-
рицы
A
. Пусть наибольшая сумма строк есть
M
, а наименьшая –
m
. Тогда
me Ae Me
≤
≤
, а равенство имеет место только при
m M
=
.
Из выражения
max
A
υ
λ υ
=
имеем
max
Ae
e
υ
λ υ
=
,
max
me
e
Me
υ
λ υ
υ
≤
≤
.
Если теперь разделим неравенство на положительное число
e
υ
, то получим
max
m
M
λ
≤
≤
, причём равенство вновь будет иметь место, если
m M
=
. Аналогично
для сумм столбцов.
Доказательство (2) получается либо из выражения
1/
1/
lim
1
1 1
lim
k
k
k
k
k
k
k
tr
A
tr A
λ
λ
→∞
→∞
= =
,
либо из
1
k
k
k
n
tr A
λ
λ
+ +
=
…
. Пусть во втором случае
1
max
λ λ
=
, тогда
(
)
(
)
1/
1
2
1
1
1
k
k
k
k
n
tr A
λ
λ λ
λ λ
+
+ +
=
…
,
при
k
→ ∞
,
1
k
tr A
λ
→
. Остальная часть доказательства здесь не приводится.
Теорема 7.6. Если
A
– положительная
(
)
n n
×
-матрица, у которой сумма эле-
ментов каждой строки равна единице, то существует положительная вектор-строка
υ
,
1
1
n
i
i
υ
=
=
∑
, такая, что
lim
m
m
A
e
υ
→∞
=
, где
(
)
1,1,
,1
T
e
=
…
.
Доказательство. Пусть
0
y
– любой
n
-мерный вектор-столбец. Определим
0
m
m
y
A y
=
и пусть
m
a
и
m
b
– максимальная и минимальная компоненты
m
y
соответ-
ственно. Пусть
α
– минимальный элемент матрицы
A
. Так как
1
m
m
y
Ay
+
=
, любая
159
компонента вектора
1
m
y
+
получается умножением строки
A
на
m
y
, и, следователь-
но, имеем следующие границы для произвольной компоненты
c
вектора
1
m
y
+
:
(
)
(
)
1
1
m
m
m
m
b
a
c
b
a
α
α
α
α
−
+
≤ ≤
+ −
.
Это неравенство остается в силе для наибольшей и наименьшей компонент
m r
y
+
, от-
куда
(
)
1
1
m
m
m
a
b
a
α
α
+
≤
+ −
(следовательно,
m
a
монотонно возрастает) и
(
)
1
1
m
m
m
b
a
b
α
α
+
−
+
≤
(следовательно,
m
b
монотонно убывает), или
(
)
1
1
m
m
m
b
b
a
α
α
+
−
≤ − −
−
и
(
)(
)
1
1
1 2
m
m
m
m
a
b
a
b
α
+
+
−
< −
−
.
Отсюда по индукции получаем
(
) (
)
0
0
1 2
m
m
m
a
b
a
b
α
−
≤ −
−
.
Так как правая часть этого неравенства стремится к нулю, то
m
a
и
m
b
сходятся к
общему пределу, и. следовательно, все компоненты
m
y
приближаются к нему же,
т. е.
lim
m
m
y
Ce
→∞
=
при
0
0
b
C a
≤ ≤
(равенство имеет место только при
0
0
a
b
=
). Пусть
(
)
1
2
0
0
0
0
,
,
,
n
y
y y
y
=
…
, где
0
1
i
y
=
,
0
0
j
y
=
,
j i
≠
. Тогда
m
y
есть
i
-й столбец матрицы
m
A
, и, как уже установлено,
(
)
,
,
T
T
m
i
i
y
c
c
υ
→
≡
…
, причем
0
0
b
=
,
0
0
i
c
b
>
=
. Сле-
довательно,
lim
m
m
A
e
υ
→∞
=
.
Отметим, что поскольку каждая строчная сумма
m
A
равна единице, то
1
1
n
i
i
υ
=
=
∑
.
Теорема 7.7. Если
A
– положительная
(
)
n n
×
-матрица, то
lim
k
k
k
A
ωυ
λ
→∞
=
,
где
λ
– положительная постоянная,
υ
– ненулевая вектор-строка, а
ω
– нену-
левой вектор-столбец.
Краткое доказательство. Пусть
(
)
1
1
|
,
,
,
0,
1,
, ,
1,
. .
1
n
T
n
t
i
i
S
x x
x
x
x
i
n
x
т е fx
=
=
=
≥
=
=
=
∑
…
…
, где
(
)
1,1,
, 1
f
=
…
.
Рассмотрим отображение
1
,
Tx
Ax x S
fAx
=
∈
.
Это отображение положительно: так как
1
fx
=
, то
x
имеет ненулевую компоненту,
и, следовательно,
0
Ax
>
и
0
fAx
>
. Далее
160
1
1
fTx
fAx
fAx
=
=
,
и поэтому
T
отображает
S
в
S
. Так как
A
непрерывна, по теореме Брауера о не-
подвижной точке найдется точка
ω
, что
1
A
fA
ω ω
ω
=
.
Поскольку левая часть положительна,
ω
– положительна и
0
fA
λ
ω
=
>
. Следова-
тельно,
A
ω λω
=
,
0
λ
>
,
0
ω
>
. Наконец, пусть
D
– диагональная матрица с
ii
i
d
ω
=
и
0
ij
d
=
,
i
j
≠
. Так как
0
ω
>
,
D
имеет обратную матрицу
1
D
−
, также диагональ-
ную, с диагональными элементами
1
i
ω
, т. е.
De
ω
=
и
( )
( )
1
1
1
1
1
D
AD e
D
A
D
e
λ
λ
ω
ω
−
−
−
=
=
=
.
Отсюда следует, что суммы строк матрицы
( )
1
1
D
AD
λ
−
равны единице, т. е.
эта матрица – стохастическая, и исходя из теоремы 7.6 найдётся такой вектор-
строка
*
υ
, что
( )
(
)
*
1
1
lim
1
lim
1
k
k
k
k
k
e
D
AD
D
A D
υ
λ
λ
−
−
→∞
→∞
=
=
,
(т. е. строки предельной матрицы все одинаковы), откуда непосредственно получа-
ем
( )
*
1
*
1
lim 1
k
k
k
A
De D
D
λ
υ
ωυ
ωυ
−
−
→∞
=
=
=
.
Теорема 7.8.
υ
и
ω
– собственные векторы матрицы
A
, соответствующие соб-
ственному значению
λ
.
Доказательство.
( )
( )
( )
( )
1
1
1
1
lim 1
lim 1
k
k
k
k
k
k
A
A
A
A
λ ωυ
λ
λ
λ
ωυ
+
+
→∞
→∞
=
=
=
,
откуда имеем
A
ωυ λωυ
=
и
A
e
e
ωυ
λωυ
=
, и так как
e
υ
постоянная, то
A
ω λω
=
.
Аналогично
A
υ
λυ
=
.
Следствие. Векторы
υ
и
ω
положительны.
Доказательство. Из равенства
A
ω λω
=
имеем
( )
1
A
λ ω ω
=
. Так как
, A
λ
– по-
ложительны, а
ω
– неотрицателен (с некоторыми ненулевыми компонентами), все
компоненты левой части равенства положительны, и, следовательно,
ω
– положи-
телен; аналогично для
υ
.
Теорема 7.9. Все собственные векторы, соответствующие собственному значе-
нию
λ
, являются постоянными множителями
ω
и
υ
.
Доказательство. Если
Au
u
λ
=
, то
k
k
A u
u
λ
=
, а
( )
1
k
k
A u u
λ
=
для всех
k
. При
k
→ ∞
имеем
u u
ωυ
=
. Аналогично для векторов-строк.
Теорема 7.10. Модуль любого другого собственного значения
h
матрицы
A
удовлетворяет неравенству
h
λ
<
.
Доказательство. Если
Au hu
=
, то
k
k
A u h u
=
, а
( )
(
)
1
k
k
k
A u
h
u
λ
λ
=
. Переходя к
пределу при
k
→ ∞
имеем
[ ]
lim
k
k
u
h
u
ωυ
λ
→∞
=
,