第3章 线性代数方程组的解法

第三章线性代数方程组的解法引言高斯消去法高斯列主元消去法矩阵分解法向量和矩阵范数解线性代数方程组的迭代法第一节引言

快速、高效地求解线性方程组是数值线性代数研究中的核心问题，也是目前科学计算中的重大研究课题之一。各种各样的科学和工程问题，往往最终都要归结为求解一个线性方程组。线性方程组的数值解法有：直接法和迭代法。直接法：在假定没有舍入误差的情况下，经过有限次运算可以求得方程组的精确解；(快速有效)迭代法：从一个初始向量出发，按照一定的迭代格式，构造出一个趋向于真解的无穷序列(节省内存)。高斯消去法是解线性方程组最常用的方法之一，它的基本思想是通过逐步消元，把方程组化为系数矩阵为三角形矩阵的同解方程组，然后用回代法解此三角形方程组可得方程组的解。第二节高斯消去法我们知道，下面有3种方程的解我们可以直接求出：①②上三角③下三角消元法就是对方程组做些等价的变换，变为我们已知的3种类型之一，而后求根。对方程组，作如下的变换，解不变①交换两个方程的次序②一个方程的两边同时乘以一个非0的数③一个方程的两边同时乘以一个非0数，加到另一个方程因此，对应的对增广矩阵(A,b)，作如下的变换，解不变。①交换矩阵的两行②某一行乘以一个非0的数③某一行乘以一个非0数，加到另一行举例（一）解：例：直接法解线性方程组高斯消去法的主要思路：将系数矩阵A经过消元过程化为上三角矩阵，然后回代求解。考虑一般n阶线性方程组：矩阵形式=

即:相当于第i个方程-第一个方程×数→新的第i方程同解！第一方程不动！

一、Gauss消去法计算过程第一步消元：消元：上述消元过程除第一个方程不变以外,第2—第n个方程全消去了变量1，而系数和常数项全得到新值：每步消元，先计算系数，然后计算矩阵新元素及右端项系数矩阵与常数项：讨论第K次消元，得到消元公式第K次消元目的：aik(k)=0(i=k+1….n),设akk(k)≠0,为使aik(k)=0(i=k+1….n）选取适当因子M使aik(k)-Makk(k)=0可求出

M=aik(k)/akk(k)第i个方程其他系数的变化为（Ri-M.Rk)aij(k+1)=aij(k)–M.akj(k)(i=k+1….n,j=k+1…..n+1)所以，第K次消元时（后）（K=1….n-1)消元因子：

M=aik(k)/akk(k)(i=k+1,n）系数变化：

①aij(k+1)=aij(k)

（i≤k)

