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

Question

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

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

Longer объяснение:

У меня есть большая стохастическая матрица 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, чтобы решить мою проблему быстрее, чем путем вычисления самого большого собственного значения и сопутствующего собственного вектора?

Answer 1

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

1. Пусть х обозначим (строка) левый ^† собственного вектора, связанного с собственным значением 1. Это удовлетворяет системе линейных уравнений (или матричного уравнения) хА = х или х ( - я) = .
2. Чтобы избежать решения всех нулей этой системы уравнений, удалите первое уравнение и произвольно установите первую запись x в 1 в остальных уравнениях.
3. решить эти оставшиеся уравнения (с х = 1), чтобы получить другие записи из х.

Пример с использованием 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.

В вашей формулировке можно определить х быть (колонка) правый собственный вектор от A^T (такой, что A^Tx = 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 

---

^{† После usual convention. Эквивалентно это соответствует правым собственным вектором транспонированной матрицы; Смотри ниже.}