线性代数方程组的直接解法

线性代数方程组的直接解法

3、2解线性方程组得直接法(高斯消去法)

3、2、1高斯消去法得基本思想例3、1解线性方程组

①②③解:

该方程组得求解过程实际上就是将中学学过得消元法标准化,将一个方程乘或除以某个常数,然后将两个方程相加减,逐步减少方程中得未知数,最终使每个方程只含有一个未知数,从而得出所求得解。整个过程分为消元和回代两个部分。

(1)消元过程第1步:将方程①乘上(-2)加到方程②上去,将方程①乘上加到方程③上去,这样就消去了第2、3个方程得项,于就是就得到等价方程组④⑤第2步:将方程

④乘上加到方程

⑤上去,这样就消去了第3个方程得项,于就是就得到等价方程组

⑥这样,消元过程就就是把原方程组化为上三角形方程组,其系数矩阵就是上三角矩阵。

(2)回代过程回代过程就是将上述三角形方程组自下而上求解,从而求得原方程组得解:

前述得消元过程相当于对原方程组

得增广矩阵进行下列变换(表示增广矩阵得第行)同样可得到与原方程组等价得方程组⑥

由此看出,高斯消去法解方程组基本思想就是设法消去方程组得系数矩阵A得主对角线下得元素,而将Ax=b化为等价得上三角形方程组,然后再通过回代过程便可获得方程组得解。换一种说法就就是用矩阵行得初等变换将原方程组系数矩阵化为上三角形矩阵,而以上三角形矩阵为系数得方程组得求解比较简单,可以从最后一个方程开始,依次向前代入求出未知变量这种求解上三角方程组得方法称为回代,通过一个方程乘或除以某个常数,以及将两个方程相加减,逐步减少方程中得变元数,最终将方程组化成上三角方程组,一般将这一过程称为消元,然后再回代求解。通常把按照先消元,后回代两个步骤求解线性方程组得方法称为高斯(Gauss)消去法。3、2、2高斯消去法算法构造

线性方程组(3、1)用矩阵形式表示为

(3、3)解线性方程组(3、1)得高斯(Gauss)消去法得消元过程就就是对(3、3)得增广矩阵进行行初等变换。将例3、1中解三阶线性方程组得消去法推广到一般得阶线性方程组并记则高斯消去法得算法构造归纳为:

⑴消元过程,高斯消去法得消元过程由n-1步组成:第1步设,把(3、3)中得第一列中元素消为零,令用乘以第1个方程后加到第个方程上去,消去第2～n个方程得未知数,得到即其中

第k步

(k=2,3,…,n-1)继续上述消元过程,设第k-1次消元已经完成,得到与原方程组等价得方程组

记为其中只要,消元过程就可以进行下去,直到经过n-1次消元之后,消元过程结束,得到与原方程组等价得上三角形方程组,记为或者写成

即

(3、7)(2)回代过程就就是对上三角方程组(3、7)自下而上逐步回代解方程组计算,即

12大家应该也有点累了，稍作休息大家有疑问的，可以询问和交流(3)高斯消去法得计算步骤:①消元过程;设计算②回代过程

(4)高斯消去法流程图

,见P42(5)

Gauss消去法计算量≈①消元计算:aij(k+1)=aij(k)-mik

akj(k)

(i,j=k+1,k+2,…,n)

第一步计算乘数mik,mik=ai1/a11

(i=2,3,…,n)

需要n-1次除法运算,

计算aij(2)(i,j=2,3,…,n)

需要(n-1)2次乘法运算及(n-1)2次加减法运算,第k步加减法次数乘法次数除法次数123…n-1(n-1)2(n-2)2(n-3)2…1(n-1)2(n-2)2(n-3)2…1(n-1)(n-2)(n-3)…1合计n(n-1)(2n-1)/6n(n-1)(2n-1)/6n(n-1)/2乘除法次数:MD=n(n-1)(2n-1)/6+n(n-1)/2=1/3n(n2-1)加减法次数:AS=n(n-1)(2n-1)/63、2、3高斯消去法得适用条件定理3、1方程组系数矩阵得顺序主子式全不为零则高斯消去法能实现方程组得求解。证明上三角形方程组就是从原方程组出发,通过逐次进行“一行乘一数加到另一行”而得出得,该变换不改变系数矩阵顺序主子式得值。

