Chap7迭代解法(全章)讲解课件

1、第六章 线性方程组的迭代解法1 向量和矩阵的范数 1.1 向量的范数 1.2 矩阵的范数2 迭代解法与收敛性 2.1 迭代法的构造 2.2 迭代法的收敛性条件3 常用的三种迭代解法 2.1 Jacobi迭代法 2.2 Gauss-Seidel迭代法 2.2 超松弛(SOR)迭代法10/10/20221第六章 线性方程组的迭代解法第六章 线性方程组的迭代解法1 向量和矩阵的范数 101 向量和矩阵的范数一、向量的范数 为了对线性方程组数值解的精确程度，以及方程组本身的性态进行分析，需要对向量和矩阵的“大小”引进某种度量，范数就是一种度量尺度，向量和矩阵的范数在线性方程组数值方法的研究中起着重要的

2、作用。 定义6.1设|是向量空间Rn上的实值函数，且满足条件 求解线性方程组的数值解除了使用直接解法，迭代解法也是经常采用的一种方法，这种方法更有利于编程计算，本章将介绍这种方法。10/10/20222第六章 线性方程组的迭代解法1 向量和矩阵的范数一、向量的范数 为则称 | 为 Rn 空间上的范数，| x |为向量 x 的范数。 理论上存在多种多样的向量范数，但最常用的是如下三种。（2）齐次性：对任何实数和向量x | x| | | x |（3）三角不等式：对任何向量x和y，都有 | xy | x | y |设向量x（x1，x2，xn）T，定义 （1）非负性：对任何向量 x， | x |0，且

3、| x |0当且仅当x010/10/20223第六章 线性方程组的迭代解法则称 | 为 Rn 空间上的范数，| x |为向向量1-范数： 向量2-范数： 向量-范数： 容易验证，以上三种范数都满足向量范数的三个条件。 例6.1 设向量x（1，3，2，0）T，求向量范数| x |p，P1，2，。 10/10/20224第六章 线性方程组的迭代解法向量1-范数： 向量2-范数： 向量-范数： 容易验证，以 解:对于 向量 x(1，3，2，0)T ，根据定义可以计算出： | x|1| 1 |3 | 2 | 0 |6 由此例可见，向量不同范数的值不一定相同，但这并不影响对向量大小做定性的描述，因为不同

4、范数之间存在如下等价关系。 10/10/20225第六章 线性方程组的迭代解法 解:对于 向量 x(1，3，2，0)T 定理6.1 （范数的等价性）对于Rn上任何两种范数|和|，存在着正常数 m，M，使得： 范数的等价性表明，一个向量若按某种范数是一个小量，则它按任何一种范数也将是一个小量。容易证明，常用的三种向量范数满足下述等价关系。 | x | | x |1 n| x | x | | x |2 | x | x | 2| x |1 n| x |2 例如：10/10/20226第六章 线性方程组的迭代解法 定理6.1 （范数的等价性）对于Rn上任何两定义6.2 对于向量序列 向量序列 x(k)

5、 收敛于向量 x*，当且仅当它的每一个分量序列收敛于x*的对应分量，即 及向量如果则称向量序列 x(k) 收敛于向量 x* 。记作 或10/10/20227第六章 线性方程组的迭代解法定义6.2 对于向量序列 向量序列 x二、矩阵的范数 矩阵范数是反映矩阵“大小”的一种度量，具体定义如下。 定义6.3 设|是以n阶矩阵为变量的实值函数，且满足条件： （1）| A |0，且| A |0时，当且仅当A0 （2）|A| | A|，R （3）|AB| | A | B | （4）| AB | A | | B |则称| A |为矩阵A的范数。10/10/20228第六章 线性方程组的迭代解法二、矩阵的范数

