第三章向量范数与矩阵范数ppt课件.pptx

《第三章向量范数与矩阵范数ppt课件.pptx》由会员分享，可在线阅读，更多相关《第三章向量范数与矩阵范数ppt课件.pptx（82页珍藏版）》请在三一办公上搜索。

1、1,第三章,向量范数与矩阵范数,2,内容提要,范数的引入 向量范数的类型、定义与性质 矩阵范数的类型、定义与性质 方阵的谱半径 范数及其应用,3,本讲内容,定义、常见向量范数、性质,向量范数,定义、常见矩阵范数、性质,矩阵范数,矩阵条件数,原因,范数的引入,4,向量范数与矩阵范数,引入,为了研究线性方程组近似解的误差估计和迭代法的收敛性，我们需要对Rn中向量或Rn2中矩阵的“大小”引进某种度量范数。,5,向量范数,对于实数和复数，由于定义了它们的绝对值或模，这样我们就可以用这个度量来表示它们的大小（几何上就是长度），进而可以考察两个实数或复数的距离。,对于 维线性空间，定义了内积以后，向量就有

2、了长度（大小）、角度、距离等度量概念，这显然是3维现实空间中相应概念的推广。利用公理化的方法，可以进一步把向量长度的概念推广到范数。,6,向量范数：向量的长度或模,，当且仅当 时，等号成立。,例 1复数 的长度或模指的是量,显然复向量 的模 具有下列三条性质：,，当且仅当 时，等号成立。,显然向量 的模 也具有下列三条性质：,例 2 维欧氏空间中向量 的长度或模定义为,向量范数：向量的长度或模,8,向量范数,定义：设函数 f : Rn R，若 f 满足 f(x) 0， xRn , 等号当且仅当 x = 0 时成立 （正定性） f(x) = | f(x) ， xRn , R （齐次性） f(x+

3、y) f(x) + f(y) （三角不等式）则称 f 为 Rn 上的（向量）范数，通常记为 | |,向量范数,定义 如果 是数域 上的线性空间，对 中的任意向量 ，都有一个非负实数 与之对应，并且具有下列三个条件（正定性、正齐性和三角不等式）：,9,向量范数,则称 是向量 的向量范数，称定义了范数的线性空间 为赋范线性空间。,拓扑空间,线性空间,Hausdorff空间,赋范空间,距离空间(度量空间),拓扑线性空间,完备距离线性空间,距离线性空间,内积空间,Hilbert空间,Banach空间,欧氏空间 和,各类空间的层次关系,11,常见向量范数,Rn 空间上常见的向量范数,1-范数：,2-范数

4、：,-范数（有时也称最大范数）：,-范数：,例 3 设 是内积空间，则由,定义的 是 上的向量范数，称为由内积 导出的范数。这说明范数未必都可由内积导出。例如后面介绍的 和 。,向量范数,向量范数,常见向量范数：2-范数,例 6 对任意 ，由,定义的 是 上的向量范数，称为p -范数或 范数。,常见向量范数：p-范数,例 7 对任意 ，由,定义的 是 上的向量范数，称为1-范数或 范数或和范数，也被风趣地称为Manhattan范数。,特别地，p = 1 时，有,常见向量范数：1-范数,常见向量范数：举例,解：,遗憾的是，当 时，由,定义的 不是 上的向量范数。,因为 时，取 ，则,常见向量范数

5、：特殊点,例 8 对任意 ，由,定义的 是 上的向量范数，称为 -范数或 范数或极大范数。,在广义实数范围内，P能否取到正无穷大呢？具体而言，如何计算这种范数呢？,也就是,常见向量范数：极大范数,证明： 验证 是向量范数显然很容易。下证 。,令 ，则有,由极限的两边夹法则，并注意到 ，即得欲证结论。,常见向量范数：极大范数,这些范数在几何上如何理解呢？,例9 对任意 ，对应于 四种范数的闭单位圆 的图形分别为,特别地， 范数、 范数和 范数分别为,非常见向量范数,当 时， ；当 时由 对称正定知 ，即 。,对于任意 ，有,非常见向量范数：加权范数,由于 为Hermite正定矩阵，故存在酉矩阵

