计算机科学计算答案第二章矩阵变换和计算

1、第二章 矩阵变换和计算一、内容提要本章以矩阵的各种分解变换为主要内容，介绍数值线性代数中的两个基本问题：线性方程组的求解和特征系统的计算，属于算法中的直接法。基本思想为将计算复杂的一般矩阵分解为较容易计算的三角形矩阵. 要求掌握Gauss（列主元）消去法、矩阵的（带列主元的）分解、平方根法、追赶法、条件数与误差分析、QR分解、Shur分解、Jordan分解和奇异值分解.(一) 矩阵的三角分解及其应用1矩阵的三角分解及其应用考虑一个阶线性方程组的求解，当系数矩阵具有如下三种特殊形状：对角矩阵，下三角矩阵和上三角矩阵，这时方程的求解将会变得简单., , .对于，可得解为,.对于，可得解为,.对于，

2、可得解为,.虽然对角矩阵的计算最为简单，但是过于特殊，任意非奇异矩阵并不都能对角化，因此较为普适的方法是对矩阵进行三角分解.1）Gauss消去法只通过一系列的初等行变换将增广矩阵化成上三角矩阵，然后通过回代求与同解的上三角方程组的解其中第步消元过程中，在第步得到的矩阵的主对角元素称为主元.从的第j行减去第k行的倍数（）称为行乘数（子）.2）矩阵的分解对于n阶方阵，如果存在n阶单位下三角矩阵和n阶上三角矩阵，使得, 则称其为矩阵的分解，也称为Doolittle分解Gauss消去法对应的矩阵形式即为分解, 其中为所有行乘子组成的单位下三角矩阵, 为Gauss消去法结束后得到的上三角矩阵. 原方程组

3、分解为两个三角形方程组.3）矩阵分解的的存在和唯一性如果阶矩阵的各阶顺序主子式均不为零, 则必有单位下三角矩阵和上三角矩阵，使得, 而且和是唯一存在的4）Gauss列主元消去法矩阵每一列主对角元以下（含主对角元）的元素中, 绝对值最大的数称为列主元. 为避免小主元作除数、或作分母，在消元过程中，每一步都按列选主元的Guass消去法称为Gauss列主元消去法由于选取列主元使得每一个行乘子均为模不超过1的数，因此它避免了出现大的行乘子而引起的有效数字的损失.5）带列主元的分解Gauss列主元消去法对应的矩阵形式即为带列主元的分解,选主元的过程即为矩阵的行置换. 因此, 对任意阶矩阵，均存在置换矩阵

4、、单位下三角矩阵和上三角矩阵，使得由于选列主元的方式不唯一, 因此置换矩阵也是不唯一的. 原方程组两边同时乘以矩阵得到, 再分解为两个三角形方程组.5）平方根法(对称矩阵的Cholesky分解)对任意阶对称正定矩阵，均存在下三角矩阵使，称其为对称正定矩阵A 的Cholesky分解. 进一步地, 如果规定的对角元为正数，则是唯一确定的原方程组分解为两个三角形方程组.利用矩阵乘法规则和的下三角结构可得, , i=j+1, j+2,n, j=1,2,n.计算次序为由于，k=1,2,j因此在分解过程中的元素的数量级不会增长，故平方根法通常是数值稳定的，不必选主元6）求解三对角矩阵的追赶法对于三对角矩阵

5、, 它的分解可以得到两个只有两条对角元素非零的三角形矩阵.其中计算次序是. 原方程组分解为两个三角形方程组. 计算公式为, 该计算公式称为求解三对角形方程组的追赶法当严格对角占优时，方程组可用追赶法求解, 解存在唯一且数值稳定7）矩阵的条件数设为非奇异矩阵，为矩阵的算子范数，称为矩阵的条件数矩阵的条件数是线性方程组, 当或的元素发生微小变化，引起方程组解的变化的定量描述, 因此是刻画矩阵和方程组性态的量. 条件数越大, 矩阵和方程组越为病态, 反之越小为良态.常用的矩阵条件数为-条件数: ，1-条件数: ，2-条件数: 矩阵的条件数具有如下的性质：(1) ;(2) ;(3) ，;(4) 如果为

6、正交矩阵，则，.一般情况下，系数矩阵和右端项的扰动对解的影响为定理2.5 设，为非奇异矩阵，为非零向量且和均有扰动若的扰动非常小,使得，则.关于近似解的余量与它的相对误差间的关系有定理2.6 设，为非奇异矩阵，b为非零向量，则方程组近似解的事后估计式为. 其中称为近似解的余量，简称余量。8）矩阵的QR分解利用正交变换保条件数的性质, 将满秩矩阵化为主对角元都大于零的上三角矩阵, 保持矩阵条件数不变.设是阶可逆实矩阵, 则存在正交阵和对角元都大于零的上三角阵，使得, 称其为矩阵的分解, 并且.为实现矩阵一般的分解，我们引入Householder矩阵, 其中. 该矩阵具有如下性质：（1） 特征值为

