数值分析 第6章 线性代数方程组的迭代法

1、2020/9/18,第6章 解线性方程组的迭代法,1,6.1 迭代法的基本概念 6.2 雅可比迭代法与高斯-塞德尔迭代法 6.3 超松弛迭代法 6.4 共轭梯度法,第6章 解线性方程组的迭代法/* Iterative Techniques for Solving Linear Systems */,2020/9/18,第6章 解线性方程组的迭代法,2,6.1 迭代法的基本概念,考虑线性方程组,（1.1）,其中 为非奇异矩阵。,迭代法通常都可利用 中有大量零元素的特点.,6.1.1 引言,当 为低阶稠密矩阵时，选主元消去法是有效方法.,迭代法适用于求解大型稀疏的线性方程组。,基本思想：通过构造迭

2、代格式产生迭代序列，由迭代序列来逼近原方程组的解。,要解决的基本问题： 1. 如何构造迭代格式 2.迭代序列是否收敛,2020/9/18,第6章 解线性方程组的迭代法,3,6.1.2 向量序列与矩阵序列的极限,则称向量序列 收敛于 ，记为,定义2 设有向量序列 如果存在 ，使,其中 为任一种向量范数.,定义3 设有矩阵序列 及 , 如果 个数列极限存在且有,则称 收敛于 ，,记为,2020/9/18,第6章 解线性方程组的迭代法,4,解,由于，当 时，有,所以,证明,范数的等价性,2020/9/18,第6章 解线性方程组的迭代法,5,证明,若 ，则 ，,取 为第 个坐标向量 ，则,必要性。,故

3、对一切 ，有 .,表示 的第 列元素极限均为零，,当 时，,就得到,矩阵的算子范数满足,充分性。,2020/9/18,第6章 解线性方程组的迭代法,6,定理3 设 ，下面3个命题等价：,（1） ；,证明,与迭代矩阵相关的结论,（2） ；,（3）至少存在一种从属的矩阵范数 ，使,反证法。,假定 有一个特征值 ，,满足 ,则存在 ，使 ，,由此,由定理2知（1）不成立，从而知 ，即（2）成立.,对任意 ，存在一种从属范数 ，使 ，,适当选择 ，可使 ，即（3）成立.,由矩阵范数 ，,可得 ，从而有,又,2020/9/18,第6章 解线性方程组的迭代法,9,将 分裂为,（1.9）,其中， 为可选择的

4、非奇异矩阵，且使 容易求解，,称 为分裂矩阵.,即求解,一阶定常迭代法,（1.11）,即,（1.10）,迭代的构造,其中,迭代矩阵,2020/9/18,第6章 解线性方程组的迭代法,10,6.1.4 迭代法的收敛性,研究 的收敛性.,引进误差向量,得 ，,递推得,研究 在什么条件下有,是初始误差向量，是一个确定的值。,对任意的初始向量 ，序列 收敛,2020/9/18,第6章 解线性方程组的迭代法,11,（1）迭代法是否收敛取决于迭代矩阵的谱半径，与初始向量和常数项无关。,（2）而对于同一个方程组，不同的迭代法对应的迭代矩阵的谱半径一般不会相同，因而收敛性也不同。,注：,注：至少存在一种从属的

5、矩阵范数 ，使,迭代法收敛的判别准则,2020/9/18,第6章 解线性方程组的迭代法,12,例2 求解方程组,（1.2）,记为 ,方程组的精确解是 .,其中,现将(1.2)改写为,（1.3）,或写为 ,其中,2020/9/18,第6章 解线性方程组的迭代法,13,任取初始值，例如取 .,得到新的值,（1.4）,简写为,其中 表示迭代次数,迭代到第10次有,2020/9/18,第6章 解线性方程组的迭代法,14,对于任何由 变形得到的等价方程组 ，,迭代法产生的向量序列 是否都能逐步逼近方程组 的解 ？,如方程组,构造迭代法,对任何的初始向量，得到的序列都不收敛.,2020/9/18,第6章

6、解线性方程组的迭代法,15,例3 考察线性方程组（1.2）,给出的迭代法（1.4）的收敛性,（1.2）,（1.4）,先求迭代矩阵 的特征值. 由特征方程,可得,解得,所以迭代法（1.4） 是收敛的.,解,2020/9/18,第6章 解线性方程组的迭代法,16,例4 考察用迭代法解方程组,的收敛性，,解,其中,特征方程为,特征根,即 .,这说明用此迭代法解此方程组不收敛.,2020/9/18,第6章 解线性方程组的迭代法,17,事后估计,估计迭代次数,2020/9/18,第6章 解线性方程组的迭代法,18,证明,(2),反复递推即得(2).,(1) 是显然的.,有,(3),即,(3)反复利用(a

7、),由关系式,由,2020/9/18,第6章 解线性方程组的迭代法,19,定理6只给出迭代法（1.11）收敛的充分条件，即使条 件 对任何常用范数均不成立，迭代序列仍可能收敛.,例5 迭代法 ,其中,的各种范数均大于1，,但 ，,故此迭代法产生的迭代序列 是收敛的.,2020/9/18,第6章 解线性方程组的迭代法,20,6.1.4 迭代法的收敛速度/* Rate of Average Convergence */,假定迭代法是收敛的，即 ，,于是,根据从属范数定义，有,迭代 次后误差向量 的范数与初始误差向量 的范数之比的最大值.,由 ，得,2020/9/18,第6章 解线性方程组的迭代法,

