Быстро и эффективно вычислять собственный вектор для известного собственного значения

Краткая версия моего вопроса :

Каким будет оптимальный способ вычисления собственного вектора для матрицы A , если мы уже знаем собственное значение, принадлежащее собственному вектору?

Более длительное объяснение :

У меня есть большая стохастическая матрица A которая, поскольку она является стохастической, имеет неотрицательный левый собственный вектор x (такой, что A^Tx=x ).

Я ищу быстрые и эффективные методы численного расчета этого вектора. (Предпочтительно в MATLAB или numpy / scipy – так как оба эти обертывания вокруг ARPACK / LAPACK, любой из них будет прекрасен).

Я знаю, что 1 является наибольшим собственным значением для A , поэтому я знаю, что вызываю что-то вроде этого кода Python:

 from scipy.sparse.linalg import eigs vals, vecs = eigs(A, k=1) 

приведет к vals = 1 и vecs равным вектору, который мне нужен.

Однако меня беспокоит то, что вычисление собственных значений, как правило, является более сложной операцией, чем решение линейной системы, и, вообще говоря, если матрица M имеет собственное значение l , то поиск соответствующего собственного вектора является вопросом решения уравнение (M - 1 * I) * x = 0 , которое, по крайней мере, теоретически является операцией, которая проще, чем вычисление собственного значения, поскольку мы решаем только линейную систему, точнее, находим нулевое пространство матрицы ,

Тем не менее, я считаю, что все методы вычисления nullspace в MATLAB основаны на вычислении svd , процесс, который я не могу позволить себе выполнять на матрице моего размера. Я также не могу вызывать решатели по линейному уравнению, потому что все они находят только одно решение, и это решение равно 0 (что да, это решение, но не то, что мне нужно).

Есть ли способ избежать вызовов функции, eigs для решения моей проблемы быстрее, чем путем вычисления самого большого собственного значения и сопутствующего собственного вектора?

One Solution collect form web for “Быстро и эффективно вычислять собственный вектор для известного собственного значения”

Вот один из подходов:

  1. Пусть x обозначает (линейный) левый собственный вектор, связанный с собственным значением 1. Он удовлетворяет системе линейных уравнений (или матричного уравнения) xA = x или x ( AI ) = 0 .
  2. Чтобы избежать решения всех нулей этой системы уравнений, удалите первое уравнение и произвольно установите первую запись x в 1 в остальных уравнениях.
  3. Решите оставшиеся уравнения (с x 1 = 1), чтобы получить другие записи из x .

Пример использования Matlab:

 >> A = [.6 .1 .3 .2 .7 .1 .5 .1 .4]; %// example stochastic matrix >> x = [1, -A(1, 2:end)/(A(2:end, 2:end)-eye(size(A,1)-1))] x = 1.000000000000000 0.529411764705882 0.588235294117647 >> x*A %// check ans = 1.000000000000000 0.529411764705882 0.588235294117647 

Обратите внимание, что код -A(1, 2:end)/(A(2:end, 2:end)-eye(size(A,1)-1)) является этапом 3.

В вашей формулировке вы определяете x как собственный (прямоугольный) собственный вектор A T (такой, что A T x = x ). Это всего лишь x.' из приведенного выше кода:

 >> x = x.' x = 1.000000000000000 0.529411764705882 0.588235294117647 >> A.'*x %// check ans = 1.000000000000000 0.529411764705882 0.588235294117647 

Конечно, вы можете нормализовать собственный вектор на сумму 1:

 >> x = x/sum(x) x = 0.472222222222222 0.250000000000000 0.277777777777778 >> A.'*x %'// check ans = 0.472222222222222 0.250000000000000 0.277777777777778 

Следуя обычной конвенции . Эквивалентно это соответствует правому собственному вектору транспонированной матрицы; Смотри ниже.

  • Как я могу использовать уникальные (a, 'rows') из MATLAB в Python?
  • Представление и решение лабиринта с учетом изображения
  • Чтение всех переменных в файле .mat с помощью python h5py
  • Выбор интерфейсного / интерпретатора для научного кода
  • Имеет ли смысл использовать префиксы венгерских нотации в интерпретируемых языках?
  • Эквивалент csaps и ppval в python
  • Алгоритм группировки множеств точек, которые следуют по направлению
  • Почему numpy std () дает другой результат для matlab std ()?
  • Python - лучший язык программирования в мире.