*		*	*	*
		*	*	*	*
		0	*	*	*
	A*				*
		0	0	*
		0	0	*	*

*, a32* 0 .

Продолжая этот процесс, после n 2 шагов получим

A* Sn 2 S2 S1 AS1S2 Sn 2 ,

где A* – матрица (5.1), для которой выполняются неравенства (5.6).

Если на каком-либо шаге i получится нулевой вектор, для которого строится отражение, то полагают Si E .Окончательно, ортогональное

преобразование Т матрицы А к почти треугольному виду определяется произведением ортогональных матриц Si :

T Sn 2 S2 S1 .

Если матрица А симметричная, то промежуточные матрицы и конечная матрица будут также симметричными, следовательно, почти треугольная форма таких матриц является трехдиагональной формой (5.2).

Приведение произвольной матрицы к почти треугольной форме (5.1)

требует 103 n3 арифметических операций.

5.3.Разложение матрицы на произведение ортогональной и треугольной

Будем считать, что матрица А приведена к почти треугольному виду (5.1). Найдем разложение матрицы А в произведение

A QR

(5.7)

Q – ортогональная матрица, R – верхняя треугольная. Определим матрицу элементарного вращения

i

i 1

1

0

1

Pi

sin i

cosi

i

cosi

sin i

i 1

0

1

1

Можно проверить, что Pi ,

i 1, n 1 – ортогональные матрицы.

Умножая матрицу А вида (5.1) на матрицу P1 , получим

sin 1

cos 1

a

a

a

a

0

11

12

1,n 1

1n

cos 1

sin 1

a21

a22

a2,n 1

a2n

1

0

0

an 1,n

1

ann

a11 sin 1

a21 cos 1

a12 sin 1

a22 cos 1

a1n sin 1

a2n cos 1

a11 cos 1 a21 sin 1

a12 cos 1 a22 sin 1

a1n cos 1 a2n sin 1

a32

a3n

0

an 1,n

ann

Выберем угол 1 таким, чтобы поддиагональный элемент в первом

столбце обратился в ноль:

a11 cos1 a21 sin 1

0

a

.

arctg

11

1

a21

В результате умножения матрицы А на P , P , , P

и соответствующего

1

2

n 1

выбора углов вращения i

все поддиагональные элементы матрицы А можно

обратить в ноль. Таким образом, получим

P

P

P A R

(5.8)

n 1 n 2

1

R – верхняя треугольная матрица. Из (5.8) имеем

A QR

Q P1T P2T PnT

Т.е. (5.7). Матрица Q будет ортогональной как произведение ортогональных матриц.

5.4. QR-алгоритм определения собственных значений

Пусть матрица А приведена к почти треугольному виду (5.1). Если бы поддиагональ в (5.1) обладала свойством

a*	a*	0,	i 2, n 1,
i,i 1	i 1,i

т.е. в матрице А отсутствовали бы соседние ненулевые поддиагональные элементы, то матрица А имела бы блочно-треугольную форму

A*		A*	A*
	11	12	1n
		A*	A*
A*	0	22	2n		(5.9)
			*
			Ann

Здесь Aii* – квадратные блоки 1-го или 2-го порядка. Блоки второго порядка соответствуют ненулевым элементам поддиагонали.

Так как матрицы А и A* имеют одни и те же собственные значения, то блоки Aii* 1-го порядка – это собственные значения А. Собственные значения блоков Aii* 2-го порядка – это также собственные значения матрицы А, но среди

них могут быть комплексные числа.

Таким образом, приведение матрицы А к форме (5.9) полностью решает проблему собственных значений. Собственные векторы после приведения к (5.9) также легко определяются.

Однако для матрицы А, вообще говоря, не существует конечного вычислительного процесса на ее элементами, приводящего А к форме (5.9).

Рассматриваемый QR-алгоритм дает последовательность матриц A k

треугольного вида (5.1) таких, что lim a k		a k	0 .
k	i,i 1	i 1,i

Когда сходящиеся к нулю поддиагональные элементы матриц A k иметь величину меньше заданной точности, QR-алгоритм завершается.

Каждый шаг QR-алгоритма состоит в переходе от матрицы матрице A k 1 , k 0, 1, , A 0 A по следующему правилу.

почти

будут

A k к

1.	Матрица A k	разлагается на произведение	ортогональной и
треугольной матриц по схеме (5.8):
		A k Q k R k	(5.10)
2.	Матрица A k 1	определяется перестановкой сомножителей в (5.10):
		A k 1 R k Q k , k 0,1, 2, .

Из (5.10) определим

R k Q k 1 A k Q k T A k .

Следовательно,

A k 1 Q k 1 A k Q k

или

1		1	A Q 0	Q k .
A k 1 Q k	Q 0
Обозначим через P k Q 0 Q k . Тогда QR-алгоритм					можно записать	в
форме
	1		T	AP k	(5.11)
A k 1 P k		AP k P k
Это соотношение показывает, что		собственные		значения	матриц A k и	А
совпадают.
Соотношения (5.10) и (5.11) позволяют получить следствие из QR-
алгоритма. Рассмотрим произведение правых треугольных матриц
R k R k 1 R 0			U k .

Имеем

P k U k P k 1 Q k R k U k 1 P k 1 R k 1 Q k 1 U kP k 1 P k 1 1 AP k 1 U k 1 A P k 1 U k 1 Ak

Т.е. для любых k матрицы P k и U k являются ортогональными и правыми треугольными сомножителями в соответствующих степенях матрицы А.

Каждый шаг QR-алгоритма, если матрица предварительно приведена к форме (5.1), требует 6n2 арифметических операций. При этом верхняя форма Хессенберга сохраняется QR-итерацией. Вначале получается почти треугольная матрица Q k , умножение которой слева на верхнюю треугольную матрицу R k

не изменит форму матрицы A k 1 R k Q k .

Сформулируем утверждение о сходимости QR -алгоритма.

Пусть матрица А невырождена, имеет различные собственные значенияi , i 1, n , модули которых i , за исключением комплексно-

сопряженных, также различны и упорядочены в порядке невозрастания. Тогда при k

i 1

k

a k

a k

O

,

i 2, n 1.

i,i 1

i 1,i

i 1