2数值分析讲义――线性方程组的解法

数值分析讲义第三章线性方程组的解法§3.0引言§3.1雅可比(Jacobi)迭代法§3.2高斯-塞德尔(Gauss-Seidel)迭代法§3.3超松驰迭代法§3.7三角分解法§3.4迭代法的收敛性§3.8追赶法§3.5高斯消去法§3.9其它应用§3.6高斯主元素消去法§3.10误差分析§3作业讲评3§3.11总结§3.0引言重要性：解线性代数方程组的有效方法在计算数学和科学计算中具有特殊的地位和作用.如弹性力学、电路分析、热传导和振动、以及社会科学及定量分析商业经济中的各种问题.分类：线性方程组的解法可分为直接法和迭代法两种方法.(a)直接法：对于给定的方程组，在没有舍入误差的假设下，能在预定的运算次数内求得精确解.最基本的直接法是Gauss消去法，重要的直接法全都受到Gauss消去法的启发.计算代价高.(b)迭代法：基于一定的递推格式，产生逼近方程组精确解的近似序列.收敛性是其为迭代法的前提，此外，存在收敛速度与误差估计问题.简单实用,诱人.§3.1雅可比Jacobi迭代法(AX=b)1基本思想:与解f(x)=0的不动点迭代相类似,将AX=b改写为X=BX+f的形式,建立雅可比方法的迭代格式：Xk+1=BX(k)+f,其中，B称为迭代矩阵.其计算精度可控,特别适用于求解系数为大型稀疏矩阵(sparsematrices)的方程组.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.0213312321xxxxxxxxx(2)据此建立迭代公式：84.02.01.083.02.01.072.02.01.0)(2)(1)1(3)(3)(1)1(23)(2)1(1kkkkkkkkkxxxxxxxxx(3)取迭代初值0)0(3)0(2)0(1xxx,迭代结果如下表.JocabiMethodP31.cpp迭代次数x1x2x3000010.720.830.8420.9711.071.1531.0571.15711.248241.085351.185341.2828251.0950981.1950991.29413861.0983381.1983371.29803971.0994421.1994421.29933581.0998111.1998111.29977791.0999361.1999361.299924101.0999791.1999791.299975111.0999931.1999931.299991121.0999981.1999981.299997131.0999991.1999991.299999141.11.21.3151.11.21.34Jocobi迭代公式:设方程组AX=b,通过分离变量的过程建立Jocobi迭代公式，即),,2,1()(1),,2,1(0,11nixabaxniabxanijjjijiiiiiiniijij由此我们可以得到Jacobi迭代公式：),,2,1()(11)1(nixabaxnijjkiijiiiki[Jacobi迭代公式的算法]1:初始化.n,(aij),(bj),(x1),M.2:执行k=1直到M为止.①执行i=1直到n为止.iinijjjijiiaxabu/)(1;②执行i=1直到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□§3.2高斯-塞德尔Gauss-Seidel迭代法注意到利用Jocobi迭代公式计算)1(kix时，已经计算好)(1)(2)(1,,,kikkxxx的值，而Jocobi迭代公式并不利用这些最新的近似值计算，仍用)(1)(2)(1,,,kikkxxx.这启发我们可以对其加以改进,即在每个分量的计算中尽量利用最新的迭代值，得到),,2,1()(1111)1()1(nixaxabaxnijkjijijkjijiiiki上式称为Gauss-Seidel迭代法.其矩阵形式是X=-(D+L)-1UX+(D+L)-1b,Xk+1=BX(k)+f.迭代次数x1x2x3000010.720.9021.164421.043081.1671881.28205431.093131.1957241.29777141.0991261.1994671.29971951.099891.1999331.29996561.0999861.1999921.29999671.0999981.1999991.29999981.11.21.3§3.3超松驰迭代法SOR方法1基本思想:逐次超松弛迭代法(SuccessiveOverRelaxationMethod,简写为SOR)可以看作带参数ω的高斯-塞德尔迭代法，是G-S方法的一种修正或加速.是求解大型稀疏矩阵方程组的有效方法之一.2SOR算法的构造:设方程组AX=b,其中，A=(aij)n为非奇异阵，X=(x1,x2,…,xn)T,b=(b1,b2,…,bn)T.假设已算出x(k)，),,2,1()(1111)1()1(nixaxabaxnijkjijijkjijiiiki(1)相当于用高斯-塞德尔方法计算一个分量的公式.若对某个参数ω，作)1(kix与)(kix加权的平均,即)()1()()1()()1()(1kikikikikikixxxxxx(2)其中，ω称为松弛因子.用(1)式代入(2)式，就得到解方程组AX=b的逐次超松弛迭代公式：),,2,1()()(11)1()()1(nixaxabaxxxxnijkjijijkjijiiiiikiki(3)显然，当取ω=1时，式(3)就是高斯-塞德尔迭代公式.3例题分析:利用SOR方法解方程组3322242024321321321xxxxxxxxx(1)其准确解为X*={1,1,2}.建立与式(1)相等价的形式：132315.05.05.025.05.0213312321xxxxxxxxx(2)据此建立迭代公式：132315.05.05.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,迭代结果如下表.逐次超松弛迭代法次数x1x2x310.6250000.0625001.75000020.3906250.8828131.46875031.0175780.5166021.80859440.5568850.8809811.71044951.0237120.7434231.86810360.7462500.9084191.83873770.9977150.8602641.91389480.8640500.9367421.90860590.9862590.9222251.945523100.9281100.9586491.947493110.9852420.9559441.966198120.9616610.9738181.969521130.9881030.9746991.979289140.9792060.9837461.982172150.9915210.9853181.987416160.9885090.9900381.989513170.9943410.9914141.992397180.9935380.9939461.993806190.9963670.9949501.995424200.9963130.9963421.996331210.9977240.9970181.997254220.9978710.9977981.997822230.9985960.9982341.998355GS迭代法须迭代85次得到准确值X*={1,1,2};而SOR方法只须55次即得准确值.由此可见，适当地选择松弛因子ω，SOR法具有明显的加速收敛效果.□§3.4迭代法的收敛性1.向量和矩阵范数(a)向量范数Rn空间的向量范数||·||,对任意nRyx,,满足下列条件：00||||;0||||)1(xxx(正定性)||||||||||)2(xx(齐次性)||||||||||||)3(yxyx（三角不等式）常见的向量范数有：(1)列范数：(2)谱范数：(欧几里德范数或向量的长度,模)(3)行范数：(4)p范数:上述范数的几何意义是:||||x=max(|x2-x1|,|y2-y1|);1||||x=|x2-x1|+|y2-y1|;2122122)()(||||yyxxx.向量序列}{)(kx依坐标收敛于向量x*的充要条件是向量序列}{)(kx依范数收敛于向量x*,即0||||lim*)(xxkk.(b)矩阵范数nmR空间的向量范数||·||,对任意nmRBA,,满足下列条件：||||||||||AB||(4)||||||||||||)3(||||||||||)2(00||||;0||||)1(BABABAAAAAA常见的矩阵范数有：njijaAni1||max||||1(行和范数)niijaAnj11||max||||1(列和范数))(||||max2AAAT(谱范数)若A对称，则有)()(2maxmaxAAAT.矩阵A的谱半径记为)(||||2AA,(A)=||max1ini,其中i为A的特征根。2.迭代法基本定理设有方程组X=BX+f,对于任意初始向量X(0)及任意f,迭代公式X(k+1)=BX(k)+f收敛的充要条件是)(B1,)(B为矩阵B的谱半径.证：设X*为方程组X=BX+f的准确解，即X*=BX*+f.对于任意初始向量X(0)及任意f,迭代公式X(k+1)=BX(k)+f,于是，)()()()(*)0(*)2(2*)1(*)1(*)(XXBXXBXXBfBXfBXXXkkkkk由此可得,迭代法收敛的充要条件是)(0kBk.即,)(B1.□上述定理是线性方程组迭代解法收敛性分析的基本定理，然而由于)(B的计算往往比较困难，尽管有各种办法估计)(B的上界，但往往偏听偏大而不实用，由此导致定理的理论价值胜于实用价值，为满足实际判敛的需要，有如下定理.(迭代收敛的充分条件)设有迭代公式X(k+1)=BX(k)+f，如果||B||1,则对于任意初始向量X(0)及任意f,迭代公式均收敛.3.从方程组的系数矩阵A判断迭代收敛性实际中要求解的某些线性方程组，其系数矩阵往往具有一些特点，如系数矩阵为对称正定、对角元素占优等.由这些方程组系数矩阵的特殊性，使得我们可以直接从方程组的系数矩阵A出发来讨论迭代法的收敛性.设nnnnijRaA)(，满足nijjijiiniaa1,,2,1,||||且至少有一个i值，使得nijjijiiaa1||||成立，则称A为对角占优矩