矩陣及其基本算法.ppt

1、矩陣及其基本算法,計(jì)13 劉汝佳,矩陣及其基本算法,矩陣的表示 矩陣的基本運(yùn)算 小結(jié)和應(yīng)用舉例,一、矩陣的表示,三角矩陣的壓縮表示法 稀疏矩陣的三元組表示法 稀疏矩陣的十字鏈表表示法,矩陣在形式上最直接的表示是一個(gè)二維數(shù)組，但是在一些特殊的場(chǎng)合中，我們需要引入一些特殊的方法來表示一些特殊的矩陣。在本節(jié)中，大家還將了解到以下幾種表示方法:,矩陣的二維數(shù)組表示法,struct TMatrix int n,m; int numbersMAXN+1MAXN+1; ;,我們用二維數(shù)組很容易表示一個(gè)矩陣。加上矩陣的維數(shù)M和N，我們可以定義一個(gè)TMatrix結(jié)構(gòu):,這就是矩陣的二維數(shù)組表示法。怎么樣，容易吧

2、？,三角矩陣的壓縮表示(1),N階上三角矩陣，對(duì)稱矩陣和反對(duì)稱矩陣都只需要儲(chǔ)存主對(duì)角線以上的共(N+1)*N/2個(gè)元素。 因此，我們可以用一個(gè)大小為(N+1)*N/2的一維數(shù)組來表示。 不過，我們需要一個(gè)公式，把每個(gè)元素原來的位置(i,j)映射到一維數(shù)組的下標(biāo)k。,三角矩陣的壓縮表示(2),我們從上到下，從左到右地儲(chǔ)存各個(gè)元素，如下圖：,Aij前面的數(shù)的個(gè)數(shù)為：,計(jì)算得:,稀疏矩陣,在前面的二維數(shù)組表示法中，我們表示一個(gè)N*M的矩陣需要N*M個(gè)內(nèi)存單元。 如果已知矩陣中存在著大量的0元素，那么這種表示方法是很浪費(fèi)空間的。 由于非零元素的個(gè)數(shù)L十分有限，我們可以只儲(chǔ)存下這L個(gè)元素的位置和大小，占

3、用的空間便會(huì)少得多。,稀疏矩陣的三元組表示法,顯然，表示稀疏矩陣最直接的方法就是僅記錄下非零元素的個(gè)數(shù)L和這L個(gè)元素的位置(row,col)和大小(value)，即下面這個(gè)結(jié)構(gòu)：,struct TMatrix2 int l; int rowMAXL,colMAXL,valueMAXL; ;,稀疏矩陣的十字鏈表表示(1),三元組表示法比較好的解決了稀疏矩陣的空間存儲(chǔ)問題，卻忽視了稀疏矩陣可能進(jìn)行了一些基本操作。 考慮兩個(gè)稀疏矩陣A和B相加的問題。對(duì)于運(yùn)算結(jié)果矩陣C來說，可能會(huì)因?yàn)檎?fù)抵消而產(chǎn)生出很多新的零元素和非零元素，導(dǎo)致三元組需要進(jìn)行一些插入和刪除操作。當(dāng)這些操作很頻繁的時(shí)候，程序的速度會(huì)明

4、顯變慢。 在某些特定情況下，我們需要對(duì)元素進(jìn)行檢索，由于三元組的元素之間聯(lián)系并不緊密，所以檢索很不方便。,稀疏矩陣的十字鏈表表示(2),為了加強(qiáng)同一行和同一列之間元素的聯(lián)系，我們把每一行分別做成一個(gè)鏈表，把每一列也分別做成一個(gè)鏈表。 通過對(duì)鏈表的遍歷，我們可以很方便的按順序訪問到某一特定行或列的所有元素。插入和刪除操作也很方便。 這樣，我們了建立一種十字型的鏈表結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)有上，下，左，右四個(gè)指針和自身的位置坐標(biāo)，大小共7個(gè)域。,稀疏矩陣的十字鏈表表示(3),結(jié)點(diǎn)類型如下定義：,struct Tnode int row, col; int value; Tnode *left, *right

5、, *up, *down; ;,row,col分別為該非零元素的位置，value為它的值。,left,right,up,down分別為指向四個(gè)方向的后繼元素。,稀疏矩陣的十字鏈表表示(4),為了方便的找到每一個(gè)包含非零元素的行和列，我們把所有行串在一起，組成一個(gè)行鏈表，把所有列也串在一起，組成一個(gè)列鏈表。像這樣：,struct TRow int RowNo; TNode * firstnode; ;,struct TCol int ColNo; TNode * firstnode; ;,矩陣表示方法小結(jié),矩陣的表示方法和應(yīng)用是分不開的。 我們衡量一種表示方法的優(yōu)劣，需要從不同的角度進(jìn)行分析。

