3.5向量与矩阵的范数.ppt

1/35计算方法计算方法计算方法计算方法三三三三上节课回顾上节课回顾直接法直接法是通过有限步运算后得到线性方程组的解是通过有限步运算后得到线性方程组的解.包含包含:高斯消元法高斯消元法(列主元消去法列主元消去法)、三角分解法、三角分解法、追赶法追赶法.解线性方程组的所有直接的方法比较适用于中小解线性方程组的所有直接的方法比较适用于中小型方程组型方程组.对高阶方程组对高阶方程组,即使系数矩阵是稀疏的即使系数矩阵是稀疏的,但在但在计算中很难保持稀疏性计算中很难保持稀疏性,因而有存储量大，程序复杂等因而有存储量大，程序复杂等不足，这些不足之处可用迭代法来弥补解决不足，这些不足之处可用迭代法来弥补解决.线性方程组线性方程组 AX=bLY=bUX=YA=LU列主元素法列主元素法的精度虽稍低些的精度虽稍低些,但但计算简单计算简单,且具有良好且具有良好的数值稳定性。的数值稳定性。三角分解法三角分解法2/35计算方法计算方法计算方法计算方法三三三三 迭代过程中经常要遇到向量范数，矩阵范数以迭代过程中经常要遇到向量范数，矩阵范数以及序列极限的概念。为此，下面先介绍这方面的知及序列极限的概念。为此，下面先介绍这方面的知识和有关概念。识和有关概念。3.5 向量与矩阵的范数向量与矩阵的范数一、.向量范数向量范数：对对n维实空间维实空间Rn中中任一向量任一向量X，按一定规则有一确按一定规则有一确定的实数与其相对应，该实数记为定的实数与其相对应，该实数记为|X|，若若|X|满足下满足下面三个性质：面三个性质：(1)(非负性非负性)|X|0，|X|=0当且仅当当且仅当X=0。(2)(齐次性齐次性)对任意实数对任意实数 ，|X|=|X|。(3)(三角不等式三角不等式)对任意向量对任意向量Y Rn，|X+Y|X|+|Y|则称该实数则称该实数|X|为向量为向量X的范数的范数3/35计算方法计算方法计算方法计算方法三三三三几种常用的向量范数几种常用的向量范数：设：设X=(x1,x2,.,xn)T（1）向量的）向量的1范数：范数：（2）向量的）向量的2范数：范数：（3）向量的）向量的范数：范数：（4）向量的）向量的p范数：范数：(1p)4/35计算方法计算方法计算方法计算方法三三三三例例：设：设 x=(1 ,-4,0,2)T 求它的向量范数求它的向量范数=7=4注：前三种范数都是注：前三种范数都是p范数的特殊情况。其中范数的特殊情况。其中5/35计算方法计算方法计算方法计算方法三三三三向量范数的连续性向量范数的连续性:定理定理3.3 设设f(X)=|X|为为Rn上的任一向量范数上的任一向量范数,则则f(X)为为X的分量的分量x1,x2,xn的连续函数的连续函数.定理定理3.4 若若|X|p与与|X|q为为Rn上上任意两种范数任意两种范数，则则存存在在C1，C20，使得，使得对对任意任意XRn，都有：，都有：C1|X|p|X|q C2|X|p（证明略）（证明略）注：同注：同样样有下列有下列结论结论：存在：存在C3,C40 使得：使得：C3|X|q|X|p C4|X|q向量范数的等价性向量范数的等价性注：上述性质，称为向量范数的注：上述性质，称为向量范数的等价性等价性。也就是说，。也就是说，Rn上任意上任意两种范数都是等价的。两种范数都是等价的。在讨论向量序列的收敛性时要用到向量在讨论向量序列的收敛性时要用到向量范数的等价性。范数的等价性。6/35计算方法计算方法计算方法计算方法三三三三向量序列的收敛问题向量序列的收敛问题定义定义：假定给定了：假定给定了Rn空间中的向量序列空间中的向量序列X(1),X(2),.,X(k),.，简记为，简记为X(k)，其中，其中X(k)=(x1(k),x2(k),.,xn(k)T，若，若X(k)的每一个分量的每一个分量xi(k)都存在极限都存在极限xi，即，即则称向量则称向量X=(x1，x2，.，xn)T为向量序列为向量序列X(k)的极限，或者说向量序列的极限，或者说向量序列X(k)收敛收敛于向量于向量X，记为，记为7/35计算方法计算方法计算方法计算方法三三三三x1x2xn(k)(k)8/35计算方法计算方法计算方法计算方法三三三三例例：设：设解解:显然，当显然，当k时，时，9/35计算方法计算方法计算方法计算方法三三三三注：显然有：注：显然有：定理定理3.5 在空间在空间Rn中，向量序列中，向量序列X(k)收敛于向量收敛于向量X的充要条件是对的充要条件是对X的任意范数的任意范数|，有：，有：10/35计算方法计算方法计算方法计算方法三三三三定理定理3.5 在空间在空间Rn中，向量序列中，向量序列X(k)收敛于向收敛于向量量X的充要条件是对的充要条件是对X的任意范数的任意范数|，有：，有：二、二、矩阵范数矩阵范数：设：设A是是n n 阶矩阵，阶矩阵，ARnnXRn，|X|为为Rn中的某范数，称中的某范数，称为矩阵为矩阵A的的从属于从属于该该向量范数向量范数的的范数范数，或称，或称为矩阵为矩阵A的的算子算子，记为，记为|A|。|A|=11/35计算方法计算方法计算方法计算方法三三三三几种常用的矩阵范数几种常用的矩阵范数常用的矩阵范数有常用的矩阵范数有A的的1范数、范数、A的的2范数、范数、A的的范数，可以证明下列定理范数，可以证明下列定理:定理定理3.6 设设ARnn，XRn，则，则(又称为又称为A的的列范数列范数)(为为ATA的特的特征值中绝对征值中绝对值最大者值最大者)(又称为又称为A的的行范数行范数)列元素绝对值之列元素绝对值之和的最大值和的最大值行元素绝行元素绝对值之和对值之和的最大值的最大值12/35计算方法计算方法计算方法计算方法三三三三例：设例：设A=求求A的各种范数的各种范数解：解：|A|1=6，|A|=7|E-AA|=02-30+4=0弗罗贝尼乌斯弗罗贝尼乌斯 (Frobenius)范数范数 简称简称F范数范数注：注：13/35计算方法计算方法计算方法计算方法三三三三弗罗贝尼乌斯弗罗贝尼乌斯(Frobenius)范数简称范数简称F范数范数几种常用的矩阵范数：几种常用的矩阵范数：14/35计算方法计算方法计算方法计算方法三三三三Matlab中计算矩阵的范数的命令中计算矩阵的范数的命令(函数函数)：(1)n=norm(A)矩阵矩阵A的谱范数的谱范数(2范数范数),=AA的最大特征值的算术根的最大特征值的算术根.(2)n=norm(A,1)矩阵矩阵A的列范数（的列范数（1-范数）范数）等等 于于A的最大列之和的最大列之和.(3)n=norm(A,inf)矩阵矩阵A的行范数的行范数(无穷范数无穷范数)等于等于A的最大行之和的最大行之和.(4)n=norm(A,fro)矩阵矩阵A的的Frobenius范数范数.15/35计算方法计算方法计算方法计算方法三三三三例例6.计算矩阵计算矩阵A的各种范数的各种范数n1=norm(A,1),n2=norm(A),n3=norm(A,inf)，n4=norm(A,fro)解：解：A=1,2,3,4;2,3,4,1;3,4,1,2;4,1,2,9;n1=16，n2=12.4884，n3=16，n4=13.856416/35计算方法计算方法计算方法计算方法三三三三矩阵范数的性质矩阵范数的性质：（1）对任意）对任意ARnn,有有|A|0，当且仅当，当且仅当A=0时，时，|A|=0.（2）|A|=|A|（为任意实数）为任意实数）（3）对于任意）对于任意A、B Rnn，恒有，恒有|A+B|A|+|B|.（4）对于矩阵对于矩阵A Rnn，X Rn，恒有：恒有：|AX|A|X|.（5）对于任意对于任意A、B Rnn 恒有恒有|AB|A|B|17/35计算方法计算方法计算方法计算方法三三三三谱半径：谱半径：设设 n n 阶矩阵阶矩阵A的特征值为的特征值为 i(i=1,2,3n),则则称称 (A)=MAX|i|为矩阵为矩阵A的谱半径的谱半径.1 i n例例5.求矩阵求矩阵 的的谱半径谱半径 谱半径谱半径=A的特征值中绝对值的最大者的特征值中绝对值的最大者解解:18/35计算方法计算方法计算方法计算方法三三三三定理定理3.7设设A为任意为任意n阶方阵，则对任意矩阵范阶方阵，则对任意矩阵范数数|A|，有：，有：(A)|A|矩阵范数与谱半径之间的关系为矩阵范数与谱半径之间的关系为:(A)|A|证证:设设为为A的任意一个特征值的任意一个特征值,X为对应的特征向量为对应的特征向量A X=X两边取范数两边取范数,得得:|A X|=|X|=|X|X|=|X|=|A X|A|X|由由X 0,所以所以|X|0,故有故有:|A|所以特征值的最大值所以特征值的最大值|A|，即，即(A)|A|19/35计算方法计算方法计算方法计算方法三三三三定理定理3.7 设设A为任意为任意n阶方阵，则对任意阶方阵，则对任意矩阵范数矩阵范数|A|，有：，有：(A)|A|定理定理3.8 设设A为为n阶阶对称方阵对称方阵，则，则有有:|A|2=(A)ATA=A220/35计算方法计算方法计算方法计算方法三三三三矩阵序列的收敛性矩阵序列的收敛性定义定义 设设Rnn中有矩阵序列中有矩阵序列A(k)|A(k)=(aij(k)，若若则称矩阵序列则称矩阵序列A(k)收敛于矩阵收敛于矩阵A=(aij)，记为，记为a11a21a12a22如如21/35计算方法计算方法计算方法计算方法三三三三a11a21a12a22则有则有22/35计算方法计算方法计算方法计算方法三三三三关于矩阵序列收敛的性质：关于矩阵序列收敛的性质：定义定义 设设ARnn中，称中，称|A-B|为为A与与B之间的之间的距离距离,其中其中|A|为为Rnn上的某种范数。上的某种范数。定理定理3.10 设设A(0)，A(1)，.，A(k)，.为为Rnn上的上的一个一个矩阵序列，矩阵序列矩阵序列，矩阵序列A(k)收敛于矩阵收敛于矩阵A的充的充要条件是存在要条件是存在A的某种范数的某种范数|A|，使得：，使得：即即定理定理3.11 任意任意ARnn，有，有(证明略证明略)23/35计算方法计算方法计算方法计算方法三三三三三、方程组的性态和条件数三、方程组的性态和条件数线性方程组解对系数的敏感性线性方程组解对系数的敏感性（误差分析）（误差分析）这种解依赖于方程组系数的误差这种解依赖于方程组系数的误差 A及及 b的问的问题，称为题，称为线性方程组解对系数的敏感性。线性方程组解对系数的敏感性。对于线性方程组对于线性方程组A X=b来说，由于观测或计算等原来说，由于观测或计算等原因，线性方程组两端的系数因，线性方程组两端的系数A和和b都带有误差都带有误差 A和和 b，这样实际建立的方程组是近似方程组，这样实际建立的方程组是近似方程组(A+A)(X+X)=b+b。对近似方程组求出的解是。对近似方程组求出的解是原问题的真解原问题的真解X加上误差加上误差 X,即即X+X。而。而 X是由是由 A及及 b引起的，它的大小将直接影响所求解的可靠性。引起的，它的大小将直接影响所求解的可靠性。24/35计算方法计算方法计算方法计算方法三三三三绝对误差绝对误差例：方程组例：方程组此方程组的准确解为此方程组的准确解为x1=0,x2=-1。现将其右。现将其右端加以微小的扰动使之变为：端加以微小的扰动使之变为：经计算可得它的解为经计算可得它的解为x1=2,x2=-3.这两个方程组的解相差很大，说明方程组的这两个方程组的解相差很大，说明方程组的解对常数项解对常数项b的扰动的扰动很敏感。很敏感。25/35计算方法计算方法计算方法计算方法三三三三相对误差关系式：设有方程组相对误差关系式：设有方程组 AX=b (A是可是可逆矩阵逆矩阵,b0)1）仅常数项有误差的情形）仅常数项有误差的情形:设常数项设常数项b有扰动有扰动b,则相应的解为则相应的解为X+X，即，即 A（X+X）=b+b则有则有这说明常数项的相对误差这说明常数项的相对误差 在解中放大了在解中放大了|A-1|A|倍。倍。解的相解的相对误差对误差常数项的相常数项的相对误差对误差26/35计算方法计算方法计算方法计算方法三三三三2）仅系数矩阵有误差的情形）仅系数矩阵有误差的情形:设方程组的系数设方程组的系数A有扰动有扰动A，则相应的解为，则相应的解为X+X，即，即 (A+A)(X+X)=b这说明系数的相对误差这说明系数的相对误差 在解中也放大了在解中也放大了|A-1|A|倍。倍。27/35计算方法计算方法计算方法计算方法三三三三一般情形一般情形3)常数项和系数矩阵都有误差的情形常数项和系数矩阵都有误差的情形:设方程组设方程组的系数的系数A有扰动有扰动A，常数项常数项b有扰动有扰动b，则相应则相应的解为的解为X+X，即，即 可推得：可推得：与与|A-1|A|有关有关(A+A)(X+X)=b+b28/35计算方法计算方法计算方法计算方法三三三三由由上上面面关关系系式式可可看看到到，带带有有扰扰动动的的近近似似方方程程组组中中,扰扰动动的的大大小小直直接接影影响响着着所所求求解解的的相相对对误误差差，而而解解的相对误差都与的相对误差都与|A-1|A|有关有关,故可作如下定义：故可作如下定义：定义定义：设：设A非奇异，称非奇异，称|A-1|A|为矩阵为矩阵A的条件数的条件数,记为记为Cond(A)，即，即Cond(A)=|A-1|A|.当当cond(A)1，则方程组称为，则方程组称为“病态病态”的；的；当当cond(A)较小时，则方程组称为较小时，则方程组称为“良态良态”的。的。方方程程组组的的系系数数矩矩阵阵发发生生微微小小扰扰动动，引引起起方方程程组组性性质质上上的的变变化化，这这是是方方程程组组本本身身的的“条条件件问问题题”。29/35计算方法计算方法计算方法计算方法三三三三通常使用的条件数有：通常使用的条件数有：（1）cond(A)=|A-1|A|，（2）cond(A)2=|A-1|2|A|2 当当A为对称矩阵时，为对称矩阵时，cond(A)2（这里（这里max与与min分别是分别是A的绝对值最大和绝的绝对值最大和绝对值最小的特征值）对值最小的特征值）cond(A)2当当A为正定矩阵时，为正定矩阵时，cond(a,p)p=1,2,inf,frocond(a,1)cond(a,2)cond(a,inf)cond(a,fro)30/35计算方法计算方法计算方法计算方法三三三三Cond(A)可反映出方程组解对系数的敏感性。可反映出方程组解对系数的敏感性。我们通过下面的例子加以理解。我们通过下面的例子加以理解。绝对误差绝对误差这两个方程组的解相差很大，说明方程组的解对常数这两个方程组的解相差很大，说明方程组的解对常数项项b的扰动很敏感。同时注意到的扰动很敏感。同时注意到Cond(A)1.2 104,可可见见条件数很大条件数很大,因而是病态方程组因而是病态方程组.例例:方程组方程组现将其右端加以微小的扰动使之变为：现将其右端加以微小的扰动使之变为：经计算可得它的准确解为经计算可得它的准确解为x1=2,x2=-3.准确解为准确解为x1=0,x2=-131/35计算方法计算方法计算方法计算方法三三三三一一般般来来说说，方方程程组组的的条条件件数数越越小小，求求得得的的解解就越可靠；反之，解的可靠性就越差。就越可靠；反之，解的可靠性就越差。病态方程组的求解问题：病态方程组的求解问题：首先考虑怎样判断方程组是否属于病态方程组。首先考虑怎样判断方程组是否属于病态方程组。设方程组设方程组Ax=b的系数矩阵的系数矩阵A非奇异，计算非奇异，计算A的条的条件数，是判断病态方程组的可靠方法。但在实际件数，是判断病态方程组的可靠方法。但在实际问题中，当方程组的规模较大时，计算条件数的问题中，当方程组的规模较大时，计算条件数的工作量很大，甚至超过了求解方程组的计算量。工作量很大，甚至超过了求解方程组的计算量。一般采用下列方式，初步进行直观的判断。一般采用下列方式，初步进行直观的判断。32/35计算方法计算方法计算方法计算方法三三三三1）当当det(A)相对来说很小相对来说很小,或者或者A的某些行的某些行（或列）近似线性相关，（或列）近似线性相关，Ax=b可能病态可能病态;如果确定待解的方程组如果确定待解的方程组Ax=b是一个病态方程是一个病态方程组组,则数值求解必须小心，选择合适的方法，否则则数值求解必须小心，选择合适的方法，否则难以达到要求的精确度。难以达到要求的精确度。一般方法有：一般方法有：2）当系数矩阵当系数矩阵A中元素的绝对值相差很大中元素的绝对值相差很大且无规则，且无规则，Ax=b可能病态；可能病态；3）如果采用如果采用Gauss选主元消去法求解，在选主元消去法求解，在消元过程中出现小主元，消元过程中出现小主元，Ax=b可能病态；可能病态；4）求解方程组时，出现一个很大的解，求解方程组时，出现一个很大的解，Ax=b可能病态。可能病态。33/35计算方法计算方法计算方法计算方法三三三三方法方法1 采用尽可能高精度的运算，例如双精度或多精采用尽可能高精度的运算，例如双精度或多精度，以改善和减轻矩阵病态的影响，但此时的计算量度，以改善和减轻矩阵病态的影响，但此时的计算量将大大增大。将大大增大。例例 方程组方程组 1 1/2 1/3 1/41/2 1/3 1/4 1/51/3 1/4 1/5 1/61/4 1/5 1/6 1/7x1x2x3x425/1277/6057/60319/420=它的精解为它的精解为 x=1111分别用分别用3位和位和5位有效数字舍入运算的位有效数字舍入运算的消去法求解，得到的解分别为消去法求解，得到的解分别为x=(0.988，1.42，-0.428,2.10)T 和和x=(1.0000，0.99950，1.0017,0.99900)T显然后者的精度大大提高了显然后者的精度大大提高了34/35计算方法计算方法计算方法计算方法三三三三方法方法2 采用豫处理，采用豫处理，降低降低矩阵矩阵A的的条件数条件数，以改善方程组的病态程度。以改善方程组的病态程度。例如当系数矩阵例如当系数矩阵A元素的数量级差别很大时，可以对某些行或元素的数量级差别很大时，可以对某些行或列乘上适当的数，使得列乘上适当的数，使得A的所有行或列按某种范数大体上有相的所有行或列按某种范数大体上有相同的长度。我们称这种方法为行（列）均衡法。同的长度。我们称这种方法为行（列）均衡法。例例 设方程组设方程组 1 104 1 1 x1x21042=考虑用均衡法改善它的条件数。考虑用均衡法改善它的条件数。解：矩阵解：矩阵A的条件数的条件数cond(A)104，方程组是病态的。，方程组是病态的。为了使各行元素的大小均衡，将第一个方程乘以为了使各行元素的大小均衡，将第一个方程乘以10-4，得到方程组，得到方程组10-4 1 1 1 x1x212=BX=cond(B)435/35计算方法计算方法计算方法计算方法三三三三再计算矩阵再计算矩阵B的条件数的条件数cond(B)4，显然经过行均，显然经过行均衡后，系数矩阵的条件数得到很大的改善。衡后，系数矩阵的条件数得到很大的改善。方法方法3 采用近似解的迭代改善方式，逼近方程组采用近似解的迭代改善方式，逼近方程组的精确解。的精确解。设设x是方程组是方程组Ax=b的近似解，则以其残余向量的近似解，则以其残余向量 r=b-Ax为新的右端项的方程组：为新的右端项的方程组：Ax=r（*）方程组（方程组（*）的解）的解e作为近似解作为近似解x修正，得到原修正，得到原方程组更好的近似解方程组更好的近似解 x=x+e重复该过程，就可得到一个近似解序列，可以重复该过程，就可得到一个近似解序列，可以证明该序列收敛于证明该序列收敛于Ax=b的真解。具体内容可参的真解。具体内容可参见有关文献。见有关文献。36/35计算方法计算方法计算方法计算方法三三三三实验实验1、计算、计算A的条件数的条件数cond(A).2、如何改变方程组、如何改变方程组AX=b的病态性？的病态性？作业：作业：P74-75 8、9、10、17