Chap7.迭代解法(全章).ppt

2019/7/11,第六章 线性方程组的迭代解法,1,第六章 线性方程组的迭代解法,1 向量和矩阵的范数 1.1 向量的范数 1.2 矩阵的范数 2 迭代解法与收敛性 2.1 迭代法的构造 2.2 迭代法的收敛性条件 3 常用的三种迭代解法 2.1 Jacobi迭代法 2.2 Gauss-Seidel迭代法 2.2 超松弛(SOR)迭代法,2019/7/11,第六章 线性方程组的迭代解法,2,1 向量和矩阵的范数,一、向量的范数,为了对线性方程组数值解的精确程度，以及方程组本身的性态进行分析，需要对向量和矩阵的“大小”引进某种度量，范数就是一种度量尺度，向量和矩阵的范数在线性方程组数值方法的研究中起着重要的作用。,定义6.1设|是向量空间Rn上的实值函数，且满足条件,求解线性方程组的数值解除了使用直接解法，迭代解法也是经常采用的一种方法，这种方法更有利于编程计算，本章将介绍这种方法。,2019/7/11,第六章 线性方程组的迭代解法,3,则称 | 为 Rn 空间上的范数，| x |为向量 x 的范数。,理论上存在多种多样的向量范数，但最常用的是如下三种。,（2）齐次性：对任何实数和向量x | x| | | x |,（3）三角不等式：对任何向量x和y，都有 | xy | x | y |,设向量x（x1，x2，xn）T，定义,（1）非负性：对任何向量 x， | x |0，且| x |0当且仅当x0,2019/7/11,第六章 线性方程组的迭代解法,4,向量1-范数：,向量2-范数：,向量-范数：,容易验证，以上三种范数都满足向量范数的三个条件。,例6.1 设向量x（1，3，2，0）T，求向量范数| x |p，P1，2，。,第六章 线性方程组的迭代解法,5,解:对于 向量 x(1，3，2，0)T ，根据定义可以计算出：,| x|1| 1 |3 | 2 | 0 |6,由此例可见，向量不同范数的值不一定相同，但这并不影响对向量大小做定性的描述，因为不同范数之间存在如下等价关系。,2019/7/11,第六章 线性方程组的迭代解法,6,定理6.1 （范数的等价性）对于Rn上任何两种范数|和|，存在着正常数 m，M，使得：,范数的等价性表明，一个向量若按某种范数是一个小量，则它按任何一种范数也将是一个小量。容易证明，常用的三种向量范数满足下述等价关系。,| x | | x |1 n| x |,| x | | x |2 | x |,| x | 2| x |1 n| x |2,例如：,2019/7/11,第六章 线性方程组的迭代解法,7,定义6.2 对于向量序列,向量序列 x(k) 收敛于向量 x*，当且仅当它的每一个分量序列收敛于x*的对应分量，即,及向量,如果,则称向量序列 x(k) 收敛于向量 x* 。记作,或,2019/7/11,第六章 线性方程组的迭代解法,8,二、矩阵的范数,矩阵范数是反映矩阵“大小”的一种度量，具体定义如下。,定义6.3 设|是以n阶矩阵为变量的实值函数，且满足条件：,（1）| A |0，且| A |0时，当且仅当A0 （2）|A| | A|，R （3）|AB| | A | B | （4）| AB | A | | B | 则称| A |为矩阵A的范数。,2019/7/11,第六章 线性方程组的迭代解法,9,设 n 阶矩阵 A（aij），常用的矩阵范数有：,矩阵1-范数：,矩阵2-范数：,矩阵-范数：,以上三种范数都满足矩阵范数的条件，通常将这三种矩阵范数统一表示为| A |p，P1，2，。,2019/7/11,第六章 线性方程组的迭代解法,10,例6.2 设矩阵,求矩阵A的范数| A |p，P1，2，。,解 根据定义,由于,则它的特征方程为:,2019/7/11,第六章 线性方程组的迭代解法,11,此方程的根为矩阵ATA的特征值，解得,因此,在线性方程组的研究中，经常遇到矩阵与向量的乘积运算，若将矩阵范数与向量范数关联起来，将给问题的分析带来许多方便。设|是一种向量范数，由此范数派生的矩阵范数定义为,注意，此式左端|A|表示矩阵范数，而右端是向量Ax 和 x 的范数，利用向量范数所具有的性质不难验证，由上式定义的矩阵范数满足矩阵范数的条件。,2019/7/11,第六章 线性方程组的迭代解法,12,通常将满足上式的矩阵范数称为与向量范数相容的矩阵范数。,可以证明，前述的三种矩阵范数| A |p，P1，2， 就是由向量范数| x |p派生出的矩阵范数，即,通过向量范数定义的矩阵范数，满足不等式关系：,均为相容范数，即,2019/7/11,第六章 线性方程组的迭代解法,13,三、矩阵的谱半径,矩阵范数同矩阵特征值之间有密切的联系，设是矩阵A相应于特征向量x的特征值，即 Axx,于是利用,向量-矩阵范数的相容性，得到,| | x |x|,从而，对A的任何特征值均成立,=| Ax|, | A | |x|,| A | （6.1）,设n阶矩阵A的n个特征值为1,2，n。称,为矩阵A的谱半径，从（6.1）式得知，对矩阵A的任何一种相容范数都有 (A)|A| （6.2）,2019/7/11,第六章 线性方程组的迭代解法,14,另一个更深刻的结果,对于任意的0，必存在一种相容的矩阵范数，使,| A | (A) （6.3）,式（6.2）和（6.3）表明，矩阵A的谱半径是它所有相容范数的下确界。,定义6.4 设有矩阵序列 和矩阵A（aij）。称 A（k）收敛于A，如果,记作 A（k）A，或 A（k）A。,2019/7/11,第六章 线性方程组的迭代解法,15,四、矩阵的条件数,引进了矩阵的度量标准范数，就可以对方程组求解进行误差分析，对于方程组,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|,2019/7/11,第六章 线性方程组的迭代解法,16,于是，由 | x |A-1 | |b|,得到解的相对误差为,及 |b | |A | |x|,令 Cond(A)=|A | |A-1 | ,并称其为矩阵A的条件数。,这时,可见，求解线性方程组所产生的误差与系数矩阵的条件数有关。,2019/7/11,第六章 线性方程组的迭代解法,17,对于线性方程组 Ax=b，如果系数矩阵的条件数Cond(A)=|A | |A-1 | 太大，则称相应的方程组为病态方程组。,病态现象是方程组的固有属性，无法改变，因此在求解时为了不至于产生太大的误差，应该尽量减少原始数据 A、b 的误差，或者用高精度的计算机计算。,例如：对于方程组,系数矩阵和逆矩阵分别为,可以求得,条件数比较大，可见该方程组为病态方程组。,2019/7/11,第六章 线性方程组的迭代解法,18,2 迭代解法与收敛性,一、迭代解法,设有线性方程组 AX=b (1),ARnn, bR .,对A 进行分裂，,A=A1+A2 ,其中 A1 可逆，,则 (A1+A2)x=b A1x = - A2x+b,令 B= - A1-1 A2 , F =A1-1 b,则 x= Bx+F （2）, x = - A1-1 A2 x + A1-1 b,2019/7/11,第六章 线性方程组的迭代解法,19,得到 x(1)= Bx(0)+F,称(3)为求解(1)的近似解的迭代解法，称x(k)为(1)近似解序列，称B为迭代矩阵。, x(2)= Bx(1)+F, x(k+1)= Bx(k)+F , k=0 ,1 , , （3）,x*= Bx*+F （4）,我们称迭代法(3)收敛，否则为发散。下面分析迭代格式(3)收敛的条件.,由 x= Bx+F,x(0)Rn,2019/7/11,第六章 线性方程组的迭代解法,20,由(3) (4)得 x(k+1) - x* = B(x(k)- x* ),令 e(k)= x(k)- x* , 则有,若 x(k+1) x* ,则 e(k) 0。,这时只有 Bk+1 0 （k ）。,而 Bk+1 0 (B)1，由此可得如下的收敛性条件。,2019/7/11,第六章 线性方程组的迭代解法,21,二、迭代法收敛性条件,x(k+1)= Bx(k)+F , k=0 ,1 , , （3）,定理6.3 若 |B|1 ，则迭代法(3)收敛.,定理6.4 若 |B|1 ，则有估计式,定理6.2 迭代法格式(3)收敛的充要条件是(B)1.,这是一个充分条件，根据范数与谱半径的关系式 (A)|B| ，容易推出该充分条件.,2019/7/11,第六章 线性方程组的迭代解法,22,3 常用的三种迭代解法,一、Jacobi迭代法,对于线性方程组 Ax=b (1),A=L+D+U (2),设 det(A) 0 ，aii 0,i=0,1,2,n ，按照如下方式对A进行分裂：,2019/7/11,第六章 线性方程组的迭代解法,23,则由 Ax=b 得到,令 BJ=-D-1(L+U) ， FJ= D-1 b.,(L+D+U) x=b, D x=-(L+U)x+b, x=-D-1(L+U)x+ D-1 b,则有 x= BJ x+ FJ (3),任取初始向量 x(0)Rn , 则可以由上式得到如下的迭代格式：,并称其为Jacobi迭代格式，迭代矩阵为,x(k+1)= BJ x(k)+ FJ (4),BJ=-D-1(L+U),= -D-1(A - D),= E - D-1 A,2019/7/11,第六章 线性方程组的迭代解法,24,例如, 对于三元线性方程组,2019/7/11,第六章 线性方程组的迭代解法,25,得到具体的迭代格式,由定理6.4的结论,可以通过| x(k+1)-x(k)|控制迭代次数。,x(0)Rn,2019/7/11,第六章 线性方程组的迭代解法,26,对于 n 元线性方程组,其一般式为：,从中解出：,得Jacobi迭代格式,通过| x(k+1)-x(k)| 控制迭代次数。,2019/7/11,第六章 线性方程组的迭代解法,27,二、 Gauss-Seidel迭代法,对于三元方程组，将Jacobi迭代格式,改进为,并称其为Gauss-Seidel迭代格式。,2019/7/11,第六章 线性方程组的迭代解法,28,对于n元方程,先写出Jacobi迭代格式,同样可以用 | x(k+1)-x(k)| 控制迭代次数。,再写出Gauss-Seidel迭代格式,2019/7/11,第六章 线性方程组的迭代解法,29,为讨论收敛性方便，下面再写出Gauss-Seidel迭代格式的矩阵表示式。首先改写Gauss-Seidel迭代格式,为：,2019/7/11,第六章 线性方程组的迭代解法,30,令,则有,其中 BG 为迭代矩阵。,例6.3 用Jacobi迭代法和Gauss-Seidel迭代法解下列方程组,已知方程组得精确解为 x*=(1，1，1)T 。,2019/7/11,第六章 线性方程组的迭代解法,31,解：先改写方程如下,再写出Jacobi迭代格式,取初值为: x(0)=(0，0，0)T , 求得:,x(1)=(1.4，0.5，1.4)T,x(6)=(1.00025，1.00580，1.00251)T,误差为由x*=(1，1，1)T 得到 |x(6)-x*|=0.00580 。,2019/7/11,第六章 线性方程组的迭代解法,32,初值也取为: x(0)=(0，0，0)T , 求得近似解：,Gauss-Seidel迭代格式为,误差为由x*=(1，1，1)T 得到 |x(4)-x*|=0.00846 。,Jacobi迭代法迭代6次与Gauss-Seidel迭代法迭代4次的精度一致，说明Gauss-Seidel迭代法收敛的较快。,x(1)=(1.4，0.78，1.026)T,x(4)=(0.99154，0.99578，1.00210)T,2019/7/11,第六章 线性方程组的迭代解法,33,三.超松弛(SOR)迭代法 (Successive Over Relaxation Method),对Gauss-seidel迭代进行改写,令,2019/7/11,第六章 线性方程组的迭代解法,34,再通过加权加速收敛：,并称其为超松弛迭代法，称为松弛因子。,当 0 1 时，称为低松弛；,当 =1 时，为Gauss-Seidel 迭代格式 ；,当 1 2 时，称为高松弛。,2019/7/11,第六章 线性方程组的迭代解法,35,超松弛迭代法(SOR)也可以用矩阵的形式来表示,令 B =(D+ L)-1D- (D+U),则有 x(k+1)=B x(k)+F , k=0,1, 2 , 。,改写SOR,为,或者,F = (D+wL)-1 b,2019/7/11,第六章 线性方程组的迭代解法,36,定理6.6 Gauss-Seidel 迭代法 收敛的充要条件是(BG)1 ，收敛的充分条件是 |BG|1 。,定理6.7 对于 线性方程组 AX=b ，如果系数矩阵A严格对角占优，则Jacobi、G-S迭代法都收敛。,定理6.8 SOR迭代法收敛的必要条件是 0 2 。,定理6.9 如果系数矩阵A对称正定，且 0 2 ，则SOR 法收敛,定理6.10 如果系数矩阵A对称正定，则G-S迭代法收敛。,四、收敛性条件,定理6.5 Jacobi迭代法收敛的充要条件是(BJ)1 ，收敛的充分条件是 |BJ |1 。,2019/7/11,第六章 线性方程组的迭代解法,37,例6.4 分别用Jacobi迭代法和Gauss-Seidel迭代法解下列方程组是否收敛？,解：由于第一个方程组的系数矩阵严格对角占优，所以Jacobi迭代法和Gauss-Seidel迭代法均收敛。,第二个方程组的系数矩阵不是严格对角占优的，但可以交换两个方程的次序，将原方程变为同解方程组：,这时方程组得系数矩阵严格对角占优，两种迭代法都收敛。,2019/7/11,第六章 线性方程组的迭代解法,38,例6.5 用Jacobi迭代法解下列方程组，问是否收敛？,解：方程组的系数矩阵为,非严格对角占优，无法判断迭代法是否收敛。需要通过谱半径判断，先写出Jacobi迭代法的迭代矩阵：,由于无穷范数 |BJ |=31,还无法判断迭代法是否收敛。,2019/7/11,第六章 线性方程组的迭代解法,39,这时只能通过求迭代矩阵的谱半径来判断，由迭代矩阵,解得特征值,谱半径 (BJ)1,故Jacobi迭代法收敛.,2019/7/11,第六章 线性方程组的迭代解法,40,例6.6 分别用Jacobi迭代法和Gauss-Seidel迭代法解下列方程组，问是否收敛？,由于该矩阵非严格对角占优，无法判断；但由于对称，再看是否正定。,解：系数矩阵为,各阶顺序主子式 |A1|=1, |A2|=3/4, |A3|=1/2, 说明矩阵对称正定,所以Gauss-Seidel迭代法收敛。但无法判断Jacobi迭代法是否收敛，再利用迭代矩阵的范数或者谱半径进行判断。,2019/7/11,第六章 线性方程组的迭代解法,41,由系数矩阵,写出Jacobi迭代矩阵,其-范数 |BJ |=1 和 1-范数|BJ |1=1，不小于1，还无法判断是否收敛。再求其谱半径进行判断。,由 det(I-BJ)=0 求得特征值1 = -1，2= 3=0.5,谱半径 (BJ)=|1| = 1，由此可知Jacobi迭代法是发散的。,2019/7/11,第六章 线性方程组的迭代解法,42,例6.7 取初值 x(0)=(0，0，0)T 用Jacobi迭代法解下列方程组，如果要保证各分量的误差的绝对值小于10-6,问需要迭代多少次？,解：由于方程组得系数矩阵严格对角占优，所以Jacobi迭代法收敛。要确定迭代次数需要用到估计式,其中 BJ=E-D-1A ， FJ= D-1 b，范数用-范数 。,2019/7/11,第六章 线性方程组的迭代解法,43