线性方程组的迭代解法.ppt

第二章线性方程组的迭代解法 迭代法的基本思想Jacobi迭代和Gauss Seidel迭代迭代法的收敛性超松弛迭代分块迭代法 第二章线性方程组的迭代解法 2 7迭代法的基本思想 例 求解方程组 其精确解是x 3 2 1 T 现将原方程组改写为 简写为x B0 x f 其中 任取初始值 如取x 0 0 0 0 T 代入x B0 x f右边 若等式成立则求得方程组的解 否则 得新值x 1 x1 1 x2 1 x3 1 T 2 5 3 3 T 再将x 1 代入 反复计算 得一向量序列 x k 和一般的计算公式 迭代公式 简写为x k 1 B0 x k fk 0 1 2 x 10 3 000032 1 999838 0 999813 T 迭代到第10次时有 10 x 10 x 0 000187 定义 1 对于给定方程组x Bx f 用迭代公式x k 1 Bx k f k 0 1 2 逐步代入求近似解的方法称迭代法 2 若k 时limx k 存在 记为x 称此迭代法收敛 显然x 就是方程组的解 否则称迭代法发散 3 B称为迭代矩阵 问题 如何建立迭代格式 收敛速度 向量序列的收敛条件 误差估计 设Ax b A非奇异 且对角元不为零 将原方程组改写为 2 7Jacobi迭代与Gauss Seidel迭代 2 7 1Jacobi迭代法 又代入 反复继续 得迭代格式 称Jacobi迭代法 选取初始向量 代入上面方程组右端得 Jacobi迭代法的矩阵表示 计算公式为 i 1 2 n k 0 1 2 表迭代次数 矩阵表示 则BJ I D 1A D 1 L U fJ D 1b 称BJ为Jacobi迭代矩阵 aii 0 将方程组Ax b的系数矩阵A分解为 A D L U 例1 用Jacobi迭代法求解方程组 误差不超过10 4 解 依此类推 得方程组满足精度的解为x12 迭代次数 12次 x4 3 02411 94780 9205d 0 1573x5 3 00031 98401 0010d 0 0914x6 2 99382 00001 0038d 0 0175x7 2 99902 00261 0031d 0 0059x8 3 00022 00060 9998d 0 0040 x9 3 00031 99990 9997d 7 3612e 004x10 3 00001 99990 9999d 2 8918e 004x11 3 00002 00001 0000d 1 7669e 004x12 3 00002 00001 0000d 3 0647e 005 若在迭代时尽量利用最新信息 则可将迭代格式变为 2 7 2Gauss Seidel迭代法 称Gauss Seidel迭代法 计算公式 i 2 3 n 1 i 1 2 n 即 其中BG S D L 1U称Gauss Seidel迭代矩阵 D L x k 1 b Ux k 故 Gauss Seidel迭代格式 例2 用Gauss Seidel迭代法求解例1方程组 要求误差仍然不超过10 4 解 Gauss Seidel迭代格式为 x1 2 50002 09091 2273d 3 4825x2 2 97732 02891 0041d 0 5305x3 3 00981 99680 9959d 0 0465x4 2 99981 99971 0002d 0 0112x5 2 99982 00011 0001d 3 9735e 004x6 3 00002 00001 0000d 1 9555e 004x7 3 00002 00001 0000d 1 1576e 005 取初值x 0 0 0 0 T通过迭代 至第7步得到满足精度的解x7 从例1和例2可以看出 Gauss Seidel迭代法的收敛速度比Jacobi迭代法要快 Jacobi迭代法和Gauss Seidel迭代法统称为简单迭代法 2 8迭代法的收敛性 设求解线性方程组的迭代格式为 将上面两式相减 得 而方程组的精确解为x 则 则 因此迭代法收敛的充要条件 可转变为 引理 迭代格式 收敛的充要条件为 定理 迭代格式 收敛的充要条件为 迭代矩阵的谱半径 B 1 证 对任何n阶矩阵B 都存在非奇矩阵P 使B P 1JP其中 J为B的Jordan标准型 其中 Ji为Jordan块 其中 i是矩阵B的特征值 由B P 1JP Bk P 1JP P 1JP P 1JP P 1JkP 迭代法x k 1 Bx k f收敛 i 1 2 r i 1 2 r 谱半径 B 1 定理 设x 为方程组Ax b的解 若 B 1 则对迭代格式x k 1 Bx k f 有 1 2 推论若 B 1 则迭代法x k 1 Bx k f收敛 因为 B B 证由 B 1 有 所以 x k 1 x B x k x x k 1 x Bx k f Bx f B x k x x k x x k x k 1 x k 1 x x k x k 1 x k 1 x x k x k 1 B x x k x k 1 x k B x k x 所以 x k 1 x k Bx k f Bx k 1 f B x k x k 1 x k 1 x k B x k x k 1 故可得误差估计式 注 1 式说明 只要 B 不是很接近1 当x k 1 和x k 很接近时 x k 也越接近x 故可用 x k 1 x k 中止迭代 2 式说明 B 越小 x k 收敛越快 可作误差估计式 例3 判别下列方程组用Jacobi法和Gauss Seidel法求解是否收敛 解 1 求Jacobi法的迭代矩阵 所以 即Jacobi迭代法收敛 2 求Gauss Seidel法的迭代矩阵 显然BJ的几种常用算子范数 BJ 1 故用其特征值判断 所以Gauss Seidel迭代法发散 注 在例1和例2中 Gauss Seidel迭代法收敛速度比Jacobi迭代法要高 但例3却说明Gauss Seidel迭代法发散时而Jacobi迭代法却收敛 因此 不能说Gauss Seidel迭代法比Jacobi迭代法更好 可得 故 定义设A aij n n Rn n 若 i 1 2 n 则称A为对角占优矩阵 若不等式严格成立 则称A为严格对角占优矩阵 迭代法收敛的其他结论 定理若Ax b中A为严格对角占优矩阵 则Jacobi迭代和Gauss Seidel迭代均收敛 证明 因为系数矩阵A严格对角占优 所以 故Jacobi迭代法收敛 1 对于Jacobi迭代法 其迭代矩阵为 即 从而 因此 2 对于G S迭代法 其迭代矩阵为 BG的特征值 满足 分析 要证G S迭代法收敛 即证其迭代矩阵的谱半径 B 1 只要证明其特征值 1即可 由于 可得 矛盾 由前述定理知 G S迭代法收敛 定理若A为对称正定阵 则Gauss Seidel迭代收敛 考虑解线性方程组的Gauss Seidel迭代法 2 9超松弛迭代法 SOR 迭代法的加速 令 因此 上式称为逐次超松弛法 SOR迭代法 由G S迭代法的矩阵形式 上式为逐次超松弛法 SOR迭代法 的矩阵形式 令 当 1时 SOR法化为 G S迭代法 G S法为SOR法的特例 SOR法为G S法的加速 例1 用G S法和SOR法求下列方程组的解 要求精度1e 6 解 1 G S迭代法 x1x2x31110 75000000 37500001 50000000 56250000 53125001 54166670 65104170 59635421 61458330 70182290 65820311 6727431 0 99999330 99999231 99999260 99999430 99999351 99999370 99999520 99999441 9999946k 71 x 0 9999950 9999941 999995 满足精度的解 迭代次数为71次 2 SOR迭代法 x1x2x31110 63750000 01218751 31990630 20042700 37175721 31228050 65503350 53401191 69228480 70584680 77334011 7771932 0 99999900 99999761 99999910 99999840 99999931 99999890 99999980 99999941 99999980 99999960 99999981 9999997k 24 x 1 0000001 0000002 000000 满足精度的解 迭代次数为24次 选取适当的 SOR法的收敛速度比G S法要快得多 SOR迭代收敛条件 SOR迭代收敛 B 1 SOR迭代收敛的必要条件是0 2 若A对称正定 则当0 2时 SOR收敛 若A为严格对角占优矩阵 则当0 1时 SOR收敛 另外 松弛因子的选取是很困难的 一般采用试算进行 functionx jacobi f A b x0 tol max 迭代终止准则 x tol 最大迭代次数max n m size A xold x0 C A fori 1 nC i i 0 endfori 1 nC i C i A i i endfori 1 nd i 1 b i A i i 2 10 1Jacobi迭代法的Matlab函数文件 endi 1 whilei maxxnew C xold difnorm xnew xold tolx xnewdisp Jacobi迭代法收敛 return elsexold xnew enddisp ixnew i i 1 enddisp Jacobi迭代法不收敛 disp 最大迭代次数后的结果为 x xnew 2 10 2SOR法的Matlab函数文件 functionx sor f A b x0 w tol max n m size A x