计算方法 线性方程组的迭代解法

计算方法线性方程组的迭代解法第一页，共五十页，编辑于2023年，星期五三、小结二、线性方程组的解法一、线性方程组有解的判定条件回顾《线性代数》中线性方程组的解法第二页，共五十页，编辑于2023年，星期五一、线性方程组有解的判定条件一、线性方程组有解的判定条件定理4n元线性方程组Ax=b(i)无解的充分必要条件是R(A)<R(A,b);(ii)有唯一解的充分必要条件是R(A)=R(A,b)=n;(iii)有无限多解的充分必要条件是R(A)=R(A,b)<n.当R(A)=R(B)=r<n时，n元线性方程组可由含有n-r个参数的解来表示，这是线性方程组的通解。第三页，共五十页，编辑于2023年，星期五定理定理5

线性方程组Ax=b有解的充分必要条件是R(A)=R(A,b).定理6n元齐次线性方程组Ax=0有非零解的充分必要条件是R(A)<n.定理7

矩阵方程AX=B有解的充分必要条件是R(A)=R(A,B).定理8

设AB=C，则R(C)min{R(A),R(B)}.定理9

矩阵方程AX=0只有零解的充分必要条件是R(A)=n第四页，共五十页，编辑于2023年，星期五小结有唯一解bAx=()()nBRAR==Û()()nBRAR<=Û有无穷多解.bAx=齐次线性方程组：系数矩阵化成行最简形矩阵，便可写出其通解；非齐次线性方程组：增广矩阵化成行阶梯形矩阵，便可判断其是否有解．若有解，化成行最简形矩阵，便可写出其通解；当R(A)=R(B)=r<n时，由于含有n-r个参数的解可表示线性方程组的任一解，因此称为线性方程组的通解。第五页，共五十页，编辑于2023年，星期五二、线性方程组的解法例1