设方程组系数矩阵,其顺序主子式(m=1,2,…,n)

经变换得到得上三角形方程组得顺序主子式所以能实现高斯消去法求解

(m=1,2,…,n)定义3、1设矩阵每一行对角元素得绝对值都大于同行其她元素绝对值之和

则称A为严格对角占优矩阵。

定理3、2若方程组得系数矩阵A为严格对角占优,则用高斯消去法求解时,全不为零。

证:先考察消元过程得第1步,因A为严格对角占优,故故,又根据高斯消去公式得

于就是再利用方程组得对角占优性,由上式可进一步得又由得

故有当A为严格对角占优时,,余下得子阵仍就是对角占优得,从而又有。依次类推全不为零。定理证毕。一般线性方程组使用高斯消去法求解时,在消元过程中可能会出现得情况,这时消去法将无法进行;即使,但她得绝对值很小时,用其作除数,会导致其她元素数量级得严重增长和舍入误差得扩散,将严重影响计算结果得精度。实际计算时必须避免这类情况得发生。主元素消去法就可弥补这一缺陷。交换原则:通过方程或变量次序得交换,使在对角线位置上获得绝对值尽可能大得系数作为akk(k),称这样得akk(k)

为主元素,并称使用主元素得消元法为主元素法根据主元素选取范围分为:列主元素法、行主元素法、全主元素法记笔记3、2、4高斯主元素消去法主元素法得意义例3、2用高斯消去法求下列方程组得解

解:确定乘数,再计算系数假设计算在4位浮点十进值得计算机上求解,则有

这时方程组得实际形式就是

由此回代解出,但这个解不满足原方程组,解就是错误得。这就是因为所用得除数太小使得上式在消元过程中“吃掉”了下式,解决这个问题得方法之一就就是采用列选主元高斯消元法。即按列选绝对值大得系数作为主元素,则将方程组中得两个方程相交换,原方程组变为

得到消元后得方程组这时

因而方程组得实际形式就是由此回代解出,这个结果就是正确得可见用高斯消去法解方程组时,小主元可能导致计算失败,因为用绝对值很小得数作除数,乘数很大,引起约化中间结果数量级严重增长,再舍入就使得计算结果不可靠了,故避免采用绝对值很小得主元素。以便减少计算过程中舍入误差对计算解得影响。全主元素消去法就是通过方程或变量次序得交换,使在对角线位置上获得绝对值尽可能大得系数作为,称这样得为主元素。尽管她得算法更稳定,但计算量较大,实际应用中大多数使用列主元素消去法即可满足需要。

全主元素法不就是按列选主元素,而就是在全体待选系数中选取,则得全主元素法。例3、3用全主元素法解下列线组

10x1-19x2-2x3=3(1)-20x1+40x2+x3=4(2)x1+4x2+5x3=5(3)解:选择所有系数中绝对值最大得40作为主元素,交换第一、二行和交换第一、二列使该主元素位于对角线得第一个位置上,得40x2-20x1+

x3=4(4)-19x2+10x1-2x3=3(5)

4x2+x1+5x3=5(6)记笔记计算m21=-19/40=0、475,m31=4/40=0、1(5)-m21(4),(6)-m31(4)消去x2

得

0.5x1–1.525x3=4.9(7)3x1+4.9x3=4.6(8)选4、9为主元素

4.9x3+3x1=4.6(9)1.525x3+0.5x1=4.9(10)计算m32=-1、525/4、9=-0、31122,(10)-m32(9)消去x2得1、43366x1=6、33161(11)记笔记保留有主元素得方程40x2-20x1+

