ПРИЛОЖЕНИЕ 8.2. Ускоренное вычисление собственных значений и собственных векторов

В этом приложении мы дадим (на базе § 8.4) ускоренный алгоритм вычисления собственных значений и собственных векторов корреляционной матрицы [Фукуиага, 19706].

Многие существующие алгоритмы для вычисления собственных значений и собственных векторов являются итеративными. Вычисления начинаются с некоторой ортогональной матрицы и формируется последовательность такая, что

где

и

где — диагональная, а — единичная матрица. В большинстве зтих алгоритмов в качестве начальной матрицы берется

Предположим, однако, что матрица имеющая размерность разбита на подматрицы в соответствии с (8.82) и вектор уже известен. Тогда матрицу можно использовать в качестве начального приближения в итеративном алгоритме. Если удвоить размерность корреляционной матрицы увеличится до Обозначим ее Следовательно, можно определить

Алгоритм заключается в следующем:

1. Взять в качестве начального приближения собственный вектор матрицы равный 1.

2. Располагая вычисленными собственными векторами матрицы использовать в качестве начального приближения в итерационной процедуре для вычисления собственных векторов матрицы

3. Повторять шаг 2 до тех пор, пока не достигнет требуемого значения.

Этот алгоритм называют быстрым алгоритмом определения собственных векторов, потому что его идея заимствована из быстрого преобразования Фурье.

Вычислительное время этого алгоритма зависит от используемого итеративного метода. Одним из широко используемых итеративных методов является метод порога Якоби [Гринштадт, 1962]. Вычислительное время в случае использования этого метода приближенно оценивается как

Для использования начального приближения в методе Якоби нужно преобразовать матрицу в матрицу следующим образом:

и применить последовательные преобразования Якоби для диагонализации матрицы Подставляя (8.82) и (8.85) в получим

где

и

Следовательно, нам нужно вычислить только Общее число требуемых для этого умножений составляет около Это время должно быть добавлено к Однако, так как это добавочное время незначительно.

В описанном выше алгоритме метод Якоби применяется раз для Вычислительное время, расходуемое на шаге, уменьшается за счет использования начальных условий. Учтем это путем его умножения на некоторый коэффициент 0.

Рис. П8.2.1. (см. скан) Экспериментальные кривые для определения коэффициента сходимости [Фукунага, 1970б].

Для простоты предположим, что — константа, т. е. Тогда общее время будет равно

Следовательно, вычислительное время уменьшается в раз по сравнению с методом Якоби.

Для метода Якоби параметр определяется экспериментально. Вычислительное время пропорционально числу итераций метода Якоби, требуемых для получения желаемой точности. Таким

образом, определяется как

где — число итераций, требуемых для получения из вектора вектора обычлю требуемое число итераций.

На рис. П8.2.1 приведены кривые для матрицы с элементами

в зависимости от размерности матрицы при разных значениях Расстояние между кривыми, соответствующими быстрому и обычному методам, на полулогарифмическом графике является почти константой для данного v, а 0 колеблется между 0,25 и 0,35. Таким образом, быстрый алгоритм позволяет уменьшить время вычислений. Фактическая экономия времени зависит, конечно, от конкретной задачи.