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

1、科大研究生学位课程,1,第2章 解线性方程组的迭代法,n元线性方程组,（2.1）,或,Ax=b, 如何建立迭代格式？ 收敛速度？ 向量序列的收敛条件？ 误差估计？,（2.2）,科大研究生学位课程,2,2.1 迭代法的一般理论,为了研究线性方程组近似解的误差估计和迭代法的收敛性，我们需要对Rn(n维向量空间)中的向量或Rnxn中矩阵的“大小”引入一种度量，向量和矩阵的范数。,在一维数轴上，实轴上任意一点x到原点的距离用|x|表示。而任意两点x1，x2之间距离用| x1-x2 |表示。,科大研究生学位课程,3,向量和矩阵的范数,而在二维平面上，平面上任意一点P(x,y)到原点的距离用 表示。而平面

2、上任意两点P1(x1,y1),P2(x2,y2)的距离用 表示。 推广到n维空间，则称为向量范数。,科大研究生学位课程,4,2.1.1 向量和矩阵的范数,向量的范数,定义2.2 设是向量空间Rn上的实值函数, 且满足条件:,(1)非负性: 对任何向量xRn ,x0 ,且x=0当 且仅当x=0,(2)齐次性: 对任何向量x Rn 和实数 , x=| |x,(3)三角不等式: 对任何向量x ,yRn x+yx+y,则称为空间Rn上的范数,x为向量x的范数.,科大研究生学位课程,5,记x=(x1,x2,xn)T, 常用的向量范数有:,向量的1-范数:x1=|x1|+|x2|+|xn|,向量的2-范数

3、:x2=,向量的-范数:x=,例 设向量x=(2,-4,3,1)T, 求向量范数xp ,p=1,2, .,解 由定义x1=10 , x2=,x=4 .,虽然不同范数的值可能不同，但它们间存在等价关系.,定理 (范数的等价性),对于 Rn 上的任何两种范数和 ,存在正常数m,M,使得 m x x M x , xRn,科大研究生学位课程,6,常用的三种向量范数满足如下等价关系 x x1 nx , xRn,定义 设向量序列,k=1, 2,向量,如果,则称向量序列x(k)收敛于向量x*, 记作,易见,科大研究生学位课程,7,2.矩阵的范数,定义2.3 设是以n阶方阵为变量的实值函数,且满足条件:,(1

4、)非负性: A0 ,且A=0当且仅当A=0,(2)齐次性: A=| |A, R,(3)三角不等式:A+BA+B,(4)相容性:ABAB,则称A为矩阵A的范数.,记A=(aij) , 常用的矩阵范数有:,矩阵的1-范数:A1,也称矩阵的列范数.,矩阵的2-范数:A2,也称为谱范数.,科大研究生学位课程,8,矩阵的-范数:A,也称为行范数.,矩阵的F-范数:AF,例 设矩阵,求矩阵A的范数Ap ,p=1,2, ,F.,解 A1=4 , A=5 , AF,科大研究生学位课程,9,设是一种向量范数, 则定义,称之为由向量范数派生的矩阵算子范数.,矩阵的算子范数满足,AxAx, xRn,把满足上式的矩阵

5、范数称为与向量范数相容的矩阵范数.,对于p=1,2,矩阵范数Ap是由向量范数xp派生的矩阵算子范数,所以Ap是与xp相容的矩阵范数.但AF不是一种算子范数,却与x2是相容的.,设是一种算子范数, 则,科大研究生学位课程,10,矩阵的范数与矩阵的特征值之间也有密切的联系.,设是矩阵A的特征值,x是对应的特征向量,则有,Ax= x,利用向量和矩阵范数的相容性, 则得,|x=x=AxAx,于是 |A,设n阶矩阵A的n个特征值为1, 2, , n, 则称,为矩阵A的谱半径.,对矩阵的任何一种相容范数都有, (A)A,另外, 0, 一种相容范数, 使 A (A)+,科大研究生学位课程,11,任何两种矩阵