求解齐次线性方程组解二、线性方程组的解法第六页，共五十页，编辑于2023年，星期五即得与原方程组同解的方程组第七页，共五十页，编辑于2023年，星期五由此即得方程组的通解是：第八页，共五十页，编辑于2023年，星期五例２求解非齐次线性方程组解对增广矩阵B进行初等变换，,3)(,2)(==BRAR由于，故方程组无解．第九页，共五十页，编辑于2023年，星期五例３求解非齐次方程组的通解解对增广矩阵B进行初等变换第十页，共五十页，编辑于2023年，星期五故方程组有解，且有第十一页，共五十页，编辑于2023年，星期五所以方程组的通解为k1k2第十二页，共五十页，编辑于2023年，星期五例４

解证对增广矩阵B进行初等变换，方程组的增广矩阵为第十三页，共五十页，编辑于2023年，星期五第十四页，共五十页，编辑于2023年，星期五由于原方程组等价于方程组由此得通解：第十五页，共五十页，编辑于2023年，星期五例５

设有线性方程组解第十六页，共五十页，编辑于2023年，星期五第十七页，共五十页，编辑于2023年，星期五其通解为第十八页，共五十页，编辑于2023年，星期五这时又分两种情形：第十九页，共五十页，编辑于2023年，星期五第二十页，共五十页，编辑于2023年，星期五此题也可以先求系数行列式。第二十一页，共五十页，编辑于2023年，星期五三、小结()()nBRAR==Û()()nBRAR<=Û有无穷多解.bAx=非齐次线性方程组齐次线性方程组三、小结第二十二页，共五十页，编辑于2023年，星期五引言

直接法是通过有限步运算后得到线性方程组的解,解线性方程组还有另一种解法，称为迭代法,它的基本思想是将线性方程组Ax=B化为

x=Bx+f再由此构造向量序列{x(k)}:x(k+1)=Bx(k)+f若{x(k)}收敛至某个向量x*,则可得向量x*就是所求方程组AX=b的准确解.

线性方程组的迭代法主要有Jocobi迭代法、Gauss-Seidel迭代法和超松弛(SOR)迭代法.第二十三页，共五十页，编辑于2023年，星期五若在求解过程中xkx*(k)，由xk+1=(xk)产生的迭代xk向x*的逼近，在数次迭代求解之后，由于机器跳动产生的xk值误差或是有效数字产生的舍入误差，都会在第k+1次迭代计算中自动弥补过来或逐步纠正过来。因此，在迭代求解过程中产生的各种误差是可以忽略的，即迭代求解无累积误差，实际上，xk只是解的一个近似，机器的舍入误差并不改变它的此性质。迭代法的特点

第二十四页，共五十页，编辑于2023年，星期五迭代过程中经常要遇到向量范数，矩阵范数以及序列极限的概念。为此，下面先介绍这方面的知识和有关概念。

第二十五页，共五十页，编辑于2023年，星期五几个基本概念及性质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||第二十六页，共五十页，编辑于2023年，星期五三种常用的向量范数：例：设x=(1,-4,0,2)T求它的向量范数第二十七页，共五十页，编辑于2023年，星期五三种常用的矩阵范数：例：设A，求它的矩阵范数第二十八页，共五十页，编辑于2023年，星期五矩阵范数的性质：（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||.谱半径：

第二十九页，共五十页，编辑于2023年，星期五5几个定理及定义

第三十页，共五十页，编辑于2023年，星期五

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

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

j=1,ji

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

a11

a12a13…a1n

a21a22a23…a2n

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

an1an3an4…ann-421例矩阵A=1-972-610ULD第三十一页，共五十页，编辑于2023年，星期五Jacobi迭代一：设有方程组

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

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

an1x1+an2x2+····+annxn=bn用矩阵表示：Ax=b（A为系数矩阵，非奇异；b为右端，x为解向量）第三十二页，共五十页，编辑于2023年，星期五假设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(L+U)P148,D=....

anngn

把方程组写成容易迭代的形式：第三十三页，共五十页，编辑于2023年，星期五Jacobi迭代公式第三十四页，共五十页，编辑于2023年，星期五Gauss-Seidel迭代法为了加快收敛速度，同时为了节省计算机的内存，我们作如下的改进：每算出一个分量的近似值，立即用到下一个分量的计算中去，即用迭代格式：这样所得的迭代法就称为Gauss-Seidel迭代法，也称为“异步迭代法”，简称为GS迭代法．利用Ax=b及A=L+D+U,其中D为对角矩阵,L,U分别为严格下，上三角矩阵．则有，GS迭代法的矩阵形式为:

第三十五页，共五十页，编辑于2023年，星期五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

第三十六页，共五十页，编辑于2023年，星期五收敛性及误差估计Jacobi迭代和GS迭代格式可表述为统一形式:对于其收敛性，我们有如下定理：定理１：对任意初始向量x(0)及任意右段向量g，由此产生的迭代向量序列{x(k)}收敛的充要条件是证明：必要性：设｛x(k)｝收敛，其极限为x*，则第三十七页，共五十页，编辑于2023年，星期五因上式对任意均成立，故Bk0(k),(B)<1

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

定理２：若||B||<1,则迭代法收敛.推论１若满足下列条件之一：（１）第三十八页，共五十页，编辑于2023年，星期五推论2：如果A为严格对角占优阵，则其Jacobi迭代和Seidel迭代对任何初始向量x(0)都收敛。推论3：如果A为对称正定阵，则其Seidel迭代对任何初始向量x(0)都收敛。

第三十九页，共五十页，编辑于2023年，星期五三．例题及求解例：用迭代法解方程组AX=b,其中[已知该方程的解为]

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

第四十页，共五十页，编辑于2023年，星期五第四十一页，共五十页，编辑于2023年，星期五表１第四十二页，共五十页，编辑于2023年，星期五第四十三页，共五十页，编辑于2023年，星期五表2第四十四页，共五十页，编辑于