Преобразование отражения. Сведение матрицы к почти треугольному виду
Запишем -матрицу в виде:
,
где
,
,
.
Построим матрицу отражения:
,
где
,
.
Матрица
- самосопряженная и ортогональная.
Действительно:
;
Построим матрицу
.
В
силу свойств матрицы
матрица
также является самосопряженной и
ортогональной.
Рассмотрим:
.
Рассмотрим
подробнее элементы матрицы
:
,
(1)
при этом
Уточним
выражение для
.
Для этого вычислим
:
,
тогда
.
Возвращаясь к формуле (1), вычислим
,
поэтому
.
Таким образом, у матрицы нули в первом столбце, начиная с третьего элемента.
Для сохранения подобия необходимо матрицу умножить на справа:
.
Очевидно, первый столбец матрицы остался без изменений.
Далее
строится матрица отражения для второго
столбца матрицы
для получения нулей во втором столбце
преобразованной матрицы, начиная с
четвертого элемента и т.д. Конечный
результат – построение верхней почти
треугольной матрицы.
QR-, QL-алгоритмы решения полной проблемы собственных значений
QR-,
QL-алгоритмы
решения полной проблемы собственных
значений наиболее эффективны для
небольших матриц (размера
).
Эти алгоритмы эффективны для симметричных
ленточных матриц, особенно для
трехдиагональных.
Основная идея: QR-, QL-алгоритмы за счет подобных преобразований быстро уменьшают внедиагональные элементы, пока они не станут пренебрежимо малыми.
Любая ненулевая матрица може быть представлена в виде произведения:
(1)
где
- ортогональная вещественная матрица
(т.е.
,
- единичная матрица соответствующего
размера),
- верхняя треугольная матрица с
неотрицательными диагональными
элементами. Матрицы
и
определяются однозначно.
Если
- невырожденная вещественная матрица,
то
- это верхний множитель Холесского для
симметричной положительно определенной
матрицы
:
.
Для матрицы возможно разложения вида:
(2)
где - ортогональная вещественная матрица (т.е. , - единичная матрица соответствующего размера), - нижняя треугольная матрица. Эта матрица получается из соответствующего разложения матрицы с учетом :
.
Сохранение ширины ленты матрицы в qr-, ql-алгоритмах
Необходимо отметить, что QR, QL-алгоритмы в общем случае сохраняют ширину ленты исходной матрицы. Для определенности рассмотрим далее QR-алгоритм. Пусть для ненулевой ленточной -матрицы построено QR-разложение:
где
—
ортогональная матрица с элементами
;
— верхняя
треугольная матрица с элементами
.
Пусть
.
Рассмотрим значения элементов
последней строки матрицы
:
,
(7.3)
откуда
вытекает, что
.
Составляя
уравнение, аналогичное (7.3) для
,
получим из него, что
.
Первый ненулевой элемент в последней строке матрицы будет находится в той же позиции, что и первый ненулевой элемент в последней строке матрицы . Рассмотрев последовательно выражения для значений всех элементов , двигаясь по строкам снизу вверх, получим, что структура нижнего треугольника матрицы аналогична ленточной структуре нижнего треугольника матрицы :
На очередной итерации основного QR-алгоритма (без использования сдвигов для ускорения сходимости) получаем матрицу
.
(7.4)
Таким образом, если исходная матрица была симметричной, то итерации QR-алгоритма сохраняют симметричность:
.
(7.5)
Сохранение
нулевих элементов (ленточной структуры)
в нижнем треугольнике матрицы
вытекает из вида
и
:
Действительно, при вычислении элементов последней строки матрицы получаем, что первым отличным от нуля может быть лишь элемент, стоящий на том же месте, что и первый отличный от нуля элемент последней строки матрицы :
Аналогичный результат в нижнем треугольнике получится и при вычислении элементов всех строк матрицы .
Сохранение исходной ленточной структуры матрицы в верхнем треугольнике матрицы вытекает из (7.5). Таким образом, соотношение (7.6) можно уточнить:
