解线性代数方程组的迭代法学习培训模板课件.ppt

1、2022-11-141第四章 解线性代数方程组的迭代法 4.1向量和矩阵序列的极限 4.3 几种常用的迭代法4.2 迭代法的基本理论2022-11-1424.向量和矩阵序列的极限一.极限的概念0lim*)(xxkkRemark：上面的收敛性实际上和范数的选择无关。（范数的等价性）1.向量序列收敛 则称 收敛于 。记为：)(kx*x*)(limxxkk设 是 中的向量序列，若有 )(kxnR向量 ，使nRx*定义：2022-11-143 设 是 中的矩阵序列，若有 ，使 ，则称 收敛于，记为 )(kAnnRnnRA0lim)(AAkk)(kAAAAkk)(lim.矩阵序列收敛Remark：上面的

2、收敛性也和范数的选择无关。定义：2022-11-144二.序列收敛的等价条件 设 ，则 的充要条件是：Tknkkkxxxx),()()(2)(1)(Tnxxxx),(*2*1*)(limxxkk*limikikxx）（）（ni,2,11.向量序列收敛的等价定理2022-11-1450maxlim*)(1ikinikxx0lim*)(xxkk*klimikixx）（）（ni,2,1证明：充分性 由范数的等价性，*)(limxxkk即*)(1xxck*)(2xxck*)(xxk序列收敛的等价条件（续）2022-11-146*)(limxxkk0lim*)(xxkk必要性由等价性知：0lim*)(x

3、xkk有*limikikxx）（即0maxlim*)(1ikinikxx即*)(1xxck*)(xxk*)(2xxck序列收敛的等价条件（续）证毕2022-11-1472.矩阵序列收敛的等价定理0)(maxlim1)(1njijkijnikaa即0limAAkk）（故 0limAAkk）（由矩阵范数的等价性，有AAkk )(lim即证明：充分性ijkijkaa)(lim，则 ，0maxlim)(,1ijkijnjikaa 设 ，则 的充要条件 是nnkijkaA)()()(nnijaA)(AAkk）（limijkijkaa)(lim序列收敛的等价条件（续）2022-11-1480)(maxli

4、m1)(1njijkijnikaa即0maxlim)(,1ijkijnjikaa也即ijkijkaa)(lim故 .向量序列、矩阵序列的收敛性等价于按分量、按元 素的收敛性。.对向量序列和矩阵序列，按范数或者按分量元素收敛，都可以转化为数列的收敛。必要性：由矩阵范数的等价性，有0limAAkk）（0limAAkk）（AAkk）（lim即 ,序列收敛的等价条件（续）Remark证毕2022-11-149序列收敛的等价条件（续）定理定理 的充要条件是 limkkA 0 lim0,knkAxxR 证明证明 必要性是显然的,现证充分性。取 为第i个单位坐标向量 ,则 ，这意味 的第i列元素的极限为零,

5、取 ,则充分性得证.x lim0kikA e0,0,1,0,0Tie kAn,i212022-11-1410三.引理rJJJJ21iinniiiiJ11，)2,1(riJi 证明：任何矩阵B总相似于它的Jordan标准型，即存 在可逆阵P，使 其中 JBPP1设 ，则 的充要条件是 ，nnRB1)(B0limkkB其中 叫做矩阵B 的谱半径。）（BBini1max)(称为Jordan块。为B的特征值 的重数，.innnrii1i2022-11-1411kikikkinkinkkikkinkinkkikkikkikiCCCCCCJiiii112211112211由归纳法可证0lim0limkik

6、kkJB），（ri,21显然121PJJJPBkrkkk1111)()(PPJPJPPJPPJPBkk 由 ，则1 PJPB续2022-11-14121)(1Bi 即1)(0lim)(BJkik从而 其中 ，时 ，不难看出 的充要条件为 0limkikJ)1()1(!1mkkkmCmk0mkC)1,in,2,1(mkm 1)(0limBBkk故），（ri,21 0limkik续证毕2022-11-14134.迭代法的基本理论迭代法的一般格式为),()()1()()1(mkkkkkxxxfx ,1,mmk若 ，即 ，称为单步迭代法。)()()1(kkkxfx0m,1,0kkkkkgxBx)()1

