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, а также соответствующий этому собственному значению собственный вектор. Алгоритм метода обратной итерации :