论文矩阵运算研究摘要

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

什么叫作矩阵矩阵乘法是线性代数中最常见的运算之一，它在数值计算中有广泛的应用。若A和B是2个nn的矩阵，则它们的乘积C=AB同样是一个nn的矩阵。A和B的乘积矩阵C中的元素C[i,j]定义为:若依此定义来计算A和B的乘积矩阵C，则每计算C的一个元素C[i,j]，需要做n个乘法和n-1次加法。因此，求出矩阵C的n2个元素所需的计算时间为0(n3)。60年代末，Strassen采用了类似于在大整数乘法中用过的分治技术，将计算2个n阶矩阵乘积所需的计算时间改进到O(nlog7)=O(n2.18)。首先，我们还是需要假设n是2的幂。将矩阵A，B和C中每一矩阵都分块成为4个大小相等的子矩阵，每个子矩阵都是n/2n/2的方阵。由此可将方程C=AB重写为:(1)由此可得:C11=A11B11 A12B21(2)C12=A11B12 A12B22(3)C21=A21B11 A22B21(4)C22=A21B12 A22B22(5)如果n=2，则2个2阶方阵的乘积可以直接用(2)-(3)式计算出来，共需8次乘法和4次加法。当子矩阵的阶大于2时，为求2个子矩阵的积，可以继续将子矩阵分块，直到子矩阵的阶降为2。这样，就产生了一个分治降阶的递归算法。依此算法，计算2个n阶方阵的乘积转化为计算8个n/2阶方阵的乘积和4个n/2阶方阵的加法。2个n/2n/2矩阵的加法显然可以在c*n2/4时间内完成，这里c是一个常数。因此，上述分治法的计算时间耗费T(n)应该满足：这个递归方程的解仍然是T(n)=O(n3)。因此，该方法并不比用原始定义直接计算更有效。究其原因，乃是由于式(2)-(5)并没有减少矩阵的乘法次数。而矩阵乘法耗费的时间要比矩阵加减法耗费的时间多得多。要想改进矩阵乘法的计算时间复杂性，必须减少子矩阵乘法运算的次数。按照上述分治法的思想可以看出，要想减少乘法运算次数，关键在于计算2个2阶方阵的乘积时，能否用少于8次的乘法运算。Strassen提出了一种新的算法来计算2个2阶方阵的乘积。他的算法只用了7次乘法运算，但增加了加、减法的运算次数。这7次乘法是:M1=A11(B12-B22)M2=(A11 A12)B22M3=(A21 A22)B11M4=A22(B21-B11)M5=(A11 A22)(B11 B22)M6=(A12-A22)(B21 B22)M7=(A11-A21)(B11 B12)做了这7次乘法后，再做若干次加、减法就可以得到:C11=M5 M4-M2 M6C12=M1 M2C21=M3 M4C22=M5 M1-M3-M7以上计算的正确性很容易验证。例如:C22=M5 M1-M3-M7=(A11 A22)(B11 B22) A11(B12-B22)-(A21 A22)B11-(A11-A21)(B11 B12)=A11B11 A11B22 A22B11 A22B22 A11B12-A11B22-A21B11-A22B11-A11B11-A11B12 A21B11 A21B12=A21B12 A22B22由(2)式便知其正确性。至此，我们可以得到完整的Strassen算法如下：procedureSTRASSEN(n,A,B,C);beginifn=2thenMATRIX-MULTIPLY(A，B，C)elsebegin将矩阵A和B依(1)式分块;STRASSEN(n/2,A11,B12-B22,M1);STRASSEN(n/2,A11 A12,B22,M2);STRASSEN(n/2,A21 A22,B11,M3);STRASSEN(n/2,A22,B21-B11,M4);STRASSEN(n/2,A11 A22,B11 B22,M5);STRASSEN(n/2,A12-A22,B21 B22,M6);STRASSEN(n/2,A11-A21,B11 B12,M7);;end;end;其中MATRIX-MULTIPLY(A，B，C)是按通常的矩阵乘法计算C=AB的子算法。Strassen矩阵乘积分治算法中，用了7次对于n/2阶矩阵乘积的递归调用和18次n/2阶矩阵的加减运算。由此可知，该算法的所需的计算时间T(n)满足如下的递归方程:按照解递归方程的套用公式法，其解为T(n)=O(nlog7)≈O(n2.81)。由此可见，Strassen矩阵乘法的计算时间复杂性比普通矩阵乘法有阶的改进。有人曾列举了计算2个2阶矩阵乘法的36种不同方法。但所有的方法都要做7次乘法。除非能找到一种计算2阶方阵乘积的算法，使乘法的计算次数少于7次，按上述思路才有可能进一步改进矩阵乘积的计算时间的上界。但是Hopcroft和Kerr(197l)已经证明，计算2个22矩阵的乘积，7次乘法是必要的。因此，要想进一步改进矩阵乘法的时间复杂性，就不能再寄希望于计算22矩阵的乘法次数的减少。或许应当研究33或55矩阵的更好算法。在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是O(n2.367)。而目前所知道的矩阵乘法的最好下界仍是它的平凡下界Ω(n2)。因此到目前为止还无法确切知道矩阵乘法的时间复杂性。关于这一研究课题还有许多工作可做。关于应用简单一点的表格，像考试分数求和复杂一点的魔方的解决方法，用矩阵代换方法

