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