c++ - 几次乘法后浮点矩阵停止变化

Question

我有一个 double a[50][50];我用小于 1 的浮点值初始化的二维数组。在将矩阵与自身相乘 14-15 次后，矩阵保持不变。

更具体地说，我发现了A^k其中 A是二维矩阵。矩阵的值在 14 次乘法后停止变化。

如何防止这种情况发生？我想对 k 的大值执行矩阵乘法,

1 <= k <= 10^9 .

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
#define pb push_back
using namespace std;

std::vector<std::vector<double> > A(51, std::vector<double>(51));
void expo(long long t,int n){
    if(t==1)
        return;
    std::vector<std::vector<double> > B(n+1, std::vector<double>(n+1));
    if(t&1){
        for(int x=0;x<n;x++)
            for(int y=0;y<n;y++)
                B[x][y]=A[x][y];
    }
    std::vector<std::vector<double> > C(n+1, std::vector<double>(n+1));
    for(int x=0;x<n;x++)
        for(int y=0;y<n;y++){
            C[x][y]=0;
            for(int z=0;z<n;z++){
                C[x][y]=(C[x][y]+A[x][z]*A[z][y]);
            }
        }
    for(int x=0;x<n;x++)
        for(int y=0;y<n;y++)
            A[x][y]=C[x][y];
    expo(t>>1,n);
    if(t&1){
        for(int x=0;x<n;x++)
            for(int y=0;y<n;y++){
                C[x][y]=0;
                for(int z=0;z<n;z++){
                    C[x][y]=(C[x][y]+A[x][z]*B[z][y]);
                }
            }
        for(int x=0;x<n;x++)
            for(int y=0;y<n;y++)
                A[x][y]=C[x][y];
    }
}
int main(){
    int k;
    cin>>k;
    int ix,iy;
    for(ix=0;ix<50;ix++)
        for(iy=0;iy<50;iy++)
            cin>>A[ix][iy];

    expo(k,50);
    for(int i=0;i<50;i++) 
    {
        for(int j=0;j<50;j++) 
        {
            cout<<A[i][j]<<" ";
        }
        cout<<"\n";
    }

    return 0;
}

编辑:

1. 给定的矩阵是一个 Markov Matrix .

2. 我已经替换了double a[50][50];与 std::vector<std::vector<double> > a(50, std::vector<double>(50)); ( vector 大小可能不同)

Answer 1

我会将我的评论变成答案:

Markov (or stochastic) matrices可以达到稳定状态，这样无论初始状态如何，经过足够的时间/迭代后状态将大致相同(即稳定状态)。例如(跟随幻灯片 here ):

经过 n 次迭代，我们得到了

任何初始状态(元素之和必须等于 1)都会导致 {2/3, 1/3}。当使用 float 表示矩阵值时，迭代 n 和 n+1 之间的变化通常小于 ULP .