Сохранение ширины ленты матрицы в QR-, QL-алгоритмах
1. Каханер Д. Численные методы и программное обеспечение / Д.Каханер, К.Моулер, С.Нэш; пер. с англ. Х.Д.Икрамова. — М.: Мир, 2001. — 575 с.
2. Бахвалов Н.С. Численные методы / Н.С.Бахвалов, Н.П.Жидков, Г.М.Кобельков. — М.: БИНОМ. Лаборатория знаний, 2006. — 636 с.
Лекция 26. Алгоритмы решения полной проблемы собственных значений
План
QR-, QL-алгоритмы решения полной проблемы собственных значений
Два представления о сходимости QR-, QL-алгоритмов
Ускорение сходимости QR-, QL-алгоритмов. Сдвиг по отношению Рэллея, по Уилкинсону.
Сохранение ширины ленты матрицы в QR-, QL-алгоритмах
- QR-, QL-алгоритмы решения полной проблемы собственных значений
QR-, QL-алгоритмы решения полной проблемы собственных значений наиболее эффективны для небольших матриц (размера ). Эти алгоритмы эффективны для симметричных ленточных матриц, особенно для трехдиагональных.
Основная идея: QR-, QL-алгоритмы за счет подобных преобразований быстро уменьшают внедиагональные элементы, пока они не станут пренебрежимо малыми.
Любая ненулевая матрица може быть представлена в виде произведения:
(1)
где - ортогональная вещественная матрица (т.е. , - единичная матрица соответствующего размера), - верхняя треугольная матрица с неотрицательными диагональными элементами. Матрицы и определяются однозначно.
Если - невырожденная вещественная матрица, то - это верхний множитель Холесского для симметричной положительно определенной матрицы :
.
Для матрицы возможно разложения вида:
(2)
где - ортогональная вещественная матрица (т.е. , - единичная матрица соответствующего размера), - нижняя треугольная матрица. Эта матрица получается из соответствующего разложения матрицы с учетом :
.
Пример. Построить , - разложения матрицы
.
Матрица является невырожденной, поэтому - верхний множитель Холесского для матрицы . Вычислим элементы матрицы и построим для нее разложение Холесского:
,
.
Элементы матрицы определяются из матричного соотношения:
,
.
Таким образом, - разложение исходной матрицы выглядит следующим образом:
.
Построим теперь для матрицы - разложение. Для этого:
.
Составляя уравнения для элементов матрицы в порядке, отмеченном выше, получим
.
.
Таким образом, - разложение исходной матрицы выглядит следующим образом:
.
Для определенности рассмотрим далее -алгоритм.
Пусть дана матрица и число , называемое сдвигом (сдвиг используется для ускорения сходимости -алгоритма). Для матрицы построим -разложение:
. (3)
Из (3) выразим :
. (4)
-преобразование матрицы с учетом (4) определим следующим образом:
. (5)
Поскольку - ортогональная матрица, это преобразование является подобным.
-алгоритм.
Обозначим исходную матрицу через . Для делать
1. Определить сдвиг , построить -разложение матрицы :
.
2. Построить .
3. Проверка сходимости алгоритма.
Числа выбираются так, чтобы ускорить сходимость -алгоритма. Каждый шаг алгоритма генерирует очередную матрицу , подобную исходной матрице .
Дата добавления: 2015-03-20; просмотров: 725;