《应用数值分析》课件数值分析5.6线性方程组的数值解法.pptx

1、第第5章章 线性方程组的数值解法线性方程组的数值解法5.2 方程组的性态与条件数-基本的高斯消元法5.3 高斯消元法高斯列主元消去法高斯 若当消去法矩阵的三角分解5.4 基于矩阵三角分解的方法 平方根法和改进的平方根法追赶法（三对角矩阵）-SOR雅可比迭代法5.5 雅可比迭代法和高斯 赛德尔迭代法高斯 赛德尔迭代法5.6 逐次超松弛迭代法（）直接法迭代法5.1 引言bAx 改善迭代法收敛速度的基本思想：xxbAx余量()()0kkrb Ax(1)()()kkkxxbAx(1)()()kkkxxr(1)()()()kkkxxP bAx更一般地 特别地 1=1,PD，为雅克比迭代。同步迭代余量(1

2、)()()kkb LxD U x(1)()(1)()()kkkkxxP bLxDU x特别地 1=1,PD，为高斯-塞德尔迭代。异步迭代若只固定 1,PD称为逐次超松弛迭代法（Successive Over Relaxation Method,简称SOR方法）松弛因子1时，称为欠松弛法欠松弛法1时，称为超松弛法超松弛法 无论是解线性方程组的无论是解线性方程组的Jacobi迭代法还是迭代法还是G-S迭代法，迭代法，都涉及到收敛速度问题，也涉及到初值的都涉及到收敛速度问题，也涉及到初值的选取问题选取问题.逐次超松弛迭代法（逐次超松弛迭代法（Successive Over Relaxation Me

3、thod,简称简称SOR方法）是方法）是G-S方法的一种加速方法，方法的一种加速方法，是 解 大 型 稀 疏 矩 阵 方 程 组 的 有 效 方 法 之 一是 解 大 型 稀 疏 矩 阵 方 程 组 的 有 效 方 法 之 一.5.6 5.6 SOR(逐次超松弛逐次超松弛)迭代法迭代法SOR(逐次逐次超松弛超松弛)迭代法迭代法1,1,1,Gaussseidel 为为迭迭代代法法称称为为低低松松弛弛法法称称为为超超松松弛弛法法SOR迭代公式矩阵形式迭代公式矩阵形式111111111()()()()()()()()()()()()()()()()kkkkkkkkkkxxDLxUxbDxDxLxUx

4、bDL xDU xb用用G-S法和法和SOR法求下列方程组的解法求下列方程组的解,1 45.取取321242124321xxx320要求精度要求精度1e-6例例1解解:(1)G-S迭代法迭代法GB1()DLU 1400240123 021002000GB5.03/10625.025.0025.05.00f1()DLb13210420043203/25.00(0)(0,0,)Tx取初值满足精度的解满足精度的解迭代次数为迭代次数为71次次0.999995x0.9999941.999995111()()()()kkxDLDU x1()DLb(2)SOR迭代法迭代法()kB xf满足精度的解满足精度的

5、解迭代次数为迭代次数为24次次00 0()(,)Tx取取初初值值0.999996x0.9999981.999997SOR法的收敛速度比法的收敛速度比G-S法要快得多法要快得多,选取适当的 例例3 用用SOR方法解线性方程组方法解线性方程组Ax=b12344111114111.1141111141xxxx 解解 取初始向量取初始向量x(0)=0，迭代公式为，迭代公式为它的精确解为它的精确解为x*=(-1,-1,-1,-1)T.(1)()()()()()111234(1)()(1)()()()221234(1)()(1)(1)()()331234(1)()(1)(1)(1)()441234(14)

6、/4,(14)/4,(14)/4,(14)/4.kkkkkkkkkkkkkkkkkkkkkkkkxxxxxxxxxxxxxxxxxxxxxxxx 取取=1.3，第，第11次迭代结果为次迭代结果为(11)(0.99999646,1.00000310,0.99999953,0.99999912),Tx (11)520.46 10.满足误差满足误差迭代次数迭代次数k1.01.11.21.31.41.51.61.71.81.922171211(最少迭代次数最少迭代次数)1417233353109()5210.k 对对 取其它值，迭代次数如表取其它值，迭代次数如表.从此例看到，松弛因子选择从此例看到，松

7、弛因子选择得好，会使得好，会使SOR迭代法的收迭代法的收敛大大加速敛大大加速.本例中本例中=1.3是是最佳松弛因子最佳松弛因子.5.6.102SOR 方方法法收收敛敛的的条条件件是是必必要要定定理理 选选择择的的实实用用方方法法1选选择择最最优优松松弛弛因因子子(Y Yo ou un ng g（）-1 19 95 50 0)2实实用用中中采采取取试试算算法法是是最最有有效效的的（）逐逐步步搜搜索索）5.6 2.20AxbAwSOR 若若线线性性方方程程组组的的系系数数矩矩阵阵 为为对对称称正正定定矩矩阵阵，且且，则则解解此此方方程程组组的的迭迭代代定定理理 法法收收敛敛。5.6 1.30Axb

8、AwSOR 若若线线性性方方程程组组的的系系数数矩矩阵阵严严格格对对角角占占优优，则则解解此此方方程程组组的的迭迭代代定定理理 法法收收敛敛。SORSOR法的收敛性法的收敛性1(1)()()11()(1)(1)(1)(1)1211()1,2,inkkkiijjijjijj iiikkkkkixa xa xbinaxxxxx 1)雅克比迭代公式每次迭代使用的所有分量计算没有利用已经计算出的。1(1)(1)()11(1)()(1)(1)(1)1211()1,2,inkkkiijjijjijj iiikkjkkkixa xa xbinaxxxxx 2)高斯赛德尔迭代公式计算时使用(j=i+1,n)和

9、已经计算出的解线性方程组的迭代法小结解线性方程组的迭代法小结(1)()(1)(),.,.kkjjkknjGSxxxx3）G-S迭代中 计算出后便不需要了 而在J迭代中 一直要到计算出来后 才不需要G-S迭代法的程序设计要比J迭代法省事 这是迭代法的优点,.,4)求迭代矩阵的谱半径需要求特征值 阶数较大时是很麻烦的利用矩阵范数去判别比较方便实际中 线性方程组的系数矩阵是对称正定或对角元素占优时 可方便地判别迭代法的收敛性.,.,.5）某个线性方程组 可能用J法收敛 而用G-S法不收敛 也可能前者不收敛 而后者收敛，也可能两种迭代方法收敛性相同在都收敛的情况下 收敛性的速度取决于谱半径的大小作业9 第5章小结 课后习题：1-16 数值实验：1、4