湖南师范大学数值分析课件第8章解线性方程组的迭代法.ppt

第八章解线性方程组的迭代法;第八章解线性方程组的迭代法; 运算量大，不适合大规模的线性方程组求解 无法充分利用系数矩阵的稀疏性;如何构造迭代格式； 迭代序列是否收敛； 收敛速度如何； 如何估计误差。;例1 求解线性方程组;改写原方程组为;任取初值, 如 x(0)=(0,0,0)T, 得到 x(1)=(2.5, 3, 3)T.;矩阵分裂迭代法基本思想;问：对于任何一个方程组，按迭代法作出的向量序列 {x(k)}是否一定逐步逼近方程组的解 x*？ 思考：用迭代法求解方程组 ;k = 0, 1, 2, …;在Rn中，点列的收敛等价于每个分量的收敛。即 ;例4 设矩阵序列;定理2 设 则;例6 用迭代法求解方程组 ;定理3 (迭代法基本定理) 设有方程组 对于任意初始向量x(0)及任意f，解此方程组的迭代法 收敛的充要条件是;;是否：建立与矩阵元素直接有关的条件来判别迭代法的收敛性？;;例8 设有迭代过程;;第八章解线性方程组的迭代法;第八章解线性方程组的迭代法;8.2 Jacobi迭代法与Gauss-Seidel迭代法;矩阵分裂迭代法基本思想;Jacobi迭代法;令 M = D，N = L + U，得 雅可比 (Jacobi) 迭代方法。;等价的方程组（分量形式）：;每迭代一次只需要计算一次矩阵和向量乘法; 需要两组工作单元以存储x(k)和x(k+1);;在计算 时，如果用 代替 ，则可能会得到更好的收敛效果。;得：;例2 用Gauss-Seidel迭代法求解线性方程组(1.2), 取初值x(0)=(0,0,0)T. ;例3 分别用Jacobi迭代法和Gauss-Seidel迭代法 求解方程组 ;8.3 Jacobi迭代法与G-S迭代法的收敛性;定理5 解方程组(2.1)的高斯－赛德尔(Gauss－ Seidel)迭代法收敛的充要条件是?(BG)1 , 其中BG是Gauss－Seidel迭代法的迭代矩阵.;例5 考察用Jacobi方法方程组(1.2)的收敛性 ;定义4（对角占优矩阵）;例题9;定义5（可约与不可约矩阵）; 如果 A 是可约矩阵，则方程组 Ax = b 等价于;例10：判断例9中B矩阵是否可约？;定理6（对角占优定理）若A=(aij)n×n∈Rn×n(或Cn×n)为严格对角占优或不可约弱对角占优阵，则A非奇异. ;例11：设 ，给出 Jacobi 和 G-S 收敛的充要条件 ;解法二：;第八章解线性方程组的迭代法;第八章解线性方程组的迭代法;超松弛(SOR) 迭代;写成矩阵形式:;当? =1时，SOR方法就是Gauss-Seidel迭代法. 当? 1时，(4.5)为低松弛法 当? 1时，(4.5)为超松弛法;例1： 用SOR方法求解方程组;例2：分别用 Jacobi、G-S、SOR 迭代解线性方程组;G-S 迭代：;SOR 迭代：;定理8 设有线性方程组(4.1)且 aii≠0 (i=1, 2, ...n) , 则解方程组的SOR方法收敛的充要条件是 ;SOR算法;5 对于 i=1,2,…,n 有 (1) (2) 如果|p||p0|，则 (3) 6 输出p0； 7 如果 ，则转3； 8 输出结果x, k。 ;第八章解线性方程组的迭代法;第八章解线性方程组的迭代法;等 价 问 题;;(2) 对任意 x, y?Rn 和 ??R，有;;最速下降法;思想：任取一个迭代初始向量 x(0)，构造迭代序列 x(0), x(1) , x(2), . . . ，使得 ?(x(0)) ?(x(1)) ?(x(2)) . . .， 且每一步都以 “最快的速度” 下降到 ?(x) 的极小值。;如何计算 ?k 的值？;;;共轭梯度法;思想：在确定 x(k+1) 时，不沿负梯度方向取极小，而是寻找 一个更好的方向 p(k) ，使得 ?(x) 下降得更快！;具体作法：令 p(0) = r(0) ，设 x(k) 已经求得，则 x(k+1) 由下面的公式确定：;;; ?k 与 ?k 的计算公式;②; ?k 与 ?k 的计算;;;例：用共轭梯度法解线性方程