解线性方程组的迭代法

1第6章解线性方程组的迭代法§6.1迭代法的基本概念§6.2雅可比迭代法与高斯-赛德尔迭代法21引言我们知道，凡是迭代法都有一个收敛问题，有时某种方法对一类方程组迭代收敛，而对另一类方程组进行迭代时就会发散。一个收敛的迭代法不仅具有程序设计简单，适于自动计算，而且较直接法更少的计算量就可获得满意的解。因此，迭代法亦是求解线性方程组，尤其是求解具有大型稀疏矩阵的线性方程组的重要方法之一。6.1迭代法的基本概念32迭代法的基本思想迭代法的基本思想是将线性方程组转化为便于迭代的等价方程组，对任选一组初始值，按某种计算规则，不断地对所得到的值进行修正，最终获得满足精度要求的方程组的近似解。),,2,1()0(nixi迭代法的基本思想设非奇异，，则线性方程组有惟一解，经过变换构造出一个等价同解方程组nnRAnRbbAxbAx1dGxx4将上式改写成迭代式选定初始向量,反复不断地使用迭代式逐步逼近方程组的精确解,直到满足精度要求为止。这种方法称为迭代法如果存在极限则称迭代法是收敛的，否则就是发散的。Tnxxxx)0()0(2)0(1)0(,,,迭代法的基本思想Tknkkkxxxx)()(2)(1)(,,,Tnxxxx**2*1*,,,),1,0()()1(kdGxxkkTknkkkxxxx)()(2)(1)(,,,5收敛时，在迭代公式中当时，,则,故是方程组的解。对于给定的方程组可以构造各种迭代公式。并非全部收敛*xbAx迭代法的基本思想k*)(xxkdGxx**),1,0()()1(kdGxxkk6例1用迭代法求解线性方程组352322121xxxx解构造方程组的等价方程组3423212211xxxxxx据此建立迭代公式3423)(2)(1)1(2)(2)(1)1(1kkkkkkxxxxxx0)0(2)0(1xx取计算得例题7例题迭代解离精确解越来越远迭代不收敛1,121xx,3333,1515,99,33,33)5(2)5(1)4(2)4(1)3(2)3(1)2(2)2(1)1(2)1(1xxxxxxxxxx81雅可比（Jacobi）迭代法1.雅可比迭代法算法构造6.2雅可比迭代法与高斯-赛德尔迭代法例2用雅可比迭代法求解方程组3612363311420238321321321xxxxxxxxx9例题解：从方程组的三个方程中分离出和21,xx3x341213111114254183213312321xxxxxxxxx10例题341213111114254183)(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx建立迭代公式取初始向量进行迭代,可以逐步得出一个近似解的序列：TTxxxx)0,0,0(),,()0(3)0(2)0(1)0(),,()(3)(2)(1kkkxxx（k=1,2,…）11直到求得的近似解能达到预先要求的精度，则迭代过程终止，以最后得到的近似解作为线性方程组的解。当迭代到第10次有计算结果表明，此迭代过程收敛于方程组的精确解x*=(3,2,1)T。TTxxxx)9998813.0,999838.1,000032.3(),,()10(3)10(2)10(1)10(例题12nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111nibxainjjij,,2,11写成例题考察一般的方程组，将n元线性方程组13若,分离出变量0iia),,2,1(niixnixabaxjnijjijiiii,,2,1)(11例题据此建立迭代公式nixabaxnijjkjijiiiki,2,1)(11)()1(上式称为解方程组的Jacobi迭代公式。142.雅可比迭代法的矩阵表示设方程组的系数矩阵A非奇异，且主对角元素，则可将A分裂成bAx),,2,1(0niaii000000001223113122211121323121nnnnnnnnnnaaaaaaaaaaaaaaaA记作A=L+D+U雅可比（Jacobi）迭代法15则等价于bAxbxUDL)(即bxULDx)(因为，则),,2,1(0niaiibDxULDx11)(这样便得到一个迭代公式bDxULDxkk1)(1)1()(bDxDADk1)(1)(bDxADIk1)(1)(雅可比（Jacobi）迭代法16000)(21222222111111121nnnnnnnnaaaaaaaaaaaaADIB其中雅可比（Jacobi）迭代法称为雅可比迭代公式,B称为雅可比迭代矩阵则有fBxxkk)()1(（k=0,1,2…）令bDfADIB11)(17雅可比迭代矩阵表示法，主要是用来讨论其收敛性，实际计算中，要用雅可比迭代法公式的分量形式。即雅可比（Jacobi）迭代法01231261110114828301ADIB在例2中,由迭代公式写出雅可比迭代矩阵为18雅可比（Jacobi）迭代法)(1)(1)(1)(11)(22)(11)1(2)(2)(323)(12122)1(21)(1)(313)(21211)1(1nknnnknknnnknknnkkkknnkkkbxaxaxaaxbxaxaxaaxbxaxaxaax(k=0,1,2,…)193高斯-塞德尔（Gauss-Seidel）迭代法1.高斯-塞德尔迭代法的基本思想在Jacobi迭代法中，每次迭代只用到前一次的迭代值，若每次迭代充分利用当前最新的迭代值，即在求时用新分量代替旧分量,就得到高斯-赛德尔迭代法。其迭代法格式为：)1(kix)1(1)1(2)1(1,,,kikkxxx)(1)(2)(1,,,kikkxxx高斯-赛德尔迭代法)(1111)()1()1(ijnijkjijkjijiiikixaxabax(i=1,2,…,nk=0,1,2,…)20例3用GaussSeidel迭代格式解方程组35410218321321321xxxxxxxxx精确要求为ε=0.005解GaussSeidel迭代格式为5/)3(10/)42(8/)1()1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx例题21例题取初始迭代向量,迭代结果为：Tx)0,0,0()0(Tx)5000.0,3750.0,1250.0()1(Tx)4925.0,3031.0,2344.0()2(Tx)4939.0,3059.0,2245.0()3(Tx)4936.0,3056.0,2250.0()4(x*≈)3,2,1(,005.0)3()4(ixxii222.Gauss—Seidel迭代法的矩阵表示将A分裂成A=L+D+U，则等价于(L+D+U)x=b，于是,则高斯—塞德尔迭代过程bAxbUxLxDxkkk)()1()1(因为,所以0D0DLDbUxxLDkk)()1()(bLDUxLDxkk1)(1)1()()(bLDdULDG1111)(,)(1)(1)1(dxGxkk则高斯-塞德尔迭代形式为：故令高斯-赛德尔迭代法23我们知道,对于给定的方程组可以构造成简单迭代公式、雅可比迭代公式、高斯-塞德尔迭代公式，但并非一定收敛。现在分析它们的收敛性。对于方程组经过等价变换构造出的等价方程组bAx),1,0()()1(kdGxxkk在什么条件下迭代序列收敛？)(kx迭代法的收敛性24定理1迭代公式收敛的充分必要条件是迭代矩阵G的谱半径。),1,0()()1(kdGxxkk1)(G迭代法的收敛性25由此定理可知，不论是雅可比迭代法、高斯—塞德尔迭代法还是简单迭代法，它们收敛的充要条件是其迭代矩阵的谱半径。1)(G事实上,在例1中,迭代矩阵G=，其特征多项式为,特征值为-2，-3，,所以迭代发散421165)det(2GI13)(G迭代法的收敛性26定理2(迭代法收敛的充分条件)若迭代矩阵G的一种范数,则迭代公式收敛。1G),1,0()()1(kdGxxkk迭代法的收敛性27例5已知线性方程组6612363311420238321321321xxxxxxxxx考察用Jacobi迭代和G-S迭代求解时的收敛性解:⑴雅可比迭代矩阵01231261110114828300003332333122232221111311121aaaaaaaaaaaaADIB例题28⑵将系数矩阵分解01023003604012118ULDA则高斯-塞德尔迭代矩阵例题1129129,115,85maxB故Jacobi迭代收敛01023012361148)(111ULDG2918517641,227,85max1G故高斯—塞德尔迭代收敛。例题88717627011222308283001023012144117690111221008130定理3设n阶方阵为对角占优阵,则非奇异。（证明省略）nnijaA)(迭代法的收敛性系数矩阵为对角占优阵的线性方程组称作对角占优方程组。31定理4对角占优线性方程组的雅可比迭代公式和高斯-赛德尔迭代公式均收敛。bAx迭代法的收敛性32定理5若方程组的系数矩阵A是对称正定的，则G－S迭代法收敛。bAx迭代法的收敛性33例6设求解线性方程组的雅可比迭代bAx,1,0,)()1(kfBxxkk求证当1时,相应的高斯-塞德尔迭代收敛B例题34证:由于B是雅可比迭代的迭代矩阵,故有00021222222111111121nnnnnnnnaaaaaaaaaaaaADI例题35∴系数矩阵为对角占优阵,故G-S迭代收敛bAx例题11nijjiiijaa则niaaiinijjij,,2,1,1又1,故有B36例7设,证明,求解方程组02211aa22221211212111bxaxabxaxa的Jacobi迭代与G-S迭代同时收敛或发散例题37证:雅可比迭代矩阵00222111121aaaaADIB例题其谱半径22112112)(aaaaB38G-S迭代矩阵其谱半径2211212111121100)(aaaaaaULDG22112