浮點矩陣在幾次乘法後停止變化

我有一個double a[50][50];二維數組，我使用小於1的浮點值進行初始化。矩陣與自身相乘14-15次後，矩陣保持不變。浮點矩陣在幾次乘法後停止變化

更具體地說，我找到了A^k其中A是2D矩陣。矩陣的值在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; 
}

編輯：

給定的矩陣是Markov Matrix。
我已經取代double a[50][50];與std::vector<std::vector<double> > a(50, std::vector<double>(50));（矢量大小可能會有所不同）

來源

2014-11-09 xennygrimmato

'double B [n + 1] [n + 1];'這不是合法的C++。數組在編譯時必須已知其大小。 – PaulMcKenzie 2014-11-09 06:42:58

我沒有看過你的代碼來檢查它，但是如果矩陣應該表示一個馬爾可夫矩陣，那麼經常足夠'A^k-> A'，特別是如果你使用有限的浮點數來表示它。 – 2014-11-09 06:48:02

至於合法的C++，用這個替換那兩個數組：'std :: vector > B（n + 1，std :: vector （n + 1））;''std :: vector < std :: vector > C（n + 1，std :: vector （n + 1））;'當你做出這些改變時，你的代碼將是合法的C++。 – PaulMcKenzie 2014-11-09 06:49:51

我要把我的意見變成一個答案：

Markov (or stochastic) matrices可以達到一個穩定的狀態，使得無論什麼初始狀態，經過足夠的時間/迭代後，狀態將大致相同（即穩定狀態）。例如（以下幻燈片here）：

enter image description here

n後迭代，我們得到的是

enter image description here

使得任何初始狀態（元素的總和必須等於1）將導致{ 2/3，1/3}。當使用浮點數來表示矩陣值時，迭代n和n+1之間的變化通常可能小於ULP。

來源

2014-11-09 07:52:11

浮點矩陣在幾次乘法後停止變化

回答

相關問題