矩阵及其基本算法

《矩阵及其基本算法》由会员分享，可在线阅读，更多相关《矩阵及其基本算法（32页珍藏版）》请在金锄头文库上搜索。

1、矩阵及其基本算法计13 刘汝佳矩阵及其基本算法z矩阵的表示z矩阵的基本运 算z小结和应用举 例一、矩阵的表示z三角矩阵的压缩表示法z稀疏矩阵的三元组表示法z稀疏矩阵的十字链表表示 法矩阵在形式上最直接的表示是一个二维数组，但矩阵在形式上最直接的表示是一个二维数组，但 是在一些特殊的场合中，我们需要引入一些特殊是在一些特殊的场合中，我们需要引入一些特殊 的方法来表示一些特殊的矩阵。在本节中，大家的方法来表示一些特殊的矩阵。在本节中，大家 还将了解到以下几种表示方法还将了解到以下几种表示方法: :矩阵的二维数组表示法struct TMatrix int n,m;int numbersMAXN+1M

2、AXN+1; ;我们用二维数组很容易表示一个矩阵。加上矩阵的维数我们用二维数组很容易表示一个矩阵。加上矩阵的维数M M 和和N N，我们可以定义一个我们可以定义一个TMatrix结构结构: :这就是矩阵的二维数组表示法。这就是矩阵的二维数组表示法。怎么样，容易吧？怎么样，容易吧？三角矩阵的压缩表示(1)zN阶上三角矩阵，对称矩阵和反对称矩 阵都只需要储存主对角线以上的共 (N+1)*N/2个元素。z因此，我们可以用一个大小为 (N+1)*N/2的一维数组来表示。z不过，我们需要一个公式，把每个元素 原来的位置(i,j)映射到一维数组的下标k 。三角矩阵的压缩表示(2)z我们从上到下，从左到右地

3、储存各个元 素，如下图：A Aijij前面的数的个数为前面的数的个数为 ：计算得计算得: : 稀疏矩阵z在前面的二维数组表示法中，我们表示 一个N*M的矩阵需要N*M个内存单元 。z如果已知矩阵中存在着大量的0元素， 那么这种表示方法是很浪费空间的。z由于非零元素的个数L十分有限，我们 可以只储存下这L个元素的位置和大小 ，占用的空间便会少得多。稀疏矩阵的三元组表示法z显然，表示稀疏矩阵最直接的方法就是 仅记录下非零元素的个数L和这L个元 素的位置(row,col)和大小(value)，即下 面这个结构：struct TMatrix2 int l;int rowMAXL,colMAXL,val

4、ueMAXL; ;稀疏矩阵的十字链表表示(1)z三元组表示法比较好的解决了稀疏矩阵的空间存储 问题，却忽视了稀疏矩阵可能进行了一些基本操作 。z考虑两个稀疏矩阵A和B相加的问题。对于运算结果 矩阵C来说，可能会因为正负抵消而产生出很多新的 零元素和非零元素，导致三元组需要进行一些插入 和删除操作。当这些操作很频繁的时候，程序的速 度会明显变慢。z在某些特定情况下，我们需要对元素进行检索，由 于三元组的元素之间联系并不紧密，所以检索很不 方便。稀疏矩阵的十字链表表示(2)z为了加强同一行和同一列之间元素的联系， 我们把每一行分别做成一个链表，把每一列 也分别做成一个链表。z通过对链表的遍历，我们

5、可以很方便的按顺 序访问到某一特定行或列的所有元素。插入 和删除操作也很方便。z这样，我们了建立一种十字型的链表结构， 每个结点有上，下，左，右四个指针和自身 的位置坐标，大小共7个域。稀疏矩阵的十字链表表示(3)z结点类型如下定义：struct Tnode int row, col;int value;Tnode *left, *right, *up, *down; ;row,row,colcol分别为该非零元素的位置，分别为该非零元素的位置，valuevalue为它的值。为它的值。 left,right,up,downleft,right,up,down分别为指向四个方向的后继元素。分别为