7、： 即，；（2） , 即H阵为对称阵；（3） ，即H阵为正交阵；（4） 如果，则 (不变长度，镜面反射)；（5） 设且，取，则（6）提示：Householder变换并不是直接变换阶矩阵, 而是通过重复变换矩阵的下三角部分的列向量得到上三角矩阵, 因此, 每次变换的Householder矩阵在逐渐降阶, 然后将它们分别“嵌入”阶单位矩阵得到相应的阶正交阵, 最后得到正交阵.具体变换过程见例子.(二) 特殊矩阵的特征系统特征系统即为矩阵的特征值和特征向量, 本节主要介绍与其计算相关的Schur分解. 矩阵变换的思想主要为两点: 一是三角矩阵的主对角元素即为其所有特征值, 二是矩阵的特征多项式和特征

8、值在相似变换下是不变的. 因此, 理论上获得矩阵特征值的方法就是通过相似变换将其变为一个三角矩阵.Schur定理: 设，则存在酉阵使得 , 其中为上三角矩阵由于实矩阵的特征值可能是复数, 因此通常在复数域中考虑Schur分解. 复数域中相应的矩阵名称及记号为:的共轭转置: , 它在实数域即为转置矩阵.为酉阵: 若, 它在实数域即为正交阵.为正规矩阵: 若.常见的Hermite阵（）、实对称矩阵（）、斜Hermite阵（）、实反对称矩阵（）、酉阵（）和正交矩阵（）等均为正规矩阵Schur分解的一些特殊情况如下:l 上三角矩阵为正规矩阵当且仅当为对角矩阵.l 阶方阵为正规矩阵当且仅当存在酉阵使得,

9、为阶对角阵.l 阶方阵为Hermite阵当且仅当存在酉阵使得,为阶实对角阵.l 阶方阵为酉阵当且仅当存在酉阵使得,为阶对角阵,且对角元的模均为1.(三) 矩阵的Jordan分解介绍矩阵的每一个特征值有两个重要的指标: 代数重数和几何重数. 一个特征值作为矩阵多项式的根个重数称为代数重数; 它对应的特征子空间的维数称为几何重数. 它们分别刻画了特征值在矩阵特征系统中的代数和几何的性质. 一般有, 代数重数几何重数. 当一个特征值的代数重数几何重数, 称它为半单的; 而当代数重数几何重数时称它为亏损的. 阶方阵可对角化当且仅当它的所有特征值都是半单的, 此时称为单纯矩阵; 否则, 不可对角化当且仅

10、当它有亏损的特征值, 此时称为亏损矩阵.对于亏损矩阵, 只能将其经过相似变换为一个三角矩阵, 即为其Jordan标准型. Jordan标准型是一个块对角矩阵，每一个块称为Jordan块, 其对角元便为矩阵的特征值所谓矩阵的Jordan分解即为通过可逆变换矩阵化为与之相似的Jordan标准型, 使得. 1. 关于Jordan标准型对于特征值, 它的代数重复度就是Jordan标准型中以为特征值的Jordan块阶数的和，而其几何重复度（即与相对应的线性无关的特征向量的个数）恰为以为特征值的Jordan块的个数中以为特征值、阶数为的Jordan块的个数为,其中, 2. 关于变换矩阵T可以通过Jorda

11、n链得到 将按的对角线上的Jordan块相应地分块为, 其中i为nni型矩阵记, 则 , , 我们称向量为关于特征值的长度为的Jordan链显然该Jordan链的第一个向量就是矩阵的关于特征值的特征向量，称其为链首而链中的第j个向量则可由等价的方程 （2-45）求出但是应当注意:1) Jordan链的链首不仅要求是一个特征向量，而且还要求利用（2-45）可以求出Jordan链中的其它向量(即不是任何一个特征向量都可作为Jordan链的链首).2) 对应于某个特征值 的Jordan链虽然一定存在，但当与 相对应的线性无关的特征向量的个数大于或等于2时，关于特征值的特征向量中的任何一个有可能都不能

12、作为链首.因此我们必须从的特征子空间中选取适当的向量作为Jordan链的链首(四) 矩阵的奇异值分解对于方阵,利用其特征值和特征向量可以刻画矩阵的结构.对非方阵情形,这些方法已经不适用.而推广的特征值-矩阵的奇异值分解理论能改善这种情况. 利用奇异值和奇异向量不仅可以刻画矩阵的本身结构,而且还可以进一步刻画线代数方程组的解的结构,是构造性的研究线代数问题的有利的工具.设, Hermite半正定矩阵的特征值为, 称非负实数 ()为矩阵的奇异值奇异值分解: 设A, 且其秩rank(A)=r, 则存在m阶、n阶酉阵U、V使得, 其中，为矩阵A的非零奇异值U与V的列向量和分别称为矩阵A的与奇异值对应的