②aij(k+1)=aij(k)-M.akj(k)(i>k,j=k+1…n+1)最后得到：[A(n)|b(n)](n-1次消元后）其增广矩阵为：回代：

Xn=ann+1(n)/ann(n)

编程时，为节省内存将Xn放在ann+1(n)

同理Xi放在

ain+1(i)

第i次回代公式（i=n-1…..1)Xi(即ain+1(i))=(ain+1(i)-）/aii(i)二、算法描述1、消元对k=1…..n-1

消元因子：

C=aik(k)/akk(k)

(i=k+1….n）系数变化：

①aij(k+1)=aij(k)

（i≤k)②aij(k+1)=aij(k)-C.akj(k)

(i>k,j=k+1,…,n+1)2、回代第i次回代公式（

i=n,n-1….1)Xi(即ain+1(i))=(ain+1(i)-）/aii(i)

三、特点1、优点：公式简明，容易程序化2、缺点：第k次消元时，必须

akk

≠0,且当

akk

0时，误差很大，数值不稳定(p35N-S图）第三节GAUSS列主元消去法一、高斯消去法的缺点在简单的高斯消去法中，如果遇到

a（k）kk=0,则消去过程就会中断，如果a（k）kk≠0，但其绝对值很小时，在高斯消去法中，因为M=aik(k)/akk(k)

，所以不是因为M数值过大，就是舍入误差过大，与实际的解相差很远。

零主元或小主元问题例如：求解下列方程组此方程组的准确解为：x1=10.00；x2=1.00下面采用高斯消去法解方程组（取四位有效数字），消元后得-1043x2=-1044，则x2=1.001.

将x2代入第一个方程中，得x1=-9.713显而易见，利用高斯消去法得到的结果与精确解相差太悬殊了从求解过程可以看出，在第一种解法中，乘以的系数为m=5.291/0.0030如果将两个方程互换，再采用高斯消去法解方程组消元后得59.14x2=59.14，则x2=1.000

将x2代入第一个方程中，得x1=10.000此时，利用高斯消去法得到的结果与精确解一致。从求解过程可以看出，在第一种解法中，乘以的系数为m=5.291/0.0030，第二种解法中，乘以的系数为m=0.0030/5.291。我们希望m尽量小，希望主元尽可能大，就有了列主元消去法（按列）。二、列主元消去法

1、选主元再消元在每一步消元之前，即第k次消元时，在第k列上选取绝对值最大的元素为主元素

ai0k(最大值在i0行上）

若|ai0k|<εp中断否则若i0≠k

将i0和k行互换

再按高斯消去法消元

2、回代不改变方程组的解，同时又有效地克服了Gauss消元的缺陷

三、算法描述1、选主元（对

k=1…..n-1)(1)p(主元素）0(2)对

i=k……n做若|aik|>p则p|aik|i0i2、换行

a

kj<-->ai0j(j=k……n)3、消元：同Gausss4、回代:同Gausss

（p175)

取四位有效数字计算。解②中-18为主元,交换②和①得

①②③①②③例1用列主元素消去法解方程组

②+①×12/18,③+①×1/18得

①②③第二列消元时,主元为1.167,交换方程②和③得①②③③+②×1/1.167得①②③回代求得

x1=1.000,x2=2.000,x3=3.001方程组的实际解

x1=1,x2=2,x3=3四、高斯―约当消去法

前面所述的消去法均要进行两个过程,即消元过程和回代过程。但对消元过程稍加改变可以把方程组化为对角形

此时求解就不要回代了。这种无回代过程的主元素消去法称为高斯―约当(Jordan)消去法。特别是方程组还可化为

显然等号右端即为方程组的解。对于n阶线性方程组,其增广矩阵为首先把主元素(按列选主元或全选主元)调换到主对角线上,并化为1,再将主元素所在列的其它元素消为0练习：1、用GAUSS消去法解方程组

2x1+x2+x3=4x1+3x2+2x3=6x1+2x2+2x3=52、用GAUSS列主元消去法解方程组

2x1+x2+2x3=55x1-x2+x3=8x1-3x2-4x3=-43、用GAUSS列主元消去法解方程组

-3x1+2x2+6x3=410x1-7x2=75x1-x2+5x3=6第四节矩阵分解法（直接法）复习、基本概念1、顺序主子式（P40定义1）

n*n阶矩阵A的左上角P*P阶子矩阵的行列式

P=称为A的P阶顺序主子式2、正定矩阵特征值都大于0(或各阶顺序主子式都大于0)的实矩阵(如何求特征值？）

解特征多项式|λE-A|=03.矩阵相乘公式Cm×n=Am×kB

k×nA的第i行

(ai1ai2….aik)B的第j列（b1jb2j……bkj)cij=(ai1b1j+ai2b2j+….aikbkj)=

思考:下面矩阵左乘的结果?设li1=ai1(1)/a11(1)==结果为:M=------为第2次消元后的结果?2第四节矩阵分解法（直接法）一、三角分解法从矩阵的初等变换来看,前面讲的高斯消去法和列主元消去法来解方程，实际是通过一系列的初等变换将方程组的系数矩阵A化为三角矩阵，其每一步的消元过程相当于对增广矩阵(A,b)作一次初等变换。下面将上述这种方程组的消去过程通过矩阵分解来实现。在消去第一列中的ai1(i=2,3,…,n)时,左乘的矩阵为令：在消去第一列中的ai1(i=2,3,…,n)时,左乘的矩阵为2在消去第二列中的ai2(i=2,3,…,n)时,左乘的矩阵为这样就把A化为一个上三角矩阵U，即根据得A=LU称为矩阵A的LU分解或三角分解。把A分解为一个单位下三角阵L和一个上三角阵的乘积，称为A的LU分解，也叫Doolittle（杜利特尔）分解。一般的，如果能把系数矩阵分解为A=LU，其中L为单位下三角阵，U为非奇异上三角阵，那么方程Ax=b可化为

LUx=b

令Ux=y，则有Ly=b，这样原方程组转化为先解下三角方程组Ly=b，求出y，再解上三角方程组Ux=y求出x。即:a11a12….a1n1

u11u12..u1i…u1na21a22……a2nl211

u22

.u2i…u2n……………ar1ar2……a

rn

lr1lr2……1(lrr)uii..uin…………..…………..…an1an2…annln1ln2……...1

unn

=

正如高斯消去法中的消元过程不一定能进行到底那样，一个矩阵也不一定能进行LU分解。由下面讨论能进行LU分解的条件。定理1：(p40)nxn阶矩阵有唯一LU分解的充分必要条件是矩阵A的各阶顺序主子式都不等于0。证明略。我们关心的是如何进行LU分解，即如何把LU求出来。设A的各阶顺序主子式都不等于0，并设L=(lij),U=(uij)。由A=LU知：a11a12…a1na21a22…a2n……ar1ar2…arn……an1an2…annlr1

lr2

lr3U=先计算U的第一行，L的第一列元素，有矩阵乘法知

a1j=u1j(j=1,2,…,n)

ai1=li1u11(i=2,3,…n)得到

u1j=a1j(j=1,2,…,n)

li1=ai1/u11(i=2,3,…,n)类似的由A的第二（r）行元素，计算U的第二（r）行，由A的第二（r）列元素计算L的第二（r）列元素。一般的计算U的第r行，L的第r列元素的方法设计考虑A的第r行，第r列元素，由矩阵乘法知：由得到由得到按公式将A进行LU分解后，此时AX=b

LUx=b令Ux=y，则Ly=b，方程组Ax=b化为下列两个等价的方程组

Ly=b

Ux=y

y1b1y2=b2…...

yn

bn

y1=b1l21y1+y2=b2

li1y1+li2y2+….Lii-1yi-1+yi=bi……….ln1y1+ln2y2+………+yn=bn可以计算yi(下三角方程组)再带入UX=Y………x1y1x2=y2…………xn

yn同理，可求：xn=yn/unn=a11=u11a12=u12

u11=a11u12=a12a21=l21u11a22=l21u12+u22

l21=a21/u11u22=a22-l21u12

注意计算顺序u11u12u13……….u1nl21l31….ln1第一步计算u22u23………u2nl32….ln2第二步计算….

unn第n步计算LU计算的紧凑格式例3用杜利特尔分解方法求解下列方程组的解：2-11-3647/3-8解：利用上面3-19计算公式

可求得

再由Ly=b求出y后根据Ux=y最后求得原方程组的解为从上面的讨论我们可以看到,用LU分解方法解线性方程组,就是将其化为依次求解下面两个三角形方程组:Ly=b

Ux=y显然求解Ly=b的过程即为消元过程,它只不过是对

LUx=b

两端左乘L-1而得,即

Ux=L-1b=y

而求解Ux=y的过程即为回代过程。因此三角分解方法实质上还是高斯消去法。二、解对称正定的平方根法在工程计算中，常遇到方程组的系数矩阵是对称正定矩阵，由于对称正定的性质，它的三角分解的形式有着特殊性，因此，其计算量以及在计算机中的存储量可大大减少。二、解对称正定的平方根法定理2：若n阶方阵A对称正定，则存在唯一的对角元素为正的下三角阵L，使A=LLT(Cholesky分解）证明略a11a12…a1na21a22…a2n……ar1ar2…arn……an1an2…ann由a11=l211，得l11=考虑第一行元素，a1j=l11lj1,j=2,3,…n，得lj1=a1j/l11这样就计算出L的第一列，LT的第一行考虑第二列的下三角元素，由a22=l221+l222，得到由ai2=li1l21+li2l22,得到li2=（ai2-li1l21）/l22,i=3,…,n这样就计算出L的第二列，LT的第二行一般的由上面的推导可求出按行计算公式:对i=1,2,…n将A分解后，即A=LLT，代入Ax=b，得

LLTx=b将其化为下列与原方程组等价的两个方程组

Ly=bLTx=y然后回代，求出y与x。此时AX=bLLTX=b令LTX=Y

则AX=b等价于LY=b

LTX=Y=由

LY=b得l11y1=b1l21y1+l22y2=b2………………..li1y1+li2y2+…liiyi=bi…………………ln1y1+li2y2+…lnnyn

=bn解之得:yi=(bi-)/lii(i=1,...n)

l11x1+l21x2+….ln1xn=y1l22x2+….ln2xn=y2………………..

liixi+…lnixn=yi…………………lnnxn

=yn解之得：xi=(yi-)/lii(i=n,....,1)

再代入LTX=Y

例1：用平方根法求

4x1+2x2+4x3=42x1+10x2+5x3=114x1+5x2+21x3=-9

例1：用平方根法求

4x1+2x2+4x3=42x1+10x2+5x3=114x1+5x2+21x3=-9解:系数矩阵:424l11

l

11

l21

l312105=l21

l22

l

22

l324521l31

l32

l33

l

33

例2用LLT分解方法解线性方程组

取四位小数计算。解用公式(3―26)依次计算由式(3―27)求得

y1≈1.3416,y2≈-0.4474,y3≈1.7320再由式(3―27)求得原方程组的解为

x1≈0.9993,x2≈0.9989,x3≈0.9999实际上,原方程组的准确解为

x1=1,x2=1,x3=1例3：已知方程组Ax=f,其中

2-1b0A=-12af=1b-120试问参数a和b满足什么条件时，可选用平方根法求解该方程组。三、解三对角阵的追赶法解三对角方程组的追赶法（Thomas算法）基本思想：

AX=F=若A为对角占优即

|b1|>|c1||bi|≥|ai|+|ci|i=2,,..n-1ai.ci≠0|bn|>|an|则A可以写成：A=LU即

对比法求得pi与qi的递推公式：p1=a1

a1=p1*1q1=c1/p1c1=p1*q1对于i=2,3,…n行计算pi=ai-bi*qi-1

ai=bi*qi-1+piqi=ci/piAX=F即LUX=F可写成由

LY=F知

=由矩阵乘法可求将（3.29)代入可得

i=2,...n求出yi后再由

UX=Y即

=

同样根据矩阵乘法求

(3.32)i=n-1,..1

例（大纲

p13)取b=0,a=-1,用追赶法解方程组A=LUAX=fLUX=fLY=fUX=Y=第五节向量和矩阵的范数在数值分析中，经常要分析解向量的误差，比较误差向量的“大小”，那么怎么定义向量的大小，并进行比较呢？这可以对向量按一定的法则取一个非负实数，作为它的“长度”，然后以其长度为标准进行比较，这就是数值方法中广泛应用的范数的概念。第五节向量和矩阵的范数一、向量的范数定义1:若向量x∈Rn

即x=(x1,x2.....xn)T,定义某个实数值函数N(X)=||X||，若满足以下三个条件：

(1)||X||≥0当且仅当X=0时，||X||=0正定性

(2)||C.X||=|C|.||X||C为任意常数齐次性

(3)||X+Y||≤||X||+||Y||三角不等式则称N(X)是R上的一个向量范数或模。例1:向量空间

x=(x1,x2,x3)T,

（1）|x1|+|2x2|+|x3|是不是一种向量范数？（2）|x1+3x2|+|x3|是不是一种向量范数？

2、常用的向量范数1-范数||X||1=2-范数||X||2=()1/2∞-范数||X||∞=max|xi|

1<=i<=np-范数||X||p=()1/p例2

已知向量

X=（1,-2,3)T求||X||1

