第三章 逐次逼近法
1.1
1、一元迭代法x n+1=φ(x n )收敛条件为：
1）映内性x ∈[a,b]，φ(x) ∈[a,b] 2）压缩性∣φ(x) -φ(y)∣≤L ∣x-y ∣其中L ＜1，此时φ为压缩算子，在不断的迭代中，就可以得到最终的不动点集。由微分中值定理，如果∣φ’∣≤L ＜1，显然它一定满足压缩性条件。
2、多元迭代法x n+1=φ(x n )收敛条件为：
1）映内性x n ∈Ω，φ(x n ) ∈Ω 2）压缩性ρ（▽φ）＜1，其中▽φ为x n 处的梯度矩阵，此时φ为压缩算子，在不断的迭代中，就可以得到最终的不动点集。
3、当φ(x )= Bx+f 时，收敛条件为，ρ（B ）＜1，此时x n+1= Bx n +f ，在不断的迭代中，就可以得到线性方程组的解。
4、线性方程组的迭代解法，先作矩阵变换 U L D A --= Jacobi 迭代公式的矩阵形式 f Bx b D x U L D x n n n +=++=--+111)(
Gauss-Seidel 迭代公式的矩阵形式 f Bx b L D Ux L D x n n n +=-+-=--+111)()( 超松弛迭代法公式的矩阵形式
f Bx
b L D x U D L D x
k
k k +=-++--=--+ωωωωω111
)(])1[()(
三种迭代方法当1)(
5、线性方程组的迭代解法，如果A 严格对角占优，则Jacob 法和Gauss-Seidel 法都收敛。
6、线性方程组的迭代解法，如果A 不可约对角占优，则Gauss-Seidel 法收敛。
7、Newton 迭代法，单根为二阶收敛 2
2
11'
'
'2
1lim
)
(2)(lim
---∞
→+∞
→--=-=
=--k k k k k k k k x x x x f f c x x ξξα
α
8、Newton 法迭代时，遇到重根，迭代变成线性收敛，如果知道重数m ， )
()('
1k k k k x f x f m x x -=+仍为二阶收敛 9、弦割法)
()())((111--+---
=k k k k k k k x f x f x x x f x x 的收敛阶为1.618，分半法的收敛速度为（b-a ）/2n-1
10、Aitken 加速公式1
1211112)
(),(),(+-
-
--
+-
+-
-
+-
--
+---
===k k k k k k k k k k k x x x x x x x x x x x ϕϕ
1.2 典型例题分析
1、证明如果A 严格对角占优，则Jacob 法和Gauss-Seidel 法都收敛。
证明：首先证Jacob 法收敛，因为A 严格对角占优，则),...,2,1(,,1n i a a n
i
j j ij ii =>
∑
≠-，于是
),...,2,1(,11,1n i a a n
i
j j ij ii
=<∑
≠-，从而1)
(1
<+∞
-U L D
，这又有1))((1
<+-U L D
ρ，因
此Jacob 迭代法收敛。
再证G-S 法收敛，因为1)
(1
<+∞
-U L D
，由定理1.6，)(1
U L D
I ++-非奇异，而
0)det()det()det())(det())(det(1
1
1
1
≠==++=++----A D
A D U L D D
U L D
I ，所以
0)d e t (≠A ，从而严格对角占优矩阵一定可逆。
在G-S 法中，0)det(1
≠=
-∏=n
i ii
a
L D ，从而0))
det((1
≠--L D ，求矩阵特征值时，
))(det())
det()))(()
det(())(det(1
1
1=---=---=-----U L D L D U L D L D U L D I λλλ只能是0))(det(=--U L D λ，因为A 严格对角占优，),...,2,1(,,1n i a a n
i
j j ij ii =>
∑
≠-，如果
1≥λ，两边乘∑
∑
∑
∑
∑
+---+---≠-+
>
+
=
>
n
i j ij i j ij n
i j ij i j ij n
i
j j ij ii a a a a a a 1
11
1
1
1
,1,λλλλλλ那么，这说
明矩阵U L D --)(λ仍然严格对角占优，前面已证明，该行列式不能为0，这是一个矛盾。因此，只能是1<λ，而这恰好说明Gauss-Seidel 迭代法收敛。
2、证明：如果A 的对角元非零，超松弛迭代法收敛的必要条件是20<<ω
证明：令])1[()(1
U D L D L ωωωω+--=-，如果超松弛迭代法收敛，应该有1)(<ωρL
∏∏∏===--=
-=-=+--=n
i i
n
n
i ii
n
n i ii d
d U D L D L 1
1
1
1
1
)1()
1()())1det(())det(()det(λ
ωωωωωω而11,1)max (1)
1(,1max )(11
1
1<-<≤=
-=
-<=≤≤==≤≤∏
∏ωλλω
λ
ωλρωn
i n
i n
i i n
n
i i
n
i n
i L ，所以，
从而必须满足20<<ω。
3、分析方程2x -3x +4x -5x +6x -7x +8x -9x +10x =10是否有实根，确定根所在的区间，写出求根的Newton 迭代公式,并确定迭代的初始点。
解：0)ln()1()(,0)2(,0)1(,10)1()(10
2
'
10
2
>-=
><--=
∑∑==i i
x f f f i
x f x
i i x
i i 显然令
因此该方程在[1,2]有且仅有一个实根，Newton 迭代公式为
(
1-=+n n x x )10)1(10
2
--∑
=n
x i i
i
/（)ln()1(10
2
i i
n
x i i
∑=-）
，x 0=1.5 即可
