ВУЗ: Омский государственный технический университет
Категория: Книга
Дисциплина: Методы оптимальных решений
Добавлен: 12.02.2019
Просмотров: 13068
Скачиваний: 111
161
и предел в правой стороне должен существовать, что возможно только при
h
λ
=
или
h
λ
<
, причем в последнем случае предел равен нулю.
Собственное значение
λ
есть главное собственное значение матрицы
A
, кото-
рое обозначается
max
λ
, а
υ
и
ω
– главные собственные векторы матрицы
A
.
Следствие. Главный собственный вектор-строка (столбец) —
( )
υ ω
ортогонален
ко всем не главным собственным векторам-столбцам (строкам) матрицы
A
.
Доказательство. Рассмотрим равенство
0
u
ωυ
=
из доказательства предыдущей
теоремы. Так как
0
ω
>
, имеем
0
u
υ
=
, и, следовательно,
υ
ортогонален вектору-
столбцу
u
. Аналогичный аргумент можно использовать, чтобы показать ортогональ-
ность
ω
ко всем не главным собственным векторам-строкам матрицы
A
.
Следствие.
1
υω
=
.
Доказательство. В условиях теоремы пусть
u
ω
=
, тогда
h
λ
=
и
ωυω ω
=
. Так
как
υω
– число, получаем
1
υω
=
.
Замечание.
υω
есть след матрицы
ωυ
, и, следовательно, этот след всегда равен
единице.
Замечание. Система
1
n
ij
j
i
j
a x
b
=
=
∑
,
1,
,
i
n
= …
.
где
0
ij
a
≥
,
0
ij
d
>
, имеет неотрицательное решение
0
j
x
≥
,
1,
,
j
n
= …
, если
11
12
13
11
12
11
21
22
23
21
22
31
32
33
0,
0,
0,
,
0
a
a
a
a
a
a
a
a
a
A
a
a
a
a
a
>
>
>
>
…
.
Теорема 7.11 [182]. Если
A
– неотрицательная неприводимая матрица, то зна-
чение
max
λ
возрастает с увеличением любого элемента
ij
a
.
Доказательство. Пусть
A
– неотрицательная матрица, определим
( )
B
I A
ρ
ρ
=
−
,
где
ρ
– действительный параметр [110]. Пусть
M
– множество всех
ρ
, для кото-
рых существует и не отрицательна обратная матрица
(
)
1
I A
ρ
−
−
. Множество
M
не-
пусто для
0
x
>
и остается таким для сравнительно большого
ρ
,
x Ax
ρ
>
, т. е.
0
x Ax
ρ
−
>
, и это условие обеспечивает существование неотрицательного решения
и эквивалентно вышеописанному условию на главные миноры. Так как
M
зависит
от
A
, обозначим его
( )
M A
.
Пусть
0
A
A
′
′′
≥
≥
. Тогда
( )
( )
M A
M A
′
′′
⊂
. В самом деле, заметим, что если
( )
M A
ρ
′
∈
, то
(
)
0
I A x
ρ
′
−
>
для некоторого
0
x
>
и так как
I A
I A
ρ
ρ
′′
′
−
≥
−
,
(
)
0
I A x
ρ
′′
−
>
для того же самого
x
, и, следовательно,
( )
M A
ρ
′′
∈
. Теперь макси-
мальное собственное значение
max
λ
матрицы
0
A
>
есть
( )
inf
M A
ρ
ρ
∈
, для которого
(
)
1
I A
ρ
−
−
существует, т. е. это первое значение, для которого
0
I A
ρ
− =
, ибо все
другие собственные значения не превосходят
max
λ
. Поэтому
( )
( )
( )
( )
max
max
inf
inf
M A
M A
A
A
ρ
ρ
λ
ρ
ρ λ
′
′′
∈
∈
′
′′
=
≥
=
.
162
Следовательно,
max
λ
– монотонная функция
A
.
Ниже показан важный результат, который заключается в том, что собственный
вектор, соответствующий
max
λ
, представляет собой нормализованные суммы элемен-
тов строк предельной матрицы в точности
k
-й степени
k
A
-матрицы
A
(а не суммы
всех степеней
A
).
Теорема 7.12.
1
lim
k
T
k
k
A e
c
e A e
ω
→∞
=
,
где
0
A
>
,
1
ω
– главный собственный вектор, соответствующий максимальному соб-
ственному значению
1
λ
,
i
j
λ λ
≠
для всех
i
и
j
,
i
ω
– правый собственный вектор,
соответствующий
i
λ
, а
c
– постоянная.
Доказательство.
1 1
n
n
e a
a
ω
ω
=
+ +
…
, где
,
1,
,
i
a i
n
= …
– постоянные.
(
)
(
)
1 1
1
1
1 1
2
2
1
2
1
k
k
k
k
k
k
n n
n
n
n
n
A e a
a
a
a
a
λ ω
λ ω
λ
ω
λ λ ω
λ λ ω
=
+ +
=
+
+ +
…
…
,
(
)
(
)
1
1
2
2
1
1
k
k
T
k
k
n
n
e A e
b b
b
λ
λ λ
λ λ
=
+
+ +
…
;
T
i
i
i
b
a e
ω
=
.
Так как
1
0
ω
>
,
0
b
≠
, что и требовалось доказать.
Теперь обобщим эту теорему.
Определение 7.2. Неотрицательная неприводимая матрица
A
примитивна то-
гда и только тогда, когда существует целое
1
m
≥
. такое, что
0
m
A
>
. В противном
случае матрицу называют импримитивной. Граф примитивной матрицы имеет длину
пути между любыми двумя вершинами
m
≥
.
Из работ [50, 114, 182] известно, что неотрицательная неприводимая матрица
A
примитивна тогда и только тогда, когда
A
имеет единственный характеристический
корень с максимальным модулем, и этот корень имеет кратность, равную единице.
Теорема 7.13. Для примитивной матрицы
A
lim
k
k
k
A e
c
A
ω
→∞
=
,
k
T
A
e Ae
≡
,
где
c
– постоянная, а
ω
– собственный вектор, соответствующий
max
1
λ
λ
≡
.
Доказательство. Допустим
0
A
>
. Рассмотрим жорданову каноническую форму
B
матрицы
A
. Тогда для некоторой невырожденной матрицы
N
1
2
1
0
.
.
.
0
r
B
NAN
B
B
λ
−
=
=
где
,
2,
,
i
B i
r
= …
есть
i
i
m m
×
жорданова блочная форма, которая имеет вид
163
1
0
1
1
.
.
.
.
.
.
.
0
1
i
i
i
i
i
i
B
λ
λ
λ
λ
λ
=
где
2
,
,
r
λ
λ
…
– различные собственные значения с кратностями
2
,
,
r
m
m
…
соот-
ветственно, а
2
1
r
i
i
m
n
=
+
=
∑
– размерность матрицы
A
. Выбираем соответствующие
базисные векторы для каждого подпространства жордановой формы
2
3
1
21
22
2
31
32
3
1
2
,
,
,
,
,
,
,
,
,
r
m
m
r
r
rm
V
V
V
V
V
V
V
V
V
V
…
…
…
и имеем
1
1 1
AV
V
λ
=
,
1
1
2
i
i i
i
AV
V
V
λ
=
+
,
2
2
3
i
i i
i
AV
V
V
λ
=
+
,
i
i
im
i im
AV
V
λ
=
.
Отметим, что
i
i
B
I u
λ
=
+
,
где
0
1 0
0
1 .
.
.
0
10
u
=
и
164
1
2 2
1
1
k
k
k
k
k
i
i
i
i
k
k
B
I
u
u
u
λ
λ
λ
−
−
=
+
+
+ +
…
,
где
k
u
– нулевая матрица, если
k n
≥
, а если
k n
>
– диагональ единиц в
u
,
сдвинутая вниз на каждую дополнительную степень
u
. Например,
2
0 0
0 0 0
0 0
0 0 0
1 0
0 0 0
0 1
0 0 0
0 0
1 0 0
u
=
…
…
…
…
…
.
Теперь пусть
2
2
1 1
21 21
22 22
2
2
31 31
r
r
m
m
r m
r m
e a V
a V
a V
a V
a V
a V
=
+
+
+ +
+
+ +
…
…
,
1 1
1
2
1
0
r
m
j
r
k
k
k l
ij
i
ij
i
j
i
k
A e a
V
a
V
j l
λ
λ
−
=
=
=
=
+
−
∑∑∑
,
1
1 1
2,
2
2,
1 2
2,1 2
,1
2
k
k
k
k
k
k
k
rk r
r
r
A
c
p
p
p
p
p
c
λ
λ
λ
λ
λ
λ
−
−
=
+
+
+ +
+ +
+ +
+
…
…
…
,
где
ij
p
– полиномы от
k
, а
1
c
,
2
c
– постоянные, не зависимые от
k
. Выражение
k
k
A e
A
, будет иметь член
1 1
1
1
1 1
2,
2
2,
1 2
2
k
k
k
k
k
k
a
V
c
p
p
c
λ
λ
λ
λ
−
−
+
+
+ +
…
,
предел которого при
k
→ ∞
будет
(
)
1
1
1
a c V
, так как
1
λ
– единственное наи-
большее собственное значение.
Типичный член
(
)
2
i
≥
1
1 1
2
k
il
i
ij
k
k
ik i
k
a
V
j l
c
p
c
λ
λ
λ
−
−
+ +
+ +
…
…
будет стремиться к нулю при
k
→ ∞
(так как
1
λ
превосходит все другие
λ
). Пола-
гая
(
)
1
1
e
a c
=
и
1
V
ω
=
, получаем теорему для
0
A
>
.
Замечание. Отметим, что
1
0
c
=
в том и только в том случае, если
1
0
a
=
. Можно
показать, что
1
0
a
≠
, исходя из того, что все
ij
a
в разложении
e
и все
i
V
действи-
тельны и положительны. Малое возмущение
e
оставляет
1
0
a
≠
, а результат при
этом останется тем же самым.
Теперь для доказательства теоремы при
0
A
≥
отметим, что из-за
0
ij
a
>
сущест-
вует такое положительное целое
m
, что
0
m
A
>
(т. е. при движении по петлям в ко-
нечном счете возможно получение пути любой желаемой длины между произволь-
ной парой вершин соответствующего графа). Приведенное выше доказательство
применимо к
m
A
и его наибольшему собственному вектору
( )
m
A
ω
. Действительно,
так как
A
– ограниченный линейный оператор (и поэтому непрерывный), имеем
165
( )
lim
, 0
mk i
m
mk i
k
A
c
A
i m
A
ω
+
+
→∞
=
≤ <
.
Легко убедиться, что
( )
m
A
ω
есть искомый неотрицательный собственный век-
тор.
Это завершает доказательство.
Замечание. Следующая неотрицательная матрица неприводима (ее граф – силь-
но связный, так как у любой пары вершин имеется путь, связывающий их):
0 2 0
0 0 4
1 0 0
A
=
.
Эта матрица не удовлетворяет условиям теоремы, поскольку она импримитивна,
имея 2 как единственное собственное значение кратности 3. Для пояснения этого
отметим следующее:
(
)
2, 4,1
T
Ae
=
; нормализацией получаем
(
)
1
2 / 7, 4 / 7,1/ 7
T
x
=
;
(
)
1
8 / 7, 4 / 7, 2 / 7
T
Ax
=
;
нормализацией
получаем
(
)
2
4 / 7, 2 / 7, 1/ 7
T
x
=
;
(
)
2
4 / 7, 4 / 7, 4 / 7
T
Ax
=
;
нормализацией
получаем
(
)
3
1/ 3,1/ 3,1/ 3
T
x
=
;
(
)
3
2 / 3, 4 / 3, 1/ 3
T
Ax
=
и нормализацией получаем
(
)
4
2 / 7, 4 / 7, 1/ 7
T
x
=
, что то же са-
мое, что и
1
x
с зацикливанием вместо сходимости.
7.4. ВЫЧИСЛЕНИЕ СОБСТВЕННОГО ВЕКТОРА
Вычисление главного собственного вектора основано на использовании теоре-
мы 7.13. Она утверждает, что нормализованные строчные суммы степеней прими-
тивной матрицы (и, следовательно, положительной матрицы) в пределе дают иско-
мый собственный вектор. Поэтому краткий вычислительный способ получения дан-
ного вектора – возводить матрицу в степени, каждая из которых представляет собой
квадрат предыдущей. Строчные суммы вычисляются и нормализуются. Вычисления
прекращаются, когда разность между этими суммами в двух последовательных вы-
числениях меньше заранее заданной величины.
7.5. СОГЛАСОВАННОСТЬ
Обратносимметричные неотрицательные матрицы могут иметь комплексные соб-
ственные значения. Следовательно, они не допускают просто общей характеристи-
ки. Однако поскольку максимальное собственное значение лежит между наиболь-
шей и наименьшей из строчных сумм, согласованная матрица имеет собственное
значение, равное сумме любого из ее столбцов. Как будет показано, малое возму-
щение не сильно меняет максимальное собственное значение и остальные собствен-
ные значения находятся в окрестности нуля, причем их сумма – действительное чис-
ло.
Выбор возмущения, наиболее соответствующего описанию влияния несогласо-
ванности на вычисляемый собственный вектор, зависит от психологического про-
цесса, имеющего место при заполнении матрицы попарных сравнений исходных