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

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

2、如何构造迭代格式 2.迭代序列是否收敛7/17/20222第6章 解线性方程组的迭代法 6.1.2 向量序列与矩阵序列的极限 则称向量序列 收敛于 ，记为 定义2 设有向量序列 如果存在 ，使其中 为任一种向量范数. 定义3 设有矩阵序列 及 ,如果 个数列极限存在且有 则称 收敛于 ，记为 7/17/20223第6章 解线性方程组的迭代法 解由于，当 时，有 所以 例1 设有矩阵序列 且设 ，考查其极限. 证明范数的等价性 定理1 其中为矩阵的任意一种算子范数. 7/17/20224第6章 解线性方程组的迭代法 证明 定理2 的充分必要条件是（1.7）若 ，则 ，取 为第 个坐标向量 ，则必

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

4、阵. 即求解一阶定常迭代法 （1.11）即（1.10）迭代的构造其中 迭代矩阵7/17/20229第6章 解线性方程组的迭代法6.1.4 迭代法的收敛性 研究 的收敛性. 引进误差向量 得 ，递推得 研究 在什么条件下有是初始误差向量，是一个确定的值。对任意的初始向量 ，序列 收敛7/17/202210第6章 解线性方程组的迭代法 定理5 给定线性方程组 及一阶定常迭代法 对任意选取初始向量 ，迭代法收敛的充要条件是矩阵 的谱半径（1）迭代法是否收敛取决于迭代矩阵的谱半径，与初始向量和常数项无关。（2）而对于同一个方程组，不同的迭代法对应的迭代矩阵的谱半径一般不会相同，因而收敛性也不同。注：注

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

6、方程组的迭代法例3 考察线性方程组（1.2）给出的迭代法（1.4）的收敛性 （1.2）（1.4） 先求迭代矩阵 的特征值. 由特征方程可得解得所以迭代法（1.4）是收敛的.解7/17/202215第6章 解线性方程组的迭代法例4 考察用迭代法解方程组 的收敛性，解其中特征方程为特征根 即 . 这说明用此迭代法解此方程组不收敛. 7/17/202216第6章 解线性方程组的迭代法 定理6及一阶定常迭代法 如果有 的某种算子范数 ，则 (迭代法收敛的充分条件)设有方程组 (1) 迭代法收敛，即对任取 有 利用矩阵的范数判定迭代收敛只是一个充分条件，通常采用矩阵的1-范数、 -范数来判定。事后估计估

7、计迭代次数7/17/202217第6章 解线性方程组的迭代法 证明(2)反复递推即得(2). (1) 是显然的. 有 (3) 即 (3)反复利用(a)由关系式由 7/17/202218第6章 解线性方程组的迭代法 定理6只给出迭代法（1.11）收敛的充分条件，即使条件 对任何常用范数均不成立，迭代序列仍可能收敛. 例5 迭代法 ,其中 的各种范数均大于1，但 ，故此迭代法产生的迭代序列 是收敛的.7/17/202219第6章 解线性方程组的迭代法 下面考察迭代法的收敛速度.6.1.4 迭代法的收敛速度/* Rate of Average Convergence */ 假定迭代法是收敛的，即 ，

8、于是根据从属范数定义，有 迭代 次后误差向量 的范数与初始误差向量 的范数之比的最大值.由 ，得7/17/202220第6章 解线性方程组的迭代法平均每次迭代误差向量范数的压缩率其中 ，可取 . 因为 ，故 ，即（1.12）它表明迭代次数 与 成反比.若要求迭代 次后有由 两边取对数得越大越小收敛越快7/17/202221第6章 解线性方程组的迭代法 定义4 迭代法（1.11）的平均收敛速度定义为（1.13） 定义5 迭代法(1.11)的渐近收敛速度定义为 由 ，（1.14）（1.15）估计迭代次数所以 与迭代次数及 取何种范数无关，它反映了迭代次数趋于无穷时迭代法的渐近性质。当 越小时 越大

9、，迭代法收敛越快。7/17/202222第6章 解线性方程组的迭代法迭代矩阵 的谱半径 即取 即可达到要求.若要求 ，则由于是几种实用的基本迭代法应用实例7/17/202223第6章 解线性方程组的迭代法（2.1）6.2.1 雅可比迭代法 6.2 雅可比迭代法与高斯-塞尔迭代法（1.1）设 ，选取 (对角阵)，（2.2）解 的雅可比(Jacobi)迭代法其中 雅可比迭代法的迭代阵7/17/202224第6章 解线性方程组的迭代法记 雅可比迭代或 （2.2）其中 （2.3）解 的雅可比迭代法的分量计算公式 Jacobi方法是由方程组第i个方程解出xi得到的等价方程组。7/17/202225第6章

