Сохранение ширины ленты матрицы в QR-, QL-алгоритмах. Необходимо отметить, что QR, QL-алгоритмы в общем случае сохраняют ширину ленты исходной матрицы

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

 

 

где — ортогональная матрица с элементами ;

— верхняя треугольная матрица с элементами .

Пусть . Рассмотрим значения элементов последней строки матрицы :

 

, (7.3)

откуда вытекает, что .

Составляя уравнение, аналогичное (7.3) для , получим из него, что .

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

 

 

На очередной итерации основного QR-алгоритма (без использования сдвигов для ускорения сходимости) получаем матрицу

 

. (7.4)

 

Таким образом, если исходная матрица была симметричной, то итерации QR-алгоритма сохраняют симметричность:

 

. (7.5)

 

Сохранение нулевих элементов (ленточной структуры) в нижнем треугольнике матрицы вытекает из вида и :

Действительно, при вычислении элементов последней строки матрицы получаем, что первым отличным от нуля может быть лишь элемент, стоящий на том же месте, что и первый отличный от нуля элемент последней строки матрицы :

 

 

Аналогичный результат в нижнем треугольнике получится и при вычислении элементов всех строк матрицы .

Сохранение исходной ленточной структуры матрицы в верхнем треугольнике матрицы вытекает из (7.5). Таким образом, соотношение (7.6) можно уточнить:

 

 

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

 








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


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

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

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

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