第3章_解线性方程组的迭代法_962109547(3)

则称A是严格对角占优

（2）如果A的元素满足

n

aii

j 1j i

aij,

i 1,2, ,n

且上式中至少有一个不等号严格成立，那么称A为（弱） 对角占优

定理2.6 设 A Rn n为严格对角占优，那么A是非 奇异的

证：用反证法。设A是奇异阵，那么存在 x 0使得

Ax 0

记 xk maxj

j

,Ax

n

的第k个方程 0

akkxk akjxj

j 1

j k

n

akk xk

j 1j k

akj xj

n

akk

j 1j k

akj

xjxk

n

j 1j k

akj

这与A严格对角占优矛盾。 A非奇异

定理2.7 Ax b,A R

n n

,b R

n

设A严格对角占优。那么求解Ax b的Jacobi迭代和 Gauss-Seidel迭代均收敛。 证明： Jacobi迭代的迭代矩阵

BJ D

1

(L U) I D

1

A

其中 A D L U

n

BJ

max

1 i n

j 1

bij max

1 i n

j i

aijaii

1

(BJ) BJ

1

hao

Gauss-Seidel迭代收敛性 A严格对角占优， aii 0

G (D L)U

1

考虑G的特征值

det[ I G] det[ I (D L)U] det[(D L)

1

1

(D L) U ]

设 为G的特征值。那么 det[ I G] 0。由于aii 0 ，

det[D L] 0

det[(D L)] 0

1

det[ (D L) U] 0 （ 为G的特征值）

令

a11

a21

C (D L) U

an1

a12

a13a23

a22

an2 an3

a1n

a2n

ann

要证 1，从而有 (G) 1。Gauss-Seidel迭代收敛用 反证法。设 满足 1。利用A是严格对角占优 aii

j i

a

j

i 1

n

aii

j ii 1

aij

j 1n

aij

j i 1

aij

j 1

aij

j i 1

aij

这表明，矩阵C严格对角占优， C为非奇异，

detC 0，这说明 满足 1时不是G的特征值

1 (G) 1

例2.7 用Jacobi迭代法和Gauss-Seidel迭代法 求解

Ax b

其中

hao

10 A 1

1

110 1

2

2 5

,

72

b 83

42

解 Jacobi迭代 x1

(k 1)

110

1

(72 x

k(

2

)

x2

k

3

(

)

)

x2

(k 1)

x3

(k 1)

101(k)(k) (42 x1 x2) 5

(83 x1

(k)

2x3)

(k)

k01

x1

(k)

x2

(k)

x3

(k)

07.2

08.3

08.4

89

10.998110.9994

11.994111.9994

12.997812.9992

Gauss-Seidel

x1

(k 1)

1101

(72 x2(83 x1

(k)

2x3) 2x3)

(k)

(k)

x2x3

(k 1)(k 1)

(k 1)

101(k 1)(k 1) (42 x1 x2) 5

k01

x1

(k)

x2

(k)

x3

(k)

07.2

09.02

011.644

610.999911.999913.0000

数值结果看出。二个方法均收敛。事实上A为严格对角占优。 此外，Gauss-Seidel迭代比Jacobi迭代收敛更快。 （V）迭代法收敛速度 Ax b

x

(k 1)

(k)

x Bx f

Bx f

(B) 1，任取 x

(0)

R,

n

limx

k

(k)

x,

*

x Bx f

**

hao

e

(k)

x

k(

x 称为误差向量。并有

(k

1)

)*

e

(k)

Be Be

k(

e

ee

n

(k)

B

k

e

()

(k)(0)

B

k

此外，注意到 x

e

(0)

(0)

R是任取的，因此可以认为

0是任取的。

B

k

max(0)

e

0

ee

(k)(0)

即 B

k

给出了迭代k次后误差向量范数与初始误差向量

范数之比的最小上界（上确界）

一般要求

e

(k)

e

(0)

其中 1，一般 为一相当小的数。

已经证明 (B) 1 B 0 采用算子范数有

B有 B

k

k

k

0 。 那么当 k K时

(k)

从而有 e e

()

改写上面条件 B (B两边取对数

k

为

1k

k

)

k

1

B k(ln(

k

k

) ) ln

k

ln

1

lnB

k

k

1

可以看出，收敛快慢与 lnB

k

k

有关

hao

定理2.8 设

B Rn n,（算子范数），那么有

1

为任一矩阵范数

liB

k

k

k

B( )

定义2.5 R(B) ln (B) 称为迭代法 x(k 1) Bx

k(

f的渐近收敛速度；

1k

k

)

Rk(B) lnB

称为上述迭代法的平均收敛速度。

一般都采用渐近收敛速度来讨论迭代的收敛速度。 由定义可以看出，迭代方法的谱半径 (B)越小，收敛 速度越大。

例2.8 讨论用Jacobi迭代法和Gauss-Seidel迭代法解方 程组Ax b的收敛性。如果收敛，试比较哪种方法收敛较 快。其中

3

A 0

2

0 2

21

12

解（1）Jacobi迭代方法

3 D 0

0000

020

0

0 2

0

L 0

2

00 1

0

0 0

A D L U,,

0

U 0

02

1 0

0

1

BJ D(L U) 0

1

00 12

2

3 1 2 0

hao

I BJ 0

1

0

23

3

12

12

23

14

0

1 0, 2,3 收敛

（2）Gauss-Seidel迭代

3 1

G (D L)U 0

2

021

0

0 2

, B(J

) 1

1

0

00

0

2

1 0 0

0

000

2

3 1 2 11 12

(G)

1112

1 ， Gauss-Seidel迭代法收敛

1112

Gauss-Seidel方法收敛快。

并有：

R(G)R(BJ)

ln (G) ln (BJ)