第三章 逐次逼近法
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、线性方程组的迭代解法，先作矩阵变换 A?D?L?U Jacobi迭代公式的矩阵形式 xn?1?D?1(L?U)xn?D?1b?Bxn?f
Gauss-Seidel迭代公式的矩阵形式 xn?1?(D?L)?1Uxn?(D?L)?1b?Bxn?f 超松弛迭代法公式的矩阵形式
xk?1?(D??L)?1[(1??)D??U]xk?(D??L)?1?b?Bxk?f
三种迭代方法当?(B)?1时都收敛。
5、线性方程组的迭代解法，如果A严格对角占优，则Jacob法和Gauss-Seidel法都收敛。 6、线性方程组的迭代解法，如果A不可约对角占优，则Gauss-Seidel法收敛。 7、Newton迭代法，单根为二阶收敛 limk??xk?1??xk??2xk?xk?1?f''(?)?c??lim2f'(?)k??xk?1?xk?22
8、Newton法迭代时，遇到重根，迭代变成线性收敛，如果知道重数m， xk?1?xk?m仍为二阶收敛 9、弦割法xk?1?xk?f(xk)f'(xk)f(xk)(xk?xk?1) 的收敛阶为1.618，分半法的收敛速度为（b-a）/2n-1
f(xk)?f(xk?1)????10、Aitken 加速公式xk??(xk?1),xk?1??(xk),xk?xk?1?(xk?1?xk)2xk?1?2xk?xk?1????
1.2 典型例题分析
1、证明如果A严格对角占优，则Jacob法和Gauss-Seidel法都收敛。 证明：首先证Jacob法收敛，因为A严格对角占优，则aii?j?1,j?i?anij,(i?1,2,...,n)，于是
1aiij?1,j?i?anij?1,(i?1,2,...,n)，从而D?1(L?U)??1，这又有?(D?1(L?U))?1，因
此Jacob迭代法收敛。
再证G-S法收敛，因为D(L?U)?1??1，由定理1.6，I?D?1(L?U)非奇异，而
det(I?D?1(L?U))?det(D?1(D?L?U))?det(D?1A)?det(D?1)det(A)?0，所以
det(A)?0，从而严格对角占优矩阵一定可逆。
在G-S法中，det(D?L)??ai?1nii?0，从而det((D?L)?1)?0，求矩阵特征值时，
det(?I?(D?L)?1U)?det((D?L)?1(?(D?L)?U))?det(D?L)?1)det(?(D?L)?U)?0只能是det(?(D?L)?U)?0，因为A严格对角占优，aii?ni?1nj?1,j?i?anij,(i?1,2,...,n)，如果
n??1，两边乘?,那么?aii?j?1,j?i?aij???aij??j?1j?i?1?aij???aij??j?1i?1j?i?1?aij，这说
明矩阵?(D?L)?U仍然严格对角占优，前面已证明，该行列式不能为0，这是一个矛盾。因此，只能是??1，而这恰好说明Gauss-Seidel迭代法收敛。
2、证明：如果A的对角元非零，超松弛迭代法收敛的必要条件是0???2
证明：令L??(D??L)?1[(1??)D??U]，如果超松弛迭代法收敛，应该有?(L?)?1
det(L?)?det((D??L))det((1??)D??U)?(?dii)(1??)?1?1i?1nn?di?1nii?(1??)???ini?1n而?(L?)?max?i?1,所以(1??)?1?i?nn1????，ii?1nn???i?(max?i)n?1,1???1，
i?11?i?nn从而必须满足0???2。
3、分析方程2x-3x+4x-5x+6x-7x+8x-9x+10x=10是否有实根，确定根所在的区间，写出求根的Newton迭代公式,并确定迭代的初始点。 解：令f(x)??(?1)ii?21010ix?10,显然f(1)?0,f(2)?0,f(x)??(?1)iixln(i)?0
'i?210因此该方程在[1,2]有且仅有一个实根，Newton迭代公式为 ，x0=1.5 即可 xn?1?xn?(?(?1)i?10)/（?(?1)iixnln(i)）
ixni?2i?2104、由求a的Newton 迭代公式 xk?1?证明：对一切k?1,有xk?1a(xk?),xk?0,k?0,1,2,,... 2xka,并且x1,x2,... 是递减序列。
?证明：首先，如果x0?0,则迭代序列?xk?k?1中的xk>0 ，于是
xk?1a?x1xka1a(?)?.2k.?1,所以xk?1?a,k?0,1,2,...。又因为k=1开始 2axk2xakxk?a，于是xk?11a1a?(1?2)?(1?)?1,所以xk?xk?1，为递减序列 2xk22xk(a)xk?xk?1xk?1?xk?225、若f(x)在零点ξ的某个邻域中有二阶连续导数，并且f’(ξ)≠0，试证：由Newton迭代法产生的xk(k=0,1,2,…)有lim证明：由Taylor公式，
k???f''(?)? 2f'(?)f''(?x)f(x)?f(xk?2)?f(xk?2)(x?xk?2)?(x?xk?2)2???????（1）2!''f(?xk?1)f(xk?1)?f(xk?2)?f'(xk?2)(xk?1?xk?2)?(xk?1?xk?2)2??（2）2!由Newton迭代公式整理可以得到'f(xk?2)?f'(xk?2)(xk?1?xk?2)?0????（3）f(xk?1)?f'(xk?1)(xk?xk?1)?0?????（4）用（4）代替（3）后，（2）式变为f(xk?1)?f(xk?1)?f'(xk?1)(xk?xk?1)?xk?xk?1xk?1?xk?22
f''(?xk?1)2!(xk?1?xk?2)2，整理得到??f''(?xk?1)2f(xk?1)n*n
'，由于xk?1，?xk?1??,得证。k6、证明：A∈C,对任意范数有，limkAk????(A)
??(Ak)??，而?(Ak)??k(A) 所以
证明：首先存在某种范数
?(Ak)?Ak*?(A)?Akk*??k(A)????k(A)(1??/?k(A))，取???k(A) 得到 ?2?k(A) ，对不等式同时取极限即得到 limkAkk??k**?k(A)?Ak**??(A)
再根据范数的等价性 c1A?Ak?c2Ak 对不等式同时取极限即得到对任意范数有
结果 limkAk?k???(A)
37、确定常数p,q,r，使如下迭代法收敛到a,xk?1qara2?pxk?2?5，该方法至少几阶？
xkxk解：根据定理3.6，一个迭代格式，在根附近它的p-1阶导数为零，就至少有p阶收敛速度
qara23由迭代格式?(x)?px?2?5,如果它收敛到a，那么x?3a为根，在此处求函xx数值和各阶导数，令?(3a)?3a,?'(3a)?0,?\(3a)?0,对?(x)右端求函数和导数值51立即可以解出：p?q?,r??，此时该迭代格式在根附近，至少有三阶收敛速度。99
1.3 习题解答
1、 判断正误、选择和填空：
'*1）、对于迭代过程，xn+1=φ(xn)，若迭代函数在x* 的邻域有连续的二阶导数，且?(x)?1，
则迭代过程为超线性收敛。 （不正确），xn+1=φ(xn)的迭代收敛条件有两条，1）映内性xn∈[a,b]，φ(xn) ∈[a,b] 2）
'*压缩性?(x)?L?1。更不能保证有超线性收敛，例如：
12xk?1??(xk)?(xk?1)，迭代收敛，并有根x*?0.38197,满足?(x*)?13 xk?2?xk?1xk?2?xk?13但是lim?lim?*?0，它只有线性收敛速度1x?x2x22k??k??k?1k(xk?xk?1)32） 用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*的
充要条件是（?(B)?1）。
6） 设φ(x)=x-β(x-7)，要使迭代法xk+1=φ(xk)局部收敛到x*=7，则β取值范围是
2（0???1/7）。
7） 用迭代法xk+1=xk-λ(xk)f(xk)求f(x)=x3-x2-x-1=0的根，若要使其至少具有局部平方收敛，
则（?(xk)收敛到
1）。 2(3??2??1)?(x)?x??(x)f(x)?x??(x)(x3?x2?x?1)，?'(x)?1??'(x)f(x)??(x)(3x2?2x?1)如果平方收敛，则x??时，应有?'(?)?0，而?'(?)?1??'(?)f(?)??(?)(3?2?2??1)1?1??(?)(3?2?2??1)?0，所以?(?)?(3?2?2??1)
8） 用二分法求x3-2x-5=0在[2，3]内的根，并要求xk????10，需要迭代（18）步。 9） 求f(x)=5x-ex=0在[0，1的根，迭代函数?(x)?12?51?xe的简单迭代公式收敛阶为（线性）； 55x?exNewton迭代公式的函数（?(x)?x?）；其收敛阶为（二阶）。 x5?e10） 给定方程组?SOR法收敛。
解：超松弛迭代格式 xk?1?(D??L)?1[(1??)D??U]xk?(D??L)?1?b
现A对称，再加上正定就一定收敛，
?1?a??x1??b1?，且0 ?1.150.42100.71???193.7?????2、用列主元消去法解方程组Ax=b，其中A=1.190.550.33，b=2.28 ???????1.000.351.50????0.68??对所求的结果x，使用三次迭代改善后，解的精度能否有明显提高？ 4、设有线性方程组 ?3.3330015.920?10.333??2.222016.7109.6120?????1.56115.17911.6853??元消去法，得到的近似解x （1）?x1??15.913??x?=?28.544?，其精确解x*=(1,1,1)T，现用Gauss列主 ??2????8.4254???x3???=(1.2001,0.99991,0.92538)T，试用迭代改善法改善其精度。 ?a115、设方程组为??a21a12?a22???x??b1??x?=?b? , a11a22?0 ?2??2?证明：（1）用Jacobi迭代和Gauss-Seidel迭代法收敛的充要条件为 （2）Jacobi迭代和Gauss-Seidel迭代法同时收敛或者发散 a12a21?1 a11a22