7-范数与条件数

1第三章线性方程组求解的数值方法第二节范数与条件数2为了研究线性方程组近似解的误差估计和迭代法的收敛性，引进向量（矩阵）的范数的概念。3向量范数（Vectornorm）•公理化定义：向量范数：满足如下性质的函数：1.0x2.0xx03.aaxx4.xyxy():nfx正定性齐次性三角不等性4向量范数•例：判断下面那些是向量范数，那些不是，不满足那些性质。11niixx1/2221niixxmaxiixxlp范数：1/1pnpipixx000011,0;00niixxxx1xx0x√aaxx√xyxy√最常用的范数不满足性质3aaxx×不满足性质20xx0×5向量范数的几何意义-1-0.500.51-1-0.8-0.6-0.4-0.200.20.40.60.81P=0.4范数P=1范数P=2范数P=5范数P大于1，p范数为凸函数P小于1，p范数不为凸函数范数的凸性对求解最优化问题很重要。•除了范数等于0以外，任意范数取值都对应无穷多向量，上述向量构成了高维空间的连续曲面。6向量范数的几何意义•clearall•%closeall•clc••%figure•holdon•axisequal•p=0.4;•••foriii=1:200•t=(iii-1)/200*pi/2;•x1=(sin(t)).^(2/p);•y1=(cos(t)).^(2/p);•plot((x1),(y1),'r')•plot((-x1),(y1),'r')•plot((x1),(-y1),'r')•plot((-x1),(-y1),'r')•end12122/12/211sin(),cos()pppppppxxxxxtxt•利用参数法绘制等范数曲线。7向量范数应用•应用：判断向量的大小12xx12xx×向量不能比大小√向量通过定义范数比大小8向量范数应用•最重要的用途之一：分析向量收敛性，定义向量的极限：01,...limkkkxxxxx{,,...,},给定向量序列0,,kKkKxx：使得∀时，满足ξ-δ语言描述：9向量范数的等价性定理1212,0nststsxxRcccxxcx：设和是上的任意两种向量范数，则存在常数，使得向量范数的等价性定理：1212lim0limlim0nnnnsssnnnnnnstsxxxcxxcxxcxxxxcxx：s推论证明在收敛:由向量范数等价定理，可得：limlim,limlim=0kkkkkkkkkntngfhghAfAxx夹逼定理：已知，如果则所以：推论：向量序列在某范数下收敛，则在任意范数下收敛。收敛到同一值。122cxxcx10矩阵范数（Matrixnorm）•满足性质1~4的的函数•矩阵范数：–Frobenius范数：mn211||||||nnFijijAa—向量||·||2的直接推广1.0A2.0AA03.aAaA4.ABAB正定性齐次性三角不等性•任意矩阵范数等价•矩阵范数应用：–病态问题–分析迭代算法的收敛性11矩阵的算子范数（Inducednorm）•算子（诱导）范数：由向量范数导出的矩阵范数：0max()xAxAx•常见算子范数：101||||max()max||innijxjAxAax111011||||max()max||jnnijxiAxAax22max02||||max()()TxAxAAAx列和范数行和范数谱范数12矩阵的算子范数•例：已知矩阵A，求算子1范数和算子∞范数。1max21612366541578914152416()16.712497TAAAAAA所以，行和范数为，列和范数为和列和行13矩阵范数的性质amaAxAx•相容性：设‖‖a是向量范数，‖‖m是矩阵范数则矩阵范数‖‖m为与向量范数‖‖a相容的矩阵范数。ABAB•矩阵范数相容性：设‖‖矩阵范数，满足：则矩阵范数‖‖为相容矩阵范数。14矩阵范数的性质性质1：算子范数与其对应的向量范数相容，即：性质2：算子范数是相容范数：1,2,1,2,1,2,AxAxABABmaxmaxABxBxABAABxxmaxAxAAxAxx15矩阵范数与谱半径的关系性质3：对于任意算子范数有：()||||AA证明：1||||||||||||||||||||||||||||||||||()max||||||iniAxAxuuuAuAuAAA：由算子范数相容性可得：将任意特征值对应的特征向量带入得由于为任意特征值，则定义：矩阵A的谱半径记为(A)=，其中i为A的特征根。1max||ini16矩阵范数与谱半径的关系性质4：若A对称矩阵，则有：2||||()AA若是A的一个特征根，则2必是A2的特征根。若（最大特征根），则02必是A2的最大特征根。0()||A222max00||||()()AAA证明：17范数概念结构底层概念继承了顶层概念的性质。多元单值函数范数向量范数矩阵范数相容矩阵范数算子范数mnABAB性质1~4211||||||nnFijijAaFrobenius范范12，，...,12，，...,不相容矩阵范数n常用范数。18病态问题•“良态”问题和“病态”问题若原始数据有很小的变化δx，对应的输出变化δy也很小，则称该数学问题是良态问题；若δy很大，则称为病态问题病态问题中，结果对于数据的变化率都很大（很敏感），因此数据微小变化必将导致参数模型精确解的很大变化数学问题的病态问题完全取决于该数学问题本身的属性，在采用数值方法求解之前就存在，与数值方法无关。19线性方程组的病态问题12121212121223823.000018.000021223822.999998.000038.53xxxxxxxxxxxx：例线性方程组：的解为＝，＝若方程系数有一个小的扰动，解此方程得＝，＝－上述两组解都是对应方程的真实解，因此，病态问题与算法无关。方程系数变化很小，但方程的解变化很大从系统角度分析，系统输入很小误差，对结果产生很大影响。20线性方程组的病态问题问题一：b存在扰动：给定方程组Ax=b，其解为x*，另给定包含误差方程组Ax=b+e，其解为x’，分析其误差。111'/xxAeAeeAAbAbxx111'xAbxAbAe相容性1AbAxbAxbx21线性方程组的病态问题问题二，A存在扰动：给定方程组Ax=b，其解为x*，给定包含误差方程组（A+E）x=b，其解为x’，分析误差（A+E可逆）令x’=x*+δx，将方程（A+E）x’=b与Ax*=b做差，并展开，得到：1111()()()AExExxAEExIAEAEx11111111||||||||1|||||||()||||||||||||||||||||||||||||1|||||||||||||xIAEAExEAAEAAAEAAAAEAAE误差很小情况下。矩阵范数性质522矩阵范数的性质性质：证明：111||||IBB111111111()()()()()()||()||1||||||()||||()||(1||||)111||||IIBIBIBBIBIBIBIBIBBIBIBBIBB上页证明中用到了如下性质：23线性方程组的病态问题1AA为该方程对应于该（相容）矩阵范数的条件数111||||||||||||()||||||||()||||||||||||||||||||1||||||||||||eEeExAAAAAxbAbAAAA问题三，A，b都存在扰动：–给定方程组Ax=b，其解为x*，–另给定包含误差方程组（A+E）x=b+e，其解为x’，分析误差。24条件数的性质11max22min1()()2(2)()TTcondAAAAAcondAAAAA（），（），条件数与所取的矩阵范数有关。常用的条件数有：,()10,()()(2)1AcondAAccondcAcondAAcondA，1.对任何非奇2-范数对应的条件数异矩阵2.对非奇异矩阵和常数有3.对正交矩阵，当条件数很大时,方程组Ax=b是病态问题；当条件数较小时,方程组Ax=b是良态问题。25条件数的性质1、一个问题的病态性与算法有关。×2、无论问题好坏，好的算法都可得到其近似解。×3、提高计算精度，可改变系统病态性。×4、假设A的条件数为1，下面那些矩阵条件数也是1？（1）cA（2）QA,Q为正交矩阵（3）DA，D为对角矩阵（4）A的逆矩阵（5）BA，B为非奇异矩阵（6）A的转置矩阵注：A与A的转置具有相同的特征值。注意：条件数是矩阵的特征，与算法无关。条件数与所选择的范数有关，不同范数计算的条件数不同。26Hilbert矩阵1111...231111...23411111...1221nnHnnnnn典型的病态矩阵-Hilbert矩阵：利用matlab函数“hilb”，产生3阶、5阶、7阶……Hilbert矩阵,用matlab函数“cond”计算相应的条件数。编程分析矩阵误差对结果的影响。27Hilbert矩阵•clearall•closeall•clc•%病态方程求解•display('病态方程求解')•A=hilb(5)•display(strcat('cond(A)=',num2str(cond(A))))•b1=[1,2,3,4,5]*0.01•e=[0.2,-0.1,0.05,0.1,-0.3]*0.01•b2=b1+[0.2,-0.1,0.05,0.1,-0.3]*0.01•x1=A\b1.';•x1=x1.'•x2=A\b2.';•x2=x2.'•display('误差增益为norm(x1-x2)/norm(e)')•display('')•display(strcat('误差增益=',num2str((norm(x1-x2)/norm(e)))))•display('')28良态问题的不稳定算法1101,1,2,...1,2,3,..nxnnnExedxnEnEn：例计算积分解：利用分部积分可得到如下迭代公式：-111-11,2,3,...,10,,-1,...,3,2nnnNnEeEnEnEEEnNNn：，：，迭代一迭代二前面提到，“病态”是问题的固有属性，与选择的算法无关。下面给一个良态问题但存在不稳定算法的例子。29良态问题的不稳定算法-1112213311:3!!2nnEeEEEEEEn+......+迭代一的误差：假设，则051015202530-4-3-2-101x101530良态问题的不稳定算法1122(1).:(1..(1))NNNNNNNNNmmNmEEEENEENNEEENNNm+......+迭代二的误差：假设，则!!NmEmN+因此，“良态”问题可能存在不稳定的算法。246810-1-0.500.5131良态问题的不稳定算法•clearall•closeall•clc•••E1(1)=exp(-1);•foriii=2:40•E1(iii)=1-iii*E1(iii-1);•end•plot(E1)••NN=40;•E2(NN)=10.0;••foriii=1:(NN-1)•kkk=NN-iii•E2(kk