高斯—塞德尔迭代法
(1.4)
即
x(k+1)=B0x(k)+f, (k=0,1,2,…)
0.000187 , 其中ε (10) x (10) x * .
x (10) (3.000032 , 1.999838 , 0.9998813 )T , ε (10)
一般地,由Ax b变形得到等价的x Bx f .
第 6章
解线性代数方程组的迭代法
§1 引言
考虑线性方程组
a11x1 a12 x2 a1n xn b1 a x a x a x b 21 1 22 2 2n n 2 an1x1 an2 x2 ann xn bn
§2
考虑线性方程组
基本迭代法
a11x1 a12 x2 a1n xn b1 a x a x a x b 21 1 22 2 2n n 2 an1x1 an2 x2 ann xn bn
也就是
Ax=b.
(2.1)
k
是解, 否则迭代法发散.
引进误差向量ε ( k ) x ( k ) x*,则由(1.6) (1.5)得 ε ( k 1) Bε ( k ) B k ε ( 0) .
收敛: lim ε ( k ) 0 lim B k 0.
k k
要研究B满足什么条件下B k 0( k ) .
( k 1) (k ) (k ) x1 (3 x2 2 x3 20) / 8, ( k 1) (k ) (k ) x ( 4 x x 33) / 11, 2 1 3 x ( k 1) ( 6 x ( k ) 3 x ( k ) 36) / 12. 1 2 3
也就是
AX=b.
(1.1)
低阶稠密的线性方程组用直接法(如高斯消去法和三 角分解法)。
大型稀疏非带状的线性方程组(n很大,且零元素很多. 如偏微方程数值解产生的线性方程组,n≥104)的求解 问题? 零元素多,适合用迭代法。 我们将介绍迭代法的一般理论及雅可比迭代法、高 斯—塞德尔迭代法,研究它们的收敛性。 例1 求解线性方程组
一、雅可比迭代法
设aii 0(i 1,2,, n), 从(2.1)的第i个方程中解出xi ,
1 x 1 a (b1 a12 x2 a1n xn ) 11 i 1 n 1 xi (bi aij x j aij x j ) aii j 1 j i 1 1 (bn an1 x1 an,n1 xn 1 ) xn a nn
进行矩阵分裂
A=M-N,
(2.2)
其中M为可选择的非奇异矩阵,且使Mx=d容易求解. 于是, Ax=b⇔x=M-1Nx+M-1b.
可得一阶定常迭代法:
取初始向量x ( 0), ( k 1) (k ) x Bx f , k 0,1,,
(2.3)
其中B M 1 N M 1 ( M A) I M 1 A, f M 1b.
就有
Dx
( k 1)
Lx
(k )
Ux
(k )
b
雅可比迭代法的矩阵表示形式为 x ( k 1) D 1 ( L U ) x ( k ) D 1b BJ x ( k ) f
精确解x*=(3,2,1)T.
改写(1.2)为
(1.3)
x1 1 (3 x2 2 x3 20), 8 1 x2 11 ( 4 x1 x3 33), x 1 ( 6 x 3 x 36). 1 2 3 12
或写为x=B0x+f,即
x1 0 x 4 2 11 6 x3 12
设有解x*,则 x* Bx * f (1.5)
又设任取初值x (0) , 则可构造迭代序列 x ( k 1) Bx ( k ) f (1.6)
定义1 (1)对于方程组x Bx f,用公式(1.6)逐步代入求 近似解的方法称为迭代法( 一阶定常迭代法) .
(2)若 lim x ( k )存在(记为x*),则称此迭代法收敛, 显然x *
3 8
0
3 12
2 8 1 11 0
20 x1 8 x 33 . 2 11 36 x3 12
任取初值,如x(0)=(0,0,0)T,代入(1.3)得到x(1)= (2.5,3,3)T. 反复迭代
0 a11 0 a12 a1n a 0 a22 0 21 ,U , L . D an1,n a a 0 a 0 n 1 n , n 1 nn
8 x1 3 x2 2 x3 20, 4 x1 11x2 x3 33, 6 x 3 x 12 x 36. 1 2 3 (1.2)
记为Ax=b,即
8 4 6 3 11 3 2 1 12 x1 20 x 33 . 2 x3 36
可以得到计算公式(雅可比迭代法) :对k=0,1,…, ( 0) ( 0) T x ( 0) ( x1 ,, xn ) , n ( k 1 ) xi (bi aij x (jk ) ) / aii , (i 1,, n) j 1 j i
采用矩阵分裂记号 A D L U, 其中