，||X||2

，||X||∞要求:会计算向量的范数3、向量范数的性质设x,y∈Rn则

|||x||-||y|||<=||x-y||

证：||x||=||(x-y)+y||<=||x-y||+||y||所以

||x||-||y||<=||x-y||同理||y||-||x||<=||y-x||=||x-y||也即：||x||-||y||>=-||x-y||所以：|||x||-||y|||<=||x-y||（2）设||x||α与||x||β是Rn上任意两种向量范数，则存在正常数m和M使一切

x∈Rn

有m||x||β<=||x||α<=M||x||β如：||X||∞<=||X||1<=n||X||∞

说明：向量范数的等价性，说明x的一切范数都是等价的。一种范数对应一种长度，一种长度对应一种收敛性，等价性表明，当||x||α趋于0时，||x||β也趋于0，只不过趋于0的速度不一样，即收敛的速度不一样。但收敛性是一样的。定义3:设向量序列X(K)=(x1(K),x2(K).....xn

(K))T

和向量X*=(x1*,x2*...xn*)T

对任意i(i=1,2...n)有则称向量序列{X(K)}收敛于X*

记做说明：如果向量的每一个分量都收敛，则向量收敛于X*。定理3：对Rn上的任一种向量范数||.||，向量序列{x(k)}收敛于向量x*的充要条件是：||x(k)–x*||0（当k->∞时)x(k)–x*=（x1(k)-x1*,x2(k)-x2*,xn(k)-xn*）T

