第三章逐次逼近法.docx

第三章逐次逼近法

1、 一元迭代法xn+1=^ (x n)收敛条件为：
映内性 x € [a,b](x) C [a,b] 2 )压缩性 I 4 (x)-力(y) I v L I x-y I 其中 Lv 1,
此时4为压缩算子，在不断的迭代中，就可以得到最终的不动点集。由微分中值定理， 如果
I 4 ' I < Lv 1,显然它一定满足压缩性条件。
2、 多元迭代法xn+1=力(xn)收敛条件为：
1)映内性xn£ Q , (f) (xn) EQ 2 )压缩性p ( ▽ 4 ) V 1 ,其中▽'为xn处的梯度矩阵， 此时4为压缩算子，在不断的迭代中，就可以得到最终的不动点集。
3、 当4 (x)= Bx+f时，收敛条件为，p (B) V 1,此时xn+1= Bxn+f,在不断的迭代中，就可 以得到线性方程组的解。
4、 线性方程组的迭代解法，先作矩阵变换 A = D - L -U
1 1.
Jacobi迭代公式的矩阵形式 xn^ = D (L+U)x/D b = Bx” + f
1 1.
Gauss-Seidel 迭代公式的矩阵形式 xn^ = (D — L) Uxn + (D — L) b = Bxn 十 f
超松弛迭代法公式的矩阵形式
xk 1 =(D - L)」[(1 一 )D U]xk (D - L)」b = Bxk f
三种迭代方法当 P(B) < 1时都收敛。
5、线性方程组的迭代解法，如果 A严格对角占优，则 Jacob法和Gauss-Seidel法都收敛。
6、线性方程组的迭代解法，如果 A不可约对角占优，则 Gauss-Seidel法收敛。
7、Newton迭代法，单根为二阶收敛
" it
-f () c
2f ()
=lim k ■:
xk
—xka 2
—Xk J2
8、Newton法迭代时，遇到重根，迭代变成线性收敛,
如果知道重数m,
xk 1
=xk
f (xk)
f (xk)
仍为二阶收敛
9、弦割法xk * = xk
f(xk)(xk -x^)
f (xk) - f(xkj)
,分半法的收敛速度为
n-1
(b-a) /2
2
(xk 1 - xk)
10、Aitken 加速公式 xk =9(xk」)，xk+= ?(xk), xk = xk+
xk】- 2xk xk 1

1、证明如果 A严格对角占优，则 Jacob法和Gauss-Seidel法都收敛。
证明：首先证Jacob法收敛，因为 A严格对角占优，则 》Z an ,(i =1,2,...,n),于是
j T j=i
n
Z a,j
j JL,j#
<1,(i =1,2,...,n)，从而 |D-(^U^<1 ,这又有 P(D」(L+U)) <1，因
此Jacob迭代法收敛。
再证G-S法收敛，因为
D「(L+U)|艺<1，, l+D」(L+U )非奇异，而
_ 1
det(l + D (L + U )) = det(D (D + L + U)) = det(D A) = det(D ) det(A) # 0，所以
det(A)。0,从而严格对角占优矩阵一定可逆。
n
在G-S法中，det(D—L)=n a^ #0,从而det((D — L)」)# 0 ,求矩阵特征值时，
i 4
_ 1 _ 1 _ _ 1 _ _
det(T-(D-L) U)=det((D-L) (，(D - L)-U)) = det(D - L) — )det。(D - L)-U ) = 0
只能是det(A(D —L) —U )=0,因为A严格对角占优，aH > Z a^ ,(i =1,2,...,n),如果 j」,j =i n i _1 n i _1 n
国习，两边乘|纣，那么加|>2： aj归=£ aM+Z aj^ a. || " + £国，这说
j」j# j .1 jx4 jn j-±4
明矩阵从D -L) -U仍然严格对角占优，前面已证明，该行列式不能为 0,这是一个矛盾。
因此，只能是同<1,而这恰好说明 Gauss-Seidel迭代法收敛。
2、证明：如果 A的对角元非零，超松弛迭代法收敛的必要条件是 0<与<2
证明：令L^ = (D —coL)」［(1 -co)D十切U］,如果超松弛迭代法收敛，应该有 P(LQ<1
n n n
det(L.) =det((D - 山尸闭制(1- ・)D ，U) =Q【dii"(1-，)ni【dii =(1 -，)n『 ％
而代LQ=maw"i <1,所以(1一由)
=H K ,1f
i」