6、范数也具有等价性 m A A M A , ARnn,矩阵序列的收敛性也定义为,科大研究生学位课程,12,科大研究生学位课程,13,把n元线性方程组,（2.1）,或,Ax=b,改写成等价的方程组,或 x=Mx+f,2.1.2 迭代格式的构造,（2.2）,科大研究生学位课程,14,由此建立方程组的迭代格式 x(k+1)=Mx(k)+f , k=0,1,2, (2.5) 其中M称为迭代矩阵。,对任意取定的初始向量x(0),由(2.5)式可逐次算出迭代向量x(k),k=1,2,如果向量序列x(k) 收敛于x*,由(2.5)式可得,x*=Mx*+f,从而x*是方程组x=Mx+f 的解,也就是方程组Ax=

7、b的解.,对迭代格式(2.5),定义误差向量 e(k)=x(k)-x*, 则迭代法收敛就是e(k)0.,由于,x(k+1)=Mx(k)+f k=0,1,2,x*=Mx*+f k=0,1,2,科大研究生学位课程,15,x(k+1)=Mx(k)+f k=0,1,2,x*=Mx*+f k=0,1,2,所以,e(k+1)=Me(k) , k=0,1,2,递推可得,e(k)=Mke(0) , k=0,1,2,可见,当k时, e(k)0 Mk O.,对任意初始向量x(0),迭代法收敛(M)1.,定理2.4,证: (必要性）,若(M)0,使得(M)+1.则由定理2.2 MkMk (M)+)k 0.,若Mk0

8、,k(M)=(Mk)Mk0,所以(M)1.,科大研究生学位课程,16,若M1,则对任意x(0),迭代法收敛,而且,定理2.5-6,证 由于 x(k+1)=Mx(k)+f , x(k)=Mx(k-1)+f x*=Mx*+f,所以 x(k+1) -x(k)=M(x (k) -x(k-1) ) , x(k+1) x*=M(x (k) x* ),于是有 x(k+1) -x(k) Mx (k) -x(k-1) x(k+1) x*Mx (k) x*,x(k+1) -x(k) =(x (k+1) x* )-(x(k) x* ) x (k) x*-x(k+1) x*,(1-M)x(k) x*,科大研究生学位课

9、程,17,所以,上述定理只是收敛的充分条件,并不必要,如,则M1=1.2,M=1.3,M2=1.09,MF=1.17,但(M)=0.81,所以迭代法是收敛的.,由(2.10)式可见,M越小收敛越快,且当x (k) -x(k-1) 很小时,x(k) x*就很小,实际上用x (k) -x(k-1) 作为迭代终止的条件.,科大研究生学位课程,18, 即,若使x(k) x* ,只需,可以事先估计达到某一精度需要迭代多少步.,线性方程组的迭代法主要有Jocobi迭代法、Gauss-Seidel迭代法和超松弛(Sor)迭代法.,科大研究生学位课程,19,2.2雅克比（Jacobi）迭代法,若系数矩阵非奇异

10、，且 (i = 1, 2, n)，将方程组,改成,科大研究生学位课程,20,然后写成迭代格式,（2.11）,（2.11）式也可以简单地写为,（2.11）,科大研究生学位课程,21,写成矩阵形式：,L,U,D,Jacobi 迭代阵,(2.12),科大研究生学位课程,22,算法2.1（Jacobi迭代法）：,程序见P19。,科大研究生学位课程,23,2.2.2 Jacobi迭代法的收敛条件,迭代格式收敛(B)1 。若B1迭代法收敛.,定理：若系数矩阵A满足下列条件之一，则Jacobi迭代收敛。,A为行对角占优阵,A为列对角占优阵, A满足,对于Jacobi迭代，我们有一些保证收敛的充分条件.,引理