xi(k)->xi*xi(k)-xi*->0||x(k)–x*||∞

0由范数的等价性知，存在M，m>0使得m||x(k)–x*||∞

≤||x(k)–x*||≤M||x(k)–x*||∞说明：看向量x(k)

是否收敛于向量x*，就要看||x(k)–x*||是否收敛于0。二、矩阵的范数1、定义4若矩阵A∈Rn×n

的某个非负实值函数N(A)=||A||满足

(1)||A||≥0当且仅当A=0时，||A||=0正定性

(2)||C.A||=|C|.||A||C为任意常数齐次性

(3)||A+B||≤||A||+||B||三角不等式

(4)||AB||≤||A||||B||相容性则称N(A)是Rn×n

上的一个矩阵范数或模。

在数值计算中,为了进行某种估计,常常要比较不同向量的范数,向量有时以Ax的形式出现,其中A为n×n阶矩阵

A=(aij)n×n

这就需要寻求‖x‖和‖Ax‖之间的某种关系定义5设X∈Rn

，A∈Rn×n，且给出一种向量范数||X||，则称为矩阵A的算子范数。说明:||AX||γ≤||A||γ.||X||γ常用公式由向量范数诱导出的矩阵范数，即矩阵范数和向量范数的关系。A的行范数||A||∞=max1<=i<=n2、常用的矩阵范数A的列范数||A||1=max1<=j<=nA的2范数||A||2=

