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

第四章 解线性方程组的迭代法 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) …… 此处隐藏：3524字，全部文档内容请下载后查看。喜欢就下载吧 ……