数值分析——误差估计.ppt

1,第五章线性方程组直接解法,误差估计,2,本讲内容,向量范数,矩阵范数,向量范数的定义常见的向量范数向量范数的性质,矩阵范数的定义F-范数与算子范数矩阵范数的性质、算子范数的性质,误差估计,3,向量范数,设函数f:RnR，若f满足,f(x)0，xRn,等号当且仅当x=0时成立f(x)=|f(x)，xRn,Rf(x+y)f(x)+f(y),则称f为Rn上的（向量）范数，通常记为|,方程组的解为一组数，称为解向量，近似解向量与准确解向量之差称为误差向量，为了估计误差向量的大小，以及在迭代法讨论收敛性的需要，首先需引入衡量向量与矩阵大小的度量范数。,4,向量范数,常见的向量范数,无穷范数（最大范数）,2-范数Euclid范数。,1-范数,5,范数性质,范数的性质,(1)连续性,设f是Rn上的任意一个范数，则f关于x的每个分量是连续的,(2)等价性,设|s和|t是Rn上的任意两个范数，则存在常数c1和c2，使得对任意的xRn有,6,范数性质,(3)Cauchy-Schwarz不等式,(4)向量序列的收敛性,7,矩阵范数,设函数f:RnnR，若f满足,f(A)0，ARnn,且f(A)=0A=0f(A)=|f(A)，ARn,Rf(A+B)f(A)+f(B)f(AB)f(A)f(B),则称f为Rnn上的（矩阵）范数，通常记为|,矩阵范数,8,矩阵范数,常见的矩阵范数,(1)F-范数(Frobenious范数),(2)算子范数(从属范数、诱导范数),其中|是Rn上的任意一个范数,9,算子范数,常见的算子范数,无穷范数（行范数）,2-范数（谱范数）,1-范数（列范数）,10,算子范数,例,求矩阵A的各种常用范数,解:,由于,11,特征方程为,12,容易计算,计算较复杂,对矩阵元素的变化比较敏感,不是从属范数,较少使用,性质较好,13,矩阵范数性质,矩阵范数的性质,(1)连续性：设f是Rnn上的任一矩阵范数，则f关于A的每个分量是连续的,(2)等价性：设|s和|t是Rnn上的任意两个矩阵范数，则存在常数c1和c2，使得对任意的ARnn有,14,定理：（相容性条件）设|是Rn上的任一向量范数，其对应的算子范数也记为|，则有,算子范数性质,算子范数的性质,定理：设|是任一算子范数，则,15,算子范数性质,定理：设|是任一算子范数，若|B|1，则IB非奇异，且,定理：,：(特征值上界),设,则,即A的谱半径不超过A的任何一种算子范数.,16,定理：设,则的充要条件是B的谱半径,17,病态矩阵,考虑线性方程组Ax=b，如果A或b的微小变化会导致解的巨大变化，则称此线性方程组是病态的，并称矩阵A是病态的，反之则是良态的。,病态矩阵,例：,18,定理：考虑线性方程组Ax=b，设A是精确的，b有微小的变化b，此时的解为x+x，则,病态矩阵,19,设方程组AX=b+b的解为,即,-得,即,于是有,另一方面，由得,且,故,由与有,20,定理：考虑线性方程组Ax=b，设b是精确的，A有微小的变化A，此时的解为x+x，则,当A充分小时，不等式右端约为,病态矩阵,21,分析表明，数反映了方程组AX=b的解对初始数据A，b扰动的灵敏度，可用来刻画方程组的病态程度。,矩阵的条件数,定义：设A非奇异，则称为A的条件数。,矩阵条件数,22,条件数与范数有关，常用的有无穷范数和2-范数,Cond(A)2称为谱条件数，当A对称时有,矩阵条件数,23,条件数性质,条件数的性质,Cond(A)1Cond(A)=Cond(A),其中为任意非零实数若R是正交矩阵，则Cond(R)2=1若R是正交矩阵，则对任意非奇异矩阵A，有Cond(AR)2=Cond(RA)2=Cond(A)2,24,举例,例：计算Cond(Hk)其中H为Hilbert矩阵,解：,k=1时，Cond(H1)=1,k=2时，,Cond(H2)=27,k=3时，,Cond(H3)=748,Cond(H4)=28375,Cond(H10)=3.51013,25,fori=3:10h=hilb(i);condA(i)=cond(h,2);%cond(h,inf)enddisp(ncond);fori=3:10s=sprintf(%d%f,i,condA(i);disp(s);end,运行后得到如下结果:ncond3524.056778415513.7387395476607.250242614951058.6410057475367356.370393815257575270.7723649493153986466.2709401016025391750078.617000,华长生制作,26,简记为,方程组与(6.8)的精确解分别为,华长生制作,27,这就是说与相对误差不超过，而引起解的相对误差超过.,28,利用定义判断一个方程组是否病态，需要计算矩阵的条件数，从而涉及计算逆矩阵，极不方便。,注,用选主元消去法消元中出现小主元；系数行列式的绝对值相对地很小系数矩阵元素间数量级上相差很大且无一定规律；出现了相对地很大的解。,当出现下列情况之一时，方程组很可能病态：,方程组的病态性质，是方程组本身的特性。对于病态方程组，用一般的求解方法不易求得较精确的解，而且病态越严重，求解越困难。,29,迭代改善(Iterativerefinement)：,设Ax=b，其中A为非奇异矩阵，且为病态方程组(但不过分病态).,Step1:近似解,Step2:,Step3:,Step4:,Ifisexactsolution，thenOtherwisegotostep2,经验表明：若A不是非常病态（例如：），则如此迭代可达到机器精度；但若A病态，则此算法也不能改进。,ApproximatesolutionbyGuassianelimination,华长生制作,30,向后误差估计(Backwarderroranalysis),设为方程组Ax=b的近似解，于是可计算的剩余向量，当r很小时，是否为一个较好的近似解呢?,定理：设A为非奇异矩阵，x