资源预览内容
第1页 / 共34页
第2页 / 共34页
第3页 / 共34页
第4页 / 共34页
第5页 / 共34页
第6页 / 共34页
第7页 / 共34页
第8页 / 共34页
第9页 / 共34页
第10页 / 共34页
亲,该文档总共34页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
计 算 方 法,第八章 线性方程组的解法,计算方法课程组,8.0 引 言,重要性:解线性代数方程组的有效方法在计算数学和 科学计算中具有特殊的地位和作用。如弹性力学、电 路分析、热传导和振动、以及社会科学及定量分析商 业经济中的各种问题。,求解线性方程组 的求解方法,其中 , 。,假设 非奇异,则方程组有唯一解.,8.0 引 言,分类: 线性方程组的解法可分为直接法和迭代法两种方法。 直接法: 对于给定的方程组,在没有舍入误差的假设下,能在预定的运算次数内求得精确解。最基本的直接法是Gauss消去法,重要的直接法全都受到Gauss消去法的启发。 计算代价高. 迭代法:基于一定的递推格式,产生逼近方程组精确解的近似序列.收敛性是其为迭代法的前提,此外,存在收敛速度与误差估计问题。简单实用, 诱人。,8.1 雅可比Jacobi迭代法 (AX=b),一、迭代法的基本思想,二、例题分析,三、 Jacobi迭代公式,与解f (x)=0 的不动点迭代相类似,将AX=b改写为X=BX+f 的形式,建立雅可比方法的迭代格式: 其中,B称为迭代矩阵。其计算精度可控,特别适用于求解系数为大型稀疏矩阵(sparse matrices)的方程组。,8.1 雅可比Jacobi迭代法 (AX=b),迭代法的基本思想,问题: (a) 如何建立迭代格式? (b) 向量序列 x(k) 是否收敛以及收敛条件?,2 例题分析:,其准确解为X*= 1.1, 1.2, 1.3 。,考虑解方程组,(1),3.1Jacobi迭代法,2 例题分析:,建立与式(1)相等价的形式:,(2),其准确解为X*=1.1, 1.2, 1.3。,考虑解方程组,(1),3.1Jacobi迭代法,2 例题分析:,其准确解为X*=1.1, 1.2, 1.3。,建立与式(1)相等价的形式:,考虑解方程组,取迭代初值,据此建立迭代公式:,迭代结果如下表:,设方程组 AX=b , 通过分离变量的过程建立Jacobi迭代公式,即,由此我们可以得到 Jacobi 迭代公式:,8.1 Jacobi迭代公式, 雅可比迭代法的矩阵表示,写成矩阵形式:,L,U,D,Jacobi 迭代阵,8.2 高斯-塞德尔迭代法 (AX=b),注意到利用Jacobi迭代公式计算,时,已经计算好了,的值,而Jacobi迭代公式并不利用这些最新的近似值计算, 仍用, ,写成矩阵形式:,Gauss-Seidel 迭代阵,8.2 高斯-塞德尔迭代法,其准确解为X*=1.1, 1.2, 1.3。,考虑解方程组,高斯-塞德尔迭代法算例,高斯-塞德尔迭代格式,开始,T,F,T,F,T,逐次超松弛迭代法(Successive Over Relaxation Method,简写为SOR)可以看作带参数的高斯-塞德 尔迭代法,是 G-S 方法的一种修正或加速,是求解大 型稀疏矩阵方程组的有效方法之一。,8.3 超松驰迭代法SOR方法,1. SOR基本思想,设方程组AX=b, 其中,A=(aij) 为非奇异阵, x=(x1, x2, , xn)T, b=(b1, b2, , bn)T. 假设已算出 x(k) ,,8.3 超松驰迭代法SOR方法,2. SOR算法的构造,称为松弛因子,利用高斯-塞德尔迭代法得:,8.3 超松驰迭代法SOR方法,2. SOR算法的构造 (基于G-S迭代),解方程组AX=b的逐次超松弛迭代公式:,显然,当取=1时,上式就是高斯-塞德尔迭代公式.,8.3 超松驰迭代法SOR方法,2. SOR算法的构造(基于Jacobi迭代),得到解方程组 AX=b 的逐次超松弛迭代公式:,显然,上式就是 基于Jacobi 迭代的 SOR 方法.,下面令 , 希望通过选取合适的 来加速收敛,这就是松弛法 。,3. SOR算法的进一步解释,SOR方法,其中ri(k+1) =,相当于在 的基础上加个余项生成 。,利用SOR方法解方程组,SOR例题分析:,其准确解为x*=1, 1, 2.,建立与式(1)相等价的形式:,据此建立G-S迭代公式:,取迭代初值:,=1.5,迭代结果如下表.,SOR迭代公式为:,GS迭代法须迭代85次得到准确值 x*=1, 1, 2;而 SOR方法只须55次即得准确值.,由此可见,适当地选择松弛因子,SOR法具有明显的加速收敛效果.,关于SOR方法的说明: 显然,当 时,SOR方法就是Gauss- Seidel方法。 SOR 方法每一次迭代的主要运算量是计算一次矩阵与向量的乘法。 时称为超松弛方法, 时称为低松弛方法。 计算机实现时可用 控制迭代终止,或用 SOR方法可以看成是Gauss-Seidel方法的一种修正。,(迭代法基本定理) 设有方程组 ,对于任意的初始向 量 ,迭代公式 收敛的充要条件是迭 代矩阵 的谱半径 .,8.4 迭代法的收敛性-充要条件,迭代法的基本定理在理论分析中有重要意义。,定理2:设X*是方程组AX = b的同解方程X = BX + F 的准确解,若迭代公式中迭代矩阵B的某种范数,,(1),(2),则有,在具体使用上,由于 ,因此,我们利用范数可以建立判别迭代法收敛的充分条件。,关于解某些特殊方程组迭代法的收敛性 定义:(对角占优阵) 设 (1) 如果 元素满足 称 为严格对角占优阵 (2) 如果 元素满足 且上式至少有一个不等式严格成立, 称 为弱对角占优阵。,设 ,如果: 为严格对角占优,则解 的Jacobi迭代法, Gauss-Seidel迭代法均收敛。,Seidel迭代格式为,从式中解出,故可得Seidel迭代矩阵为,从例中可以看出Jacobi迭代矩阵Bj的主对角线为零,而Seidel迭代矩阵Bs的第1列都是零,这对一般情况也是成立的。,举例检验Jacoai迭代的收敛性,首先将原方程组写为迭代形式的方程组,即:,求任一行之和的最大值1,即: |M|=max5/8,5/11,9/12=9/121,i,或求任一列之和的最大值1,即: |M|1=max114/132,60/96,30/88=114/1321,结论:该方程组采用Jacobi迭代法计算是收敛的。,已知线性方程组为:,8.5 迭代法的误差估计,定理4:设X*是方程组AX = b的同解方程X = BX + F 的准确解,若迭代公式中迭代矩阵B的某种范数,,(1),(2),则有,
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号