8、21,平均每次迭代误差向量范数的压缩率,其中 ，可取 .,因为 ，故 ，,即,（1.12）,它表明迭代次数 与 成反比.,若要求迭代 次后有,由 两边取对数得,越大,越小,收敛越快,2020/9/18,第6章 解线性方程组的迭代法,22,定义5 迭代法(1.11)的渐近收敛速度定义为,由 ，,（1.14）,（1.15）,估计迭代次数,所以,与迭代次数及 取何种范数无关，它反映了迭代次数趋 于无穷时迭代法的渐近性质。,当 越小时 越大，迭代法收敛越快。,2020/9/18,第6章 解线性方程组的迭代法,23,迭代矩阵 的谱半径,即取 即可达到要求.,若要求 ，,则由,于是,几种实用的基本迭代法

9、应用实例,2020/9/18,第6章 解线性方程组的迭代法,24,（2.1）,6.2.1 雅可比迭代法,6.2 雅可比迭代法与高斯-塞尔迭代法,（1.1）,设 ，,选取 (对角阵)，,（2.2）,解 的雅可比(Jacobi)迭代法,其中,雅可比迭代法的迭代阵,2020/9/18,第6章 解线性方程组的迭代法,25,记,雅可比迭代,或,（2.2）,其中,（2.3）,解 的雅可比迭代法的分量计算公式,Jacobi方法是由方程组第i个方程解出xi得到的等价方程组。,2020/9/18,第6章 解线性方程组的迭代法,26,每迭代一次只需计算一次矩阵和向量的乘法且计算过程中 原始矩阵 始终不变.,6.2

10、.2 高斯-塞德尔迭代法,分裂矩阵 取为 的下三角部分，即 (下三角阵)，,解 的高斯-塞德尔(Gauss-Seidel)迭代法,（2.4）,其中,高斯-塞德尔迭代法的迭代阵,研究高斯-塞德尔迭代法的分量计算公式.,2020/9/18,第6章 解线性方程组的迭代法,27,记,高斯-塞德尔迭代,或,即,解 的高斯-塞德尔迭代法的分量计算公式,（2.5）,雅可比迭代法的一种改进,2020/9/18,第6章 解线性方程组的迭代法,28,或,（2.6）,2020/9/18,第6章 解线性方程组的迭代法,29,迭代一次，这个算法需要的运算次数至多与矩阵 的 非零元素的个数一样多.,算法1 (高斯-塞德尔

11、迭代法),设 ，其中 为非奇异矩阵且 本算法用高斯-塞德尔迭代法解 ， 数组 开始存放 ,后存放 为最大迭代次数.,2020/9/18,第6章 解线性方程组的迭代法,30,例6 用高斯-塞德尔迭代法解线性方程组(1.2).,按高斯-塞德尔迭代公式,迭代7次，得 ，,（1.2）,取 ，,且,解,2020/9/18,第6章 解线性方程组的迭代法,31,方程组的精确解为x*=(1,1,1)T.,J迭代法计算公式为,取初始向量x(0)=(0,0,0)T,迭代可得,计算结果列表如下:,解,例7 用J法和G-S法求解线性方程组,2020/9/18,第6章 解线性方程组的迭代法,32,可见,迭代序列逐次收敛

12、于方程组的解, 而且迭代7次得到精确到小数点后两位的近似解.,x (6) -x(5) =0.011339,x(7) x(6)=0.0056695,2020/9/18,第6章 解线性方程组的迭代法,33,同样取初始向量x(0)=(0,0,0)T, 计算结果为,由计算结果可见,G-S迭代法收敛较快.取精确到小数点后两位的近似解,G-S迭代法只需迭代3次,而J迭代法需要迭代7次.,G-S迭代法的计算公式为:,不具有一般性,2020/9/18,第6章 解线性方程组的迭代法,34,用J迭代法求上例中方程组的解,取x(0)=(0,0,0)T,若使误差 x(k)-x*10-5,问需要迭代多少次?,由上例知,

