第三章、逐次逼近法

第三章逐次逼近法1.1内容提要1、一元迭代法xn+1=φ(xn)收敛条件为：1）映内性x∈[a,b]，φ(x)∈[a,b]2）压缩性∣φ(x)-φ(y)∣≤L∣x-y∣其中L＜1，此时φ为压缩算子，在不断的迭代中，就可以得到最终的不动点集。由微分中值定理，如果∣φ’∣≤L＜1，显然它一定满足压缩性条件。2、多元迭代法xn+1=φ(xn)收敛条件为：1）映内性xn∈Ω，φ(xn)∈Ω2）压缩性ρ（▽φ）＜1，其中▽φ为xn处的梯度矩阵，此时φ为压缩算子，在不断的迭代中，就可以得到最终的不动点集。3、当φ(x)=Bx+f时，收敛条件为，ρ（B）＜1，此时xn+1=Bxn+f，在不断的迭代中，就可以得到线性方程组的解。4、线性方程组的迭代解法，先作矩阵变换ULDAJacobi迭代公式的矩阵形式fBxbDxULDxnnn111)(Gauss-Seidel迭代公式的矩阵形式fBxbLDUxLDxnnn111)()(超松弛迭代法公式的矩阵形式fBxbLDxUDLDxkkk111)(])1[()(三种迭代方法当1)(B时都收敛。5、线性方程组的迭代解法，如果A严格对角占优，则Jacob法和Gauss-Seidel法都收敛。6、线性方程组的迭代解法，如果A不可约对角占优，则Gauss-Seidel法收敛。7、Newton迭代法，单根为二阶收敛2211'''21lim)(2)(limkkkkkkkkxxxxffcxx8、Newton法迭代时，遇到重根，迭代变成线性收敛，如果知道重数m，)()('1kkkkxfxfmxx仍为二阶收敛9、弦割法)()())((111kkkkkkkxfxfxxxfxx的收敛阶为1.618，分半法的收敛速度为（b-a）/2n-110、Aitken加速公式11211112)(),(),(kkkkkkkkkkkxxxxxxxxxxx1.2典型例题分析1、证明如果A严格对角占优，则Jacob法和Gauss-Seidel法都收敛。证明：首先证Jacob法收敛，因为A严格对角占优，则),...,2,1(,,1niaanijjijii，于是),...,2,1(,11,1niaanijjijii，从而1)(1ULD，这又有1))((1ULD，因此Jacob迭代法收敛。再证G-S法收敛，因为1)(1ULD，由定理1.6，)(1ULDI非奇异，而0)det()det()det())(det())(det(1111ADADULDDULDI，所以0)det(A，从而严格对角占优矩阵一定可逆。在G-S法中，0)det(1niiiaLD，从而0))det((1LD，求矩阵特征值时，0))(det())det()))(()det(())(det(111ULDLDULDLDULDI只能是0))(det(ULD，因为A严格对角占优，),...,2,1(,,1niaanijjijii，如果1，两边乘nijijijijnijijijijnijjijiiaaaaaa111111,1,那么，这说明矩阵ULD)(仍然严格对角占优，前面已证明，该行列式不能为0，这是一个矛盾。因此，只能是1，而这恰好说明Gauss-Seidel迭代法收敛。2、证明：如果A的对角元非零，超松弛迭代法收敛的必要条件是20证明：令])1[()(1UDLDL，如果超松弛迭代法收敛，应该有1)(LniinniiinniiiddUDLDL11111)1()1()())1det(())det(()det(而11,1)max(1)1(,1max)(1111nininiinniininiL，所以，从而必须满足20。3、分析方程2x-3x+4x-5x+6x-7x+8x-9x+10x=10是否有实根，确定根所在的区间，写出求根的Newton迭代公式,并确定迭代的初始点。解：0)ln()1()(,0)2(,0)1(,10)1()(102'102iixfffixfxiixii显然令因此该方程在[1,2]有且仅有一个实根，Newton迭代公式为(1nnxx)10)1(102nxiii/（)ln()1(102iinxii），x0=1.5即可4、由求a的Newton迭代公式,...,2,1,0,0),(211kxxaxxkkkk证明：对一切,...,,,121xxaxkk并且有是递减序列。证明：首先，如果10,0kkxx则迭代序列中的xk0，于是,...2,1,0,,1.2.21)(2111kaxxaaxxaaxaxkkkkkk所以。又因为k=1开始，为递减序列所以，于是1221,1))(1(21)1(21kkkkkkxxaaxaxxax5、若f(x)在零点ξ的某个邻域中有二阶连续导数，并且f’(ξ)≠0，试证：由Newton迭代法产生的xk(k=0,1,2,…)有)(2)(lim'''2211ffxxxxkkkkk证明：由Taylor公式，得证。，，由于，整理得到）式变为）后，（）代替（用（）（）（迭代公式整理可以得到由）（）（,)(2)()(!2)())(()()(23440))(()(30))(()(2)(!2)())(()()(1)(!2)())(()()(111111'''2211221''11'1111'1212'2221''212'2122''22'2kkkkxkkxkkkkkkxkkkkkkkkkkkkkkkxkkkkkkxkkkxxffxxxxxxfxxxfxfxfxxxfxfxxxfxfNewtonxxfxxxfxfxfxxfxxxfxfxf6、证明：A∈Cn*n,对任意范数有，)(limAAkkk证明：首先存在某种范数)()()()(*AAAAAkkkkk，而所以))(/1)(()()(*AAAAAkkkkk，取)(Ak得到)(2)(*AAAkkk，对不等式同时取极限即得到)(lim*AAkkk再根据范数的等价性*2*1kkkAcAAc对不等式同时取极限即得到对任意范数有结果)(limAAkkk7、确定常数p,q,r，使如下迭代法收敛到52213,kkkkxraxqapxxa，该方法至少几阶？解：根据定理3.6，一个迭代格式，在根附近它的p-1阶导数为零，就至少有p阶收敛速度速度。附近，至少有三阶收敛，此时该迭代格式在根立即可以解出：右端求函数和导数值对数值和各阶导数，令为根，在此处求函，那么如果它收敛到由迭代格式91,95)(,0)(,0)(,)(,)(33'3333522rqpxaaaaaxaxraxqapxx1.3习题解答1、判断正误、选择和填空：1）、对于迭代过程，xn+1=φ(xn)，若迭代函数在x*的邻域有连续的二阶导数，且1)(*'x，则迭代过程为超线性收敛。（不正确），xn+1=φ(xn)的迭代收敛条件有两条，1）映内性xn∈[a,b]，φ(xn)∈[a,b]2）压缩性1)(*'Lx。更不能保证有超线性收敛，例如：，它只有线性收敛速度但是满足，迭代收敛，并有根023)(311)(,38197.0)1(31)(*21212112**21limlimxxxxxxxxxxxxxxkkkkkkkkkkkkk2）用Newton迭代法求任何非线性方程均局部平方收敛。（不正确）3）若线性方程组Ax=b的系数矩阵A为严格对角占优，则Jacobi迭代法和G-S迭代法都收敛。（正确）4）解非线性方程f(x)=0的弦解法迭代具有（局部超线性敛速1.618）。（A）局部平方收敛；（B）局部超线性收敛；（C）线性收敛5）任给初始向量x(0)及右端向量f，迭代法x(k+1)=Bx(k)+f收敛于方程组Ax=b的精确解x*的充要条件是（1)(B）。6）设φ(x)=x-β(x2-7)，要使迭代法xk+1=φ(xk)局部收敛到x*=7，则β取值范围是（7/10）。7）用迭代法xk+1=xk-λ(xk)f(xk)求f(x)=x3-x2-x-1=0的根，若要使其至少具有局部平方收敛，则（)123(1)(2收敛到kx）。)123(1)(0)123)((1)123)(()()(1)(0)()123)(()()(1)()1)(()()()(222'''2''23，所以，而时，应有如果平方收敛，则，fxxxxxfxxxxxxxxfxxx8）用二分法求x3-2x-5=0在[2，3]内的根，并要求51021kx，需要迭代（18）步。9）求f(x)=5x-ex=0在[0，1的根，迭代函数xex51)(的简单迭代公式收敛阶为（线性）；Newton迭代公式的函数（xxeexxx55)(）；其收敛阶为（二阶）。10）给定方程组212111bbxxaa，a为实数，当a满足（1a），且0w2时SOR法收敛。解：超松弛迭代格式bLDxUDLDxkk111)(])1[()(现A对称，再加上正定就一定收敛，10101110aaAaaaAI，所以正定，由于，，解出由2、用列主元消去法解方程组Ax=b，其中A=50.135.000.133.055.019.171.10042.015.1，b=68.028.27.193对所求的结果x，使用三次迭代改善后，解的精度能否有明显提高？4、设有线性方程组6853.11791.55611.16120.9710.162220.2333.10920.0153330.3321xxx=4254.8544.28913.15，其精确解x*=(1,1,1)T，现用Gauss列主元消去法，得到的近似解x（1）=(1.2001,0.99991,0.92538)T，试用迭代改善法改善其精度。5、设方程组为22211211aaaa2xx=21bb,02211aa证明：（1）用Jacobi迭代和Gauss-Seidel迭代法收敛的充要条件为122112112aaaa（2）Jacobi迭代和Gauss-Seidel迭代法同时收敛或者发散证明：（1）先作矩阵变换ULDAJacobi迭代公式的矩阵形式bDxULDxnn111)(其中2211211222221111210,00)(aaaaBIaaaaULDBJJ解出由而2211211222aaaa，由迭代收敛的充要条件1)(JB，于是1,1,1221121122aaaaGauss-Seidel迭代公式的矩阵形式bLDUxLDxnn111)()(其中2211211221221121122