数值分析 第六章 解线性方程组的迭代法

数值分析 Numerical Analysis第六章 解线性代数方程组的迭代 法郑州大学研究生课程 （2015-2016学年第一学期） ISCM 2007,Beijing China1第六章 解线性代数方程组的迭代法§6.1 引言 §6.2 范数与误差分析 §6.3 几种常用的迭代格式 §6.4 迭代法的收敛性及误差估计 §6.5 判别收敛的几个常用条件 §6.6 迭代法收敛判定的应用举例ISCM 2007,Beiji ng China2015-2016学年课程 数值分析 Numerical Analysis§6.1 引言q 线性方程组的数值解法有：直接法和迭代法。ü 直接法：在假定没有舍入误差的情况下，经过有限次 运算可以求得方程组的精确解；ISCM 2007,Beiji ng China2015-2016学年课程 数值分析 Numerical Analysis§6.1 引言当A为稀疏矩阵时，直接法将破坏矩阵A的稀疏性。系数矩阵的分类第一类：低阶稠密方程组，即系数矩阵的阶数不高，含零元素很少，在线性代数等课程学习中通常见到的，都属这类方程组；第二类：高阶稀疏方程组，系数矩阵的阶数很高，如几百阶、甚至成千上万阶，其中零元素成片分布，数量上绝对占优。ISCM 2007,Beiji ng China2015-2016学年课程 数值分析 Numerical Analysis迭代法适用于解大型稀疏方程组 (万阶以上的方程组,系数矩阵中零元素占很大 比例,而非零元按某种模式分布)问题: (1)如何构造迭代格式？(2)迭代格式是否收敛？(3)如何进行误差估计？§6.1 引言ISCM 2007,Beiji ng China2015-2016学年课程 数值分析 Numerical Analysis§6.1 引言迭代法的基本思想迭代法的基本思想是将线性方程组转化为便于迭代的等价方程组，对任选一组初始值 ，按迭代格式，不断地对所得到的值进行修正，最终获得满足精度要求的方程组的近似解。ISCM 2007,Beiji ng China2015-2016学年课程 数值分析 Numerical Analysis设 非奇异， ，则线性方程组 有惟一解 ，经过变换构造出一个等价同解方程组将上式改写成迭代式选定初始向量 ,反复不断地使用迭代式逐步逼近方程组的精确解,直到满足精度要求为止。ISCM 2007,Beiji ng China2015-2016学年课程 数值分析 Numerical Analysis如果向量序列 存在极限则称迭代法是收敛的，否则就是发散的。收敛时，在迭代公式中当 时， , 则故 是方程组 的解。注：对于给定的方程组，可以构造各种迭代公式，但并非全部收敛 。ISCM 2007,Beiji ng China2015-2016学年课程 数值分析 Numerical Analysis§6.2 范数与误差分析Ø 为了研究线性方程组近似解的误差估计和迭代 法的收敛性, 有必要对向量及矩阵的“大小” 引进某种度量-范数的概念。Ø 向量范数是用来度量向量长度的,它可以看成是 二、三维解析几何中向量长度概念的推广。Ø 用Rn表示n维实向量空间。ISCM 2007,Beiji ng China2015-2016学年课程 数值分析 Numerical Analysis§6.2 范数与误差分析 （一、向量范数）§6.2.1 向量范数定义6.2.1 设 X R n， 表示定义在Rn上的一个实值函数，称之为X的范数，若它满足下列性质：（3）三角不等式：即对任意两个向量X、Y R n，恒有 (1) 正定性：即对一切X R n，(2) 齐次性：即对任何实数 a R，X R n，ISCM 2007,Beiji ng China2015-2016学年课程 数值分析 Numerical Analysis注:向量范数是向量长度概念的推广.例如就是向量 x 的一种范数常见向量范数常用的范数:1-范数2-范数-范数ISCM 2007,Beiji ng China2015-2016学年课程 数值分析 Numerical Analysis§6.2 范数与误差分析ISCM 2007,Beiji ng China2015-2016学年课程 数值分析 Numerical Analysis§6.2 范数与误差分析例6.2.1 证明 |x|2 是 Rn 上的一种范数(正定性成立)(齐次性成立)证明：ISCM 2007,Beiji ng China2015-2016学年课程 数值分析 Numerical Analysis先证柯西不等式: | xTy | |x|2·| y|2对任意实数, 有(x - y)T(x - y)0 xTx 2xTy + 2yTy 0| xTy |2 (xTx)(yTy) 0 | xTy | |x|2·| y|2判别式（3） 三角不等式ISCM 2007,Beiji ng China2015-2016学年课程 数值分析 Numerical Analysis(三角不等式成立)ISCM 2007,Beiji ng China2015-2016学年课程 数值分析 Numerical Analysis例6.2.2. 范数意义下的单位向量: X=x1, x2T1-11|X|1 = 111-1-1|X|2 = 1-111-1-1|X| = 1ISCM 2007,Beiji ng China2015-2016学年课程 数值分析 Numerical Analysis§6.2 范数与误差分析ISCM 2007,Beiji ng China2015-2016学年课程 数值分析 Numerical Analysis定理6.2.1 对于任意向量x ,有证: 即 当 p， ISCM 2007,Beiji ng China2015-2016学年课程 数值分析 Numerical Analysis§6.2 范数与误差分析ISCM 2007,Beiji ng China2015-2016学年课程 数值分析 Numerical Analysis例6.2.3 证明对任意同维向量x , y 有 证 ： 即 ISCM 2007,Beiji ng China2015-2016学年课程 数值分析 Numerical Analysis例6.2.4 设x=(1, 0, -1, 2)T, 计算 解: =1+0+|-1|+2=4ISCM 2007,Beiji ng China2015-2016学年课程 数值分析 Numerical Analysis定理6.2.2 （向量范数的等价性）设 为 上任意两种向量范数, 则存在常数C1, C2>0,使得对任意 恒有有限维空间的范数等价定 理有限维空间的范数等价定 理ISCM 2007,Beiji ng China2015-2016学年课程 数值分析 Numerical Analysis§6.2 范数与误差分析ISCM 2007,Beiji ng China2015-2016学年课程 数值分析 Numerical AnalysisØ 当不需要指明使用哪一种向量范数时，就用记号 泛指任何一种向量范数。Ø 有了向量的范数就可以用它来衡量向量的大小和表示向量的误差。Ø 设x*为Ax=b的精确解，x为其近似解，则其绝对误差可表示成 ，其相对误差可表示成ISCM 2007,Beiji ng China2015-2016学年课程 数值分析 Numerical Analysis定义6.2.2 ( 向量序列的极限 ) 设 为 中的一向量序列， , 记。如果 ，则称 收敛于向量 ，记为ISCM 2007,Beiji ng China2015-2016学年课程 数值分析 Numerical Analysis定理6.2.3 其中 为向量中的任一种范数。 证 由于 而对于 上的任一种 范数, 由定理6.2.2 知存在常数C1，C2，使 于是可得 向量序列依范数收敛与依坐标收敛是等价的。ISCM 2007,Beiji ng China2015-2016学年课程 数值分析 Numerical Analysis定义在Rn上的向量范数 是变量X分量的连续函数。定理6.2.4ISCM 2007,Beiji ng China2015-2016学年课程 数值分析 Numerical Analysis§6.2 范数与误差分析 （二、矩阵范数）§6.2.2 矩阵范数ISCM 2007,Beiji ng China2015-2016学年课程 数值分析 Numerical Analysis§6.2 范数与误差分析ISCM 2007,Beiji ng China2015-2016学年课程 数值分析 Numerical Analysis§6.2 范数与误差分析证明:(1)ISCM 2007,Beiji ng China2015-2016学年课程 数值分析 Numerical Analysis§6.2 范数与误差分析证明:(2)矩阵范数和向量 范数的相容性ISCM 2007,Beiji ng China2015-2016学年课程 数值分析 Numerical AnalysisISCM 2007,Beiji ng China2015-2016学年课程 数值分析 Numerical Analysis§6.2 范数与误差分析与前述三种向量范数相容的三种矩阵范数：ISCM 2007,Beiji ng China2015-2016学年课程 数值分析 Numerical Analysis§6.2 范数与误差分析,X=-3 5T, 求A、X的“1-范数”,“2-范数”和“无穷范数”例6.2.5ISCM 2007,Beiji ng China2015-2016学年课程 数值分析 Numerical Analysis§6.2 范数与误差分析1 = 26.1803, 2 = 3.8197ISCM 2007,Beiji ng China2015-2016学年课程 数值分析 Numerical Analysis§6.2 范数与误差分析矩阵的谱半径ISCM 2007,Beiji ng China2015-2016学年课程 数值分析 N