数值分析向量,矩阵范数,矩阵的条件数.

1、 8向量，矩阵范数，矩阵的条件数、向量、矩阵范数为了讨论线性方程组近似解的误差估计与研究解方程组迭代法的收敛 性，需要在Rn（或Rnn）中引进向量序列（或矩阵序列）极限概念。为此， 这就需要对量空间 Rn（或Rn n矩阵空间）元素的“大小”引进某种度量即向量范数（或矩阵范数）即距离的概念。（一）向量范数 :向量范数是 R3中向量长度概念的推广。Xi定义8 （1） cn =x x= ：xi为复数称为n维复向量空间。Xn= a a = G ）网为复数称为n n复矩阵空间。设x Cn, A Cn n ,称xH = （Xi，Xn）二xT为x的共轭转置，HTA =A称为A共轭转置矩阵。在许多应用中，对向

2、量的范数 （对向量的“大小”的度量）都要求满足正定条件，齐次条件和三角不等式，下面给出向量范数的抽象定义。定义9（向量范数）关于向量x e Rn （或xE Cn）的某个实值非负函数N（x）三|x|，如果满足下述条件（1）正定性 |x=0u n x=0齐次性|a*其中a e R（或a e C ）三角不等式 収+ y|W|x| +|y| Wx, y乏Rn（或乏Cn），称N（x）三|x是Rn上（或Cn） 一个向量范数（或为模）。由三角不等式可推出不等式（4）x|y| x - y下面给出矩阵计算中一些常用向量范数。定义10设X =(为，Xn) E Rn(或X壬CS(1)向量的“ o”范数n/x)三恻辺

3、=max Xin向量的“ 1”范数 N,(x)三I*,=送xiTn向量的“ 2”范数 n2(x)三|卷=(x,x)1/2 = (瓦xi 2)1/2i=1（4）向量的能量范数设A Rn n为对称正定阵xRn Na（x）二xA = （Ax,x）1/2称为向量的能量范数。定理 19| 设Rn（或 xCn），则 N/xhNzgNjx）是 Rn 上（或 Cn）的向量范数。证明只验证三角不等式：对任意 x,y Rn，则| x+y 2勻x2科 心利用哥西不等式：(x, yNIJy 2，则有x y 2 =(x y,x y) =(x, x) 2(x,y)(y, y)2 2X22 y：=(x2 y2)2定理20（

4、范数的等价性）|对任何x, y w Rn则（1）x； x2 - n x|：ML引Ml兰阿X2 X 肿 xnx：xil证只证(1)。记xXjF hL=maxxiN2于是有冈孑2Xjn 0(当 k)k .7其中II .|7为向量的任一范数。证明只对v - :, v = 2证明。显然有lim x(k)k_)：:=x 二= |im Xj(k) -Xj= 0(i , ,n)0(当 k；u n lim x(k) x tin的某个非负实值函数N(A)三|A|，如果满足下述条件：(1)正定性：A 0,且A =0= 是A = 0齐次性：|ctA 叫A,a E R(3)三角不等式：|a + B兰制+|b|则称N(

5、A)是Rn n上的一个 矩阵范数(或模)。由于在许多应用问题中，矩阵和向量是相联系的，现引进一种矩阵的算子范数。它是由向量范数诱导出来的并且这种矩阵范数和向量范数是相容的，即-xRn,A Rn n不等式 Ax 一 A| x 成立。定义14(矩阵的算子范数)设x e Rn,Ae Rn：且设有一种向量范数| X| v相应的定义一个矩阵的非负函数N(A)= Av二 maxx=.Ox.RnAXvXv(最大比值),称N(A)为矩阵A的算子范数AXvXvF面验证三角不等式:Bv 乞 Av B=max xRn x P(A B)Xv定理2彳设lix v是Rn上的向量范数，贝y N(A)三|A|v是R询上一个范

6、数 且满足相容条件：(1) Ax vXv AB J Av BvA,B Rnn)证明由N(A)三|Av定义,可知有”或 Ax J Av XvA Rnn,x Rn)由于(A B)x AXv BxjAvXv BvX(A B)x(A B)XvXv勻 a|v+|b|v，(WxE R% X)故IA + B|v 兰|A|v+|冋v|Ax|車nA “ = max=max 瓦aii1g “1j J称为A的行范数）n定理23 （矩阵范数公式）设x Rn, A Rnn，则网max骨max叨（称为A的列范数）A 2 = max X-=max(ATA)(称为 A 的 “ 2” 范数)X 2其中max （ A A）为A

