数值方法线性方程组的迭代法

用迭代法解线性方程组Jacoai迭代和Seidel迭代因为收敛速度较慢，已经越来越不适应该前信息时代人们对计算速度和精度要求，所以在实际应用中使用得并不多。不过，他们表达了迭代法最基本思想，是学习其它迭代法基础。第1页引言直接法是经过有限步运算后得到线性方程组解,解线性方程组还有另一个解法，称为迭代法,它基本思想是将线性方程组Ax=b化为

x=Bx+f

再由此结构向量序列{x(k)}:

x(k+1)=Bx(k)+f若{x(k)}收敛至某个向量x*,则可得向量x*就是所求方程组AX=b准确解.线性方程组迭代法主要有Jocobi迭代法、Seidel迭代法和超松弛(Sor)迭代法.第2页迭代法特点

若在求解过程中xk

x*(k)，由xk+1=(xk)产生迭代xk向x*迫近，在数次迭代求解之后，因为机器跳动产生xk值误差或是有效数字产生舍入误差，都会在第k+1次迭代计算中自动填补过来或逐步纠正过来。所以，在迭代求解过程中产生各种误差是能够忽略，即迭代求解无累积误差，实际上，xk只是解一个近似，机器舍入误差并不改变它此性质。

迭代过程中经常要碰到向量范数，矩阵范数以及序列极限概念。为此，下面先介绍这方面知识和相关概念。

单击此处即可第3页几个基本概念及性质1.向量范数：

对任一向量X，按一定规则确定一个实数与其相对应，该实数记为||X||，若||X||满足下面三个性质：（1）||X||

0，||X||=0当且仅当X=0。（2）对任意实数

，||

X||=|

|||X||。（3）对任意向量YRn，||X+Y||

||X||+||Y||。则称该实数||X||为向量X范数2.矩阵范数：设A是NN阶矩阵，定义||A||=Max

（||AX||/||X||）=Max||AX||x0,xRn

||x||=1,xRn

为矩阵A(算子）范数。

||Ax||

||A||||x||第4页三种惯用向量范数：例：设x=(1,-4,0,2)T求它向量范数第5页三种惯用矩阵范数：例：设A，求它矩阵范数第6页矩阵范数性质：（1）对任意非零矩阵A,有||A||恒为正数，当且仅当A=0，||A||=0.（2）||aA||=|a|||A||（a为任意实数）（3）对于任意两个阶相同矩阵A，B恒有||A+B||

||A||+||B||.（4）对于与矩阵A有相同维数向量X，恒有||AX||

||A||

||X||.（5）对于同阶矩阵A，B恒有||AB||

.||A||

||B||谱半径：

设nn阶矩阵A特征值为

i(i=1,2,3……n),则称

(A)=MAX|

i|

为矩阵A谱半径.

1in矩阵范数与谱半径之间关系为:

(A)

||A||.单击此处试做例题第7页5几个定理及定义设{x(k)}为Rn中向量序列,x(*)为Rn中向量对矩阵也有类似结论

下一页第8页

假如矩阵A=(aij)满足 n|aii|>

|aij|i=1,2,……n,

j=1,ji

则称方阵A是严格(行)对角占优.

a11a12a13…a1n

a21

a22

a23…a2n

A=……………=L+D+U

an1an3an4…ann-421例矩阵A=1-972-610ULD第9页Jacobi迭代一：设有方程组

a11x1+a12x2+····+a1nxn=b1a21x1+a22x2+····+a2nxn=b2

.....................

an1x1+an2x2+····+annxn=bn用矩阵表示：Ax=b（A为系数矩阵，非奇异；b为右端，x为解向量）}

上一页第10页假设aii0令cij=-aij/aii(ij)

gi=bi/aij,i=1,2,3,n

则

x1(k+1)=c12x2(k)+c13x3(k)++c1nxn(k)+g1

x2(k+1)=c21x1(k)+c23x3(k)++c2nxn(k)+g2。。。。。。。。。。。。。。。。。。。。。。。。。。。。

xn(k+1)=cn1x1(k)+cn2x2(k)++cn(n-1)xn-1(k)

+gn

Jacobi迭代格式若令

0c12c13…c1n

x1c210c23…c2n

