第三章 逐次逼近法
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
?1?1Jacobi迭代公式的矩阵形式 xn?1?D(L?U)xn?Db?Bxn?f
?1?1Gauss-Seidel迭代公式的矩阵形式 xn?1?(D?L)Uxn?(D?L)b?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迭代法，单根为二阶收敛 limxk?1??xk??2k??xk?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
?1证明：令L??(D??L)[(1??)D??U]，如果超松弛迭代法收敛，应该有?(L?)?1
det(L?)?det((D??L))det((1??)D??U)?(?dii)(1??)?1?1i?1nnn?di?1nii?(1??)???ini?1n而?(L?)?max?i?1,所以(1??)?1?i?n1????，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?210ix?10,显然f(1)?0,f(2)?0,f(x)??(?1)iixln(i)?0
'i?210因此该方程在[1,2]有且仅有一个实根，Newton迭代公式为
xn?1?xn?(?(?1)ii?210ixn?10)/（?(?1)iixnln(i)），x0=1.5 即可
i?2104、由求a的Newton 迭代公式 xk?1?1a(xk?),xk?0,k?0,1,2,,... 2xk证明：对一切k?1,有xk?a,并且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,对任意范数有，lim证明：首先存在某种范数
kk??Ak??(A)
k*?(A)?A??(Ak)??，而?(Ak)??k(A) 所以
?k(A)?Ak?k(A)?Ak*??k(A)????k(A)(1??/?k(A))，取???k(A) 得到 ?2?k(A) ，对不等式同时取极限即得到 limkAkk??k****??(A)
再根据范数的等价性 c1A?Ak?c2Ak 对不等式同时取极限即得到对任意范数有
结果 limkk??Ak??(A)
37、确定常数p,q,r，使如下迭代法收敛到a,xk?1qara2?pxk?2?5，该方法至少几阶？
xkxk解：根据定理3.6，一个迭代格式，在根附近它的p-1阶导数为零，就至少有p阶收敛速度
qara2由迭代格式?(x)?px?2?5,如果它收敛到3a，那么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 x?xk?1x?xk?13但是limk?2?limk?2?*?0，它只有线性收敛速度xk?1?xk2x22k??k??1(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）。
26） 设φ(x)=x-β(x-7)，要使迭代法xk+1=φ(xk)局部收敛到x*=7，则β取值范围是
（0???1/7）。
7） 用迭代法xk+1=xk-λ(xk)f(xk)求f(x)=x3-x2-x-1=0的根，若要使其至少具有局部平方收敛，
则（?(xk)收敛到
1）。 2(3??2??1)
相关推荐：
杳然