计算方法 线性方程组的数值解法

第3章线性代数计算方法§1高斯消去法§2高斯―约当消去法§3解实三对角线性方程组的追赶法§4矩阵的三角分解§5行列式和逆矩阵的计算§6迭代法

§7迭代法的收敛性AX=b若A非奇异，即|A|≠0，则X=A-1b克莱姆法则：则Xi=Ai/|A|计算量：一个n阶行列式，需要(n-1)*n!次乘法要计算n+1个n阶行列式，需(n+1)(n-1)*n!X含有n个分量，要做n次除法，共需运算次数(n+1)(n-1)*n!+n=(n2-1)*n!+n每项共n个因子共包含n！项解线性方程组的两类方法:直接法:

经过有限次运算后可求得方程组精确解的方法(不计舍入误差!)迭代法：从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法(一般有限步内得不到精确解)§1高斯消去法高斯消去法是一个古老的直接法，由它改进的方法是目前计算机上常用的求低阶稠密矩阵方程组的有效方法。思路首先将方程组Ax=b

化为上三角方程组，此过程称为消去过程，再求解上三角方程组，此过程称为回代过程.§1高斯消去法一、顺序消去法1、三角形方程组的解法

且aii≠0,i=1,2,…,n(3―4)由方程组(3―4)的最后一个方程直接可得将其代入倒数第二个方程可求得如此再解出xn-2,…,x2,x1，一般有(3―5)2、一般线性方程组的解法现举例如下:解方程组①②③(3―6)

