线性方程组的解法例题线性方程组的解法.docx
- 文档编号:16324983
- 上传时间:2023-07-12
- 格式:DOCX
- 页数:61
- 大小:36.84KB
线性方程组的解法例题线性方程组的解法.docx
《线性方程组的解法例题线性方程组的解法.docx》由会员分享,可在线阅读,更多相关《线性方程组的解法例题线性方程组的解法.docx(61页珍藏版)》请在冰点文库上搜索。
线性方程组的解法例题线性方程组的解法
线性方程组的解法例题线性方程组的解法
第二章线性方程组的解法
n阶线性方程组的一般形式为:
a11x1,a12x2,,a1nxnb1ax,ax,,axb2112
222nn2
(2.0.1)
an1x1,an2x2,,annxnbn
Axb
用矩阵表示为:
其中
A称为系数矩阵,x称为解向量,b称为常数向量(简称
方程组自由项),它们分别为:
x1b1a11a12a1n
xbaa
2122a2nx2b2
1
,,A
xnbnan1an2ann
如果矩阵A非奇异,即A的行列式值det(A)0,则根据
克莱姆(Cramer)规则,方程组有唯一解:
Di
i1,2,,nxiD
其中Ddet(A),Di表示D中等i列换b后所得的行列式值。
但克莱姆规则不适用于求解线性代数方程组,因为计算工作量大得难以容忍。
实际用于求解线性代数方程组的计算方法主要有两种:
一
是消去法,它属于直接解法;二是迭代解法。
消去法的优
点是可以预先估计计算工作量,并且根据消去法的基本原理,可以得到矩阵运算(如矩阵求逆等)的求解方法。
但是,由于实际计算过程总存在有误差,由消去法得到的结果并不是绝对精确的,存在数值计算的稳定性问题。
迭代解法的优点是简单,便于编制计算机程序。
在迭代解法中,必须考虑迭收敛速度快慢的问题。
?
2.1线性方程组的直接计算
求解线性代数方程组的直接解法主要是消去法(或称消元
2
法)。
消去法的基本思想是通过初等行变换:
将一个方程乘以某个常数,以及将两个方程相加或相减,减少方程中的未知数数目,最终使每个方程中含一个未知数,从而得到所需要的解。
2.1.1三角形方程组的计算对下三角形方程组:
a11x1b1
ax,axb2112222
(2.1.1)
an1x1,an2x2,,annxnbn
可以通过前代的方法求解:
先从第1个方程求出x1,代入第2个方程求出
x2,依次类推,可以逐次前代求出所有
xi(i1,2,,n),计算公式如下:
b1
x1a
11
i~1
bi~aijxj
(2.1.2)
j1
3
xi,i2,3,,naii
对上三角形方程组:
a11x1,a12x2,,a1nxnb1
ax,,axb2222nn2
annxnbn
(2.1.3)
可以通过回代的方法求解:
先从第n个方程求出xn,代入第n~1个方程求出xn~1,依次类推,可以逐次回代求出所有
xi(in,n~1,,1),计算公式如下:
bn
xna
nn
n
bi~aijxj
(2.1.4)
ji,1
xi,in~1,n~2,,1aii
2
n前代法和回代法的计算量都是次四则运算。
4
2.1.2高斯(Gauss)消去法和LU分解
高斯消去法是将线性方程组等价地变换为一个上三角方程组,然后用回代法求解,它包括消元与回代两个过程。
下面举例说明高斯消去法求解性代数方程组的简要过程。
例求解线性代数方程组
2x1~x2~x34
3x1~4x2~2x311
3x~2x~4x11
231
解将该线性代数方程组写成增广矩阵的形式
2~1~14
34~211
3~2411
用高斯法求解过程如下:
(1)通过消元过程将方程组的增广矩阵变换成右上三角矩阵,且对角线上元素1,具体步骤如下:
将第1个方程中的所有系数以及右端的常数均除以2(称为归一化),得
13
3
~124
~12~24
5
21111
~2
然后将第2个方程减去第1个方程的3倍,以及第3个方
程减去第1个方程的3倍,得
1
1~
21102
0~1
21
22
1
~5211
52~
将第2个方程中的所有系数以及右端的常数均除以11/2
(归一化),得
1
1~
2
01
0~1
6
2
1
22110~111111
52~
然后将第3个方程减去第2个方程的(-1/2)倍,得
1
1~
2
01
00
1
22110~11116060
1111~
此时方程组已经被等价地变为上三角型方程组:
11
x~x~1222x32
110
x3x2~1111
6060
x31111
最后从第3个方程解出x31,将x31代入第2个方程
解出x21,将x31与x21代入第1个方程解出x13。
7
一般来说,高斯消去法解线性方程组分为以下两大步:
1、将系数矩阵
A经过一系列的初等变换变成右上三角矩
100
a12a1n10
a2n
ann
b1b2
bn
阵,其常向量b也同时作相应的变换,即
a11a12a1nb1a
21a22a2nb2
an1an2annbn
在变换过程中,采用原地工作,即经变换后的元素仍存放在原来的存储单元中。
为了实现上述目标,对于k从1开始直到n~1作以下两步:
(1)归一化
akj/akkakj,jk,1,,n
bk/akbkk
这一步的作用是将主对角线上的元素变成1。
为此,第k
8
行上的所有元素akj(j
k,1,,n)与常数向量中的bk,都
要除以akk,一开始没有真正将akk变成1,并且最后也没有真正将akk变成1,因为akk是否真正变成1已经是无关紧要了,只要在以后的变换中将所有对角线上的元素认为是1就行了。
(2)消元
aij~aikaa,kj
ij
ik,1,,;nj
n
k1,
n
bi~aikbkik,1,,b
这一步的作用是将k列中对主对角线以下的元素消成0。
为此,第i(ik,1,,n)行的其他元素aij(
jk,1,,n)
与常数向量b中的元素bi都要减去第k行对应元素的aik倍,开始没有真正将aik变成0,并且最后也没有真正将aik变成0,因为是否真正变成0已经是无关紧要了,以后的变换中已经用不着
aik这个元素了。
通过以上步骤就将系数矩阵变成了右上三角矩阵,并且主
9
对角线上的元素(除最后一个)均为1。
2、进行回代,依次解出xn,xn~1,…,x2,x1。
首先从最后一个方程解出xn,即bn/annxn。
然后从后到前依次回代,逐个解出xn~1,…,x2,x1,即
bk~
jk,1
a
n
kj
xjxk,kn~1,,2,1
保证高斯消去法能够顺利进行的条件:
各次主元素
(i)
aii0(i1,2,,n)。
(i)
a定理2.1.1主元ii0(i1,2,,k)的充要条件为主
子矩阵Ai0(i1,2,,k)非奇异,kn。
证明对k应用归纳法。
(1)
Aak1当时,111,成立。
(i)
ak~1设定理直至成立,即ii0(i1,2,,k~1),由
10
(1)
(2)(k)
高斯消去法过程可知,det(Ak)a11a22akk。
因此,Ak
(k)
a非奇异的充要条件为kk0。
从高斯消去法过程可知,高斯消去法就是对系数矩阵A左
乘了n~1个初等单位下三角矩阵:
A(k,1)LkA(k),k1,2,,n~1(2.1.12)
其中
11Lk
1
~a(k)(k)
k,1,k/akk
1
~a(k)/a(k)nkkk得:
A(n)
Ln~1Ln~2L1A即:
A(L~1~1~1(1L2Ln)n~1
)ALU其中
LL~1~1~11L2Ln~1
11
UA(n)
1
1L~1k1
a(k)(k)
k,1,k/akk1
a(k)(k)
nk/akk
(2.1.13)1
(2.1.14)(2.1.15)(2.1.16)
(2.1.17)
1
1
(1)
(1)a21/a111
(1)
(1)
(2)
(2)
a31/a11a32/a221L
12
1
(1)
(1)
(2)
(2)(n~1)(n~1)
an1/a11an2/a22
an,n~1/an~1,n~11
(2.1.18)
1,a1100
1,
a12
1,
a1n
2,,2,a22a2n
n,
00ann
(k)
UA(n)
k,1,
aij
(k)(k)aik
aij~akj(k),i,jk,1,,n;k1,,n~1
akk
(2.1.10)
13
当A作了LU分解后,线性方程组(2.0.1)就容易求解了:
Lyb
Uxy(2.1.19)
这两个方程组可以通过前代法和回代法求解。
以上的LU分解,称为杜利特尔(Doolittle)分解,其中
L是单位下三角阵,U是上三角阵;若L是下三角阵,U是单
位上三角阵,则称其LU分解为克劳特(Crout)分解。
高斯消去法求解线性方程组的算法分析:
(1)算法的时间复杂度:
算法执行过程中所需乘除法次数。
在第1步中,对于
k的每一个循环,归一化过程需要做
n~k,1次除法,消元过程需要做(n~k,1)(n~k)次乘法。
因此,在算法的第1大步中所做的乘除次数(包括回代中的一次除法)为
1
n~k,1,6n,n,1,(2n,1)k1
2
n
在第2大步中,对于每一个k,只需要做,n~k,次乘法。
因此,回代过程所做的乘法次数
14
1
n~k,2n,n,1,k1
由上分析,高斯消去法执行过程中所需要的总的乘除法次
n
数为:
1132
n~k,1,,,n~k,nn,3n~1n
33k1k1
n
2
n
,
(2)算法的空间复杂度:
算法执行过程中所需存储空间。
在上述算法中,数据空间为系数矩阵、解向量与常数向量所占的存储空间,而所需要的额外空间(算法程序中的工作单元、循环控制变量等所占的存储空间)与数据空间无关。
因此,上述算法符合原地工作的原则。
(3)数值计算的稳定性在上述算法中,对于每一个
k做归一化运算时要用akk作除
数。
由此会带来以下两个问题:
当akk=0,运算就会中断(因为出现分母为0的情况);即使akk0,但当akk很小时,一方面会损失精度,另一方
15
面还可能会导致商太大而使计算产生溢出。
总之,上述算法对数值计算是不稳定的。
2.1.3选主元的LU分解
高斯消去法是按照方程及未知数给定的排列顺序依次进行消元计算,也称为顺序消去法。
虽然A非奇异,但不能保证A的顺序主子矩阵非奇异;即使
A的顺序主子矩阵非奇异,也可能
因为akk很小而使计算结果不可靠。
例如:
0.00001x1,2x212x,3x2
12
用顺序消去法求解(4位浮点数进行运算),有
~4
0.000010002.0001.0000.100010
2.0001.000
2.0003.0002.00066
0.000~0.400010~0.200010
回代求得:
x20.5000,x10.0000
与方程组的准确解x20.499998,
x10.250001相比,严重失真。
为了避免上述高斯消去法中数值计算的不稳定性,一般要在每次归一化之前增加一个选主元的过程,将绝对值最大或
16
较大的元素交换到主元素的位置上。
列选主元(简称列主元)
列主元的思想是:
当变换到第k步时,从第k列akk以下
(包括akk)的各元素中选出绝对值最大者,然后通过行
变换将它交换到主元素akk的位置上。
即选取aikk,满足:
(k)|ai(kkk)|max|aik|,进行k行与ik互换(即相当于左
乘Ik,ik)。
kin
(k)
对于上例,我们有:
0.000010002.0001.0002.000
3.0002.0002.0003.0002.0000.000010002.0001.000
2.0003.0002.000
0.00002.0001.000
回代求得:
x20.5000,x10.2500。
在求解线性代数方程组的高斯消去法中,交换系数矩阵中
的两行(包括常数向量中的两个对应元素),只相当于交换
了两个方程的位置。
因此,采用列主元的高斯消去法是不影
响求解
结果的。
列主元保证了当前的主元素akk是第
k列中akk以下元素
17
中的绝对值最大者,但还不能保证它是同一行(即第k行)中的绝对值最大者。
因此,经过列选主元后,虽然避免了akk=0,但其计算过程还是不稳定的,不适于求解大规模的线性方程组。
全选主元(简称为全主元)
全主元的基本思想是:
当变换到第k步时,从系数矩阵的
右下角,n~k,1,阶矩阵中选取绝对值最大的元素,然后通过行,列变换将它交换到主元素akk的位置上。
在求解线性代数方程组的高斯消去法的变换过程中,虽然行交换不影响最后求解的结果,但列交换将会导致最后结果(即
解向量)中对应未知数的次序混乱。
即在进行列交换时,相应
的两个未知数的次序也被交换了。
因此,在使用全主元的高斯消去法时,必须在选主元过程中记住所进行的一切列交换,以便对最后结果进行恢复。
(*)高斯-约当消去法
高斯-约当(Gauss-Jordan)消去法是一种无回代过程的求解线性代数方程组的直接解法。
这种方法的基本的思想是:
通过一系列的初等行变换,直
接将系数矩阵变换成单位矩阵,常数向量作同样的变换,则常数向量就为解向量。
这种消去法的基本过程与高斯消去
18
法相同,只是在消元过程中,不仅将主对角线以下的元素消为0,而且同时将主对角线以上的元素也消为0。
显然,在这种情况下,回代过程就没有必要了。
同样的道理,在高斯一约消去法中,为了计算过程的稳定性,也需要进行全选主元。
高斯-约当消去的基本思想可以用在矩阵求逆中。
矩阵的LU分解
前面给出的LU分解,是在高斯消去法的基础上给出的
LU分解,实际上也可以直接从矩阵出发进行矩阵分解。
当A作
了LU分解后,就可以通过方程组(2.1.19):
Lyb
Uxy
容易得到线性方程组的求解(前代法和回代法)。
设实矩阵A的各阶主子式det(Ai)0(i1,2,,n),则可以对A进行如下分解(杜利特尔Doolittle分解):
ALU
其中,L为主对角元素全为1的下三角矩阵(即单位下三角矩阵),U为上三角矩阵。
下面先从高斯消去法的基本原理来说明这种分解的具
19
体过程
在高斯消去法中,如果去掉归一化这一步,同样可以将原矩阵变换成上三角矩阵,只是主对角线上的元素不是1。
因此,在没有归一化的消去法中,实际上就是通过一系列的初等行变换
依次将主对角线以下的元素消为0,而这一系列的初等行变换就相当于用一系列的初等矩阵左乘矩阵A。
(1)首先,为了使矩阵A的第一列中a11以下的元素变为0,可以用一个初等矩阵:
1
~l21
L1~l31
~ln1
左乘矩阵A,即
101
001
1a11a12a13~l
121a21a22a23
aL1A~l3101a32a3331
20
~l001aan2an3n1n1
a1n
a2na3n
ann
a11a12a13a1n,1,,1,,1,0a22a23a2n
1,,1,,1,
(1)
0a32a33a3An
1,,1,
(1)0an2an3ann
为了使上式运算成立,初等矩阵L1中的元素lij必须满足下列关系:
ai1~li1a110,i2,3,,n即
li1aija11,i2,3,,n
而在新矩阵中,除第一行中,其余各元素相应满足下列关系:
1,aijaij~li1a1j,i2,3,,n;j2,3,,n
21
(2)按以上方法继续往下做。
假设已经做了k-1步,原
矩阵A已经变为:
(k~1)ALk~1L2L1A
a11000a12
1,
a22
a13a1k
1,a23,2,a33
1,a2k,2,a3k
a1,k,1
1,a2,k,1
a1n
1,
a2n
00,2,,2,
a3,k,1a3n
0
(k~1)
akk
(k~1)
ak,k,1
k~1,
22
akn
0000
进行第k步变换,即
A(k)L(k~1)
k
Aa11
a12
a130a,1,
21
a,1,2300a,2,33
0
000000
1
01
001
其中L000k
000000a(k~1)
23
a(k~1)k,1,k
k,1,k,a,k~1,1
k,1,na(k~1)
a(k~1)
n,kn,k,1
a,k~1,nn
a1k
a1,k,1a1n
a,1,2ka,1,2,k,1a,1,
2na,1,3k
a,1,3,k,1
a,1,3n
a(k~1)
a(k~1),k~1,kk
k,k,1akn0a(k),k,k,1,k,1ak,1,n
0
a(k),k,n,k,1ann
24
1~lk,1,k1
~lnk,0
1
同样,为了使上式运算成立,初等矩阵Lk中的元素lik必
须满足下列关系:
k,
(k~1)
(k~1)
aijaik~likakj
ik,1,,n;jk,1,,n
k~1,,k~1,
la/a,ik,1,,nikikkk
如此继续下去,则有:
A(n~1)Ln~1LkL2L1A
(n~1)
(n~1)A其中为上三角矩阵。
令UA
,则有ULn~1LkL2L1A
25
最后可以得到
ALU
~1
~1
其中,L
L1L2Ln~1,L为单位下三角矩阵,即
1l211L
lk1lk21
ln1ln2lnk1
~1
由此可以看出,矩阵A在一定条件下(各阶主子式异于
零)可以分解成单位下三角矩阵L和上三角矩阵U的乘积,
即若令
ALU
u11l21
QL,U~In
lk1
ln1
u12u1ku22u2k
26
lk2ukk
u12u2n
ukn
ln2lnkunn
则对矩阵A进行三角分解的问题化为A变成Q的问题了。
由前面的叙述可以看出,在消元过程中,通过k步的消元后,第k行的元素不变,即
k~1,
ukjakj,jk,k,1,,n
而初等矩阵Lk中的元素lik满足如下关系:
k~1,,k~1,
la/a,ik,1,,nikkikk
且第k行、第k列以后的元素也相应地作如下变换:
k,(k~1)(k~1)aijaik~likakj,ik,1,,n;
jk,k,1,,n
但在实际计算过程中,为了节省存储空间和简化计算步骤,对于Q矩阵的各元素仍可以存放在原矩阵的空间中。
这样,以上的三个计算步骤实际上变为
aik/akkaik,ik,1,,n
27
aij~aikakjaij,ik,1,,n;jk,1,,n求得Q矩阵后,就可以立即得到L和U矩阵了。
3
O(n)。
矩阵三角分解的计算工作量(乘作法次数)为
下面举例说明矩阵三角分解的过程。
例设矩阵
244
233126
A
24~12421
1
求L和U。
解首先求出Q矩阵,其计算过程如下:
2
44
22
442
3126~363A32
4~12k13/210~504211
2
~6
28
~7
~3
(l3
212
l311,l412;u112,u124,u134,u142)
24422442
k3/2~3633/2~363210~50k
310~5022~19~92
2
19/5
~9
(l320,l422;u22~3,u236,u243)(l43
19
5
;u33~5,u340;u44~9)由此可以分离出L和U如下:
10
0
2442
L
3/21000~631010,
29
U
3
00~502
219/51
000
~9
矩阵形式的Doolittle分解法
设实矩阵A的各阶主子式det(Ai)0(i1,2,,n),对
A进行如下LU分解:
其中
ALU
1u11u12u13u1nuu
ul122232n21
Uu33u3nLl31l321
,
lll
unn1n1n2n,n~1
由矩阵相等条件,可通过aij导出计算lij和uij的公式:
(1)由a1i由ai1
u1i,得u1ia1i(i1,2,,n);
li1u11,得li1ai1/u11(i2,3,,n)l21u1i,u2i,
30
得
(2)由a2i
u2i由ai2
a2i~l21u1i(i2,3,,n)(ai2~li1u12)/u22
(i3,4,,n)
li1u12,li2u22,得
li2
(3)一般地,在求出U的前k~1行与L的前k~1列后,U
的k行、L的k列元为:
ukiaki~lkjuji(ik,k,1,,n)
j1
k~1
lik(aik~lijujk)/ukk(ik,1,k,2,,n)
j1
k~1
nn
AR矩阵三角分解基本定理设,若A的顺序主子
式det(Ak)0(k1,2,,n),则存在唯一的Doolittle分
解:
ALU
31
唯一性:
若A存在两个Doolittle分解:
AL1U1和AL1U1则
1~1
L1U1L2U
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 线性方程组 解法 例题