Сохранение ширины ленты матрицы в QR-, QL-алгоритмах

Лекция 26. Алгоритмы решения полной проблемы собственных значений

План

QR-, QL-алгоритмы решения полной проблемы собственных значений

Два представления о сходимости QR-, QL-алгоритмов

Ускорение сходимости QR-, QL-алгоритмов. Сдвиг по отношению Рэллея, по Уилкинсону.

Сохранение ширины ленты матрицы в QR-, QL-алгоритмах

1. QR-, QL-алгоритмы решения полной проблемы собственных значений

QR-, QL-алгоритмы решения полной проблемы собственных значений наиболее эффективны для небольших матриц (размера ). Эти алгоритмы эффективны для симметричных ленточных матриц, особенно для трехдиагональных.

Основная идея: QR-, QL-алгоритмы за счет подобных преобразований быстро уменьшают внедиагональные элементы, пока они не станут пренебрежимо малыми.

Любая ненулевая матрица може быть представлена в виде произведения:

(1)

где - ортогональная вещественная матрица (т.е. , - единичная матрица соответствующего размера), - верхняя треугольная матрица с неотрицательными диагональными элементами. Матрицы и определяются однозначно.

Если - невырожденная вещественная матрица, то - это верхний множитель Холесского для симметричной положительно определенной матрицы :

.

Для матрицы возможно разложения вида:

(2)

где - ортогональная вещественная матрица (т.е. , - единичная матрица соответствующего размера), - нижняя треугольная матрица. Эта матрица получается из соответствующего разложения матрицы с учетом :

.

Пример. Построить , - разложения матрицы

.

Матрица является невырожденной, поэтому - верхний множитель Холесского для матрицы . Вычислим элементы матрицы и построим для нее разложение Холесского:

,

.

Элементы матрицы определяются из матричного соотношения:

,

.

Таким образом, - разложение исходной матрицы выглядит следующим образом:

.

Построим теперь для матрицы - разложение. Для этого:

.

Составляя уравнения для элементов матрицы в порядке, отмеченном выше, получим

.

.

Таким образом, - разложение исходной матрицы выглядит следующим образом:

.

Для определенности рассмотрим далее -алгоритм.

Пусть дана матрица и число , называемое сдвигом (сдвиг используется для ускорения сходимости -алгоритма). Для матрицы построим -разложение:

. (3)

Из (3) выразим :

. (4)

-преобразование матрицы с учетом (4) определим следующим образом:

. (5)

Поскольку - ортогональная матрица, это преобразование является подобным.

-алгоритм.

Обозначим исходную матрицу через . Для делать

1. Определить сдвиг , построить -разложение матрицы :

.

2. Построить .

3. Проверка сходимости алгоритма.

Числа выбираются так, чтобы ускорить сходимость -алгоритма. Каждый шаг алгоритма генерирует очередную матрицу , подобную исходной матрице .