6、 矩阵范数是反映矩阵“大小”的一种度量，具设 n 阶矩阵 A（aij），常用的矩阵范数有： 矩阵1-范数： 矩阵2-范数： 矩阵-范数： 以上三种范数都满足矩阵范数的条件，通常将这三种矩阵范数统一表示为| A |p，P1，2，。 列和行和10/10/20229第六章 线性方程组的迭代解法设 n 阶矩阵 A（aij），常用的矩阵范数有： 矩阵1-例6.2 设矩阵求矩阵A的范数| A |p，P1，2，。 解 根据定义 由于则它的特征方程为: 10/10/202210第六章 线性方程组的迭代解法例6.2 设矩阵求矩阵A的范数| A |p，P1，2此方程的根为矩阵ATA的特征值，解得 因此 在线性方程

7、组的研究中，经常遇到矩阵与向量的乘积运算，若将矩阵范数与向量范数关联起来，将给问题的分析带来许多方便。设|是一种向量范数，由此范数派生的矩阵范数定义为 注意，此式左端|A|表示矩阵范数，而右端是向量Ax 和 x 的范数，利用向量范数所具有的性质不难验证，由上式定义的矩阵范数满足矩阵范数的条件。10/10/202211第六章 线性方程组的迭代解法此方程的根为矩阵ATA的特征值，解得 通常将满足上式的矩阵范数称为与向量范数相容的矩阵范数。 可以证明，前述的三种矩阵范数| A |p，P1，2，就是由向量范数| x |p派生出的矩阵范数，即通过向量范数定义的矩阵范数，满足不等式关系：均为相容范数，即1

8、0/10/202212第六章 线性方程组的迭代解法通常将满足上式的矩阵范数称为与向量范数相容的矩阵范数。 三、矩阵的谱半径 矩阵范数同矩阵特征值之间有密切的联系，设是矩阵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）10/10/202213第六章 线性方程组的迭代解法三、矩阵的谱半径 矩阵范数同矩阵特征值之间有密切的联系， 另一个更深

9、刻的结果,对于任意的0，必存在一种相容的矩阵范数，使| A | (A) （6.3） 式（6.2）和（6.3）表明，矩阵A的谱半径是它所有相容范数的下确界。 定义6.4 设有矩阵序列 和矩阵A（aij）。称 A（k）收敛于A，如果 记作 A（k）A，或 A（k）A。 10/10/202214第六章 线性方程组的迭代解法 另一个更深刻的结果,对于任意的0，必存四、矩阵的条件数 引进了矩阵的度量标准范数，就可以对方程组求解进行误差分析，对于方程组Ax =b如果常数项产生了误差b, 并设求解时产生的误差为x，则有A(x + x) =b+ b两式相减得到 A x = b当系数矩阵可逆时x = A-1b取

10、范数|x| = |A-1b|A-1 | |b|再由 Ax =b，得到| b|= | Ax |A | |x|10/10/202215第六章 线性方程组的迭代解法四、矩阵的条件数 引进了矩阵的度量标准范数，于是，由 | x |A-1 | |b|得到解的相对误差为及 |b | |A | |x|令 Cond(A)=|A | |A-1 | ,并称其为矩阵A的条件数。这时可见，求解线性方程组所产生的误差与系数矩阵的条件数有关。10/10/202216第六章 线性方程组的迭代解法于是，由 | x |A-1 | |b| 对于线性方程组 Ax=b，如果系数矩阵的条件数Cond(A)=|A | |A-1 | 太大

11、，则称相应的方程组为病态方程组。 病态现象是方程组的固有属性，无法改变，因此在求解时为了不至于产生太大的误差，应该尽量减少原始数据 A、b 的误差，或者用高精度的计算机计算。例如：对于方程组系数矩阵和逆矩阵分别为可以求得条件数比较大，可见该方程组为病态方程组。10/10/202217第六章 线性方程组的迭代解法 对于线性方程组 Ax=b，如果系数矩阵的条件数2 迭代解法与收敛性一、迭代解法设有线性方程组 AX=b (1) ARnn, bR .对A 进行分裂， A=A1+A2 , 其中 A1 可逆，则 (A1+A2)x=b A1x = - A2x+b令 B= - A1-1 A2 , F =A1-