A的p范数||A||p=()1/2例3已知

A=-1302计算A的1，2，∞范数要求:会计算矩阵的范数定义6谱半径设A∈Rn×n

的特征值为λi(i=1,2...n)称ρ(A)=max|λi|为A的谱半径

1≤i≤n

那么,谱半径和范数之间是什么关系呢?定理4：特征值上界定理设

A∈Rn×n,则ρ(A)≤||A||，即A的谱半径不超过A的任何一种范数。证明：设λ是A的任一特征值，x为相应的特征向量，则

AX=λx|λ|||x||=||λx||=||AX||<=||A||||X||所以|λ|〈=||A||也即ρ(A)〈=||A||结论：任何一种特征值都小于范数，最大的特征值是谱半径。

三、方程组的性态和条件数方程组的系数和右端项都或多或少的带有误差，这种误差有时会使方程组的解面目全非，有时却影响不大。这涉及到方程组解的敏感程度。首先来考察一个例子：(p49例11)Ax=b12x17精确解为12-1x2=-1312x17A(x+δx)=b+δb2-1.0009x2=-1.003此时方程组的解为：y10.99988

y2=3.00006

p49(例10)

2x1+6x2=82x1+6.00001x2=8.00001其解为：x1=1x2=12x1+6x2=82x1+5.9999x2=8.00002其解为：x1=10x2=-2说明：有的方程对扰动敏感，有的不敏感。定义6若矩阵A或常数项的微小变化，引起方程组AX=b解的巨大变化，则称此方程组为“病态”方程组，矩阵A称为“病态”矩阵，否则，称此方程组为“良态”方程组，矩阵A称为“良态”矩阵注意：矩阵“病态”的性质是矩阵本身的特性，我们希望找出刻画矩阵病态本身的量。讨论

