1 6 2线性方程组迭代解法

第六章线性方程组迭代解法内容提要§6.1概论§6.2(I)Jacobi

迭代法

§6.2(II)Gauss-Seidel迭代法§6.3迭代法的收敛性§6.4

SOR法本章学习要点概

论引子迭代法的基本思想迭代法的主要步骤引子直接法得到的解是理论上准确的，但是我们可以看得出，它们的计算量都是n3数量级，存储量为n2量级，这在n比较小的时候还比较合适（n<400），但是对于现在的很多实际问题，往往要我们求解很大的n的矩阵，而且这些矩阵(系数矩阵)往往是含有大量的0元素。对于这类的矩阵，再用直接法时就会耗费大量的时间和存储单元。另一方面,实际计算结果精度有时无法保.主要原因是在多次消去、回代过程中四则运算的误差积累与传播无法控制.因此我们有必要引入一类新的方法：迭代法。返回节迭代法的基本思想迭代法是解线性方程组的一个重要的实用方法，特别适用于求解在实际中大量出现的，系数矩阵为稀疏阵的大型线性方程组。迭代法的基本思想是去构成一个向量序列{X(k)}，，并且X*就是要求解使其收敛至某个极限向量X*的方程组：AX=b的准确解。返回节迭代法的主要步骤解线性方程组迭代法的主要步骤是:

1.把所给的线性方程组AX=b化成如下形式的同解方程组（1),按迭X=BX+f2.给出初始向量代公式(k=0,1,2,…)（2)X(k+1)=BX(k)+f进行计算。nTn(0)

(0)(0)1

2(0)X

=

(x

,

x

),

x

˛

R如果按上述迭代公式所得到的向量序列{X

(k)}收敛于某个向量X

*

,则X*

就是方程组

AX

=b

的解，并称此迭代法收敛。否则，就叫不收敛或发散。式(1)、(2)中的矩阵B

，称为迭代矩阵。研究

内容：

如何建立迭代格式？

向量序列的收敛条件？

收敛速度？

误差估计？本章重要介绍三个迭代法，即：1）Jacobi迭代法,2）Gauss-Seidel

迭代法,3）超松弛迭代法（SOR法）及其收敛性。返回章§3.2(I)Jacobi迭代法数学问题的描述Jacobi迭代法的主要步骤数学问题的描述设有线性方程组AX

=b即aa

x

+

ax

+

a

x

+

+

a

x

=

bx

+

+

a

x

=

ban1

x1

+

an2

x2

+

+

ann

xn

=

bn21

1

22

2

2n

n

211n

n12

211

1（3）其中

A=(aij)nn

非奇异（|A|„0），且a

ii≠0

(i=1,2,…,n),

由式（3）得aii

xi(i

=

1,2,,

n)

（4）=

bi

-

aij

x

jj

„i返回引用若记00

002122

2n

n1

n2

nn

-

a1n

0

-

a12

0

-

aU

=

-

a

-

a

-

aL

=

aaa11D

=

（5）（6）则有A=D-L-U成立，而式（3-4）的矩阵形式为DX

=（L+U）X+b等式两边乘以D-1，得X=

D-1（L+U）X+

D-1b由此得到迭代公式X（k+1）=

D-1（L+U）X（k）+

D-1b（7）即(i

=

1,2,,

n)(k

=

0,1,2,)

（8）)

/

aa

x=

(b

-xii(

k

)j

„iij

ji(

k

+1)i这种迭代法，称为Jacobi迭代法。返回节

...

...

...

...

an1x1

+an2

x2

+...+annxn

=bn

a21x1

+a22x2

+...+a2n

xn

=b2

a11x1

+a12x2

+...+a1n

xn

=b1aii

„0写成矩阵形式：A

=-L-UDAx

=

b(D

-(L

+U

))x

=

bDx

=

(L

+U

)x

+

bx=

D-1

(L

+U

)x

+

D-1bBfJacobi

迭代阵kk+1x

=

D-1(L

+U)x

+D-1bJacobi

迭代法33a22aaa11D

=nn

210L

=-a31

n1-a

0-a32

0

-a

-an2

-an3

0232n

U

=0

-a12

-a13

-a1n

0

-a

-a

0

-a3n

03312132221233132J2naa-1a-1-1B

=D-1(L+U)

=a-10

0

-a1n-a

0

+

3n

11

n1

n2

n3

nn

-a

-a

0

-a

-a0

-a

-a

-a

0

0-a

-a

-a

0

1111112122222233333300nnnnnnaaaaaaaaaaaaaa

0-

a12-

a13-

a1

n--

a

23-

a

2

nB

J

=-31

-

a

32-

a

3

n

-

a

n

1-

a

n

2-

a

n3

0雅可比(Jacobi)迭代法每迭代一次主要近似计算一次矩阵乘向量；计算过程中,初始数据A始终不变;,需要两J迭代矩阵

B

=

D-1

(

L

+

U

)

;(

k

)JB

X计算过程中涉及到的中间变量X

(K

)及X

(k

+1)组工作单元x(n), y(n)来存储.Jacobi

迭代法的计算步骤(5步)为：①k=1；输入最大迭代次数N，误差ε以及迭代初值

X=（x1，x2，…

，xn）②(i

=

1,2,；,

n)yi

=

(bi

-

aij

x

j

)

/

aiij„i③

如果||Y-X||<ε，则输出Y=（y1，y2，…

，yn）。④k=k+1，如果k>N，算法失败。⑤置X=Y，即xi=yi

(i=1,2,…,n)，转②；Jacobi迭代法的主要步骤例1=

62

3

4141

2

33

x2

-

x3

+

8

x4

=

152

x

-

x

+

10

x

-

x

10

x1

-

x2

+

2

x3求解

-

x

+

11x

-

x

+

3

x

=

25=

-11)

