0111 第六章 线性方程组的数值解法-迭代法1

第三节向量范数和矩阵范数向量范数和矩阵范数是研究迭代法及其收敛性、估计方程组近似解的误差的一种有力工具，本节简要介绍其相关概念。一、向量范数1、向量范数的定义（1）绝对值范数的最简单的例子，是绝对值函数：并且有三个熟知的性质：①x0x0x=0当且仅当x=0②ax=axa为常数③x+y≤x+y2xx第三节向量范数和矩阵范数（2）范数的另一个简单例子是二维欧氏空间的长度欧氏范数也满足三个条件：设x=(x1,x2)①x0x0②ax=axa为常数③x+y≤x+y前两个条件显然，第三个条件在几何上解释为三角形一边的长度不大于其它两边长度之和。因此，称之三角不等式。220yxM（勾股定理）第三节向量范数和矩阵范数（3）下面我们给出n维空间中向量范数的概念：设X=(x1,x2,…,xn)T，记为XRn定义1：设XRn，Ｘ表示定义在Rn上的一个实值函数，称之为X的范数，它具有下列性质：①非负性：即对一切XRn，X0,Ｘ0②齐次性：即为任何实数aR，XRn，③三角不等式：即对任意两个向量X、YRn，恒有从以上规定范数的三种基本性质、立即可以推出Rn中向量的范数必具有下列性质：④0=0⑤XaaXYXYXXXX1第三节向量范数和矩阵范数2、常用的范数设X=(x1,x2,…,xn)T，则有：（1）向量的1范数（2）向量的2范数（3）向量的无穷范数不难验证，上述三种范数都满足定义的条件。nxxxX211222212nTxxxXXXinixX1max第三节向量范数和矩阵范数3、举例例1：求向量范数Tx)1,3,4,1(1x421xxx92x21242221)(xxx3327xiix41max4解：第三节向量范数和矩阵范数例2：P128设下x=[123]T，求x的1范数，2范数和无穷范数解：根据定义可以得到：63211X143213222X3max1inixX第三节向量范数和矩阵范数二、矩阵范数1、定义对于任意n阶方阵A，按一定的规则由一实数与之对应，记为，若满足：①②③则称为矩阵A的范数。AA0,0A,0AA当且仅当且为任意实数,AA阶方阵为任意两个和n,BABABAA正定奇次三角不等第三节向量范数和矩阵范数2、矩阵范数与向量范数的相容性对于任意的n维向量x，都有：这一性质称为矩阵范数与向量范数的相容性。xAAx第三节向量范数和矩阵范数3、常用的矩阵范数（1）矩阵的1范数niijnjaA111||||||1max范数：1Aniijnja11max,大值的每列绝对值之和的最A的列范数又称A第三节向量范数和矩阵范数（2）矩阵的无穷范数njijniaA11||max||||范数：Anjijnia11max,大值的每行绝对值之和的最A的行范数又称A第三节向量范数和矩阵范数（3）矩阵的2范数矩阵的谱半径：矩阵B的诸特征值为：则特征值的最大绝对值称为B的谱半径，记为：则：矩阵的2范数其实为AAT的谱半径的1/2次方。),,2,1(niiiniB1max)()(||||22TAAA范数：?)(TAA第三节向量范数和矩阵范数关于谱半径的说明：矩阵A的谱半径不是A的一种范数，但与A的任何一种范数有某种关系。)(A。的任意性，有由，故有由于则的任一特征对，即为矩阵）设证明（的任意一种算子范数为这里则定理：设AAAAAAAAAAARAxxxxxxxxnn}max{)(0,,1;||||||,||)()1(,第三节向量范数和矩阵范数4、矩阵的收敛性。的充分必要条件是则定理设1)(0,limARAkknnA第三节向量范数和矩阵范数5、举例例1：求矩阵A的各常用范数解：110121021A2523421Aniijnja11max5}2,5,2{max1njAnjijnia11max4}2,4,3{max1ni2A)(maxAAT第三节向量范数和矩阵范数先求ATA的特征值：特征方程为：解之可得ATA特征值：AAT110121021110122011211190102)det(AAIT20109111209361.0,9211.2,1428.9321第三节向量范数和矩阵范数可得：所以：对各个常用范数比较：1428.9)(maxAAT2A)(maxAAT0237.31AA2A容易计算计算较复杂对矩阵元素的变化比较敏感使用最广泛性质较好第三节向量范数和矩阵范数例2：844.4466.23||||534.1,466.2301710108||1710108421241226}4|2||,1|2max{||||5}4|1||,2|2max{||:||),2,1(||||,42122211AAAIAAAApAATTp，故解得由因为解求设矩阵第三节向量范数和矩阵范数例3：P129例6－7第四节解线性方程组的迭代法迭代法在计算过程中保持迭代矩阵不变，这类方法主要适用于大型稀疏线性方程组的求解。其基本思想是通过构造迭代格式产生迭代序列，由迭代序列来逼近原方程组的解，因此，要解决的基本问题是：（1）如何构造迭代格式（2）迭代序列是否收敛第四节解线性方程组的迭代法一、迭代法的基本思想设有线性代数方程组：a11x1+a12x2+····+a1nxn=b1a21x1+a22x2+····+a2nxn=b2.....................an1x1+an2x2+····+annxn=bn用矩阵表示：Ax=b其中A为系数矩阵，非奇异且设aii≠0；b为右端，x为解向量做方程组的一个等价变换为：x=Bx+f第四节解线性方程组的迭代法任取初始向量x(0)，按照下列公式构造迭代序列：结论：如果迭代序列收敛，则它一定收敛到方程组的解概念：迭代公式：迭代矩阵：B不同的迭代矩阵构成不同的迭代法，先介绍两种迭代法：雅可比迭代法和高斯－赛得尔迭代法。fBxxkk)()1()(kxfBxxkk)()1(第四节解线性方程组的迭代法二、雅可比（Jacobi）迭代法1、公式推导方程组：a11x1+a12x2+····+a1nxn=b1a21x1+a22x2+····+a2nxn=b2.....................an1x1+an2x2+····+annxn=bn),,2,1(0niaii设ix则可从上式解出,)]([112121111nnxaxabax-----(1)第四节解线性方程组的迭代法依此类推,线性方程组可化为:)]([123231212222nnxaxaxabax)]([1)(113132121111111111nnnjjjjxaxaxabaxabax)]([1)(123231212222122222nnnjjjjxaxaxabaxabax)]([1)(122111niniiiiinijjjijiiiixaxaxabaxabax)]([1)(11122111nnnnnnnnnnjjjnjnnnnxaxaxabaxabax-----(2)第四节解线性方程组的迭代法对(2)作迭代过程：)(11)()1(nijjkjijiiikixabax),2,1,0;,,2,1(kni--------(3)则(3)式转化为矩阵形式：),,,(2211nnaaadiagD记])([)(1)1(kkxDAbDxbDxDADxkk1)(1)1()(--------(4)第四节解线性方程组的迭代法另外，(2)还可以转化为矩阵形式：（教材）00021222222111111120nnnnnnnnaaaaaaaaaaaaBnnnabababf222111fxBxkk)(0)1(--------(5)第四节解线性方程组的迭代法令：0000002121nnaaaLULDAULDA0000002112nnaaaUA的下三角部分矩阵A的上三角部分矩阵--------(6)第四节解线性方程组的迭代法由式（4）（5）（6）可以有：fxBxkJk)()1(),2,1,0(k--------(7)式（7）等价线性方程组为fxBxJbAx称(7)式为解线性方程组(1)的Jacobi迭代法(J法)迭代法的迭代矩阵为JacobiBJbDxDADxkk1)(1)1()(fxBxkk)(0)1(ULDA由式（4）（5）（6）总结有：)(1ULDBJbDf1第四节解线性方程组的迭代法2、举例例1：用Jacobi迭代法求解方程组,误差不超过1e-41233204121114238321xxx4121114238A4000110008D000100230U012004000L解：第四节解线性方程组的迭代法则：)(1ULDBJ04121111011441830bDf1335.2迭代法使用取初值JacobixT,]000[)0(fxBxkJk)()1(),,2,1,0(nk第四节解线性方程组的迭代法即：雅克比迭代公式为：fxBxkJk)()1(04121111011441830)1(kx335.2)(3)(2)(1kkkxxx3412131111145.24183)(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx即：第四节解线性方程组的迭代法可以得到：04121111011441830fxBxJ)0()1(335.2000T]3,3,5.2[924.42)0()1(xx04121111011441830fxBxJ)1()2(335.2335.2T]1,3636.2,875.2[1320.22)1()2(xx第四节解线性方程组的迭代法依此类推,得方程组满足精度的解为x1204121111011441830fxBxJ)2()3(335.213636.2875.2T]9716.0,0455.2,1364.3[4127.02)2()3(xx迭代次数为12次x4=3.02411.94780.9205d=0.1573x5=3.00031.98401