1.1三角形方程组和三角分解

第一章线性方程组的直接解法直接法：是指在没有舍入误差的情况下经过有限次运算求得方程组的精确解；Gauss消去法是其中最基本的一种，适用于中小规模线性方程组(n1000)，系数稠密有没有任何特殊结构的线性方程组。迭代法：从一个初始向量出发，按照一定的计算格式，采取逐次逼近的的方法，构造一个向量的无穷序列，其极限时方程组的精确解，有限次运算得不到精确解。§1.1三角形方程组和三角分解1.1.1三角形方程组的解法下三角形方程组的解法考虑下三角形方程组Ly=b(1.1.1)b∈Rn已知,y∈Rn未知,L∈Rn×n已知非奇异的下三角阵11212212,0,1,2,,,iinnnnlllLlinlll则(1.1.1)的分量形式为1111lyb2112222lylyb11iiiiilylyb1122nnnnnnlylylyb1111/ybl2221122()/yblyl11()/iiiijjiijyblyl11()/nnnnjjnnjyblyl这种解方程组(1.1.1)的方法称为前代法。实际计算时bi在算完yi之后就没用了,故将得到的yi存放在bi所用的存储单元内，则上式变为1111/bbl2221122()/bblbl1122,11()/iiiiiiiiibblblblbl1122,11()/nnnnnnnnnbblblblbl第i个式子的计算可先计算分子，算法为forj=1:i-1b(i)=b(i)-L(i,j)*b(j)end故计算上述方程组,可先按循环方式算出来分子,再除以lii，具体步骤如下第一步:b(1)=b(1)/L(1,1)b(2)=b(2)-L(2,1)*b(1)b(3)=b(3)-L(3,1)*b(1)……b(n)=b(n)-L(n,1)*b(1)第二步:b(2)=b(2)/L(2,2)b(3)=b(3)-L(3,2)*b(2)b(4)=b(4)-L(4,2)*b(2)……b(n)=b(n)-L(n,2)*b(2)递推直至第n-1步:b(n-1)=b(n-1)/L(n-1,n-1)b(n)=b(n)-L(n,n-1)*b(n-1)第n步:b(n)=b(n)/L(n,n)写成算法的形式：forj=1:n-1b(j)=b(j)/L(j,j)fori=j+1:nb(i)=b(i)-L(i,j)*b(j)endendb(n)=b(n)/L(n,n)b(j+1:n)=b(j+1:n)-b(j)*L(j+1:n,j)该算法运算量：13521n211(1)(21)22.2nniinniinnn算法1.1.1(解下三角形方程组:前代法)上三角形方程组的解法考虑下三角形方程组Ux=y(1.1.2)y∈Rn已知,x∈Rn未知,U∈Rn×n已知非奇异的上三角阵11121222,0,1,2,,,nniinnuuuuuUuinu该方程组可用回代法求解，即从方程组的最后一个方程出发，依次求出xn,xn-1,···,x1,计算公式为1()/,,1,,1.niiijjiijixyuxuinn类似算法1.1.1可得算法1.1.2(回代法).运算量亦为n2.一般的线性方程组的解法考虑一般的线性方程组Ax=b(1.1.3)A∈Rn×n,b∈Rn已知,x∈Rn未知,如果A能分解为A=LU即一个下三角阵L与一个上三角阵U的乘积,那么方程组(1.1.3)的解x可由以下两步得到(1)用前代法解Ly=b得y；(2)用回代法解Ux=y得x；问题关键：如何将A分解为下三角阵*上三角阵？1.1.2Gauss变换Gauss变换的定义称具有如下形式的初等下三角矩阵Lk=I－lkekT为Gauss变换,其中ek是第k个单位坐标向量,且T1000kknkllkl为Gauss向量，111.11kkknkLll即Gauss变换的性质(1)设x∈Rn,xk≠0,则存在Gauss变换Lk使得Lkx=(x1···xk0···0)T.事实上，T111kkkkknknkxxxxlxxl只需取1111111kkkkknknxxLlxlxx,i=k+1,···,n,xk≠0.iikkxlx写出此时lk=？(2)Gauss变换的逆(I－lkekT)－1=I＋lkekT.事实上，T0,kkelTTTT()().IIIIkkkkkkkklelelele(3)LkA=(I－lkekT)A=A－lk(ekTA).T11110000(),kkkkkknnkknkknAlalalalakkle事实上,rank(lkekTA)=1.将Gauss变换作用于一个矩阵相当于对该矩阵进行秩1修正(外加一个秩为1的修正,例如A+a·e·eT,e是单位向量,e·eT就是秩为1的矩阵).1.1.3三角分解的计算三角分解的定义设A∈Rn×n,A的三角分解是指A=LU,其中L∈Rn×n为下三角矩阵,U∈Rn×n为上三角矩阵，11212212,nnnnlllLlll11121222,nnnnuuuuuUu矩阵的三角分解也称为矩阵的LU分解.使用Gauss变换实现矩阵的LU分解:一个例子例.求的LU分解.1472583610A121311001001Lll100210,30131212131111123,11aallaa解:(1)因为,所以11470360611LA(1.A）23210001001Ll100010,0211)3232(1)22623ala（解:(2)因为,所以(1)221147()036.001LALLA11470360611LA(1.A）使用Gauss变换实现矩阵的LU分解:一般步骤(1)记A(0)=(aij(0))=A=(aij),计算Gauss变换L1使得(1)(0)1ALA(0)(0)(0)11121(0)(0)(0)2121222(0)(0)(0)112111nnnnnnnaaalaaalaaa(0)(0)(1)(0)(0)(0)(0)11111111111(0)(0)11110.iiiiiiiaalaalaaaaa(0)(0)(0)11121(0)(0)(0)(0)(0)(0)2121112221122211(0)(0)(0)(0)(0)(0)1111211211nnnnnnnnnnnaaaalaalaalaalaalaala(0)(0)(0)11121(1)(1)(1)21222(1)(1)(1)12nnnnnnaaaaaaaaa0┇0(0)112:0ina(2)对A(1),计算Gauss变换L2使得(2)(1)2ALA(0)(0)(0)(0)1112131(1)(1)(1)22232(1)(1)(1)3232333(1)(1)(1)2231101010nnnnnnnnaaaaaaalaaalaaa(1)(1)(2)(1)(1)(1)(1)22222222222(1)(1)22220.iiiiiiiaalaalaaaaa(0)(0)(0)(0)1112131(1)(1)(1)22232(1)(1)(1)(1)(1)(1)3232223332233322(1)(1)(1)(1)(1)(1)2222322322000nnnnnnnnnnnnaaaaaaaalaalaalaalaalaala(0)(0)(0)(0)1112131(1)(1)(1)22232(2)(2)(2)32333(2)(2)(2)23000nnnnnnnaaaaaaaaaaaaa0┇0(1)223:0ina(3)假定已求出L1,···,Lk－1,使得(1)(1)(1)1112121(1)22,kkkkkAAALLLAA0其中A11(k－1)是k－1阶上三角阵,(1)(1)(1)22(1)(1).kkkkknkkknknnaaAaa若,则又可计算一个Gauss变换Lk使得LkA(k－1)中的第k列的最后n－k个元素为0.即(1)0kkka()(1)kkkALA(1)(1)1112(1)(1)1(1)(1)1111kkkkkkknkkkknknnnkAAaalaal0(1)(1)1112(1)(1)(1)(1)(1)(1)1111(1)(1)(1)(1)kkkkkkknkkkkkkkkkkkkkkknkkkknknkkknnnkknAAaaalaalaalaala0(1)(1)1112(1)(1)()()11()()kkkkkkknkkkkkkkknknnAAaaaaaa00┇0(1)(1)()(1)(1)(1)(1)(1)(1)0.kkkkkkkikikikikikikkkikkkkkkkkkaalaalaaaaa1:.ikn(4)重复上述步骤n-1次,得到A(n－1)为n阶上三角阵,即Ln－1···L2L1A=A(n－1).记L=(Ln－1···L2L1)－1,U=A(n－1),则得A=LU.(5)下证:上述L是单位下三角阵.证明:111121nLLLLTTT1122()()()kkIIIleleleTTT1122kkIlelele2112111.1nnnnllll21T111211010000000000nnllllleGauss消去法Doolittle分解(6)当Lk作用于A(k-1)后,A(k-1)的元素发生了什么变化？(a)前k行元素不变;(b)第k列第k+1个元素开始往后变为0;(c)其余元素:aij(k)=aij(k-1)–likakj(k-1),(1)(1)1112(1)(1)(1)(1)(1)kkkkkkkknkknknnAAaaAaa0(1)(1)1112(1)(1)()()1()00kkkkkkknkkkkknnAAaaAaa0(1)(1)kikikkkkala其中，i,j=k+1:n.(7)Lk和A(k)的元素怎样存储？(1)(1)1112(1)(1)(1)(1)(1)kkkkkkkknkknknnAAaaAaa0(1)(1)1112(1)(1)()()1()00kkkkkkknkkkkknnAAaaAaa0(a)A(k-1)中的第k+1行至第n行的元素在算出A(k)后不再有用,故可用新算出的A(k)的元素冲掉A(k-1)中对应的元素.(b)A