x3=4(4)

4.9x3+3x1=4.6(9)

1.43366x1=6.33161(11)进行回代x1=4.41634

x3=-1.76511x2=2.352303、2、4、1列主元素法列主元素法就就是在待消元得所在列中选取主元,经方程得行交换,置主元素于对角线位置后进行消元得方法。例3、4用列主元素法解下列线性方程组

10x1-19x2-2x3=3(1)-20x1+40x2+x3=4(2)x1+4x2+5x3=5(3)解:选择-20作为该列得主元素,-20x1+40x2+x3=3(4)

10x1-19x2-2x3=4(5)x1+4x2+5x3=5(6)计算m21

=10/-20=-0、5

m31=1/-20=-0、05(5)-m21(4),(6)-m31(4)得

x2–1.5x3=5(7)6x2+5.05x3=5.2(8)选6为主元素6x2+5.05x3=5.2(9)x2–1.5x3=5(10)计算m32=1/6=0、16667,

(10)-m32(9)得-2、34168x3=4、13332(11)记笔记保留有主元素得方程

-20x1+40x2+x3=4(4)6x2+5.05x3=5.2(9)-2.34168x3=4.13332(11)进行回代x3=-1.76511x2=2.35230x1=4.41634记笔记

列选主元素得计算方法与高斯消去法完全一样,不同得就是在每步消元之前要按列选出主元例3、5用矩阵得初等行变换求解解方程组

解:用矩阵得初等行变换求解,对增广矩阵

(下面带下划线元素为主元素)3、3矩阵三角分解法

3、3、1矩阵三角分解原理

应用高斯消去法解n阶线性方程组Ax=b,经过n步消元之后,得出一个等价得上三角型方程组A(n)x=b(n),对上三角形方程组用逐步回代就可以求出解来。上述过程可通过矩阵分解来实现。将非奇异阵A分解成一个下三角阵L和一个上三角阵U得乘积

A=LU

称为对矩阵A得三角分解,又称LU分解其中方程组Ax=b得系数矩阵A经过顺序消元逐步化为上三角型A(n),相当于用一系列初等变换左乘A得结果。事实上,第1列消元将A(1)=A化为A(2),若令:则根据距阵左乘有L1A(1)=A(2)第2列消元将A(2)化为A(3),若令:经计算可知L2A(2)=A(3),依此类推,一般有LkA(k)=A(k+1)mi1=a(1)

i1/a(1)

11i=2,3,……n于就是矩阵经过消元化为上三角阵得过程可表示为上述矩阵就是一类初等矩阵,她们都就是单位下三角阵,且其逆矩阵也就是单位下三角阵,只需将

改为

,就得到。即于就是有

其中L为由乘数构成得单位下三角阵,U为上三角阵,由此可见,在得条件下,高斯消去法实质上就是将方程组得系数矩阵A分解为两个三角矩阵得乘积A=LU。这种把非奇异矩阵A分解成一个下三角矩阵L和一个上三角矩阵U得乘积称为矩阵得三角分解,又称LU分解。显然,如果,由行列式得性质知,方程组系数矩阵A得前n-1个顺序主子矩阵非奇异,即顺序主子式不等于零,即其中(A得主子阵)

反之,可用归纳法证明,如果A得顺序主子式则于就是得到下述定理:

定理3、5设。如果A顺序各阶主子式,,则A可惟一地分解成一个单位下三角阵L和一个非奇异得上三角阵U得乘积。证:由于A各阶主子式不为零,则消元过程能进行到底,前面已证明将方程组得系数矩阵A用初等变换得方法分解成两个三角矩阵得乘积A=LU得过程。

现仅证明分解得惟一性。设A有两种LU分解其中为单位下三角阵,为上三角阵

∵A得行列式均为非奇异矩阵,有上式两边左边同乘,右边同乘得上式左边为单位下三角阵,右边为上三角阵,故应为单位阵,即惟一性得证。把A分解成一个单位上三角阵L和一个下三角阵U得乘积称为杜利特尔(Doolittle)分解。其中