找点文献给你自己看看吧，需要就发邮件给我[1]高朝邦,祝宗山.关于矩阵的秩的等价描述[J].成都大学学报（自然科学版）,2006,25(1)从行列式、矩阵的等价、线性方程组、线性空间、线性映射等角度来刻画矩阵的秩,进而用这些命题来证明与矩阵的秩有关的一些命题.[2]费绍金.用矩阵的秩判断空间中平面与平面、直线与直线及直线与平面间的位置关系[J].牡丹江教育学院学报,2007,(6)利用线性方程组解的理论讨论空间中平面与平面、直线与直线及直线与平面间的位置关系,给出用矩阵的秩判定以上关系的方法及结论.[3]严坤妹.一类矩阵的秩[J].福建商业高等专科学校学报,2005,(4)矩阵的秩是矩阵的一个重要不变量,根据两个重要的矩阵的秩的不等式以及分块矩阵的初等变换的性质,本文研究了一类矩阵的秩的特征.[4]戴红霞.关于矩阵的秩的例题教学[J].南京审计学院学报,2005,2(2)本文通过三个典型例题的具体讲解,加深学生对抽象概念"矩阵的秩"的理解和掌握.[5]余航.试论分块矩阵的秩[J].桂林师范高等专科学校学报,2001,15(3)任一矩阵都可求得它的秩,而在矩阵运算中,矩阵的分块是一个很重要的技巧.本文从不同角度,从特殊到一般地探求了分块矩阵的秩.[6]徐兰.利用分块矩阵探讨矩阵的秩的有关定理[J].昌吉学院学报,2003,(4)矩阵是线性代数的主要研究对象之一,利用分块矩阵,研究高阶矩阵的秩及矩阵在运算后秩的变化,得到有关的定理.[7]邹晓光.互素多项式矩阵的秩的一个简单结论及其应用[J].金华职业技术学院学报,2006,6(1)本文给出了互素多项式在矩阵的秩讨论中的一个简单结果:定理:设f(x),g(x)∈P[x],A是n阶方阵,若(f(x),g(x))=1,则n+r[f(A)g(A)]=r(f(A))+r(g(A)).以及结果的一些简单应用,对文献[1]中的一些结论进一步讨论.[8]张丽梅,乔立山,李莹.可逆坡矩阵与坡矩阵的秩[J].山东大学学报（理学版）,2007,42(9)坡是两个元素的乘积小于等于每个因子的加法幂等半环.讨论了可逆坡矩阵的若干性质,证明了可逆坡矩阵必是满秩的.讨论了坡矩阵的行秩、列秩与Schein秩.给出了坡矩阵的Schein秩的一个重要性质.

1、运算规则设矩阵

简言之，两个矩阵相加减，即它们相同位置的元素相加减！

注意：只有对于两个行数、列数分别相等的矩阵（即同型矩阵），加

减法运算才有意义，即加减运算是可行的

矩阵之间相乘，必须满足B矩阵列数等于A矩阵行数才能运算，矩阵与矩阵之间的计算可以拆分为矩阵与多个向量的计算再将结果组合，返回的结果为一个列数等于B矩阵、行数等于A矩阵的矩阵。

矩阵加减必须满足矩阵之间纬度相同，返回的结果也会是一个相同纬度的矩阵。