《科学与计算工程办法第3章》由会员分享，可在线阅读，更多相关《科学与计算工程办法第3章（45页珍藏版）》请在金锄头文库上搜索。
1、第三章 线性方程组的解法 第三章 线性方程组的解法 3.0 引言引言 3.1 雅可比雅可比(Jacobi)迭代法迭代法 3.2 高斯高斯-塞德尔塞德尔(Gauss-Seidel)迭代法迭代法3.3 超松驰迭代法超松驰迭代法3.4 迭代法的收敛性迭代法的收敛性 3.5 高斯消去法高斯消去法3.6 高斯主元素消去法高斯主元素消去法3 作业讲评作业讲评 33.7 三角分解法三角分解法3.8 追赶法追赶法 3.9 其它应用其它应用3.10 误差分析误差分析 3.11 总结总结 3.0 引 言 3.0 引 言 重要性：解线性代数方程组的有效方法在计算数学和科学计算中具有特殊的地位和作用.如弹性力学、电路
2、分析、热传导和振动、以及社会科学及定量分析商业经济中的各种问题. 分类：线性方程组的解法可分为直接法和迭代法两种方法. (a) 直接法：对于给定的方程组，在没有舍入误差的假设下，能在预定的运算次数内求得精确解.最基本的直接法是 Gauss 消去法，重要的直接法全都受到 Gauss 消去法的启发.计算代价高. (b) 迭代法：基于一定的递推格式，产生逼近方程组精确解的近似序列.收敛性是其为迭代法的前提，此外，存在收敛速度与误差估计问题.简单实用,诱人. 3.1 雅可比 Jacobi 迭代法 (AX=b) 1 基本思想: 与解f(x)=0 的不动点迭代相类似,将AX=b改写为X=BX+f 的形式,
3、建立雅可比方法的迭代格式： Xk+1=BX(k)+f ,其中， B称为迭代矩阵.其计算精度可控,特别适用于求解系数为大型稀疏矩阵(sparse matrices)的方程组. 2 问题: (a) 如何建立迭代格式？如何建立迭代格式？ (b) 向量序列向量序列Xk是否收敛以及收敛条件是否收敛以及收敛条件? 3 例题分析: 考虑解方程组 =+=+=2 . 453 . 82102 . 7210321321321xxxxxxxxx(1) 其准确解为X*=1, 1.2, 1.3. 建立与式(1)相等价的形式： +=+=+=84. 02 . 01 . 083. 02 . 01 . 072. 02 . 01
4、. 0213312321xxxxxxxxx(2) 据此建立迭代公式： (3) +=+=+=+84. 02 . 01 . 083. 02 . 01 . 072. 02 . 01 . 0)( 2)( 1)1( 3)( 3)( 1)1( 23)( 2)1( 1kkkkkkkkkxxxxxxxxx取迭代初值0)0( 3)0( 2)0( 1=xxx,迭代结果如下表. JocabiMethodP31.cpp 迭代次数 x1 x2 x3 0 0 0 0 1 0.72 0.83 0.84 2 0.971 1.07 1.15 3 1.057 1.1571 1.2482 4 1.08535 1.18534 1.2
5、8282 5 1.095098 1.195099 1.294138 6 1.098338 1.198337 1.298039 7 1.099442 1.199442 1.299335 8 1.099811 1.199811 1.299777 9 1.099936 1.199936 1.299924 10 1.099979 1.199979 1.299975 11 1.099993 1.199993 1.299991 12 1.099998 1.199998 1.299997 13 1.099999 1.199999 1.299999 14 1.1 1.2 1.3 15 1.1 1.2 1.3
6、4 Jocobi 迭代公式: 设方程组 AX=b, 通过分离变量的过程建立 Jocobi 迭代公式，即 ), 2 , 1()(1), 2 , 1(0,11nixabaxniabxanijjjiji iiiiiniijij?=由此我们可以得到 Jacobi 迭代公式： ), 2 , 1()(11)1(nixabaxnijjk iiji iik i?=+Jacobi 迭代公式的算法迭代公式的算法 1: 初始化. n, (aij), (bj), (x1) , M. 2: 执行 k=1 直到 M 为止. 执行 i=1 直到 n 为止. ; iinijjjijiiaxabu/ )( 1= 执行 i=1
7、直到 n 为止. ; iiux 输出k, (xi). 另外，我们也可以建立 Jacobi 迭代公式的矩阵形式. 设方程组 AX=b, 其中，A=(aij)n为非奇异阵， X=(x1,x2,xn)T, b=(b1,b2,bn)T将系数阵 A 分解为: A=U+D+L, U 为上三角矩阵，D 为对角矩阵，L 为下三角矩阵. 于是 AX=b 可改写为 (U+D+L)X=b X=D-1b-D-1(U+L)X 由此可得矩阵形式的 Jocobi 迭代公式： Xk+1=BX(k)+f 2 高斯-塞德尔 Gauss-Seidel 迭代法 注意到利用 Jocobi 迭代公式计算)1(+k ix时，已经计算好的值
8、，而 Jocobi 迭代公式并不利用这些最新的近似值计算，仍用.这启发我们可以对其加以改进,即在每个分量的计算中尽量利用最新的迭代值，得到 )( 1)( 2)( 1,k ikkxxx?)( 1)( 2)( 1,k ikkxxx?), 2 , 1()(1111)1()1(nixaxabaxnijk jijijk jiji iik i?= +=+上式称为 Gauss-Seidel 迭代法. 其矩阵形式是 X=-(D+ +L L) )-1UX+ +(D+ +L L) )-1b, , Xk+1=BX(k)+f . . 迭代次数 x1 x2 x3 0 0 0 0 1 0.72 0.902 1.1644
9、2 1.04308 1.167188 1.282054 3 1.09313 1.195724 1.297771 4 1.099126 1.199467 1.299719 5 1.09989 1.199933 1.299965 6 1.099986 1.199992 1.299996 7 1.099998 1.199999 1.299999 8 1.1 1.2 1.3 3.2 超松驰迭代法 SOR 方法 1 基本思想: 逐次超松弛迭代法(Successive Over Relaxation Method,简写为 SOR)可以看作带参数的高斯-塞德尔迭代法， 是 G-S 方法的一种修正或加速.是求
10、解大型稀疏矩阵方程组的有效方法之一. 2 SOR 算法的构造: 设方程组AX=b, 其中，A=(aij)n为非奇异阵，X=(x1,x2,xn)T, b=(b1,b2,bn)T. 假设已算出x(k)， ), 2 , 1()(1111)1()1(nixaxabaxnijk jijijk jiji iik i?= +=+(1) 相当于用高斯-塞德尔方法计算一个分量的公式. 若对某个参数，作)1( +k ix与加权的平均,即 )(k ix)()1 ()()1()()1()(1k ik ik ik ik ik ixxxxxx+=+=+(2) 其中，称为松弛因子. 用(1)式代入(2)式，就得到解方程组
11、AX=b 的逐次超松弛迭代公式： =+=+), 2 , 1()()(11)1()()1(nixaxabaxxxxnijk jijijk jiji iiiik ik i?(3) 显然，当取=1 时，式(3)就是高斯-塞德尔迭代公式. 3 例题分析: 利用 SOR 方法解方程组 =+=+=3322242024321321321xxxxxxxxx(1) 其准确解为X*=1, 1, 2. 建立与式(1)相等价的形式： +=+=+=132 315 . 05 . 05 . 025. 05 . 0213312321xxxxxxxxx(2) 据此建立迭代公式： +=+=+=+132 315 . 05 . 05
12、 . 025. 05 . 0)( 2)( 1)1( 3)( 3)( 1)1( 23)( 2)1( 1kkkkkkkkkxxxxxxxxx(3) 利用 SOR 算法，取迭代初值1)0( 3)0( 2)0( 1=xxx, =1.5,迭代结果如下表. 逐次超松弛迭代法 次数 x1 x2 x3 1 0.625000 0.062500 1.750000 2 0.390625 0.882813 1.468750 3 1.017578 0.516602 1.808594 4 0.556885 0.880981 1.710449 5 1.023712 0.743423 1.868103 6 0.746250
13、0.908419 1.838737 7 0.997715 0.860264 1.913894 8 0.864050 0.936742 1.908605 9 0.986259 0.922225 1.945523 10 0.928110 0.958649 1.947493 11 0.985242 0.955944 1.966198 12 0.961661 0.973818 1.969521 13 0.988103 0.974699 1.979289 14 0.979206 0.983746 1.982172 15 0.991521 0.985318 1.987416 16 0.988509 0.990038 1.989513 17 0.994341 0.991414 1.992397 18 0.993538 0.993946 1.993806 19 0.996367 0.994950 1.995424 20 0.996313 0.996342 1.996331 21 0.997724 0.997018 1.997254 22 0.997871 0.997798 1.997822 23
