解线性代数方程组的迭代法

迭代法适用于求解大型稀疏的线性方程组，其基本思想是通过构造迭代格式产生迭代序列，由迭代序列来逼近原方程组的解，因此，要解决的基本问题是：1.如何构造迭代格式2.迭代序列是否收敛第六章解线性代数方程组的迭代法一.基本迭代法的格式及收敛性二.几种实用的基本迭代法三.应用实例一.基本迭代法的格式及收敛性设有线性代数方程组a11x1+a12x2+····+a1nxn=b1a21x1+a22x2+····+a2nxn=b2.....................an1x1+an2x2+····+annxn=bnA=M+NM的逆好求。Ax=b(M+N)x=bMx=-Nx+bx=-M-1Nx+M-1b用矩阵表示：Ax=bA为系数矩阵，非奇异且设aii≠0；b为右端，x为解向量11,,AxbxBxgBMNgMb1(11)(),,(0,1,2,)nkknxBAxbxBxxgBMNgMbkBRgng基其中称为迭代矩本迭代法的阵，是已知迭格式的代维向量，(0)(1)()(),{}kkkxxBxgx给定由迭代格式即可产生迭代序列。()(1)()limkkkkxxxBxgxBxgAxb当对取极限得注：分解A是一个重要问题20,3336,AxbAbAAMNMN例：解：8-32对线性方程组，其中=411-163128000-32将分解为,其中=0110=40-10012630231312()20323343663AxbxMNxMbMbNxxxxxxx-1-1-110081001110012231312(2032)/8(334)/11(3663)/12xxxxxxxxx123()()23()()13()()12(2032)/8(334)/11(3663)/120,1,2,....kkkkkkxxxxxxxxxk(k+1)1(k+1)2(k+1)3迭代格式的分量形式为(3.000032,1.999838,0.9998813)(3,2,1)TTxx(10)迭代到第10次,得到已知精确解为(1)(),kkxBxgBg迭代格式32200-8884133迭代矩阵=-01111116336--0121212(1)()()(0)(){}kkkkxBxgxxxxk基本迭代法产生的迭代序列，如果对任取初始向量都有lim，则称此迭代法是收敛的，否则是定义发散的。()()()()1212()()(,,,),(,,,),limlim,(1,2,,)kkkkTnTnnkkiikkxxxxxxxxRxxxxin对则在Rn中，点列的收敛等价于每个分量的收敛。即()()()()()(),(),limlim,(,1,2,,)kkkijijkkijijkkAAaAaAAaaijn同理，的收敛与所选择的范数无关。若则lim0kkB()(1)()()(1)(1)(0)(0)(0)()kkkkkkkxAxbxBxgxBxgxxBxxBBxx是精确解迭代格式为误差向量其中是初始误差向量，是一个确定的值收敛性分析(0)()0()kkxxBk由此，得到结论:对任意初值，迭代序列收敛121rJordanPJJPBPJJ由矩阵的标准型知存在非奇异阵使(1)()(0)()()1.kkxBxgxB迭代法收敛的充要条件迭代格式对任意初始向量都收敛的充分必要条件是定理1()(0):0().0()()1.kkkkBBkBkB由知迭代法收敛以下证明的充分必要条件是证明(),11(1,2,,)1iiiiiiiinnJJir为若当块且1111111,riikknnBPJPJPBPJPBPPBPPBPPBP于是112,(1,2,)kkkkkrJJPBPJkJ1,,00kkkkBPJPkBJ故显然当时1200(1,2,,)()()max(,,,),01,(1,2,,)kkirkiiJJirBJJir为此只需证明2222121102101,02,0000(1)2000kkkkkkkJJkkkJk例:01()0()1(1,2,,)0()()1jkjkkiikCkJkirBkB由极限运算知：所以即此结论1(1)112(2)1111()!(1)(1),!()!!iiiiiinknkkikikinknkkikikikikkikinnjkccccJckkkkjCjkjj其中21,2det()60,6,()2.4491.1.IBB由得由定理迭代格式不收敛12122535xxxx用迭代法求程组例：解方(1)()(1)()12(1)()21:,52(1,2,)35025,305kkkkkkxBxgxxkxxBg构造迭代格解式，迭代矩阵()(1)()12,.kkxBxgBB迭代法收敛的充分条件如果迭代格式的迭代矩阵的某一种范数则此迭定代格式收敛理,.,(1,2,)()nnppARpAA（特征值上界定理）设对于有引理:,,,.pppppAUAUUUUAUAUAA设是的任一特征值为相应的特征向量则有因是证的任一特征值故定理得证明()(1)()()()()(1)1kkkkkkkxxBxxBxxBxxxxB从而()(1)()()(1)()(1)(0)1,.113kkkkkkkxBxgBBBxxxxBBxxxxB如果迭代格式的迭代矩阵满足则有如下的误差估计式定理()(1)()(1)(1)()():()()()kkkkkkkxBxgxBxgxxBxxBxxBxx由和证明有:(1),.(2)1,.BB注越小收敛越快接近时收敛慢()(1)(1)(2)1(1)(2)(1)(0)()()()kkkkkkkxxBxxBxxBxx()()(1)(1)(0)11kkkkBBxxxxxxBB()(1)(1)(2)()(1)(1)(2)()kkkkkkkkxBxgxBxgxxBxx又因为，maxmax(3)kkk给出最大迭代次数当迭代终止，给出失败信息。()(1)()()(1)()(1)||||1,2,,.,||(||ma|1)x|kkpkkkkkiiixxpxxpxxxx绝对误差标准。给出容许误差界当时，终止迭代，解取为常取()(1)()||||||||(2)kkkxxx相对误差标准。给出容许误差界迭代终止标准()(1)(0)1kkBxxxxB由误差估计式估计迭代次数()(1)(0)(1)(0)1ln1()lnkkBxxkBxxxxBB估计迭代次数()(0)()(0)(0)()(0)|||||||||||||(())||||(())01||||||||.(()).kkkkkkkkBBBBB由说明表示迭代误差的缩减因子，若希望实际的缩减因子为（），即则可令渐近收敛速度6106ln10ln(ln())ln(())kBkB由此，可估计出所需的迭代次数相当于相对误差限，如取，则有ln(())RB为迭代格式的渐定义近收敛速度。二.几种实用的基本迭代法1、Jacobi迭代法2、Gauss-Seidel迭代法3、超松弛迭代法（SOR)1、Jacobi迭代12121211,12,112nnnnnnnnnaaADaaaUaLaaaa422142114400000022040,100,002004110000ADLUDLU例：1111()(),JJAxbxDLUxDbBxgBDLUgDb于是其中(1)()kkJJacoxxgiBb迭代的矩阵格式Jacobi迭代矩阵11()()()AxbDLUxbDxLUxbxDLUxDb推导其分量形式1111221331122221123322112211nnnnnnnnnnnnnaxaxaxaxbaxaxaxaxbaxaxaxaxb第i个方程除以aii(i=1,2,…,n),得()()AxbDLUxbDxLUxb由得1311211231111111123221221322222222121121nnnnnnnnnnnnnnnnnnnaaabxxxxaaaaaaabxxxxaaaaaaabxxxxaaaa1311211231111111123221221322222222121121nnnnnnnnnnnnnnnnnnnaaabxxxxaaaaaaabxxxxaaaaaaabxxxxaaaaJacobi迭代的分量形式(1)()()()13112121311111111(1)()()()23221213222222222(1)()()()121121kkkknnkkkknnkkkknnnnnnnnnnnnnnnaaabxxxxaaaaaaabxxxxaaaaaaabxxxxaaaa1121111111()12221()()2222222()1200,0nknkkJknnnnnnnnnnaabaaaxabaxaaaBxgxbaaaaa令：，则x(k+1)=BJx(k)+g，这里BJ=D-1(L+U),g=D-1b(1)()1()/,1,2,,nkkiiijjiijjixbaxain(1)()kkJJacoxxgiBb迭代的矩阵格式Jacobi迭代公式（分量形式）给出初始向量x(0),即可得到向量序列：x(1),x(2),…,x(k),…若x(k)→x*,则x*是解。例1：设方程组为3103220241225321321321xxxxxxxxx解：Jacobi迭代格式为试写出其Jacobi分量迭代格式以及相应的迭代矩阵，并求解。10310351)323(10152141)220(415125152)212(51)(2)(1)(2)(1)1(3)(3)(1)(3)(1)1(2)(3)(2)(3)(2)1(1kkkkkkkkkkkkkkkxxxxxxxxxxxxxx