6、，使得,从而有,这里 的特征值 都为正数。,此时,因此对任意 ，,一般地，由于 是Hermite正定矩阵，从而有可逆矩阵 （未必是酉矩阵），使得 ，因此,如果 ，此时 ，这就是加权范数或椭圆范数名称的由来。,这从几何上可以理解成求可逆变换 的像的“长度” 。这说明只要运算 成立即可，因此对矩阵 的要求可放宽为列满秩矩阵。,为李雅普诺夫（Lyapunov）函数，这里 是正定对称矩阵。大家已经知道，此函数是讨论线性和非线性系统稳定性的重要工具。,在现代控制理论中，称二次型函数,非常见向量范数：加权范数,例 12 （模式识别中的模式分类问题）,模式分类的问题指的是根据已知类型属性的观测样本的模式向量

7、 ，判断未知类型属性的模式向量 归属于哪一类模式。其基本思想是根据 与模式样本向量 的相似度大小作出判断。,最简单的方法是用两向量之间的距离来表示相似度，距离越小，相似度越大。最典型的是Euclidean距离,其他距离测度还包括,以及与椭圆范数类似的Mahalanobis距离：,这里 是从正态母体 中抽取的两个样本。,30,范数性质,范数的性质,(1) 连续性,定理：设 f 是 Rn 上的任一向量范数，则 f 关于 x 的每个分量连续。,(2) 等价性,定理：设 | |s 和 | |t 是 Rn 上的任意两个范数，则存在常数 c1 和 c2 ，使得对任意的 xRn 有,31,定理：设 | |

8、是 Rn 上的任意一个向量范数，则,范数性质,(3) Cauchy-Schwarz 不等式,(4) 向量序列的收敛性,定理：,证明：略,定义：设 是 Rn 中的一个向量序列，其中 如果 ，则称 收敛到 ，记为,定理 Euclid范数是酉不变的，即对任意酉矩阵 以及任意 ，均有,这个定理的结论是显然的，因为酉变换保持向量的内积不变，自然也保持了Euclid意义下的几何结构（长度、角度或范数等）不变。,范数性质,注意这个结论对无限维未必成立。另外，根据等价性，处理向量问题（例如向量序列的敛散性）时，我们可以基于一种范数来建立理论，而使用另一种范数来进行计算。,定理 有限维线性空间 上的不同范数是等

9、价的，即对 上定义的任意两种范数 ，必存在两个任意正常数 ，使得,范数性质,向量是特殊的矩阵， 矩阵可以看成一个 维向量，因此自然想到将向量范数推广到矩阵范数。,矩阵范数,35,矩阵范数,定义：设函数 f : Rnn R，若 f 满足 f(A) 0， A Rnn , 且 f(A) = 0 A = 0 （正定性） f(A) = | f(A) ， ARn , R （齐次性） f(A+B) f(A) + f(B) （三角不等式） f(AB) f(A)f(B) （相容性）则称 f 为 Rnn 上的（矩阵）范数，通常记为 | |,矩阵范数,36,矩阵范数,定义 对 中的任意矩阵 ，都有一个非负实数 与之

10、对应，并且具有下列三个条件（正定性、正齐性和三角不等式）：,则称 是矩阵 的（广义）矩阵范数。,37,常见矩阵范数,常见的矩阵范数,(1) F-范数 (Frobenious 范数),(2) 算子范数 (从属范数、诱导范数),其中 | | 是 Rn 上的任意一个范数,矩阵不仅仅是向量，它还可以看成变换或算子。 实际中，从算子或变换的角度来定义范数更加有用。,定义5 对 中的任意矩阵 ，用一个非负实数 表示对于任意向量 ， 可以“拉伸”向量 的最大倍数，即使得不等式成立的最小的数 。称 为范数 和 诱导出的矩阵范数或算子范数。,算子范数,由矩阵范数的正齐性可知 的作用是由它对单位向量的作用所决定，

11、因此可以等价地用单位向量在 下的像来定义矩阵范数，即,从几何上看，矩阵范数反映了线性映射把一个向量映射为另一个向量，向量的“长度”缩放的比例 的上界。,算子范数,40,算子范数,常见的算子范数, -范数（行范数）, 2-范数（谱范数）, 1-范数（列范数）,求矩阵A的各种常用范数,解:,由于,特征方程为,容易计算,计算较复杂,对矩阵元素的变化比较敏感,使用最广泛,性质较好,同样给出这些范数在几何上的理解。,例 8 对应于 三种向量范数的闭单位球 在矩阵作用下的效果分别为,定理 上的谱范数具有下列性质：,矩阵范数性质,(1),设有 使 ，令 ，则有,证明：,(2),(3),设有 使 ，则,证明：

