C ++の列確率マトリックスの固有ベクトルを計算する方法

Question

列の確率マトリックスAがあり、c ++で次の方程式を解きたいです：ax = x

固有値が1に設定されている固有ベクトルXを見つける必要があると仮定していますが、C ++では把握できませんでした。これまでのところ、セルドン、cppscalapack、eigenなどの数学をいくつかチェックしてきました...その中で、Eigenは良い選択肢のように思えますが、上記の方程式を解決するためにそれらのいずれかを利用する方法を理解できませんでした。

方程式を解決するために、いくつかの提案/コードスニペットやアイデアを教えてください。どんな助けも高く評価されています。

ありがとう。

編集：aはn-by-nリアル、非陰性マトリックスです。

Answer 1

私は固有を使用していませんが、 EigenSolver と SelfAdjointEigenSolver これを解決できるように見えます。これらは「実験的」としてリストされているため、バグがある可能性があり、APIは将来変化する可能性があります。

// 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());
    }
}

2つのソルバークラスには、固有値と固有のベクトルコレクションの種類が異なりますが、クラスマトリックスとマトリックスは両方ともコンバーチブルであるため、上記は機能するはずです。

または、問題に次にアプローチすることもできます 均一な線形方程式 （ai_n) バツ = 0, 、AIを変換することで解決できます_n 上部三角形のマトリックスに。 ガウスエリミネーション それを行います（ただし、整数がフィールドではないため、先行係数が1であることを確認する各行の正規化ステップをスキップする必要があります）。上記のプロジェクトの迅速な閲覧では、列のエシェロン変換のサポートが表示されませんでした。いずれにせよ、いくつかのヘルパークラスで実装するのはそれほど難しくありません（RowMajor, RowMajor::iterator, RowWithPivot 以下では）。これがコンパイルされるかどうかさえテストしていないので、完全なドロップインソリューションよりも、アルゴリズムのイラストをより多く見てみましょう。サンプルは機能を使用しますが、クラスを使用する方が理にかなっている可能性があります（アライメンソルバー）。

/* 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;
}

ヘルパークラスのインターフェイスは、C ++を機能させるために、constorectnessやその他の必要な詳細について吟味されていません。

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();
};