第2章 线性方程组的迭代法yjs11.ppt

2.1 迭代法的一般理论 为了研究线性方程组近似解的误差估计和迭代法的收敛性，我们需要对Rn(n维向量空间)中的向量或Rnxn中矩阵的“大小”引入一种度量，——向量和矩阵的范数。 2.1.1 向量和矩阵的范数 而在二维平面上，平面上任意一点P(x,y)到原点的距离用 表示。而平面上任意两点P1(x1,y1),P2(x2,y2)的距离用 表示。 推广到n维空间，则称为向量范数。 取 x(0)=(0,0,0)T 计算如下： 1.3 1.199999 1.099998 8 … … … … 1.1644 0.902 0.72 1 x3(k) x2(k) x1(k) k 2.3.2 Gauss-Seidel迭代法收敛条件 考察Gauss-Seidel迭代法收敛的充分条件 定理：若A满足下列条件之一，则Seideli迭代收敛。 ①A为行或列对角占优阵 ②A对称正定阵（证略书上定理2.9） 迭代格式收敛??(B)1 。若‖B‖1?迭代法收敛. det(?I-B)= det(?I-(D-L)-1U) 证明： = det((D-L)-1)det(?(D-L)-U)=0 所以有 det(?(D-L)-U)=0 若|?|?1, 则矩阵?(D-L)-U 是严格对角占优矩阵, 这与 det(?(D-L)-U)=0矛盾, 所以 |?|1,于是?(B)1. 注：二种方法都存在收敛性问题。 有例子表明：Gauss-Seidel法收敛时，Jacobi法可能不收敛；而Jacobi法收敛时， Gauss-Seidel法也可能不收敛。 例 设线性方程组Ax=b的系数矩阵 判断解Ax=b的Jacobi迭代法和G-S迭代法的收敛性。 解：易见A是严格对角占优矩阵，故J法和G-S法收敛。 1、Jacobi迭代的迭代矩阵 特征值为 2、Gauss－Siedel迭代 例 已知方程组的系数矩阵 判断解Ax=b的Jacobi迭代法和G-S迭代法的收敛性。 2.4 逐次超松弛迭代法 记 则 可以看作在前一步上加一个修正量。若在修正量前乘以一个因子 ，有 对Gauss－Seidel迭代格式有 (2.22) 故SOR(Successive Over Relaxation)的迭代格式 （2.23） SOR的迭代矩阵 用分量形式讨论，设 松弛 （2.24） ?是松驰因子(0?2), 当0?1时叫低松弛，?1时叫超松弛， ?=1时，就是Gauss-Seidel迭代法。 数值分析第2章 第2章 解线性方程组的迭代法 n元线性方程组 （2.1） 或 Ax=b 思路 与解 f (x)=0 的不动点迭代相似 ……,将Ax=b等价改写为x=Mx+f,建立迭代x(k+1)=Mx(k)+f,从初值x(0)出发，得到序列{x(k)}. 研究 内容： ? 如何建立迭代格式？　 ? 收敛速度？ ? 向量序列的收敛条件？ ? 误差估计？ （2.2） 在一维数轴上，实轴上任意一点x到原点的距离用|x|表示。而任意两点x1，x2之间距离用| x1-x2 |表示。 2.1.1 向量和矩阵的范数 向量的范数 定义2.2 设‖?‖是向量空间Rn上的实值函数, 且满足条件: (1)非负性: 对任何向量x?Rn ,‖x‖?0 ,且‖x‖=0当 且仅当x=0 (2)齐次性: 对任何向量x ?Rn 和实数? , ‖?x‖=|? |‖x‖ (3)三角不等式: 对任何向量x ,y?Rn ‖x+y‖?‖x‖+‖y‖ 则称‖?‖为空间Rn上的范数,‖x‖为向量x的范数. 记x=(x1,x2,…,xn)T, 常用的向量范数有: 向量的1-范数:‖x‖1=|x1|+|x2|+…+|xn| 向量的2-范数:‖x‖2= 向量的?-范数:‖x‖?= 例 设向量x=(2,-4,3,1)T, 求向量范数‖x‖p ,p=1,2, ?. 解 由定义‖x‖1=10 , ‖x‖2= ,‖x‖?=4 . 虽然不同范数的值可能不同，但它们间存在等价关系. 定理 (范数的等价性) 对于 Rn 上的任何两种范数‖?‖?和‖?‖? ,存在正常数m,M,使得 m ‖x‖?? ‖x‖? ?M ‖x‖? ,? x?Rn 常用的三种向量范数满足如下等价关