ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 21.10.2020
Просмотров: 432
Скачиваний: 2
www.uchites.ru
6
.
8388
,
0
cos
;
5445
,
0
sin
;
5758
,
0
46
,
2
19
,
3
819
,
0
2
2
1
)
2
(
)
2
(
)
2
(
=
=
=
−
⋅
=
ϕ
ϕ
ϕ
actg
;
38
,
9
232
,
0
1565
,
0
232
,
0
929
,
1
0003
,
0
1565
,
0
0003
,
0
706
,
3
;
1
0
0
0
8388
,
0
5445
,
0
0
5445
,
0
8388
,
0
)
2
(
)
2
(
)
2
(
)
3
(
)
2
(
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
=
=
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
−
=
U
A
U
A
U
T
( )
ε
<
=
+
+
=
2
/
1
2
/
1
2
2
2
)
3
(
07839
,
0
)
232
,
0
1565
,
0
0003
,
0
(
A
t
.
Таким
образом
в
качестве
искомых
собственных
значений
могут
быть
приняты
диагональные
элементы
матрицы
)
3
(
A
:
.
38
,
9
;
929
,
1
;
706
,
3
3
2
1
≈
≈
≈
λ
λ
λ
Собственные
векторы
определяются
из
произведения
;
58
,
0
2209
,
0
78
,
0
;
7
,
0
398
,
0
58
,
0
6
,
0
7625
,
0
2209
,
0
361
,
0
5064
,
0
78
,
0
1
)
2
(
)
1
(
)
0
(
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
−
=
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
−
−
−
=
x
U
U
U
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
−
−
=
398
,
0
7625
,
0
5064
,
0
2
x
;
.
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
=
7
,
0
6
,
0
361
,
0
3
x
Полученные
собственные
векторы
ортогональны
в
пределах
заданной
точности
,
т
.
е
.
(
)
(
)
(
)
.
0039
,
0
,
;
0081
,
0
,
;
00384
,
0
,
3
2
3
1
2
1
−
=
=
−
=
x
x
x
x
x
x
1 . 2 . 3 .
Ч а с т и ч н а я
п р о б л е м а
с о б с т в е н н ы х
з н а ч е н и й
и
с о б с т в е н н ы х
в е к т о р о в
м а т р и ц ы
.
С т е п е н н о й
м е т о д
Рассмотренный
метод
вращения
решает
полную
проблему
собственных
значений
и
собственных
векторов
матриц
(
симметрических
)
в
том
смысле
,
что
определяются
все
собственные
значения
и
собственные
векторы
.
Зачастую
не
нужно
находить
все
собственные
значения
(
спектр
)
и
все
собственные
векторы
,
а
необходимо
найти
максимальное
и
минимальное
из
них
.
Существует
степенной
метод
по
определению
спектрального
радиуса
матрицы
,
т
.
е
.
максимального
собственного
значения
матрицы
,
и
соответствующего
ему
собственного
вектора
.
Пусть
дана
матрица
A
и
пусть
ее
собственные
значения
упорядочены
по
абсолютным
величинам
:
n
λ
λ
λ
≥
≥
>
...
2
1
(1.25)
www.uchites.ru
7
Тогда
,
выбрав
некоторый
вектор
,
например
,
вектор
,
компоненты
которого
равны
единице
,
можно
для
определения
)
0
(
y
( )
T
y
)
1
...
1
1
(
0
=
λ
1
построить
следующий
итерационный
процесс
:
y
Ay
( )
( )
1
0
=
,
λ
1
1
1
0
( )
( )
( )
=
y
y
j
j
y
Ay
( )
( )
2
1
=
,
λ
1
2
2
1
( )
( )
( )
=
y
y
j
j
;
(1.26)
………………………………………
y
Ay
k
k
( )
(
)
=
−
1
,
λ
1
1
( )
( )
(
)
k
j
k
j
k
y
y
=
−
;
где
,
-
соответствующие
компоненты
векторов
,
.
При
этом
в
качестве
номера
y
j
k
(
)
−
1
y
j
k
( )
y
k
(
)
−
1
y
k
( )
j
может
использоваться
любое
число
из
диапазона
j
n
=
1,
.
В
связи
с
тем
,
что
вектор
на
-
ой
итерации
может
быть
представлен
в
виде
,
рассматриваемый
итерационный
процесс
носит
название
"
степенной
метод
".
При
выполнении
условий
( 1.25 )
итерационный
процесс
сходится
к
искомому
собственному
значению
y
k
( )
k
y
Ay
A y
k
k
k
( )
(
)
( )
=
=
−
1
0
λ
1
и
соответствующему
собственному
вектору
,
причем
скорость
сходимости
определяется
отношением
λ
λ
2
1
(
чем
оно
меньше
,
тем
выше
скорость
сходимости
).
В
качестве
критерия
завершения
вычислений
используется
следующее
условие
:
ε
( )
k
=
λ
λ
1
1
1
( )
(
)
k
k
−
≤
−
ε
,
где
ε
-
задаваемая
вычислителем
точность
расчета
.
Пример
1.8.
Вычислить
спектральный
радиус
матрицы
=
A
5 1
2
1
4 1
2 1
3
⎛
⎝
⎜
⎜
⎜
⎞
⎠
⎟
⎟
⎟
с
точностью
ε
=
0 1
,
.
В
качестве
начального
приближения
собственного
вектора
возьмем
.
y
T
( )
(
)
0
111
=
Реализуем
итерационный
процесс
(2.90),
полагая
j
=
1
.
(
)
y
Ay
T
( )
( )
1
0
8
6
6
=
=
,
λ
1
1
1
1
1
0
8
1
8
( )
( )
( )
=
= =
y
y
;
(
)
y
Ay
T
( )
( )
2
1
58
38
40
=
=
,
λ
1
2
1
2
1
1
58
8
7 25
( )
( )
( )
,
=
=
=
y
y
;
ε
( )
2
=
λ
λ
1
2
1
1
0 75
( )
( )
,
−
=
>
ε
;
www.uchites.ru
8
(
)
y
Ay
T
( )
( )
3
2
480
250
274
=
=
,
λ
1
3
1
3
1
2
480
58
7 034
( )
( )
( )
,
=
=
=
y
y
;
ε
(3)
=
λ
λ
1
3)
1
2
0 216
(
( )
,
−
=
>
ε
;
(
)
y
Ay
T
( )
( )
4
3
2838 1682 1888
=
=
,
λ
1
4
1
4
1
3
2838
408
6 9559
( )
( )
( )
,
=
=
=
y
y
;
ε
( )
4
=
λ
λ
1
4
1
3
0 078
( )
( )
,
−
=
<
ε
.
Таким
образом
,
полученное
на
4-
ой
итерации
значение
=6,9559
удовлетворяет
заданной
точности
и
может
быть
взято
в
качестве
приближенного
значения
λ
1
4
( )
λ
1
.
Искомое
значение
спектрального
радиуса
ρ
λ
( )
max
A
i
i
=
=
1
λ
= 6,9559.
Рассмотренный
выше
пример
наглядно
иллюстрирует
существенный
недостаток
алгоритма
(1.26),
связанный
с
сильным
возрастанием
компонентов
итерируемого
вектора
в
ходе
итерационного
процесса
.
Видно
,
что
y
k
( )
y
y
j
k
j
k
( )
(
)
−
≈
1
1
λ
.
Во
избежание
неограниченного
возрастания
(
при
λ
1
1
>
)
или
убывания
(
при
λ
1
1
<
)
компонентов
по
мере
увеличения
числа
итераций
y
k
( )
k
обычно
при
проведении
компьютерных
расчетов
применяется
степенной
метод
с
нормировкой
итерируемого
вектора
.
С
этой
целью
алгоритм
(2.89)
модифицируется
следующим
образом
:
z
Ay
k
k
( )
(
)
=
−
1
,
λ
1
1
( )
( )
(
)
k
j
k
j
k
z
y
=
−
,
y
z
z
k
k
k
( )
( )
( )
=
(1.27)
При
этом
в
качестве
начального
приближения
берется
вектор
с
единичной
нормой
.
y
( )
0
Широко
распространена
также
версия
степенного
метода
,
использующая
скалярные
произведения
[2]:
z
Ay
k
k
( )
(
)
=
−
1
,
y
z
z
k
k
k
( )
( )
( )
=
,
(1.28)
λ
1
( )
( )
( )
(
,
k
k
k
y
Ay
=
)
ЗАДАЧИ
Используя
степенной
метод
,
с
точностью
ε
=
0 1
,
оценить
спектральный
радиус
симметрических
матриц
,
заданных
в
разделе
1.2.2.
Сравнить
значение
λ
1
и
соответствующий
ему
собственный
вектор
с
результатами
,
полученными
в
разделе
1.2.2.
методом
вращений
.
www.uchites.ru
9
1.2.4. QR-
алгоритм
нахождения
собственных
значений
матриц
При
решении
полной
проблемы
собственных
значений
для
несимметричных
матриц
эффективным
является
подход
,
основанный
на
приведении
матриц
к
подобным
,
имеющим
треугольный
или
квазитреугольный
вид
.
Одним
из
наиболее
распространенных
методов
этого
класса
является
QR-
алгоритм
,
позволяющий
находить
как
вещественные
,
так
и
комплексные
собственные
значения
.
В
основе
QR-
алгоритма
лежит
представление
матрицы
в
виде
,
где
-
ортогональная
матрица
(
),
а
QR
A
=
Q
T
Q
Q
=
−
1
R
-
верхняя
треугольная
.
Такое
разложение
существует
для
любой
квадратной
матрицы
.
Одним
из
возможных
подходов
к
построению
QR
разложения
является
использование
преобразования
Хаусхолдера
,
позволяющего
обратить
в
нуль
группу
поддиагональных
элементов
столбца
матрицы
.
Преобразование
Хаусхолдера
осуществляется
с
использованием
матрицы
Хаусхолдера
,
имеющей
следующий
вид
:
T
T
vv
v
v
E
H
2
−
=
,
(1.29)
где
-
произвольный
ненулевой
вектор
-
столбец
,
v
E
-
единичная
матрица
,
-
квадратная
матрица
того
же
размера
.
T
vv
Легко
убедиться
,
что
любая
матрица
такого
вида
является
симметричной
и
ортогональной
.
При
этом
произвол
в
выборе
вектора
дает
возможность
построить
матрицу
,
отвечающую
некоторым
дополнительным
требованиям
.
v
Рассмотрим
случай
,
когда
необходимо
обратить
в
нуль
все
элементы
какого
-
либо
вектора
кроме
первого
,
т
.
е
.
построить
матрицу
Хаусхолдера
такую
,
что
Hb
b
=
~
,
,
T
n
b
b
b
b
)
,...,
,
(
2
1
=
T
b
b
)
0
,...,
0
,
~
(
~
1
=
.
Тогда
вектор
определится
следующим
образом
:
v
1
2
1
)
(
e
b
b
sign
b
v
+
=
,
(1.30)
где
2
/
1
2
2
⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
=
∑
i
i
b
b
-
евклидова
норма
вектора
,
.
T
e
)
0
,...,
0
,
1
(
1
=
www.uchites.ru
10
Применяя
описанную
процедуру
с
целью
обнуления
поддиагональных
элементов
каждого
из
столбцов
исходной
матрицы
,
можно
за
фиксированное
число
шагов
получить
ее
QR –
разложение
.
Рассмотрим
подробнее
реализацию
данного
процесса
.
Положим
и
построим
преобразование
Хаусхолдера
(
A
A
=
0
1
H
0
1
1
A
H
A
=
),
переводящее
матрицу
в
матрицу
с
нулевыми
элементами
первого
столбца
под
главной
диагональю
:
0
A
1
A
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎝
⎛
=
0
0
2
0
1
0
2
0
22
0
21
0
1
0
12
0
11
0
...
...
...
...
...
...
nn
n
n
n
n
a
a
a
a
a
a
a
a
a
A
⎯→
⎯
1
H
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎝
⎛
=
1
1
2
1
2
1
22
1
1
1
12
1
11
1
0
...
...
...
...
...
0
...
nn
n
n
n
a
a
a
a
a
a
a
A
Ясно
,
что
матрица
Хаусхолдера
должна
определяться
по
первому
столбцу
матрицы
,
т
.
е
в
качестве
вектора
в
выражении
(1.30)
берется
вектор
.
Тогда
компоненты
вектора
вычисляются
следующим
образом
:
1
H
0
A
b
T
n
a
a
a
)
,...,
,
(
0
1
0
21
0
11
v
2
/
1
1
2
0
1
0
11
0
11
1
1
)
(
)
(
⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
+
=
∑
=
n
j
j
a
a
sign
a
v
,
0
1
1
i
i
a
v
=
,
n
i
,
2
=
.
Матрица
Хаусхолдера
вычисляется
согласно
(1.29):
1
H
1
1
1
1
1
2
v
v
v
v
E
H
T
T
−
=
.
На
следующем
,
втором
,
шаге
рассматриваемого
процесса
строится
преобразование
Хаусхолдера
(
2
H
1
2
2
A
H
A
=
) ,
обнуляющее
расположенные
ниже
главной
диагонали
элементы
второго
столбца
матрицы
.
Взяв
в
качестве
вектора
вектор
размерности
1
A
b
T
n
a
a
a
)
,...,
,
(
1
2
1
32
1
22
1
−
n
,
получим
следующие
выражения
для
компонентов
вектора
v
:
0
2
1
=
v
,
2
/
1
2
2
1
2
1
22
1
22
2
2
)
(
)
(
⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
+
=
∑
=
n
j
j
a
a
sign
a
v
,
1
1
2
i
i
a
v
=
,
n
i
,
3
=
.