《数值分析课件(第6章)》由会员分享，可在线阅读，更多相关《数值分析课件(第6章)（52页珍藏版）》请在金锄头文库上搜索。
1、第6章 解线性代数方程组的迭代法,6.1 几种常用的迭代格式 6.2 迭代法收敛性理论,迭代法的基本思想:,，使得它收敛于方程组的解向量,迭代法要讨论的主要问题如下 ：,按某种规则构造一个向量序列,如何构造迭代格式,如果收敛，收敛的速率如何,构造的迭代格式所产生的序列在什么情况下收敛,近似解的误差估计,。,6.1 几种常用的迭代格式,6.1.2 Seidel迭代法,6.1.1 简单迭代法(Jacobi迭代),6.1.3 松弛迭代法(SOR迭代),6.1.1 简单迭代法(Jacobi迭代法),把,项留在左边,其它项移到右边得到,n阶线性代数方程组:,设,第i个方程两边除,得到,令,再令,则有,则
2、有,选取任意初始向量,得到一个新向量,把它代入(*)式右边,按这样做下去就会得到一个向量序列,把它代入(*)式右边又得到一个新向量,记为,它通常称为简单迭代序列或Jacobi迭代序列.,简单迭代序列中的向量可以表示为,它称为简单迭代格式或Jacobi迭代格式,称为初始迭代向量,称为简单迭代矩阵或Jacobi迭代矩阵.,即有,记为,所以由公式,得到简单迭代格式用向量分量表示的形式:,因为,或者表示为:,收敛于,对,可以证明:若由简单迭代格式所确定的向量序列,两边求极限得到,则,必为方程组,的解向量.,证,因为向量序列,所以有,收敛于,而另一方面,若令,则有,从而有,而,于是得到,从而得到简单迭代
3、格式为,例6-1 用简单迭代法解方程组,方程组的准确解是:,把方程组改写成,解,当k=0时,迭代格式为,代入得,选取初始迭代向量,当k=1时,迭代格式为,代入得,把,使用Jacobi迭代格式，得到迭代结果如下表所示:,从表中看到，近似解向量序列收敛，且收敛到准确解。,Jacobi迭代法算法, k = 1,则打印“求解失败”, 停机;否则,对 j = 1, 2, , n 计算,迭代 对 i = 1, 2, , n 计算, 若,， 输出X , k , 停机; 否则,做下一步.,输入A, b，初始向量Y，容许误差，容许最大迭代次数M,若,形成迭代矩阵B（存放在A中）,对 i = 1, 2, , n
4、循环,若k M , 则 k = k + 1 ，将X赋值给Y，转; 否则，输出求解失败信息，停机。,6.1.2 Seidel迭代法,称为Seidel迭代格式.,对上面式子归纳得到如下计算公式:,若令,和,则Seidel迭代格式用矩阵表示为,即,而,用,乘上式两边得,其中,称为Seidel迭代矩阵.,收敛于,可以证明:若由Seidel迭代格式所确定的向量序列,则,必为方程组,的解向量.,由迭代格式,可以得到,从而得到Seidel迭代格式为,补充例 用Seidel迭代法解方程组,方程组的准确解是:,把方程组改写成,解,当k=0时,迭代格式为,代入得,选取初始迭代向量,当k=1时,迭代格式为,代入得,
5、把,Seidel迭代法算法, k = 1 ,对 i = 1, 2, , n 做,则打印“求解失败”, 停机，否则,对 j = 1, 2, , n 计算,迭代 对 i = 1, 2, , n 计算, 若,， 输出X , k , 停机; 否则,做下一步.,输入A, b，初始向量Y，容许误差，容许最大迭代次数M,若,形成迭代矩阵B（存放在A中）,对 i = 1, 2, , n 循环,若k M , 则 k = k + 1 ，将X赋值给Y，转，否则，输出求解失败信息，停机。,6.1.3 松弛迭代法,令,则有,在,前面乘上参数,得到,称为松弛迭代格式,其中,称为松弛因子.,当,时,称为超松弛迭代格式,当,
6、时,称为低松弛迭代格式,当,时,就是Seidel迭代格式,即,它是松弛迭代格式的另一种形式.,称为松弛迭代矩阵.,可以证明:若由松弛迭代格式所确定的向量序列,收敛于,则,必为方程组,的解向量.,松弛迭代法算法, k = 1 ,对 i = 1, 2, , n 做,则打印“求解失败”, 停机，否则,对 j = 1, 2, , n 计算,迭代 对 i = 1, 2, , n 计算, 若,， 输出X , k , 停机; 否则,做下一步.,输入A, b，初始向量Y，松弛因子,容许误差，容许最大迭代次数M,若,形成迭代矩阵B（存放在A中）,对 i = 1, 2, , n 循环,若k M , 则 k = k
7、 + 1 ，将X赋值给Y，转，否则，输出求解失败信息，停机。,6.2 迭代法收敛性理论,例6-2 用Jacobi迭代法解方程组,它的准确解是:,取初始迭代向量 X (0) = (0, 0, 0)T , 利用Jacobi迭代格式，迭代计算结果如下表：,这说明:迭代序列收敛是有条件的。,从表中可以看到，迭代序列发散.,Jacobi迭代格式:,Seidel迭代格式:,松弛迭代格式:,上面几种迭代格式都具有如下形式:,其中M为迭代矩阵,定理6.1 对任何初始向量 X (0) 和常数项f ，由迭代格式,产生的向量序列,收敛的充分必要条件是迭代矩阵的谱半径,可以看到，迭代格式是否收敛与迭代矩阵的谱半径有关
8、,而迭代矩阵是由方程组的系数矩阵演变而来的,所以迭代格式是否收敛与系数矩阵和演变方式有关,与方程组的常数项b和初始迭代向量X (0)无关.,从而得到简单迭代格式为,补充例 考察用简单迭代法和Seidel迭代法解方程组,的收敛性.,把方程组改写成,解,因而得到简单迭代矩阵为,又因M的特征方程为,所以M的特征值为,从而得知,据定理6.1,使用简单迭代法解此方程组是收敛的.,从而得到Seidel迭代矩阵为,又因M的特征方程为,所以M的特征值为,从而得知,据定理6.1,使用Seidel迭代法解此方程组是不收敛的.,求矩阵的谱半径是比较困难的,但由前面证明得知,故由,就能保证有,所以可以用,来判别迭代,
9、法的收敛性.,需注意的是:,不能保证有,故不能用,判别不收敛.,从而得到简单迭代格式为,补充例 考察用简单迭代法解方程组,的收敛性.,把方程组改写成,解,因而得到简单迭代矩阵为,所以使用简单迭代法解此方程组是收敛的.,定理6. 2 若迭代矩阵 M的范数,，则迭代格式,对任何初始向量 X (0) 一定收敛，且,定理6. 3 Jacobi迭代法收敛的充分必要条件是,的所有根 i ( i = 1 , 2 , , n )的绝对值（复数理解为模）,小于1。,从而得到,补充例 考察用简单迭代法(Jacobi迭代法)解方程组,的收敛性.,由6.13式得,解,解方程得,因而,据定理6.3,用 Jacobi迭代
10、法解此方程组不收敛.,定理6. 4 Seidel迭代法收敛的充分必要条件是,的所有根 i ( i = 1 , 2 , , n )的绝对值小于1。,从而得到,补充例 考察用Seidel迭代法解方程组,的收敛性.,由6.14式得,解,解方程得,因而,据定理6.4,用 Seidel迭代法解此方程组收敛.,定理6. 5 松弛迭代 法收敛的充分必要条件是,的所有根 i ( i = 1 , 2 , , n ) 的绝对值小于1。,定义6.1 如果矩阵A不能通过行交换和相应的列交换变成为,其中 A11 , A22 为方阵，0为零矩阵,则称A为不可约的;反之,称A为可约的。,例如:,A是可约的.,又如:,B是不
11、可约的.,定义6.2 若矩阵,满足,且至少有一个 i 值，使上式中不等号严格成立，则称矩阵A具有对角优势（又称为弱对角占优）。,若所有的i 值,上式中不等号严格成立，则称矩阵A具有强对角占优。,例如:,具有对角优势(弱对角占优)。,又如:,具有强对角占优。,定理6. 8 若A强对角占优，或者A弱对角占优且不可约，则 (1) Jacobi迭代法和Seidel迭代法一定收敛。 (2) 若松弛因子满足 0 1，则松弛迭代法一定收敛。,补充例 考察用Jacobi,Seidel和松弛迭代法解方程组,的收敛性.,因为,解,从而该方程组弱对角占优且不可约.,因此,据定理6.8,用 Jacobi和Seidel
12、迭代法解此方程组收敛.,若松弛因子满足 0 1，则用松弛迭代法解此方程组也收敛。,定理6. 9 松弛法收敛的必要条件是 0 2。,定理6. 10 若矩阵A对称且对角线元素均为正实数，则当0 2时，松弛法收敛的充分必要条件是A正定。,例6-3 取初始向量 X (0) = (1, 1, 1)T ，用SOR方法求解方程组,使,，该方程组的精确解为 X * = (3, 4, -5) 。,SOR方法的迭代公式为,解,取 = 1.8,取 = 1.22,定理6.11 设,Jacobi迭代的迭代矩阵的特征值为实值，且,则,(2)SOR法最优松弛因子,。,为分块三对角阵，且,(1)当,时，SOR迭代收敛；,实验八,用Jacobi迭代法或Seidel迭代法解此方程组，取初始向量,实验九,使,。,已知方程组,X (0) = (0, 0, 0)T ，,。,取初始向量 X (0) = (1, 1, 1)T ，用SOR方法求解方程组,本章结束,
