矩阵及其基本算法精选课件.ppt

《矩阵及其基本算法精选课件.ppt》由会员分享，可在线阅读，更多相关《矩阵及其基本算法精选课件.ppt（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于矩阵及其基本算法关于矩阵及其基本算法第一页，本课件共有33页矩阵及其基本算法矩阵及其基本算法zz矩阵的表示zz矩阵的基本运算zz小结和应用举例第二页，本课件共有33页一、矩阵的表示一、矩阵的表示zz三角矩阵的压缩表示法zz稀疏矩阵的三元组表示法zz稀疏矩阵的十字链表表示法矩阵在形式上最直接的表示是一个二维数组，但是在一些特殊的场合中，我们需要引入一些特殊的方法来表示一些特殊的矩阵。在本节中，大家还将了解到以下几种表示方法:第三页，本课件共有33页矩阵的二维数组表示法矩阵的二维数组表示法struct TMatrixstruct TMatrix int n,m;int n,m;int numb

2、ersMAXN+1MAXN+1;int numbersMAXN+1MAXN+1;我们用二维数组很容易表示一个矩阵。加上矩阵的维数我们用二维数组很容易表示一个矩阵。加上矩阵的维数M M和和N N，我，我们可以定义一个们可以定义一个TMatrix结构结构:这就是矩阵的二维数组表示法。这就是矩阵的二维数组表示法。怎么样，容易吧？怎么样，容易吧？第四页，本课件共有33页三角矩阵的压缩表示三角矩阵的压缩表示(1)zzN阶上三角矩阵，对称矩阵和反对称矩阵都只需要储存主对角线以上的共(N+1)*N/2个元素。zz因此，我们可以用一个大小为(N+1)*N/2的一维数组来表示。zz不过，我们需要一个公式，把每个

3、元素原来的位置(i,j)映射到一维数组的下标k。第五页，本课件共有33页三角矩阵的压缩表示三角矩阵的压缩表示(2)zz我们从上到下，从左到右地储存各个元素，如下图：A Aijij前面的数的个数为：前面的数的个数为：计算得计算得:第六页，本课件共有33页稀疏矩阵稀疏矩阵zz在前面的二维数组表示法中，我们表示一个N*M的矩阵需要N*M个内存单元。zz如果已知矩阵中存在着大量的0元素，那么这种表示方法是很浪费空间的。zz由于非零元素的个数L十分有限，我们可以只储存下这L个元素的位置和大小，占用的空间便会少得多。第七页，本课件共有33页稀疏矩阵的三元组表示法稀疏矩阵的三元组表示法zz显然，表示稀疏矩阵

4、最直接的方法就是仅记录下非零元素的个数L和这L个元素的位置(row,col)和大小(value)，即下面这个结构：struct TMatrix2 int l;int rowMAXL,colMAXL,valueMAXL;第八页，本课件共有33页稀疏矩阵的十字链表表示稀疏矩阵的十字链表表示(1)zz三元组表示法比较好的解决了稀疏矩阵的空间存储问题，却忽三元组表示法比较好的解决了稀疏矩阵的空间存储问题，却忽视了稀疏矩阵可能进行了一些基本操作。视了稀疏矩阵可能进行了一些基本操作。zz考虑两个稀疏矩阵考虑两个稀疏矩阵A A和和B B相加的问题。对于运算结果矩阵相加的问题。对于运算结果矩阵C C来来说，可

5、能会因为正负抵消而产生出很多新的零元素和非说，可能会因为正负抵消而产生出很多新的零元素和非零元素，导致三元组需要进行一些插入和删除操作。当零元素，导致三元组需要进行一些插入和删除操作。当这些操作很频繁的时候，程序的速度会明显变慢。这些操作很频繁的时候，程序的速度会明显变慢。zz在某些特定情况下，我们需要对元素进行检索，由于三元组的在某些特定情况下，我们需要对元素进行检索，由于三元组的元素之间联系并不紧密，所以检索很不方便。元素之间联系并不紧密，所以检索很不方便。第九页，本课件共有33页稀疏矩阵的十字链表表示稀疏矩阵的十字链表表示(2)zz为了加强同一行和同一列之间元素的联系，我们为了加强同一行

