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

第四章 解线性方程组的迭代法 4.1 4.1引言 在第二章中我们知道， 在第二章中我们知道，凡是迭代法都有一个收 敛问题，有时某种方法对一类方程组迭代收敛， 敛问题，有时某种方法对一类方程组迭代收敛，而 对另一类方程组进行迭代时就会发散。 对另一类方程组进行迭代时就会发散。 一个收敛的迭代法不仅具有程序设计简单， 一个收敛的迭代法不仅具有程序设计简单，适 于自动计算， 于自动计算，而且较直接法更少的计算量就可获得 满意的解。因此，迭代法亦是求解线性方程组， 满意的解。因此，迭代法亦是求解线性方程组，尤 其是求解具有大型稀疏矩阵的线性方程组的重要方 法之一。 法之一。 2012-5-1 jkhh 1

4.2 迭代法的基本思想 迭代法的基本思想是将线性方程组转化 为便于迭代的等价方程组， 为便于迭代的等价方程组，对任选一组初始 按某种计算规则， 值 xi( 0) (i = 1,2, L , n) ,按某种计算规则，不断地 对所得到的值进行修正，最终获得满足精度 对所得到的值进行修正， 要求的方程组的近似解。 要求的方程组的近似解。

2012-5-1

jkhh

设 A∈ R

n×n

b ∈ R n ,则线性方程组 非奇异， 非奇异，

有惟一解 x = A 1 b ,经过变换构造 Ax = b 出一个等价同解方程组 x = Bx + g 将上式改写成迭代式x ( k +1 ) = Bx ( k ) + g ( k = 0 ,1, 2 ,...)

选定初始向量 x = {x , x ,L, x( 0) ( 0) 1 ( 0) 2

( 0) T n

}

,反复不断地

使用迭代式逐步逼近方程组的精确解, 使用迭代式逐步逼近方程组的精确解,直到满 足精度要求为止。这种方法称为迭代法。 足精度要求为止。这种方法称为迭代法。2012-5-1 jkhh 3

如果 存在极限

xx

(k )

= x=

*

{ {x

(k ) 1* 1

,x

(k ) 2

,L , x

(k ) n

}

T

, x ,L , x

* 2

* n

}

T

则称迭代法是收敛的，否则就是发散的。 则称迭代法是收敛的，否则就是发散的。 收敛时， 收敛时，在迭代公式( k +1)

x

= Bx

(k )(k )

+g*

( k = 0,1, L)

中当 k → ∞ 时， x

x * = Bx * + g →x ,则

, 故 x * 是方程组 Ax = b 的解。 的解。 对于给定的方程组可以构造各种迭代公式， 对于给定的方程组可以构造各种迭代公式， 但并非全部收敛 。2012-5-1 jkhh 4

例4.1

用迭代法求解线性方程组

2 x1 + x 2 = 3 2 x1 + 5 x 2 = 3解 构造方程组的等价方程组 x1 = x1 x 2 + 3 据此建立迭代公式 x 2 = 2 x1 4 x 2 + 3 x x( x11) = 3 (1) x2 = 3,2012-5-1

( k +1) 1 ( k +1) 2

= x x + 3 = 2x 4x + 3(k ) 1 (k ) 1 (k ) 2 (k ) 2

取 x

(0) 1

=x

( 0) 2

=0

计算得( x14) = 15 (4) , x2 = 15 ( x15) = 33 L (5) , x2 = 335

( x12) = 3 (2) x2 = 3,

( x13) = 9 (3) x2 = 9,

迭代解

离精确解 x1 = 1, x2 = 1 越来越远迭代不收敛 jkhh

4.3 雅可比(Jacobi)迭代法 雅可比( )4.3.1雅可比迭代法算法构造 4.3.1雅可比迭代法算法构造 例4.2 用雅可比迭代法求解方程组

8 x1 3x 2 + 2 x3 = 20 4 x1 + 11x 2 x3 = 33 6 x + 3x + 12 x = 36 2 3 1

解：从方程组的三个方程中分离出 x1 , x2 和 x3 建立迭代公式1 5 3 (k ) 3 1 (k ) 5 ( k +1) x 2 xx2 + x3 + 3 x1 1 = x = 8 2 84 4 2 1 (k ) 1 ( k +1) 4 x 2 = 4 x1( k ) x = x 1 + 11 x3 + + 3 x 3 + 3 2 11 11 11 ( k +1) 1 1 () x3 = x1( k ) x 2k 1 +3 x = 1 x 4 2 x + 3 3 jkhh 2 1 2 4