A,b有扰动时（δA，δb),对解的相对误差的影响，分三种情况讨论：（1）b有扰动δb时的情况（b->b+δb

）此时，解为

X+δX,则有A(X+δX)=b+δb

据AX=b得AδX=δbδX=A-1δb||δX||<=||A-1||||δb||①

由b=AX知||b||<=||A||||X||

则②

由①，②可得2）设b精确，A有扰动

δA（A->A+δA

）

此时(A+δA)(X+δX)=b

由AX=b知

(A+δA)δX=-δAX

即

AδX=-δA(X+δX)||δX||=||A-1δA(X+δX)||<=||A-1||||δA||(||X||+||δX||)整理得(1-||A-1||||δA||)||δX||<=||A-1||||δA||||X||当||A-1||||δA||<1时有：变形为：3)A,b都有扰动

δA，δb,解为X+δX

由此我们可知：A或b有扰动时,解的相对误差的上界随||A-1||||A||的增大而增大，也即||A-1||||A||标志着方程组解的敏感程度。并且完全是由系数矩阵A的特性所决定的。定义7设A为非奇异阵，称Cond(A)=||A-1||||A||为矩阵A的条件数由此可知，方程组AX=b的病态程度可由系数矩阵A的条件数Cond(A)来刻画，其值越大，方程组的病态就越严重。常用的条件数有：

(1)Cond(A)∞=||A-1||∞||A||∞(2)Cond(A)2=||A-1||2||A||2=当A为对称正定时Cond(A)2=|λ1|/|λn|,其中

λ1，λn为矩阵A的最大和最小特征值例:求矩阵A的条件数逆阵的求法A-1=A*/|A|A*为A的伴随矩阵判断以为系数矩阵的方程组是病态还是良态。1、常用的向量范数1-范数||X||1=2-范数||X||2=()1/2∞-范数||X||∞=max|xi|

1<=i<=n复习A的行范数||A||∞=max

1<=i<=n2、常用的矩阵范数:A的列范数||A||1=max

1<=j<=n

A的2范数||A||2=

A的F范数||A||F=()1/23、谱半径

设

A∈Rn×n

的特征值为λi(i=1,2...n)称ρ(A)=max|λi|为A的谱半径

1≤i≤n4、特征值上界定理设A∈Rn×n,则ρ(A)≤||A||

，即A的谱半径不超过A的任何一种范数5、条件数设

A为非奇异阵，称Cond(A)=||A-1||||A||为矩阵A的条件数---------方程组AX=b的病态程度可由系数矩阵A的条件数Cond(A)来刻画，其值越大，方程组的病态就越严重常用的条件数有：

