线性方程组的解法.ppt

Numerical Analysis J. G. Liu School of Math. 3、超松弛迭代法（SOR); 本节主要介绍 ： Date 1 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U. 1 迭代法的一般形式及其收敛性 下面考虑 事实上，令 ，则 ? 设 (1) 给定初值x(0)，可以构造序列 迭代格式 (2) Date 2 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U. 若 并且， (与初值x(0)的选取无关!) 所以， 序列收敛 (3) 定理1 迭代格式(2)收敛 Date 3 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U. 定义1 迭代法（2）的平均收敛速度定义为 。 由（3）式可得 引理 设ARnn，为任一矩阵范数，则 注： 平均收敛速度与范数和迭代次数有关，计算不便！ 定义2 迭代法（2）的渐近收敛速度定义为 Date 4 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U. 定理2若 ，则 (1) 方程组(1)的解x*存在并且唯一； (2) 对迭代格式(2)有 并且 下面给出迭代格式(2)收敛的一个充分条件及误差估计， 证明： (1 ) 非奇异 Date 5 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U. (2) 下证误差估计式， 由迭代公式(3) 得证！ 注： 可作为迭代是否停止的判断条件！ 由知可由或 得证！ # 即 迭代格式收敛。 Date 6 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U. 2 线性代数方程组的常用迭代法 迭代矩阵G的构造原则： 充分利用矩阵的稀疏性，使运算量和存贮量尽量少，办法就是 使迭代矩阵G与原矩阵A有相同的稀疏结构。 具体构造方法: 令 其中 Date 7 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U. 由可以得到 1、Jacobi 迭代算法 令 可得： 从而可得Jacobi 迭代算法： 算法的分量形式为(具有并行性)： 若D非奇异， Jacobi迭代矩阵 Date 8 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U. 2、Gauss-Seidel 迭代算法 从而可得Gauss-Seidel迭代算法： 算法的分量形式为(只能逐个元素进行计算) ： 也可写成如下形式： 易于编程实现 G-S迭代矩阵 Date 9 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U. 迭代算法的收敛性： (1) Jacobi迭代算法收敛 (2) 若A按行（列）严格对角占优，则Jacobi迭代和Gauss- Seidel迭代收敛；# Jacobi迭代收敛； Gauss-Seidel迭代收敛； (3) (4) 若A为正定矩阵，则Gauss-Seidel迭代收敛。# 两种方法都存在收敛性问题，但两者的收敛性没有必然联系！ 有例子表明：Gauss-Seidel法收敛时，Jacobi法可能不收敛； 而Jacobi法收敛时， Gauss-Seidel法也可能不收敛。 注注: : G-S迭代算法收敛 Date 10 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U. 算法描述: Jacobi迭代算法： 给定迭代初始向量x(0)，置迭代次数k=0，精度要求 和最大迭 代次数N； 计算 ，k=k+1；(1) (2)若 ，则停止计算（x(1)作为方程的解）； (3) 若 k=N，则停止计算（输出某些信息），否则x(0)=x(1)， 转(1)； 注： 将 (1)中的迭代公式换作 即为G-S迭代的算法描述！ 1） 2）通常取向量的无穷范数！ Date 11 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U. 3 超松弛(SOR)迭代算法 设已得到利用松弛技术对由高斯-赛德尔迭代进行加速： ( 松弛因子)， 超松弛迭代算法(SOR) 注： =1 时，即为Gauss-Seidel迭代算法。 SOR算法的分量形式(只能逐个元素进行计算)： Date 12 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U. 注： 若令 则可以得到矩阵表示形式： 其中 Date 13 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U. SOR迭代算法的收敛性 ： （5）若A为正定矩阵，则当02时， SOR迭代算法收 敛；# （4）若A为严格对角占优阵，则当01时， SOR迭 代算法收敛；# （2）SOR迭代收敛的必要条件02 # 注 ： 松弛因子的选择通常靠经验或用试算的方法来确定！ Date 14 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U. 4 解线性代数方程组的共轭梯度法 我们知道二次函数 当A是对称正定矩阵时，有唯一的极小值点x*。 由多元函数取得极值的必要条件，得 可以证明 即解对称正定矩阵方程组的问题等价于求二次函数极小值的问题。 Date 15 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U. 如何寻找 的极小点呢？ 从某点x(0)出发，逐步产生一串点： 以“最快”的速度，下降到 的极小值。 基本思想就是下降法： Date 16 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U. 下降法的算法描述： 假设已经求得x(k)，考虑如何确定x(k+1)， 根据下降方向的选择不同，我们有不同的下降算法！ 下面主要介绍最速下降法和共轭梯度法。 Date 17 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U. 4.1 最速下降法 我们知道，函数的负梯度方向是函数值下降最快的方向。 取 的下降算法称为最速下降算法。 从而得到满足的点 Date 18 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U. 算法描述如下： 注： r(k+1)和r(k)正交! 这是因为 Date 19 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U. 收敛定理： 设A的特征值为则由上述算法得到的序列满足 其中 1 该算法简单易行，可充分利用A的稀疏性等特点，但当 A的最大特征值远远大于最小特征值时收敛速度变得非常 慢，以至于完全不适用。 注： 2 最速下降法并非最速！ Date 20 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U. 4.2 共轭梯度(CG)算法 有比负梯度方向更好的下降方向吗？ 设x(k)是沿下降方向p(k-1)求得的，且x(k)的最速下降方向为r(k)=b-Ax(k) 。 下面确定x(k)的下降方向p(k)，使之满足： 从而由极小值问题： 可以确定x(k+1)。 注：A共轭向量是线性无关的!# Date 21 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U. 由 令 则 具体做法如下： 共轭梯度方向 Date 22 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U. 算法如下： 共轭梯度算法！ 确定下降 方向 计算极小值 点 Date 23 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U. 共轭梯度算法的收敛性： 对于共轭梯度算法，可以证明： (1) (2) (3) (4) 说明，共轭梯度算法至多n步就能得到精确解 注 ： 1、实际计算中由于误差的影响，r(k)之间的正交性很快就 会消失，以 至于有限步内不