5向量和矩阵的范数2

1、1 5 向量和矩阵的范数为了研究线性方程组近似解的误差估计和迭代法解线性方程组的收敛性，需要对向量和矩阵引进范数的概念。一、向量的范数1、向量范数的概念定义 1 如果向量空间nr上的某个非负实值函数xxn)(满足条件：（ 1） 正 定 性 ：0 x， 当 且 仅 当0 x时0 x；2 （2）齐次性 ：xccx，c为任意实数；（3）三角不等式 ：yxyx。则称为nr上的一个向量范数。由（3）可得yxyx。n维向量空间, 2, 1,),(|21nirxxxxxxrinn上常用的三种范数：3 inixx1max； （范数）niixx11； （1范数）niixx122； （2范数）进一步，可定义pni

2、pipxx11。 （p范数）4 例计算向量tx)3 , 2, 1(的各种范数。解61x，3x，142x。2、迭代法收敛的概念定义 2 设nknkkrxxx),()()(1)(，nnrxxx),(*1*，若),2, 1(,lim*)(nixxikik，则称点列)(kx收敛于*x，并记作5 *)(limxxkk。由定义可知：*)(limxxkk0lim*)(xxkk，*)(limxxkk0lim1*)(xxkk，*)(limxxkk0lim2*)(xxkk。3、向量范数的等价性定理设sx和tx是nr上向量的任意两种范数，则存在常数012cc，使得对一切nrx，有6 stsxcxxc21。特别，对于

3、上述常用的三种范数，有12121,1xxn xxxn xxxxn。二、矩阵范数定义 3 如果矩阵空间nnr上的某个非负实值函数aan)(满足以下条件：7 （1）正定性：0a，且00aa；（2）齐次性：acca，c为任意实数；（3）三角不等式：baba；则称)(an为nnr上的一个矩阵范数。由（3）可得baba。在研究方程组解的误差时，常需要涉及到矩阵乘积的范数以及矩阵与向量乘积的范数，8 为了研究的方便，我们要求它们之间满足xaax，baab，其中前一个条件称为矩阵范数与向量范数的相容性 ，后一个条件称为 矩阵范数的可乘性 。下面用向量范数定义一类矩阵范数，这种矩阵范数满足上述两个条件。定理

4、1 设nnnrarx,，给定一种向量范数vx，相应地定义一个矩阵的非负函数vxvvxvaxxaxav10maxmax，9 则va是一个矩阵范数，称之为向量范数vx的诱导范数（算子范数） 。证明只要验证矩阵范数定义的三个条件即可。（1）对于任意的nrx，1vx，由于0ax，故0max1vxvaxav。进一步，1max00,10,10vvvxnvvnvaaxaxxrxaxxrxa（2）10 111max ()max()maxvvvvvxvxvxvaa xaxaxa（3）11max ()maxvvvvxvxabab xaxbx111maxmaxmaxvvvvvxvvxxvvaxbxaxbxab。11

5、 根据矩阵范数的定义，va是一个矩阵范数。性质 1设a是由向量范数x诱导的矩阵范数，则（1）xaax；（2）baab；（3）ia时，1i。证明（1）由xaxax 0max12 当0 x时，axaxxaax。进一步，当0 x时，xaax显然成立。（2）xbxaxxababxx)(max)(max00baxbxaxbxaxx00maxmax。（3）显然。13 有的矩阵范数不是向量的诱导范数。例如：niijfaa12可以验证，它是一个矩阵范数 （叫做 frobenius范数） ，但不是任何向量范数的诱导范数。定理 2 对于诱导矩阵范数， 如果1b，则bi为非奇异矩阵，且bbi111。证明如果bi为奇

6、异矩阵，则方程组0)(xbi有 非 零 解 ， 设 为0 x， 于 是14 00bxx，从而00000 xxbbxbxx，这是矛盾。又111)()()(bibbibibii所以11)()(bibibi，两边取范数，得1111()()()1()ibib ibib ibbib，15 移项，得1)(11bib，即有bbi11)(1。定理 3由向量范数21,xxx诱导的矩阵范数分别为（1）njijniaa11max，行范数，（2）niijniaa111max，列范数，16 （3）)(max2aaat，谱范数，其中)(maxaat表示aat的最大特征值。证明只要证明（ 1）和（3） ， （2）的证明与（

7、1）类似。（1）设0),(21tnxxxx，不妨设0a，则111111maxmaxmaxnijjinjnijjinjnijinjaxa xaxxa，因此17 njijnixaxaxa110maxmax下面证明存在nrx)0(，使njijniaxax11)0()0(max。不 妨 设njjinjijniaa1110max， 在)0(x中 ， 对nj,2, 1，取010, 100)0(jijijaax如果，如果，则1max)0(1)0(inixx，18 因此(0)(0)(0)11maxnijji njaxa xx0111maxnni jiji njjaa。（3）对于一切0 x，0,22axaxax

8、axaxtt，从而aat的特征值都是非负实数，设为021n。由于aat为对称矩阵， 故存在 标准正交 的特征向量组nuuu,21，使得), 2, 1()(niuuaaiiit19 对于任意的非零向量nrx，设niiiuyx1，则2221222002212111021maxmaxmaxniiinxyiiniinyiiyaxaxyyy取1ux，则20 22111221221122auuuu因此122a，即有)(max2aaat。定 义设nnra的 特 征 值 为),2, 1(nii，称inia1max)(为矩阵a的谱半径。21 定理（特征值的上界） 设nnra，为nnr上的任意一种诱导范数，则aa

9、)(。证明对于a的一个特征值，设x为其对应的特征向量，则xax因此xaaxx。注意到0 x，得a。6 误差分析22 考虑线性方程组bax（6.1 ）其中nnra为非奇异矩阵，0b。本节不考虑求解过程中的舍入误差，仅考虑当线性方程组的系数矩阵或右端项有舍入误差时，这些误差对方程组解的影响。一、输入数据的误差对解的影响设a有误差a，b有误差b。定理设bax，a为非奇异矩阵，0b，且a和b分别有扰动a和b。若a的扰动a很小，使11aa，则有23 )(111aabbaaaaaaxx。证明扰动后的方程组为bbxxaa)(将bax代入上式，整理后有)()()(111xaaxaabax将上式两端取范数，应用

10、向量范数的三角不等式及矩阵和向量范数的相容性，有xaaxaabax111，整理后，得)()1(11xabaxaa。24 由于a足够小，使得11aa，所以)(111xabaaax。利用bax1，得)(111aabbaaaaaaxx。推论设bax，a为非奇异矩阵，25 0b，则有（1）当a是精确的而b有误差b时，bbaaxx1。（2）当b是精确的而a有误差a，且11aa时，aaaaaaaaxx111。26 上述推论中结论（1）表明：最坏的情况下，b的相对误差可能在解中被放大aa1倍；结论（2）表明：虽然11aaaa，但是，当aa1较大时， 可能出现1aaaa接近 1，此时就可能导致解的相对误差较大

11、。总之，量aa1可以刻划方程组的解对原始数据误差的敏感程度，通常用它来描述方程组是否病态。27 二、矩阵的条件数与病态方程组1矩阵的条件数定义设a为非奇异矩阵，称1cond()vvvaaa为矩阵a的v范数下的条件数。当aa1很大时：（1）即使不考虑计算过程的舍入误差，仅输入误差就使求解结果有较大的误差。（2）很多求解方程组的算法是数值不稳定的。譬如，即使采用选主元的高斯消去法，也28 不能有效求解病态方程组。因此，当aa1较大时，称方程组是病态的，并称相应的系数矩阵a是病态矩阵。应该注意的是：所谓矩阵是病态的，是针对解线性方程组（包括求逆矩阵）而言的。譬如对于矩阵的加法运算，aa1的大小对结果

12、的精确性就没有直接影响。通常使用的条件数有：29 （1）1cond( )aaa（2）a的谱条件数1max222min()cond()()tta aaaaa a，这是因为1111maxmax2minmin()()11()()ttttaaaaaaaa a最后一式成立是因为当a为非奇异矩阵时，ta a与taa相似，即存在可逆矩阵1a，1()ttaaaaa a而相似矩阵有相同的特征值。30 特 别 ， 当a为 对 称 矩 阵 时 ，12cond( )na， 其中n,1分别为a的绝对值最大和最小特征值。例如： hilbert矩阵),2, 1,(11njijiaij1211111131211211nnnn

13、nhn3cond()784a76cond()2.9 10a31 87cond()9.85 10a，可见，n越大，nh病态越严重。令一个典型的病态矩阵是pascal 矩阵：), 2,(),2, 1(5.01, 111njiaaaaniaajijijiijii2病态方程组的判断虽然矩阵的条件数可以定量反映矩阵是否病态，但逆矩阵的范数很难求得，导致求条件32 数实际上难以实现。通常依照经验判断矩阵是否病态，出现以下情况，病态的可能性较大：（1）用列主元消去法时，出现绝对值很小的主元；（2）系数矩阵行列式的绝对值很小或很大；（3）系数矩阵元素的量级差别很大。（4）系数矩阵的行列式 “几乎”线性相关。对

14、矩阵性态的深入了解，可参考文献：郑孝勇等，病态线性方程组的判定方法，33 数学的实践与认识， 2006（36） （9） ：166-169。 3病态方程组解法简介病态线性方程组的求解是一个十分困难的问题，理论上讲最可靠的方法是扩充计算机的字长，但无论如何扩充，计算机的字长总是有限的。因此，需要研究克服方程组病态的有效算法。方法一：对方程组作预处理，改善系数矩阵的条件数。预处理方法的基本思路是：取非奇异矩阵qp,（ 特 别 ，q最 好 是 正 定 矩 阵 ） ， 使cond()cond()paqa， 然 后 将 求 解 方 程 组34 bax转化为求解pbpaqy， 得到y后，令qyx*作为原方程

15、组的解。算法的具体实现可参见：1赵金熙，一个解高度病态问题的高精度算法的数值结果。高等学校计算数学学报， 1987 （1） ：59-64。2 高等学校计算数学学报， 1988 （3） ：250-262。3 高等学校计算数学学报， 2002（2） ：155-162。35 方法二：转化为最优化问题)()(21minbaxbaxtrxn或)()(21)(minbaxxaaxxttttrxn算法的实现思路是：将求解方程组bax转化为求最优化问题的稳定点0baaxatt这实际上相当于在原方程组的两边同时左乘可逆矩阵ta。 记babaaatt,， 其中a为正定矩阵，则问题变为求x，使bxa。算法：36 第

16、 1 步：确定初始搜索区域nkkkbad1)0()0()0(,第 2 步：计算tnnbabax2,2)0()0()0(1)0(1)0(第 3 步：计算并判断（1）baxx)()0(（2）如果baxx)()0(，结束，输出解)0(x；否则对于nk,2, 1，执行如果0()0(kx，则令)0()0()0()0(:,:kkkkxbaa，37 如果0()0(kx，则令)0()0()0()0(:,:kkkkabxa，如果0()0(kx，则令)0()0()0()0(:,:kkkkxbxa。转第 2 步。上述算法可参见：史文谱等，求解线性方程组的一种新方法，计算力学学报，2003（20）（6） ：715-7

17、20。方法三：转化为常微分方程问题算法可参见：吴新元，解病态线性方程组38 的常微分方程方法。南京大学学报，1993（29）（2） ：195-199。三、解的误差估计与解的修正线性方程组解的误差是由两方面原因产生的：一是输入数据的误差，二是计算过程中的舍入误差。下面的定理给出了解的误差的一种度量。定理设bax，a非奇异，0b，x为方程组的精确解，x为求得的近似解，其剩余向量为xabr，则有误差估计braxxx)(cond。39 证 明由bax， 得xab， 即bax1，rxabxaaxxxa)(raxx1raxx1所以brabraaxxx)(cond1。从上述误差估计式可以看出，当系数矩阵的条件数很大时，即使残差向量r的范数很小，40 也不能保证解的相对误差很小。当系数矩阵的条件数不太大时，用下面的方法可以提高解的精度。 （金一庆）设1x是方程组bax的近似解，1r是剩余向量，11axbr，解方程组，1rad得解1d。 取112dxx， 如果1d是1