2012-5-1

( 取初始向量 x ( 0 ) = ( x 1( 0 ) , x 2 0 ) , x 3( 0 ) ) T = ( 0 , 0 , 0 ) T

进行迭代, 可以逐步得出一个近似解的序列： 进行迭代 可以逐步得出一个近似解的序列：( ( ) ( x1( k ) , x 2k ) , x 3 k ) ) (k=1, 2, …)

直到求得的近似解能达到预先要求的精度， 直到求得的近似解能达到预先要求的精度， 则迭代过程终止， 则迭代过程终止，以最后得到的近似解作为线 性方程组的解。 性方程组的解。 当迭代到第10次有 当迭代到第 次有( ( x (10) = ( x1(10) , x210) , x310) )T = (3.000032,

1.999838,

0.9998813)T

计算结果表明， 计算结果表明，此迭代过程收敛于方程组的精 确解x 确解 *= (3, 2, 1)T。2012-5-1 jkhh 7

考察一般的方程组， 考察一般的方程组，将n元线性方程组 a 11 x 1 + a 12 x 2 + ... + a 1 n x n = b1 a 21 x 1 + a 22 x 2 + ... + a 2 n x n = b2 ...... a n 1 x 1 + a n 2 x 2 + ... + a nn x n = bn

据此建立迭代公式 i = 1, 2 , L , n 写成 ∑ a ij x j = b i j =1 1= 1,2,L ,nn) ( k ) 若iakii+1) 0 (i (bi ∑ a,分离出变量,2xL n x( ≠ = i =1 ,i ij x j ) aii j =1 j ≠n i 1 xi = ( b i ∑ a ij x j ) i = 1, 2 , L , n a ii 上式称为解方程组的Jacobi迭代公式。 Jacobi迭代公式 上式称为解方程组的1 j = Jacobi迭代公式。2012-5-1

n

j≠i

jkhh

4.3.2 4.3. 雅可比迭代法的矩阵表示设方程组 Ax = b 的系数矩阵A非奇异，且主对 的系数矩阵A非奇异， 则可将A 角元素 aii ≠ 0(i = 1,2, L , n) ,则可将A分裂成 0 0 a12 a13 L a1n a a11 0 0 a23 L a2n 21 a22 + + A = a31 a32 0 0 O O O an 1n ann an1 an2 L ann 1 0 0

记作2012-5-1

A=L+D+Ujkhh 9

则 Ax = b 等价于 ( L + D + U ) x = b 即 Dx = ( L + U ) x + b 因为 aii ≠ 0(i = 1,2, L, n) 这样便得到一个迭代公式

,则

x = D 1 ( L + U ) x + D 1b

x

( k +1)

= D (L + U )x 1

1

(k )(k )

+D b 1

1

= D ( A D) x + D b = ( I D 1 A ) x ( k ) + D 1b令 则有2012-5-1

B = ( I

D 1 A)

g = D 1b) + g (k = 0,1,2…)10

x

( k +1)

= Bx

(k )

jkhh 称为雅可比迭代公式, 称为雅可比迭代矩阵 称为雅可比迭代矩阵。 称为雅可比迭代公式 B称为雅可比迭代矩阵。

其中

0 a 21 B = ( I D 1 A) = a 22 M a n1 a nn

a12 a11 0 M an2 a nn

L L O L

a1n a11 a2n a 22 M 0

在例4.2中,由迭代公式写出雅可比迭代矩阵为 在例4.2中 4.23 ( k ) 3 1 ( k ) 25 ( k +1) = x1 0 8 x 2 4 x 3 + 2 8 8 4 ( k )4 1 (k ) 1 ( k +1) + B = I x D 1 = 11 1 2 A = x 011 x 3 + 3 11 11 1 1 ( k +1) ( x3 = x 1( k ) 6 x 2k ) 3 +3 0 2 4

2012-5-1

jkhh

12

12

雅可比迭代矩阵表示法， 雅可比迭代矩阵表示法，主要是用来讨论其收敛 实际计算中， 性，实际计算中，要用雅可比迭代法公式的分量 形式。 形式。即

( k +1) 1 ( ( ( x1 = ( a12 x2k ) a13 x3k ) L a1n xnk ) + b1 ) a11 ( k +1) 1 ( ( ( x2 = ( a21 x1 k ) a23 x3k ) L a2n xnk ) + b2 ) a22 LLLLLLLLLLLLLL 1 ( k +1) (k ) (k ) (k ) xn = a ( an1 x1 an 2 x2 L an n 1 xn 1 + bn ) nn (k=0,1,2,…)2012-5-1 jkhh 12

2012-5-1

4.3.3 4.3.3 4.3.3 4.3.3

输 入 a i j ,b i , 和 方 程 阶 数 n , ε ,M

雅 可 比(bi

1 k

∑aj =1 j≠i

n

ij

x j ) / a ii y i

迭 代 法 的 算 法 实 现k+ 1 k y i x i i = 1 ,2 ,… ,n n

i = 1, 2 , L , n

max x i y i < ε ?1≤ i ≤ n

y

n k = M ? y 输出迭代 失败标志jkhh

输出 y 1, y 2 ,…

yn13

4.4 高斯-塞德尔(Gauss-Seidel)迭代法 高斯 塞德尔( ) 塞德尔4.4.1 高斯 塞德尔迭代法的基本思想 高斯-塞德尔迭代法的基本思想 迭代法中， 在Jacobi迭代法中，每次迭代只用到前一次的迭 迭代法中 代值，若每次迭代充分利用当前最新的迭代值， 代值，若每次迭代充分利用当前最新的迭代值，即在 求 xi( k +1) 时用新分量( k x 1( k +1 ) , x 2 k +1 ) , L , x i( 1+1 )

代替

( k 就得到高斯-赛德尔迭代法 赛德尔迭代法。 旧分量 x1( k ) , x 2k ) ,L, xi( 1) , 就得到高斯 赛德尔迭代法。

其迭代法格式为： 其迭代法格式为：

xi( k +1)

i 1 1 = (bi ∑ aij x (jk +1) aii j =1

j = i +1

aij x (jk ) ) ∑14

n

=1,2,…, (i=1,2, ,n =1,2, 2012-5-1

k=0,1,2, ) =0,1,2,…) =0,1,2, jkhh