6、指向四个方向的后继元素。稀疏矩阵的十字链表表示(4)z为了方便的找到每一个包含非零元素的 行和列，我们把所有行串在一起，组成 一个行链表，把所有列也串在一起，组 成一个列链表。像这样： struct TRow int RowNo;TNode * firstnode; ;struct TCol int ColNo;TNode * firstnode; ;矩阵表示方法小结z矩阵的表示方法和应用是分不开的。z我们衡量一种表示方法的优劣，需要从不同 的角度进行分析。z适用范围z空间需求量z基本操作的时间消耗z实现的难易程度z以上几种方法都在某些方面表现良好而其他 方面不够理想，因此我们需要根据实际需要

7、 的侧重点不同，选择合适的表示方法二、矩阵的基本运算z矩阵的判重z矩阵的线性运算z矩阵的转置z矩阵乘法矩阵的判重z在二维数组表示法中，我们可以用一个二重 循环判断两个矩阵是否相等。z在三元组表示方法中，我们如果保证非零元 素是按照从上到下，从左到右的顺序储存的 ，则可以用一个循环直接判断。但如果不能 保证，则需要二重循环。因此在未加说明的 情况下，三元组表示法均需要按顺序保存各 个元素。z在十字链表表示方法中，我们需要依次遍历 每一个非零行（或者列）。矩阵的线性运算z矩阵的数乘: B=kAz在任何一种表示法中，我们都可以通过遍历所有 元素的方法完成数乘运算。z矩阵的加法: C=A+Bz在二维数

8、组表示法中，我们可以通过二重循环来 进行矩阵加法z在稀疏矩阵中，注意到结果中的非零元素所在的 位置必对应A或B中的一个非零元素，所以加法运 算不会在A和B中原非零元素之外的其他位置上生 成新的非零元素。矩阵的线性运算(2)z考虑三元组表示法中的矩阵加法。由于 都需要按顺序储存各个元素，我们应当 按顺序对每个A或B中非零的位置做加 法。z下面有一个例子：矩阵的线性运算(3)z我们记录两个矩阵A，B的当前非零元 素序号pA和pB。为了保证结果的有序 性，我们每次比较这两个当前元素的位 置。z如果A的当前位置靠前，则把A的第pA个元素加 入矩阵C，并使pA=pA+1z如果B的当前位置靠前，则把B的第

9、pB个元素加入 矩阵C，并使pB=pB+1z如果当前位置相同，则先使pA=pA+1, pB=pB+1。 如果A的第pA-1个元素和B的第pB-1个元素的和不 为零，则把它加到矩阵C中。矩阵的线性运算(4)z十字链表表示法下的加法可以一行行的做。 即：z如果A的当前行号比B小，把A的当前行整个复制到C中。z如果B的当前行号比A小，把B的当前行整个复制到C中。z否则把A的当前行和B的当前行的合并结果加入C中。z第三种情况和三元组表示下的加法很类似， 只是下标pA,pB换成了指针。z同样的，需要注意两个非零元素之和可能等 于零，从而不能插入到结果中矩阵的转置(1)z矩阵的转置z在二维数组中，转置可以

10、通过简单的坐标变换得 到z在三元组表示法中，在对每个元素进行坐标变换 后还需要进行一次排序，以维持元素位置的有序 性。z在十字链表表示法中，我们不仅需要对每个结点 进行坐标变换，还需要交换行链表和列链表，以 及更改每个结点四个方向的指针，实现比较麻烦 。矩阵的转置(2)z二维数组的转置可以通过下列代码来实现：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.numbersji=A.numbersij;return B; 对代码稍作修改，我们可以对矩阵进行旋

11、转和镜像变换生成对代码稍作修改，我们可以对矩阵进行旋转和镜像变换生成8 8个新矩阵个新矩阵矩阵的转置(3)z前面提到过，三元组表示法中，矩阵的转置 可以通过坐标变换后排序来实现。z不过，我们通常使用的是另外一种方法。这 种方法不用排序，而速度也更快。z快速转置算法：直接写到正确的位置。z首先，求出每一列第一非零元素转置后的序号。这一步只 需要统计一下每列的非零元素的个数就可以了。z由于每一列的元素在转置以后的先后次序保持不变，每个 元素就可以直接写到该行的下一个空闲位置。矩阵的转置(4)z请看下面的例子：各列非零元素个数为：2,3,0,1各列第一个元素序号：0,2,5,50 1 2 3 4 5

