全網最最最最最詳細的c++算法講解（三）矩陣乘法進階與高斯消元法

建議各位在看本篇部落格之前，先看一下我的部落格的算法講解（二），了解一些關于矩陣乘法和矩陣的相關知識

這裡先來一道矩陣乘法好題，前幾天看到的

設n元向量x=[x1,x2,…,xn]，y=[y1,y2,…,yn]，若A=yTx，求A^k      (yT表示矩陣y的轉置）

n的範圍是n<=100000

一看到，這個題，肯定很多人會想：”這不是個sb題嗎？直接做不就好了？”

但其實不然，如果我們直接進行矩陣快速幂，複雜度是n^2*logk的

顯然跑不過。

那麼我們這時候就可以，動動腦筋了。 好像在前一篇文章裡，我提到過這麼一個結論

隻要當A矩陣為x*y，B矩陣的乘法y*z時，乘出的C矩陣是一個x*z的矩陣！！！

那麼，我們要是可以将x和yT相乘 就好了哎

展開式子，根據矩陣乘法的結合律，我們就會驚奇的發現：

Ak=(yTx)(yTx)…(yTx)

    =yT(xyT)(xyT)…(xyT)x

    =<x,y>^k-1A

woc 騷操作呀！時間複雜度直接O(n^2 log k)-->O(log k+n^2)

社會社會

一道華麗的分割線------------------------------------

好啦，進入正題。

原諒我的懶.....

對于一個Ax=b的線性方程組

若b=0，則稱Ax=b為齊次線性方程組

若b≠0，則稱Ax=b為非齊次線性方程組

在解方程之前，我們先介紹一下矩陣的初等行變換

矩陣的三種初等行變換

(1)将A的第i行與第j行對換

(2)将A的第i行乘以非零常數k

(3)将A第i行的k倍加到第j行

并且并且并且------矩陣的初等行變換不改變線性方程組的解！

對矩陣A做一次初等行變換，等價于，在A的左邊乘一個初等矩陣

這是矩陣行變換中常用的三個初等矩陣

Eij                  對換第i行與第j行

Ei(k)              第i行乘以k

Eij(k)             第i行的k倍加到第j行

在高斯消元中，我們普遍是将矩陣化為最簡階梯型矩陣：

階梯形矩陣

若矩陣的每個非零行的上方沒有零行，且各個非零行自左向右的第一個非零元素a1j1,a2j2,…,arjr所在列的編号滿足j1<j2<…<jr，則稱該矩陣為階梯形矩陣。其中第j1列，第j2列，…，第jr列被稱為矩陣的主元列。

若階梯形矩陣中個非零行自左向右第一個非零元素均為1，他們所在列的其餘元素均為0，則稱該階梯形矩陣為最簡階梯形矩陣。

任意非零矩陣A隻經初等行變換可化為階梯形矩陣。

該階梯形矩陣中主元列的個數稱為矩陣A的秩，記作rank(A)

那麼我們該如何求矩陣的秩？           化為階梯形矩陣！

如何求方程組的解？                        化為最簡潔階梯型矩陣！

如何隻通過行變換将任意矩陣化為階梯形矩陣？   Gauss消元法！！！

大概步驟就是

i：1~n      k：目前已經選中的行數（矩陣的秩）

①挑選未被選中的某一行，滿足這一行的第i列不為0

(若所有未被選擇的行中，第i列都為0，則第i列不為主元列)

②将這一行換到第k+1行

③将這一行的若幹倍加到其它未被選中的行上，使得它們的第i列變成0

最後求解即可。

這裡注意

齊次方程組有解的條件：

若rank(A)=n，則隻有零解

若rank(A)=r<n，則有非零解

且非零解有n-r個自由變量

基礎解系有n-r個解

非齊次方程組有解的條件：

若rank(A)≠rank([A,b])，則非齊次方程組無解

若rank(A)=rank([A,b])=n，則非齊次方程組有唯一解解

若rank(A)=rank([A,b])<n，則非齊次方程組有無數組解

我們需要在求解之前判斷解的情況！！！！

上代碼

bool gsxy()
{
	int k=1;
	for (int i=1;i<=n;i++)
	{
		int now = k; 
		while (now<=n && !a[now][i]) now++;
		if (now == n+1) continue;
		for (int j=1;j<=n+1;j++) swap(a[now][j],a[k][j]);
		for (int j=1;j<=n;j++)
		{
			if (j!=k){
				double t = a[j][i]/a[k][i];
				for (int p=1;p<=n+1;p++) a[j][p]=a[j][p]-a[k][p]*t;
			}
		}
		k++;
	}
	if (a[k][n+1]) return false;
	if (k-1<n) return false;
	for (int i=1;i<=k-1;i++) a[i][n+1]=a[i][n+1]/a[i][i];
}
           

那麼對于一些對解取餘的題

我就在除法上，就需要逆元了

void gaosixiaoyuan()
{
	int k=1;
	for (int i=1;i<=n;i++)
	{
		int now=k;
		while (now<=n && !a[now][i]) now++;
		if (now==n+1) continue;
		for (int j=1;j<=n+1;j++) 
		  swap(a[now][j],a[k][j]);
		int inv=power(a[k][i],mod-2);
		for (int j=1;j<=n;j++)
		  if (j!=k)
		  {
		  	int t=(long long)*a[j][i]*inv%mod;
		  	for (int p=1;p<=n+1;p++) 
			  a[j][p]=(a[j][p]-(long long)*t*a[k][p]%mod+mod)%mod;
		  }
		k++;
	}
	if (a[k][n+1]) return false;
	if (k-1<n) return false;
	for (int i=1;i<=k;i++) a[i][n+1]=1ll*a[i][n+1]*power(a[i][i],mod-2)%mod;
}
           

差别不大 主要是逆元

啦啦啦 高斯消元的講解就到這了~

希望大家能懂 嗯 不懂可以加我qq 752742355 有事情随意交流

如果您們能從我的部落格中得到任何一點收獲，都是我莫大的榮幸

共勉！

from y_immortal