6、適用范圍 空間需求量 基本操作的時(shí)間消耗 實(shí)現(xiàn)的難易程度 以上幾種方法都在某些方面表現(xiàn)良好而其他方面不夠理想，因此我們需要根據(jù)實(shí)際需要的側(cè)重點(diǎn)不同，選擇合適的表示方法,二、矩陣的基本運(yùn)算,矩陣的判重 矩陣的線性運(yùn)算 矩陣的轉(zhuǎn)置 矩陣乘法,矩陣的判重,在二維數(shù)組表示法中，我們可以用一個(gè)二重循環(huán)判斷兩個(gè)矩陣是否相等。 在三元組表示方法中，我們?nèi)绻ＷC非零元素是按照從上到下，從左到右的順序儲(chǔ)存的，則可以用一個(gè)循環(huán)直接判斷。但如果不能保證，則需要二重循環(huán)。因此在未加說明的情況下，三元組表示法均需要按順序保存各個(gè)元素。 在十字鏈表表示方法中，我們需要依次遍歷每一個(gè)非零行（或者列）。,矩陣的線性運(yùn)算,矩陣

7、的數(shù)乘: B=kA 在任何一種表示法中，我們都可以通過遍歷所有元素的方法完成數(shù)乘運(yùn)算。 矩陣的加法: C=A+B 在二維數(shù)組表示法中，我們可以通過二重循環(huán)來進(jìn)行矩陣加法 在稀疏矩陣中，注意到結(jié)果中的非零元素所在的位置必對(duì)應(yīng)A或B中的一個(gè)非零元素，所以加法運(yùn)算不會(huì)在A和B中原非零元素之外的其他位置上生成新的非零元素。,矩陣的線性運(yùn)算(2),考慮三元組表示法中的矩陣加法。由于都需要按順序儲(chǔ)存各個(gè)元素，我們應(yīng)當(dāng)按順序?qū)γ總€(gè)A或B中非零的位置做加法。 下面有一個(gè)例子：,矩陣的線性運(yùn)算(3),我們記錄兩個(gè)矩陣A，B的當(dāng)前非零元素序號(hào)pA和pB。為了保證結(jié)果的有序性，我們每次比較這兩個(gè)當(dāng)前元素的位置。 如

8、果A的當(dāng)前位置靠前，則把A的第pA個(gè)元素加入矩陣C，并使pA=pA+1 如果B的當(dāng)前位置靠前，則把B的第pB個(gè)元素加入矩陣C，并使pB=pB+1 如果當(dāng)前位置相同，則先使pA=pA+1, pB=pB+1。如果A的第pA-1個(gè)元素和B的第pB-1個(gè)元素的和不為零，則把它加到矩陣C中。,矩陣的線性運(yùn)算(4),十字鏈表表示法下的加法可以一行行的做。即： 如果A的當(dāng)前行號(hào)比B小，把A的當(dāng)前行整個(gè)復(fù)制到C中。 如果B的當(dāng)前行號(hào)比A小，把B的當(dāng)前行整個(gè)復(fù)制到C中。 否則把A的當(dāng)前行和B的當(dāng)前行的合并結(jié)果加入C中。 第三種情況和三元組表示下的加法很類似，只是下標(biāo)pA,pB換成了指針。 同樣的，需要注意兩個(gè)非

9、零元素之和可能等于零，從而不能插入到結(jié)果中,矩陣的轉(zhuǎn)置(1),矩陣的轉(zhuǎn)置 在二維數(shù)組中，轉(zhuǎn)置可以通過簡(jiǎn)單的坐標(biāo)變換得到 在三元組表示法中，在對(duì)每個(gè)元素進(jìn)行坐標(biāo)變換后還需要進(jìn)行一次排序，以維持元素位置的有序性。 在十字鏈表表示法中，我們不僅需要對(duì)每個(gè)結(jié)點(diǎn)進(jìn)行坐標(biāo)變換，還需要交換行鏈表和列鏈表，以及更改每個(gè)結(jié)點(diǎn)四個(gè)方向的指針，實(shí)現(xiàn)比較麻煩。,矩陣的轉(zhuǎn)置(2),二維數(shù)組的轉(zhuǎn)置可以通過下列代碼來實(shí)現(xiàn)：,void MatrixT(TMatrix A) TMatrix B; B.m=A.n; B.n=A.m; for(int i=1;i=A.n;i+) for(int j=1;j=A.m;j+) B.nu

10、mbersji=A.numbersij; return B; ,對(duì)代碼稍作修改，我們可以對(duì)矩陣進(jìn)行旋轉(zhuǎn)和鏡像變換生成8個(gè)新矩陣,矩陣的轉(zhuǎn)置(3),前面提到過，三元組表示法中，矩陣的轉(zhuǎn)置可以通過坐標(biāo)變換后排序來實(shí)現(xiàn)。 不過，我們通常使用的是另外一種方法。這種方法不用排序，而速度也更快。 快速轉(zhuǎn)置算法：直接寫到正確的位置。 首先，求出每一列第一非零元素轉(zhuǎn)置后的序號(hào)。這一步只需要統(tǒng)計(jì)一下每列的非零元素的個(gè)數(shù)就可以了。 由于每一列的元素在轉(zhuǎn)置以后的先后次序保持不變，每個(gè)元素就可以直接寫到該行的下一個(gè)空閑位置。,矩陣的轉(zhuǎn)置(4),請(qǐng)看下面的例子：,各列非零元素個(gè)數(shù)為：2,3,0,1,各列第一個(gè)元素序號(hào)：

