【教学课件】第六章线性方程组的迭代解法.ppt

第六章 线性方程组的迭代解法,1 向量和矩阵的范数 1.1 向量的范数 1.2 矩阵的范数2 迭代解法与收敛性 2.1 迭代解法的构造 2.2 迭代解法的收敛性条件3 常用的三种迭代解法 2.1 Jacobi迭代法 2.2 Gauss-Seidel迭代法 2.2 超松弛(SOR)迭代法,1 向量和矩阵的范数,一、向量的范数,为了对线性方程组数值解的精确程度，以及方程组本身的性态进行分析，需要对向量和矩阵的“大小”引进某种度量，范数就是一种度量尺度，向量和矩阵的范数在线性方程组数值方法的研究中起着重要的作用。,定义6.1 设|是向量空间Rn上的实值函数，且满足条件,（1）非负性：对任何向量x，|x|0，且|x|0当且仅当x0,则称|为 Rn 空间上的范数，|x|为向量 x 的范数。,理论上存在多种多样的向量范数，但最常用的是如下三种。,（2）齐次性：对任何实数和向量x|x|x|,（3）三角不等式：对任何向量x和y，都有|xy|x|y|,设向量x（x1，x2，xn）T，定义,向量1-范数：,向量2-范数：,向量-范数：,容易验证，以上三种范数都满足向量范数的三个条件。,例6-1 设向量x（1，3，2，0）T，求向量范数|x|p，P1，2，。,解:对于 向量 x(1，3，2，0)T，根据定义可以计算出：,|x|1|1|3|2|0|6,由此例可见，向量不同范数的值不一定相同，但这并不影响对向量大小做定性的描述，因为不同范数之间存在如下等价关系。,定理6.1（范数的等价性）对于Rn上任何两种范数|和|，存在的正常数 m，M，使得：,范数的等价性表明，一个向量若按某种范数是一个小量，则它按任何一种范数也将是一个小量。容易证明，常用的三种向量范数满足下述等价关系。,|x|x|1 n|x|,|x|x|2|x|,|x|x|1|x|2,例如：,定义6.2 对于向量序列,向量序列 x(k)收敛于向量 x*，当且仅当它的每一个分量序列收敛于x*的对应分量，即,及向量,如果,则称向量序列 x(k)收敛于向量 x*。记作,或,二、矩阵的范数,矩阵范数是反映矩阵“大小”的一种度量，具体定义如下。,定义2.3 设|是以n阶矩阵为变量的实值函数，且满足条件：,（1）|A|0，且|A|0时，当且仅当A0（2）|A|A|，R（3）|AB|A|B|（4）|AB|A|B|则称|A|为矩阵A的范数。,设 n 阶矩阵 A（aij），常用的矩阵范数有：,矩阵1-范数：,矩阵2-范数：,矩阵-范数：,列和,行和,以上三种范数都满足矩阵范数的条件，通常将这三种矩阵范数统一表示为|A|p，P1，2，。,例2-6 设矩阵,求矩阵A的范数|A|p，P1，2，。,解 根据定义,由于,则它的特征方程为:,此方程的根为矩阵ATA的特征值，解得,因此,在线性方程组的研究中，经常遇到矩阵与向量的乘积运算，若将矩阵范数与向量范数关联起来，将给问题的分析带来许多方便。设|是一种向量范数，由此范数派生的矩阵范数定义为,注意，此式左端|A|表示矩阵范数，而右端是向量Ax 和 x 的范数，利用向量范数所具有的性质不难验证，由上式定义的矩阵范数满足矩阵范数的条件。,通常将满足上式的矩阵范数称为与向量范数相容的矩阵范数。,可以证明，前述的三种矩阵范数|A|p，P1，2，就是由向量范数|x|p派生出的矩阵范数，即,通过向量范数定义的矩阵范数，满足不等式关系：,均为相容范数，即,另一种常用的矩阵范数称为F-范数，定义为,它仅与向量的2-范数相容，即成立,三、矩阵的谱半径,矩阵范数同矩阵特征值之间有密切的联系，设是矩阵A相应于特征向量x的特征值，即Axx,利用向量-矩阵范数的相容性，得到,|x|x|,从而，对A的任何特征值均成立,=|Ax|,|A|x|,|A|（6.1）,设n阶矩阵A的n个特征值为1,2，n。称,为矩阵A的谱半径，从（6.1）式得知，对矩阵A的任何一种相容范数都有,（6.2）,另一个更深刻的结果：0，必存在一种相容的矩阵范数，使,|A|（6.3）,式（6.2）和（6.3）表明，矩阵A的谱半径是它所有相容范数的下确界。,定义6.3 设有矩阵序列 和矩阵A（aij）。称 A（k）收敛于A，如果,记作 A（k）A，或 A（k）A。,四、矩阵的条件数,引进了矩阵的度量标准范数，就可以对方程组求解进行误差分析，对于方程组,Ax=b,如果常数项产生了误差b,并设求解时产生的误差为x，则有,A(x+x)=b+b,两式相减得到 A x=b,当系数矩阵可逆时,x=A-1b,取范数,|x|=|A-1b|,|A-1|b|,再由 Ax=b，得到,|b|=|Ax|,|A|x|,于是，由|x|A-1|b|,得到解的相对误差为,及|b|A|x|,令 Cond(A)=|A|A-1|,并称其为矩阵A的条件数。,这时,可见，求解线性方程组所产生的误差与系数矩阵的条件数有关。,对于线性方程组 Ax=b，如果系数矩阵的条件数Cond(A)=|A|A-1|太大，则称相应的方程组为病态方程组。,病态现象是方程组的固有属性，无法改变，因此在求解时为了不至于产生太大的误差，应该尽量减少原始数据 A、b 的误差，或者用高精度的计算机计算。,例如：对于方程组,系数矩阵和逆矩阵分别为,可以求得,条件数比较大，可见该方程组为病态方程组。,2 迭代解法与收敛性,一、迭代解法,二、收敛性,3 常用的三种迭代解法,一、Jacobi迭代解法,二、Gauss-Seidel迭代解法,三、超松弛(SOR)迭代解法,第6章 线性方程组的迭代解法-习题,6-1 对二维向量x（x1，x2）T，画出由平面上点集：|x|11，|x|21，|x|1所确定的几何图形。,6-2 证明下列不等式（1）|xy|xz|zy|（2）|x|y|xy|,6-3 设|为一向量范数，P为非奇异矩阵，定义|x|p|Px|。证明|p也是一种向量范数。,6-4 设A为对称正定矩阵，定义。证明|A 也是一种向量范数。,6-5 证明范数的等价性（1）|x|x|2|x|（2）|x|2|x|1|x|2（3）|A|2|A|F|A|2,6-7 试证明（1）如果A为正交矩阵，则Cond2（A）1（2）如果A为对称正定矩阵，则 Cond2（A）1/n1和n分别为A的最大和最小特征值。,6-8 设A是非奇异矩阵，b0，x*是方程组Axb的一 个近似解，剩余向量rbAx。证明,