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

第八线性方程组的迭代一、简单迭代法（Jacobi迭代

10x1x22x3x x 其准确解是：x*1.1,x*1.2,x* 解：把方程组改写成如下x1 0.1x20.2x3

x(0)x(0)

代入上面方程的右端，得x(1)0.72,x(1)0.83,x(1) 采用如下迭代公1x(k1) 0.1x(k)0.2x(k1

x(k

0.1x(k 0.2x(k

x(k1)0.2x(k)0.2x(k

直至

x(k1)x(k

计算结果如下所示，近似解向收敛，并以准确解为其极限，这就是Jacobi迭代k00001…………9下面就一般方法来叙述这一方

a12x2a1nxn设方程组a21x1a22x2a2nxn设方程组用矩阵表示

an2x2annxn假设aii

bijaij/ (i b/ i 方程组变x1 b12x2b13x3 b1nxn b bx x

bn,n1xn1若

b1n

B

2n

0

g1

g2aDa

g 3

nn

n容易BD1(DA)ID1A,gD1bxBxg 选取初始向x(0)x(0)x(0

代入方,x(0))Tn右端XBX,x(0))Tn,x(1))Tn x(1),x(1))Tn

再把x（1）代入方程右端此下去，迭代格式可以写

g,n当kx(k)收敛到x*,x*就是方程组的x*=x*则x*=（I－B）x*=（I－B）x*=g=D-即AX*算法输入矩阵。置33对nbin

aij

xxjix j1, i若||x-x(0)||<ε,输出x，否则转步骤若k<N,k+1=>k,x=>x(0),转步骤3；否则输出失败信息，停机Gauss-Seidel迭代从简单迭代法看到，用x(k)计算x(k+1)时，需要保留x(k)x(k+1)两个分量，实际上，假若我们采用(x(kx(kxk)T 入第一个方程，计算出x(k1)，然后用新计算出来的x(k 1 1

(x(k1),x(k),x(k)

代入第二个方程，计2出新x(k2

，再用(x(k1)x(k1x(k,x(k)

代入第三个，计

，如此等等，直到全部分量都用x(k 取代x(kx 程为：xx(k1) bx(k)bx(k) bx(k)

x(k1)bx(k bx(k)

x(k) 21

x(k1)bx(k1)

x(k

x(k1) n1

0

L

U

0bn1,n n 矩阵x(k1)Lx(k1)Ux(k) k0,1,2,因(IL)1存在，上面的x(k1)(IL)1Ux(k)(IL)11称B(I1

为Gauss-Seidel算法。 置

x

a1

x(0))/n n

11njxij

aijxj

aij

x(0))/

,i2,3,...,n xn(bn anjxj)/ann若||x-x(0)||<ε,输出x，否则转步骤若k<N,k+1=>k,x=>x(0),转步骤3；否则输出失败信息，停三、松驰法可以看成是Gauss-Seidel迭代法的加速，Seidel迭代是松驰法的特例，Gauss-Seidel迭代格x(k1)Lx(k1)Ux(k)现在令xx(k1)x(k)Lx(k1)Ux(k)gx(k于 x(k1)x(k)若在修正项Δx前面加上一个参数ωx(k1)x(k)x(1)x(k)(Lx(k1)Ux(k)ω称为松弛因子当ω＜1时，称低松驰法当ω=1时，显然就是Gauss-Seidel方法x(k (1)x(k)(Lx(k1)Ux(k g)因(IL)1存在，松弛x(k1)(IL)1((1)IU)x(k)(IL)1其中

B(IL)1((1)I叫做松驰法的迭代矩阵算法输入矩阵。置（3）计x1(1（3）计

xx1

(b1

aa )/1 xi(1

xxi

(bi

xj

aa )/ xn(1

anj

xj)/ann 若||x-x(0)||<ε,输出x，否则转步骤

若k<N,k+1=>k,x=>x(0),转步骤3；否则输出失败信息，停机前面介绍的几种迭代格式，可以统一表示成下面x(k1)Mx(k)其中，M是迭代矩阵，f对简单迭代法（Jacobi迭代法）来说M=B=I-D- f=g=D-对Gauss-Seidel迭代法M=B1=(I-L)- f=g=(I-L)-对松弛法来说M=Bω=(I-ωL)-1((1-ω)I+ f=ω(I-ωL)-1迭代法的收敛从任意选取的初始向量x0)出发，构造x(k，

10x1x22x3x x 3其准确解是x*1.1，x(*)1.2，x(* 例方程

x110x220x310x 5x 其准确解

x*x(*)x(*) x1

10x220x3把方程组改

取初始向量x(0)x(0)x(0) ，采用Jacobi迭代法，下 可以看出，向量序列发散，除了初始值取x(0)x(0)x(0) k00001--2-3---定理8.1对任何初始向量x(0)和常数项f，由迭代格x(k1)Mx(k

f,k产生的向量序列x(k)收敛且极限(M)其中，ρ(M)是矩阵M证明:先证必要性，假设x(k)收敛到 ，limx(k)k则x*Mx*则

x(k

x*表示第kx(k1)x(*)Mx(k

Mx*M(x(k)k 所以 M,k 或者写

k

M k

Mk0对于任意初始向量ε0，要,向量序列Mk收敛于零向00必须由定理6.4

limMkk(M)0再证充分性，假设(M)0

,则I-M非奇异，从而方程组k kM)x＝f有唯一解，现记为x*，于是 k k

Mk成立

limMk0limx(k)xk k

，定理证毕补充(A)max为矩阵A的谱补充向量范向量范数是n维Eucli空间中长度概念的推广，其任一xRn，按照一定规则确定一个（1）正定性：‖x‖≥0，当且仅当x=0，‖x‖=0三角不等式：对任意向量yRn,‖x+y‖‖x‖那么称该实数‖x‖补充矩阵范矩阵范数具有下面的性正定性：对任意非零矩阵A，‖A‖恒为正数，当且当矩阵为零时，其范数为零齐次性：对任意实数,有A＝ 三角不等式：对任意两个阶相同的矩阵A，BABA相容性：对同阶矩阵A,B

AB

A

中，常用的几种范nxn x xn

nx2x2x2x212ni2

x2)1/ maxx,

,,

x1x2,

分别是x的n个分以上三种范数形式都满足范数定义的三个在Rnn中，常用的几nA1maxn

(aij是矩阵A的元素1 2

（1是A的最大特征值

nn

下面用定理8.1来检验上面的几个10x1x22x3

x1

0.1x20.2x3例：x

迭代矩

00.10.2 M0.100.20.20.2矩阵M的特征方IM30.090.008计算得1

2,3

0.33)/也就是说(M1，故迭代收x110x220x3

例 10x1x25x3

x2

5x3

010

迭代矩

M10 5 0矩阵M的特征方

IM35450

(M)1课堂练

22A 1 2 1证明：（1）对于Jacobi迭代法，其迭 2M 1 0 0矩阵M的特征方

计算 即(M

，故Jacobi迭代收敛（2）对于Gauss-Seidel迭法 0

0 2L 0

U 1 0 0

0 2其迭代矩

M(IL)1U 1 2矩阵M的特征方

计算得1 (M

，故Gauss-Seidel迭代收敛，证毕判别收敛的几个常用 A12 A22其中A11,A22为方阵，则称A为不可约对角优若矩阵A＝(aij)nxn

(aij)(i1,,ni1,i,n且至少有一个i值，使上式中严格的不等号成立，则。定理8.3 若系数矩阵A具有严格对角优势，或者不可