12、123456矩阵乘法(1)z矩阵乘法z在二维数组表示中，最简单的方法就是对每个元素用循环 累加出结果，二重循环枚举每个元素，共三层循环。z在三元组表示中，对于A中的一个元素Aij，我们只需要访问 B中第j行所有元素Bjk，把每个乘积Aij Bjk加到Cik中。这样 ，每遍历A的一行元素，就计算出了C的一行元素。和快速 转置算法类似，我们可以事先算出B的每行元素的下标范围 ，再用一个循环依次考虑A中的每个元素就可以了。z十字链表在本质上是三元组的链式存储，所以乘法和三元 组差别不大，但是实现却麻烦得多。该方法的好处在于， 把中间结果Aij Bjk 加到Cik时，如果Cik并不存在，就需要 对矩阵

13、进行插入操作。在十字链表上的插入操作比三元组 快得多。矩阵乘法(2)zStrassen矩阵乘法z下面，我们来介绍基于二维数组的矩阵相乘算法 。z考虑两个2*2矩阵A和B相乘。普通的方法需要进行8次乘法。矩阵乘法(3)zStrassen的新方法如下：只需要只需要7 7次乘法次乘法!矩阵乘法(3)z当矩阵为2N*2N时，我们可以利用分块 矩阵，分成2*2个2N-1*2N-1矩阵，递归求 解。当N=1时可以直接利用公式得出结 果。z分析指出，Strassen乘法比常规乘法的 加法和乘法运算量都有减少，但存储量 增加，是一种用空间换时间的方法。z此方法还可以推广到矩阵的求逆运算。三、小结与应用举例z矩

14、阵表示小 结z矩阵运算小 结z结束语z鸣谢小结 矩阵的表示z矩阵的表示z矩阵有三种常用的表示方法：二维数组，三元组 和十字链表。z二维数组适合稠密矩阵，表示直观，操作方便z三元组是稀疏矩阵最省空间的表示方法之一，它 可以很好的支持线性运算和乘法运算，且编程复 杂度低，是稀疏矩阵表示法的首选。z十字链表比三元组占用空间大些，不过仍适合稀 疏矩阵的表示，尤其适用于非零元素个数变化较 大的场合，但不适合转置操作，且编程实现难度 较大。小结 矩阵的运算z矩阵的运算z三种方法都可以通过遍历表的方式判定两个矩阵是否相同 。z三种表示方法都能较好的支持线性运算。数乘运算只需要 遍历一次所有元素，而稀疏矩阵的

15、加法运算需要进行类似 有序表合并的操作。z二维数组的转置只需要进行坐标变换，三元组还需要排序 ，而十字链表需要更新多个指针域。转置可以推广到平面 点阵图象的变换，这时一般采用数组来表示矩阵。z矩阵乘法的算法有很多种。基于数组的算法中，Strassen算 法是一种以空间换时间的算法。稀疏的乘法不是依次计算 结果的每个元素，而是依次考虑A和B的每对元素对结果的 贡献。结束语z在前面的内容中，我们讨论了矩阵的表示和基本 运算。希望这些内容能开阔大家的眼界，启发大 家的思维，激发大家进一步学习的兴趣。z这些内容只是矩阵中最最基本的东西。像初等变 换，矩阵求逆，求特征值等方面并为涉及到。但 是如果能熟练的掌握以上内容，相信各位各方面 的能力都会有显著的提高。z每一个内容都有它存在的理由，每一种方法都体 现出一种思路。前面提到的快速转置，Strassen矩 阵乘法等算法都值得我们去思考。鸣 谢z感谢吴老师给我这次与大家交流的机会。z感谢各位同学，特别是我的室友在我准备期 间给我支持和鼓励z感谢一位不愿意我透露其姓名的同学协助我 校对本幻灯片z感谢大家专心听完我的矩阵及其基本算法 同学们辛苦了！同学们辛苦了！