12、1 b则 x= Bx+F （2） x = - A1-1 A2 x + A1-1 b10/10/202218第六章 线性方程组的迭代解法2 迭代解法与收敛性一、迭代解法设有线性方程组 得到 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+Fx(0)Rn10/10/202219第六章 线性方程组的迭代解法得到 x(1)=

13、 Bx(0)+F 称(3)为求解(1)的近由(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 ）。x(k+1)= Bx(k)+F , k=0 ,1 , , （3）x*= Bx*+F （4）而 Bk+1 0 (B)1，由此可得如下的收敛性条件。10/10/202220第六章 线性方程组的迭代解法由(3) (4)得 x(k+1) - x* = B二、迭代法收敛性条件 x(k+1)= Bx(k)+F , k=0 ,1 , , （3）定理6.3 若 |B|1 ，则迭

14、代法(3)收敛. 定理6.4 若 |B|1 ，则有估计式 定理6.2 迭代法格式(3)收敛的充要条件是(B)1. 这是一个充分条件，根据范数与谱半径的关系式 (A)|B| ，容易推出该充分条件.10/10/202221第六章 线性方程组的迭代解法二、迭代法收敛性条件 x(k+1)= Bx(k)+F , 3 常用的三种迭代解法一、Jacobi迭代法对于线性方程组 Ax=b (1) A=L+D+U (2)设 det(A) 0 ，aii 0,i=0,1,2,n ，按照如下方式对A进行分裂：10/10/202222第六章 线性方程组的迭代解法3 常用的三种迭代解法一、Jacobi迭代法对于线性方程则由

15、 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 A10/10/202223第六章 线性方程组的迭代解法则由 Ax=b 得到令 BJ=-D-1(L+U) ， F例如, 对于三元线性方程组10/10/202224第六章 线性方程组的迭

16、代解法例如, 对于三元线性方程组10/9/202224第六章 线性 得到具体的迭代格式由定理6.4的结论,可以通过| x(k+1)-x(k)|控制迭代次数。x(0)Rn10/10/202225第六章 线性方程组的迭代解法 得到具体的迭代格式由定理6.4的结论,可以通过| x(k对于 n 元线性方程组其一般式为：从中解出： 得Jacobi迭代格式通过| x(k+1)-x(k)| 控制迭代次数。10/10/202226第六章 线性方程组的迭代解法对于 n 元线性方程组其一般式为：从中解出： 得Jacobi二、 Gauss-Seidel迭代法对于三元方程组，将Jacobi迭代格式改进为并称其为Gau

17、ss-Seidel迭代格式。10/10/202227第六章 线性方程组的迭代解法二、 Gauss-Seidel迭代法对于三元方程组，将Jac对于n元方程 先写出Jacobi迭代格式同样可以用 | x(k+1)-x(k)| 控制迭代次数。 再写出Gauss-Seidel迭代格式10/10/202228第六章 线性方程组的迭代解法对于n元方程 先写出Jacobi迭代格式同样可以用 | x 为讨论收敛性方便，下面再写出Gauss-Seidel迭代格式的矩阵表示式。首先改写Gauss-Seidel迭代格式为：10/10/202229第六章 线性方程组的迭代解法 为讨论收敛性方便，下面再写出Gauss-

18、Se令 则有 其中 BG 为迭代矩阵。 例6.3 用Jacobi迭代法和Gauss-Seidel迭代法解下列方程组,已知方程组得精确解为 x*=(1，1，1)T 。 10/10/202230第六章 线性方程组的迭代解法令 则有 其中 BG 为迭代矩阵。 例6.3 用解：先改写方程如下再写出Jacobi迭代格式取初值为: x(0)=(0，0，0)T , 求得:x(1)=(1.4，0.5，1.4)Tx(6)=(1.00025，1.00580，1.00251)T误差为由x*=(1，1，1)T 得到 |x(6)-x*|=0.00580 。10/10/202231第六章 线性方程组的迭代解法解：先改写方

19、程如下再写出Jacobi迭代格式取初值为: x(初值也取为: 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)Tx(4)=(0.99154，0.99578，1.00210)T10/10/202232第六章 线性方程组的迭代解法初值也取为: x(0)=(0，0，0)T , 求得近似解：三.超松弛(SOR)迭代法 (Succes

20、sive Over Relaxation Method)对Gauss-seidel迭代进行改写令 10/10/202233第六章 线性方程组的迭代解法三.超松弛(SOR)迭代法 (Successive Over再通过加权加速收敛： 并称其为超松弛迭代法，称为松弛因子。当 0 1 时，称为低松弛； 当 =1 时，为Gauss-Seidel 迭代格式 ；当 1 2 时，称为高松弛。 10/10/202234第六章 线性方程组的迭代解法再通过加权加速收敛： 并称其为超松弛迭代法，称为松弛因子。超松弛迭代法(SOR)也可以用矩阵的形式来表示令 B =(D+ L)-1D- (D+U)则有 x(k+1)=

21、B x(k)+F , k=0,1, 2 , 。改写SOR为或者F = (D+wL)-1 b10/10/202235第六章 线性方程组的迭代解法超松弛迭代法(SOR)也可以用矩阵的形式来表示令 B =( 定理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迭代法收敛。四、

22、收敛性条件 定理6.5 Jacobi迭代法收敛的充要条件是(BJ)1 ，收敛的充分条件是 |BJ |1,还无法判断迭代法是否收敛。10/10/202238第六章 线性方程组的迭代解法例6.5 用Jacobi迭代法解下列方程组，问是否收敛？ 这时只能通过求迭代矩阵的谱半径来判断，由迭代矩阵解得特征值谱半径 (BJ)1故Jacobi迭代法收敛.10/10/202239第六章 线性方程组的迭代解法这时只能通过求迭代矩阵的谱半径来判断，由迭代矩阵解得特征值谱 例6.6 分别用Jacobi迭代法和Gauss-Seidel迭代法解下列方程组，问是否收敛？ 由于该矩阵非严格对角占优，无法判断；但由于对称，再

23、看是否正定。解：系数矩阵为 各阶顺序主子式 |A1|=1, |A2|=3/4, |A3|=1/2, 说明矩阵对称正定所以Gauss-Seidel迭代法收敛。但无法判断Jacobi迭代法是否收敛，再利用迭代矩阵的范数或者谱半径进行判断。10/10/202240第六章 线性方程组的迭代解法 例6.6 分别用Jacobi迭代法和Gauss由系数矩阵写出Jacobi迭代矩阵其-范数 |BJ |=1 和 1-范数|BJ |1=1，不小于1，还无法判断是否收敛。再求其谱半径进行判断。由 det(I-BJ)=0 求得特征值1 = -1，2= 3=0.5 谱半径 (BJ)=|1| = 1，由此可知Jacobi

24、迭代法是发散的。10/10/202241第六章 线性方程组的迭代解法由系数矩阵写出Jacobi迭代矩阵其-范数 |BJ | 例6.7 取初值 x(0)=(0，0，0)T 用Jacobi迭代法解下列方程组，如果要保证各分量的误差的绝对值小于10-6,问需要迭代多少次？ 解：由于方程组得系数矩阵严格对角占优，所以Jacobi迭代法收敛。要确定迭代次数需要用到估计式其中 BJ=E-D-1A ， FJ= D-1 b，范数用-范数 。10/10/202242第六章 线性方程组的迭代解法 例6.7 取初值 x(0)=(0，0，0)T 由方程组得到系数矩阵和常数项迭代矩阵为-范数 |BJ |=1/3 1 , |FJ |