13、x(1)=(1.4,0.5,1.4)T,于是有 x(1)-x(0)=1.4 ,B=0.5 .,例8,k应满足,故取k=19, 即需要迭代19次.,解,若使x(k) x* ,只需,，即,事前估计迭代次数,2020/9/18,第6章 解线性方程组的迭代法,35,定理7 设 ，其中 为非奇异矩 阵且 非奇异，则,6.2.3 雅可比迭代与高斯-塞德尔迭代法的收敛性,雅可比迭代法收敛的充分条件是,高斯-赛德尔迭代法收敛的充分条件是,2020/9/18,第6章 解线性方程组的迭代法,36,例9：说明用J法和G-S法求解下列方程组的收敛性：,解：,计算特征值：,J法不收敛,G-S法的迭代矩阵为,G-S法收敛

14、,2020/9/18,第6章 解线性方程组的迭代法,37,例9：说明用J法和G-S法求解下列方程组的收敛性：,解：,计算特征值：,J法收敛,计算特征值：,G-S法不收敛,2020/9/18,第6章 解线性方程组的迭代法,38,其他收敛性结论,1）对角占优矩阵的性质,(1) 如果 的元素满足,称 为严格对角占优阵.,(2) 如果 的元素满足,且上式至少有一个不等式严格成立，,称 为弱对角占优阵.,定义6 (对角占优阵) 设,定义7(可约与不可约矩阵) 设 , 如果存在置换阵 使,（2.7）,否则,称 为不可约矩阵.,进行一次行列重排,2020/9/18,第6章 解线性方程组的迭代法,39,且记,

15、其中 为 维向量.,由上式第2个方程组求出 ,无零元素的矩阵是不可约矩阵。,再代入第1个方程组求出,例：,矩阵,可约矩阵,都是不可约矩阵.,2020/9/18,第6章 解线性方程组的迭代法,40,定理8 (对角占优定理)如果 为严格对角 占优矩阵或 为不可约弱对角占优矩阵，则 为非奇异矩阵.,就 为严格对角占优阵证明此定理.,如果 ，则 有非零解，,记为 ,齐次方程组第 个方程,则有,则,证明,即,与条件矛盾，故,反证法。,2020/9/18,第6章 解线性方程组的迭代法,41,定理9 设 ,如果：,(1) 为严格对角占优阵，则解 的雅可比迭 代法，高斯-塞德尔迭代法均收敛.,(2) 为弱对角

16、占优阵，且 为不可约矩阵，则解 雅可比迭代法，高斯-塞德尔迭代法均收敛.,2）系数矩阵对角占优的J和G-S迭代的收敛性,证明,只证(1)中高斯-塞德尔迭代法收敛.,由设可知， ，,高斯-塞德尔迭代法的迭代矩阵为,又 ,于是,2020/9/18,第6章 解线性方程组的迭代法,42,记,当 时，,由 为严格对角占优阵，,有,因此，当 时，矩阵 为严格对角占优阵，,因此,即 的特征值均满足 ，,高斯-塞德尔迭代法收敛. ,2020/9/18,第6章 解线性方程组的迭代法,43,证明,只证(1)中Jacobi迭代法收敛.,由设可知， ，,Jacobi迭代法的迭代矩阵为,又 ,于是,记,当 时，,由 为

17、严格对角占优阵，,有,因此,2020/9/18,第6章 解线性方程组的迭代法,44,定理10 设矩阵 对称，且对角元,(1) 解线性方程组 的雅可比法收敛的充要条件是 与 均为正定矩阵，其中,(2) 解线性方程组 的高斯-塞德尔法收敛的充分条件是 正定.,3）系数矩阵对称正定的J和G-S迭代的收敛性,例：说明用J法和G-S法求解下列方程组的收敛性：,解：,计算特征值：,2020/9/18,第6章 解线性方程组的迭代法,45,证明,由 的顺序主子式,当 时， 正定，故高斯-塞德尔法收敛.,雅可比迭代,当 时雅可比法收敛.,2020/9/18,第6章 解线性方程组的迭代法,46,6.3 超松弛迭代

18、法,6.3.1 逐次超松弛迭代法,加速高斯-塞德尔迭代,设已知 及已计算 的分量,(1) 首先用高斯-塞德尔迭代法定义辅助量,(2) 再由 与 加权平均定义 ，,2020/9/18,第6章 解线性方程组的迭代法,47,选取分裂矩阵 为,其中 为可选择的松弛因子.,解 的逐次超松弛迭代法(Successive Over Relaxation）,（3.1）,其中,解 的SOR方法的分量计算公式,（3.2）,2020/9/18,第6章 解线性方程组的迭代法,48,或,（3.3）,注,(1) 当 时，SOR方法即为高斯-塞德尔迭代法.,(2) 每迭代一次主要运算量是计算一次矩阵与向量的乘法.,(3) ，称为超松弛法；