11、0,2,5,5,0 1 2 3 4 5,1,2,3,4,5,6,矩陣乘法(1),矩陣乘法 在二維數(shù)組表示中，最簡(jiǎn)單的方法就是對(duì)每個(gè)元素用循環(huán)累加出結(jié)果，二重循環(huán)枚舉每個(gè)元素，共三層循環(huán)。 在三元組表示中，對(duì)于A中的一個(gè)元素Aij，我們只需要訪問B中第j行所有元素Bjk，把每個(gè)乘積Aij Bjk加到Cik中。這樣，每遍歷A的一行元素，就計(jì)算出了C的一行元素。和快速轉(zhuǎn)置算法類似，我們可以事先算出B的每行元素的下標(biāo)范圍，再用一個(gè)循環(huán)依次考慮A中的每個(gè)元素就可以了。 十字鏈表在本質(zhì)上是三元組的鏈?zhǔn)酱鎯?chǔ)，所以乘法和三元組差別不大，但是實(shí)現(xiàn)卻麻煩得多。該方法的好處在于，把中間結(jié)果Aij Bjk 加到Cik

12、時(shí)，如果Cik并不存在，就需要對(duì)矩陣進(jìn)行插入操作。在十字鏈表上的插入操作比三元組快得多。,矩陣乘法(2),Strassen矩陣乘法 下面，我們來介紹基于二維數(shù)組的矩陣相乘算法。 考慮兩個(gè)2*2矩陣A和B相乘。,普通的方法需要進(jìn)行8次乘法。,矩陣乘法(3),Strassen的新方法如下：,只需要7次乘法!,矩陣乘法(3),當(dāng)矩陣為2N*2N時(shí)，我們可以利用分塊矩陣，分成2*2個(gè)2N-1*2N-1矩陣，遞歸求解。當(dāng)N=1時(shí)可以直接利用公式得出結(jié)果。 分析指出，Strassen乘法比常規(guī)乘法的加法和乘法運(yùn)算量都有減少，但存儲(chǔ)量增加，是一種用空間換時(shí)間的方法。 此方法還可以推廣到矩陣的求逆運(yùn)算。,三、

13、小結(jié)與應(yīng)用舉例,矩陣表示小結(jié) 矩陣運(yùn)算小結(jié) 結(jié)束語(yǔ) 鳴謝,小結(jié) 矩陣的表示,矩陣的表示 矩陣有三種常用的表示方法：二維數(shù)組，三元組和十字鏈表。 二維數(shù)組適合稠密矩陣，表示直觀，操作方便 三元組是稀疏矩陣最省空間的表示方法之一，它可以很好的支持線性運(yùn)算和乘法運(yùn)算，且編程復(fù)雜度低，是稀疏矩陣表示法的首選。 十字鏈表比三元組占用空間大些，不過仍適合稀疏矩陣的表示，尤其適用于非零元素個(gè)數(shù)變化較大的場(chǎng)合，但不適合轉(zhuǎn)置操作，且編程實(shí)現(xiàn)難度較大。,小結(jié) 矩陣的運(yùn)算,矩陣的運(yùn)算 三種方法都可以通過遍歷表的方式判定兩個(gè)矩陣是否相同。 三種表示方法都能較好的支持線性運(yùn)算。數(shù)乘運(yùn)算只需要遍歷一次所有元素，而稀疏矩陣的加法運(yùn)算需要進(jìn)行類似有序表合并的操作。 二維數(shù)組的轉(zhuǎn)置只需要進(jìn)行坐標(biāo)變換，三元組還需要排序，而十字鏈表需要更新多個(gè)指針域。轉(zhuǎn)置可以推廣到平面點(diǎn)陣圖象的變換，這時(shí)一般采用數(shù)組來表示矩陣。 矩陣乘法的算法有很多種?；跀?shù)組的算法中，Strassen算法是一種以空間換時(shí)間的算法。稀疏的乘法不是依次計(jì)算結(jié)果的每個(gè)元素，而是依次考慮A和B的每對(duì)元素對(duì)結(jié)果的貢獻(xiàn)。,結(jié)束語(yǔ),在前面的內(nèi)容中，我們討論了矩陣的表示和基本運(yùn)算。希望這些內(nèi)容能開闊大家的眼界，啟發(fā)大家的思維，激發(fā)大家進(jìn)一步學(xué)習(xí)的興趣。 這些內(nèi)容只是矩陣中最最基本的東西。像初等變換，矩