7、A最大特征值。证明证(1):记 X=(Xi,Xn)T ,|x=max Xi| =tnn4 =max送同| =送|aij (其中1兰io兰n)-jj =inn送 ajXj max送 代唏_ jmaijXjj#于是 IIACmsxEtmaxZ aij =ti j#说明，对任何向量 x=O，则有AxL：X :如果能找到一向量x0且x0 :厂1使那末，定理得证。F面来寻求Xo使比值等于 岂，记Xo =（Xi,X2，,Xn）T且使| Xo| = 1nnn曰是，AxoaXj,aiojXj,anjXj)Tjjj且由(a)式有 Ax。：1,当 aij 色0 由此，应选取X0为：Xj =.-1，当 aij :i

8、 ii d特征值为，i(i =1,1,，n)，则有r 一匕一一厶- 0 且有Ui： 满足 ATA5MV =1,2,n ),4,5)=“考查比值：nX R 且 x0，于是 xaiuii=1nnM2T(/ iui，/ 卫 iUi )_2 (Ax,Ax) (ATAx,x)(x,x)(x,x)n 2 :-ii An 2 :-ii =1说明，对任何非零向量 X Rn，则有Ax1IWL另一方面，取x1则有上心一卫皿U1(U1,U1)故 A 2 = max(A A)定理24 (矩阵范数等价性)设A Rn馮，则设I -B为奇异阵，则曰是,2)由(I -B)(I -B)，-I1 _ 1比勻IA2 兰 JnllA

9、Q.nn定义25（矩阵的谱半径）设Aw R网的特征值为 扎（i =1,，n），称P（A）三max入为A的谱半径。定理25 （特征值界）（1）设A ，则P（A）勻A，其中IA为满足矩阵，向量相容性条件 的矩阵范数。设A Rn n为对称矩阵，则| A 2 =（A）。证明只证（1）。设为A的任一特征值，于是，存在x = 0使Ax二，x且內 MFIM = Ax 兰|A|x|即园 |xi或 p（a）|A定理26 设卄为矩阵的算子范数，且|B| 1,则I B为非奇异矩阵，且有估计（I _B）证明1）反证法。（I - B）x = 0有非零解记为x0，即Bx0二x0B -1，这与假设矛盾。即得(I B)v =

10、1 B(l B)斗从而IN -B）|印1+剛（I订（I -B）*詁可矩阵的条件数、病态方程组直接法的误差原因：1 算法及舍入原因2 方程组本身固有的问题要分析方程组的状态并估计算法的误差（原始数据扰动对解的影响）- 量度：矩阵的条件数【引例】设方程组1 1卜=精确解为x = 2. 占 1.0001 一x2 一 X。a=1 1;1 1.0001;b=2,2;ab对右端项作微小变化（小扰动）：J1irxj ?甘出弘卩1=其中6b =1 1.0001 上2 一2.0001 一0.0001 一a=1 1;1 1.0001;b=2,2.0001;ab显然有，X * x-20150.0011312102二