(1)Cond(A)∞=||A-1||∞||A||∞(2)Cond(A)2=||A-1||2||A||2

第六节解线性方程组的迭代法解：从三个方程中分别分离出x1,x2,x3,即：一、雅可比(Jacobi)迭代(简单迭代)法及其收敛条件回忆非线性方程求根的迭代法？下面用一个具体的例子说明雅可比迭代的基本思想。例：用简单迭代法解方程组：这样就构成了

X=CX+d

的形式用任意一组近似值（x1(k),x2(k),x3(k)）代入上式右端，可得到一组新的近似值（迭代格式）：取初始值X(0)=（0，0，0）T可得：方程的精确解为：x1=1.1x2=1.2x3=1.3可见，当迭代次数增加时，迭代结果越来越逼近其精确解，这时我们认为迭代格式是收敛的。x1

(k+1)=-x2(k)+5x3(k)-4.2x2

(k+1)=10x2

(k)-2x3

(k)-7.2x3(k+1)=0.5x1(k)+5x2(k)-8.3例如：方程组依次从第三、第一及第二个方程分离出x1,x2,x3？但是对于任意线性方程组，按各种方式建立的简单迭代格式是否一定收敛？回答是否定的。迭代格式必须满足一定条件才能收敛！开始迭代…….显然不收敛!可见，对同一方程组，同样的初始值，由于变量分离的方式不同，其结果也不同，一个收敛，一个发散。1、迭代公式

方程组AX=b即:a11x1

+a12x2+……..a1nxn=b1a21x1+a22x2+……..a2nxn=b2……………….

ai1x1+ai2x2+…aiixi

...ainxn

=bi……………….an1x1+an2x2+………annxn

=bn若aii≠0，则可从第i个方程分离出xi(i=1,2….n)若aii≠0，则从第i个方程分离出:其中cij=-aij/aii,di=bi/aii

(i=1,...,n,j=1,....,n,j≠i)

cii

=0

xi=(bi-)/aii=+di(i=1,...,n)

即:x1=c11x1

+c12x2+……..c1nxn+d1x2=c21x1+a22x2+……..c2nxn+d2……………….xi=

ci1x1+ci2x2+…ciixi

...cinxn

+di……………….xn

=cn1x1+cn2x2+………annxn

+dnxi(k+1)=+di(i=1,...,nk=0,1,2...)(3.40)-------Jacobi迭代公式(分量形式)也可写成X(K+1)=CX(K)+d-------Jacobi迭代公式(矩阵形式)

其中cij=-aij/aii

j≠i

cii=0选一初始近似值x(0)=(x1(0),x2(0),…,xn(0))T，用上式进行迭代计算，可得到一个近似解序列

x1(k),x2(k),…,xn(k)(k=0,1,2,…)如果极限存在，则称迭代格式收敛，其极限值(x1,x2,…,xn)T就是原方程组的解。按照上述格式进行迭代求方程组的解的方法称为简单迭代法，又称为雅可比迭代法。2、迭代格式的收敛条件充分条件1在迭代格式中，若则雅可比迭代格式对任意初始值x(0)和d都是收敛的。证明：回忆定义3:设精确解为X*=(x1*,x2*...xn*)T

对任意i(i=1,2...n)有则称向量序列{X(K)}收敛于X*，记作

根据定理4，要证明当k->∞时，

由于x*满足方程X*=CX*+dxi

*=ci1x1*

+ci2x2*

+…ciixi*...cinxn*+dixi

(k)=ci1x1(k-1)

+ci2x2(k-1)

+…ciixi

(k-1)...cinxn

(k-1)+dixi

(k)-xi

*=ci1(x1(k-1)-x1*)

+ci2(x2(k-1)

-x2)+...+cin(xn

(k-1)-xn*)

|xi

(k)-xi