7、(,1,0kkB若 为线性的，即，称为单步线性迭代法，称为迭代矩阵。kfkgkBgxBxkk)()1(若，与k无关，即 ,k=0,1,，称为单步定常线性迭代法，或者叫简单迭代法。本章主要讨论简单迭代。因为计算 一般要用到前面多步的值 故称为多步迭代法。)1(kx)()1()(,mkkkxxx2022-11-1414一.简单迭代法的构造 将该方程组等价变形为 构造简单迭代格 式 ，。若 收敛于确定的向量 ，则 就是方程组的解。此时称简单迭代法 ，关于初始向量 收敛。gxBx)(kx,1,0kgxBxkk)()1(*x*xgxBxkk)()1(,1,0k)0(x设要求解的线性方程组为 ，其中 为非

8、奇异矩阵，为向量。bxAbA2022-11-1415 变形为 的方式不唯一。gxBxbxA 当收敛时，只要 充分大，则可用 作为 的k）（1kx*x近似值。同一个简单迭代法可以关于某一个 收敛，而关)0(x于另外 不收敛。)0(x 如果对初始向量 ，则称此简单迭)0(x*)(limxxkk对任意 ，均有 .)0(x*)(limxxkk代法关于初始向量 收敛。一般谈及收敛，是指)0(x简单迭代法的构造（续）2022-11-1416二.简单迭代法的收敛性和收敛速度0lim kkBa.1)(Bb.迭代矩阵的谱半径1.收敛的充要条件 定理1.简单迭代法 ，对 任意初始向量 都收敛的充要条件是：)0(x

9、gxBxkk)()1(,1,0k简单迭代法为 .,2,1,)1()(kgxBxkk)()(*)0(*)1(*)(xxBxxBxxkkk故设 有唯一解 ，*xgxBx2022-11-14170010qe作为 ，*)0(xx证明：必要性：用 表示 的（i,j）元素，简单迭代对 任意初始向量 有 .设 不趋 于零，则必有位置（p,q）使 不趋于零。取第qkijbkB)0(x0)(lim*)0(xxBkkkBkpqb个单位向量 a.充分性：，则由0limkkB）（）（）（*0*xxBxxkk)0(x*)(limxxkk知对于任意初始向量 ，。收敛的充要条件（续）2022-11-1418000100)(

10、*)0(kpqkpqkbbxxB 即向量 的第q个元素不趋于零，从而 与 矛盾。)(lim*)0(0 xxBkk0)(lim*)0(xxBkk则有：收敛的充要条件（续）b.由上节引理可以直接证明。证毕2022-11-1419 是判定收敛的根本法则。1)(B 时，有可能存在某个初始向量 使简 单迭代法收敛。1)(B)0(y收敛的充要条件（续）Remark2022-11-1420 2.收敛的充分条件 引理：由矩阵范数的定义，有pTppTyxByx),2,1(,)(FpBBp或即),2,1(,)(FpBBp或对任意矩阵 ，有nnRB特征向量，则 。xxB证明：事实上，设为B的任一特征值，为相应于 的

11、0 x从而有pB显然有向量nRy，使得 为非零矩阵。Tyx用 右乘上式，可得TyTTyxyxB证毕2022-11-1421)1()(*)(1kkkxxBBxxb.)0()1(*)(1xxBBxxkk c.a.简单迭代格式关于任意初始向量 收敛.)0(x 定理2.设方程组 有唯一解 ，其简单迭gxBx*x数要求与用到的向量范数相容），则代法为 ，若 （用到的矩阵范gxBxkk)()1(1B收敛的充分条件（续）2022-11-1422 b.由 ，相减，得：gxBxkk)()1(gxBx*)()(*)1(*kkxxBxx)()1()()()1(kkkkxxBxx 故 )1()()1()()()1(k

12、kkkkkxxBxxBxx 故 )(*)(*)1(*(kkkxxBxxBxx又由 ，相减得：gxBxkk)()1(gxBxkk)1()(证明：敛基本定理，简单迭代格式对任意 收敛。)0(xa.由 且 ，故 ，由迭代收BB)(1)(B1B收敛的充分条件（续）2022-11-1423从而)()1(*)(*)()1(kkkkxxxxxx由)(*)(*)(*)1(kkkxxBxxBxx1B从而有)()1(*)(11kkkxxBxx由)1()(1kkxxBB即*)(xxk)1()(1kkxxBB)1(*)(*kkxxxx收敛的充分条件（续）2022-11-1424 .*)(xxk)1()(1kkxxBB

13、)2()1(21kkxxBB)0()1(1xxBBkc.由 及b即*)(xxk)0()1(1xxBBk收敛的充分条件（续）证毕2022-11-1425 3.收敛速度 由定理2可见，若 且 越小，则 收敛到解的速度越快。实际上，可以确切地说，谱半径 相对于1来说越小，则 的收敛速度越快。1BB)(kx)(B)(kxgxBx*由 和 还可得到gxBxkk)1()(*)(*)(*)(*)0()2(2)1()(xxBxxBxxBxxkkkk*)0()(xxBxxkk若要求迭代k次后所产生的误差缩小为初始误差的10m倍，即*10*)0()(xxxxmk则只需mkB102022-11-1426收敛速度（续

14、）可以证明，则存在从属于矩阵范数 ，使 。因而上面的条件可以近似代替为0)(BBmkB10)(故)(ln10lnBmk为了达到所提出的精度，上式给出了大约所需要的迭代次数。当误差压缩量10m确定后，这个次数主要由分母)(lnB所刻划的。越大，则迭代次数越少，收敛越快。一般将定义为简单迭代法的收敛速度。2022-11-1427三.高斯塞德尔（Gauss-Seidel）迭代将B分解为 bbbbbbbbbBBBnnnnnn22211211212121000设有简单迭代法 ,k=0,1,gxBxkk)()1(gxBxBxkkk)(2)(1)1(则将其修改为 k=0,1,gxBxBxkkk)(2)1(1

15、)1(i=1,2,ninijkjijijkjijkigxbxbx)(11)1()1(上式称为由简单迭代法导出的Gauss-Seidel迭代法。它的分量形式为2022-11-1428gBIxBBIxkk11)(211)1()()(Gauss-Seidel迭代收敛的充要条件为1)(211BBI1.迭代收敛的充要条件与简单迭代法相应的Gauss-Seidel迭代可化为2.迭代收敛的充分条件若 或 ，则Gauss-Seidel迭代 关于任意的初始向量 收敛。1B11B21BBB)0(x 若 ，则对于任意初始向量 ,Gauss-Seidel迭代收敛。1)(211BBI)0(x2022-11-1429的分

16、量形式inijkjijijkjijkigxbxbx)(11)1()1(injjijigxbx1*相减有)()(*)(11*)1(*)1(jnijkjijijjkjijikixxbxxbxxnijjkjijijjkjijikixxbxxbxx*)(11*)1(*)1(记 *)(1maxikinikxx11ijijibnijijib证明：由gxBxgxBxBxkkk*)(2)1(1)1(k=0,1,迭代收敛的充分条件（续）111maxnjijnibB仅以 为例。2022-11-1430有 上式对i=1,2,n都成立，ikikikixx1*)1(1*)1(00kikixx故有 使 0ii 0011i

17、kikk有001()1ikki即注意：njijiiBb1001 即0100ii迭代收敛的充分条件（续）所以 。00011ii 记 1max1kkkiinic 2022-11-1431故当k 时，则0max*)1(11ikinikxx故由序列收敛的等价性定理，知*)(limxxkk*)(limikikxx即对任意的 都成立。)0(x迭代收敛的充分条件（续）Remark：当 或 时，简单迭代法与相应的Gauss-Seidel迭代法同时关于任意初始向量收敛。1B11B证毕其中(0)*01max0iii nxx 显然，c 1，从而有110kkkcc2022-11-14324.3 几种常用的迭代法 一.

18、Jacobi迭代法1.迭代格式设有n 阶方程组nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111 其中系数矩阵非奇异，且 ，i=1,2，n0iia将上式变形为)(1)(1)(111,22112232312122211313212111nnnnnnnnnnnnnbxaxaxaaxbxaxaxaaxbxaxaxaax2022-11-1433Jacobi迭代法的迭代格式（续）建立迭代格式)(1)(1)(1)(11,)(22)(11)1(2)(2)(323)(12122)1(21)(1)(313)(21211)1(1nknnnknknnnknknnk

19、kkknnkkkbxaxaxaaxbxaxaxaaxbxaxaxaax上面的迭代式称为雅可比（Jacobi）迭代格式。用矩阵形式来表示方程组的迭代法 设det(A)，且00iia000000000000000000000000000000022311312213231212211212222111211nnnnnnnnnnnnaaaaaaaaaaaaaaaaaaaaaa2022-11-1434Jacobi迭代法的迭代格式（续）bDxULDx11)(雅可比迭代式成为：bDxULDxkk1)(1)1()(则)(1ULDBJbDg11令1)()1(gxBxkJk则得bxULD)(bxAxULbxD)

20、(记A=D+L+U 2022-11-1435 a.充要条件：Jacobi方法关于任意初始向量 都收敛 的充要条件是 。)0(x1)(JB 2.收敛条件 b.充分条件：（II）设系数矩阵 严格对角占优，nnijaA)(则Jacobi迭代法关于任意初始向量 收敛。)0(x（I）若 则Jacobi方法关于任意初始向量 都 收敛。1JB)0(x即（按行）,（i=1,2,n）njijijiiaa,12022-11-1436由严格对角占优矩阵的定义有（按行）i=1,2,n11,1,11nijjnijjijiiiiijnjijaaaab即 1JB证明：因此Jacobi迭代法对任意初始向量收敛。)0(x定义：

21、设 ，若 nijjijiiaa,1（i=1,2,n）nnijRaA)(且其中至少有一个严格不等式成立，则称A为按行弱对角占优。Jacobi迭代法的收敛条件（续）证毕2022-11-1437则称A为可约矩阵。以n阶单位矩阵In的n个列向量 为列构成n阶矩阵 称为置换矩阵.是1，2，,n的一个排列。neee,21njjj,21),(21jnjjeeep2212110AAAPAPT若可找到置换矩阵P，使A呈2212110AAA换化为 ，其中 是方阵，则称A为不可约矩阵。2211,AA定义：设 ，若A不能经过行置换与相应的列置nnRA（III）设A为弱对角占优矩阵且不可约矩阵，则Jacobi迭代法关于

22、任意初始向量 收敛。)0(xJacobi迭代法的收敛条件（续）2022-11-1438二.与Jacobi迭代法相应的Gauss-Seidel法1.迭代格式其迭代式为)(1)(1)(1)1(11.)1(22)1(11)1(2)(2)(323)1(12122)1(21)(1)(313)(21211)1(1nknnnknknnnknknnkkkknnkkkbxaxaxaaxbxaxaxaaxbxaxaxaax)()1()(kkxUbxLD)()1()1(kkkxUxLbxDxUbxLD)(矩阵形式为bxULD)(bxA2022-11-1439因 ,故 存在，于是Gauss-Seidel 迭代式为0i

23、ia1)(LDbLDxULDxkk1)(1)1()()(sG称为Gauss-Seidel迭代法的迭代矩阵。2)()1(gxGxksk则得ULDGS1)(2gbLD1)(令迭代格式（续）Remark1:今后若无特殊说明，凡谈到Gauss-Seidel迭代法（简称G-S迭代法），均指与Jacobi迭代法相应的Gauss-Seidel迭代法。Remark2:并不是任何时候Gauss-Seidel迭代法都比Jacobi迭代法收敛快。甚至也有Jacobi法收敛而Gauss-Seidel迭代法不收敛的例子。2022-11-1440 2.收敛条件a.充要条件：收敛的充要条件是：()1sG)0(xG-S法关于

24、任意初始向量 都 b.充分条件：关于任意初始向量 收敛。设系数矩阵 严格对角占优，则G-S方法)(ijaA)0(x设A为不可约弱对角占优矩阵，则G-S迭代法关 于任意初始向量 收敛。)0(x设A为对称正定矩阵，则G-S迭代法关于任意初 始向量 收敛。)0(x)0(x若 ，则G-S方法关于任意初始向量 都收敛。1sG2022-11-1441 三.逐次超松弛迭代法（SOR法-Successive Over Relaxation）1.迭代公式 将G-S迭代格式11)1(1ijijiiikiabax）nijkjijkjxax1)()1(ni,.,2,1改写为：nijkjijkjijijiiikikix

25、axabaxx)(1)()1(11)()1(并记 nijkjijkjijijikixaxabr)()1(11)1(一般地，残量 。0)1(kirni,.,2,1ni,.2,12022-11-144211)()1(ijijiiikikiabaxx）nijkjijkjxax)()1(ni,.2,1)()1()1(kikixx11ijijiiiaba（）nijkjijkjxax1)()1(矩阵形式:将迭代格式改写)()1(1)(11)1()()1(nijkjijijkjijikiiikiiixaxabxaxa由矩阵分解成ADLU这就是逐次超松驰迭代法（SOR方法)，称为松驰因子。SOR方法的计算公式

26、也常写为：逐次超松弛迭代法的迭代格式（续）Remark：可见，SOR方法的得到的 可以看成是G-S方法的结果与 的加权平均。)1(kix)(kix2022-11-1443则相应的矩阵形式为 bxUDxLDkk)()1()1()()()1()()1()()1(kkkkxUxLbxDxD故 bLDxUDLDxkk1)(1)1()()1()(gxLxkk)()1(故SOR方法的矩阵形式为其中)1()(1UDLDLbLDg1)(L称为SOR方法的迭代矩阵。即逐次超松弛迭代法的迭代格式（续）2022-11-14442.SOR方法的收敛性SOR方法收敛 设 的特征值为 Ln,.,21即1)(Ln.21)d

