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

1第二章矩阵变换和计算一、内容提要本章以矩阵的各种分解变换为主要内容，介绍数值线性代数中的两个基本问题：线性方程组的求解和特征系统的计算，属于算法中的直接法。基本思想为将计算复杂的一般矩阵分解为较容易计算的三角形矩阵.要求掌握Gauss（列主元）消去法、矩阵的（带列主元的）LU分解、平方根法、追赶法、条件数与误差分析、QR分解、Shur分解、Jordan分解和奇异值分解.(一)矩阵的三角分解及其应用1．矩阵的三角分解及其应用考虑一个n阶线性方程组bAx的求解，当系数矩阵具有如下三种特殊形状：对角矩阵D，下三角矩阵L和上三角矩阵U，这时方程的求解将会变得简单.ndddD21,nnnnllllllL21222111,nnnnuuuuuuU22212111.对于bDx，可得解为iiidbx/,ni,,2,1.对于bLx，可得解为1111/lbx,iiikkikiilxlbx/)(11,ni,,3,2.对于bUx，可得解为nnnnlbx/,iinikkikiilxlbx/)(1,1,,2,1nni.虽然对角矩阵的计算最为简单，但是过于特殊，任意非奇异矩阵并不都能对角化，因此较为普适的方法是对矩阵进行三角分解.1）．Gauss消去法只通过一系列的初等行变换将增广矩阵)|(bA化成上三角矩阵)|(cU，然后通过回代求与bAx同解的上三角方程组cUx的解．其中第k步消元过程中，在第1k步得到的矩阵)1(kA的主对角元素)1(kkka称为主元.从)1(kA的第j行减去第k行的倍数)1()1(kkkkjkjkaal（njk）称为行乘数（子）.2）．矩阵A的LU分解对于n阶方阵A，如果存在n阶单位下三角矩阵L和n阶上三角矩阵U，使得LUA,则称其为矩阵A的LU分解，也称为Doolittle分解．Gauss消去法对应的矩阵形式即为LU分解,其中L为所有行乘子组成的单位下三角矩阵,U为Gauss消去法结束后得到的上三角矩2阵.原方程组bAx分解为两个三角形方程组yUxbLy.3）．矩阵LU分解的的存在和唯一性如果n阶矩阵A的各阶顺序主子式),,2,1(nkkD均不为零,则必有单位下三角矩阵L和上三角矩阵U，使得LUA,而且L和U是唯一存在的．4）．Gauss列主元消去法矩阵每一列主对角元以下（含主对角元）的元素中,绝对值最大的数称为列主元.为避免小主元作除数、或0作分母，在消元过程中，每一步都按列选主元的Guass消去法称为Gauss列主元消去法．由于选取列主元使得每一个行乘子均为模不超过1的数，因此它避免了出现大的行乘子而引起的有效数字的损失.5）．带列主元的LU分解Gauss列主元消去法对应的矩阵形式即为带列主元的LU分解,选主元的过程即为矩阵的行置换.因此,对任意n阶矩阵A，均存在置换矩阵P、单位下三角矩阵L和上三角矩阵U，使得LUPA．由于选列主元的方式不唯一,因此置换矩阵P也是不唯一的.原方程组bAx两边同时乘以矩阵P得到PbPAx,再分解为两个三角形方程组yUxPbLy.5）．平方根法(对称矩阵的Cholesky分解)对任意n阶对称正定矩阵A，均存在下三角矩阵L使TLLA，称其为对称正定矩阵A的Cholesky分解.进一步地,如果规定L的对角元为正数，则L是唯一确定的．原方程组bAx分解为两个三角形方程组yxLbLyT.利用矩阵乘法规则和L的下三角结构可得21112jkjkjjjjlal,jjjkjkikijijlllal/11,i=j+1,j+2,…,n,j=1,2,…,n.计算次序为nnnnlllllll,,,,,,,,,2322212111．由于jjjkal，k=1,2,…,j．因此在分解过程中L的元素的数量级不会增长，故平方根法通常是数值稳定的，不必选主元．6）．求解三对角矩阵的追赶法对于三对角矩阵nnnnnbacbacbacb11122211A,它的LU分解可以得到两个只有两条对角元素非零的三角形矩阵3nnnnudududulll11221132,1111UL.其中niclbuniualbunicdiiiiiiiii,,3,2,,,3,2,/1,,2,1,1111计算次序是nnulululu33221.原方程组bAx分解为两个三角形方程组yUxbLy.计算公式为niylbybyiiii,,3,2,,111,.1,,2,1,/)(,/1nniuxcyxuyxiiiiinnn该计算公式称为求解三对角形方程组的追赶法．当A严格对角占优时，方程组bAx可用追赶法求解,解存在唯一且数值稳定．7）．矩阵的条件数设A为非奇异矩阵，为矩阵的算子范数，称1)(condAAA为矩阵A的条件数．矩阵的条件数是线性方程组bAx,当A或b的元素发生微小变化，引起方程组解的变化的定量描述,因此是刻画矩阵和方程组性态的量.条件数越大,矩阵和方程组越为病态,反之越小为良态.常用的矩阵条件数为∞-条件数:1)(condAAA，1-条件数:1111)(condAAA，2-条件数:)()()(condminmax2122AAAAAAAHH．矩阵的条件数具有如下的性质：(1)1)(condA;(2))(cond)(cond1AA;(3))(cond)(condAA，0，R;(4)如果U为正交矩阵，则1)(cond2U，)(cond)(cond)(cond222AAUUA.4一般情况下，系数矩阵和右端项的扰动对解的影响为定理2.5设bAx，A为非奇异矩阵，b为非零向量且A和b均有扰动．若A的扰动δA非常小,使得11AAδ，则)()(cond1)(condbδbAδAAAAAxδx.关于近似解的余量与它的相对误差间的关系有定理2.6设bAx，A为非奇异矩阵，b为非零向量，则方程组近似解x~的事后估计式为bxAbAxxxbxAbA~)cond(~~)cond(1.其中称xAb~为近似解x~的余量，简称余量。8）．矩阵的QR分解利用正交变换保条件数的性质,将满秩矩阵化为主对角元都大于零的上三角矩阵,保持矩阵条件数不变.设A是n阶可逆实矩阵,则存在正交阵Q和对角元都大于零的上三角阵R，使得QRA,称其为矩阵A的QR分解,并且)(cond)(cond22RA.为实现矩阵一般的QR分解，我们引入Householder矩阵ωωωωIωH2)(,其中0,ωωnR.该矩阵具有如下性质：（1）特征值为：)(21))((TTH即，121TT，个11,,1n；（2）)()(ωHωH,即H阵为对称阵；（3）nIωHωH)()(，即H阵为正交阵；（4）如果yxωH)(，则22xy(不变长度，镜面反射)；（5）设nnxxxR),,,(21x且0x，取12exxω，则（6）.00)()(12212exxxexxHωHx提示：Householder变换并不是直接变换n阶矩阵A,而是通过重复变换矩阵的下三角部分5的列向量得到上三角矩阵,因此,每次变换的Householder矩阵)(,),(),(1-n21ωHωHωH在逐渐降阶,然后将它们分别“嵌入”n阶单位矩阵得到相应的n阶正交阵1-n21QQQ,,,,最后得到正交阵1-n21QQQQ,,,.具体变换过程见例子.(二)特殊矩阵的特征系统特征系统即为矩阵的特征值和特征向量,本节主要介绍与其计算相关的Schur分解.矩阵变换的思想主要为两点:一是三角矩阵的主对角元素即为其所有特征值,二是矩阵的特征多项式和特征值在相似变换下是不变的.因此,理论上获得矩阵特征值的方法就是通过相似变换将其变为一个三角矩阵.Schur定理:设nnAC，则存在酉阵nnUC使得HURUA,其中nnRC为上三角矩阵．由于实矩阵的特征值可能是复数,因此通常在复数域中考虑Schur分解.复数域中相应的矩阵名称及记号为:U的共轭转置:THUU,它在实数域即为转置矩阵.U为酉阵:若IUUUUHH,它在实数域即为正交阵.A为正规矩阵:若HHAAAA.常见的Hermite阵（AAH）、实对称矩阵（AAT）、斜Hermite阵（AAH）、实反对称矩阵（AAT）、酉阵（IAAAAHH）和正交矩阵（IAAAATT）等均为正规矩阵．Schur分解的一些特殊情况如下:上三角矩阵R为正规矩阵当且仅当R为对角矩阵.n阶方阵A为正规矩阵当且仅当存在酉阵U使得HUDUA,D为n阶对角阵.n阶方阵A为Hermite阵当且仅当存在酉阵U使得HUDUA,D为n阶实对角阵.n阶方阵A为酉阵当且仅当存在酉阵U使得HUDUA,D为n阶对角阵,且对角元的模均为1.(三)矩阵的Jordan分解介绍矩阵的每一个特征值有两个重要的指标:代数重数和几何重数.一个特征值作为矩阵多项式的根个重数称为代数重数;它对应的特征子空间的维数称为几何重数.它们分别刻画了特征值在矩阵特征系统中的代数和几何的性质.一般有,代数重数几何重数.当一个特征值的代数重数几何重数,称它为半单的;而当代数重数几何重数时称它为亏损的.n阶方阵A可对角化当且仅当它的所有特征值都是半单的,此时称A为单纯矩阵;否则,A不可对角化当且仅当它有亏损的特征值,此时称A为亏损矩阵.6对于亏损矩阵,只能将其经过相似变换为一个三角矩阵,即为其Jordan标准型.Jordan标准型是一个块对角矩阵，每一个块称为Jordan块,其对角元便为矩阵的特征值．所谓矩阵A的Jordan分解即为通过可逆变换矩阵T化为与之相似的Jordan标准型J,使得1TJTA.1.关于Jordan标准型J．对于特征值i,它的代数重复度就是Jordan标准型中以i为特征值的Jordan块阶数的和，而其几何重复度（即与i相对应的线性无关的特征向量的个数）恰为以i为特征值的Jordan块的个数．J中以i为特征值、阶数为l的Jordan块的个数为lllrrr211,其中lilIr)(rankA,nIIri)(rank)(rank00A．2.关于变换矩阵T可以通过Jordan链得到．将T按J的对角线上的Jordan块相应地分块为kTTTT,,,21,其中Ti为n×ni型矩阵．记iniiiitttT,,,21,则ininiiniiiiiiiiii112211ttAtttAttAtnijCt,ki,,2,1,inj,,2,1我们称向量iniiittt,,,21为关于特征值i的长度为in的Jordan链．显然该Jordan链的第一个向量就是矩阵A的关于特征值i的特征向量，称其为链首．而链中的第j个向量则可由等价的方程iijijninj,,3,2,1ttIA（2-45）求出．但是应当注意:1)Jordan链的链首i1t不仅要求是一个特征向量，而且还要求利用（2-45）可以求出Jordan链中的其它向量iniitt,,2(即不是任何一个特征向量都可作为Jordan链的链首).2)对应于某个特征值i的Jordan链虽然一定存在，但当与i相对应的线性无关的特征向量的个数大于或等于2时，关于特征值i的特征向量中的任何一个有可能都不能作为链首.因此我们必须从i的特征子空间中选取适当的向量作为Jordan链的链首．(四)矩