- •5.1. Характеристика итерационных методов
- •5.2. Приведение матрицы к почти треугольному виду
- •5.3. Разложение матрицы на произведение ортогональной и треугольной
- •5.4. QR-алгоритм определения собственных значений
- •5.5. Ускорение сходимости QR-алгоритма
- •5.6. Практическая организация вычислений в QR-алгоритме
- •5.7. Определение собственных векторов
- •5.8. Алгоритмы для симметричной проблемы собственных значений
- •5.8.1. Метод Якоби
- •5.8.2. Трехдиагональная QR-итерация
- •5.8.3. RQ-итерация
- •5.8.4. «Разделяй-и-властвуй»
- •5.8.5. Бисекция и обратная итерация
5.5. Ускорение сходимости QR-алгоритма
Так как скорость сходимости определяется отношениями собственных значений, для ускорения сходимости применим сдвиги. Тогда QR-алгоритм со сдвигами состоит в следующем. Для заданной матрицы А положить k 0 и выполнить:
1.Выбрать сдвиг sk вблизи некоторого собственного значения А.
2.Вычислить по схеме (5.8) QR-разложение для матрицы:
|
|
|
|
|
|
|
|
A k s |
k |
E Q k R k |
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3. Определить матрицу A k 1 : |
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
A k 1 R k Q k sk E . |
|
|
|
|
||||||||
4. Если сходимость к собственным значениям не достигнута, положить |
||||||||||||||||||
k k 1 и перейти к п.1. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
Матрицы |
A k |
и A k 1 в QR-алгоритме со сдвигами будут ортогонально |
||||||||||||||||
подобными: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A k 1 |
R |
k Q k s |
k |
E Q k T Q k R k Q k |
s |
k |
Q k T Q k |
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Q k T Q k R k |
s |
k |
E Q k |
Q k T A k Q k |
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Если матрица R k невырождена, то аналогично можно записать: |
||||||||||||||||||
A k 1 |
R k Q k s |
|
|
|
|
|
|
|
|
1 |
s |
|
1 |
|
||||
k |
E R k Q k R k R k |
k |
R k R k |
|||||||||||||||
R k Q k |
|
|
|
|
|
|
|
|
|
|
R k A k R k |
|
|
|
||||
R k s E R k |
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
1 |
|
|
|
|
|
|
|
|
|
k |
|
|
|
|
|
|
|
|
|
|
|
|
|
Утверждение: Если s |
k |
|
– точное собственное значение матрицы A k , |
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
то QR-итерация сойдется за один шаг. |
|
|
|||||||||||||||
Доказательство. Если |
sk является собственным значением матрицы |
|||||||||||||||||
A k , то матрица |
A k s |
k |
E |
– вырождена. Поэтому вырожденной будет матрица |
R k , следовательно, какой-то из ее диагональных элементов равен нулю. Пусть
это будет элемент r k 0 . Тогда последняя строка матрицы |
R k Q k |
будет |
nn |
|
|
нулевой, а последняя строка матрицы A k 1 R k Q k sk E совпадет с |
sk enT , |
где enT – последний столбец единичной матрицы порядка n. Другими словами, последняя строка в A k 1 – нулевая за исключением того, что в позиции (n, n) находится собственное значение sk . Это означает, что алгоритм сошелся:
матрица A k 1 имеет блочно-треугольный вид, в нижнем диагональном блоке размера 1 1 находится число sk . Ведущая главная подматрица A' порядка n 1
определяет новую меньшую спектральную задачу, которая может быть решена
QR-итерацией без какого-либо изменения |
собственного значения |
|
sk : |
|||
A' |
|
a |
|
|
|
|
A k 1 |
|
|
. |
|
|
|
0 |
|
sk |
|
|
|
|
Если |
s |
k |
не является точным собственным значением, то элемент |
a |
k 1 |
|
|
|
|
|
|
nn |
|
считается |
сошедшим, если левый нижний |
блок A k 1 достаточно |
мал. |
Поскольку матрица A k 1 получается из матрицы А ортогональным подобием, |
||||||||||||||||||||||||||
то A k 1 включает в себя ошибки округлений порядка O |
|
|
|
A |
|
|
|
. Таким образом, |
||||||||||||||||||
|
|
|
|
|||||||||||||||||||||||
любой поддиагональный элемент в A k 1 , по абсолютной величине меньший |
||||||||||||||||||||||||||
чем O |
|
|
|
A |
|
|
|
, |
мог быть нулем, поэтому его можно заменить на ноль. Т.е. для |
|||||||||||||||||
|
|
|
|
|||||||||||||||||||||||
|
|
a k 1 |
|
|
|
|
|
, j 1.. |
|
можно положить a k 1 0 . |
||||||||||||||||
|
|
|
A |
|
n 1 |
|||||||||||||||||||||
|
|
n, j |
|
|
|
|
|
|
|
n, j |
||||||||||||||||
|
|
Выбор |
|
sk вблизи вещественного собственного значения обеспечивает |
квадратичную сходимость, означающую, что на каждом шаге число верных разрядов приближения удваивается.
5.6. Практическая организация вычислений в QR-алгоритме
Пусть требуется определить все собственные значения матрицы А порядка n с точностью ε.
|
|
|
|
|
|
Вначале матрица приводится к верхней форме Хессенберга (5.1). К |
|||||||||||||||||||||||||||||
произвольным матрицам QR-итерация обычно не применяется. Это снижает |
|||||||||||||||||||||||||||||||||||
стоимость одного шага QR-итерации с O n3 |
до O n2 , а общую стоимость – с |
||||||||||||||||||||||||||||||||||
O n4 |
до O n3 . Если А – |
симметричная матрица, |
то одна будет приведена |
||||||||||||||||||||||||||||||||
трехдиагональной форме (5.2). В результате стоимость одного шага QR- |
|||||||||||||||||||||||||||||||||||
алгоритма снижается до величины O n . |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||
|
|
|
|
|
|
Затем к матрице А применяется QR-итерация со сдвигами. На шаге k в |
|||||||||||||||||||||||||||||
качестве сдвига выбираем элемент a k , т.е. |
|
s |
k |
a k |
. Поскольку a k |
|
n |
, то |
|||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
nn |
|
|
|
|
|
nn |
|
|
nn |
|
|
||
s |
k |
является приближением к |
n |
|
и скорость сходимости к нулю элемента a |
k |
|||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n,n 1 |
|||
будет |
высокой. Как только на |
некотором |
|
шаге |
|
k выполняется |
условие |
||||||||||||||||||||||||||||
|
a |
k 1 |
|
|
|
A |
|
|
, в качестве принимают |
|
a k |
и далее алгоритм применяют к |
|||||||||||||||||||||||
|
|
|
|
|
|
||||||||||||||||||||||||||||||
|
|
|
n,n 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n |
|
|
nn |
|
|
|
|
|
|
|
|||
|
|
A' a k , i, j |
|
. |
|
|
|
|
|
||||||||||||||||||||||||||
подматрице |
|
1..n 1 |
Так |
поступают до тех пор, пока |
порядок |
||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
ij |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
матрицы A' |
не станет равным 2. |
Для этой матрицы собственные значения |
|||||||||||||||||||||||||||||||||
определяются как решения квадратного уравнения. |
|
|
|
|
|
|
|||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
a11 |
|
|
a12 |
|
|
|
a11 a22 |
a12a21 0 |
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
a21 |
|
a22 |
|
|
|
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
a |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
a |
22 |
|
a |
a |
22 |
2 |
4a a |
21 |
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
1,2 |
11 |
|
|
|
|
11 |
|
|
|
|
12 |
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Если матрица имеет комплексные собственные значения, то выбор в качестве sk комплексного числа приводит к последующей комплексной
арифметике. Для вещественной матрицы это означает увеличение общей стоимости процесса примерно в 4 раза. Во избежание этого используют факт, что комплексные собственные значения вещественных матриц встречаются
|
|
|
|
|
|
|
|
|
|
|
|||
сопряженными парами. Поэтому сдвиги на |
sk |
и sk |
можно |
проводить |
|||||||||
совместно по следующей схеме, которую называют неявным QR- |
|||||||||||||
алгоритмом с двойным сдвигом : |
|
|
|
|
|
|
|
||||||
A k s |
k |
E Q k R k |
, |
|
|
|
|
|
|||||
|
|
|
|
|
Q k T A k Q k , |
|
|||||||
A k 1 R k Q k s |
E, так что A k 1 |
|
|||||||||||
k |
|
|
|
|
|
|
|
|
|
|
|
|
|
A k 1 |
|
|
E Q k 1 R k 1 , |
|
|
|
|
|
|||||
s |
|
|
|
|
|
|
|||||||
|
|
k |
|
|
|
|
|
|
|
|
|
|
|
A k 2 R |
k 1 Q k 1 |
|
|
|
|
|
|
|
|
||||
s |
E, |
|
|
|
|
|
|||||||
|
|
|
|
|
|
k |
|
|
|
|
|
|
|
так что A k 2 Q k 1 T A k 1 Q k 1 Q k 1 T Q k T A k Q k Q k 1 . |
|||||||||||||
Произведение Q k Q k 1 будет вещественным, следовательно, будет |
|||||||||||||
вещественной и матрица A k 2 . |
|
|
Это позволяет |
вести |
весь |
процесс в |
вещественной арифметике, рассматривая только вещественную часть сдвига sk
– Re sk и его модуль, т.е. |
|
|
|
|
|
. Для симметричной |
|
sk |
|
|
Re sk 2 Im sk 2 |
||
|
|
вещественной матрицы, все ее собственные значения вещественны, и этой проблемы не возникает.
5.7. Определение собственных векторов
Рассмотренные численные методы решения проблемы собственных значений лучше приспособлены к вычислению собственных значений, чем собственных векторов. Применение QR-алгоритма для нахождения собственных векторов требует дополнительно на каждом шаге вычислять и
запоминать |
матрицу |
результирующего |
преобразования |
подобия |
P k Q 0 Q k . Эта |
операция очень не |
выгодна, если |
необходимо |
определить только несколько собственных векторов. Кроме того, вычисление матрицы усложняет численный метод, т.к. теперь сложнее осуществить переход к матрицам меньшего размера при появлении нулевых поддиагональных элементов.
Степенной метод позволяет определить максимальное по модулю собственное значение 1 и соответствующий этому собственному значению
собственный вектор. Его скорость сходимости зависит от величины 2 1 . Если 2 1 1, то сходимость метода очень медленная.
В общем случае метод обратной итерации или обращенный степенной метод позволяет найти собственное значение, которое ближе всего к величине сдвига s, а также соответствующий этому собственному значению собственный вектор. Алгоритм метода обратной итерации :