Chapter8_1_线性方程组的迭代法

第八章解线性方程组的迭代法(IterativeMethods)思路Axb将改写为等价形式，建立迭代。从初值出发，得到序列。xBxg1kkxBxg0x{}kx研究内容：如何建立迭代格式？收敛速度？向量序列的收敛条件？误差估计？§1逐次逼近法(迭代格式的构造)把矩阵A分裂为0||,QCQA则bxCQbAx)(bQxCQI11)(gBxx写为迭代过程:gBxxkk1这种迭代过程称为逐次逼近法，B称为迭代矩阵给定初值x0,就得到向量序列,,,,10nxxx收敛性：若称逐次逼近法收敛，否则，称逐次逼近法不收敛或发散。*lim,nnxx定义1问题：x*是否是方程组Ax=b的解？任意给定初始向量x0，如果由逐次逼近法产生的向量序列收敛于向量x*，那么，x*是方程组x=Bx+g的解定理1gBxxgBxxkkkk**)(limlim1证明当k时，Bk0(B)1设线性方程组x=Bx+g有惟一解，那么逐次逼近法对任意初始向量x０收敛的充分必要条件是迭代矩阵B的谱半径(B)1**1**1*10()().kkkkkxBxgxBxgxxBxxBxx*11lim()0lim0()1.kkkkxxBB因此一、逐次逼近法收敛的条件定理2定理3证明若逐次逼近法的迭代矩阵满足‖B‖1，那么逐次逼近法收敛Remark:因为矩阵范数都可以直接用矩阵的元素计算，因此,用定理容易判别逐次逼近法的收敛性。1,BFB,B要检验一个矩阵的谱半径小于1比较困难，所以我们希望用别的办法判断收敛性定理4BB)(收敛速度：称R(B)=-lnρ(B)迭代的收敛速度。定义2（充分条件）若存在一个矩阵范数使得||B||1,则迭代收敛，且有下列误差估计：11||||||*||||||1||||kkkBxxxxB②①1110||||||*||||||1||||kkBxxxxB②111*(*)(*)kkkkkxxBxxBxxxx111||*||||||(||*||||||)kkkkxxBxxxx11||||||*||||||1||||kkkBxxxxB误差表达式及收敛速度停机准则二、误差估计（终止迭代）定理5证明①)()(0111xxBxxBxxkkkkk||||||||||||011xxBxxkkk||||||||1||||||*||11kkkxxBBxx||||||||1||||011xxBBknnnnnnnnnnbxaxaxabxaxaxabxaxaxa.....................221122222121112121110iia写成矩阵形式：A=-L-UD(())()AxbDLUxbDxLUxb11()xDLUxDbBfJacobi迭代阵§2Jacobi法/*JacobiIterativeMethods*/bDxULDxkk111)(nnaaaaD3322110000321323121nnnaaaaaaL0000322311312nnnaaaaaaU)(1ULDBJ000000003223113123213231211133122111nnnnnnnnaaaaaaaaaaaaaaaa0000321333333233312222223222111111131112nnnnnnnnnnnnaaaaaaaaaaaaaaaaaaaaaaaaJacobi迭代的矩阵形式bDxULDxkk111)(Jacobi迭代的分量形式niabxaaxiiinijjkjiiijki,,2,11)()1(niabxaaxaaxiiinijkjiiijijkjiiijki,,2,1)(1)(11)()1(例1试用Jacbi迭代法解线性方程组1015352111021210321xxx解因为迭代矩阵为0525110101021011020JB原方程改写为25.13.004.02.01.002.01.02.00321321xxxxxx其迭代格式为,..1,021.02.05.11.02.03.01.02.0)(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kxxxxxxxxxkkkkkkkkk取T)0()0,0,0(xT)11()0000.3,0000.2,0000.1(x有Algorithm:JacobiIterativeMethodSolvegivenaninitialapproximation.Input:thenumberofequationsandunknownsn;thematrixentriesa[][];theentriesb[];theinitialapproximationX0[];toleranceTOL;maximumnumberofiterationsMmax.Output:approximatesolutionX[]oramessageoffailure.Step1Setk=1;Step2While(kMmax)dosteps3-6Step3Fori=1,…,nSet;/*computexk*/Step4IfthenOutput(X[]);STOP;/*successful*/Step5Fori=1,…,nSetX0[]=X[];/*updateX0*/Step6Setk++;Step7Output(Maximumnumberofiterationsexceeded);STOP./*unsuccessful*/Axb0XiinjijjijiiaXabX1)0(TOLXXXXiini|0|max||0||1Whatifaii=0?迭代过程中，A的元素不改变，故可以事先调整好A使得aii0，否则A不可逆。必须等X(k)完全计算好了才能计算X(k+1)，因此需要两组向量存储。Abitwasteful,isn’tit?111()()kkxDLUxDLbBG-SgGauss-Seidel迭代阵作A的另一个分裂：其迭代格式的矩阵形式为()ADLU(())()AxbDLUxbDLxUxb11()()xDLUxDLb1kGSkGSxBxg§3Gauss-Seidel迭代法(1)()()kkDLxUxb(1)1(1)()1()kkkxDLxUxDb写成分量形式：下面从另一个角度来说明niabxaaxaaxiiinijkjiiijijkjiiijki,,2,1)(1)(11)1()1(具体如下:)(11)(1)(414)(313)(21211)1(1bxaxaxaxaaxknnkkkk)(12)(2)(424)(323)1(12122)1(2bxaxaxaxaaxknnkkkk)(13)(3)(434)1(232)1(13133)1(3bxaxaxaxaaxknnkkkk)(1)1(11)1(33)1(22)1(11)1(nknnnknknknnnknbxaxaxaxaax…………只存一组向量即可。注：这二种方法都存在收敛性问题。在讨论收敛性之前我们先来讲一些预备知识和有关的定理例2试用G-S迭代法解例1中线性方程组1015352111021210321xxx解其迭代格式为取T)0()0,0,0(x24.02.05.11.02.03.01.02.0)1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx有T)6()0000.3,0000.2,0000.1(x显然G-S迭代收敛快.§4有关基本概念一、严格对角占优矩阵与对角占优矩阵设A是n阶矩阵.若满足不等式且至少有一个i，使严格不等号成立，则称A为对角占优矩阵.若对所有的i=1,2,…,n，都有严格不等号成立，称A为严格对角占优矩阵定义2niaaiinijjij,,2,1||||1二、可约矩阵与不可约矩阵其中A11和A22分别是k阶和n-k阶方阵(n≥2,kn),那么,称A是可约矩阵.如果不存在这样的排列阵P，使上式成立，称A是不可约矩阵设A是n阶矩阵.A是不可约的充分必要条件是对有限整数集W={1,2,…,n}中任意两个非空子集R,SW，R∪S=W,R∩S=，存在i∈R,j∈S，使aij≠0.定义3设A是n阶矩阵.如果存在排列阵P,使定理62212110AAAAPPT三、有关性质设A是n阶(按行)严格对角占优矩阵,那么A是非奇异的设A是严格对角占优矩阵，那么，其各阶主子阵也是严格对角占优矩阵.设A是严格对角占优矩阵.记经过一步Gauss消去后的矩阵为那么，A(2)n-1仍是严格对角占优的.定理7定理8定理900)2(111211nnAaaa设A是不可约对角占优矩阵，那么A是非奇异矩阵.n阶矩阵A是按行严格对角占优矩阵的充分必要条件是Jacobi迭代法的迭代矩阵满足‖BJ‖∞1.n阶矩阵A是按列严格对角占优矩阵的充分必要条件是Jacobi迭代法的迭代矩阵满‖BJ‖11.定理10定理11定理12§5Jacobi迭代法和Gauss-Seidel迭代法的收敛性设线性方程组x=Bx+g有惟一解，那么逐次逼近法对任意初始向量x０收敛的充分必要条件是迭代矩阵B的谱半径(B)1设A是有正对角元的n阶对称矩阵,那么Jacobi迭代法收敛的充分必要条件是A和2D-A同为正定矩阵.如果A是有正对角元的对称矩阵，aii0记D=diag(a11,a22,…,ann).定理13定理14证明对于BJ=I-D-1A,有(1)若Jacobi迭代法收敛，则(BJ)1，即即D－1/2AD-1/2是正定矩阵,从而A也是正定矩阵.现考虑矩阵2D－AADIDADDID121212121)(2121ADDIBJ1)(2121ADDI111i20i21212121)2(2DADDIDAD即2D－A与的特征值的符号相同21212ADDI因此2D-A的特征值为正，从而2D-A为正定矩阵充分性：A为正定矩阵I－D－1A的特征值全小于12D-A为正定矩阵I－D－1A的特征值全大于－1(I－D－1A)1(BJ)1的特征值为2－i21212ADDI如果A是按行(列)严格对角占优的矩阵,那么Jacobi和G－S迭代法都收敛设A是不可约对角占优矩阵，那么Jacobi迭代法与G－S迭代法都收敛.设A是n阶正定矩阵,那么,G－S迭代法收敛.定理15定理16定理17A按行严格对角占优,则G-S迭代收敛。定理18证明设λ是BG-S任