10、 解线性方程组的迭代法 每迭代一次只需计算一次矩阵和向量的乘法且计算过程中原始矩阵 始终不变. 6.2.2 高斯-塞德尔迭代法 分裂矩阵 取为 的下三角部分，即 (下三角阵)，解 的高斯-塞德尔(Gauss-Seidel)迭代法（2.4）其中 高斯-塞德尔迭代法的迭代阵研究高斯-塞德尔迭代法的分量计算公式. 7/17/202226第6章 解线性方程组的迭代法记 高斯-塞德尔迭代或 即 解 的高斯-塞德尔迭代法的分量计算公式 （2.5）雅可比迭代法的一种改进7/17/202227第6章 解线性方程组的迭代法或 （2.6）7/17/202228第6章 解线性方程组的迭代法 迭代一次，这个算法需要的

11、运算次数至多与矩阵 的非零元素的个数一样多. 算法1 (高斯-塞德尔迭代法) 设 ，其中 为非奇异矩阵且 本算法用高斯-塞德尔迭代法解 ，数组 开始存放 ,后存放 为最大迭代次数. 7/17/202229第6章 解线性方程组的迭代法 例6 用高斯-塞德尔迭代法解线性方程组(1.2). 按高斯-塞德尔迭代公式迭代7次，得 ，（1.2）取 ， 且 解7/17/202230第6章 解线性方程组的迭代法方程组的精确解为x*=(1,1,1)T.J迭代法计算公式为取初始向量x(0)=(0,0,0)T,迭代可得计算结果列表如下:解例7 用J法和G-S法求解线性方程组7/17/202231第6章 解线性方程组

12、的迭代法可见,迭代序列逐次收敛于方程组的解, 而且迭代7次得到精确到小数点后两位的近似解.kx1(k)x2(k)x3(k)x(k)-x*0123456701.41.110.9290.99061.011591.0002510.998236400.51.201.0550.96450.99531.0057951.000125501.41.110.9290.99061.011591.0002510.998236410.50.20.0710.03550.011590.0057950.0017636x (6) -x(5) =0.011339,x(7) x(6)=0.00566957/17/202232第6

13、章 解线性方程组的迭代法 同样取初始向量x(0)=(0,0,0)T, 计算结果为 由计算结果可见,G-S迭代法收敛较快.取精确到小数点后两位的近似解,G-S迭代法只需迭代3次,而J迭代法需要迭代7次.kx1(k)x2(k)x3(k)x(k)-x*012301.41.06340.995104400.781.020480.9952756801.0260.9875161.0019068610.40.06340.0048956 G-S迭代法的计算公式为:不具有一般性7/17/202233第6章 解线性方程组的迭代法 用J迭代法求上例中方程组的解,取x(0)=(0,0,0)T,若使误差x(k)-x*10

14、-5,问需要迭代多少次?由上例知,x(1)=(1.4,0.5,1.4)T,于是有 x(1)-x(0)=1.4 ,B=0.5 .例8k应满足故取k=19, 即需要迭代19次.解若使x(k) x* ,只需，即事前估计迭代次数7/17/202234第6章 解线性方程组的迭代法 定理7 设 ，其中 为非奇异矩阵且 非奇异，则 (1) 解方程组的雅可比迭代法收敛的充要条件是 ，其中 (2) 解方程组的高斯-塞德尔迭代法收敛的充要条件是其中 6.2.3 雅可比迭代与高斯-塞德尔迭代法的收敛性雅可比迭代法收敛的充分条件是高斯-赛德尔迭代法收敛的充分条件是7/17/202235第6章 解线性方程组的迭代法例9

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

16、阵， 为 阶方阵 ，为可约矩阵.则称进行一次行列重排7/17/202238第6章 解线性方程组的迭代法且记 其中 为 维向量. 由上式第2个方程组求出 , 无零元素的矩阵是不可约矩阵。 再代入第1个方程组求出 例：矩阵可约矩阵 都是不可约矩阵. 7/17/202239第6章 解线性方程组的迭代法 定理8 (对角占优定理)如果 为严格对角占优矩阵或 为不可约弱对角占优矩阵，则 为非奇异矩阵. 就 为严格对角占优阵证明此定理. 如果 ，则 有非零解，记为 , 齐次方程组第 个方程 则有 则 证明即 与条件矛盾，故 反证法。7/17/202240第6章 解线性方程组的迭代法 定理9 设 ,如果： (

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

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

19、可比迭代当 时雅可比法收敛.7/17/202245第6章 解线性方程组的迭代法6.3 超松弛迭代法 6.3.1 逐次超松弛迭代法 加速高斯-塞德尔迭代设已知 及已计算 的分量 (1) 首先用高斯-塞德尔迭代法定义辅助量 (2) 再由 与 加权平均定义 ，7/17/202246第6章 解线性方程组的迭代法选取分裂矩阵 为其中 为可选择的松弛因子. 解 的逐次超松弛迭代法(Successive Over Relaxation） （3.1）其中 解 的SOR方法的分量计算公式 （3.2）7/17/202247第6章 解线性方程组的迭代法或 （3.3）注(1) 当 时，SOR方法即为高斯-塞德尔迭代法. (2) 每迭代一次主要运算量是计算一次矩阵与向量的乘法. (3) ，称为超松弛法； 时，称为低松弛法. (4) 在计算机实现时用 控制迭代终止，或用 控制迭代终止. 7/17/202248第6章 解线性方程组的迭代法例10 用SOR方法解方程组 精确解为 取 ，解取 ，