13、左奇异向量和右奇异向量利用矩阵的奇异值讨论矩阵的性质:(1) 矩阵A的非零奇异值的个数恰为矩阵A的秩(2) , ，其中, 为由的列向量生成的子空间，称为的值域或像空间，即。称为的零空间或核，即。(3) 设，则, =(4) 如果为Hermite矩阵，则的奇异值即为的特征值的绝对值(5) 如果为阶方阵，则 (6) 秩为r的mn矩阵可以表示为r个秩为1的矩阵的和.(7) 为正规阵, 是A的特征值, 是相应于的特征向量, 则是的特征值, 相应于的特征向量仍为.(8) 为正规阵, 是A的特征值, 是相应的特征向量, 如果, 则 与正交.2.2典型例题分析例1 证明在对矩阵进行Gauss消去法的过程中,

14、主元 () 均不为零的充要条件是的各阶顺序主子式() 均不为零.证明 利用归纳法, 当时, , 结论显然成立. 假设结论直到成立, 则Gauss消去法可以进行到步, 即存在个Gauss变换, 使得,其中是对角元为()的上三角阵, 于是的阶顺序主子阵为. 另一方面, 将的两端在第行列处分块有, 其中为阶单位下三角阵. 因此的阶顺序主子式,由归纳假设知, 主元当且仅当, 即结论对成立. 故由归纳法, ()当且仅当() .例2 证明: 若为可逆矩阵, 则可进行LU分解的充要条件是的各阶顺序主子式() 均不为零.证明 充分性. 由例1结论知如果() 均不为零, 则主元, 于是可对进行Gauss消去法,

15、 从而得到的LU分解.必要性. 若存在单位下三角阵和上三角阵使得, 则,由可逆知主元(), 再由例1可得的各阶顺序主子式().例3 证明, 若可逆矩阵可进行LU分解, 则分解必唯一.证明 如果存在两个LU分解, 即, 其中皆为单位下三角阵, 皆为上三角阵. 由可逆知也可逆, 于是有. 不难验证, 单位下三角阵的逆矩阵为单位下三角阵, 而上三角阵的逆也为上三角阵. 进一步, 单位下三角阵的乘积仍是单位下三角阵, 而上三角阵的乘积也为上三角阵. 因此上式左端为一个单位下三角阵, 而右端为一个上三角阵. 显然, 等式成立当且仅当两端皆为单位矩阵, 故可得, 即分解唯一.例4 阶Hilbert矩阵为,

16、 计算的条件数.解 (1) 计算的条件数, 容易得到, , , , 于是, . 同样可计算, . 当越大, 矩阵病态越严重.(2) 考虑方程组, 设和有微小误差（取3位有效数字）有，简记为，其解为. 而方程组的精确解为. 于是, , , . 这就是说和的相对误差不超过, 而引起解的相对误差超过.例5 阶复Householder矩阵定义为, 其中. 证明为Hermite矩阵, 也是酉矩阵, 并求它的特征值.证明 , , 即为Hermite矩阵, 也是酉矩阵.由矩阵特征值的性质知, , 而, 因此的特征值为.例6 已知, 求Householder矩阵, 使得.解 由, 取, 则,使得.例7 设为阶

17、正规矩阵, 证明若, 则.证明 根据Shur定理, 正规矩阵存在分解, 其中为阶酉阵, 为阶对角矩阵, , . 于是由, 当且仅当, , 即.例8 求矩阵的Jordan分解.解 , 于是的特征值为, 代数重数为4, 故以为特征值的Jordan块阶数之和为4. 而的几何重数为, 故以为特征值的Jordan块的个数为2. 注意到故以为特征值的阶数为1的Jordan块的个数为. 因此的Jordan标准型为.下面求矩阵化Jordan标准型的变换矩阵. 首先求出所对应的线性无关的特征向量为, . 其次确定长度为3的Jordan链的链首, 令, 由, 为使有解, 只需取即可. 再取, 此时为链首, 解得,

