数值分析(研究生)第五章线性方程组的迭代解法一

第五章线性方程组的迭代解法第二节基本迭代方法第三节迭代法的收敛性第四节超松弛迭代法第一节实际问题的导入第五节分块迭代法上页下页返回求解bxA思路.lim}.{.)()()0()()1(的解为则，若出发，得到序列从初值形式，建立迭代等价改写为将bxAxxxxxfxBxfxBxbxAkkkkk计算精度可控，特别适用于求解系数为大型稀疏矩阵的方程组.§1实际问题的导入上页下页返回定义1（1）对给定的方程组研究内容：如何建立迭代格式？收敛速度？向量序列的收敛条件？误差估计？bxA.)2,1,0()()1(法称为迭代法逐步代入求近似解的方用式kfxBxkk.,.)(lim)2()(称此迭代法发散否则的解就是方程组此时，则称此迭代法收敛，记为存在如果xxxkk上页下页返回§2基本迭代方法一、雅可比迭代法nnnnnnnnnnbxaxaxabxaxaxabxaxaxa.....................22112222212111212111nnnnnnnnnnnnbxaxaaxbxaxaaxbxaxaax11112212122211212111...1...............1...10iia写成矩阵形式：A=LUDbxULxDbxULDbxA)()(bDxULDx11)(Bf雅可比迭代阵bDxULDxkk1)(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…………只存一组向量即可.写成矩阵形式：bDxUxLDxkkk1)()1(1)1()(bxUxLDkk)()1()(bLDxULDxkk1)(1)1()()(Bf高斯-塞德尔迭代阵上页下页返回注：二种方法都存在收敛性问题.有例子表明：高斯-塞德尔迭代法收敛时，雅可比迭代法可能不收敛；而雅可比迭代法收敛时，高斯-塞德尔迭代法也可能不收敛.上页下页返回§3迭代法的收敛性的收敛条件fxBxkk)()1(*)1()1(xxekk)()()(*)()*()(kkkeBxxBfxBfxB)0()(eBekk||||||||...||||||||||||)0()1()(eBeBekkk充分条件:||B||1kBkas0||||0||||)(ke必要条件:kkBkeas0)(？定义设：.)(,)()(nnnnkijknnijRaAaAAAkklim是指ijkijkaa)(lim对所有1i,jn成立.等价于对任何算子范数有kAAkas0||||上页下页返回0||||xBk对任意非零向量成立x定理设fxBx存在唯一解，则从任意出发，)0(x迭代fxBxkk)()1(收敛0.kB证明：Bk0||Bk||00||||||||max0xxBkx“”：对任意非零向量有x0||||||||||||kkBxxB“”：取则Tix)0...1...0()(第i位0)(kijb0xBk对任意非零向量成立x从任意出发，记，则)0(x*)0()0(xxe0)0()(eBekkask}{)(kx收敛.上页下页返回定理Bk0B1证明：“”若是B的特征值,则k是Bk的特征值。则[B]k=[max||]k=|mk|Bk||Bk||0B1“”首先需要一个引理对任意0,存在算子范数||·||使得||A||A。由B1可知存在算子范数||·||使得||B||1。||Bk||||B||k0askBk0迭代从任意向量出发收敛Bk0B1证明：对A做Jordan分解，有，其中，，i为A的特征值.令，则有易证：是由导出的算子范数.所以只要取，就有||A||A.rJJAPP...11ininiiiJ101riinn1121nDrrAPDPD1111)()||(max||||||||1111AAPDPDAiri11||)(||||||xPDxv上页下页返回定理（充分条件）若存在一个矩阵范数使得||B||=q1,则迭代收敛，且有下列误差估计：①||||1||*||)1()()(kkkxxqqxx②||||1||*||)0()1()(xxqqxxkk证明：①)*()*(*)1()()()1()(kkkkkxxxxBxxBxx||)||||*(||||*||)1()()()(kkkkxxxxqxx②)(...)()0()1(1)2()1()1()(xxBxxBxxkkkkk||||||||)0()1(1)1()(xxqxxkkk上页下页返回定理（充分条件）若A为严格对角占优阵则解的雅可比迭代和高斯-塞德尔迭代均收敛.bxA证明：首先需要一个引理若A为严格对角占优阵，则det(A)0，且所有的aii0.证明：若不然，即det(A)=0，则A是奇异阵。存在非零向量使得Tnxxxx),,(210.00xA记||max||1inimxxniiimxa10miimmmiiimmmmaxxaxa||||||显然我们需要对雅可比迭代和高斯-塞德尔迭代分别证明：任何一个||1都不可能是对应迭代阵的特征根，即|IB|0.雅可比:BJ=D1(L+U)|)(|||1ULDIBI|||||)(|11ULDDULDDaii0ijaijannaa11如果||1则ijijiiiiaaa||||||是严格对角占优阵|IB|0关于高斯-塞德尔迭代的证明与此类似.另一种证明引理的方法利用GeršgorinDiscTheorem.上页下页返回.,3322231323迭代收敛的条件并指出迭代格式，和试构造对方程组例JacobiSGJacobizayaxazyaxazayx.3131122212*3aJacobizayaxazyaxazayx充要条件是（雅可比）迭代收敛的证明：解方程组例上页下页返回快？取何值时，迭代收敛最取何值时，迭代收敛？问：考察迭代若例.2.1],[.21,4211**3)()()1(bxAxxbAkkk.,1284194313617324由格式，并说明收敛的理迭代和试构造收敛的对方程组例SGJacobiwzyxwzyxwzyxwzyx上页下页返回§4超松弛迭代法换个角度看高斯-塞德尔方法：nijkjijijkiijiiikixaxabax1)(11)1()1(][1iikikiarx)1()(其中ri(k+1)=ijijkjijkjijixaxab)()1(相当于在的基础上加个余项生成.)(kix)1(kix下面令，希望通过选取合适的来加速收敛，这就是松弛法.iikikikiarxx)1()()1(01低松弛法=1高斯-塞德尔迭代法1(渐次)超松弛法上页下页返回写成矩阵形式：iikikikiarxx)1()()1(ijikjijijkjijiikibxaxaax][)1()()1()(][)1()()1(1)()1(bxUxLDxxkkkkbLDxUDLDxkk1)(1)1()(])1[()(Hf松弛迭代阵定理设A可逆，且aii0，松弛法从任意出发对某个收敛H1.)0(x上页下页返回定理（Kahan必要条件）设A可逆，且aii0，松弛法从任意出发收敛02.)0(x证明：从出发])1[()(1UDLDHniiH1)det(利用，而且收敛|i|1总成立可知收敛|det(H)|1niiiaLDLD111)det(1))det((niiinaUD1)1())1det((nH)1()det(|det(H)||1|n102上页下页返回定理（Ostrowski-Reich充分条件）若A对称正定，且有02，则松弛法从任意出发收敛.)0(xQ:Whatfactordeterminesthespeedofconvergence?考察迭代fxBxkk)()1(：设B有特征根1、…、n对应n个线性无关的特征向量.则从任意出发，可表为的线性组合，即n,...,1)0(x*)0()0(xxen,...,1niiie1)0(niikiikkeBe1)0()(~)0()]([eBkA:ThesmallerBis,thefastertheiterationswillconverge.对于SOR法，希望找使得H最小.迭代收敛的速度v=-ln[H].定义上页下页返回定理若A为对称正定三对角阵，则且SOR的最佳松弛因子为，此时.1)]([)(2JSGBB2)]([112JB1)(H例521,2112bA，考虑迭代格式)()()()1(bxAxxkkk问：取何值可使迭代收敛？取何值时迭代收敛最快？解：考察B=I+A的特征根1=1+,2=1+3收敛要求B12/30B=max{|1+|,|1+3|}当取何值时最小？2/31/30=1/2上页下页返回点迭代法分块迭代法§5分块迭代法