27、et(L由 的特征多项式的模与系数的关系知：Ln21)det(L()nL证：A.充要条件：SOR法关于任意初始向量 都收敛的充要条件是 。1)(L)0(x B.必要条件：设解 的SOR方法关于任意初始向量 都收敛，则0 2。)0(det,AbxA)0(x2022-11-1445)1det()det(1UDLD)1det(det1DDnnnnnaaaaa.)1().(1112211n)1(即 1)()det(1LLn而)1det()det(1UDLD)det(L即11)det(1nL故02。SOR方法的收敛性（续）证毕2022-11-1446yyL12(,.,)0Tnyy yy即 yyUDLD)

28、1()(1yLDyUD)()1(在复空间 中考虑内积nC)(是复数),)(,)1(yyLDyyUD）即),(),(),(),(),(yyLyyDyyUyyDyyD设 为对应 的 的特征向量，即yLSOR方法的收敛性（续）C.充分条件：若A 对称正定，且0 2，则SOR法关于任意初始向量 收敛（此时，0 2对称正定为充要条件）。)0(x证：2022-11-1447又记iyyL),(),(yyU),(yLy)()(ii)()(iiii)()(yUyTyLyTTyyLT)(),(yyLi所以),(0yyA),)(yyULD2因为 niiiiyayyD120),(SOR方法的收敛性（续）2022-11

29、-14482222222)()(当0 2时，则有22)()()(240)2)(2(即 ，故SOR方法收敛。1SOR方法的收敛性（续）证毕2022-11-1449SOR方法的收敛性（续）Remark：能使SOR方法收敛最快的松弛因子叫做最佳松弛因子，记为opt。对某些特殊类型的矩阵，可以建立SOR方法最佳松弛因子理论。例如，对于具有对称正定，或严格对角占优或弱对角占优且不可约等性质的矩阵A的线性方程组，可以建立最佳松弛因子其中(J)为解Axb的雅可比迭代法的迭代矩阵的谱半径。一般情况下确定opt并不容易，实际计算时一般都是根据试算的情况确定opt的一个近似值。2)(112Jopt2022-11-1450四.数值算例取 ，用迭代方法求解如下的方程组，使得 。Tx)1,1,1(05)()1(10kkxx244304324343232121xxxxxxx2022-11-14514.如果 ,则用此判断法比用 方便。1 qB1)(BRemark：使用迭代法求解线代数方程组需注意的问题 3.在迭代格式 中，若 是病态阵，fxBxkk)()1(BI 那么一般迭代法得不到好的结果。1.迭代法的收敛性与初始向量的选取无关。但初始向量的选取对迭代的工作量有重大影响。2.在使用实用误差估计式 停止迭代时，)()1(kkxx 要选的恰当。5.对某些方程组，有时可适当作些变形，以使得迭代法收敛。