ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 21.10.2020
Просмотров: 435
Скачиваний: 2
www.uchites.ru
11
Повторяя
процесс
раз
,
получим
искомое
разложение
,
где
1
−
n
QR
A
=
T
n
n
H
H
H
Q
)
...
(
0
2
1
−
−
=
1
2
1
...
−
=
n
H
H
H
,
1
−
=
n
A
R
.
Следует
отметить
определенное
сходство
рассматриваемого
процесса
с
алгоритмом
Гаусса
.
Отличие
заключается
в
том
,
что
здесь
обнуление
поддиагональных
элементов
соответствующего
столбца
осуществляется
с
использованием
ортогонального
преобразования
.
Процедура
-
разложения
многократно
используется
в
-
алгоритме
вычисления
собственных
значений
.
Строится
следующий
итерационный
процесс
:
QR
QR
A
A
=
)
0
(
,
)
0
(
)
0
(
)
0
(
R
Q
A
=
-
производится
QR
-
разложение
,
)
0
(
)
0
(
)
1
(
Q
R
A
=
-
производится
перемножение
матриц
,
…………………
)
(
)
(
)
(
k
k
k
R
Q
A
=
-
разложение
,
)
(
)
(
)
1
(
k
k
k
Q
R
A
=
+
перемножение
.
Таким
образом
,
каждая
итерация
реализуется
в
два
этапа
.
На
первом
этапе
осуществляется
разложение
матрицы
)
(
k
A
в
произведение
ортогональной
и
верхней
треугольной
)
(
k
Q
)
(
k
R
матриц
,
а
на
втором
–
полученные
матрицы
перемножаются
в
обратном
порядке
.
Нетрудно
показать
подобие
матриц
)
1
(
+
k
A
и
)
(
k
A
.
Действительно
,
учитывая
ортогональность
(
),
можно
записать
:
)
(
k
Q
E
Q
Q
k
T
k
=
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
1
(
k
k
T
k
k
k
k
T
k
k
k
k
Q
A
Q
Q
R
Q
Q
Q
R
A
=
=
=
+
.
Аналогично
можно
показать
,
что
любая
из
матриц
)
(
k
A
ортогонально
подобна
матрице
A
.
При
отсутствии
у
матрицы
кратных
собственных
значений
последовательность
)
(
k
A
сходится
к
верхней
треугольной
матрице
(
в
случае
,
когда
все
собственные
значения
вещественны
)
или
к
верхней
квазитреугольной
матрице
(
если
имеются
комплексно
-
сопряженные
пары
собственных
значений
).
Таким
образом
,
каждому
вещественному
собственному
значению
будет
соответствовать
столбец
со
стремящимися
к
нулю
поддиагональными
элементами
и
в
качестве
критерия
сходимости
итерационного
процесса
для
таких
собственных
www.uchites.ru
12
значений
можно
использовать
следующее
неравенство
:
.
При
этом
соответствующее
собственное
значение
принимается
равным
диагональному
элементу
данного
столбца
.
ε
≤
⎟
⎠
⎞
⎜
⎝
⎛
∑
+
=
2
/
1
1
2
)
(
)
(
n
m
l
k
lm
a
Каждой
комплексно
-
сопряженной
паре
соответствует
диагональный
блок
размерностью
2
х
2,
т
.
е
.
матрица
имеет
блочно
-
диагональную
структуру
.
Принципиально
то
,
что
элементы
этих
блоков
изменяются
от
итерации
к
итерации
без
видимой
закономерности
,
в
то
время
как
комплексно
-
сопряженные
собственные
значения
,
определяемые
каждым
блоком
,
имеют
тенденцию
к
сходимости
.
Это
обстоятельство
необходимо
учитывать
при
формировании
критерия
выхода
из
итерационного
процесса
.
Если
в
ходе
итераций
прослеживается
комплексно
-
сопряженная
пара
собственных
значений
,
соответствующая
блоку
,
образуемому
элементами
)
(
k
A
j
-
го
и
-
го
столбцов
,
то
,
несмотря
на
значительное
изменение
в
ходе
итераций
самих
этих
элементов
,
собственные
значения
,
соответствующие
данному
блоку
и
определяемые
из
решения
квадратного
уравнения
,
начиная
с
некоторого
,
отличаются
незначительно
.
В
качестве
критерия
окончания
итераций
для
таких
блоков
может
быть
использовано
следующее
условие
)
1
(
+
j
)
(
1
1
)
(
1
)
(
1
)
(
,
,
,
k
j
j
k
j
j
k
jj
k
jj
a
a
a
a
+
+
+
+
)
(
1
)
(
1
)
(
)
(
1
1
)
(
)
(
)
)(
(
k
j
j
k
jj
k
k
j
j
k
k
jj
a
a
a
a
+
+
+
+
=
−
−
λ
λ
k
ε
λ
λ
≤
−
−
)
1
(
)
(
k
k
.
Замечание
.
Существенным
недостатком
рассмотренного
выше
алгоритма
является
большое
число
операций
(
пропорционально
,
где
-
размерность
матрицы
),
необходимое
для
-
факторизации
матрицы
на
каждой
итерации
.
Эффективность
-
алгоритма
может
быть
повышена
,
если
предварительно
с
помощью
преобразования
подобия
привести
матрицу
к
верхней
Хессенберговой
форме
,
в
которой
равны
нулю
все
элементы
,
находящиеся
ниже
главной
диагонали
за
исключением
элементов
первой
поддиагонали
.
Иными
словами
предварительно
производится
следующая
операция
:
3
n
n
QR
QR
AH
H
A
T
=
)
0
(
,
где
)
0
(
A
-
матрица
Хессенберга
,
имеющая
следующую
структуру
(
знак
x
обозначает
ненулевые
элементы
):
www.uchites.ru
13
,
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
⎛
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
0
0
0
0
...
...
...
...
...
0
0
...
0
...
...
Здесь
принципиально
то
,
что
в
дальнейшем
,
в
ходе
-
итераций
,
матрицы
QR
)
(
k
A
сохраняют
верхнюю
Хессенбергову
форму
,
что
позволяет
более
экономно
проводить
их
-
разложение
.
Подробное
изложение
данного
вопроса
можно
найти
,
например
,
в
[2].
QR
Пример
1.9.
Используя
преобразование
Хаусхолдера
,
построить
-
разложение
матрицы
.
QR
A
=
⎛
⎝
⎜
⎜
⎜
⎞
⎠
⎟
⎟
⎟
1
3 1
1 1
4
4
3 1
Решение
.
1.
Положим
и
найдем
ортогональную
матрицу
Хаусхолдера
,
такую
что
в
матрице
все
поддиагональные
элементы
первого
столбца
равны
нулю
.
С
этой
целью
компоненты
вектора
определим
,
используя
элементы
первого
столбца
матрицы
:
A
A
=
0
1
H
0
1
1
A
H
A
=
v
0
A
2
/
1
3
1
2
0
1
0
11
0
11
1
1
)
(
)
(
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
+
=
∑
=
j
j
a
a
sign
a
v
=
1
1
=5,24,
1
4
2 1 2
+ + +
(
/
)
0
21
1
2
a
v
=
=1,
0
31
1
3
a
v
=
=4.
В
результате
получен
вектор
.
T
v
)
4
1
24
,
5
(
1
=
Найдем
соответствующую
этому
вектору
матрицу
Хаусхолдера
:
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
−
−
−
−
−
−
−
=
−
=
28
,
0
18
,
0
94
,
0
18
,
0
96
,
0
24
,
0
94
,
0
24
,
0
24
,
0
2
1
1
1
1
1
v
v
v
v
E
H
T
T
.
В
заключение
первого
шага
вычислим
матрицу
:
1
A
0
1
1
A
H
A
=
=
.
−
−
−
−
−
−
⎛
⎝
⎜
⎜
⎜
⎞
⎠
⎟
⎟
⎟
4 24
3 77
2 12
0
0 29
3 40
0
2 17
1 3
,
,
,
,
,
,
, 8
Таким
образом
,
после
первого
шага
получена
матрица
с
нулевыми
поддиагональными
элементами
в
первом
столбце
.
www.uchites.ru
14
1 2
2.
На
втором
шаге
проделаем
аналогичную
процедуру
,
обнуляя
поддиагональный
элемент
второго
столбца
.
0
2
1
=
v
,
2
/
1
3
2
2
2
2
1
22
1
22
2
2
)
(
)
(
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
+
=
∑
=
j
j
a
a
sign
a
v
=
=-2,48,
−
−
+
0 29
0 29
2 17
2
2
,
( ,
,
)
/
1
32
2
3
a
v
=
=-2,17.
Т
.
е
.
искомый
вектор
.
T
v
)
17
,
2
48
,
2
0
(
2
−
−
=
Далее
найдем
соответствующую
ему
матрицу
Хаусхолдера
:
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
−
−
−
=
−
=
13
,
0
99
,
0
0
99
,
0
13
,
0
0
0
0
1
2
2
2
2
2
2
v
v
v
v
E
H
T
T
и
вычислим
матрицу
:
2
A
1
2
2
A
H
A
=
=
.
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
−
−
−
−
56
,
3
0
0
91
,
0
19
,
2
0
12
,
2
77
,
3
24
,
4
Таким
образом
,
исходная
матрица
А
приведена
к
верхнему
треугольному
виду
,
т
.
е
.
получена
матрица
искомого
разложения
.
2
A
R
=
Результирующая
ортогональная
матрица
преобразования
получается
в
результате
перемножения
матриц
Q
2
,
1
,
=
i
H
i
:
2
1
H
H
Q
=
=
.
−
−
−
−
−
⎛
⎝
⎜
⎜
⎜
⎞
⎠
⎟
⎟
⎟
0 24
0 97
0 11
0 24
0 05
0 97
0 94
0 25
0 22
,
,
,
,
,
,
,
,
,
В
заключение
выпишем
окончательный
результат
A QR
=
в
явном
виде
:
A
=
⎛
⎝
⎜
⎜
⎜
⎞
⎠
⎟
⎟
⎟
1
3 1
1 1 4
4 3 1
=
х
.
−
−
−
−
−
⎛
⎝
⎜
⎜
⎜
⎞
⎠
⎟
⎟
⎟
0 24
0 97
0 11
0 24
0 05
0 97
0 94
0 25
0 22
,
,
,
,
,
,
,
,
,
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
−
−
−
−
56
,
3
0
0
91
,
0
19
,
2
0
12
,
2
77
,
3
24
,
4
www.uchites.ru
15
Пример
1.10.
С
помощью
-
алгоритма
вычислить
собственные
значения
матрицы
QR
A
из
предыдущего
примера
с
точностью
ε
=
0 01
,
.
Решение
.
1.
Положим
A
A
( )
0
=
и
найдем
-
разложение
этой
матрицы
.
QR
A
Q R
( )
( )
( )
0
0
=
0
Эта
процедура
подробно
рассмотрена
в
предыдущем
примере
.
Получены
следующие
:
Q
R
( )
( )
,
0
0
Q
( )
0
=
−
−
−
−
−
⎛
⎝
⎜
⎜
⎜
⎞
⎠
⎟
⎟
⎟
0 24
0 97
0 11
0 24
0 05
0 97
0 94
0 25
0 22
,
,
,
,
,
,
,
,
,
,
R
( )
0
=
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
−
−
−
−
56
.
3
0
0
91
,
0
19
,
2
0
12
,
2
77
,
3
24
,
4
.
Матрицу
A
( )
1
определим
перемножением
полученных
в
результате
-
разложения
матриц
в
обратном
порядке
:
QR
A
R Q
( )
( )
( )
1
0
=
0
A
( )
,
,
,
,
,
,
,
,
,
1
3 89
3 75
2 74
1 38
0 12
1 92
3 35
0 9
0 77
=
−
−
−
−
−
⎛
⎝
⎜
⎜
⎜
⎞
⎠
⎟
⎟
⎟
.
Первая
итерация
завершена
.
Поддиагональные
элементы
матрицы
A
( )
1
достаточно
велики
,
поэтому
итерационный
процесс
необходимо
продолжить
.
2.
а
).
Находим
-
разложение
(
используя
преобразование
Хаусхолдера
аналогично
примеру
):
QR
A
Q R
( )
( )
( )
1
1
=
1
Q
( )
1
=
−
−
−
⎛
⎝
⎜
⎜
⎜
⎞
⎠
⎟
⎟
⎟
0 73
0 68
0 05
0 26
0 21
0 94
0 63
0 7
0 33
,
,
,
,
,
,
,
,
,
,
R
( )
1
=
−
−
−
−
⎛
⎝
⎜
⎜
⎜
⎞
⎠
⎟
⎟
⎟
5 32
2 14
2 02
0
3 21
2 0
0
0
1 9
,
,
,
,
,
, 3
.
б
).
Перемножая
полученные
выше
матрицы
в
обратном
порядке
находим
матрицу
A
( )
2
:
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
−
−
−
=
64
,
0
36
,
1
22
,
1
37
,
2
08
,
2
09
,
2
09
,
1
75
,
1
72
,
5
)
2
(
A
.
Продолжая
итерационный
процесс
получим
соответственно
на
6-
ой
и
7-
ой
итерациях
следующие
матрицы
:
A
( )
,
,
,
,
,
,
,
,
,
6
6 34
0 94
0 73
0 034
2 53
1 69
0 023
1 86
0 81
=
−
−
−
−
⎛
⎝
⎜
⎜
⎜
⎞
⎠
⎟
⎟
⎟
,
.
A
( )
,
,
,
,
,
,
,
7
6 34
0 27
113
0 0014
2 01
2 58
0 0006
0 98
1 33
= −
−
−
−
⎛
⎝
⎜
⎜
⎜
⎞
⎠
⎟
⎟
⎟
,
,
Видно
,
что
поддиагональные
элементы
первого
столбца
становятся
достаточно
малыми
,
и
,
следовательно
,
диагональный
элемент
может
быть
принят
в
качестве
собственного
значения
.
В
то
же
время
отчетливо
прослеживается
комплексно
-
сопряженная
пара
собственных
значений
,
соответствующая
блоку
,
образуемому
элементами
второго
и
третьего
столбцов
a
.
Несмотря
a
11
7
( )
a
a
a
k
k
k
k
22
23
32
33
( )
( )
( )
( )
,
,
,