*|<=|ci1||x1(k-1)-x1*|

+|ci2||x2(k-1)

-x2*|+...+|cin||xn

(k-1)-xn*|<=(|ci1|+|ci2|+…+|cin|).所以

因为0<μ<1,δ0为一常数,当k->∞时，证得δk->0。μΔk-1充分条件2在迭代格式中，若则雅可比迭代格式收敛。充分条件3在迭代格式中，若则雅可比迭代格式收敛。汇总充分条件1，2，3，只要迭代矩阵至少有一种范数<1，则雅可比迭代格式收敛。迭代收敛格式，什么时候终止？每次迭代后判断|xi(k+1)-xik|=|Δxi(k)|<ε是否成立，如果成立，可停止迭代。由Jacobi迭代公式

xi(k+1)=+di(i=1,...,nk=0,1,2...)，在迭代的每一步计算过程中，是用x（k)的全部分量来求x(k+1)

的所有分量，

显然，在计算第i个分量xi(k+1)时，已经计算出的最新分量

x1(k+1),…..xi-1(k+1)没有被利用，对这些最新计算出的分量加以利用，也即在Jacobi迭代中用:x1(k+1),…..xi-1(k+1）来代替x1(k),…..xi-1(k）所得公式即为Gauss-seidel迭代。二、Gauss-Seidel迭代法及其收敛条件1、迭代公式

Xi(k+1)=++di

(i=1,2....,n)(3-41)

其中

cij=-aij/aii(i=1,...,n,j=1,....,n,j≠i)

cii=0di=bi/aii

2、迭代格式的收敛条件充分条件1在迭代格式中，若则高斯-赛德尔迭代格式对任意初始值x(0)和d都是收敛的。

充分条件2在迭代格式中，若则高斯-赛德尔迭代格式收敛。汇总充分条件1，2，只要迭代矩阵至少有一种范数<1，则高斯-赛德尔迭代格式收敛。迭代收敛格式，什么时候终止？每次迭代后判断|xi(k+1)-xik|=|Δxi(k)|<ε是否成立，如果成立，可停止迭代。三、严格对角占优矩阵的雅可比和高斯-赛德尔迭代格式定义8

设A=(aij)是一个

nxn矩阵，若

|aii|>(i=1,2....,n)

则称A为严格对角占优矩阵。定理4:方程组Ax=b，其中A为n阶严格对角占优矩阵时，一定存在收敛的雅可比迭代和高斯-赛德尔迭代格式。证明。

总结：

Jacobi迭代收敛条件充分条件(1):方程组AX=b的系数矩阵A为

严格对角占优阵充分条件(2):迭代矩阵至少存在一种矩阵范数||.||,

使

||C||<1充要条件(3)：迭代矩阵的谱半径ρ(C)<1总结：

高斯-赛德尔迭代收敛条件充分条件1:方程组

AX=b的系数矩阵A对称正定充分条件2:方程组

AX=b的系数矩阵A严格对角占优充分条件3：迭代矩阵C的范数||C||<1充要条件4：迭代矩阵C的谱半径

ρ(C)<1例1:已知：

8x1-3x2+2x3=204x1+11x2-x3=336x1+3x2+12x3=36写出

jacobi迭代格式，判断其收敛性解:由原方程可得jacobi迭代公式x1(k+1)=3/8x2(k)-2/8x3(k)+20/8x2

(k+1)=-4/11x1(k)+1/11x3

(k+33/11x3

(k+1)=-6/12x1(k)–3/12x2(k)+36/12因为系数矩阵对角占优,所以,该迭代公式收敛例2：设有方程组

X=CX+d,考察用迭代法

X(k+1)=CX(k)+d求解方程的收敛性其中

C=0.90d=10.30.82例3：将例1改写成Gauss-seidel迭代

x1(k+1)=3/8x2(k)-2/8x3(k)+20/8x2

(k+1)=-4/11x1(k+1)+1/11x3

(k)+