分块矩阵的初等运算论文00927.doc

毕 业 设 计（论 文）设计(论文)题目：分块矩阵的初等运算及其应用目录摘要.ABSTRACT.第1章 绪论.1第2章 分块矩阵的定义及相关运算.16 2.1 分块矩阵的定义.182.2 分块矩阵的运算.20 2.2.1 加法与数量乘法运算.21 2.2.2乘法运算.22 2.2.3 转置运算.23 2.3 分块矩阵的初等变换.28 2.3.1定义. 2.3.2运算.第3章 分块矩阵的应用.29 3.1分块矩阵在解线性方程组中的应用.3.2 遗传算法运行参数分析.32 3.2.1 确立评价目标函数.36 3.2.2 分析各参数的影响.383.3 对基本遗传算法的改进.40 3.3.1适应值函数的改进.42 3.3.2 自适应遗传算法.46结论. . .48参考文献.49致谢.50附录.55附录 中文译文. .55附录 英文原文.62(注1：如果还有其他附录，可放在中文译文之前，中文译文、英文原文编号顺延)(注2：先将目录排好，基本对齐，然后选择段落-对齐方式-分散对齐)分块矩阵的初等运算及其应用摘要 作为高等代数中的一个工具，矩阵是高等代数中的一个重要概念，分块矩阵是矩阵中的一个重要内容，在高等代数中有着很重要的应用，本文详细且全面论述了分块矩阵阵的概念和算法，包括用分块矩阵来算矩阵的乘积，利用分块矩阵求逆矩阵的问题，用分块矩阵求矩阵的行列式问题。分块矩阵是处理矩阵问题的重要技巧。分块矩阵思想来源于对矩阵运算复杂度及存储空间的考虑。特别当矩阵太大不适合存储在计算机内存中的时候，通过分块矩阵允许计算机每次只处理存储在内存中几个子矩阵，支持向量传输结构的向量计算机能够更加高效地运行支持分块矩阵的矩阵算法。分块矩阵可以降低矩阵的阶数，使矩阵更加条理清晰，使得矩阵的相关运算简单化，并使矩阵证明方面的相关问题得以便捷的解决。本文重点就分块矩阵的定义、分块方法、基本运算，行列式和求逆矩阵的计算，以及关于矩阵的秩的方面的证明问题进行了分析。使用了大量的例题说明了分块矩阵的技巧可以使高等代数中的很多计算与证明问题简单化。所以了解分析并掌握分块矩阵的性质与应用及相关的技巧是非常必要的。关键词：矩阵；分块矩阵；子矩阵；行列式；矩阵的秩；逆矩阵；特征值。The partitioned matrix of the elementary operation and its application ABSTRACTMatrix is an important concept in high algebra, but also an instrument for research of many filiation in high algebra. And the means of dividing a large-scale matrix up into some small one is a main skill to resolve the question of matrix. The idea of partitioned matrix comes of the advisement to the complexity of matrix's calculate and the unit of space.Especially,when the matrix is too large to save in the EMS memory, the computer which support the network management vector transport can take order with the partitioned matrix algorithm in high efficiency, with the partitioned matrix permit the computer only deal with the submatrix that store in the EMS memory every time.Theory about block matrix could be used to decline high order matrix and make it clearer and easier to calculate and prove some problems about matrix. This paper focuses on the problems of the concept of block matrix, and the numeration of square matrixand the proof of matrix. It shows the convenience of the block matrix in the problems of matrix and high algebra by making use of a number of examples. It is necessary that we must learn and analyse and grasp the skill of block matrix which is an important concept in high algebra.Keywords： matrix；block matrix ；submatrix；determinant ；Matrix rank ；inverse matrix ；characteristic value 第1章 绪论矩阵作为数学工具之有其重要的实用价值，他常见于很多学科中，如：高等代数、数值分析、线性规划、统计分析，以及组合数学等，在实际生活中，很多问题都可以借用矩阵抽象出来进行表述并进行运算，如在密码的编译和破译等，矩阵的概念和性质相对矩阵的运算比较容易掌握，对于矩阵的运算和应用，则有很多的问题值得我们去研究，其中当矩阵的行数和列数都相当大时，矩阵的运算和证明回事很繁琐的过程，因此这时我们得有一个新的矩阵处理工具，来使这些问题得到更好的解释，矩阵分块的思想由此产生。分块矩阵形象的揭示了一个复杂或是特殊矩阵的内部本质结构，它的特点是简化运算，把大矩阵化成若干个小矩阵，使原矩阵的结构显得简单清晰。本文总结讨论了分块矩阵在各方面的应用，主要以计算与证明两个方面为主，而计算方面则有所侧重。（1） 详尽论述了分块矩阵的基本定义、分块方法、基本性质以及运算规则，分析了一些分块的技巧。（2） 由分块矩阵的初等变换推导出分块矩阵的一些性质，并说明这些性质在行列式计算与证明中的应用。特别的对于一些高阶行列式通过分块处理可以直观方便的求出它的值。（3） 分块矩阵作为线性代数中的一个基本工具，研究很多问题都要用到它。借助分块矩阵的初等变换可以发现分块矩阵在求逆矩阵以及矩阵的秩方面的应用。（4） 矩阵最多是用于解线性方程组。利用分块矩阵对于求解齐次线性方程组与非齐次线性方程组在大量的实例中得出求解方程组解向量、基础解系、通解的一些简便公式。（5） 通过论述分块矩阵在证明方面的应用，如矩阵的秩的相关问题，证明一个矩阵是某些特殊矩阵的问题，证明有关矩阵的秩的定理问题。本文将通过对分块矩阵性质的研究分析，比较系统的总结讨论分块矩阵在计算与证明方面的应用，为很多线性代数中问题的处理带来很大的方便。第2章 分块矩阵的定义及相关运算2.1 分块矩阵的定义 设是一个矩阵，如果将用条横线和条竖线分成个小矩阵，每一个小矩阵称为的一个子块或子矩阵，以这些子块作为元素构成的行列的矩阵称为矩阵的分块矩阵。亦称是一个块矩阵。例如，矩阵=中，表示2级单位矩阵，而 =， O=这就是我们所说的矩阵的分块2.2分块矩阵的运算2.2.1加法与数量乘法运算 设都是阶矩阵，如果其分块方式一样，其中，都是矩阵，其中，。则有，。2.2.2乘法运算设将分块成，其中每个都是小矩阵，每个是小矩阵。于是有其中（）。应该注意，矩阵A的列的分法必须与矩阵B的行的分法一致。2.2.3转置运算 分块矩阵的转置不仅要行列互换，各个子矩阵也要进行转置。如，其中是小矩阵，则 。2.3分块矩阵的初等变换2.3.1定义受线性方程组的消元法启发得出矩阵的初等行变换（行对换变换、行倍乘变换、行倍加变换），而将分块矩阵与初等变换结合就成为矩阵运算中极端重要的手段。如同一般矩阵，分块矩阵的初等变换有三种： .交换分块矩阵的两个块行（列）； .用一个非奇异矩阵K左乘（右乘）分块矩阵的某一个块行（列）； .将分块矩阵的某一个块行（列）的K（矩阵）倍加到分块矩阵的另一个块行（列）上。2.3.2运算 将分块乘法与初等变换结合就成为矩阵运算中极端重要的手段。现将某个单位矩阵分成，对其作相应的初等变换得到的矩阵称为分块初等矩阵：对换阵；倍乘阵，；倍加阵，。定理1：对分块矩阵作分块初等行变换，相当于用相应的分块初等矩阵左（右）乘该矩阵。证明：记的分块形式与上述分块单位矩阵的分块形式一样，则由分块矩阵的乘法得=；=；=。例1.设方阵其中(i=1，.，9)都是矩阵，设是任意阶方阵，则矩阵对于有。证明：设是级单位矩阵，则 =，所以=。例2. 设方阵=其中都是矩阵，设是任意阶方阵，则矩阵对于=有。证明：由=，取行列式得。例3.试证行列式乘积公式。证明1：设，为阶单位矩阵。1）对K的行列式按前行展开，得；2）对K作初等变换=；由例2可知。将M的行列式按前n行展开，得。由1）2）得。证明2：作阶行列式，展开得，由初等变换得。定理2.设都是阶方阵，则有4。证明：。例4.计算阶行列式解：令=，=， 则 。第三章 分块矩阵的应用3.1分块矩阵在解线性方程组中的应用常规解线性方程组一般使用初等变换法，方程个数较多时初等变换稍显繁琐。采用分块矩阵解法，线性方程组解向量、基础解系、通解变得直观，步骤简洁。3.1.1齐次线性方程组用行初等变换可以将一般的矩阵化为阶梯形，得到的最简形式称为标准阶梯形。如矩阵=，经行初等变换后得=，为的标准阶梯形。设一般的齐次线性方程组为 。其中=，=。定理1：设元齐次线性方程组的系数矩阵的秩，则方程组基础解系存在，且基础解系中含线性无关解的个数为。其通解为。证明：（应用分块矩阵）1） 假设的阶非零子式位于的左上角（如果不在左上角通过互换行列可以达到目的），则经过初等行变换可化为标准阶梯形=，由=O=满足，从而满足，所以为的个解。2）设是AX=0的一个解。因为是的解，所以线性组合，也是的解。比较知，即任一个解都可以由线性表示。即使方程组的一个基础解系。证明过程给出了一种求基础解系的方法。例1.解方程组解：系数矩阵=，=2，基础解系含4-2=2个解。基础解系为：=即=，。通解：，c1，c2R。3.1.2非齐次线性方程组 定义：设是阶非奇异阵，对其分块=，其中分别是，矩阵，。当非奇异时，存在=，有其中，非奇异。=，=（可逆）求解非齐次线性方程组。例2.求解方程组解：系数矩阵=，其中=，=，=，=。求得=，=。方程左乘=得=，解得=2 5 4 -3/2 1/2。3.2 分块矩阵在行列式计算中的应用行列式是线性代数中的一个基本概念，它的理论已经涉及几乎所有的数学分支，如数学分析、离散数学、数值分析等，是一个极其重要的数学工具。而直接计算高阶行列式和一些特殊的行列式往往比较困难，利用分块矩阵的方法求行列式往往会意想不到的方便。3.2.1 引理设矩阵 =或=，其中都是方阵，则 。3.2.2 定理及几条推论设=，为阶方阵，为阶方阵，或可逆。定理：可逆，； 特别的，当为同阶方阵，有。 可逆，； 特别的，当为同阶方阵，有。 可逆，为同阶方阵， 有。证明： 由分块矩阵的乘法，=； 由引理得； 特别的，当 ，有。 同理，=， 取行列式得 特别的，当，有。 由行列式的性质和引理， 有。例1. 计算行列式，解：令 =，=，=，=。则皆为阶方阵，得可逆。=，所以。例2.计算行列式解：令，其中=，=1，=2 0 0 0，=。则，所以=33。例3.求行列式，解：令=，=，=，=。可逆，。=1 1 . 1=。所以。例4：计算： 的值 解：原式=其中= ，=，=， = 又因为=100 ，而， 所以原式=53推论：分别是，矩阵，；为阶零矩阵，；皆为阶方阵，。证明：由定理得，分别令，即；，所以；对矩阵的后行应用Laplace定理，所得的所有阶子式中，除外，其余至少包含一列零向量，所以值为0。而的余子式为，位于矩阵的第行，第列。所以；=。所以。例1.计算解：令=，其中=，=，=；所以=所以=-。例2.计算解：，其中=，=，= 由推论可得。第2章 遗传算法简介本章主要介绍了遗传算法产生的背景，遗传算法的发展及研究状况，以及本文的主要工作。2.1 遗传算法的基本流程本章主要介绍了遗传算法产生的背景，遗传算法的发展及研究状况，以及本文的主要工作。应用程序模块容错模块决策模块资源/权限模块攻击者图2.1 基于拜占庭协议的容侵系统重构设计模块图2.2 遗传算法的基本实现技术本章主要介绍了遗传算法产生的背景，遗传算法的发展及研究状况，以及本文的主要工作。2.2.1 编码本章主要介绍了遗传算法产生的背景，遗传算法的发展及研究状况，以及本文的主要工作。表2.1 时间表时间地点任务性格5678结论本文介绍了当前解决各类矩阵特征值问题的方法，特别的研究了计算矩阵特征值问题的几种经典的算法，具体研究了幂法、反幂法、Jacobi方法、QR方法的基本思想、算法并用MATLAB编制程序实现该算法，对运行出来的结果进行分析从而比较这几种算法的优缺点。本文所研究的这几种经典的算法都能有效的解决矩阵特征值问题，但是随着科技的发展，电脑硬件不断提高，人们对于计算的速度，结果的精确度，算法的简洁度都有了更高的要求。因此，新的迭代方法不断地出现。比如说幂法是求矩阵按模最大特征值与最大特征向量的经典数值方法，但是幂法的最大缺点是收敛的速度比较慢。作为对幂法的补充，利用矩阵的函数，提出了另一种求非负方阵的最大特征值及最大特征向量的迭代算法，也就是方法。方法的收敛速度常快于幂法。并且在解决大规模非对称矩阵的传统投影类方法基础上又提出了一种精化的Arnoldi方法，这种精化的投影类方法在解决一些困难问题时效果更加明显。虽然近年来矩阵特征值问题的计算方法取得了重大进展，但是矩阵特征值问题的研究还远远没有结束。面对实际应用中纷繁复杂的矩阵特征值问题，现有的算法及计算机硬件、软件常常望之兴叹，今后的研究工作依旧任重而道远。参考文献1 徐成贤，陈志平，李乃成.近代优化方法M.北京：科学出版社,2002.2427.2 Isidori A. Nonlinear control systemsM.2nd,New York:Springer Press,1989.3233.3 王俊伟，汪定伟.微粒群算法中惯性权重的实验与分析J.系统工程学报,2005,20(2):194198.4Reynolds C W, Locks F. Adistributed behavioral model J,Computer Graphic,1987,21(4):2530.5 肖龙光.部分智能优化算法的改进及其数学理论分析D.上海：东华大学，2005.6 Sun M.A study of helicopter rotor aerodynamics in ground effectD.Princeton:品册，1983.7 辛希孟. 信息技术与信息服务国际研讨会论文集：A集C. 北京：中国社会科学出版社，1994.8 北京空气动力研究所. 第九届高超声速气动力会议论文集C. 北京：北京空气动力研究所，1997.9 陈永康，李素循，李玉林. 高超声速流绕双椭球的实验研究A. 见：北京空气动力研究所编. 第九届高超声速气动力会议论文集C. 北京：北京空气动力研究所，1997：914.10 Peng J, Luo X Z, Jin C J. The study about the dynamics of the approach glide-down path control of the carrier aircraftA. In: GONG Yao-nan ed. Proceedings of the Second Asian-Pacific Conference on Aerospace Technology and ScienceC. Beijing: Chinese Society of Aeronautics and Astronautics, 1997: 236241.11 孔祥福. FD-09风洞带地面板条件下的流场校测报告R. 北京空气动力研究所技术报告 BG7-270，北京：北京空气动力研究所，1989.12 MIL-E-5007 D, 航空涡轮喷气和涡轮风扇发动机通用规范S. 美国空军，1973.13 黎志华，黎志军. 反馈声抵消器P. 中国专利：ZL85100748，19860924.致谢附录附录 中文译文分块对角矩阵的逆矩阵冉瑞生 黄廷祝电子科技大学 数学与应用数学 成都610054 中国内容简介首先，对扭曲的分块对角矩阵的分解块进行了介绍。通过对一些特殊的矩阵的分解，计算其中每一块的逆矩阵，更进一步地获得了分块对角矩阵的算法，而且还对每一块元素的逆矩阵进行了比较。最后，本文对该算法及其一些其他关于逆矩阵的算法的计算复杂度和计算所需时间进行了比较。版权归教育部博士点基金公司所有 2005年关键词 分块对角矩阵 逆矩阵 扭曲的分块矩阵分解 算法1. 介绍 对角矩阵中通常出现的大多数问题来自数学、物理学和工程学，有很多人投身于对角矩阵的研究，对角矩阵和分块对角矩阵是一项还存一些问题需要解决的重要课题。相反的是nec-essary的许多问题例如计算的条件数，预算的逆元素以及关于线性系统的系数矩阵都是分块对角矩阵。近年来，许多人已经研究了对角矩阵的逆，但是很少有人研究分块对角矩阵的逆，在最近几年提交的文章中，我们看到的最新的结果是该算法应用高性能计算机的对称分块对角矩阵的发展，该算法对于分块矩阵的应用极其重要。该算法应用于分块矩阵，主要是计算multipli-cations矩阵，在许多计算环境中，这种算法比线性代数的基本算法更加有效，分块是本文研究的以下表格。 A = 当和都是有顺序的矩阵序列，在这里，“-”只是为了计算方便没有特定的意义。本文中所有的矩阵都是非奇异的，除非另有说明。LU对角矩阵的分解提出了问题，显然，LU分解和UL判别可以容易的分解对角矩阵。结合这两种分解方法，第二章确定提出了扭曲的矩阵分解。根据特殊构造分解扭曲的矩阵、迭代计算公式每一块的逆矩阵的元素j可以被确定.让j=1,2，.，K，每一块对角矩阵的演算可以被建立。基于该算法的表达式，我们对逆矩阵的元素进行了构造。2. 引理 引理2.1 假设A是分块矩阵（形式同1.1），然后使j=1,2，.，k，扭曲的分块分解为当和都是矩阵序列，可以通过一下矩阵计算迭代公式：证明 ：考虑到二次曲线的分解，用的第行乘上的第列，以此迭代即可计算得到矩阵和。此时，类似地，我们用的第行乘上的第列，我们就可以得到第二种情况，第三种情况也可以通过的第行和的第列得到。然后，通过获得的矩阵序列和构造矩阵和，我们得到了二次曲线的分解是正确的。3. 主要结果 定理3.1 假定A是分块对角矩阵（形式同1.1），使得当都是次矩阵，然后的第块元素就是下列矩阵的形式：。证明：，是一个有元素的单位矩阵，代表第个单位矩阵。 ,当矩阵块是2.2的形式，通过引理2.1特殊构造和得综上所述，得；令；通过计算，易得，如下： “”代表非零常数高斯消去即得矩阵的逆矩阵的求法。我们发现和的结构相同，第行和第列是。通过3.2得 即 综上所述，我们的结论成立。不论还是，通过代入公式3.1，我们都可以容易求得分块对角矩阵的逆。定理3.2 令A是一个分块对角矩阵（形如1.1），且令，则的逆矩阵可以被表示为这里和通过2.2求得。4. 对比计算的复杂程度及代入数值进行计算对于任意阶的矩阵，我们都可以通过两个矩阵的乘积以及高斯消去法得到，因此计算复杂程度，我们只需考虑乘积和消去，易得计算复杂程度为。Meurant已经用列出了对称矩阵的逆的算法，注 非对称对角矩阵的形式，我们有 ；是对角矩阵的一块，则对角元素是 ，是对称对角矩阵。综上所述，Meurant的算法是相等的，由此获得对角矩阵的逆矩阵，我们翻出经典的“高斯消去法”或“分块矩阵初等行列变换法”，我们比较一下这些算法的计算复杂度，得表1。显而易见，本文的算法复杂度小于已有的算法，通常分块矩阵的逆矩阵是满置的，有个元素需要计算，所以本文的计算复杂度是最小的。此外，1.1式也可以认为是元素个数为的带宽矩阵，带宽为，易得计算复杂度为，即。很明显，“高斯消去法”比该方法复杂很多。我们通过计算机做一些实验，矩阵序列中的元素是和是之间的随机数字，对角矩阵序列的元素也是之间的随机数，该对角矩阵是矩阵序列与之和，因此，测试矩阵是一个对角占优矩阵。表2为上述算法的时间复杂度，在表2中，本文中的算法，Meurant算法和分块矩阵的基本算法都由决定，区分T_Bmeurant和T_Bcatchup。该算法与Meurant算法进行比较分析，分块矩阵的算法通过和来进行弥补。在时间复杂度上“高斯消去法”比该算法更加复杂，因此我们不在表2中进行比较。通过表2可以得出，与其他两种算法进行比较，该算法节约了很多时间，尤其是与分块矩阵的初等行列变换相比。表1 计算复杂度的比较高斯消去法分块矩阵初等算法Meurant算法本文算法表2 时间复杂度的比较100200600100015002550200500500443230.03000.15003.785026.428048.61000.06000.27004.987033.278058.19400.10000.48108.282053.707077.46100.50000.55560.75900.79420.85330.30000.31190.45700.49210.6489参考文献1 M.E.A.El-Mikkawy,On the inverse of a general tridiagonal matrix, Appl. Math. Comp. 150 (2004) 669679.2 C.M.da Fonseca, J. Petronilho, Explicit inverses of some tridiagonal matrices, Lin. Alg. Appl. 325 (2001) 721.3 G. Meurant, A review on the inverse of symmetric tridiagonal and block tridiagonal matrices, SIAM J. Matrix Anal. Appl. 13 (1992)707728.4 M.E.A. El-Mikkawy, A note on a three-term recurrence for a tridiagonal matrix, Appl. Math. Comp. 139 (2003) 503511.5 G.H. Golub, C.F. Van Loan, Matrix Computation, third ed., the Science Press, Beijing, 2001, p. 27.6 L.J. Ding, Numerical Computing Method, Sci. and Eng. Univ. Press, Beijing, 1997, p. 26.7 S. Dhillon Inderjit, Reliable computation of the condition number of a tridiagonal matrix in O( n) time, SIAM J. Matrix Anal. Appl 19(3) (1998) 776796.8 C.X. Liu, Computing Method of the Super Large-Scale Sparse Matrices, Shanghai Sci. and Tech. Press, Shanghai, 1991, p. 189. 附录 英文原文