Cómo calcular el vector propio de una matriz columna estocástico en C ++

Question

Tengo una columna estocástico matriz A y quiero resolver la siguiente ecuación en C ++: Ax = x

Estoy asumiendo que necesito para averiguar un vector propio x donde valor propio está dispuesto a ser 1 (¿verdad?), Pero no pude averiguarlo en C ++. Hasta ahora he comprobado algunas matemáticas-libs como Seldon, CPPScaLapack, Eigen ... Entre ellos, Eigen parece una opción buena, pero no podía entender cómo utilizar cualquiera de ellos para resolver la ecuación anterior.

¿Me puede dar algunas sugerencias / fragmentos de código o ideas para resolver la ecuación? Cualquier ayuda es muy apreciada.

Gracias.

edit:. A es n-por-n matriz real, no negativo

Answer 1

Tenga en cuenta que no he utilizado Eigen, pero su EigenSolver y SelfAdjointEigenSolver que sea capaz de resolver esto. Estos se enumeran como "experimental", por lo que podría haber errores y la API podría cambiar en el futuro.

// simple, not very efficient
template <typename _M> 
bool isSelfAdjoint(const _M& a) {
    return a == a.adjoint();
}

template <typename _M> 
std::pair<Eigen::EigenSolver<_M>::EigenvalueType Eigen::EigenSolver<_M>::EigenvectorType>
eigenvectors(const _M& a) {
    if (isSelfAdjoint(a)) {
        Eigen::EigenSolver<M> saes(a);
        return pair(saes.eigenvalues(), saes.eigenvectors());
    } else {
        Eigen::EigenSolver<M> es(a);
        return pair(es.eigenvalues, es.eigenvectors());
    }
}

Las dos clases solucionador tienen diferentes tipos para las colecciones de valor eigen y vector propio, pero a medida que los dos están basadas en la clase Matrix y matrices son convertibles, lo anterior se debe trabajar.

Como alternativa, puede abordar el problema como el homogéneo lineal ecuación (AI _n ) x = 0 , que puede ser resuelto mediante la conversión de AI _n a una matriz triangular superior. eliminación de Gauss hará que (aunque tendrá que saltarse la etapa de normalización para cada fila en la que garantizar el coeficiente principal es 1, como enteros no son un campo). Una lectura rápida de los proyectos mencionados no apareció soporte para la conversión escalonada, lo que probablemente significa que me lo perdí. En cualquier caso, no es demasiado difícil de implementar con algunas clases de ayuda (RowMajor, RowMajor::iterator, RowWithPivot en la siguiente). Ni siquiera he probado si o no este compilará, a fin de tomar como más de una ilustración del algoritmo de un completo, gota-en solución. Aunque las funciones de los usos de ejemplo, podría tener más sentido utilizar una clase (a la eigensolver).

/* Finds a row with the lowest pivot index in a range of matrix rows.
 * Arguments:
 * - start: the first row to check 
 * - end:   row that ends search range (not included in search)
 * - pivot_i (optional): if a row with pivot index == pivot_i is found, search 
 *     no more. Can speed things up if the pivot index of all rows in the range
 *     have a known lower bound.
 *
 * Returns an iterator p where p->pivot_i = min([start .. end-1]->pivot_i)
 *
 */
template <typename _M>
RowMajor<_M>::iterator 
find_lead_pivot (RowMajor<_M>::iterator start,
                 const RowMajor<_M>::iterator& end,
                 int pivot_i=0) 
{
    RowMajor<_M>::iterator lead=start;
    for (; start != end; ++start) {
        if (start->pivot() <= pivot_i) {
            return start;
        }
        if (start->pivot() < lead->pivot()) {
            lead = start;
        }
    }
    return end;
}

/* Returns a matrix that's the row echelon form of the passed in matrix.
 */
template <typename _M>
_M form_of_echelon(const _M& a) {
    _M a_1 = a-_M::Identity();
    RowMajor<_M> rma_1 = RowMajor<_M>(a_1);
    typedef RowMajor<_M>::iterator RMIter;
    RMIter lead;
    int i=0;

    /*
      Loop invariant: row(i).pivot_i <= row(j).pivot_i, for j st. j>i
     */
    for (RMIter row_i = rma_1.begin(); 
         row_i != rma_1.end() && row_i->pivot() != 0; 
         ++row_i, ++i) 
    {
        lead = find_lead_pivot(row_i, rma_1.end(), i);
        // ensure row(i) has minimal pivot index
        swap(*lead, *row_i);

        // ensure row(j).pivot_i > row(i).pivot_i
        for (RMIter row_j = row_i+1; 
             row_j != rma_1.end(); 
             ++row_j) 
        {
            *row_j = *row_j * row_i->pivot() - *row_i * row_j->pivot();
        }
        /* the best we can do towards true row echelon form is reduce 
         * the leading coefficient by the row's GCD
         */
        // *row_i /= gcd(*row_i);
    }
    return static_cast<_M>(rma_1);
}

/* Converts a matrix to echelon form in-place
 */
template <typename _M>
_M& form_of_echelon(_M& a) {
    a -= _M::Identity();
    RowMajor<_M> rma_1 = RowMajor<_M>(a);
    typedef RowMajor<_M>::iterator RMIter;
    RMIter lead;
    int i=0;

    /*
      Loop invariant: row(i).pivot_i <= row(j).pivot_i, for j st. j>i
     */
    for (RMIter row_i = rma_1.begin(); 
         row_i != rma_1.end() && row_i->pivot() != 0; 
         ++row_i, ++i) 
    {
        lead = find_lead_pivot(row_i, rma_1.end(), i);
        // ensure row(i) has minimal pivot index
        swap(*lead, *row_i);

        for (RMIter row_j = row_i+1; 
             row_j != rma_1.end(); 
             ++row_j) 
        {
            *row_j = *row_j * row_i->pivot() - *row_i * row_j->pivot();
        }
        /* the best we can do towards true row echelon form is reduce 
         * the leading coefficient by the row's GCD
         */
        // *row_i /= gcd(*row_i);
    }
    return a;
}

Las interfaces para las clases de ayuda, que no han sido seleccionados para la const-corrección y otros detalles necesarios que hacen el trabajo de C ++.

template <typename _M>
class RowWithPivot {
public:
    typedef _M::RowXpr Wrapped;
    typedef _M::Scalar Scalar;

    RowWithPivot(_M& matrix, size_t row);

    Wrapped base();
    operator Wrapped();

    void swap(RowWithPivot& other);

    int cmp(RowWithPivot& other) const;
    bool operator <(RowWithPivot& other) const;

    // returns the index of the first non-zero scalar
    // (best to cache this)
    int pivot_index() const;
    // returns first non-zero scalar, or 0 if none
    Scalar pivot() const;
};

template <typename _M, typename _R = RowWithPivot<_M> >
class RowMajor {
public:
    typedef _R value_type;

    RowMajor(_M& matrix);

    operator _M&();
    _M& base();

    value_type operator[](size_t i);

    class iterator {
    public:
        // standard random access iterator
        ...
    };

    iterator begin();
    iterator end();
};