18、 . 令, 由, 为使有解, 只需取即可. 再取, 此时, 解得链尾或者. 于是可得或者,故有的Jordan分解为.例9 证明若阶方阵的奇异值满足, 则可逆, 而且, .证明 由奇异值的定义, , 知, 则可逆, 且. 于是, 也可逆, 且的特征值为, 注意到的特征值与的特征值相同, 因此.例10 设, 如果存在阶和阶的正交矩阵和, 使得, 则称和正交相抵. 证明正交相抵的矩阵有相同的奇异值.证明 由, , 知与相似, 从而它们由相同的特征值, 故和有相同的奇异值.注: 不难验证, 正交相抵具有自反性、对称性和传递性. 因此正交相抵是等价关系. 它所形成的等价类称为正交相抵等价类. 此例说明,

19、 正交相抵等价类中的矩阵都有相同的奇异值, 所以对此类中任一矩阵, 所作的奇异值分解中的对角矩阵相同, 并由它们的奇异值组成. 即是该矩阵类中的标准型矩阵.2.3 习题1. 填空题 (1) ,当满足条件 时，可作分解.(2), 当满足条件 时，可作分解，其中是对角元素为正的下三角阵，则.(3) ，则= .(4) 设,其Schur分解为，其中为酉矩阵，为上三角矩阵特别地，当为正规矩阵时，R为 矩阵，的特征值为，的特征向量为 ；当为Hermite矩阵时，R为 矩阵；当为斜Hermite矩阵时，R为 阵.2利用Gauss消去法，Gauss列主元法解方程组3用Gauss列主元法求解方程组，并求出系数矩

20、阵的行列式det（）的值4设, 利用1题消元过程求出L和U矩阵，并验证 =LU5下述矩阵能否作Doolittle分解，若能分解，分解式是否唯一？6利用Doolittle分解法，Cholesky法和三对角追赶法三种方法求解线性方程组：7设，求的分解.8证明（1）；（2）（为非零常数）9设、都是阶非奇异方阵，试证10证明上三角矩阵R为正规阵的充分必要条件为R为对角矩阵11证明Schur不等式：，其中为的特征值，并证明Schur不等式等号成立的充分必要条件是为正规矩阵12求矩阵的Jordan分解13证明定理2.15.14证明 正规矩阵的奇异值是其特征值的模，Hermite半正定矩阵的奇异值为其特征值

21、15.设,特征值的代数重数为4, 已知，,其中，求的Jordan标准型.16.设的奇异值分解为求，17.设, 求的奇异值分解,并据此计算 ，.2.4 习题解答1. (1) 当时, 可作LU分解. 注: 矩阵的各阶顺序主子式均不为零只是可作LU分解的一个充分条件. 当时, , 虽然的行列式(2阶顺序主子式)为零, 但经第一步消元可得, 这已是一个上三角矩阵, 说明此时也可作LU分解.(2) 当时, 正定, 可作分解, .(3) .(4) 设,其Schur分解为，其中为酉矩阵，为上三角矩阵特别地，当为正规矩阵时，R为 对角 矩阵，的特征值为R的对角元素 ，的特征向量为U的列向量 ；当为Hermit

22、e矩阵时，R为 实对角 矩阵；当为斜Hermite矩阵时，R为 对角元素为纯虚数或零的对角 阵.2解 (1) Gauss消元法:其中, , 所求解为 .(2) 带列主元的Gauss消元法:其中, , , , 所求解为 .3. 解, 其中, 解为 .由, .4. 解: 由第2题中Gauss消元过程可知, , 容易验证.5. 解不能继续消元, 因此不能进行LU分解., 其中, . 经过第一次消元得到一个上三角矩阵, 由于第2列主对角线以下的元素已经是0, 还可以利用把最后一行消去, 也得到一个上三角矩阵. 因此得到了矩阵两个不同的LU分解. 这说明在某些情况下, 即使矩阵的各阶顺序主子式为0, 也

23、能进行LU分解, 但分解不唯一.对于矩阵, 其各阶顺序主子式为1,1,1. 可得唯一的LU分解.6. 解 (1) Doolittle分解, 则的Doolittle分解为. 按得, 由解得, 再由解得.(2) Cholesky分解由解得.按得, 由解得, 再由解得.(3) 追赶法利用三对角矩阵的LU分解公式可得与Doolittle分解一致的结果.7. 解:, 记, , , , . 记, , , , , , , 则有, 得到分解, 其中.8. 证明: (1) 根据矩阵范数的相容性和单位矩阵的算子范数为1的性质有.(2) 当, 根据矩阵范数的齐次性和逆矩阵的性质有.9. 证明: 由矩阵范数的相容性.10. 证明: 由定义, 上三角阵是正规矩阵当且仅当分别比较等式两端乘积矩阵的主对角元素即可得知, ; , 即为对角矩阵.11 证明: 设矩阵的Shur分解为, 其中, 由相似变换保持矩阵的特征值不变可知的主对角元为的所有特征值, 即, . 再由矩阵的迹等于特征值之和, 因此. 其中等号成立的充要条件是的非主对角元