ВУЗ: Омский государственный технический университет
Категория: Книга
Дисциплина: Методы оптимальных решений
Добавлен: 12.02.2019
Просмотров: 13035
Скачиваний: 110
241
1
1
1
2
2
1 2
3 4
w
w
w
w
λ
=
,
или
1
2
1 1
2
w
w
w
λ
+
=
,
откуда
1
2
1
2
3
4
w
w
w
λ
+
=
.
Так как матрица
1
A
I
λ
−
– вырожденная, существует зависимость между её стро-
ками, и поэтому второе уравнение не содержит новой информации. Собственный
вектор
w
получается в результате присваивания произвольного значения
2
w
и вы-
числения
1
w
согласно полученному выше соотношению. Присвоим
2
w
значение 1.
Тогда имеем
1
2
, 1
1
w
λ
=
−
.
Можно нормализовать
w
, приравнивая сумму коэффициентов единице. Разделим
каждый коэффициент на сумму
1
2
w
w
+
, которая равна
(
)(
)
1
1
1
1
λ
λ
+
−
. Получим ре-
зультирующий нормализованный вектор
1
1
1
1
2
,
1
1
λ
λ
λ
−
+
+
.
Поскольку умножение на постоянную не влияет на решение уравнения
Aw
w
λ
=
,
будем рассматривать собственные векторы
w
всегда в нормализованном виде. Ана-
логично можно получить собственный вектор, соответствующий
2
λ
. Собственные
значения как корни любого полиномиального уравнения можно получить, используя
различные стандартные численные методы. В настоящее время существуют пакеты
компьютерных программ для нахождения этих корней. Для уравнения, являющегося
характеристическим уравнением матрицы, существуют компьютерные программы,
которые для данной матрицы находят собственные векторы.
Собственные значения матрицы, будучи корнями ее характеристического урав-
нения, могут быть комплексными числами и, следовательно, попарно комплексно-
сопряженными. Напомним, что комплексное число имеет вид
a ib
+
, где
1
i
= −
,
a
и
b
– действительные числа. Модуль такого числа обозначается
a ib
+
и равен
(
)
1/ 2
2
2
a
b
+
. Если элементы матрицы – действительные и она симметричная, все ее
собственные значения действительны. Собственные ректоры, соответствующие раз-
личным собственным значениям, ортогональны. Этим же свойством обладает эрми-
това матрица. Матрицы
A
и
T
A
имеют одни и те же собственные значения, но в
общем случае не одни и те же собственные векторы.
Следующая теорема (см. [48]) может быть применена к
i
ij
ij
j
w
a
w
ε
=
,
если использовать непрерывное преобразование, например логарифмическую
функцию. Теорема утверждает, что собственные значения матрицы непрерывно за-
висят от ее коэффициентов (это то же, что непрерывная зависимость корней поли-
нома от его коэффициентов).
242
Теорема. Если произвольная матрица
( )
ij
A
a
=
имеет собственные значения
1
2
,
,
,
s
λ λ
λ
…
, где кратность
j
λ
есть
j
m
с
1
s
j
j
m
n
=
=
∑
, то при заданном, достаточно ма-
лом
0
ε
>
существует
( )
0
δ δ ε
=
>
, такое, что при
ij
ij
ij
ij
a
a
ε
ε
δ
+
−
=
≤
для
,
1,
,
i j
n
= …
матрица
(
)
ij
ij
B
a
ε
=
+
имеет ровно
j
m
собственных значений в окруж-
ности
j
µ λ
ε
−
<
для каждого
1,
,
j
s
= …
,
1
,
,
n
µ
µ
…
являются собственными значе-
ниями
B
.
Доказательство. Определим
(
)
(
)
,
det
f
B
I B
µ
µ
=
−
.
Пусть
1
2
0
min
1
i
j
i
j s
ε
λ λ
=
−
≤ < ≤
и
0
ε ε
<
. Окружности
:
j
j
C
µ λ
ε
−
=
,
1,
,
j
s
= …
–
непересекающиеся. Пусть
(
)
min
,
j
r
f
A
µ
=
для
µ
на
j
C
. Заметим, что
(
)
min
,
f
A
µ
определен, так как
f
– непрерывная функция
µ
. Также
0
j
r
>
, по-
скольку корни
(
)
,
0
f
A
µ
=
являются центрами окружностей.
Определитель
(
)
,
f
B
µ
– непрерывная функция
2
1
n
+
переменных и
ij
ij
a
ε
+
,
,
1,
,
i j
n
= …
, и, следовательно, для некоторых
0
δ
>
,
(
)
,
0
f
B
µ
≠
, для
µ
на любой
j
C
,
1,
,
j
s
= …
, если
ij
ε
δ
≤
,
,
1,
,
i j
n
= …
. Из теории функций комплексной пере-
менной известно, что число
j
m
корней
µ
уравнения
(
)
,
0
f
B
µ
=
, лежащих внутри
окружности
j
C
, определяется формулой
( )
(
)
(
)
,
1
2
,
j
j
C
f
B
n B
d
i
f
B
µ
µ
π
µ
′
=
∫
,
1,
,
j
s
= …
,
которая из-за
(
)
,
0
f
B
µ
≠
является непрерывной функцией
2
1 n
+
переменных в
j
µ λ
ε
−
=
,
ij
ε
δ
≤
,
,
1,
,
i j
n
=
…
. В частности, это непрерывная функция
ij
ij
a
ε
+
при
ij
ε
δ
≤
.
Теперь для
B A
=
по предположению имеем
( )
j
j
n A
m
=
,
1,
,
j
s
=
…
. Так как ин-
теграл непрерывен, не может быть скачка с
( )
j
n A
на
( )
j
n B
, они должны быть рав-
ны и иметь общее значение
j
m
,
1,
,
j
s
=
…
для всех
B
с
ij
ij
ij
a
a
ε
δ
+
−
≤
,
,
1,
,
i j
n
= …
.
Существуют различные способы оценки
max
λ
, здесь представлен один из хорошо
известных:
(
)
1/ 2
2
max
lim
k
k
k
trA
λ
→∞
=
.
Например, для обратносимметричной матрицы размерности
3 3
×
4
12 23
13
13
12 23
4
4
3 19
a a
a
trA
a
a a
=
+
+
.
243
Аналогичное вычисление для обратносимметричной матрицы размерности
4 4
×
дает
4
12 23
13
13 34
12 24
14
14
13
12 23
14
12 24
14
13 34
4
4
4
4
4
4
4 34
a a
a
a a
a a
a
a
trA
a
a a
a
a a
a
a a
=
+
+
+
+
+
+
+
13 34
13 24
13 24
12 23 34
12 24
14
13 34
12 24
14 23
14 23
14
12 23 34
a a
a a
a a
a a a
a a
a
a a
a a
a a
a a
a
a a a
+
+
+
+
+
+
.
Отметим, что слагаемые компенсируют друг друга, так как коэффициент в числи-
теле одного члена также появляется в знаменателе следующего. Поэтому возраста-
ние этого коэффициента увеличивает один член и уменьшает другой. В общем слу-
чае это неверно для необратносимметричных матриц.
Часто встречаются функции матрицы
A
, такие, как степени и экспоненты. Имеет
смысл рассмотреть такие функции. Существует следующая теорема из этой области,
принадлежащая Сильвестру (см. [49]):
( )
(
)
( )
( ) ( )
1
1
0
!
i
m
m
k
m
i
i
i
i
m
A
I
f A
f
Z
m
λ
λ
λ
−
=
=
−
∑ ∑
.
Здесь
k
– количество различных характеристических значений матрицы
A
;
i
m
– кратность
i
-го корня
i
λ
;
( )
( )
m
i
f
λ
– (формальная) производная
f
m
-го порядка,
вычисленная при
i
λ
;
( )
i
Z
λ
– полные ортогональные идемпотентные матрицы мат-
рицы
A
, т. е. они обладают свойствами
( )
1
k
i
i
Z
I
λ
=
=
∑
;
( )
( )
0
i
j
Z
Z
λ
λ
=
,
i
j
≠
;
( )
( )
2
i
j
Z
Z
λ
λ
=
,
где
I
и
O
– единичная и нулевая матрицы соответственно.
При различных характеристических значениях для матрицы
A
порядка
n
имеем
[64]
( )
( ) ( )
1
n
i
i
i
f A
f
Z
λ
λ
=
=
∑
,
где
( )
(
)
(
)
i
j i
i
i
j
j i
I A
Z
λ
λ
λ λ
≠
≠
−
=
−
∏
∏
.
Для иллюстрации того, как это получается когда
f
является полиномом матрицы
A
, отметим, что из полинома
n
-й степени
0
I A
λ
− =
матрица
n
A
может быть вы-
ражена через низшие степени
A
и, следовательно,
f
всегда может быть сведена к
полиному степени, не превышающей
1
n
−
. Если написать
( )
(
)
1
1
n
i
j
i
j
j i
f A
A
I
α
λ
=
=
≠
=
−
∑ ∏
и умножить выражение справа последовательно на
i
v
,
1,
,
i
n
= …
– характери-
стический вектор
i
λ
с учетом того, что
i
i i
Av
v
λ
=
, и, следовательно,
( )
( )
i
i
i
f A v
f
v
λ
=
, то получим
244
( )
(
)
i
i
i
j
j i
f
λ
α
λ λ
≠
=
−
∏
,
что и дает искомый результат.
При
( )
( )
exp
f A
At
=
и различных характеристических значениях
A
имеем спек-
тральное разложение
( )
f A
, заданное выражением
( )
( ) ( )
1
exp
n
i
i
i
f A
t Z
λ
λ
=
=
∑
.
Случай кратных характеристических корней выводится из иного варианта теоре-
мы Сильвестра. Если напишем для краткости
( )
( )
1
k
i
i
f A
T
λ
=
=
∑
,
где
k
– количество различных корней, тогда
( )
( )
( )
( )
( )
( )
( )
1
2
3
!
i
i
i
i
i
i
m
i
i
m
i
m
i
f
T
f
Z
f
Z
Z
z
λ
λ
λ
λ
λ
λ
λ
−
−
−
′′
′
=
+
+
+…
Здесь
i
m
относится к кратности корня
i
λ
, а
( )
( )
( )
1
!
i
i
i
i
i
m
m
i
m
i
m
F
d
Z
m d
λ λ
λ
λ
λ
λ
=
=
∆
,
где
( )
( )
(
)
(
)
1
1
! 1
i
n m
m m
m
i
i
i
j i
F
m
I A
I A
λ
λ
λ
− −
− −
≠
=
−
−
−
∏
есть производная
F
порядка
m
, а
( )
(
)
i
m
i
j i
λ
λ λ
≠
∆
=
−
∏
.
Заметим, например, что
( )
( )
( )
( ) ( )
( ) ( )
( )
1
2
F
F
F
d
Z
d
λ
λ
λ
λ
λ
λ
λ
λ
λ
′
′
∆
−
∆
=
=
∆
∆
.
Рассмотрим систему
x x y
= +
,
y x y
= −
,
или просто
X
AX
=
,
x
X
y
=
,
1 1
1
1
A
=
−
.
Исходя из формулы Сильвестра при
1
2
λ
=
,
2
2
λ
= −
, имеем
( )
( ) (
)
( ) (
)
1
2
2
1
1
2
2
1
exp
exp
exp
t
t
At
A
I
A
I
λ
λ
λ
λ
λ λ
λ λ
=
−
+
−
−
−
,
и применим ее для получения решения системы.
Аналогично можно показать, что если
2 1
1 2
B
=
,
то
245
100
100
100
100
100
3
1 3
1
2
2
3
1 3
1
2
2
B
+
−
=
−
+
.
ПРИЛОЖЕНИЕ 2
НЕКОТОРЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ
Определения
Граф – это множество точек
V
, вершин или узлов, и множество простых кривых
E
, граней или ребер, связь которых с вершинами, называемыми его концевыми точ-
ками, описывается определенным правилом. Говорят, что вершины инцидентны
ребру. Открытое ребро инцидентно в точности двум различным вершинам. Замкну-
тое ребро (называемое петлей) инцидентно в точности одной вершине и, следова-
тельно, его концевые точки совпадают. Ребра не имеют общих точек, за исключени-
ем вершин.
На рис. П.1
1
v
и
2
v
– примеры вершин;
1
e
– петля, концевая точка которой –
5
v
;
2
e
– открытое ребро с концевыми точками
2
v
и
3
v
.
Рис. П.1
Рис. П.2