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

hao

第3章 解线性方程组的迭代法

清华大学工程硕士数学课程--数值分析 数值方法

§1 Jacobi迭代法和Gauss-Seidel迭代法

（I）迭代概念

（1） Ax b ， A Rn n， b R

A M N ， M R

n n

n

， N R

n n

，

M非奇异

Mx Nx

b

Mx Nx b

x M

1

Nx M

1

1

b

如果令 B M

1

N,f Mb，那么上式写成

（2） x Bxf 此方程组等价于Ax b

任给x

(0)

R，

(1)

n

x x

Bx

(0)

f f

(2)

Bx

(1)

（3） x

(k 1)

Bx

(k)

k(

f

(k)

)

由（3）可以确定 x

x

(k)

，当x

x R，即

*n

x

*

0 时，有

*

*

x Bx f

x同样满足 Ax b

*

*

定义 式（3） x

(k 1)

Bx

k(

f称为求解 （1）

)

Ax b 的简单形式迭代法，B称为迭代矩阵。

（II）Jacobi迭代法

hao

Ax b

写成分量形式有

n

a

j 1

ij

xj bi,

i 1,2, ,n

i 1n

ij

aiixi

a

j 1

xj

j i 1

aijxj bi,i 1,2, ,n

假定 aii 0 ，那么有 xi

1aii

i 1

n

ij

(bi

a

j 1

xj

j i 1(0)

aijxj),i 1,2, ,n

迭代法为任给 x

(k 1)i

(0)

(x1,x2, ,xn) R

n

(0)(0)Tn

x

1aii

i 1

(bi

a

j 1

ij

x

(k)j

j i 1

(k)

aijxj),i 1,2, ,n;k 0,1,

即：

(k 1 x1

(k 1) x2

(k 1) xn

)

1a111a221ann

(b (b (b

a1x21

k(

ax12

)k3

3 anxn

()k1

()

2

a21x1

(k)

a23x3

(k)

a2nxn

(k)

(k)

n

an1x1

(k)

an2x2

(k)

an,n 1xn 1

上式迭代方法称为Jacobi迭代 例1.1用Jacobi迭代法解方程组

x3 1 5x1 2x2 2

x1 4x2 x3 2

x 2x 4x 1

23 1

解 Jacobi迭代方法为 x1

(k 1)

15

14

(1 2x2(2 x1

k()

2x3

k(

k(

) 0.2

)

0x2.4

k(

)

k()

x0 .430x.3 25

k

(

k()

x2 x3

(k 1)

1

k()

x3) 0.5 0.x215

(k)

(k)

))

(k 1)

4

( 1 x1

T

(k)

2x2) 0.25 0.25x1

3

0.5x2

(k)

取 x

(0)

(0,0,0) R

hao

k012 111213

x1

(k)

x2

(k)

x3

(k)

00.2 0.1

00.50.5125

0 0.25 0.05

0.000008 0.0000340.000015

0.4998820.4999880.500002

0.0000390.0000250.000003

方程组 Ax b的准确解为x* (0,0.5,0)T R3。 若取 10那么 x(12) x(11)

x

(12)

4

。可取

T

( 0.000034,0.499988,0.000025)

为方程组的近似解。

为进行收敛性分析，把迭代方法写成向量形式。 A (aij)n n R

n n

] ,a,nn

A D L U;D diag[a11a,

0

a 21

L a31

a n1 0 U

22

0 a32 an2

a13 a230

an,n 1

， 0

a120

a1n a2n

an 1,n 0

Ax b

(D L U)x b Dx (L U)x b

x D(L U)x Db

x

(k 1)

1 1

D(L U)x

1(k)

Db

1

hao

BJ Dx

(k 1)

1

(L U)称为Jacobi迭代的迭代矩阵

(k)

BJx

Db

1

（III）Gauss-Seidel迭代法 Jacobi迭代有

i 1

n

ij

x

(k 1)i

(bi

a

j 1

x

(k)j

j i 1

aijxj)/aii,i 1,2, ,n

(k)

可以看出，当计算xi

(k 1)

时，x1

(k 1)

(k 1)

,x2

(k)

(k 1)

, ,xi 1

(k 1)

已经计算

出来了，一般可以认为xj要比xj更接近于xj。由此可

*

以设想把已经计算出来的分量在计算公式中立刻应用，这样 就有

i 1

n

ij

x

(k 1)i

(bi

a

j 1

x

(k 1)j

j i 1

aijxj)/aii,i 1,2, ,n

(k)

这个迭代公式称为Gauss-Seidel迭代公式

例1.2

x3 1 5x1 2x2 2

x1 4x2 x3 2

x 2x 4x 1

23 1

x1

(k 1)

15

(1 2x21414

k()

2x3 ) x3)

1)

k(

k()

x2 x3

取x(0)

T

(k 1)

(2 x1

k ()

(k 1)

( 1 x1

(7)

k( 1)

2x2

k (

)

1)

(0,0,0) R, x

3

(0.000002,0.500001,0.000000) R

T3

可见，Gauss-Seidel迭代法比Jacobi迭代法“好” 把Gauss-Seidel迭代方法写成

i 1

n

aiix

(k 1)

i

a

j 1

xij

(k 1)j

bi

j i 1

aijxj

(k)

(D L)x

(k 1)

b Ux

1

(k)

(k)

1

x

(k 1)

(D L)UxU,

(D L)b

令 G (D L)

1

称为Gauss-Seidel迭代的迭代矩 G

hao

阵，f (D L) 1b

x

(k 1)

Gx

(k)

f

例1.3 用Jacobi 迭代法和Gauss-Seidel迭代法解

6 10x1 x2 2x3

x1 11x2 x3 3x4 25

2x x 10x x 11234 1 3x2 x3 8x4 15

此方程组有唯一解 x* (1,2, 1,1)T R4

Jacobi x1

x2x3

(k 1)

1101

x2x1

(k)

15

x3

(k)

x3

35

3x4

(k)

(k 1)(k)

1

(k)

(k 1)

x4

(k 1)

111111111(k)1(k)3(k)11 x1 x2 x4

51010103(k)1(k)15 x2 x3

888

25

k0123 …… 此处隐藏：1793字，全部文档内容请下载后查看。喜欢就下载吧 ……