11、 若A是严格对角占优矩阵, 则det(A)0.,证 A=D-L-U=D(I-D-1(L+U)=,因为A是严格对角占优矩阵, 所以det(D)0, 而且,因此, (B)B1,故=1不是B的特征值,det(I-B)0.,所以, det(A)0.,D(I-B),科大研究生学位课程,24,证明：, 由条件知，A为列对角占优阵，则AT为行对角占优阵，有,证毕,A为行对角占优阵,A为列对角占优阵,科大研究生学位课程,25,为了加快收敛速度，同时为了节省计算机的内存，我们作如下的改进：每算出一个分量的近似值，立即用到下一个分量的计算中去，即用迭代格式：,2.3 高斯赛得尔(Gauss-Seidel)迭代法,

12、逐一写出来即为,科大研究生学位课程,26, ,只存一组向量即可。,写成矩阵形式：,Gauss-Seidel 迭代阵,2.3 高斯赛得尔(Gauss-Seidel)迭代法,(2.14),(2.16),科大研究生学位课程,27,程序见P23。,算法2.2（Gauss-Seidel迭代法）：,科大研究生学位课程,28,例 用雅可比迭代法解方程组,解：雅 可 比 迭 代 格式为,科大研究生学位课程,29,科大研究生学位课程,30,解：,Gauss-Seidel,迭代格式为,例 用GaussSeidel 迭代法解上题。,科大研究生学位课程,31,取 x(0)=(0,0,0)T 计算如下：,科大研究生学位

13、课程,32,2.3.2 收敛条件,我们看一下Gauss-Seidel迭代法收敛的充分条件,定理：若A满足下列条件之一，则Seidel i迭代收敛。,A为行或列对角占优阵,A对称正定阵（证略书上定理2.9）,迭代格式收敛(B)1 。若B1迭代法收敛.,det(I-B)= det(I-(D-L)-1U),证明：,= det(D-L)-1)det(D-L)-U)=0,所以有 det(D-L)-U)=0,科大研究生学位课程,33,若|1, 则矩阵(D-L)-U 是严格对角占优矩阵, 这与 det(D-L)-U)=0矛盾, 所以|1,于是(B)1.,注：二种方法都存在收敛性问题。 有例子表明：Gauss

14、-Seidel法收敛时，Jacobi法可能不收敛；而Jacobi法收敛时， Gauss-Seidel法也可能不收敛。,科大研究生学位课程,34,2.4 逐次超松弛迭代法,记,则,可以看作在前一步上加一个修正量。若在修正量前乘以一个因子,，有,对GaussSeidel迭代格式,(2.22),科大研究生学位课程,35,故SOR的迭代格式,（2.23）,SOR的迭代矩阵,科大研究生学位课程,36,用分量形式讨论，设,加速,（迭代公式）,是松驰因子(01时叫超松弛， =1时，就是Gauss-Seidel迭代法。,科大研究生学位课程,37,程序见P28。,算法2.3（SOR迭代法）：,科大研究生学位课程

15、,38,例 用SOR方法解线性方程组,解 SOR方法迭代公式为,方程组的精确解是x*=(2,1,-1)T.,取x(0)=(0,0,0)T,=1.46,计算结果如下:,科大研究生学位课程,39,从结果可见 ,迭代20次时已获得精确到小数点后五位的近似解.如果取=1.25,则需要迭代56次才能得到具有同样精度的近似解;如果取=1,则需迭代110次以上.,科大研究生学位课程,40,2.4.2 SOR迭代法的收敛条件,迭代格式收敛(B)1 。若B1迭代法收敛.,对于SOR迭代，我们有一些收敛的结果.,定理2.10 SOR方法收敛的必要条件是02.,证 设SOR方法收敛, 则(B)1,所以|det(B)

16、| =|12 n|1,而 det(B) =det(D-L)-1 (1-)D+U),=det(I-D-1L)-1 det(1-)I+D-1U),=(1-)n,于是 |1-|1, 或 02,科大研究生学位课程,41,定理2.11 设A是对称正定矩阵, 则当02时,解方程组Ax=b的SOR方法收敛.,证 设是B的任一特征值, y是对应的特征向量, 则,(1-)D+Uy= (D-L)y,于是 (1-)(Dy,y)+(Uy,y)=(Dy,y)-(Ly,y),由于A=D-L-U是对称正定的, 所以D是正定矩阵, 且L=UT. 若记(Ly,y)=+i, 则有,(Dy,y)= 0,科大研究生学位课程,42,(Dy,y)= 0,(Uy,y)=(y,Ly)=(Ly,y),=-i,0(Ay,y)=(Dy,y)-(Ly,y)-(Uy,y) =-2,所以,当02时,有,(-+)2-(-)2= (2-)(2-) = (2-)(2-)0,所以|21, 因此(B)1,即S0R方法收敛.,科大研究生学位课程,43,推论2.1 A是对称正定矩阵, Jacobi迭代法收敛的充要条件是2D-A也对称正定。,证,设是Jac