6、和同一列之间元素的联系，我们把每一行分别做成一个链表，把每一列也分别做把每一行分别做成一个链表，把每一列也分别做成一个链表。成一个链表。zz通过对链表的遍历，我们可以很方便的按顺序访问到某一特定行或列的所有元素。插入和删除操作也很方便。zz这样，我们了建立一种十字型的链表结构，每个结点有上，下，左，右四个指针和自身的位置坐标，大小共7个域。第十页，本课件共有33页稀疏矩阵的十字链表表示稀疏矩阵的十字链表表示(3)zz结点类型如下定义：struct Tnode int row,col;int value;Tnode*left,*right,*up,*down;row,colrow,col分别为该

7、非零元素的位置，分别为该非零元素的位置，valuevalue为它的值。为它的值。left,right,up,downleft,right,up,down分别为指向四个方向的后继元素。分别为指向四个方向的后继元素。第十一页，本课件共有33页稀疏矩阵的十字链表表示稀疏矩阵的十字链表表示(4)zz为了方便的找到每一个包含非零元素的行和列，我们把所有行串在一起，组成一个行链表，把所有列也串在一起，组成一个列链表。像这样：struct TRow int RowNo;TNode*firstnode;struct TCol int ColNo;TNode*firstnode;第十二页，本课件共有33页矩阵表

8、示方法小结矩阵表示方法小结zz矩阵的表示方法和应用是分不开的。zz我们衡量一种表示方法的优劣，需要从不同的角度进行分析。zz适用范围适用范围zz空间需求量zz基本操作的时间消耗zz实现的难易程度zz以上几种方法都在某些方面表现良好而其他方面以上几种方法都在某些方面表现良好而其他方面不够理想，因此我们需要根据实际需要的侧重点不够理想，因此我们需要根据实际需要的侧重点不同，选择合适的表示方法不同，选择合适的表示方法第十三页，本课件共有33页二、矩阵的基本运算二、矩阵的基本运算zz矩阵的判重zz矩阵的线性运算zz矩阵的转置zz矩阵乘法第十四页，本课件共有33页矩阵的判重矩阵的判重zz在二维数组表示法

9、中，我们可以用一个二重循环判在二维数组表示法中，我们可以用一个二重循环判断两个矩阵是否相等。断两个矩阵是否相等。zz在三元组表示方法中，我们如果保证非零元素是按在三元组表示方法中，我们如果保证非零元素是按照从上到下，从左到右的顺序储存的，则可以用一照从上到下，从左到右的顺序储存的，则可以用一个循环直接判断。但如果不能保证，则需要二重循个循环直接判断。但如果不能保证，则需要二重循环。因此在未加说明的情况下，三元组表示法均需环。因此在未加说明的情况下，三元组表示法均需要按顺序保存各个元素。要按顺序保存各个元素。zz在十字链表表示方法中，我们需要依次遍历每一个非零行（或者列）。第十五页，本课件共有3

10、3页矩阵的线性运算矩阵的线性运算zz矩阵的数乘:B=kAzz在任何一种表示法中，我们都可以通过遍历所有元在任何一种表示法中，我们都可以通过遍历所有元素的方法完成数乘运算。素的方法完成数乘运算。zz矩阵的加法:C=A+Bzz在二维数组表示法中，我们可以通过二重循环来进行矩在二维数组表示法中，我们可以通过二重循环来进行矩阵加法阵加法zz在稀疏矩阵中，注意到结果中的非零元素所在的位置必在稀疏矩阵中，注意到结果中的非零元素所在的位置必对应对应A A或或B B中的一个非零元素，所以加法运算不会在中的一个非零元素，所以加法运算不会在A A和和B B中原非零元素之外的其他位置上生成新的非零元中原非零元素之外

