逐次逼近法（2）.pdf

第六章逐次逼近法
§ 线性方程组的迭代法
§ 线性方程组的迭代法
在用直接法解线性方程组时要对系数矩阵不断变换
如果方程组的阶数很高,则运算量将会很大
并且大量占用计算机资源
因此对线性方程组
Ax = b --------(1)
要求找寻更经济、适用的数值解法
设A Î R n´n ,b Î R n , x Î R n
如果能将线性方程组(1)变换为
x = Bx + f --------(2)
其中B Î R n´n , f Î R n , x Î R n
显然,(1)式和(2)式同解, 我们称(1)(2)等价
对线性方程组(2),采用以下步骤:
取初始向量 x(0 ) ,代入(2),可得
x(1) = Bx (0 ) + f
依此类推
x( 2 ) = Bx ( 1) + f
M
x( k + 1) = Bx ( k ) + f --------(3)
(k = 0,1,2,L)
这种方式就称为迭代法,以上过程称为迭代过程
( k ) ¥
迭代法产生一个序列{x }0
如果其极限存在,即 lim x( k ) = x *
k ® ¥
则称迭代法收敛, 否则称为发散
一、简单迭代法(基本迭代法)
设线性方程组(1)的一般形式为
a x + a x + L + a x = b
ì 11 1 12 2 1n n 1
ï a x + a x + L + a x = b
í 21 1 22 2 2 n n 2
ï KKKK
ï
îan1 x1 + an 2 x2 + L + ann xn = bn
设
aii ¹ 0 (i = 1,2,L,n) ,则可从上式解出 xi
1
x1 = [b1 ­ (a12 x2 + L + a1n xn )]
a11
1
x2 = [b2 ­ (a21 x1 + a23 x3 + L + a2 n xn )]
a22
依此类推,线性方程组(1)可化为
n
1 1 n
x1 = (b1 ­ a1 j x j ) = x + (b ­ a x )
a å 1 1 å 1 j j
11 j =1 a11 j=1
j ¹1
ì n
1 1 n
x2 = (b2 ­ a2 j x j ) = x + (b ­ a x )
a å 2 2 å 2 j j
ï 22 j =1 a22 j=1
ï j ¹2
KKKK -----(4)
í 1 n 1 n
x = (b ­ a x ) = x + (b ­ a x )
i a i å ij j i a i å ij j
ï ii j = 1 ii j = 1
KKKj ¹Ki
ï n n
î 1 1
xn = (bn ­ anj x j ) = x + (b ­ a x )
a å n n å nj j
nn j =1 ann j =1
j ¹n
对(4)作迭代过程
n
( k +1) ( k ) 1 ( k )
xi = xi + (bi ­ å a ij x j ) --------(5)
a ii j =1
(i = 1,2,L,n;k = 0,1,2,L)
设 D = diag (a 11 , a 22 ,L , ann )
则(5)式转化为矩阵形式
x ( k + 1 ) = x ( k ) + D ­1 (b ­ Ax ( k ) )
x ( k + 1 ) = x ( k ) ­ D ­1 Ax ( k ) + D ­1b
x ( k + 1 ) = D ­1 ( D ­ A) x ( k ) + D ­1b --------(6)
令æ 0 0 L 0 ö
ç ÷ A的下三角部分
­ a 21 0 L 0
L = ç ÷ 的负矩阵
ç M O O M ÷
ç ÷
è ­ a n 1 ­ an 2 L 0 ø
æ 0 ­ a 12 L ­ a 1 n ö
ç ÷ A的上三角部分
0 0 L ­ a
U = ç 2 n ÷ 的负矩阵
ç M O O M ÷
ç ÷
è 0 0 L 0 ø
A = D ­ L ­ U
D ­ A = L + U
故迭代过程(6)化为
x ( k + 1 ) = D ­1 ( L + U )x ( k ) + D ­1b
­1 ­1
令 B J = D ( L + U ), f = D b ,于是
( k + 1 ) ( k )
x = B J x