/

8)

/

1143412(

k

)31(

k

)2

(

k

+1)4(

k

)(

k

)(

k

+1)2

1(

k

)3(

k

)3(

k

)2(

k

+1)+

xx

=

(15

-

3

xx(

k

+1)

=

(-11

-

2

x(

k

)

+

x(

k

)

+

x(

k

)

)

/

10)

/

10-

3

x=

(25

+

x

+

xx-

2

x=

(6

+

xx解:Jacobi迭代公式为：选取X（0）=(0,0,0,0)T,迭代10次，结果见表1

返回引用kx1（k）x2（k）x3（k）x4（k）00.00000.00000.00000.000010.60002.2727-1.10001.875021.04731.7157-0.80520.885230.93262.0533-1.04931.130941.01521.9537-0.96810.973950.98902.0114-1.01031.021461.00321.9922-0.99450.994470.99812.0023-1.00201.003681.00061.9987-0.99900.998990.99972.0004-1.00041.0006101.00011.9998-1.99980.9998例3.1迭代结果表1返回引用法并没有充分及时地利用这些信息,为此我们得到改进的格式,称为高斯—塞德尔(Gauss–Seidel)迭代公式。i在计算迭代值

x(k

+1)

,

利用它前面已计算的值(

)

(

)

(

)而此时x,x

,,x

也已计算,但是Jacobi迭代k

+1k

+1

k

+11

2

i

-1Jacobi迭代法的改进对于Jacobi迭代法,它的每一步设定计算顺序为x1

fi

x2

fi

fi

xnjxl(

j

=1,

2,

n;l

=1,,

k

)§3.2(II)Gauss-Seidel迭代法算法分析与描述实例求解算法分析与描述a

xxii(k

)ij

j(k

)ij

ji-

a

x=

(b

-

i

-1

n(k

+1)i)

/

a

(i

=

1,2,,

n)

(8)可写成形如原Jacobi迭代公式(8)=

(b

-xa

x

)

/

aii

(i

=

1,2,,

n)(k

=

0,1,2,)

(

k

)ij

jj

„ii(

k

+1)ij=1

j=i

+1在Jacobi

迭代中，是用X(k)的全部分量来计算X(k+1)的全部分量的。i我们应该注意到，在计算新分量x

(k+1)时，分量x1(k+1),x2(k+1),…,xi-1(k+1)都已经算出。返回引用如果Jacobi

法收敛，则可期望X(k+1)比X(k)更好，在式(8)中右边第1个求和号中，用X(k+1)的分量代替X(k)的分量，似乎更合理些。这对许多问题来说，不仅会加快收敛速度，更重要的是，在排程序时，不必另设一套单元来记存上一次的近似解。这就是逐个代换算法，又称Gauss-Seidel迭代法。因此，我们就得到新的迭代公式：xn(k

)a

x

-=

(b

-

ij

j

iij=i

+1i

-1i

ij

jj=1(k

+1)(k

+1)ia

x

)

/

a

(i

=

1,2,,

n)（9)这就是Gauss-Seidel迭代公式．X(k+1)=BG

X(k)

+

fG（10）其中BG=(D-L)-1U，fG=(D-L)-1b，称BG为G-S迭代矩阵。由于Gauss-Seidel迭代法逐次用计算出来的新值代替旧值，所以在收敛的条件下，它要比Jacobi迭代法收敛速度快。返回节Gauss-Seidel迭代公式的其矩阵形式为：实例求解

4(

k

+1)(

k

+1)1(

k

+1)2(

k

+1)3(15

-

3

x

(

k

+1)

+

x

(

k

+1)

)

/

82

3x(-11

-

2

x

(

k

+1)

+

x

(

k

+1)

+