11、的其他位置上生成新的非零元素。素。第十六页，本课件共有33页矩阵的线性运算矩阵的线性运算(2)zz考虑三元组表示法中的矩阵加法。由于都需要按顺序储存各个元素，我们应当按顺序对每个A或B中非零的位置做加法。zz下面有一个例子：第十七页，本课件共有33页矩阵的线性运算矩阵的线性运算(3)zz我们记录两个矩阵A，B的当前非零元素序号pA和pB。为了保证结果的有序性，我们每次比较这两个当前元素的位置。zz如果如果A A的当前位置靠前，则把的当前位置靠前，则把A A的第的第pApA个元素加入矩个元素加入矩阵阵C C，并使，并使pA=pA+1pA=pA+1zz如果如果B B的当前位置靠前，则把的当前位置靠

12、前，则把B B的第的第pBpB个元素加入矩阵个元素加入矩阵C C，并使，并使pB=pB+1pB=pB+1zz如果当前位置相同，则先使如果当前位置相同，则先使pA=pA+1,pB=pB+1pA=pA+1,pB=pB+1。如果。如果A A的第的第pA-1pA-1个元素和个元素和B B的第的第pB-1pB-1个元素的和不为零，则把它个元素的和不为零，则把它加到矩阵加到矩阵C C中。中。第十八页，本课件共有33页矩阵的线性运算矩阵的线性运算(4)zz十字链表表示法下的加法可以一行行的做。即：十字链表表示法下的加法可以一行行的做。即：zz如果如果A A的当前行号比的当前行号比B B小，把小，把A A的当

13、前行整个复制到的当前行整个复制到C C中。中。zz如果如果B B的当前行号比的当前行号比A A小，把小，把B B的当前行整个复制到的当前行整个复制到C C中。中。zz否则把否则把A A的当前行和的当前行和B B的当前行的合并结果加入的当前行的合并结果加入C C中。中。zz第三种情况和三元组表示下的加法很类似，只是下标pA,pBpA,pB换成了指针。换成了指针。zz同样的，需要注意两个非零元素之和可能等于零，从而不能插入到结果中第十九页，本课件共有33页矩阵的转置矩阵的转置(1)zz矩阵的转置zz在二维数组中，转置可以通过简单的坐标变换得到在二维数组中，转置可以通过简单的坐标变换得到zz在三元组

