 |
Метод итераций в подпространстве
|
|
|
|
Лекция 14
Итерации в подпространстве
Метод итераций в подпространстве
Метод основан на уже известном нам степенном методе. Отличие заключается в том, что итерации выполняются не с одним, а несколькими векторами.
Простейшая реализация метода заключается в следующем.
1. Выбираются 
нормированных и взаимно ортогональных векторов 
. Эти вектора удобно представить себе как столбцы матрицы 
размера 
:
. (17.1)
2. Выполняется итерация, которая в данном случае представляет собой умножение исследуемой матрицы 
на матрицу 
. (17.2)
В этот момент проверяется сходимость. Если отношения элементов первого столбца 
и соответствующих элементов первого столбца 
одинаковы (в реальных вычислениях очень близки), то первый столбец есть собственный вектор, соответствующий наибольшему собственному значению матрицы . Само же это отношение и будет искомым собственным значением 
:
. (17.3)
3. Столбцы полученной матрицы ортонормируют (процесс Грама-Шмидта). Полученную матрицу размера 
обозначаем 
и ее столбцы рассматриваем как очередное приближение собственных векторов. Этот шаг является важным дополнением по сравнению со степенным методом. Если бы его не было, все столбцы стремились бы к одному и тому же собственному вектору 
.
4. Переход ко второму шагу алгоритма и продолжение итераций до достижения сходимости.
Алгоритм итераций в подпространстве используется, когда надо определить несколько собственных значений и соответствующих векторов. Если требуется определить 
собственных пар, то, с целью ускорения сходимости, для итераций используется несколько большее число векторов. Например, неплохим выбором количества итерационных векторов будет 
. Следует иметь в виду, что увеличение количества итерационных векторов (иными словами, увеличение размерности подпространства) повышает скорость сходимости, но при этом каждая итерация будет требовать большего количества вычислений.
|
|
|
Пример. Для матрицы
по методу итераций в подпространстве определить два наибольших собственных значения и соответствующие собственные векторы. Для справки, точное решение задачи:
В качестве начальных векторов берем два единичных орта:
.
Первая итерация:
.
Вторая итерация:
.
Третья итерация:
.
Четвертая итерация:
.
Как видим, процесс движется в должном направлении. Правда, сходимость довольно медленная. Если продолжить вычисления, то точность в три значащие цифры после запятой будет достигнута после одиннадцатой итерации.
Использование процедуры Рэлея ‑ Ритца позволяет значительно усовершенствовать алгоритм. При этом описание алгоритма несколько усложняется, Но скорость сходимости итерационного процесса значительно повышается
1. Как и в предыдущем варианте, сначала формируется система начальных векторов, которые удобно представить в виде столбцов прямоугольной матрицы:
(17.4)
Эти векторы размерности 
( ‑ размер исследуемой матрицы 
) должны быть нормированы и ортогональны между собой. В остальном их выбор произволен. Количество итерируемых векторов (количество столбцов в матрице ) определяется исполнителем расчетов.
2. Выполняется умножение матрицы итерируемых векторов на исследуемую матрицу:
(17.5)
Полученная матрица имеет тот же размер (количество строк и столбцов), что и матрица , но столбцы ее уже не будут ортонормированны между собой.
3. Столбцы полученной матрицы 
ортонормируют с использованием процедуры Грама-Шмидта. Полученную матрицу размера обозначим 
.
4. В соответствии с процедурой Релея-Ритца формируется матрица
|
|
|
(17.6)
5. Для полученной матрицы 
размера 
решается полная проблема собственных значений:
(17.7)
Результатом решения (17.7) будут собственные значения 
и соответствующие собственные векторы 
. Из этих векторов формируем матрицу:
(17.8)
6. Матрица 
дает возможность построить матрицу ортонормированных итерационных векторов очередного приближения
(17.9)
В этот момент можно проверить, достигнута ли необходимая точность, или итерации следует продолжить. Для продолжения итераций следует вновь перейти к пункту 2 данного плана. Проверку сходимости можно выполнить путем сравнения матриц и
Пример. Рассматриваем ту же задачу, что и в предыдущем примере с тем же выбором начальных векторов:
,
Первая итерация:
; 
.
Вторая итерация:
; 
.
Третья итерация:
; 
.
Четвертая итерация:
; 
.
Как видим, использование процедуры Рэлея ‑ Ритца значительно повышает скорость сходимости метода.
Литература
17.1. Парлетт Б. Симметричная проблема собственных значений. Численные методы. – М.: Мир, 1983. – 384с.
|
|
|