作②-①消去②中的x1,作③-①×4消去③中的x1,则方程组(3―6)化为①②③(3―6′)对方程组(3―6′)作③-②×,得到三角形方程组①②③(3―6")从方程组(3―6“)的方程③解出x3,将所得的结果代入方程②求出x2,再把x3、x2同时代入方程①解出x1。这样可求出方程组的解为

上述求解方程组的方法就是高斯(Gauss)消去法。从式(3―6)到(3―6“)的过程称为消元过程而由(3―6”)求出x3、x2、x1的过程称为回代过程。

因此用高斯消去法求解线性方程组要经过消元和回代两个过程。2、一般的线性方程组将增广矩阵的第i行+li1

第1行，得到：消去过程：第一步：设，计算因子其中第k步：设，计算因子且计算共进行n

1步，得到定理：若A的所有顺序主子式均不为0，则高斯消去法能顺序进行消元，得到唯一解。回代过程：

3、顺序高斯消去法的计算步骤：在计算机上实现时,我们常把方程组右端的常数项排于系数矩阵的第n+1列，

1）消元过程

对于k=1,2,…,n-1列,若按顺序有某一ark≠0,r≥k,则交换k与r行,然后计算

(3―11)2）回代过程

对于k=n,n-1,…,2,1,计算(3―12)4、计算量：消元次数k=1时，计算li1(i=2,3，…，n)需n-1次除法运算.

使aij(1)变为aij(2)

以及使bi(1)变为bi(2)需要

n(n-1)次乘法运算和n(n-1)次加(减)法运算.消元次数k=2时，计算li2(i=3，…，n)需n-2次除法运算.

使aij(2)变为aij(3)

以及使bi(2)变为bi(3)需要

(n-1)(n-2)次乘法运算。消元次数k=1时，需n-1次除法运算,需n(n-1)次乘法运算消元次数k=2时，需n-2次除法运算,需(n-1)(n-2)次乘法运算…消元次数k=n-1时，需n-k=1次除法运算,需(n-(k-1))(n-k)=2*1次乘法运算除法运算总次数(n-1)+…+1=n(n-1)/2乘法运算总次数n(n-1)+(n-1)(n-2)+…+3.2+2.1=n(n-1)(n+1)/3总次数N1=n(n-1)/2+n(n-1)(n+1)/3回代过程的计算除法运算次数为n次.乘法运算总次数为1+…+(n-1)=n(n-1)/2回代总次数N2=n+n(n-1)/2=n(n+1)/2

N=N1+N2=n(n-1)/2+n(n-1)(n+1)/3=n3/3+n2-n/3Gauss消去法的运算次数与n3同阶，记为O(n3)克莱姆法则需运算次数为(n2-1)*n!+n二、主元素消去法用高斯消去法求解下列方程组(用四位有效数字计算):①②②-①×1/10-5,得

(1.000-1.000×1/10-5)x2=1.000-0.6000×1/10-5化简可得

x2=0.6000回代求得

x1=105(0.6-0.6000)=0而方程组的解应为

x1=0.4000x2=0.6000

10-5做除数的原因①②

x1+x2=1①10-5x1+x2=0.6

②②-①×10-5/1，得

(1000-1000×10-5)x2=0.6-1.000×10-5

化简得

x2=0.6000

回代求得

x1=(1-0.6000)=0.40001.列主元素消去法所谓列主元素消去法就是在每一步消元过程中取系数子矩阵的第一列元素中绝对值最大者作主元。对线性方程组(3―1)进行n-1次消元后,可得到上三角形方程组必须指出的是方程组(3―13)中的系数aij(i≤j)和右端的bi已经改变了,并非与原来相同。这样就可对方程组(3―13)回代求解。

(3―13)取四位有效数字计算。

解：第一列消元时，②中-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列主元素消去法的计算过程:

(1)消元过程。对于k=1,2,…,n-1进行下述运算:①选主元,确定r,使得若ark=0,说明系数矩阵为奇异,则停止计算；否则进行下一步。②交换A的r、k两行③对i=k+1,k+2,…,n,j=k+1,k+2,…,n+1计算(3―14)

aij-aik·akj/akk⇒aij

(2)回代过程。对于k=n,n-1,…,1计算(3―16)图3.1图3.1

2.全主元素消去法

所谓全主元素消去法,就是每步消元时选取系数子矩阵中绝对值最大的元素作主元。经过n-1次消元后,方程组(3―1)可化为上三角形方程组(3―17)注意：这里方程组(3―17)中的系数aij(i≤j)及bi一般改变了。特别是未知数的排列顺序,由于全主元素的消元过程中,其系数矩阵可能进行了列对调,那么未知数也相应地作了对调。例如,若矩阵第i列与第j列对调,则未知数xi与xj也相应地对调了,xi的结果实质上为xj的结果。

例2用全主元素消去法求解方程组

①②③解：这里主元为-18,交换方程①与方程②得①②③再全选主元,主元为2.333,交换x2和x3所在的两列,同时改变两未知数的排列号得

①②③③-②×0.944/2.333得①②③已经化为三角方程组,回代求解

x1=1.000,x2=3.000,x3=2.000

这里未知数x2与x3已对调,所以应恢复解的顺序,方程组的实际精确解为

x1=1.000,x2=2.000,x3=3.000全主元素消去法的计算过程:

(1)消元过程。对k=1,2,…,n-1进行下列运算:①选主元,确定r,t使得若art=0,则系数矩阵为奇异的,停止计算否则进行下一步。②交换A中的r、t两行及t、k两列,并记下交换的足码t、k。③对i=k+1,k+2,…,n,j=k+1,k+2,…,n+1计算

(2)回代过程。对k=n,n-1,…,1，计算(3―18)

(3―19)(3―20)图3.2

图3.2§2高斯―约当消去法前面所述的消去法均要进行两个过程,即消元过程和回代过程。但对消元过程稍加改变可以把方程组(3―1)化为对角形

(3―21)此时求解就不要回代了。这种无回代过程的主元素消去法称为高斯―约当(Jordan)消去法。特别是方程组(3―21)还可化为(3―22)§3解实三对角线性方程组的追赶法

其中｜a1｜＞｜c1｜＞0

｜ak｜≥｜bk｜+｜ck｜,bkck≠0,k=2,3,…,n-1

｜an｜＞｜bn｜＞0我们将利用所谓“追赶法”解决令

令

其中

当k=n时,因为

bnx

n-1+anxn=rn又

xn-1=un-1-vn-1

xn于是追赶追赶例3解线性方程组解依公式(3―27)、(3―31)求得v3=0(一般v3不必算)再由式(3―32)、(3―30)求得方程组的解图3.3图3.3

§4矩阵的三角分解

对于线性方程组，若其系数矩阵A能够分解成两个三角形矩阵相乘,譬如,A=LU

L为下三角矩阵,U为上三角矩阵,则求解方程组(3―1)就化为求解

LUx=b

令Ux=y

则Ly=b计算F1A？计算F2(F1A)？福罗贝留斯矩阵这样就把A化为一个上三角矩阵U，即在需要进行行交换时，还得左乘某些排列矩阵Pij则A=LU矩阵A的LU分解或三角分解。

4.2矩阵三角分解的唯一性设非奇异矩阵A存在一种三角分解LU,一般这种分解未必唯一,这是因为任意一个同阶的非奇异对角矩阵D总有

(LD)(D-1U)=L1U1

它也是矩阵A的一种