解线性方程组的直接法.docx
- 文档编号:16326395
- 上传时间:2023-07-12
- 格式:DOCX
- 页数:46
- 大小:32.81KB
解线性方程组的直接法.docx
《解线性方程组的直接法.docx》由会员分享,可在线阅读,更多相关《解线性方程组的直接法.docx(46页珍藏版)》请在冰点文库上搜索。
解线性方程组的直接法
解线性方程组的直接法
第三章解线性方程组的直接法
许多科学技术问题要归结为解含有多个未知量x1,x2,„,xn的线性方程组
a11x1a12x2a1nxnb1axaxaxb2112222nn2
an1x1an2x2annxnbn
(3.1)
这里aij(i,j=1,2,„,n)为方程组的系数,bi(i=1,2,„,n)为方程组自由项。
方程组(3.1)
的矩阵形式为:
AX=b其中
a11a12
a22a
A21
a
n1an2a1n
a2n
annx1
xX2
xnb1bb2
bn
线性方程组的数值解法可以分为直接法和迭代法两类。
所谓直接法,就是不考虑舍入误差,通过有限步骤四则运算即能求得线性方程组(3.1)准确解的方法。
如克莱姆法则,但通过第一章的分析,我们知道用克莱姆法则来求解线性代数方程组并不实用,因而寻求线性方程组的快速而有效的解法是十分重要的。
本章讨论计算机上常用而有效的直接解法――高斯消去法和矩阵的三角分解等问题。
为方便计,设所讨论的线性方程组的系数行列式不等于零。
§1高斯消去法高斯(Gauss)消去法是解线性方程组最常用的方法之一,它的基本思想是通过逐步消元,把方程组化为系数矩阵为三角形矩阵的同解方程组,然后用回代法解此三角形方程组得原方程组的解。
下面先讨论三角形方程组的解法。
1.三角形方程组的解法三角形方程组是指下面两种形式的方程组
a11x1b1
a21x1a22x2b2axaxaxb
n22nnnnn11
(3.2)
和
a11x1a12x2a1nxnb1
a22x2a2nxnb2
annxnbn
(3.3)
方程组(3.2)叫做下三角形方程组,方程组(3.3)叫做上三角形方程组,三角形方程组的
求解是很简单的。
如果aii0,i=1,2,„,n,则(3.2)的解为
xb1
111
k=2,3,„,n
xk(bkak1x1ak2x2ak,k1xk1)/akk
(3.4)
此过程称为前推过程。
同样地,若aii0,i=1,2,„,n,则(3.3)的解为
xbn
nnnxk(bkak,k1xk1aknxn)/akk
(3.5)
kn1,n2,,1
此过程称为回代过程。
从上面的公式来看,求出xk,需要作k–1次乘法和加减法及一次除法,总共完成
n2
次乘法、加法及n次除法。
12n2
从(3.4)、(3.5)可以看出,求解三角形方程组是很简单的,只要把方程组化成了等价的三角形方程组,求解过程就很容易完成。
2.高斯消去法为便于叙述,先以一个三阶线性方程组为例来说明高斯消去法的基本思想。
2x13x24x36
3x15x22x354x3x30x32
231
()()(III)
把方程(I)乘(
34
)后加到方程(II)上去,把方程(I)乘()后加到方程(III)上22
去,即可消去方程(II)、(III)中的x1,得同解方程组
2x13x24x36
0.5x24x343x22x20
23
()()(III)
将方程(II)乘(
3
)后加于方程(III),得同解方程组:
0.5
()()(III)
2x13x24x36
0.5x24x342x34
由回代公式(3.5)得x3=2x2=8x1=-13
下面考察一般形式的线性方程组的解法,为叙述问题方便,将bi写成ai,n+1,i=1,2,„,n。
a11x1a12x2a13x3a1nxna1,n1
a21x1a22x2a23x3a2nxna2,n1
an1x1an2x2an3x3annxnan,n1
(3.6)
如果a110,将第一个方程中x1的系数化为1,得
(1)
(1)
(1)
x1a12x2a1nxna1,n1
其中a(记aij
(0)
(1)1j
(0)aij
(0)a11
j=1,„,n+1
aiji=1,2,„,n;j=1,2,„,n+1)
从其它n–1个方程中消x1,使它变成如下形式
(1)1))
x1a12x2a1(nxna1(,1n1
(1)
(1)
(1)
a22x2a2xann2,n1
(1)
(1)
(1)axaxan22nnnn,n1
(1)
(1)
aijaijmi1aij
(3.7)
其中
i2,,n
mi1
1)
ai(1
11
j2,3,,n1
由方程(3.6)到(3.7)的过程中,元素a11起着重要的作用,特别地,把a11称为主元素。
如果(3.7)中a220,则以a22为主元素,又可以把方程组(3.7)化为:
(1))
(1)
x1a12x2a1(1nxna1,n1
(2)
(2)
(2)x2a23x3a2nxna2,n1
(2)
(2)(3)
a33x3a3nxna3,n1
(2)
(2)
(2)an3x3annxnan,n1
(1)
(1)
(3.8)
针对(3.8)继续消元,重复同样的手段,第k步所要加工的方程组是:
(1)
(1))
(1)
x1a12x2a13x3a1(1nxna1,n1
(2)
(2)
(2)
x2a23x3a2xann2,n1
(k1)(k1)(k1)
xk1ak1xkaknxnak1,n1(k1)(k1)(k1)
axaxakkknnnk,n1
(k1)(k1)(k1)
axaxankknnnn,n1
(k1)
0,第k步先使上述方程组中第k个方程中xk的系数化为1:
设akk
(k)(k)(k)xkak,k1xkaknxnak,n1
然后再从其它(n-k)个方程中消xk,消元公式为:
(k1)
(k)akj
jk,k1,,n1akj(k1)
akk
(k)(k1)(k1)(k)
(3.9)aijaijaikakj
jk1,,n1ik1,n
按照上述步骤进行n次后,将原方程组加工成下列形式:
(1)
(1))
(1)x1a12x2a13x3a1(1nxna1,n1
(2)
(2)
(2)
x2a23x3a2xann2,n1
(n1)(n1)
xaxan1nnnn1,n1
(n)xann,n1
回代公式为:
(n)
xnan
n1
n(k)(k)xkak,n1akjxj
jk1
kn1,,1
(3.10)
综上所述,高斯消去法分为消元过程与回代过程,消元过程将所给方程组加工成上三角
形方程组,再经回代过程求解。
由于计算时不涉及xi,i=1,2,„,n,所以在存贮时可将方程组AX=b,写成增广矩阵(A,b)存贮。
下面,我们统计一下高斯消去法的工作量;在(3.9)第一个式子中,每执行一次需要
n(nk)次除法,在(3.9)第二个式子中,每执行一次需要[n(k1)](nk)次除
法。
因此在消元过程中,共需要
(nk1)(nk)(nk1)
k1n
n
(nk1)2
k1
1
n(n1)(2n1)6
次乘作法。
此外,回代过程共有
(nk)
k1
n
n
(n1)2
次乘法。
汇总在一起,高斯消去法的计算量为:
n2n3n(n3n1)n2333
次乘除法。
3.主元素消去法前述的消去过程中,未知量是按其出现于方程组中的自然顺序消去的,所以又叫顺序消
(k1)
去法。
实际上已经发现顺序消去法有很大的缺点。
设用作除数的akk元过程中可能出现akk
(k1)
为主元素,首先,消
(k1)
为零的情况,此时消元过程亦无法进行下去;其次如果主元素akk
很小,由于舍入误差和有效位数消失等因素,其本身常常有较大的相对误差,用其作除数,会导致其它元素数量级的严重增长和舍入误差的扩散,使得所求的解误差过大,以致失真。
我们来看一个例子:
例
0.0001x11.00x21.00
1.00x1.00x2.0012
它的精确解为:
x1
10000
1.0001099999998x20.99990
9999
x21.00
用顺序消去法,第一步以0.0001为主元,从第二个方程中消x1后可得:
10000x210000
回代可得x1=0.00显然,这不是解。
造成这个现象的原因是:
第一步主元素太小,使得消元后所得的三角形方程组很不准确所致。
如果我们选第二个方程中x1的系数1.00为主元素来消去第一个方程中的x1,则得出如下方程式:
1.00x1=1.00x1=1.00这是真解的三位正确舍入值。
从上述例子中可以看出,在消元过程中适当选取主元素是十分必要的。
误差分析的理论和计算实践均表明:
顺序消元法在系数矩阵A为对称正定时,可以保证此过程对舍入误差的数值稳定性,对一般的矩阵则必须引入选取主元素的技巧,方能得到满意的结果。
列主元消去法在列主元消去法中,未知数仍然是顺序地消去的,但是把各方程中要消去的那个未知数的系数按绝对值最大值作为主元素,然后用顺序消去法的公式求解。
例:
用列主元高斯消去法求解方程
2x1x23x31
4x12x25x34x2x7
21
由于解方程组取决于它的系数,因此可用这些系数(包括右端项)所构成的“增广矩阵”
作为方程组的一种简化形式。
对这种增广矩阵施行消元手续:
2131*42541207
第一步将4选为主元素,并把主元素所在的行定为主元行,然后将主元行换到第一行得
到
4
254213110.51.251第一步消元*
1207020.51
01.51.25610.51.25110.51.25第二步消元010.250.5第三步消元010.25000.8755.25001消元过程的结果归结到下列三角形方程组:
x10.5x21.25x31
x20.25x30.5x36回代,得
x19x21x3
6列主元消去法计算步骤:
1、输入矩阵阶数n,增广矩阵A(n,n1)2、对k1,2,,n
(1)按列选主元:
选取l使
alkmaxkin
aik0
(2)如果lk,交换A(n,n1)的第k行与底l行元素(3)消元计算:
maik
ik
aik1,,nkk
aijaijmikakji,k1,,njk1,,n1
3、回代计算:
xiai,n1
jn
a
ij
xjin,n1,,1
i1
1
0.5
6
4、输出解向量x1,x2,,xn。
4.无回代过程的主元消去法设有线性代数方程组AX=b
其中A为nn阶非奇异矩阵,b为n1阶矩阵(列向量),由A-1AX=A-1b得X=A-1b。
因此,只要求出A-1就可以得到解X。
另外,有许多问题需要求矩阵的逆,例如常用的回归分析方法中,要求出相关矩阵的逆,因此,有必要讨论在计算机上常用的求逆方法。
步骤:
第一步选主元,在第一列中选绝对值最大的元素ak1max{aj1},设第k行为主元行,
1jn
将主元行换至第一行,将第一个方程中x1的系数变为1,并从其余n–1个方程中消去x1。
第二步:
在第二列后n–1个元素中选主元,将第二个方程中x2的系数变为1,并从其它n–1个方程中消去x2。
„„依此类推,直到每个方程中仅有一个变量为止。
此过程进行到第k–1步后,方程组将变成如下形式:
x1
1)
a1(,kk1)xka1(,kn1)xna1(,kn1
x2
(k1)(k1)(k1)a2,kxka2,nxna2,n1
(k1)(k1)(k1)xk1ak1,kxkak1,nxnak1,n1
(k1)(k1)(k1)
akkxkaknxnak,n1
(k1)(k1)(k1)ankxkannxnan,n1
第k步:
在第k列后n–k个元素中选主元,换行,将第k个方程xk的系数变为1,从
其它方程中消去变量xk,消元公式为:
(k1)
(k)akj
jk,k1,,n1akj(k1)
akk
a(k)a(k1)a(k1)a(k)
ijikkjij
(3.11)
jk1,,n1i1,2,k1,k1,,n
对k=1,2,„,按上述步骤进行到第n步后,方程组变为:
)
x1a1(,n
n1
(n)x2a2,n1
xa(n)
n,n1n
即为所求的解5.无回代消去法的应用
(1)解线性方程组系设要解的线性方程组系为:
AX=b1,AX=b2,AX=bm其中
a11a1nA
an1annx1X
xn
a1(,in)1(i)a2,n1
bi
a(i)n,n1i1,2,,n
上述方程组系可以写为AX=B=(b1,„,bm)因此X=A-1B即为线性方程组系的解。
在计算机上只需要增加几组右端常数项的存贮单元,其结构解一个方程组时一样。
行系数
1
a11
a12a1na22a2n
an2ann
)
a1(,1n)1a1(,mn1
(1)a2,n1
(m)
a2,n1
2n
a21an1
(1)(m)
anan,n1,n1
(2)求逆矩阵
设A=(aij)nn是非奇矩阵,A0,且令
XA1(Xij)nn
由于AA-1=AX=I
因此,求A-1的问题相当于解下列线性方程组
x111x210
A,,
x0n1
0x1n0x
A2n
x0nn1
也就是相当于(I)中m=n,B=I的情形。
(3)求行列式的值由于行列式任意一行(列)的元素乘以同一个数后,加到另一行(列)的对应元素上,其行列式的值不变;任意对换两行(列)的位置其值反号;三角矩阵的行列式之值等于其主对角元素的乘积。
因此,可用高斯消去法将A化成
(1)a11
A
(2)a22
(n)ann
(1)(n)
a11ann
§2解三对角方程组的追赶法在实际问题中,经常遇到以下形式的方程组
b1x1c1x2d1
axbxcxd
2223221
akxk1bkxkckxk1dk
an1xn2bn1xn1cn1xndn1
anxn1bnxndn
(3.12)
这种方程组的系数矩阵称为三对角矩阵
b1c1
a2b2c2A
akbk
ckan1
bn1an
cn1
bn
以下针对这种方程组的特点提供一种简便有效的算法—追赶法。
追赶法实际上是高斯消去法的一种简化形式,它同样分消元与回代两个过程。
先将(3.12)第一个方程中x1的系数化为1
x1
c1dx21b1b1c1b1
y1
d1
b1
(3.13)
记r1
有x1r1x2y1
注意到剩下的方程中,实际上只有第二个方程中含有变量x1,因此消元手续可以简化。
利用
(3.13)可将第二个方程化为
x2r1x3y2
这样一步一步地顺序加工(3.12)的每个方程,设第k–1个方程已经变成
xk1rk1xkyk1
(3.14)
再利用(3.14)从第k个方程中消去xk-1,得:
(bkrk1ak)xkckxk1dkyk1ak
同除bkrk1ak,得记
xk
ckdyk1ak
xk1k
bkrk1akbkrk1ak
k2,3,,n
rk
ck
bkrk1ak
yk
dkyk1ak
bkrk1ak
则有xkrkxk1yk这样做n–1步以后,便得到:
xn1rn1xnyn1
将上式与(3.12)中第11个方程联立,即可解出xn=yn这里
yn
dnyn1an
bnrn1an
于是,通过消元过程,所给方程组(3.12)可归结为以下更为简单的形式:
x1r1x2y1
xkrkxk1ykxnyn
(3.15)
这种方程组称作二对角型方程组,其系数矩阵中的非零元素集中分步在主对角线和一条
次主对角线上
1r1
1r2
1rk
1rn1
1
对加工得到的方程组(3.15)自下而上逐步回代,即可依次求出xn,xn-1,„,x1,计算
公式为:
xnyn
xkykrkxk1
kn1,n2,,1
(3.16)
上述算法就是追赶法,它的消元过程与回代过程分别称作“追”过程与“赶”过程。
综
合追与赶的过程,得如下计算公式:
c1d1ry11bb11ckrk
bkrk1ak
dkyk1akyk
bkrk1ak
xnyn
xkykrkxk1
(3.17)
k2,3,,n
(3.18)
kn1,n2,,1
§3矩阵的三角分解及其在解方程组中的应用下面我们进一步用矩阵理论来分析高斯消去法,从而建立矩阵的三角分解定理,而这个定理在解方程组的直接解法中起着重要作用,我们将利用它来推导某些具有特殊的系数矩阵方程组的数值解法。
考虑线性方程组AX=bARnn
设解此方程组用高期消去法能够完成(不进行变换两行的初等变换),由于对A施行初等变换相当于用初等矩阵左乘A,于是,高斯消去法的求解过程用矩阵理论来叙述如下:
记:
11Lklk1,k1
l1
n,ka(jii)a
(i)
ii
111
Llk1,k1k
l1
n,k
其中lji于是
(ji1,,n)记A
(1)A
1
(1)a21
(1)
a11
(1)1)
a12a1(n1
LA
(1)
a
(1)
11
a
(1)A
(1)
22
21a
(1)
n1a
(1)111
a
(1)n1
0TrT
1a
(1)
111r1a
(1)11
Tc1a
(1)IA
(1)n1
c1220
A
(1)22
c1r111
a
(1)11
a
(1)
(1)
(1)11a12a1n
a
(2)
(2)
(2)22a2nA11A
(2)
12
A
(2)022A
(2)
a
(2)
(2)2nann
10T
a11
rT1
L2A
(2)
00TrA(3)
T
112
a
(2)22
0c2
A
(2)033
a
(2)I22
0cn22
如此继续下去,到n–1步时有:
a
(1)
(1)
11a1n
L(n1)
n1Aa
(2)
(2)
22a2nU
a
(2)nn
也就是说
Ln1Ln2L2L1AU
记
1
l211
LL11
11L2Ln1
l31l32
ln1ln21
则有A=LU
其中L为单位下三角矩阵,U为上三角矩阵。
总结上述讨论得到重要性定理
A(3)
12
A(3)A(3)22
定理1:
(矩阵的三角分解)设A为nn实矩阵,如果解AX=b用高斯消去法能够完
(k)
成(限制不进行行的交换,即akk0,
k1,2,,n),则矩阵A可分解为单位下三角矩
阵L与上三角知阵U的乘积。
A=LU且这种分解是唯一的。
证明:
由上述的讨论,存在性已得证,现在证唯一性。
设A=L1U1=LU
其中L1,L1为单位下三角阵,U1,U为上三角阵,设U1存在,于是有
1
L1L1UU11
上式
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 线性方程组 直接
![提示](https://static.bingdoc.com/images/bang_tan.gif)