Метод итераций в подпространстве

Лекция 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 данного плана. Проверку сходимости можно выполнить путем сравнения матриц и

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

Первая итерация:

; .