什么是矩阵,研究它有什么意义,它在生活用有什么应用
什么叫作矩阵nbsp;矩阵乘法是线性代数中最常见的运算之一,它在数值计算中有广泛的应用。若A和B是2个nn的矩阵,则它们的乘积C=AB同样是一个nn的矩阵。A和B的乘积矩阵C中的元素C[i,j]定义为:nbsp;若依此定义来计算A和B的乘积矩阵C,则每计算C的一个元素C[i,j],需要做n个乘法和n-1次加法。 因此,求出矩阵C的n2个元素所需的计算时间为0(n3)。nbsp;60年代末,Strassen采用了类似于在大整数乘法中用过的分治技术,将计算2个n阶矩阵乘积所需的计算时间改进到O(nlog7)=O(n2。 18)。nbsp;首先,我们还是需要假设n是2的幂。将矩阵A,B和C中...全部
什么叫作矩阵nbsp;矩阵乘法是线性代数中最常见的运算之一,它在数值计算中有广泛的应用。若A和B是2个nn的矩阵,则它们的乘积C=AB同样是一个nn的矩阵。A和B的乘积矩阵C中的元素C[i,j]定义为:nbsp;若依此定义来计算A和B的乘积矩阵C,则每计算C的一个元素C[i,j],需要做n个乘法和n-1次加法。
因此,求出矩阵C的n2个元素所需的计算时间为0(n3)。nbsp;60年代末,Strassen采用了类似于在大整数乘法中用过的分治技术,将计算2个n阶矩阵乘积所需的计算时间改进到O(nlog7)=O(n2。
18)。nbsp;首先,我们还是需要假设n是2的幂。将矩阵A,B和C中每一矩阵都分块成为4个大小相等的子矩阵,每个子矩阵都是n/2n/2的方阵。由此可将方程C=AB重写为:nbsp;(1)nbsp;由此可得:nbsp;C11=A11B11nbsp;A12B21(2)nbsp;C12=A11B12nbsp;A12B22(3)nbsp;C21=A21B11nbsp;A22B21(4)nbsp;C22=A21B12nbsp;A22B22(5)nbsp;如果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)应该满足:nbsp;这个递归方程的解仍然是T(n)=O(n3)。因此,该方法并不比用原始定义直接计算更有效。
究其原因,乃是由于式(2)-(5)并没有减少矩阵的乘法次数。而矩阵乘法耗费的时间要比矩阵加减法耗费的时间多得多。要想改进矩阵乘法的计算时间复杂性,必须减少子矩阵乘法运算的次数。按照上述分治法的思想可以看出,要想减少乘法运算次数,关键在于计算2个2阶方阵的乘积时,能否用少于8次的乘法运算。
Strassen提出了一种新的算法来计算2个2阶方阵的乘积。他的算法只用了7次乘法运算,但增加了加、减法的运算次数。这7次乘法是:nbsp;M1=A11(B12-B22)nbsp;M2=(A11nbsp;A12)B22nbsp;M3=(A21nbsp;A22)B11nbsp;M4=A22(B21-B11)nbsp;M5=(A11nbsp;A22)(B11nbsp;B22)nbsp;M6=(A12-A22)(B21nbsp;B22)nbsp;M7=(A11-A21)(B11nbsp;B12)nbsp;做了这7次乘法后,再做若干次加、减法就可以得到:nbsp;C11=M5nbsp;M4-M2nbsp;M6nbsp;C12=M1nbsp;M2nbsp;C21=M3nbsp;M4nbsp;C22=M5nbsp;M1-M3-M7nbsp;以上计算的正确性很容易验证。
例如:nbsp;C22=M5nbsp;M1-M3-M7nbsp;=(A11nbsp;A22)(B11nbsp;B22)nbsp;A11(B12-B22)-(A21nbsp;A22)B11-(A11-A21)(B11nbsp;B12)nbsp;=A11B11nbsp;A11B22nbsp;A22B11nbsp;A22B22nbsp;A11B12nbsp;-A11B22-A21B11-A22B11-A11B11-A11B12nbsp;A21B11nbsp;A21B12nbsp;=A21B12nbsp;A22B22nbsp;由(2)式便知其正确性。
nbsp;至此,我们可以得到完整的Strassen算法如下:nbsp;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,A11nbsp;A12,B22,M2);STRASSEN(n/2,A21nbsp;A22,B11,M3);STRASSEN(n/2,A22,B21-B11,M4);STRASSEN(n/2,A11nbsp;A22,B11nbsp;B22,M5);STRASSEN(n/2,A12-A22,B21nbsp;B22,M6);STRASSEN(n/2,A11-A21,B11nbsp;B12,M7);nbsp;;nbsp;end;nbsp;end;nbsp;其中MATRIX-MULTIPLY(A,B,C)是按通常的矩阵乘法计算C=AB的子算法。
nbsp;Strassen矩阵乘积分治算法中,用了7次对 查看原帖>>。收起