Меню
Главная
Авторизация/Регистрация
 
Главная arrow Математика, химия, физика arrow Линейная алгебра: теория и прикладные аспекты

QR-алгоритм

QR-алгоритм — это наиболее употребительный в настоящее время итерационный метод отыскания характеристических чисел действительных и комплексных матриц. Стандартные программы к этому методу содержатся во многих пакетах математического обеспечения. фЛ-алгоритм состоит в следующем.

Для данной матрицы А = Aq строят Q/2-разложение А = Qq Rq (см. разд. 8.17). В полученном разложении меняют местами множители. Это приводит к матрице А = Rq Qq, с которой поступают аналогично, и т.д. В результате получают последовательность матриц Aq, Ai, А2, ..., Ак, ... Эти матрицы подобны, так как А = Qq1 AqQq, А2 = Qi lAi Qi и т.д.

При довольно общих предположениях построенная последовательность матриц сходится к треугольной матрице. Диагональные элементы треугольной матрицы являются ее характеристическими числами и характеристическими числами всех подобных матриц, в частности матрицы Л о = А.

Для ускорения Q Л-алгоритма желательно, чтобы на каждом его шаге быстро строилось фЛ-разложение очередной матрицы Ак. Для этого следует исходную матрицу- с помощью ортогональных (унитарных) преобразований привести к подобной матрице Aq = U~l AU более простого вида, например, почти треугольного вида или трехдиагональной формы. О приведении матрицы к подобной матрице почти треугольного вида см. разд. 8.10 и [3], с. 182-184. фЛ-алгоритм практически всегда применяется к почти треугольным матрицам, а в симметричном случае — к трехдиагоналыгым.

Другим важным приемом ускорения фЛ-алгоритма является использование сдвигов ак для повышения скорости убывания по абсолютной величине элементов, лежащих ниже главной диагонали. С этой целью на (к + 1)-м шаге Q Л-р аз л оже и и я строят не для матрицы Ак, а для матрицы Ак — ак Е. Если Акак Е = Qk Як — построенное

Q Л-р аз л ожс 11 и e, то полагают А^+1 = Rk Qk + од E. Такой переход от к Ak+1 не меняет характеристических чисел, поскольку матрицы Ak и Ак+1 подобны. Действительно,

На практике обычно в качестве сдвига ад принимают элемент матрицы Ak, стоящий в ее нижнем правом углу. При таком выборе сдвига обеспечивается высокая скорость сходимости к характеристическому числу Ап.

Пусть в результате некоторого числа шагов ДЛ-алгоритма пришли к матрице вида

с пренебрежимо малым по абсолютной величине числом г. Тогда принимают Ап = А^ и переходят к вычислению характеристического числа An_i. При этом фактически работают уже с матрицей (тг — 1)-го порядка, расположенной в матрице (11.7) в ее левом верхнем углу. При этом за сдвиг а к теперь каждый раз принимают элемент, стоящий в правом нижнем углу матрицы (п— 1)-го порядка, с которой работают. После того как вычислено An_i, аналогично поступают при вычислении Ап_2 и т.д. Если матрица действительная, то фЛ-алгоритм можно реализовать в вещественной арифметике (см. [34], с. 142).

Пример 11.3. С помощью С^Л-алгоритма найти характеристические числа матрицы

Решение. Чтобы показать, как проводятся циклы ДЛ-алгорит- ма без сдвига и со сдвигом, начнем с того, что первый цикл проведем без сдвига. Поэтому будем строить ДЛ-разложение матрицы Ао = = А. Сначала эту матрицу вращениями приведем к треугольному виду. Начнем с обнуления элемента Л32 = 2. Для этого составим матрицу вращения

и найдем cos <д и sin исходя из равенства нулю элемента матрицы Т32 Aq в третьей строке втором столбце, т.е. из равенства

Отсюда получаем, что tg Следовательно,

и

Из этого равенства получается (^-разложение

В заключение цикла строим матрицу

Следующий цикл проведем со сдвигом а = а{33 = 1. Поэтому будем строить Q^-разложение матрицы

Сначала эту матрицу вращениями приведем к треугольному виду. Здесь следует обнулить лишь элемент = 1. Для этого составим матрицу вращения

и найдем cos ср и sin<^ из равенства нулю элемента матрицы Т32 (А — Е) в третьей строке и втором столбце, т.е. из равенства

Отсюда получаем tg(/?=—1/Зи

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

Из равенства

получаем (^-разложение

В заключение цикла строим матрицу

Эта матрица уже треугольная с характеристическими числами Ai = 1, Л2 = 4, A3 = 1. Эти же числа являются характеристическими числами матрицы А. ?

 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Пред   СОДЕРЖАНИЕ ОРИГИНАЛ   След >
     

    Популярные страницы