例4.3 用Gauss Seidel 迭代格式解方程组 T (1) x = (0.1250, 0.3750, 0.5000) 8 2 x2 + x3 0 x (x)1 = (0.2344 , = 1 .3031, 0.4925 ) T ( 3) 2 x 1= (102245, x 3 0=3059, 0.4939) T + 0. x 2 x . 4 ( T * ≈ x4 ) + x 5 x = 3 x x 0 3 1 = (2 .2250 , 0.3056, 0.4936) 精确要求为ε=0.005 精确要求为ε=0.005 ( 4) ( 3

) Gauss xi < 0.005, 解 Gaussxi Seidel 迭代格式为 (i = 1,2,3)

x = ( x x + 1) / 8 ( k +1) ( k +1) (k ) = ( 2 x1 + x 3 + 4) / 10 x2 ( k +1) ( k +1) ( k +1) = ( x1 + x2 3) / 5 x3(k ) 2 (k ) 3

( k +1) 1

迭代结果为： 取初始迭代向量 x ( 0) = (0 jkhh ,0) T ,迭代结果为： ,0 2012-5-1

4.4.2 Gauss—Seidel 迭代法的矩阵表示分裂成A 将A分裂成 =L+D+U,则 Ax = b 等价于 分裂成 ， )x ( L+D+U ) = b 于是,则高斯 塞德尔迭代过程 于是,则高斯—塞德尔迭代过程

Dx ( k +1) = Lx ( k +1) Ux ( k ) + b因为 D ≠ 0 ,所以 D + L = D ≠ 0 故

( D + L) x

( k +1)

= Ux

(k )

+b

x(k+1) = (D + L) 1Ux(k) + (D + L) 1b

令

B = ( D + L) 1U , g = ( D + L) 1 b( k +1)

则高斯-塞德尔迭代形式为： 则高斯-塞德尔迭代形式为：2012-5-1

x

= Bx

(k )

jkhh +g