14、表示法中，在对每个元素进行坐标变换后还需要在三元组表示法中，在对每个元素进行坐标变换后还需要进行一次排序，以维持元素位置的有序性。进行一次排序，以维持元素位置的有序性。zz在十字链表表示法中，我们不仅需要对每个结点进行坐在十字链表表示法中，我们不仅需要对每个结点进行坐标变换，还需要交换行链表和列链表，以及更改每个结标变换，还需要交换行链表和列链表，以及更改每个结点四个方向的指针，实现比较麻烦。点四个方向的指针，实现比较麻烦。第二十页，本课件共有33页矩阵的转置矩阵的转置(2)zz二维数组的转置可以通过下列代码来实现：二维数组的转置可以通过下列代码来实现：void MatrixT(TMatrix

15、 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.numbersji=A.numbersij;return B;对代码稍作修改，我们可以对矩阵进行旋转和镜像变换生成对代码稍作修改，我们可以对矩阵进行旋转和镜像变换生成8 8个新矩阵个新矩阵第二十一页，本课件共有33页矩阵的转置矩阵的转置(3)zz前面提到过，三元组表示法中，矩阵的转置可以通前面提到过，三元组表示法中，矩阵的转置可以通过坐标变换后排序来实现。过坐标变换后排序来实现。zz不过，我们通常使用的是另外一种方法。这种方法不用排序，而速度也更快。

16、zz快速转置算法：直接写到正确的位置。zz首先，求出每一列第一非零元素转置后的序号。这一步只需要统计一下首先，求出每一列第一非零元素转置后的序号。这一步只需要统计一下每列的非零元素的个数就可以了。每列的非零元素的个数就可以了。zz由于每一列的元素在转置以后的先后次序保持不变，每个元素就由于每一列的元素在转置以后的先后次序保持不变，每个元素就可以直接写到该行的下一个空闲位置。可以直接写到该行的下一个空闲位置。第二十二页，本课件共有33页矩阵的转置矩阵的转置(4)zz请看下面的例子：请看下面的例子：各列非零元素个数为：2,3,0,1各列第一个元素序号：0,2,5,50 1 2 3 4 512345

17、6第二十三页，本课件共有33页矩阵乘法矩阵乘法(1)zz矩阵乘法zz在二维数组表示中，最简单的方法就是对每个元素用循环累在二维数组表示中，最简单的方法就是对每个元素用循环累加出结果，二重循环枚举每个元素，共三层循环。加出结果，二重循环枚举每个元素，共三层循环。zz在三元组表示中，对于在三元组表示中，对于A A中的一个元素中的一个元素A Aij ij，我们只需要访问，我们只需要访问B B中第中第j j行所有元素行所有元素B Bjkjk，把每个乘积，把每个乘积A Aij ij B Bjkjk加到加到C Cikik中。这样，每遍历中。这样，每遍历A A的的一行元素，就计算出了一行元素，就计算出了C

18、C的一行元素。和快速转置算法类似，我们的一行元素。和快速转置算法类似，我们可以事先算出可以事先算出B B的每行元素的下标范围，再用一个循环依次考虑的每行元素的下标范围，再用一个循环依次考虑A A中的每个元素就可以了。中的每个元素就可以了。zz十字链表在本质上是三元组的链式存储，所以乘法和三元组十字链表在本质上是三元组的链式存储，所以乘法和三元组差别不大，但是实现却麻烦得多。该方法的好处在于，把中差别不大，但是实现却麻烦得多。该方法的好处在于，把中间结果间结果A Aij ij B Bjkjk 加到加到C Cikik时，如果时，如果C Cikik并不存在，就需要对矩阵进行并不存在，就需要对矩阵进行

19、插入操作。在十字链表上的插入操作比三元组快得多。插入操作。在十字链表上的插入操作比三元组快得多。第二十四页，本课件共有33页矩阵乘法矩阵乘法(2)zzStrassen矩阵乘法zz下面，我们来介绍基于二维数组的矩阵相乘算法。下面，我们来介绍基于二维数组的矩阵相乘算法。zz考虑两个考虑两个2*22*2矩阵矩阵A A和和B B相乘。相乘。普通的方法需要进行8次乘法。第二十五页，本课件共有33页矩阵乘法矩阵乘法(3)zzStrassen的新方法如下：只需要只需要7 7次乘法次乘法!第二十六页，本课件共有33页矩阵乘法矩阵乘法(3)zz当矩阵为2N*2N时，我们可以利用分块矩阵，分成2*2个2N-1*2

20、N-1矩阵，递归求解。当N=1时可以直接利用公式得出结果。zz分析指出，Strassen乘法比常规乘法的加法和乘法运算量都有减少，但存储量增加，是一种用空间换时间的方法。zz此方法还可以推广到矩阵的求逆运算。第二十七页，本课件共有33页三、小结与应用举例三、小结与应用举例zz矩阵表示小结zz矩阵运算小结zz结束语zz鸣谢第二十八页，本课件共有33页小结小结 矩阵的表示矩阵的表示zz矩阵的表示zz矩阵有三种常用的表示方法：二维数组，三元组和矩阵有三种常用的表示方法：二维数组，三元组和十字链表。十字链表。zz二维数组适合稠密矩阵，表示直观，操作方便二维数组适合稠密矩阵，表示直观，操作方便zz三元组

21、是稀疏矩阵最省空间的表示方法之一，它可以很三元组是稀疏矩阵最省空间的表示方法之一，它可以很好的支持线性运算和乘法运算，且编程复杂度低，是稀好的支持线性运算和乘法运算，且编程复杂度低，是稀疏矩阵表示法的首选。疏矩阵表示法的首选。zz十字链表比三元组占用空间大些，不过仍适合稀疏十字链表比三元组占用空间大些，不过仍适合稀疏矩阵的表示，尤其适用于非零元素个数变化较大的矩阵的表示，尤其适用于非零元素个数变化较大的场合，但不适合转置操作，且编程实现难度较大。场合，但不适合转置操作，且编程实现难度较大。第二十九页，本课件共有33页小结小结 矩阵的运算矩阵的运算zz矩阵的运算zz三种方法都可以通过遍历表的方式

22、判定两个矩阵是否相同。三种方法都可以通过遍历表的方式判定两个矩阵是否相同。zz三种表示方法都能较好的支持线性运算。数乘运算只需要遍历一次三种表示方法都能较好的支持线性运算。数乘运算只需要遍历一次所有元素，而稀疏矩阵的加法运算需要进行类似有序表合并的操作。所有元素，而稀疏矩阵的加法运算需要进行类似有序表合并的操作。zz二维数组的转置只需要进行坐标变换，三元组还需要排序，而十二维数组的转置只需要进行坐标变换，三元组还需要排序，而十字链表需要更新多个指针域。转置可以推广到平面点阵图象的变字链表需要更新多个指针域。转置可以推广到平面点阵图象的变换，这时一般采用数组来表示矩阵。换，这时一般采用数组来表示

23、矩阵。zz矩阵乘法的算法有很多种。基于数组的算法中，矩阵乘法的算法有很多种。基于数组的算法中，StrassenStrassen算法算法是一种以空间换时间的算法。稀疏的乘法不是依次计算结果是一种以空间换时间的算法。稀疏的乘法不是依次计算结果的每个元素，而是依次考虑的每个元素，而是依次考虑A A和和B B的每对元素对结果的贡献。的每对元素对结果的贡献。第三十页，本课件共有33页结束语结束语zz在前面的内容中，我们讨论了矩阵的表示和基本运算。在前面的内容中，我们讨论了矩阵的表示和基本运算。希望这些内容能开阔大家的眼界，启发大家的思维，激希望这些内容能开阔大家的眼界，启发大家的思维，激发大家进一步学习

24、的兴趣。发大家进一步学习的兴趣。zz这些内容只是矩阵中最最基本的东西。像初等变换，矩阵这些内容只是矩阵中最最基本的东西。像初等变换，矩阵求逆，求特征值等方面并为涉及到。但是如果能熟练的掌求逆，求特征值等方面并为涉及到。但是如果能熟练的掌握以上内容，相信各位各方面的能力都会有显著的提高。握以上内容，相信各位各方面的能力都会有显著的提高。zz每一个内容都有它存在的理由，每一种方法都体现出每一个内容都有它存在的理由，每一种方法都体现出一种思路。前面提到的快速转置，一种思路。前面提到的快速转置，StrassenStrassen矩阵乘法等矩阵乘法等算法都值得我们去思考。算法都值得我们去思考。第三十一页，本课件共有33页鸣鸣 谢谢zz感谢吴老师给我这次与大家交流的机会。zz感谢各位同学，特别是我的室友在我准备期间给我支持和鼓励zz感谢一位不愿意我透露其姓名的同学协助我校对本幻灯片zz感谢大家专心听完我的矩阵及其基本算法同学们辛苦了！第三十二页，本课件共有33页感感谢谢大大家家观观看看第三十三页，本课件共有33页