x2BJ=……………x=..cn1cn3cn4…0xn

a11

g1

a22

g=g2易看出：BJ=D-1(D-A)=I-D-1,D=....

anngn

把方程组写成轻易迭代形式：{第11页Jacobi迭代公式第12页Seidel迭代法为了加紧收敛速度，同时为了节约计算机内存，我们作以下改进：每算出一个分量近似值，马上用到下一个分量计算中去，即用迭代格式：这么所得迭代法就称为Gauss-Seidel迭代法，也称为“异步迭代法”，简称为GS迭代法．利用Ax=b及A=L+D+U,其中D为对角矩阵,L,U分别为严格下，上三角矩阵．则有，GS迭代法矩阵形式为:

第13页Seidel迭代法详细形式Seidel迭代格式x1(k+1)=c12x2(k)+c13x3(k)++c1nxn(k)+g1

x2(k+1)=c21x1(k+1)+c23x3(k)++c2nxn(k)+g2。。。。。。。。。。。。。。。。。。。。。。。。。。。。

xn(k+1)=cn1x1(k+1)+cn2x2(k+1)++cn(n-1)xn-1(k+1)

+gn

假设aii0令cij=-aij/aii(ij)

gi=bi/aij,i=1,2,3,n

第14页．收敛性及误差预计Jacobi迭代和GS迭代格式可表述为统一形式:对于其收敛性，我们有以下定理：定理１：对任意初始向量x(0)及任意右段向量g，由此产生迭代向量序列{x(k)}收敛充要条件是证实：必要性：设｛x(k)｝收敛，其极限为x*，则第15页因上式对任意均成立，故Bk0(k

),(B)<1

充分性：设

(B)<1,则I－B为非奇异阵,且=0,所以有唯一解,记为则

定理２：若||B||<1,则迭代法收敛.推论１若满足以下条件之一：（１）第16页(2)(3)

则迭代法收敛。

推论2：假如A为严格对角占优阵，则其Jacobi迭代和Seidel迭代对任何初始向量x(0)都收敛。

推论3：假如A为对称正定阵，则其Seidel迭代对任何初始向量x(0)都收敛。

第17页下面给出

迭代法误差预计定理３：若，则对迭代法有实用第18页证实:第19页三．例题及求解例：用迭代法解方程组AX=b,其中[已知该方程解为]

解：本题分别用简单迭代法（Jacobi迭代法）和GS迭代法来解(1)简单迭代法

第20页表１第21页第22页表2返回第23页四.相关程序设计原始数据（A,b)可用一个二维数组存放，也可将A用一个二维数组，b用一个一维数组分别存放，存放需要一个一维数组．程序中应方便地对迭代方法和终止条件选择以及对初始向量和值设置．在迭代过程中，为反应迭代情况，可设置一些中间数据输出，如迭带次数，迭代向量，迭代残向量等．当然不需要每迭代一次都作输出．这可作为收敛情况或不收敛情况分析．作为不收敛判定，可设置一个大整数，当迭带次数超出该数时作为不收敛处理．GS迭代法计算公式为：第24页开始TFTFT第25页下面给出一个应用BASIC程序解方程组例子：程序以下运行：5REMGAUSS-SELDEL10INPUTN,E,M20DIMA(N,N),B(N),X(N),Y(N)30FORI=1,TON40FORJ=1,TON50READA(I,J)第26页

60NEXTJ70READB(I)80NEXTI90FORI=1TON100READX(I)110NEXTI120FORK=1TOM130R=0140FORI=1TON150S=0160T=X(I)170FORJ=1TON

第27页180IFJ=1THEN210190P=A(I,J)*X(S)200S=STP210NEXTJ220X(I)=(B(I)-S)/A(I,I)230IFABS(X(I0-T)>RTHENR=ABS(S(I)-T)240NEXTI250PRINTK;”-”;:FORI=1TON:PRINT“X(‘;I;”)=“;INT((X(I)*100000+0.5)/100000;:NEXTI:PRINT255IFR<1THEN280260NEXTK..:第28页270PRINT“DREDAISHBAI”280 END290 DATA10,-1,-2,7.2300 DATA-1,10,-2,8.3310 DATA-1,-1,5,4.2320 DATA0,0,0 RUN ?3,10