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

 

1. Каханер Д. Численные методы и программное обеспечение / Д.Каханер, К.Моулер, С.Нэш; пер. с англ. Х.Д.Икрамова. — М.: Мир, 2001. — 575 с.

2. Бахвалов Н.С. Численные методы / Н.С.Бахвалов, Н.П.Жидков, Г.М.Кобельков. — М.: БИНОМ. Лаборатория знаний, 2006. — 636 с.

 

Лекция 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. Проверка сходимости алгоритма.

 

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

 








Дата добавления: 2015-03-20; просмотров: 722;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.015 сек.