范文一:线性独立与矩阵的秩及求解
线性独立与矩阵的秩 对一组给定的向量,线性独立是一个重要的性质。如果不存在一组标量a1,a2,···,an (它们不构成零向量),使得
aX =0
则向量x1,x2,···,xn 线性独立。
确定一组向量是否线性独立的方法之一是试图从这组向量构成一组正交向量。如果从已知向量构成向量的范数是零或接近零(例如对计算机计算为10^-6),则对应的向量线性相关。换句话说,该向量可由线性独立向量的线性组合而构成。在复杂的化学反应系统中确定独立反应及在一次分析中估算独立无因次数群时,线性独立特性是非常有用的。
Gram-Schmidt 正交技术
矩阵的秩
一组向量中线性独立向量的数目称为由已知向量构成的矩阵的秩。换言之,矩阵的秩定义为矩阵中包含的最大非零行列式的阶数。在一个方阵中,如果矩阵等于矩阵的阶数,则该矩阵是非奇异矩阵。如果rA 和rB 是两个矩阵A 和B 的秩,C 是A 和B 的乘积,则C 的秩小于或等于A 和B 的秩的较小值。换言之
r C ≤min(r A , r B )
左乘或右乘一个非奇异方阵不改变矩阵的秩。
在因次分析中,矩阵的秩非常重要。因为无因次乘积的数目等于总变量数减去它们的因次矩阵的秩。第六章讨论了线性独立性在化学反应系统这的应用。在程序P -6.1中列出了用Gram -Schmidt 正交技术确定矩阵秩的计算机程序。 Gram-Schmidt 正交技术应用例
Fortran 语言程序-用正交技术确定一个矩阵的秩
C PROGRAM P-6.1
C SUBROUTINE RANK(A,L,M,N,NRANK);函数名称RANK, 参变量A,L,M,N 和NRANK
C THIS SUBPROGRAM DETERMINES (确定)THE RANK OF A MATRIX (该子程序用于确定一个已知矩阵A(M,N)的行秩)
C MATRIX IS DEFINED BY A(M,N) ―要输入的已知的矩阵数据
C GRAM-SCHMIDT ORTHOGONALIZATION IS USED
―使用的方法是GRAM-SCHMIDT 的正交法,
C NRANK - RANK OF ROWS ―NRANK 行的秩?
C M - NUMBER OF ROWS ――行数目
C N - NUMBER OF COLUMN S――列数目
C L(J) - FLAG FOR LINER INDEPENDENCE OF COLUMN J
J 列的线性独立标记向量;
C =1 LINEARLY INDEPENDENT (=1,线性独立)
C =0 LINEARLY DEPENDENT (=0,非线性独立)
DIMENSION A(M,N),L(N),B(20,20)
;定义变量,A(M,N)已知矩阵,给定的矩阵
;L(N)线性独立性标记向量,秩的数值统计之用
;B(20,20)备用数组空间
;计算起点
DO 10 J=1,N ;循环体A ,句10止。
10 L(J)=1 ;给秩标记号赋初值1,选列秩
DO 20 K=1,M ;循环体B ,句20止。M 行
20 B(K,1)=A(K,1) ;将A( )第一列的值传给B ()第一列;
DO 80 J=2,N ;循环体C ,句止于80。J=2->Norm ,句80为
continue ;
JM1=J-1
DO 30 K=1,M ;循环D ,止于30。按行进行拷贝
30 B(K,J)=A(K,J) ;按行进行,单元赋值
DO 60 I=1,JM1 ;循环体E ,终点句60
IF (L(I).EQ.0) GO TO 60 ;判断是否需要进行40,50计算
TERM1 =0 ;为循环体F 做准备
TERM2 =0 ;
DO 40 K=1,M ;循环体F ,终40句
TERM1 =TERM1+B(K,I)*A(K,J) j -1?y i ?y i ;等于计算y i =x i -∑ 中的∑(y i x i ) x i ? ?y y i =1?i =1i ?i j -1
40 TERM2 =TERM2+B(K,I)**2 ;等于y =(∑y i 2) 1/2中未开根号的部分,范数计算
i =1n
?y i ?1x i ??TERM = TERM1/TERM2 ;等于∑ ?y y i =1?i ?i j -1
DO 50 K=1,M ;按行展开处理,循环G
50 B(K,J)=B(K,J)-TERM*B(K,I)
?y i ?y i x i ?;固定列号J ,I ,等于求解y i =x i -∑ ?y y i =1?i ?i j -1
60 CONTINUE ;循环G 的终端语句
ANORM =0 ;赋初值,中间变量
DO 70 K=1,M ;循环H
70 ANORM = ANORM + B(K,J)**2 ; Norm-范数, 结果与句40对应?
;逐行计算经过变换的矩阵B ()的值,找出不全为零的行的数目
IF (ANORM .LE. 1.E-8) L(J)=0 ;如果该行的加和值足够小的话,则
标记号改写为0,否则,仍然保持为1。
80 CONTINUE ;循环H 和循环C 的终端语句
NRANK = 0 ;将秩变量归零
DO 90 J=1,N ;检查向量L (J )中等于1的单元个数的数目
90 IF (L(J).EQ.1) NRANK = NRANK +1
;统计L (J )向量中单元值等于1的项数。如果L(J)单元值
等于1,则行秩数目加上1。最终返回总计数值NRANK 。
RETURN
END
在控制论中,矩阵的秩可以用来确定线性系统是否为可控制的,或可观察的。
j := 1
while (i ≤ m and j ≤ n) do
Find pivot in column j, starting in row i:
maxi := i
for k := i+1 to m do
if abs(A[k,j]) > abs(A[maxi,j]) then
maxi := k
end if
end for
if A[maxi,j] ≠ 0 then
swap rows i and maxi, but do not change the value of i
Now A[i,j] will contain the old value of A[maxi,j].
divide each entry in row i by A[i,j]
Now A[i,j] will have the value 1.
for u := i+1 to m do
subtract A[u,j] * row i from row u
Now A[u,j] will be 0, since A[u,j] - A[i,j] * A[u,j] = A[u,j] - 1 * A[u,j] = 0. end for
i := i + 1
end if
j := j + 1
end while
这个算法和之前谈及的有点儿不同,它由绝对值最大的部分开始做起,这样可以改善算法上的稳定性。将经过调换后的第一列作为起点,这算法由左至右地计算。每作出以下两个步骤,才跳到下一列:
1. 定出每列的最后一个非0的数,将每行的数字除以该数,使到每行的第一个数成为1;
2. 将每行的数字减去第一行的第一个数的某个倍数。
所有步骤完成后,这个矩阵会变成一个行梯阵式,再用代入法就可解决这个方程组。
范文二:基于向量线性组合的并行矩阵乘法研究
文章编号:1007-757X (2015)07-0005-03
基于向量线性组合的并行矩阵乘法研究
郑建华,沈玉利,朱蓉
摘 要:为了解决 MapReduce 框架下现有矩阵乘法算法性能不高的问题,提出了一种基于向量线性组合:Vector Linear Combination:VLC:的矩阵乘法处理模式,介绍了采用 MapReduce 框架实现基于 VLC 模式的矩阵乘法算法的过程,其 中 Map 函数负责实现数据预处理,Reduce 函数完成数乘操作和向量线性叠加。随后,讨论了影响算法执行时间的因素, 并从理论方面比较了两种算法性能。实验结果显示,新算法所需执行时间更少,效率更高,与理论分析相吻合。 关键词:并行矩阵乘法;MapReduce;线性组合
中图分类号:TP312 文献标志码:A
[13]0 引言 ,从而影响 上读取 Map 的输出,导致系统 I/O 时间增加
整个计算性能。 矩阵乘法应用广泛,传统串行矩阵乘法算法需要占用较 3 为解决 BLM 模式在 MapReduce 框架中出现的问题,本 多工作单元和较大存储空间,其时间复杂度一般为 O(n) , [1]文提出采用向量线性组合的模式实现矩阵乘法,拟主要通过 随着 n 值的增大,计算效率将受到很大的影响。随着科学 减少 Map 阶段输出的中间键值对来提高计算性能。 技术的发展,并行计算机的出现使大规模地提高矩阵运算速
度成为可能,为了实现并行计算,需要将矩阵进行预划分, 1 向量线性组合的矩阵乘法原理 然后指派给不同的处理器。常用的矩阵分块乘法运算都是将 m,k k,n ,,矩阵分块再用递归算法进行计算,比较著名的分块矩阵乘法 A , (a), A , B , ,假设矩阵 ij mk ,,矩阵 [2][3]算法有 Cannon算法,Fox算法,DNS 算法,但是采用这 些算法实现较为复杂,它们要求处理器个数 P 和矩阵的规模 ).,则矩阵乘法表示为 C , A , B , (c)B , (b ij k ij m,n ,n2 3 n 之间存在关系( P , n或 P , n),而且单台计算机价格较 与矩阵 B 区别于 BLM,本文采用矩阵 A 的一个元素 aij b w 为昂贵。 的一个行向量 V进行数乘得到临时中间权重向量 V,然 jij [4]w 在大数据时代,随着 MapReduce成为最广泛用于处理 后对 V 执行 j 从 1 到 n 的线性叠加,从而得到矩阵 C 的一 ij c 个行向量 V 。其原理如 数据密集计 算的并行计 算框架,许 多研究者开 始将 i [5-9][10]MapReduce 用于矩阵乘法。其中文献关注多个矩阵乘 图 1 所示: 法,并提出一种将乘法转换为表连接的计算模式。其他文献 a, ? ab? bc? c11 ? a , , ? b , , ? c , 1 j1k 111 j1n 111 j1n [11, 12], , , , , , 重点关注两个矩阵的乘法,但是他们主要是采用块级乘 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? , , , , , ,, , , ? b, , c,法模式(Block-level Multiplication:BLM)(注:本文命名 ? ? b? b, ? c? c aaai1ijin i1ijin i1 ij ik , , , , , , ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? , , , , , ,, , , , , ,的 BLM 与传统的分块矩阵乘法不是同一个概念),即用左矩 a a a b b b c c c ??????mn m1 mj mk k1 kj kn m1 mj , , , , , , 阵 A 的一个行向量乘以右矩阵 B 的一个列向量得到目标矩 阵 C 的一个元素。对于这种模式,在采用 MapReduce 计算 , , , , , , , , a, bbbci1 12 j 2 k 2 i 2 ? b, a, ? b,? , a, ? b, c ? c 1n ij jn ik kn i1inb框架计算时,存在两点不足,第一点当矩阵规模变大时,计 11 bb j1k1图 1 VLC 计算模式原理示意图 算性能急剧下降,所耗费的计算时间急剧上升。其次,如果
本文称这种计算模式为 VLC(Vector Linear Combination) A 为稀疏矩阵,采用 BLM 模式会导致大量无意义乘法运算。 模式。 在 MapReduce 计算框架中,每个 MapReduce 计算任务 则在 VLC 模式中,矩阵 C 的计算过程表述如下: 过程被分为两个阶段:Map 阶段和 Reduce 阶段,每个阶段 w 设 V 为临时中间权重向量,则公式(1): ij 都是用键值对(key/value)作为 输入(Input)和输出(Output)。 其中 Map 阶段输出的键值对经过分区、排序和融合后作为 w b V(1) ij , aV ijjReduce 阶段的输入。当采用 BLM 模式在 MapReduce 框架
中实现矩阵乘法时,为得到矩阵 C 的一个元素,Map 阶段 则矩阵C的一个行向量 表示为公式(2): c为矩阵 A 和矩阵 B 的每个元素都产生一个键值对,然后在 V i k w c Reduce 阶段先组合成一个行向量和一个列向量,再执行两 V , (2) V i ij , j ,1 个向量乘法计算,从而得到矩阵 C 的一个元素。这种模式的
设计过程使得 Map 阶段产生太多的键值对,并存入 Hadoop 最终得到矩阵 C 公式(3): [4]分布式文件系统 HDFS中,由于 Reduce 阶段需要从 HDFS
—————————————— 基金资助:广东省科技计划项目(2012B040500040);广东省科技计划高新技术产业化项目(2012B010100048);广州市海珠区科技计划项目 (2014-cg-31) 作者简介:郑建华(1977-),男,汉族,湖南嘉禾,仲恺农业工程学院,讲师,博士,研究方向:系统架构设计,云计算,大数据处理与挖掘,广 州,510225 沈玉利(1955-),男,汉族,山东费县,仲恺农业工程学院,教授,博士,研究方向:模式识别与智能处理,大数据处理与挖掘,广州 ,510225 朱蓉(1976.9-),女, 汉族,江西吉安,仲恺农业工程学院,讲师,硕士,研究方向:系统架构设计,云计算,大数据处理与挖掘,广 州,510225
Microcomputer Applications Vol. 31, No.7, 2015 研究与设计 微型电脑应用 2015 年第 31 卷第 7 期
而 Reduce 函数接受 MapReduce 库分过组的(key,value[]),然 c ,,V 1 , , 后对具有相同键的中间结果集进行规约及相关处理,最后结 ? (3) , , c ,,C , V 果返回给 MapReduce 库。 i , , ? , , 因此在本文中,Reduce 函数将接受矩阵行下标相同的 , c , V , m , c V i 的全部数据。 键值对,这些数据即为计算矩阵 C 行向量 用 MapReduce 框架实现基于 VLC 的矩阵乘法时,Map
L # R # Reduce 函数将根据将复合数据中的“ ”和“ ”区分 函数主要负责矩阵 A 和矩阵 B 数据预处理工作,即将矩阵
j , p A 拆分成单个元素,而矩阵 B 拆分成 k 个行向量,这种拆分 矩阵 A 和 B,并对满足条件 复合数据中值进行数乘操 ba ,V 方式将减少临时中间输出键值对。而 Reduce 函数主要通过 ij j ,这个数乘结果即为中间权重向量,最后对同 作,即 数乘到中间权重向量,并对中间权重向量进行线性组合叠加
一个结点的 Reduce 函数的所有中间权重向量进行向量线性 得到矩阵 C,当矩阵 A 为稀疏矩阵的时候,即如果 a为零, ip c w V也是一个零向量,不需要进行乘法计算,从而节省了 i则 V ij组合叠加即得到矩阵 C 的行向量 ,这也是 Reduce 函数的 计算时间,因此 VLC 模式也同样适合稀疏矩阵的乘法,故 输出。 采用 VLC 模式可以有效的避免 BLM 模式中两大不足。 基于以上分析 Map 函数实现过程伪代码描述如下: 2 MapReduce 框架下基于 VLC 模式的算法设计 Algorithm of Map Function: a b VVii:矩阵 b 的行向量; Input: :矩阵 a 的行向量; 根据 MapReduce 计算框架要求,编写基于 MapReduce
Output:输出两种类型键-值序列对: ?1 左矩阵输出 计算框架的算法关键是要实现 Map 阶段函数和 Reduce 阶段 , i,[L # j : a] , aij ij 函数,为此本小节主要阐述这两个函数的实现过程。 ,其中键 为 i ,是元素 的 行号,值为 b 本研究中将采用一个 MapReduce 工作任务(Job)完成 [L # j : a] , p,[R # i :V] , p ,[1, m] ij i ;?2 右矩阵输出: ,其中键整个基于 VLC 的矩阵并行乘法计算,Map 函数负责接收矩 b
[R # i :V] 阵输入,并根据 VLC 模式要求产生相应的中间输出 i 为p,值为 Procedure: Begin 间 1: IF 输入矩阵是左矩阵 叠加,最后输出结果矩阵 C。Map 和 Reduce 函数的输入输 a2: FOR each ain VDO BEGIN ij i出如 3: IF a!=0 ij所示: 4: 输出键值序列对: 表 1 Map 和 Reduce 函数的输入输出 ij 5: ELSE 输入/输出 6: 不输出任何键值对 输入 输出 对每一个 a输出: 7: END IF ij , i,[L # j : a] , 8: END FOR ij a b b 9: ELSE IF 输入矩阵是右矩阵 Map 函数 , i,V , , , i,V , 对每一个 V 产生 m i i i 个输出: 10: FOR p=1 to m DO BEGIN b b , p,[R # i :V] , 11: 输出键值对序列对: i , i,[R # p :V ] ,i ,[1, m] p b , i,{[L # j : a ],[R # p :V ]} , 12: END FOR ij p c Reduce 函数 , i,V , i j ,[1, k] p ,[1, k] 13: END IF a , i,V, iEnd 对于 Map 函数,其所接受的输入格式为 ,其中 a Vi i类似的 Reduce 函数实现过程伪代码描述如下: 表示行标号, 表示行向量。Map 函数主要对输入数据 Algorithm of Reduce Function: aij 进行拆分处理,对矩阵 A,每个元素 对应输出一个格式 Input:每个 node 得到输入数据是具有相同键值的一系 , i,[L # j : a] , ij i b 为 的键值对,其中键值对的 key 为 ,vaule , i,{[L # j : a],[R # p :V]} , j ,[1, k] p ,[1, k] ij p 列键值序列对: j c c L # , V为一个复合结构,“ ”表示这是一个左矩阵, 表示元素 i, i,V Output:输出为键值序列对 i表示矩阵 ,其中 aij m * k C 的第 i 行向量 的列标,因此对于矩阵 A 而言,将总共产生 个键值 Procedure: 对。矩阵 B 的输出则与矩阵 A 不同,将针对矩阵 B 的每一 b Begin , i,[R # p :V] , p m Array _ A[ k, 1] , 0 行向量产生 个输出键值对 ,其中键值对的 1: p R # value 部分为复合格式,“ ”表示这是一个右矩阵, 表 Array _ C[n , 1] , 0 2: p i 示这是第 个行向量,而键值对的 key 值 表示与矩阵 A 相 Array _ B[k , 1][n , 1] , 0 b 3: m * k 对应的行号。因此对应矩阵 B 而言,将总共产生 个键 {[L # j : a],[R # p :V]} DO BEGIN ij p 4: FOR 输入列表 矩阵类型标识符为 ' L ' 5: IF 值对。 [L # j : a] ij 在 MapReduce 框架中,MapReduce 框架会收集 Map 函 6://处理 Array _ A[ j] , a 数抛出的结果,并且把具有相同的键的键值对分组、排序, ij 7: ?6? 示:矩阵类型标示符为R ' 8: ELSE IF b VLCA BLMA [R # p :V] p 250,000,000 9:// 处理 10: FOR j=1 to n DO BEGIN 200,000,000 Array _ B [p][ j] , b pj 11: 150,000,000 P 12: END FOR 100,000,000 Computation time (ms) Computation time (ms) 13: END IF 50,000,000 14:END FOR 0 15: FOR i=1 to k DO BEGIN 0 200 400 600 N:Order of Square Matrix Array _ A[i]! , 0 17: IF 图 2 理论性能比较曲线 18: FOR j=1 to n DO BEGIN n 图中显示当 逐渐增加的时候,两种算法的差距越来越 19: 大,表明了 VLCA 算法的优越性。 Array _ C[i] , Array _ C[i] , Array _ A[i] , Array _ B[ p][ j] 3.2 实验结果 20: END FOR 不同的矩阵存储格式会产生不同的预处理开销,为了得 21: END IF 到准确的实验比较结果,本次实验中对两种算法采用相同的 22:END FOR 输入格式,如图 3 所示: c Vi23: //output the 1 a, ,, a, , , a Array _ C[n , 1] 11 1 j 1m24: OUTPUT 2 a, ,, a, , , a 21 2 j 2m End row ID row vector 3 算法分析 图 3 矩阵格式 实验中采用随机的方3.1 理论分析 式生成不同大小的矩阵。 本次实验采用 3 台计算机构乘法算法是否优越性的一个重要 计算时间是衡量矩阵成的 Hadoop 集群,每台机 指标,特别是随着矩阵的增大,一般计算时间会快速地增加。 .0.4。 CPU 为 2.13GHz,操作系统采用 Ubuntu,Hadoop 版本为 1对 MapReduce 计算框架而言,时间开销包括 I/O 耗时和 CPU 为了获取最原始的计算性能数据,本集群并未做任何的配置 耗时,其中 I/O 开销包括从 HDFS 和本地硬盘读/写时间,而 优化。 CPU 开销包括执行 Mapper/Reducer/Combiner 的时间和进 不同类型矩阵的 VLCA 计算时间如图 4 所示: [13]行中间数据的分区、排序和融合所耗费的时间。故减少中 VLCA(sparse) 1,400,000 VLCA(dense) 间 2 22 3中间 基于以上分析,我们得到的理论性能对比曲线如图 2 所 (下转第 11 页) 工作站端展示的防伪信息宣传图,如图 8 所示: 银行反假货币工作、改革货币宣传的信息化都具有积极意义。 参考文献 [1] 邓少洲.反假人民币工作中的障碍与解决的对策[J].江西 社会科学,1994,06. [2] 魏剑.遏止伪币浊流,维护人民币的正常流通秩序[J].经 济教育研究,1995,09. [3] 毕赟.触摸式公共查询设施界面的用户交互模型分析方 法[D].杭州:浙江工业大学,2011.10. [4] 吴瑜.人机交互设计界面问题研究[D].武汉:武汉理工大 学,2004,5. [5] 彭泉,崔德光,李晓强.基于人类认知规律的应用系统人 图 8 工作站端防伪信息展示图 机界面设计[J].计算机工程与应用,2001,10. [6] 马继刚.第五套人民币防伪特征的研究[J].中国防伪,200 3 总结 4,02. [7] 王翠萍,胡石,宋佳.思维导图在阅读活动中的应用探析 本文在分析现有工作站在反假币宣传工作中发挥的优 [J].图书馆学研究,2011,07. 点及存在的缺点的基础上,提出一种新的反假币宣传系统的 [8] 王鹏,崔静.新一代界面技术 WPF 的架构及应用[J].成都 纺织高等专科学校学报,2011,01. 设计方案并实现该系统。系统将计算机技术、网络技术,以 (收稿日期:2015.01.04) 及数据库技术等有机结合起来,基于触摸式人机交互设计原 则,很好地实现了货币防伪信息的管理与宣传;它对于加强 高。在后续的研究中将进一步优化算法,以提升对稀疏矩阵 的(上接第 12 页) 算法性能。 VLCA(dense) 180,000 BLMA(dense) 160,000 参考文献 140,000 120,000 [1] 雷澜. 矩阵乘法的并行计算及可扩展性分析 [J]. 重庆 100,000 2004, 21(02): 121-123. 工商大学学报(自然科学版), 80,000 [2] Cannon L E. A cellular computer implement the Kalman 60,000 filter algorithm [D]. Bozeman US: Montana State 40,000 Computation time (ms) University, 1969. 20,000 [3] Fox G C, Otto S W, HEY A J G. Matrix algorithm on a 0 0 50 100 150 200 hypercube I:matrix multiplication [J]. Parallel computing, N:Order of Square Matrix 1987, 4(1): 17-31. [4] Dean J, Ghemawat S. MapReduce: a flexible data 图 6 两种算法的计算时间比较( n <=200) processing="" tool="" [j].="" communications="" of="" the="" acm,="" 2010,="" n="" 53(1):="" 72-77.="" 图="" 6="" 中清晰表明两种算法的执行时间差距随着="" 的增="" [5]="" huang="" b,="" wu="" y.="" matrix="" multiplication="" in="" mapreduce="" n="" 加而增加,vlca="" 算法显示了较为优越的性能。而当="" 小于="" [eb/ol].https://www.cs.duke.edu/courses/cps216/current/="" 50,二者的执行时间基本相等,这是因为此时的计算量不饱="" project/project/projects/matrix_multiply/proj_report.pdf,2="" 013,02.和,整个任务的执行时间主要是启动="" mapreduce="" 工作任务="" [6]="" norstad="" john.="" a="" mapreduce="" algorithm="" for="" matrix="" 的时间。="" multiplication="" [eb/ol].http://www.norstad.org/matrix-="" 3.3="" 分析结果="" multiply/,2013,02.="" [7]="" rajaraman="" a,="" ullman="" j="" d.="" mining="" of="" massive="" datasets="" [m].="" 通过对比理论分析和实验结果,可以得到="" 3="" 个结论:="" cambridge:="" cambridge="" university="" press,="" 2011.="" 1)当矩阵比较小时,blma="" 与="" vlca="" 性能相当,而当="" [8]="" seo="" s,="" yoon="" e="" j,="" kim="" j,="" et="" al.="" hama:="" an="" efficient="" matrix="" 矩阵比较大时,vlca="" 显示出较优越的性能。="" computation="" with="" the="" mapreduce="" framework[c]//="" n="" proceedings="" of="" the="" 2010="" ieee="" second="" international="" 2)对比图="" 2="" 和图="" 5="" 发现,当="" 为="" 500,实验结果的时="" conference="" on="" cloud="" computing="" technology="" and="" 间耗比倍数(vlca="" 算法时间/blma="" 算法时间)比理论分="" science.washington:ieee="" computer="" society,="" ,="" 析的时间耗比倍数要小,这说明="" 不应该是="" 0.5,应该是更="" 2010:721-726;="" [9]="" zhang="" j.="" implementation="" for="" large="" scale="" matrix="" 大,可达="" 0.9。说明基于="" mapreduce="" 框架的并行算法中="" map="" multiplication="" on="" mapreduce="" parallel="" framework="" [j].="" 函数输出的中间键值多少是影响算法性能的最重要="" z="" 因素。="" computer="" applications="" and="" software,="" 2012,="" 29(6):267-71.="" 3)vlca="" 用于稀疏矩阵并没有体现较大的性能优势,="" [10]="" j.="" myung,s.="" g.="" lee.matrix="" chain="" multiplication="" via="" multi-way="" join="" algorithms="" in="" mapreduce="" [c]//proceedings="" 这进一步证明了第二个结论的正确性,即="" mapreduce="" 框架="" of="" the="" 6th="" international="" conference="" on="" ubiquitous="" 处理中间键值对的时间要远比执行乘法运算耗费的时间多。="" information="" and="" communication.="" 2012:53-58.="" [11]="" zeng="" d="" j.="" large="" matrix="" multiplication="" processing="" program="" 4="" 总结="" design="" of="" cloud="" platform="" [j].="" science="" mosaic,="" 2012,="" 24(5):="" 42-45.="" 面对越来越大规模的数据集,传统的矩阵并行算法并不="" [12]="" z.="" g.="" sun,="" t.="" li,n.="" rishe.="" large-scale="" matrix="" factorization="" using="" mapreduce[c]//proceedings="" of="" the="" ieee="" 适用,而="" mapreduce="" 框架显示出了较好性能优势。当传统="" international="" conference="" on="" data="" mining="" workshops.="" 的基于="" mapreduce="" 的="" blma="" 矩阵乘法由于产生的中间键值="" washington:ieee="" computer="" society,="" 2010:1242-1248="" 对过多导致算法性能较低,为此本文提出了基于向量线性组="" [13]="" dawei="" jiang,="" beng="" chin,="" ooi="" lei,="" et="" al.the="" performance="" of="" mapreduce:="" an="" in-depth="" study[j].proceedings="" of="" the="" 合叠加的方式实现="" mapreduce="" 框架下矩阵乘法,该方法极="" vldb="" endowment="" 2010,3(1):472-483.="" 大地减少了中间数据的产生,实验结果表明算法性能得到提="">=200)> 第三章 向量的线性相关性与矩阵的秩 3.1 设 α1=(111)T , α2=(1?10)T , α3=(01?1)T 。 2α1?2α2+3α3。 (1) 计算 ?α1+2α2; (2) 求满足方程的向量ξ: (ξ?α1) ?3(α2+ξ) =3α3+2ξ 。 (3) 计算 α1T α2; T T T T T α1α2; a 2a 3a 1; a 2a 3a 1. 3.2 设n 阶矩阵 A = (α1 α2 T ?1??T ??2? L αn )=??,α1, L , αn 和1T , L , L n T 分别称作 ?M ??T ??n ? 矩阵A 的列向量组和行向量组,见(2.13)和(2.14)。利用 A I =I A =A ,证明: A εi =αi ; 其中 εi T A =αi T , i =1, L , n , εi 是单位向量组。 αi 的线性组合。 3.3 把向量β表示成向量组 (1) (2) β=(1?10)T , α1=(110)T , α2=(101)T , α3=(011)T ; β=(1211)T , α1=(1111)T , α2=(11?1?1)T , α3=(1?11?1)T , α4=(1?1?11)T ; (3) β=(0001)T , α1=(1101)T , α2=(2131)T , α3=(1100)T , α4=(01?1?1)T 。 3.4 判别下列向量组是否线性相关。 (1) (2) (3) (4) α1=(123)T , α2=(?2?4?6)T ; α1=(111)T , α2=(025)T , α3=(126)T ; α1=(1?124)T , α2=(0310)T , α3=(3074)T ; α1=(4?526)T , α2=(2?213)T , α3=(6?339)T , α4=(4?156)T 。 3.5 求数k , l ,使得 (1) (2) (3) α1=(451)T , α2=(302)T , α3=(k 109)T 线性相关; α1=(2111)T , α2=(3?210)T , α3=(k ?120)T 线性无关; α1=(123)T , α2=(k 00)T , α3=(0l 1)T 线性无关。 3.6 设 ?2??0??1??????? k 1?1?+k 2?1?+k 3??1?=θ, ?3??2??4??????? 证明 k 1=k 2=k 3=0。 3.7 下列命题是否正确?若正确,证明之;若不正确,举反例。 (1) 向量组α1, α2, L , αm (m ≥2) 线性无关的充分必要条件是任意两个向量线性无关。 (2) 向量组α1, α2, L , αm (m ≥2) 线性相关的充分必要条件是有某m ?1个向量线性相关。 (3) 若向量组α1, α2, L , αm (m ≥2) 线性相关,则α1可由α2, L , αm 线性表示。 (4) 若有不全为零的数k 1, k 2, L , k m ,使得 k 1α1+L +k m αm +k 1β1+L +k m βm =θ, 则α1, L , αm 线性相关,β1, L , βm 也线性相关。 (5) 若向量组α1, α2线性相关,β1, β2线性相关,则α1+β1, α2+β2线性相关。 (6) 若向量组α1, α2, α3线性无关,则 3.8 证明n 维向量组 α1, α1?α2, α1?α2?α3线性无关。 η1=(10L 0)T , η2=(11L 0)T , L , ηn =(11L 1)T 线性无关。 3.9 证明:对任意向量α1, α2, α3,向量组 α1+α2, α2+α3, α3+α13 线性相关。 3.10 设向量组α1, α2, α3, α4线性相关,但其中任何三个向量都线性无关。证明必存在一 组全不为零的数 k 1, k 2, k 3, k 4,使得 k 1α1+k 2α2+k 3α3+k 4α4=θ, 3.11 设 ?1??1??1??1+k ? ???????? α1=?1?, α2=?1+k ?, α3=?1?, β=?k ?, ?k 2??1+k ??1??1? ???????? 试问k 取何值时, β可由α1, α2, α3线性表示。 3.12 设向量组α1, α2, L , αm 线性无关,且β1, β2均可由α1, α2, L , αm 线性表示。证明 α1, α2, L , αm k β1+β2线性无关,其中 k 是任意常数。 3.13 设向量组α1, α2, α3线性相关,α2, α3, α4线性无关。问 (1) (2) α1能否由α2, α3线性表示?证明你的结论。 α4能否由α1, α2, α3线性表示?证明你的结论。 3.14 求下列向量组的秩及其一个极大线性无关组。 (1) (2) α1=(110)T , α2=(020)T , α3=(003)T ; α1=(1?124)T , α2=(0312)T , α3=(30714)T , α4=(2156)T 。 3.15 证明一个向量组的任何一个线性无关组都可以扩充成一个极大线性无关组。 3.16 设向量组 α1=(1?124)T , α2=(0312)T , α3=(30714)T , α4=(1?120)T 。 (1) 证明α1, α2线性无关; (2) 把α1, α2扩充成一个极大线性无关组。 3.17 已知向量组 A :α1, α2, L , αm 的秩为 r , 证明向量组A 中任意r 个线性无关的向 量组都构成了一个极大线性无关组。 3.18 设α1, α2, L , αm 是一组n 维向量,已知单位向量组ε1, ε2, L , εm 可由其线性表示。 证明α1, α2, L , αm 线性无关。 3.19 设α1, α2, L , αm 是一组n 维向量。证明α1, α2, L , αm 线性无关的充分必要条件是任 一n 维向量都可被其线性表示。 3.20 已知向量组A 与向量组B 有相同的秩,且向量组A 可由向量组B 线性表示。证明向 量组A 与B 等价。 3.21 设向量组α1, α2, L , αs ;β1, β2, L , βt 和α1, L , αs , β1, L , βt 的秩分别为 r 1, r 2, r 3 。证明 max (r 1, r 2) ≤r 3≤r 1+r 2 3.22 求下列矩阵的秩: ?11?1??20314? ???? (1) ?2?10?; (2)?3?5427?; ?101??15201????? ?1?1? ?2?2 (3)? 30? ?03? 21426?100 0??0?; 1??1?? ?a 1? ???a 2? (4) C =??(b 1, b 2, L , b n ), M ???a ??m ? 其中a i (i =1, 2, L , m ) 不全为零,b j (j =1, 2, L , n ) 不全为零。 3.23 设A =(a ij ) n ×n 为实系数矩阵,已知a ii >0, (i =1, 2, L , n ), a ij <0, (i="" ,="" j="1," 2,="" l="" ,="" n="" ,="" i="" ≠j="" )="" ,且∑a="" ij="0," (i="1," 2,="" l="" ,="" n="" )="" ,求a="">0,> j =1 n 3.24 求(α1, α2, α3, α4, α5) 的秩,其中: (1)α1=(1, ?1, 2, 4) , α2=(0, 3, 1, 2) , α3=(3, 0, 7, 14) , α4=(1, ?2, 2, 0) , T T T T α5=(2, 1, 5, 10) T ; (2)α1=(1, 0, 1, 0, 1) , α2=(0, 1, ?1, 1, 0) , α3=(?1, 0, 0, ?1, 0) , α4=(0, ?1, 0, 0, ?1) , α5=(1, 0, 1, 1, 1) . T T T T T ?k ??1 3.25 (1)设矩阵A =? 1??1? 1k 1111k 1 1??1? ,且r (A ) =3,求常数k 的值; 1??k ?? ?1a a L a ? ?? L a a a 1?? (2)设n 阶矩阵A =?a a 1L a ?,且r (A ) =n ?1,求常数a 的值。 ?? ?L L L L L ??a a a L 1? ?? 3.26 试用矩阵的初等变换的方法判断下列向量组的线性相关性: (1)α1=(1, ?2, 3) , α2=(0, 2, ?5) , α3=(?1, 0, 2) ; (2)α1=(2, 1, ?1, ?1) , α2=(0, 3, ?2, 0) , α3=(2, 4, ?3, ?1) ; (3)α1=(2, 4, 1, 1, 0) , α2=(1, ?2, 0, 1, 1) , α3=(1, 3, 1, 0, 1) . 3.27 设向量组α1=(1, 1, 1, 3) , α2=(?1, ?3, 5, 1) , α3=(3, 2, ?1, p +2) , T T T T T T T T T T T T α4=(?2, ?6, 10, p ) T , (1)p 为何值时,该向量组线性无关?并在此时将向量α=(4, 1, 6, 10) 用 T α1, α2, α3, α4线性表示; (2)p 为何值时,该向量组线性相关?并在此时求出它的秩和一个极大线性无关组。 ?n ? 3.28 设n 阶矩阵A 的伴随矩阵为A *,证明r (A *)=?1 ?0? 3.29 证明矩阵添加一列(或一行),则其秩或不变;或增加1。 3.30 设A 是n 阶矩阵,证明: (1) 如果A =A ,则r (A ) +r (A ?I ) =n ; (2) 如果A =I ,则r (A +I ) +r (A ?I ) =n . 22 r (A ) =n r (A ) =n ?1. r (A ) 3.31 设A 为秩是r 的m ×n 矩阵,证明: (1)存在m 阶可逆矩阵P ,使P A的后m ?r 行全为0; (2)存在n 阶可逆矩阵Q ,使A Q的后n ?r 行全为0。 ?A O ? 3.32 证明 r ??O B ??=r (A ) +r (B ) . ?? 3.33 设A =(a ij ) m ×n , B =(b ij ) k ×n , 证明max{r (A ), r (B )}≤r ??B ??≤r (A ) +r (B ) . ??3.34 设A =(a ij ) s ×n , B =(b ij ) n ×m , 证明r (AB ) ≥r (A ) +r (B ) ?n . ?A ? 实验3 矩阵的秩与向量组的线性相关性 一、实验目的 学会使用Matlab 软件构作已知矩阵对应的行(列)向量组、求矩阵的秩,对矩阵进行初等行变换,求向量组的的秩与极大线性无关组,且将其余向量用极大线性无关向量组表示。 二、实验原理 (一)预备知识 ? 线性代数中的矩阵及其初等变换、向量组的线性相关性等知识; ? 本实验所用Matlab 命令提示: 1. 构作已知矩阵对应的行(列)向量组 (1)选择A 的第 i 行作一个行向量:ai=A( i , : ); (2)选择A 的第 j 列作一个列向量:aj=A( : , j ); 2. 矩阵的初等变换 (1)让A 的第 i 行与第 j 行互换可用赋值语句:A( [i , j ], : )= A( [j , i ], : ); (2)让k 乘A 的第 i 行可用赋值语句:A( i , : ) =k*A( i , : ); (3)A 的第 i 行加上第 j 行的k 倍可用赋值语句:A( i , : ) =A( i , : ) +k *A(j , : ) ; 3. 求矩阵的秩 用命令rank(A)可以求出矩阵A 的秩; 命令rref(A)把矩阵A 化作行阶梯型最简形,可以求出矩阵的秩. 4. 向量组的极大线性无关向量组 以给定的向量组为列, 做一个矩阵A , 用命令rref(A)将A 化成行阶梯型最简形式,其中单位向量对应的列向量即为最大线性无关组所含向量,其它列向量的坐标即为其对应向量用最大线性无关组线性表示的系数. (二) 实验举例 ?1 7 例1 设A = 0 ?2 0151 21411 174-10 0??1 ?,求A 的秩. 6??-2? 输入: A=[1,0,2,1,0;7,1,14,7,1;0,5,1,4,6;2,1,1,-10,-2]; rankA 输出为: ans= 3 或输入: A=[1,0,2,1,0;7,1,14,7,1;0,5,1,4,6;2,1,1,-10,-2]; rref(A) 输出: ans= 1.0000 0 3.0000 2.0000 0 1.0000 0 0 0 0 1.0000 0 0 0 0 0 因此A 的秩为3. 注: 矩阵的秩等于它的行向量组的秩,也等于它的列向量组的秩,因此,可以用rref 求向量组的秩. 例2 求向量α1=(1,2, -1,1), α2=(0,-4, 5, -2), α3=(2,0, 3, 0) 的秩. 输入: A=[1,2,-1,1;0,-4,5,-2;2,0,3,0]; rref(A) 输出为: ans= 1.0000 0 1.5000 0 0 1.0000 -1.2500 0.5000 0 0 0 0 矩阵的秩为2, 所以它的行向量组的秩也是2. 例3 向量组α1=(1,1,2, 3), α2=(1,-1,1,1), α3=(1,3, 4, 5), α4=(3,1,5, 7) 是否线 性相关? 注: 向量组线性相关的充要条件是:它的秩等于其中向量的个数. 输入: A=[1,1,2,3;1,-1,1,1;1,3,4,5;3,1,5,7]; rref(A) ans= 1 0 0 2 0 1 0 1 0 0 1 0 0 0 0 0 向量组的秩等于3, 而它含有4个向量, 所以该向量组线性相关. 例4 求向量α1=(1,-2, -2, 3), α2=(-2, 4, -1, 3), α3=(-1, 2, 0, 3), α4=(0,6, 2, 3), α5=(1,-6, 3, 4) 的一个最大无关组, 并将其余向量用极大无关组线性表示. . 输入: A=[1,-2,-1,0,2;-2,4,2,6,-6;2,-1,0,2,3;3,3,3,3,4]; B=rref(a) 输出: B = 1 0 1/3 0 16/3 0 1 2/3 0 -1/9 0 0 0 1 -1/3 0 0 9 0 0 因此, α1, α2 , α4 是列向量组的一个最大无关组. 且有 α3 = 13 α1 + 23 α2 , α5 =2-12 163 α1- 19 α2- 13 α3 . 4?? 3, 验证α1, α2, α3是?2?? ?2 例5 设A =[α1, α2, α3]= 2 -1? 3 -1?? 2, B =[β1, β2]=?2???1 0 -4? R 的一个基,并把β1, β2 用这个基线性表示. 输入: a=[2,2,-1;2,-1,2;-1,2,2]; b=[1,4;0,3;-4,2]; c=rref([a,b]) 输出为: c= 1 0 0 2/3 4/3 0 1 0 -2/3 1 0 0 1 -1 2/3 可见α1, α2, α3的秩为3,因此α1, α2, α3线性无关,α1, α2, α3是R 3的一个基,而且 β1= 23 α1- 23 α2-α3,β2= 43 α1+α2+ 23 α3. 三、实验任务 ?1 0 1. 设A = 1 ?0 -2137 3-103 -4??1 ?, -3??1? (1) 做出A 的行向量组:a1 、a2 、a3 、a4 、a5 、a6; (2) 做出B 的列向量组:b1 、b 2 、b3 、b 4 、b5 、b6; (3) 完成以下初等变换:将A 的第一、三行互换,再将其第3列乘以6,再将其第1行的10倍加至第5行 ; (4) 求A 的列向量组的一个极大线性无关向量组,并将其它列向量用极大线性无关向量组线性表示; (5) 求矩阵A 的秩. 线性独立与矩阵的秩 对一组给定的向量,线性独立是一个重要的性质。如果不存在一组标量a1,a2,???,an(它们不构成零向量),使得 aX,0 则向量x1,x2,???,xn线性独立。 确定一组向量是否线性独立的方法之一是试图从这组向量构成一组正交向量。如果从已知向量构成向量的范数是零或接近零(例如对计算机计算为10^-6),则对应的向量线性相关。换句话说,该向量可由线性独立向量的线性组合而构成。在复杂的化学反应系统中确定独立反应及在一次分析中估算独立无因次数群时,线性独立特性是非常有用的。 Gram-Schmidt正交技术 Gram-Schmidt正交技术是一种根据一组已知向量构造一组正交向量的方法。该方法有助于确定已知向量中的线性独立向量的数目。 设有m个向量(每个向量含n个元素),x1,x2,???,xn。定义向量 yx, 11 ,,yx,12yxy,,等等。 ,,221yy,,,11 通式为 j,1,,yyii(1,2,,)yxxim (A.5) ,,,,,,,,,iii,,yyi,1ii,, 向量相互正交,而与正交。(正交的含义,)量yyxxx,,,,,,yyy,,,,,,j121j,12n 称为向量的Euclidean范数,定义为 y n21/2 (A.6) yy,(),i,1i 在计算过程中,如果任一向量y的Euclidean范数值是零或接近于零,则在后面的计算中该向量出现的项就消失了。 矩阵的秩 一组向量中线性独立向量的数目称为由已知向量构成的矩阵的秩。换言之,矩阵的秩定义为矩阵中包含的最大非零行列式的阶数。在一个方阵中,如果矩阵等于矩阵的阶数,则该矩阵是非奇异矩阵。如果rA和rB是两个矩阵A和B的秩,C是A和B的乘积,则C的秩小于或等于A和B的秩的较小值。换言之 rrr,min(,) CAB 左乘或右乘一个非奇异方阵不改变矩阵的秩。 在因次分析中,矩阵的秩非常重要。因为无因次乘积的数目等于总变量数减去它们的因次矩阵的秩。第六章讨论了线性独立性在化学反应系统这的应用。在程序P,6.1中列出了用Gram,Schmidt正交技术确定矩阵秩的计算机程序。 Gram-Schmidt正交技术应用例 Fortran语言程序,用正交技术确定一个矩阵的秩 C PROGRAM P-6.1 C SUBROUTINE RANK(A,L,M,N,NRANK);函数名称RANK,参变量A,L,M,N和NRANK C THIS SUBPROGRAM DETERMINES(确定)THE RANK OF A MATRIX (该子程序用于确定一个已知矩阵A(M,N)的行秩) C MATRIX IS DEFINED BY A(M,N) ―要输入的已知的矩阵数据 C GRAM-SCHMIDT ORTHOGONALIZATION IS USED ―使用的方法是GRAM-SCHMIDT的正交法, C NRANK - RANK OF ROWS ―NRANK 行的秩, C M - NUMBER OF ROWS ――行数目 C N - NUMBER OF COLUMN S――列数目 C L(J) - FLAG FOR LINER INDEPENDENCE OF COLUMN J J列的线性独立标记向量; C =1 LINEARLY INDEPENDENT (,1,线性独立) C =0 LINEARLY DEPENDENT (,0,非线性独立) DIMENSION A(M,N),L(N),B(20,20) ;定义变量,A(M,N)已知矩阵,给定的矩阵 ;L(N)线性独立性标记向量,秩的数值统计之用 ;B(20,20)备用数组空间 ;计算起点 DO 10 J=1,N ;循环体A,句10止。 10 L(J)=1 ;给秩标记号赋初值1,选列秩 DO 20 K=1,M ;循环体B,句20止。M行 20 B(K,1)=A(K,1) ;将A( )第一列的值传给B()第一列; DO 80 J=2,N ;循环体C,句止于80。J=2,>Norm,句80为 continue; JM1=J-1 DO 30 K=1,M ;循环D,止于30。按行进行拷贝 30 B(K,J)=A(K,J) ;按行进行,单元赋值 DO 60 I=1,JM1 ;循环体E,终点句60 IF (L(I).EQ.0) GO TO 60 ;判断是否需要进行40,50计算 TERM1 =0 ;为循环体F做准备 TERM2 =0 ; DO 40 K=1,M ;循环体F,终40句 TERM1 =TERM1+B(K,I)*A(K,J) j,1j,1,,yyii 中的 ;等于计算yxx,,()yx,,,,iiiii,,yyi,1i,1ii,, 40 TERM2 =TERM2+B(K,I)**2 n21/2;等于中未开根号的部分,范数计算 yy,(),i,1i j,1,,y1iTERM = TERM1/TERM2 ;等于x,,,,i,,yyi,1ii,, DO 50 K=1,M ;按行展开处理,循环G 50 B(K,J)=B(K,J)-TERM*B(K,I) j,1,,yyii;固定列号J,I,等于求解yxx,,,,,iii,,yyi,1ii,, 60 CONTINUE ;循环G的终端语句 ANORM =0 ;赋初值,中间变量 DO 70 K=1,M ;循环H 70 ANORM = ANORM + B(K,J)**2 ; Norm-范数,结果与句40对应? ;逐行计算经过变换的矩阵B()的值,找出不全为零的行的数目 IF (ANORM .LE. 1.E-8) L(J)=0 ;如果该行的加和值足够小的话, 则标记号改写为0,否则,仍然保持为1。 80 CONTINUE ;循环H和循环C的终端语句 NRANK = 0 ;将秩变量归零 DO 90 J=1,N ;检查向量L(J)中等于1的单元个数的数目 90 IF (L(J).EQ.1) NRANK = NRANK +1 ;统计L(J)向量中单元值等于1的项数。如果L(J)单元值 等于1,则行秩数目加上1。最终返回总计数值NRANK。 RETURN END 应用 计算矩阵的秩的一个有用应用是计算线性方程组解的数目。如果系数矩阵的秩等于增广矩阵的秩,则方程组只要有一个解。在这种情况下,它有精确的一个解,如果它的秩等于方程的数目。如果增广矩阵的秩大于系数矩阵的秩,则通解有k个自由参量,这里的 k是在方程的数目和秩的差。否则方程组是不一致的。 在控制论中,矩阵的秩可以用来确定线性系统是否为可控制的,或可观察的。 高斯消元法的其中一种虚拟码: i := 1 j := 1 while (i ? m and j ? n) do Find pivot in column j, starting in row i: maxi := i for k := i+1 to m do if abs(A[k,j]) > abs(A[maxi,j]) then maxi := k end if end for if A[maxi,j] ? 0 then swap rows i and maxi, but do not change the value of i Now A[i,j] will contain the old value of A[maxi,j]. divide each entry in row i by A[i,j] Now A[i,j] will have the value 1. for u := i+1 to m do subtract A[u,j] * row i from row u Now A[u,j] will be 0, since A[u,j] - A[i,j] * A[u,j] = A[u,j] - 1 * A[u,j] = 0. end for i := i + 1 end if j := j + 1 end while 这个算法和之前谈及的有点儿不同,它由绝对值最大的部分开始做起,这样可以改善算法上的稳定性。将经过调换后的第一列作为起点,这算法由左至右地计算。每作出以下两个步骤,才跳到下一列: 1.定出每列的最后一个非0的数,将每行的数字除以该数,使到每行的第一个数成为1; 2.将每行的数字减去第一行的第一个数的某个倍数。 所有步骤完成后,这个矩阵会变成一个行梯阵式,再用代入法就可解决这个方程组。 转载请注明出处范文大全网 » 线性独立与矩阵的秩及求解范文三:向量的线性相关性与矩阵的秩
范文四:矩阵的秩与向量组的线性相关性
范文五:行业资料线性独立与矩阵的秩及求解