12、,定理 上的矩阵F-范数和谱范数都是酉不变的，即对任意酉矩阵 ，恒有,令,则,即,对于谱范数的情形，利用定义即可。,对于谱范数， 这个定理的结论可以推广到列正交酉矩阵，即的情形，此时仍然成立,利用定理可以证明这个推广结论。,53,矩阵范数性质,矩阵范数的性质,(1) 连续性：设 f 是 Rnn 上的任一矩阵范数，则 f 关于 A 的每个分量是连续的。,(2) 等价性：设 | |s 和 | |t 是 Rnn 上的任意两个矩阵范数，则存在常数 c1 和 c2 ，使得对任意的 A Rnn 有,(3) 若 A 是对称矩阵，则,证明：略,证明：略,证明：练习,54,算子范数性质,算子范数的性质,定理：对

13、任意 0, 总存在一算子范数 | | ，使得 |A| (A) + ,证明：略,定理：设 | | 是任一算子范数，则,注：该性质对 F-范数也成立。,55,定理：设 | | 是 Rn 上的任一向量范数，其对应的算子范数也记为 | | ，则有,算子范数性质,算子范数的性质,该性质就是矩阵范数与向量范数的相容性,证明：直接由算子范数定义可得,定理：设 | | 是任一算子范数，若 |B|1 ，则 IB 非奇异，且,56,病态矩阵,定义：考虑线性方程组 Ax=b，如果 A 或 b 的微小变化会导致解的巨大变化，则称此线性方程组是病态的，并称矩阵 A 是病态的，反之则是良态的。,什么是病态矩阵,例：,57

14、,矩阵条件数,定义：设 A 非奇异，则称为 A 的条件数，其中 | |v 是 1-范数，2-范数或 -范数。,如何判别矩阵是否病态 矩阵的条件数,定理：考虑线性方程组 Ax=b，设 A 是精确的，b 有微小的变化 b，此时的解为 x + x ，则,58,矩阵条件数,定理：考虑线性方程组 Ax=b，设 b 是精确的，A 有微小的变化 A，此时的解为 x + x 。假定 ，则,当 A 充分小时，不等式右端约为,一般来说，当 A 的条件数较大时，A 就是病态的 条件数越大，病态越严重，此时就越难用一般方法求得线性方程组比较精确的解。,59,矩阵条件数,条件数与范数有关，常用的有无穷范数和2-范数,注

15、：Cond(A)2 称为谱条件数，当 A 对称时有,60,条件数性质,条件数的性质,Cond(A)1 Cond(A) = Cond(A), 其中 为任意非零实数 若 R 是正交矩阵，则 Cond(R)2=1 若 R 是正交矩阵，则对任意非奇异矩阵 A，有 Cond(AR)2=Cond(RA)2=Cond(A)2,61,举例,例： 计算 Cond(A) 和 Cond(A)2,解：,Cond(A)=|A-1| |A| 4104,Cond(A)2=max / min 4104,A 对称，且,62,举例,例：计算 Cond(Hk) 其中 Hk 为 k 阶 Hilbert 矩阵,解：,k=1 时， Co

16、nd(H1)=1,k=2 时，,Cond(H2)=27,k=3 时，,Cond(H3)=748,Cond(H4)=28375，Cond(H10)=3.51013,向量范数的应用,向量范数的概念是复数模的概念的自然推广。,二、研究矩阵和向量的序列以及级数的收敛准则,范数的主要的应用：,一、研究矩阵和向量的误差估计,监督机器学习问题无非就是也就是在规则化参数的同时最小化误差。最小化误差是为了让我们的模型拟合我们的训练数据，而规则化参数是防止我们的模型过分拟合我们的训练数据。,参数太多，会导致我们的模型复杂度上升，容易过拟合，训练误差会很小。但训练误差小并不是我们的最终目标，我们的目标是希望模型的测

