123-6-4迭代法的收敛性与稳定性

插值法主讲教师：刘春凤线性方程组的迭代解法第六章一阶定常迭代法的基本定理关于解某些特殊方程组迭代法的收敛性迭代法的收敛性与稳定性一阶定常迭代法的基本定理常用结论设为阶方阵的特征值，的谱半径定义为：(1,2,,)iinn1()max{}iinAAA的谱定义为：12{...}.n，，kkAA)]([)(AA)(xxAxAxkkiiiiiiuuAuAu事实上：对的及特征向量AiiuAi1()maxiinAAi由的任意性：1()max.iinAA当对称时，A2().AA矩阵的谱半径由的任意性i迭代法的收敛性与稳定性一阶定常迭代法的基本定理.fBxxbAx设线性方程组,(3.1)Axb其中为非奇异矩阵，记为()nnijAaR*x(3.1)精确解，且设有等价的方程组于是(3.2)xBxf)3.3(.)()1(fBxxkk设有解的一阶定常迭代法Axb迭代法的收敛性与稳定性一阶定常迭代法的基本定理有意义的问题是：迭代矩阵满足什么条件时，由迭代法产生的向量序列收敛到.B(){}kx*x误差向量的递推公式).,2,1,0(,)0()()()1(kBBkkkk).,2,1,0()()(kxxkk引进误差向量由(3.3)式减(3.2)得到研究迭代法(3.3)收敛性问题就是要研究迭代矩阵满足什么条件时，有B).)((0kBk零矩阵迭代法的收敛性与稳定性一阶定常迭代法的基本定理定义设有矩阵序列及，如果()()knnkijAaR()nnkijAaR2n个数列极限存在且有()lim(,1,2,,)kijijkaaijn，则称收敛于{}kAAlim().k记为其中||·||为矩阵的任意一种,0limlimAAAAkkkk算子范数.limnkkAAxR都有lim.kkAxAx定理1定理2迭代法的收敛性与稳定性一阶定常迭代法的基本定理例3设有矩阵序列，其中而{}kAkkAB,0,,02,011222kkkkkBBB且设，考查矩阵序列极限.1显然,当时,则有1.0000limlimkkkkBA迭代法的收敛性与稳定性一阶定常迭代法的基本定理设，则（零矩阵）的充要条件：()ijnnAalim0kkA1.A必要性0lim0limkkkkAAkkkAAA)]([)(0lim[()]0kkA()1A充分性若，则对()1A1()12A必存在一种范数，使得.12)(1)(AAA0limkkAkkAA而limlim0kkkkAA＝，于是lim0kkA定理3即迭代法的收敛性与稳定性一阶定常迭代法的基本定理迭代法基本原理设有方程组及一阶定常迭代法xBxf(1)()kkxBxf)1.B（对任意选取初始向量，迭代法收敛的充要条件是(0)x定理40...)0()1()(kkkkBBxx）（xxkk)(lim0limkk0limkkB1)(B)()0()0(xx迭代法的收敛性与稳定性一阶定常迭代法的基本定理定理3和定理4的结论和起来即为(1)迭代法收敛(1)()kkxBxflim0kB(2)迭代法收敛(1)()kkxBxf()1.B推论设，其中为非奇异矩阵且为非奇异矩阵AxbADLUD则有(1)Jacobi迭代法收敛，其中()1J1().JDLU(2)G-S迭代法收敛，其中()1G1().GDLU(3)SOR迭代法收敛，其中()1L1()[(1)].LDLDU迭代法的收敛性与稳定性一阶定常迭代法的基本定理例4考察用Jacobi方法解方程组的收敛性.12312312383220,41133,631236.xxxxxxxxx因为方程组的矩阵及迭代矩阵为AJ.012/312/611/1011/48/28/30)(,123611142381ULDJA得迭代矩阵的特征方程为J,0039772727.0034090909.0)det(317638833JI解得,3445.01841.0,3445.01841.0,3082.0321ii迭代法的收敛性与稳定性一阶定常迭代法的基本定理例4考察用Jacobi方法解方程组的收敛性.12312312383220,41133,631236.xxxxxxxxx.13592.0,13082.0321解得,3445.01841.0,3445.01841.0,3082.0321ii即所以用Jacobi方法解方程组是收敛的.()1J迭代法的收敛性与稳定性一阶定常迭代法的基本定理例5考察用迭代法解方程组的收敛性.其中.55,0320,)()1(fBfBxxkk方程组的迭代矩阵B的特征方程为22det()63IB这说明用迭代法解此方程组不收敛.矩阵B的特征值为，即1,26()1.B迭代法的基本定理在理论上是重要的，根据谱半径的性质，下面利用矩阵的范数建立判别迭代法收敛的充分条件.()BBB迭代法的收敛性与稳定性一阶定常迭代法的基本定理(迭代法收敛的充分条件)定理5及一阶定常迭代法设有方程组,()nnijxBxfBbR(1)()kkxBxf如果有的某种算子范数，则B1Bq迭代法收敛，即对任取有(0)x.xBxf()limkkxx且.)2()0()(xxqxxkk.1)3()1()()(kkkxxqqxx.1)4()0()1()(xxqqxxkk(1)迭代法的收敛性与稳定性一阶定常迭代法的基本定理(1)由基本定理4结论(1)是显然的.(2)显然有关系式及反复利用(b)即得(2).*(1)*()()kkxxBxx(1)()()(1)()kkkkxxBxx于是有(1)()()(1)()kkkkaxxqxx*(1)*()()kkbxxqxx(3)考查(1)()*()*(1)()kkkkxxxxxx*()*(1)kkxxxx*()(1)kqxx即得.111)1()()()1()(kkkkkxxqqxxqxx迭代法的收敛性与稳定性一阶定常迭代法的基本定理(4)利用(3)的结果反复利用(a)，则得到(4).即.11)0()1()1()()(xxqqxxqqxxkkkk迭代法的收敛性与稳定性关于解某些特殊方程组迭代法的收敛性在科学及工程计算中，要求解方程组，其矩阵常常具有某些特性.例如，具有对角占优性质或为不可约阵，或是对称正定阵，下面讨论用基本迭代法解这些方程组的收敛性.AxbAAAA定义(1)如果A的元素满足).,,2,1(1niaanijjijii称A为严格(按行)对角占优阵.对角占优阵设()ijnnAa(2)如果A的元素满足).,,2,1(1niaanijjijii且上式至少有一个不等式成立，称A为弱(按行)对角占优阵.迭代法的收敛性与稳定性关于解某些特殊方程组迭代法的收敛性定义可约与不可约矩阵设(),2ijnnAan，如果存在置换阵P使1112220TAAPAPA其中为阶方阵，为阶方阵，则称为可约矩阵.否则，如果不存在这样置换阵使上式成立，则称为不可约矩阵.11Ar22Anr(1)rnAPA为可约矩阵意即可经过若干行列重排化为上式或可化为两个低阶方程组求解(如果经过两行交换的同时进行相应两列的交换，称对进行一次行列重排).AAAxbAA迭代法的收敛性与稳定性关于解某些特殊方程组迭代法的收敛性2121,ddbPdyyxPyTT事实上，由可化为Axb()TTTPAPPxPb，且记其中,,iiyd为维向量。r于是，求解化为求解Axb.,22221212111dyAdyAyA由上式第2个方程组求出,再代入第1个方程组求出.2y1y显然，如果所有元素都非零，则为不可约阵.AA(对角占优定理)如果A=(aij)n×n为严格对角占优矩阵或A为不可约弱对角占优矩阵，则A为非奇异矩阵.迭代法的收敛性与稳定性关于解某些特殊方程组迭代法的收敛性定理6111||,nnnkkkkjjkjjkkjjjjjkjkjkaxaxaxxa只就A为严格对角占优矩阵证明此定理.采用反证法，如果det(A)=0，则Ax=0有非零解，记为，则12(,,)Tnxxxx1max0kixnxx由齐次方程组第k个方程,01njjijxa则有即,1nkjjkjkkaa这与假设矛盾，故det(A)≠0.迭代法的收敛性与稳定性关于解某些特殊方程组迭代法的收敛性设方程组Ax=b，如果(1)A为严格对角占优阵，则解Ax=b的Jacobi迭代法,Gauss-Seidel迭代法均收敛.(2)A为弱对角占优阵，且A为不可约矩阵,则解Ax=b的Jacobi迭代法,Gauss-Seidel迭代法均收敛.定理7只证(1)，(2)作为练习因为A是严格对角占优阵，所以0(1,,)iiainJacobi迭代阵)(1ULDJ0002122222211111112nnnnnnnnaaaaaaaaaaaa则||J||1，所以Jacobi迭代法收敛.迭代法的收敛性与稳定性关于解某些特殊方程组迭代法的收敛性])(det[)det(1ULDIGI.0])(det[])det[(1ULDLD)(.0])(det[ULD下面证明Gauss—Seidel迭代法收敛.下面证明||1.若不然,即||1,则.),,2,1(||||||||111ijnijijijijijiiniaaaa由于.0])det[(1LD所以由，得1()GDLU迭代法的收敛性与稳定性关于解某些特殊方程组迭代法的收敛性.),,2,1(||||||||111ijnijijijijijiiniaaaa即矩阵ULD)(是严格对角占优矩阵，故可逆，这与(*)式矛盾，所以||1,从而(G)1，即Gauss—Seidel迭代法收敛..212222111211nnnnnnaaaaaaaaa迭代法的收敛性与稳定性关于解某些特殊方程组迭代法的收敛性若A为正定矩阵，则方程组Ax=b的Gauss-Seidel迭代法收敛..),(),(),(yLyyDyyyLT则内积从而因为A正定，所以D正定，故定理1(),()TTDLLyyLyDLy(,)((),)TLyyDLyy因为，设为G的特征值，y为对应的特征(复)向量，即1,()TTADLLGDLL(,)0Dyy迭代法的收敛性与稳定性关于解某些特殊方程组迭代法的收敛性).(),(),(),(ibayLyLyyyyLT所以||1,从而(G)1,故Gauss-Seidel迭代法收敛.1)(||22222baba.)(),(),(),