Как вычислить собственный вектор стохастической матрицы столбца в C ++

Question

У меня есть столбцовая стохастическая матрица A (n-на-n вещественная, неотрицательная матрица) и я хочу решить следующее уравнение в C ++: Ax = x

Я предполагаю, что мне нужно найтиСобственный вектор, х, где собственное значение должно быть 1 (верно?), но я не мог понять это в C ++.До сих пор я проверял некоторые математические библиотеки, такие как Seldon, CPPScaLapack, Eigen ... Среди них Eigen кажется хорошим вариантом, но я не мог понять, как использовать любую из них для решения приведенного выше уравнения.

Можете ли вы дать мне некоторые предложения / фрагменты кода или идеи для решения уравнения?Любая помощь высоко ценится.

Спасибо.

Answer 1

Другой метод состоит в том, чтобы вычислить ядро ​​вашей матрицы за вычетом единичной матрицы. Это может или не может быть быстрее, чем использование итерации мощности, как объяснил Карл, в зависимости от размера матрицы и других собственных значений. Степень итерации лучше, когда матрица становится больше, а второе собственное значение отодвигается от единицы.

Идея состоит в том, чтобы переписать Ax = x как Ax - x = 0. Затем использовать это Ix = x, где I обозначает единичную матрицу. Таким образом, Ax - x = 0 эквивалентно Ax - Ix = 0 или (A-I) x = 0. Таким образом, ваш собственный вектор x лежит в ядре (или нулевом пространстве) A-I.

На этой странице учебника объясняется, как вычислить ядро ​​матрицы с использованием Eigen. Немного непроверенный код:

MatrixXf M;
/* initialize M */
FullPivLU<MatrixXf> lu_decomp(M);
VectorXf x = lu_decomp.kernel().col(0);
/* x now contains the vector you want */

Вы можете обнаружить, что ядро ​​пусто. Это означает, что либо матрица на самом деле не стохастическая, либо вам необходимо адаптировать порог (см. Ссылку, приведенную выше).

Answer 2

Поскольку самый большой собственный вектор в стохастической матрице $ M $ равен единице, этот собственный вектор можно найти итерацией (если только вы не очень плохо угадываете начальные значения).

Начнем с некоторого случайно выбранного начального вектора $ v_1 $, значения (вероятности) которого равны единице. Примените $ M $ к $ v_1 $, чтобы получить $ Mv_1 $. Теперь перенормируйте этот новый вектор $ Mv_1 $, то есть разделите на сумму его элементов, чтобы получить $ v_2 $. Это новый вектор вероятностей, и он будет ближе к нужному собственному вектору (если только ваше первоначальное предположение не оказалось ортогональным по отношению к собственному вектору).

Повторяйте этот процесс, пока $ v_k $ не достигнет стабильности. Это должен быть вектор с $ Mv_k = v_k $, по желанию.