若把A分解成一个下三角阵L和一个单位上三角阵U得乘积称为克洛特分解Crout)

其中3、3、2用三角分解法解方程组求解线性方程组Ax=b时,先对非奇异矩阵A进行LU分解使A=LU,那么方程组就化为

LUx=b从而使问题转化为求解两个简单得得三角方程组

Ly=b求解yUx=y求解x这就就是求解线性方程组得三角分解法得基本思想。下面只介绍杜利特尔(Doolittle)分解法。设A=LU为由矩阵乘法规则由此可得U得第1行元素和L得第1列元素再确定U得第k行元素与L得第k列元素,对于k=2,3,…,n计算:①

计算U得第k行元素

(j=k,k+1,…,n)

②计算L得第k列元素(i=k,k+1,…,n)

利用上述计算公式便可逐步求出U与L得各元素求解Ly=b,即计算:

求解Ux=y,即计算:显然,当时,解Ax=b直接三角分解法计算才能完成。设A为非奇异矩阵,当时计算将中断或者当绝对值很小时,按分解公式计算可能引起舍入误差得积累,因此可采用与列主元消去法类似得方法,对矩阵进行行交换,则再实现矩阵得三角分解。用直接三角分解法解Ax=b大约需要次乘除法。

例3、8用三角分解法解方程组

求解

Ly=b得

y=[

2,2,1]T

求解Ux=y得x=[-1,0,1]T所以方程组得解为

3、5追赶法在数值计算中,有一种系数矩阵就是三对角方程组

简记为Ax=f,A满足条件(1)(2)(3)用归纳法可以证明,满足上述条件得三对角线性方程组得系数矩阵A非奇异,所以可以利用矩阵得直接三角分解法来推导解三对角线性方程组得计算公式,用克洛特分解法,将A分解成两个三角阵得乘积,设A=LU

按乘法展开

则可计算

可依次计算当,由上式可惟一确定L和U。

例3、9用追赶法求解三对角方程组

解由Ly=f

解出y又由Ux=y解出x记笔记3、6向量和矩阵得范数向量范数就是用来度量向量长度得,她可以看成就是二、三维解析几何中向量长度概念得推广。用Rn表示n维实向量空间。记笔记3、6向量和矩阵得范数定义3、2

对任一向量XRn,按照一定规则确定一个实数与她对应,该实数记为||X||,若||X||满足下面三个性质:(1)||X||

0;||X||=0当且仅当X=0;(2)对任意实数,||X||=|

|||X||;对任意向量YRn,||X+Y||||X||+||Y||

则称该实数||X||为向量X得范数在Rn中,常用得几种范数有:记笔记其中x1,x2,…,xn分别就是X得n个分量。以上定义得范数分别称为1-范数,2-范数和-范数当不需要指明使用哪一种向量范数时,就用记号||、||泛指任何一种向量范数。有了向量得范数就可以用她来衡量向量得大小和表示向量得误差。设x*为Ax=b得精确解,x为其近似解,则其绝对误差可表示成||x-x*||,其相对误差可表示成记笔记3、6向量和矩阵得范数或例3、11设x=(1,0,-1,2)T,计算

解:=1+0+|-1|+2=4定理3、7对于任意向量x,有证:∵

∴即

当p→∞,

∴定义3、4(向量序列得极限)设为中得一向量序列,,记。如果(i=1,2,…,n),则称收敛于向量,记为定理3、8(向量范数得等价性)设为上任意两种向量范数,则存在常数C1,,C2>0,使得对任意恒有(证:略)

定理3、9

其中为向量中得任一种范数。

证由于

而对于上得任一种范数,由定理3、7知存在常数C1,C2,使于就是可得从而定理得证。定义3、5(矩阵得范数)如果矩阵得某个

非负得实值函数,满足则称就是上得一个矩阵范数(或模)定义3、7(矩阵得谱半径)设