《第二章 矩阵变换和计算》由会员分享，可在线阅读，更多相关《第二章 矩阵变换和计算（74页珍藏版）》请在金锄头文库上搜索。
1、第二章 矩阵变换和计算 一、内容提要 本章以矩阵的各种分解变换为主要内容，介绍数值线性代数中的两个基本问题：线性方程组的求解和特征系统的计算，属于算法中的直接法。基本思想为将计算复杂的一般矩阵分解为较容易计算的三角形矩阵. 要求掌握Gauss（列主元）消去法、矩阵的（带列主元的） LU分解、平方根法、追赶法、条件数与误差分析、QR分解、Shur分解、Jordan分解和奇 异值分解. (一) 矩阵的三角分解及其应用 1矩阵的三角分解及其应用 考虑一个n阶线性方程组Ax?b的求解，当系数矩阵具有如下三种特殊形状：对角矩阵D，下三角矩阵L和上三角矩阵U，这时方程的求解将会变得简单. ?d1?D? ?
2、 ?l11?l21 L?, ?ldn?n1 ?u11 ?U?, ? u21u22 ? un1? ?un2? . ?unn? d 2 l22?ln2 ? lnn ? 对于Dx?b，可得解为xi?bi/di,i?1,2,?,n. i?1 对于Lx?b，可得解为x1?b1/l11,xi?(bi? ?l k?1 n ik xk)/lii,i?2,3,?,n. 对于Ux?b，可得解为xn?bn/lnn,xi?(bi? ?l k?i?1 ik xk)/lii,i?n?1,n?2,?,1. 虽然对角矩阵的计算最为简单，但是过于特殊，任意非奇异矩阵并不都能对角化，因此较为普适的方法是对矩阵进行三角分解. 1）
3、Gauss消去法 只通过一系列的初等行变换将增广矩阵(A|b)化成上三角矩阵(U|c)，然后通过回代求与Ax?b同解的上三角方程组Ux?c的解其中第k步消元过程中，在第k?1步得到的矩阵A(k?1)的主对角元素akk (k?1) 称为主元.从A(k?1)的第j行减去第k行的倍数ljk? ajk (k?1)(k?1) akk （k?j?n）称为行乘数（子）. 2）矩阵A的LU分解 对于n阶方阵A，如果存在n阶单位下三角矩阵L和n阶上三角矩阵U，使得A?LU, 则称其为矩阵A的LU分解，也称为Doolittle分解Gauss消去法对应的矩阵形式即为LU分解, 其中L为所有行乘子组成的单位下三角矩阵
4、, U为Gauss消去法结束后得到的上三角矩 阵. 原方程组Ax?b分解为两个三角形方程组? 3）矩阵LU分解的的存在和唯一性 ?Ly?b?Ux?y . 如果n阶矩阵A的各阶顺序主子式Dk(k?1,2,?,n)均不为零, 则必有单位下三角矩阵L和上三角矩阵U，使得A?LU, 而且L和U是唯一存在的 4）Gauss列主元消去法 矩阵每一列主对角元以下（含主对角元）的元素中, 绝对值最大的数称为列主元. 为避免小主元作除数、或0作分母，在消元过程中，每一步都按列选主元的Guass消去法称为Gauss列主元消去法由于选取列主元使得每一个行乘子均为模不超过1的数，因此它避免了出现大的行乘子而引起的有效
5、数字的损失. 5）带列主元的LU分解 Gauss列主元消去法对应的矩阵形式即为带列主元的LU分解,选主元的过程即为矩阵的行置换. 因此, 对任意n阶矩阵A，均存在置换矩阵P、单位下三角矩阵L和上三角矩阵U，使得PA?LU由于选列主元的方式不唯一, 因此置换矩阵P也是不唯一的. 原方程组 ?Ly?Pb Ax?b两边同时乘以矩阵P得到PAx?Pb, 再分解为两个三角形方程组?. Ux?y? 5）平方根法(对称矩阵的Cholesky分解) 对任意n阶对称正定矩阵A，均存在下三角矩阵L使A?LLT，称其为对称正定矩阵A 的Cholesky分解. 进一步地, 如果规定L的对角元为正数，则L是唯一确定的原
6、方程 ?Ly?b Ax?b组分解为两个三角形方程组?T. Lx?y? 利用矩阵乘法规则和L的下三角结构可得 1 ljj ? ?ajj? j?1 ?l k?1 2jk ?2 ?, lij?aij? j?1 ?l k?1 ik ljk ? ?/ljj, i=j+1, j+2,n, j=1,2,n. ? ajj，k=1,2,j因此在分解 计算次序为l11,l21,?,ln1,l22,l32,?,ln2,?,lnn由于ljk? 过程中L的元素的数量级不会增长，故平方根法通常是数值稳定的，不必选主元 6）求解三对角矩阵的追赶法 ?b1 ?a2 对于三对角矩阵A? ? c1b2? c2?an?1 ?bn?
7、1an ? , 它的LU分解可以得到两个只有两条对?cn?1? ?bn? 角元素非零的三角形矩阵 ?1?l2 L? ? 1l3 ? 1ln ?,?1?u1?U? ? d1u2 d2? ?un?1 ?. ?dn?1? ?un? ?di?ci,i?1,2,?,n?1? ?u1?b1 其中? ?li?ai/ui?1,i?2,3,?,n?ui?bi?lici?1,i?2,3,?,n? 计算次序是u1?l2?u2?l3?u3?ln?un. 原方程组Ax?b分解为两个三角形方程组? ?Ly?b?Ux?y, . 计算公式为 y1?b1yi?bi?liyi?1,i?2,3,?,n, ,xi?(yi?cixi?
8、1)/ui,i?n?1,n?2,?,1. xn?yn/un 该计算公式称为求解三对角形方程组的追赶法当A严格对角占优时，方程组Ax?b可用追赶法求解, 解存在唯一且数值稳定 7）矩阵的条件数 设A为非奇异矩阵，?为矩阵的算子范数，称cond(A)?AA?1为矩阵A的条件数矩阵的条件数是线性方程组Ax?b, 当A或b的元素发生微小变化，引起方程组解的变化的定量描述, 因此是刻画矩阵和方程组性态的量. 条件数越大, 矩阵和方程组越为病态, 反之越小为良态.常用的矩阵条件数为 -条件数: cond?(A)?A1-条件数: cond1(A)?A 1? A ?1 ?1 ? ， A 1 ， 2-条件数:
9、cond2(A)?A 2 A ?1 2 ? ?max(AA)?min(AA) H H 矩阵的条件数具有如下的性质： (1) cond(A)?1; (2) cond(A)?cond(A); (3) cond(?A)?cond(A)，?0，?R; (4) 如果U为正交矩阵，则cond2(U)?1，cond2(UA)?cond2(AU)?cond2(A). ?1 一般情况下，系数矩阵和右端项的扰动对解的影响为 定理2.5 设Ax?b，A为非奇异矩阵，b为非零向量且A和b均有扰动若A的扰动A非常小,使得A?1A?1，则 xx cond(A)1?cond(A) AA bb ? AA (?). 关于近似解
10、的余量与它的相对误差间的关系有 x的事后估计定理2.6 设Ax?b，A为非奇异矩阵，b为非零向量，则方程组近似解 式为 1cond(A) b?Axb ? x?xx ?cond(A) b?Axb . x的余量，简称余量。 其中称b?Ax为近似解 8）矩阵的QR分解 利用正交变换保条件数的性质, 将满秩矩阵化为主对角元都大于零的上三角矩阵, 保持矩阵条件数不变. 设A是n阶可逆实矩阵, 则存在正交阵Q和对角元都大于零的上三角阵R，使得 A?QR, 称其为矩阵A的QR分解, 并且cond2(A)?cond2(R). 为实现矩阵一般的QR分解，我们引入Householder矩阵H()?I? ?R,?0
11、. 该矩阵具有如下性质： n 2 ? ? , 其中 （1） 特征值为：?(H(?)?1? 2 ? T ?(?) 即，1? T 2 ? T ?1，1,?,1； ? n?1个 T （2） H()?H(), 即H阵为对称阵； ? （3） H()H()?In，即H阵为正交阵； ? （4） 如果H()x?y，则y 2 ?x2 (不变长度，镜面反射)； ?n （5） 设x?(x1,x2,?,xn)?R且x?0，取?x?x2e1，则 ? （6） H()x?H(x?x2e1)x? ? x ?0? ?x2e1. ?0? 2 提示：Householder变换并不是直接变换n阶矩阵A, 而是通过重复变换矩阵的下三角
12、部分 的列向量得到上三角矩阵, 因此, 每次变换的Householder矩阵H(1),H(2),?,H(n-1)在逐渐降阶, 然后将它们分别“嵌入”n阶单位矩阵得到相应的 n阶正交阵Q1,Q2,?,Qn-1, 最后得到正交阵Q?Q1,Q2,?,Qn-1.具体变换过程见例子. (二) 特殊矩阵的特征系统 特征系统即为矩阵的特征值和特征向量, 本节主要介绍与其计算相关的Schur分解. 矩阵变换的思想主要为两点: 一是三角矩阵的主对角元素即为其所有特征值, 二是矩阵的特征多项式和特征值在相似变换下是不变的. 因此, 理论上获得矩阵特征值的方法就是通过相似变换将其变为一个三角矩阵. Schur A?URUH, 定理: 设A?Cn?n，则存在酉阵U?Cn?n使得 其中R?Cn?n为上三角矩阵 由于实矩阵的特征值可能是复数, 因此通常在复数域中考虑Schur分解. 复数域中相应的矩阵名称及记号为: U的共轭转置: U U为酉阵: 若UHH?UT, 它在实数域即为转置矩阵. HU