17、试误差小，也就是能准确的预测新的样本。,所以，我们需要保证模型“简单”的基础上最小化训练误差，这样得到的参数才具有好的泛化性能（也就是测试误差也小），而模型“简单”就是通过规则函数来实现的。,引入,一般来说，监督学习可以看做最小化下面的目标函数：,L(yi,f(xi;w) 衡量我们的模型（分类或者回归）对第i个样本的预测值f(xi;w)和真实的标签yi之前的误差。,L0范数与L1范数,L0范数是指向量中非0的元素的个数。如果我们用L0范数来规则化一个参数矩阵W的话，就是希望W的大部分元素都是0，让参数W是稀疏的 。,L1范数是指向量中各个元素绝对值之和，也有个美称叫“稀疏规则算子”。任何的规则

18、化算子，如果他在Wi=0的地方不可微，并且可以分解为一个“求和”的形式，那么这个规则化算子就可以实现稀疏。,L1是规则化的算子，我们将权值参数以L1的方式放到代价函数里面去。然后模型就会尝试去最小化这些权值参数。而这个最小化就像一个下坡的过程。,这说明，W的L1范数是绝对值，|w|在w=0处是不可微的。,L1范数和L0范数可以实现稀疏，L1因具有比L0更好的优化求解特性而被广泛应用。,稀疏的原因,特征选择 稀疏规则化受欢迎的一个关键原因在于它能实现特征的自动选择。,可解释性 通过稀疏可以使模型更容易解释。,L2范数,L2范数: |W|2，在回归里面，有人把有它的回归叫“岭回归”，有人也叫它“权

19、值衰减”。它的强大功效是改善机器学习里面一个非常重要的问题：过拟合。,上面的图是线性回归，从左到右分别是欠拟合，合适的拟合和过拟合三种情况。,Logistic回归,如果模型复杂（可以拟合任意的复杂函数），它可以让我们的模型拟合所有的数据点，也就是基本上没有误差。对于回归来说，就是我们的函数曲线通过了所有的数据点。对分类来说，就是我们的函数曲线要把所有的数据点都分类正确。这两种情况很明显过拟合了。,L2范数是指向量各元素的平方和然后求平方根。我们让L2范数的规则项|W|2最小，可以使得W的每个元素都很小，都接近于0，但与L1范数不同，它不会让它等于0，而是接近于0。,通过L2范数，我们可以实现了

20、对模型空间的限制，从而在一定程度上避免了过拟合。,L2范数的好处,从学习理论的角度来说，L2范数可以防止过拟合，提升模型的泛化能力。,从优化或者数值计算的角度来说，L2范数有助于处理 condition number不好的情况下矩阵求逆很困难的问题。,优化两大问题,局部最小值问题 要找的是全局最小值，如果局部最小值太多，那我们的优化算法就很容易陷入局部最小而不能自拔 。,ill-condition病态问题,ill-condition病态问题,ill-condition对应的是well-condition。那他们分别代表什么？,ill-conditioned系统的解对系数矩阵A或者b太敏感了。又

21、因为一般我们的系数矩阵A和b是从实验数据里面估计得到的，所以它是存在误差的，如果我们的系统对这个误差是可以容忍的就还好，但系统对这个误差太敏感了，以至于我们的解的误差更大，那这个解就太不靠谱了。,condition number,condition number就是拿来衡量ill-condition系统的可信度的。,condition number值小的就是well-conditioned的，大的就是ill-conditioned的。,condition number衡量的是输入发生微小变化的时候，输出会发生多大的变化。也就是系统对微小变化的敏感度。,如果方阵A是非奇异的，那么A的condit

22、ionnumber定义为：,如果方阵A是奇异的，那么A的condition number就是正无穷大了。实际上，每一个可逆方阵都存在一个condition number。但如果要计算它，需要先知道这个方阵的norm（范数）和Machine Epsilon（机器的精度）。,经过比较简单的证明，对于AX=b，我们可以得到以下的结论 :,解x的相对变化和A或者b的相对变化是有像上面那样的关系的，其中k(A)的值就相当于倍率，相当于x变化的界。,Condition number总结,Condition number是一个矩阵（或者它所描述的线性系统）的稳定性或者敏感度的度量，如果一个矩阵的condition number在1附近，那么它就是well-conditioned的，如果远大于1，那么它就是ill-conditioned的，如果一个系统是ill-conditioned的，它的输出结果就不要太相信了 。,在矩阵求逆很困难的问题上，目标函数如果是二次的，对于线性回归来说，那实际上是有解析解的，求导并令导数等于零即可得到最优解为：,加上L2规则项，就变成了下面这种情况，就可以直接求逆了：,