Какой самый эффективный способ вычислить собственный вектор плотной матрицы, соответствующий собственному значению наибольшей величины?

У меня плотная вещественная симметричная квадратная матрица. Размер составляет около 1000x1000. Мне нужно вычислить первый главный компонент и подумать, каким может быть лучший алгоритм для этого.

Похоже, что MATLAB использует алгоритмы Арнольди / Ланцоша (для eigs). Но читая о них, я не уверен, есть ли у них какие-либо преимущества перед простой степенной итерацией , поскольку моя матрица не разрежена, и меня интересует только первый собственный вектор.

Любые рекомендации, какой алгоритм в этом случае самый быстрый?

linear-algebra algorithms eigensystem Мика Фишер
источник

На моем компьютере, на случайно сгенерированной симметричной матрице 1000 X 1000, "собственной" функции в R потребовалось около одной секунды для вычисления всех собственных значений и векторов, округления в большую сторону. Ваш пробег может варьироваться, но я сомневаюсь, что ваш выбор алгоритма имеет какое-то значение в такие моменты.

Да, это правда, конечно. Я не очень заинтересован в том, чтобы моя программа работала быстрее. Мне просто любопытно, считаются ли упомянутые более сложные методы превосходными в этом случае использования (плотный, только первый собственный вектор), или существуют ли разные методы для плотных матриц.

Вы имеете в виду собственный вектор, соответствующий наибольшему или наименьшему собственному значению? Звучит так, как будто ты хочешь первое.

Джек Поулсон

Да, собственный вектор соответствует собственному значению с наибольшей величиной.

Мика Фишер

Ответы:

Самый быстрый метод, вероятно, будет зависеть от спектра и нормальности вашей матрицы, но во всех случаях алгоритмы Крылова должны быть строго лучше, чем степенная итерация. У Г. В. Стюарта есть хорошее обсуждение этого вопроса в Главе 4, Раздел 3 Матричных Алгоритмов, Том II: Eigensystems :

Метод мощности основан на наблюдении , что , если имеет доминирующую собственную пару , то при умеренных ограничениях на векторов производить более точные приближения к доминирующему собственному вектору. Однако на каждом этапе метод мощности учитывает только один вектор , что означает отбрасывание информации, содержащейся в ранее сгенерированных векторах. Оказывается, эта информация ценная ... » $A$ $u$ $A^k u$ $A^k u$

$100 \times 100$ $i$ $.95^i$ $i=0$

Джек Полсон
источник

Хм, я бы подумал, что MRRR теперь является стандартным методом, когда нужно просто несколько собственных векторов ...

k

$k$

O (k n^{2} + k^{2} n + k^{3})

$O(k n^2 + k^2 n + k^3)$

k

$k$

n

$n$

Я вижу; почему-то у меня сложилось впечатление, что нужно сначала тридиагонализировать, прежде чем делать Крылова. Спасибо!

Ланцош фактически постепенно строит указанную трехдиагональную матрицу.

Джек Полсон

Степенная итерация является самой простой, но, как упоминалось выше, она, вероятно, будет сходиться очень медленно, если матрица будет очень ненормальной. Вы получаете явление «горба», когда последовательность, по-видимому, расходится на протяжении многих итераций, прежде чем начнется асимптотическое поведение.

Поскольку ваша матрица симметрична, вы можете рассмотреть итерации RQI, что в симметричном случае дает кубическую сходимость: http://en.wikipedia.org/wiki/Rayleigh_quotient_iteration .

Что делает итерации Арнольди или Ланцоша очень хорошими (по крайней мере, на мой взгляд, но я не исследую числовую линейную алгебру), так это то, что они очень универсальны. Обычно можно контролировать, какие собственные значения они вам дают и сколько вы получаете. Это особенно верно в симметричном случае (и даже лучше, если ваша матрица определена). Для симметричных задач они очень устойчивы. Как черный ящик они работают хорошо, но они также очень восприимчивы к новой проблемной информации, такой как способность решать системы, включающие матрицу.

Reid.Atcheson
источник