11、 0.0186【说明】 右端常数项的相对误差 弊兰IlbL0.00012= 0.5 10*12二 0.5常数项的微小误差引起解的相对误差较大，扩大了 10*倍，也就是说，此方程组解对方程组的数据 A,b非常敏感,这样的方程组就是 病态方程组.设线性方程组为Ax=b (1)其中A Rxn,x,b 哎且A非奇异。x* :准确解，S x :解的误差，即、X = X - X (2)S A-A的误差，S b-b的误差。讨论S x与S A, S b的关系(一)b有误差而A无误差情形将带有误差的右端项和带误差的解向量代入方程组，则A(x丄说=b b ( 3)由于Ax*三b，而得到6x = A6b,从而x|另

12、一方面，由,(b = 0)(1)式取范数，有|制兰|A | x或pfnllbll可得【定理27】设A是非奇异矩阵, 差估计式Ax=bz 0,且 A (x + S x) =b+ S b 则有误乞 cond (A)其中cond (A) A | A称为方阵A的条件数。说明：1、解的相对误差是右端项 b的相对误差的cond(A)倍2、如果条件数很大，则解的误差将成倍增长。【定义】 称条件数很大的矩阵为“病态”矩阵；称病态矩阵对应的方程组为病态方程组。反之，则称A为良态矩阵。(二)A及b都有误差的情形【定理28】设在方程组Ax=b中，A及b都有误差，且|A | |pA 1，则有 IIcon d（A）网阳

13、】II All证：带有误差的方程组为（A、A）（x 、x）=b 、b （5）由于Ax三b，因而（A 、A）、x 、Ax* 二、b （ 6）为从（6）式中解出3 x，必须限定（A+ S A） -1存在。从而x = （A、A）（b- x*） （ 7）利用A ；A二A（E A J A），得到(A A) =(E AJ A) JAJ又由定理26知，当“A 1时(E A4 A)4|1(9) 1,-1cond(A)=cond(A ),cond(cA)=cond(A)(c 丰 0,c R)4. 若U为正交矩阵，即 UTU=I，贝U cond(U) 2=1 对非奇异矩阵 A,cond(A) 2=cond(UA)

14、 2=cond(AU) 2（四）病态方程组病态方程组的判可设Ax=b, A Rnxn,且A非奇异当cond（A）1,则Ax=b是病态方程组（坏条件的，A是病态的）当cond（A）相对较小时，则Ax=b是良态方程组（好条件的，A是良态的）【例】在引例方程组中，b有扰动、巾=(0, 0.0001) T，试计算cond(A) g,并说明对解向量x的影响。a=1 1;1 1.0001;b=2;2;no rm_b=no rm(b,i nf);detb=0;0.0001 ;n orm_detb=norm(detb,i nf);err_b=n orm_detb/norm_bcon d_a=c on d(a,

15、i nf)err_x=err_b*c ond_a；广叫A) 4.0004 104 牆 2 200%【例】希尔伯特矩阵的条件数：con d(hilb(2),co nd(hilb(3),co nd(hilb(5),co nd(hilb(8)a=hilb(3),b=o nes(3,1);ab a =1.0000 0.5000 0.3333;0.5000 0.33330.2500;0.3333 0.25000.2000+0.000001;b=o nes(3,1);ab【注】(1)由矩阵条件数性质可知，正交矩阵的线性方程组Ax二b是好条件的；(2) 条件数性质4指出，正交变换保持条件数Cond (A)不

16、变，这说明在很多方法中使用正交矩阵约化矩阵的合理性。设有方程组Ax=b，其中A Rnn为非奇异，x为精确解，又设X为计算解。一般，计算剩余向量r二b - Ax，用r大小来检验计算解的精度，是否r很小，x就是Ax二b 个较好的近似解呢?【定理29】|(事后误差估计)(1)设A为非奇异矩阵,x是精确解，即 Ax二b = 0。设x是方程组一个近似解，r二bAx，则近似解x的相对误差有估 计式|r|xnd(A)b证明 由 x-x = Ab-x = A，(b - Ax)二 Ar所以|x _x| W| A| |r| (12)另一方面，由Ax =b，有x即AA(13)由(12)及(13)式，则X -X|x|

17、说明近似解x精度(误差界)不仅依赖于剩余 的条件数，当A是病态时，即使有很小的剩余, 的近似解。r “大小”，而且依赖于 A 也不能保证 x是高精度三、关于病态方程组的解法Ax =b , A- Rn n非奇异矩(一)判断Ax=b是病态方程组(1) 当A的行列式相对来说很小，或A某些行(或列)近似线性相关，方程组Ax=b可能病态(2) 如果用选主元消去法求解Ax二b,在A约化中出现小主元，方程组Ax=b可能病态(3) 当系数矩阵A元素数量级相差很大，并且无一定规则时，方程组Ax=b可能病态 估计条件数由于Co nd (A)二二A ：一，所以发现Ax =b病态的可靠方法是计算 A的条件数，若直接计

18、算AJ再计算| A，沪,那末求A，大约需要n3 2n2次乘法运算,为求解(用直接法)Ax = b计算量的3倍，代价太高一个矩阵条件数的估计方法：由于max匚 J y 770:二 max w：:(令 A=y 二 w ,由解 Aw = y 求 y-0 y：w)因此 |AL-l/lyl选择向量y Rn且求解Aw =y使产生大的解w.于是Con d（AQ|A*A|AW/yb【注】方法成功的关键在于怎样使比值 |wj/|yb接近它的极大值|a|泸（二）病态方程组的解法对于病态方程组 Ax二b,当我们用一般方法求解时，仅由舍入而产生的误差也会使我们算不出比较满意的解，此时可采用下述方法求解1采用高精度的算

19、术运算例如,采用双倍字长进行运算，或用双字长求内积等，以此改善和减轻 矩阵病态的影响，其缺点是计算时间将大为增加 2采用预处理方法求解Ax二b =求解：寻求非异矩阵P，Q使1PAQ（Q x） = Pb或Ax = b其中A = PAQ，X = Qx，b = Pb且改善A的条件数，Con d（PAQ） :Co nd （A）于是，可用数值稳定方法求解 Ax = b，再求x = Qx，当A为对称正定阵时一般选择P，Q为对角阵或三角矩阵3平衡方法当系数矩阵A元素数量级差别很大，威尔金森提出采用行均衡方法，这 时矩阵A条件数可能得到改善行（或列）均衡：就是解方程组Ax = b之前首先将a的行（或列）大体 均衡一下，即对Ax = b每一行（或每一列）乘以适当的数，使所有行（列）按 照某种范数大体上有相同的长度 设Ax = b，其中A Rn n为非奇异阵.计算令 D4 二diag（1/3,1/S2，1/&）1 1 于是求解Ax = b =求解D Ax=D b或Ax = b.这时A = DJA条件数可能得到改善，再用列主元消去法或部分选主元三角分解法求解 Ax二b .设有