第二章线性代数方程组的直接解法
教学目标：
1.了解线性代数方程组的结构、基本理论以及相关解法的发展历程；
2.掌握高斯消去法的原理和计算步骤，理解顺序消去法能够实现的条件，并在此基础上理解矩阵的三角分解（即LU分解），能应用高斯消去法熟练计算简单的线性代数方程组；
3.在理解高斯消去法的缺点的基础上，掌握有换行步骤的高斯消去法，从而理解和掌握选主元素的高斯消去法，尤其是列主元素消去法的理论和计算步骤，并能灵活的应用于实际中。
教学重点：
1. 高斯消去法的原理和计算步骤；
2. 顺序消去法能够实现的条件；
3. 矩阵的三角分解（即LU分解）；
4. 列主元素消去法的理论和计算步骤。
教学难点：
1. 高斯消去法的原理和计算步骤；
2. 矩阵的三角分解（即LU分解）；
3. 列主元素消去法的理论和计算步骤。
教学方法：
教具：
引言
在自然科学和工程技术中，许多问题的解决常常归结为线性方程组的求解，有的问题的数学模型中虽不直接表现为线性方程组，但它的数值解法中将问题“离散化”或“线性化”为线性方程组。例如，电学中的网络问题、船体数学放样中建立三次样条函数问题、最小二乘法用于求解实验数据的曲线拟合问题、求解非线性方程组问题、用差分法或有限元法求解常微分方程边值问题及偏微分方程的定解问题，都要导致求解一个或若干个线性方程组的问题。
目前，计算机上解线性方程组的数值方法尽管很多，但归纳起来，大致可以分为两大类：一类是直接法（也称精确解法）；另一类是迭代法。例如线性代数中的Cramer法则就是一种直接法，但其对高阶方程组计算量太大，不是一种实用的算法。实用的直接法中具有代表性的算法是高斯（Gauss）消元法，其它算法都是它的变形和应用。
在数值计算历史上，直接法和迭代法交替生辉。一种解法的兴旺与计算机的硬件环境和问题规模是密切相关的。一般说来，对同等规模的线性方程组，直接法对计算机的要求高于迭代法。对于中、低阶（200
n ）以及高阶带形的线性方程组，由于直接法的准确性和可靠性高，一般都用直接法求解。对于一般高阶方程组，特别是系数矩阵为大型稀疏矩阵的线性方程组用迭代法有效。
§2.1 基本定理和问题
设具有n 个未知数的n 个方程的线性方程组为
11112211
211222221122n n n n n n nn n n
a x a x a x
b a x a x a x b a x a x a x b +++=??+++=????++
+=? （2.1）
或
1
n
ij j i j a x b ==∑（1,2,
,i n =） （2.1）’
其矩阵形式可以表示为
Ax b = （2.2）
其中
1112121
22
212
n n n n nn a a a a a a A a a a ?? ? ?
= ?
???
12(,,,)T n x x x x = 12(,,
,)T n b b b b =
其增广矩阵为
1,1111212,121
222,112[|]n n n n
n n n n nn a a a a a a a a A A b a a a a +++?? ?
?== ? ? ???
（,1i n i a b +=，1,2,,i n =） （2.3） 则方程组（2.1）、（2.1）’或（2.2）和（2.3）是一一对应的。
若用()r A 表示矩阵A 的秩，则有关于线性方程组（2.2）的解的存在性的基本定理（在高等代数或线性代数中有证明）：
定理2.1 （1）方程组（2.2）有解的充分必要条件是()()r A r A =； （2）若()()r A r A k n ==<，则方程组（2.2）具有一族解，其解可表示为
()1n k
i i i x x c x -*
==+∑
其中x *为Ax b =的任一特解，()i x 是齐次方程组0Ax =的解，且(1)(2)(),,,n k x x x -线
性无关，i c 为任意常数。
（3）若()()r A r A n ==，则方程组（2.2）有唯一解。
定义 2.1 如果两个方程组的解相同，则称这两个方程组为同解（等价）方程组。
不难证明：将方程组中任意两个方程交换次序，所得方程组和原方程组为同解方程组；将方程组中任一方程的一个倍数加到另一个方程上，所得方程组和原方程组为同解方程组。
用()i E 表示（2.1）的第i 个方程或（2.3）的第i 行，记（2.3）的第i 行与第j 行互换为()()i j E E ?，而（2.3）的第j 行乘以0α≠加到第i 行记为
()()j i i E E E α+→。这是矩阵的初等变换，相当于[|]A b 左乘一个初等矩阵。同样
的运算符号，我们也理解为方程组（2.1）作相应的变换。经过这些变换后得到的方程组与方程组（2.1）同解（或等价）。
对于线性方程组（2.2）的求解，在理论上并不存在困难。若()r A n =，即A 为非奇异（可逆）矩阵，它的行列式det 0D A =≠，则应用Cramer 法则可求得
i i D
x D =（1,2,,i n =）
其中i D 是用b 代替A 中第i 列而得到的相应的行列式。然而在实际中，当未知数的个数n 比较大时，按Cramer 法则进行计算，其工作量就会大得惊人，因而该方法在实际操作中并不可行。n 阶行列式共有!n 项，每项都有n 个因子，所以计算一个n 阶行列式需要做(1)!n n -?次乘法，我们共需要计算1n +个行列式，要计算出i x ，还要做n 次除法，因此用Cramer 法则求解线性方程组（2.2）就要做
2(1)(1)!(1)!N n n n n n n n =+?-?+=-?+
次乘除法（不计加减法）。如10n =时，359251210N =；当20n =时，
209.707310N ≈?，可见，在实际计算中Cramer 法则几乎没有什么用处。本章的
主要目的就是研究求解线性方程组（2.2）的有效算法。
某一算法的效率可以用下列两个主要的准则来判断：（1）该算法的计算速度如何？即计算中要设计多少次运算？（2）计算所得到解的精度如何？
这两个准则是针对在计算机上求解高阶方程组而提出的。由于线性方程组阶数很高时求解所需要的计算量极其巨大，因而很自然地提出准则（1）。准则（2）的提出，是由于在实际问题当中舍入误差的影响，可能使计算解产生偏离真实解的不可忽视的误差。特别地，在解高阶方程组时涉及大量的运算，舍入误差潜在地积累有可能造成计算解对真实解的严重偏离。后续章节还要详细地研究误差的影响。在研究（2.2）的数值方法之前，先考察一下求解中会遇到的一些困难，
这有助于理解后面将要提出的一些数值计算方法。
§2.2 Gauss 消去法
从这一节开始，我们来讨论线性方程组（2.1）或（2.2）的直接解法。所谓直接法，就是它只包含有限次的四则运算，若假定每一步运算过程中都不产生舍入误差，计算的结果就是方程组的精确解。这种方法中最基本和最简单的就是Gauss 消去法及其变形。
2.2.1 Gauss 消去法的计算过程
设方程组（2.1）或（2.2）的系数矩阵A 非奇异，并记
(1)ij ij a a =，1,2,
,i n =，1,2,,,1j n n =+
(1)(1)[|][|]A b A b =
这样方程组（2.2）又记为(1)(1)A x b =。
要完成Gauss 消去法的第1步须先假定(1)11
0a ≠，令(1)1
1(1)11
i i a l a =（2,
,i n =）
，则运算11()()i i i l E E E -+→（2,
,i n =）将(1)(1)[|]A b 变换为
(1)
(1)(1)(1)1,111
121(2)(2)(2)
2,1(2)(2)22
2(2)(2)(2)
,12
[|]n n
n n n n n nn a a a a a a a A b a a a +++??
? ?
=
? ? ??
?
（2.4） 其中
(2)
(1)(1)11ij
ij
i j
a
a l a =-，(1)1
1(1)11
i i a l a =，2,,i n =，2,,1j n =+
对应（2.4）的方程组是(2)(2)A x b =，它与（2.2）等价，而其第2至第n 个方程中的1x 项已经消去。
一般地，设消去法已进行了1k -步，得到方程组()()k k A x b =。此时对应的增广矩阵为
(1)
(1)(1)(1)1,111121(2)(2)(2)2,122
2()()
()()()
,1()()()
,1[|]n n
n n
k k k k k k n kk
kn k k k n n nk
nn a a a a a a a A b a a a a a a ++++?? ? ?
?
?= ?
? ? ??
?
（2.5） 假设()0k kk
a
≠，令()()k ik
ik k kk
a l a =（1,
,i k n =+），则运算()()
ik k i i l E E E -+→（1,,i k n =+）的结果是方程组(1)(1)k k A x b ++=，对应增广矩阵为(1)(1)[|]k k A b ++，
其中的元素为
()
(1)()(),1,,;1,,1
,1,,;1,,10,1,,k ij k k k ij
ij ik kj a i k j n a a l a i k n j k n i k n +?==+?=-=+=++??=+?
（2.6）
()()
/,1,
,k k ik ik kk l a a i k n ==+
如果依次有()
0k kk
a ≠（1,,1k n =-）
，则可进行第1n -步，得到与（ 2.2）等价的方程组()()n n A x b =，其中()n A 是一个上三角阵，且
(1)
(1)(1)(1)1,111
121(2)(2)(2)2,1()()22
2()()
,1[|]n n
n n n n n n n n nn a a a a a a a A b a a +++??
? ?
=
? ? ??
?
这样就完成了消去过程。因为A 非奇异，故有()
0n nn
a ≠。接下来解()()n n A x
b =，因为()n A 是上三角阵，这只要用逐次向后代入的方法即可，这个过程称为回代过程，其计算公式为
()
,1
()
()()
,11
()
,1,2,,1n n n n n nn
n i i i n ij j
j i i i ii a x a a a x x i n n a ++=+?=????-?
?==--??
∑ （2.7） 以上有消去过程和回代过程合起来求出（2.2）的解的过程就称为Gauss 消去法，或称为顺序Gauss 消去法。
从（2.6）可以看出，消去过程的第k 步共含有除法运算n k -次，乘法和减
法运算各()(1)n k n k -+-次，所以消去过程共含有乘除法次数为
321
1
11
5()()(1)326n n k k n n n
n k n k n k --==-+-+-=+-∑∑ 含加减法次数为
31
1
()(1)33n k n n
n k n k -=-+-=-∑
而回代过程含乘除法次数为
(1)2n n +，加减法次数为(1)2
n n -，所以Gauss 消去法总的乘除法次数为332
333n n n n +-≈，加减法次数为32353263
n n n n +-
≈。 当10n =时，用Cramer 法则需要8359251210 3.610≈?乘除法，而用Gauss 消去法仅需430次乘除法运算。
例2.1 用Gauss 消去法解方程组：
（1）12312314012824113x x x ?????? ??? ?= ??? ? ??? ???????
（2）1234123341518311151111631112x x x x -?????? ? ? ?---- ? ? ?= ? ? ? ? ? ?
-????
?? 解：（1）对增广矩阵进行初等变换
133(2)1231412314012801282411300515E E E -+→????
? ??????→ ? ? ? ?--????
得等价的方程组1232332314
28515
x x x x x x ++=??
+=??-=-?
，解得33x =，22x =，11x =。
（2）对增广矩阵进行初等变换
122133144
3
()21
()121
()412334153715123341505
22218311155321911116044343111277
70
0444E E E E E E E E E +→-+→-+→-??
??-? ?- ? ?---- ? ???????→ ? ? ? ?
?-?? ?-- ?
?
?
233244344
5
()6
77()()6
11
123341233
4151537370505151522222211
29
11
29
00
0111136367
3579100
00
003633E E E E E E E E E +→+→-+→--????
?
? ? ?-- ? ? ? ??????→??????→ ? ?
?
? ?
? ? ????
?
得等价方程组
123423434412334153715
52221129
1136
910
33x x x x x x x x x x -++=??
?-++=??
?+=??
?=?? 回代得40x =，33x =，22x =，11x =。
2.2.2 消去法的进一步讨论，矩阵的LU 分解
从上面的消去过程可以看出，Gauss 消去步骤能顺序进行的条件是
(1)(2)(1)
11221,1,,
,n n n a a a ---全不为零。设矩阵A 的顺序主子式为i ?，即
11
11
i
i i ii
a a a a ?=
，1,2,
,i n = （2.8）
则有下面的定理：
定理 2.2 ()
i ii a （1,2,
,i k =）全不为零的充分必要条件是A 的顺序主子式
0i ?≠（1,2,
,i k =），其中k n ≤。
证明：设()
0i ii
a ≠（1,2,,i k =），则可以进行消去法的1k -步，每步()m A 由A
逐次实行()()ij j i i l E E E -+→的运算得到，这些运算不改变相应顺序主子式之值，
所以有
(1)(1)(1)11
121(2)(2)(1)(2)()
22
21122()m m m
m mm
m mm
a a a a a a a a a ?=
= 这样便有0m ?≠（1,2,
,m k =）
，必要性得证。 用归纳法证明充分性。1k =时显然成立。设命题对1k -成立。现设
110,
,0,0k k -?≠?≠?≠。由归纳假设有(1)
(1)
111,10,
,0k k k a a ---≠≠，
Gauss 消去法就可以进行1k -步，A 约化为
()
()
()
1112
()22k k k k A A A O A ??= ???
其中()11k A 是对角元为(1)(2)
(1)11221,1
,,,k k k a a a ---的上三角阵。因为()
k A 是通过消去法由A 逐步得到的，A 的k 阶顺序主子式等于()k A 的k 阶顺序主子式，即
()
(1)
(1)()11
111,1,()*k k k k k k k k k kk
A a a a O
a ---?=
=
由0k ?≠可推出()
,0k k k a ≠。
定理 2.3 对方程组Ax b =，其中A 非奇异，若A 的顺序主子式均不为零，则可以Gauss 消去法求出方程组的解。
定义 2.2 设矩阵()ij n n A a ?=每一行对角元素的绝对值都大于同行其它元素绝对值之和，即1||||n
ii ij j j i a a =≠>∑，1,2,
,i n =，则称A 为严格（行）对角占优矩阵。
定理 2.4 设线性方程组Ax b =的系数矩阵为严格对角占优矩阵，则用顺序
Gauss 消去法求解时()
i ii a （1,2,
,i k =）全不为零。
证明：（略）
下面我们来讨论Gauss 消去过程用矩阵运算表示的形式。 第1步令(1)A A =，作一次运算11()()i i i l E E E -+→，2,,i n =，这相当于A
左乘矩阵
1
11
1i i M l ?? ? ?
?=- ? ? ??
?
，2,,i n =
第1步的全过程相当于(1)(1)(2)(2)1[|][|]L A b A b =，其中
21
11
21111n n n l L M M M l -?? ?- ?== ? ?-??
设1k -步后系数矩阵化为()k A ，其分块形式写成 ()()
(1)()
1112
12
1()22k k k k k k A A L L L A A
O A --??== ???
其中()11k A 为上三角的1k -阶方阵，()
22k A 为1n k -+阶方阵，设其左上角元素()
0k kk a ≠，则下一步的乘数为()()/k k ik ik kk l a a =，1,
,i k n =+。若记
(0,
,0,1,0,
,0)T k e =是第k 个分量为
1的单位向量，记
()1,(0,
,0,,
,)k T k k nk l l l +=，其前k 个分量为零，从而有()
0T k k
e l =。第k 步中系数矩阵的约化可用矩阵运算描述为 (1)
(1)
()
(1)
1112
(1)22k k k k k k A A L A
A
O A ++++??== ???
其中(1)11k A +是上三角的k 阶矩阵，(1)
22k A +是n k -阶方阵，而
()1,1
11
1k T
k k k k nk
L I l e l l +?? ? ? ?
=-=
?- ? ? ? ?-?
?
（2.9） 可以验证
()()()()()()()()k T k T k T k T
k
k k k I l e I l e I l e I l e -+=+- ()()()k T k T
k k I l e l e I =-=
即有1()1()()k T k T
k k k L I l e I l e --=-=+。这样，经过1n -步得到(1)()n 121n n L L L A A --=，
这里的()n A 是上三角阵，记()n U A =，又记
1(1)(1)1
111()()
()T
n T
n n L L L I l e I l e ----==++
21313212
,11
11
11n n n n l l l l
l l -??
? ?
?= ? ? ???
（2.10） L 是一个对角线元素全为1的下三角阵，这种矩阵称为单位下三角阵。L 的对角线以下元素就是各步消去的乘数。最后我们可以得到A LU =，其中L 是一个单位下三角阵，U 是一个上三角阵。
定义 2.3 将矩阵A 分解为一个下三角矩阵L 和一个上三角矩阵U 的乘积A LU =，称为对矩阵A 的LU 分解或三角分解。当L 是单位下三角矩阵时称为Doolittle （杜里克尔）分解。当U 是单位上三角矩阵时称为Crout （克洛特）分解。
由上面的分析过程知，Gauss 消去法的实质是将系数矩阵分解为一个下三角矩阵和一个上三角矩阵相乘，即将系数矩阵进行LU 分解。
在矩阵A 的LU 分解A LU =中，我们将U 写成U DU =，其中D 是对角矩阵，
U 是单位上三角阵，进一步记L LD =，它是一个下三角阵，这样有
()A LU LDU LD U LU ====
其中L 是一个下三角阵，U 是单位上三角阵，此即A 的Crout 分解。
在矩阵A 的Doolittle 分解A LU =中，我们将上三角阵U 写成DU 的形式，这里的D 为对角阵，U 为单位上三角阵，这样得到A LDU =，其中L 为单位下三角阵，D 为对角阵，U 为单位上三角阵，称其为A 的LDU 分解。
定理2.5 设非奇异矩阵n n A R ?∈，若其顺序主子式(1,
,1)i i n ?=-都不等于
零，则存在唯一的单位下三角阵L 和上三角阵U ，使A LU =。
证明：上面的分析过程已经说明了非奇异矩阵A 可作LU 分解，下面只需证明分解的唯一性。
设A 有两个分解式11A LU =和22A L U =，
其中12,L L 都是单位下三角阵，12,U U 都是上三角阵，则有1122LU L U =。因为A 非奇异，从而12,L L ，12,U U 都可逆。故
在1122
LU L U =两边同时左乘11L -和右乘12U -，这样得到111212U U L L --=。因为1
2U -仍为上三角阵，故112U U -也是上三角阵，同理可得1
1
2L L -是单位下三角阵，结合
111212U U L L --=知只可能11
1212U U L L I --==，即有12L L =，12U U =。证毕
可以证明，对于奇异矩阵n n A R ?∈依然满足定理2.5。而且，从上面的推导过程可以看到，对A 作LU 分解时，其中的U 为
(1)(1)(1)1112
111
121(2)(2)222222()n n n n
n nn
nn
u u u a a a u u a a U u a =
=
还可以验证A 的顺序主子式为对应的L 和U 的顺序主子式的乘积，而A 的m 阶顺序主子式满足1122
m mm u u u ?=，1,2,
,m n =。
定理2.6 非奇异矩阵n n A R ?∈有唯一的LDU 分解的充分必要条件是A 的顺序主子式(1,
,1)i i n ?=-都不等于零。
§2.3 主元素消去法
2.3.1 有换行步骤的消去法
顺序Gauss 消去法可以进行的条件是()
0(1,2,,1)i ii
a i n ≠=-，如果有某个
()
0i ii a =，消去法就不能继续使用。例如，若110a =，则第1步就不能进行，但我
们可以在A 的第1列中找出一个非零元1i a ，进行换行1()()i E E ?后再做消去法，其他各步可以类似处理。
有时候虽然()0i ii
a ≠，但()
||i ii a 很小，顺序Gauss 消去法可以顺利进行下去，但计算过程舍入误差导致误差增长过大，以致结果不可靠，此时称()
i ii a 为小主元。
例2.2 用三位十进制浮点运算求解
512121.0010 1.00 1.00
1.00 1.00
2.00
x x x x -??+=?
+=? 解：不难发现这个方程组的准确解应该接近(1.00,1.00)T 。下面我们用顺序Gauss 消去法来求解，则有
5212111
1.0010a l a =
=?，(2)
522
222112 1.00 1.0010a a l a =-=-? (2)523232113 2.00 1.0010a a l a =-=-?
在三位十进制运算的限制下，得到
(2)23
2(2)22
1.00a x a ==
代回第一个方程得10x =。这显然不正确。
从上例的计算过程不难发现，计算解产生误差的原因是小主元做除数。因此，为使这种不稳定现象发生的可能性减至最小，在每一步就要寻找一个远不是零的
数作除数，既要寻找()k k i i k ≥使()()
||max ||k k k i k ik
k i n
a a ≤≤=，并将第k i 行与第k 行对换。这样()k kk a 的当前值就远不是零，这时的元素()
k kk a 称为k 列的主元素，k i 行叫做主元素
行，这样就引出了列主元消去法。
2.3.2 列主元消去法与完全主元消去法
列主元消去法也称为按列部分选主元的消去法。其具体过程如下：
进行第1步之前，在A 的第1列中选出绝对值最大的元素1(1)1
i a ，即1(1)(1)1
11||max ||i i i n
a a ≤≤=，其中11i ≥。因为A 非奇异，故有1(1)
10i a ≠。若11i =，则消去过程与顺序Gauss 消去法一样；若11i >，则先进行换行11()()i E E ?，然后类似顺序Gauss 消去法的运算得到(2)(2)[|]A b 。
一般地，设进行了1k -步选主元和消去法的步骤，得到()()[|]k k A b 。第k 步
先选主元()k k i k a ，使()()
||max ||k k k i k ik
k i n
a a ≤≤=，即在()k A 的第k 列的对角线及对角线以下的元素中选出绝对值最大值()k k i k a ，显然k i k ≥，且由于()k A 非奇异，从而有()0k k i k a ≠。若k i k =，则进行顺序Gauss 消去法的第k 步；若k i k >，则对()()[|]k k A
b 先换行
()()k k i E E ?，然后进行类似Gauss 消去法的运算。
如上进行1n -步选主元、换行与消去法运算，得到()()n n A x b =，其中()n A 是一个上三角阵，再回代进行求解。
列主元消去算法：
1、消去过程：对1,2,,1k n =-
（1）选主元：找{,
,}k i k n ∈，使()()
||max ||k k k i k ik k i n
a a ≤≤=；
（2）若()0k k i k a =，则停止计算（det ||0A A ==）； （3）若k i k ≠，则换行()()k k i E E ?；
（4）消元： 对1,
,i k n =+，()()
/k k ik ik
kk l a a =；对1,,1j k n =++，(1)()()
k k k ij ij ik kj
a a l a +=- 2、回代过程：
（1）若()
0n nn a =，则停止计算（det ||0A A ==）；
（2）(),1()n n n n n nn
a x a +=
；
（3）对1,2,
,1i n n =--，()(),1
1()n
i i i n ij
j
j i i i ii
a
a
x x a
+=+-
=
∑。
完全主元消去法：在列主元消去算法的过程中，不是按列来选主元，而是在
()
k A 右下角的1n k -+阶子阵中选主元()k k k i j a ，即()()
||max ||k k k k i j ij k i n
k j n
a a ≤≤≤≤=，然后将
()()[|]k k A b 的第k i 行与第k 行、第k j 列与第k 列交换，再进行消去运算。
完全主元法比列主元法运算量大得多，可以证明列主元消去法的舍入误差一般已比较小，在实际计算中多用列主元法。
例2.3 用列主元消去法解方程组Ax b =，计算过程取五位数字，其中
0.002220.4[|]10.7812501.38163.996 5.562547.4178A b ?-? ?
= ? ???
解：
(1)(1)0.002220.4[|][|]10.7812501.38167.41783.996 5.56254A b A b ??- ?== ? ???
(1)
31
3.996a = 13()()
3.996 5.562547.417810.7812501.38160.002220.4E E ???
?????→ ? ?-??
21311/3.9960.250250.002/3.9960.00050050l l ===-=-
2211233113()()
()()
(2)(2) 3.996 5.562547.4178[|]00.61077 1.00100.474710.403710 2.0028 2.0020E l E E E l E E A b -→-→??
???????→=--- ? ???
(2)
32
2.0028a = 23()()
3.996 5.562547.41780 2.0028 2.00200.4037100.61077 1.00100.47471E E ???
?????→ ? ?---??
320.610770.304962.0028l -==-
33222()()
(3)(3) 3.996 5.562547.4178[|]0 2.0028 2.00200.40371000.390470.35159E l E E A b -→?? ???????→= ? ?--??
回代得：
30.90043x =，20.69850x =-，1 1.9273x =。
其精确解为
(1.92730,0.698496,0.900423)T x =-
而用顺序Gauss 消去法，则可解得
(1.9300,0.68695,0.88888)T x =-
这个结果误差比较大，这是因为消去法的第1步中，(1)
11a 按绝对值比其他元素小
很多所引起的。
§2.4 直接三角分解法
Gauss 消去法还有许多变形，有些变形是为了利用特殊技巧减少误差，把Gauss 消去法改写为更紧凑的形式，还有一些变形时根据某类矩阵的特性作一些修正和简化，这些方法可统称为直接三角分解法。
2.4.1 矩阵的三角分解
设A 的顺序主子式0(1,2,
,)k k n ?≠=，则可建立线性方程组Ax b =的Gauss
消去法与矩阵分解的关系，即矩阵A 的LU 分解。这个问题前面已经讲的比较详
细了，此处不再赘述。
2.4.2 Doolittle 分解法
首先假设A 的顺序主子式k ?都不为零，则A 可作Doolittle 分解，即
A LU =，其中L 是单位下三角阵，有1ii l =，i j <时0ij l =；U 是上三角阵，i j >时0ij u =。仔细写出为
111211112121
22
22122
2121211
1n n n n n n nn n n nn a a a u u u a a a l u u A LU a a a l l u ?????? ?
??
? ? ???
=== ? ???
?
?????????
（2.11） 在前面逐步推导L 和U 的元素公式都要借助于有关的()
k ij a 来表示。现在强调
指出，只要从给定的A 通过比较（2.11）式的两边就可能逐步地把L 和U 构造出来，而不必利用Gauss 消去法的中间结果，这种方法称为Gauss 消去法的紧凑格
式。
根据矩阵的乘法规则，比较（2.11）式的两边可得
min(,)
1
i j ij ik kj k a l u ==
∑
，,1,2,
,i j n = （2.12）
先算出U 的第1行，在（2.12）令1i =，由111l =，10(1)j l j n =<≤可得
11j j u a =，1,2,
,j n =
接着在（2.12）中令1j =，由1111i i a l u =?，从而算出L 的第1列
1111111//i i i l a u a a ==，2,
,i n =
若U 的第1至1k -行和L 的第1至1k -列已经算出，则由（2.12）可计算出U 的第k 行元素
1
1k kj kj kr rj r u a l u -==-∑，,1,
,j k k n =+ （2.13）
接着再计算出L 的第k 列元素
1
1
k ik ir rk
r ik kk
a l u l u -=-=
∑，1,,j k n =+ （2.14）
解方程组Ax b =就化为求解LUx b =，分两步求解。第一步解Ly b =，其中L 为下三角阵，只要用逐次向前代入的方法；第二步解Ux y =，其中U 为上三角阵，用逐次向后代入方法即可解除x 。 例2.4 用Doolittle 方法求解：
123462116241011141510135x x x x -?????? ? ? ?- ? ? ?= ? ? ?- ? ? ?---????
?? 解：第1步算出L 和U ：
111311
16
5119
1610
37L ?? ? ? ? ?=
? ? ?-
- ???，6211102
133337910
1019174U -??
?
? ? ?=-
? ? ?
??
?
第2步解Ly b =得：
231916,3,,574T
y ?
?=- ??
?
第3步解Ux y =得：
(1,1,1,1)T x =--
例2.5 应用Doolittle 方法求解线性方程组：
1231231220223332
x x x x x x x x ++=??
++=??--=?
解：下面用箭头表示A 作LU 分解过程
121121121121223223221221130130111101222????
? ?
????
? ? ? ?→→-→- ? ? ? ? ? ? ? ?----????-- ? ?
???? 则求得
1211112L ?? ? ?= ? ?- ???，1212112U ??
? ?
=- ? ?
?
??
解Ly b =，即解
123102131
21
12y y y ?? ????? ? ? ?= ? ? ? ? ? ?????- ???
解得10y =，23y =，31
2
y =
。 最后解Ux y =，即解
12312102131122x x x ?
??? ? ???
? ? ?-= ? ? ? ? ? ??? ? ?
????
解得11x =，21x =-，31x =。故原方程组的解为(1,1,1)T x =-。
例2.6 用直接三角分解法解
123123142521831520x x x ?????? ??? ?= ??? ? ??? ???????
解：设系数矩阵做了如下三角分解
1112
132122233132
3312310025210031510
0u u u l u u l l u ??????
? ??
?= ? ??? ? ?????????
根据矩阵乘法可得
1111111u u ?=?=，21112122l u l =?= 1212122u u ?=?=，31113133l u l =?= 1313133u u ?=?=，2112222251l u u u +=?= 311232223215l u l u l +=?=-，2113232324l u u u +=?=- 311332233333524l u l u u u ++=?=-
于是原方程组可表示为
1231001231421001418351002420x x x ????????
????? ?-= ????? ? ????? ?--????????
求解
123100142101835120y y y ??????
??? ?= ??? ? ??? ?-??????
得(14,10,72)T y =--。
求解
1231231401410002472x x x ?????? ??? ?-=- ??? ? ??? ?--??????
得(1,2,3)T x =。
设有三元非齐次线性方程组 线性方程组解的几何意义 ???????=++=++=++,,,)1(22221111m m m m d z c y b x a d z c y b x a d z c y b x a 我们来讨论一下三元非齐次线性方程组解的几何意义.
2) 有唯一解这时方程组(1) 中的m 个方?? ???=+--=--=+,423, 32,123z y x y x z x 该方程组有唯一解.817,21,4 7??? ??--则方程组(1) 的解有以下三种情况: 1) 无解这时方程组(1) 中的m 个方程所表示的平面既不交于一点, 也不共线、共面. 程所表示的平面交于一点. 例如
其几何意义如图3 -11 所示. 2x-y=-3 3x+2z=-1 x-3y+2z=4 图3-11
交直线所确定.3) 有无穷多组解 这时又可分为两种情形:情形一自由变量, 基础解系中有两个向量，其一般解的形式为 γ=c 1η1+ c 2η2+ γ0(c 1, c 2为任意常数).这时方程组的所有解构成一个平面, 而这个平面是由过点γ0且分别以η1、η2为方向向量的两条相A 的秩=A 的秩= 1 .此时，有两个γ=c 1η1+ c 2η2+ γ0 称为平面的参数方程.
例如, 设保留方程组为 x + y + z = 3, 则可求得其通解为 . 11110101121???? ? ??+????? ??-+????? ??-=c c x
则过点P (1,1,1) 分别以(1,-1,0)T , (1,0,-1)T 为方向,1 10111:,0 11111:21--=-=--=--=-z y x L z y x L 则这两条相交直线L 1, L 2所确定的平面的方程即向量的两直线的方程分别为 为x + y + z = 3 . 如图3-12
求解线性方程组的直接解法 5.2LU分解 ① Gauss消去法实现了LU分解 顺序消元结束时的上三角矩阵U和所用的乘数,严格下三角矩阵。 将下三角矩阵的对角元改成1,记为L,则有A=LU, 这事实是一般的,我们不难从消去的第k个元素时的矩阵k行及k列元素的 历史得到这一点.因为从消元的历史有 u kj=a kj-m k1u1j- m k2u2j -…- m k,k-1u k-1,j, j=k,k+1,…,n m ik=(a ik-m i1u1k- m i2u2k -…-m i,k-1u k-1,k>/u kk i=k+1,k+2,…,n 于是a kj=m k1u1j+m k2u2j+…+m k,k-1u k-1,j+u kj, j=k,k+1,…,n a ik=m i1u1k+m i2u2k+…+m i,k-1u k-1,k+m ik u kk i=k+1,k+2,…,n 从前面两个式子我们可以直接计算L和U(见下段>.将矩阵分解为单位下 三角矩阵和上三角矩阵之积称为矩阵的LU分解.顺序消元实现了LU分 解,同时还求出了g, Lg=b的解. ②直接LU分解 上段我们得到(l ij=m ij> u kj=a kj-l k1u1j-l k2u2j -…- l k,k-1u k-1,j, j=k,k+1,…,n l ik=(a ik-l i1u1k-l i2u2k -…-l i,k-1u k-1,k>/u kk i=k+1,k+2,…,n 2 诸元素对应乘积,只不过算L的元素时还要除以同列对角元.这一规律很 容易记住.可写成算法(L和U可存放于A>: for k=1:n-1 for j=k:n u kj=a kj-l k1u1j-l k2u2j -…- l k,k-1u k-1,j end for i=k+1:n l ik=(a ik-l i1u1k-l i2u2k -…-l i,k-1u k-1,k>/u kk end end 这一算法也叫Gauss消去法的紧凑格式,可一次算得L,U的元素,不需逐步 计算存储.
D =) () ()(0)()() (001 11112 132 3122211331221 1 312a a a a a a a a a a a a a a a a a a a a a a a a k k k k k k k k ------------ 按第一列展开，再将各列的公因子提出来 D = ) ()()() () () (121323122211331221131 2a a a a a a a a a a a a a a a a a a a a a a a a k k k k k k k k ------------ =(a 2－a 1)(a 3－a 1)…(a k －a 1) 22322 32 111 ---k k k k k a a a a a a 得到的k －1阶范德蒙德行列式，由归纳假设知其值为 ∏≤<≤-k i j j i a a 2)( 于是 D =(a 2－a 1)(a 3－a 1)…(a k －a 1) ∏≤<≤-k i j j i a a 2)(= ∏≤<≤-k i j j i a a 1)( 因此，对于任意正整数n ≥2，范德蒙德行列式的展开式都成立。 证毕 例1.14 计算n 阶三对角行列式： D n = 2 1 120000 021000 12 1000 12------ 解 由行列式的性质1.4，将D n 的第一列的每个元看成两个元之和，得
D n = 2100 12000002100 120 00011----- +2 1 1200000 21000 12 1 00011------ 第一个行列式按第一列展开；第二个行列式从第一行开始依次加到下一行，得 D n =D n －1+ 1 110000 01000 110 00011 ---=D n －1+1 反复利用上面的递推公式，得到 D n =D n －1+1=D n －2+2=…=D 1+n －1=2+n －1=n +1 例1.15 计算n 阶行列式 D n = n a b b b a b b b a 21 (a i ≠b , i =1,2,…,n ) 解 对于这个行列式，采用一种“加边”的技巧。 D n =n a b b b a b b b a b b b 000121 第一行乘以（－1）加到其他各行上去，得
一，填空题 1 已知四维向量α，β满足3α+4β＝()2112T ，2α+3β＝()12 31T -，则向量α＝________，β＝_____ 2 有三维列向两组1α＝()100T ，()2110αT ＝，()3111αT ＝，()123βT ＝，且有112233βχαχαχα++＝，则123χχχ＝_____ ，＝_____，＝_____ 3.若向量组123,,ααα线性无关，则向量组122331,,αααααα+++是线性____。 4若n 个 n 维列向量线性无关，则由此n 个向量构成的矩阵必是______ 矩阵。 5若R )(1234,,,4αααα=，则向量组123,,ααα是线性________。 6若向量组)()()()( 12341,1,3,2,4,5,1,1,0,2,2,6,αααα===-=则此向量组的秩是______，一个极大无关组是______。 7已知向量组()()()1231,2,1,1,2,0,,0,0,4,5,2t ααα=-==--的秩为2，则t ＝____. 8已知方程组12312112323120x a x a x ????????????+=????????????-?????? 无解，则a ＝_____。 二，选择题 1.向量组()()()()12341,1,2,0,1,1,2,3,5,2,2,4αααα==-==的极大无关组为（ ） （A ）12,;αα （B ）13,;αα （C ）123,,;ααα （D ）23,;αα 2.若A ＝12421110λ?? ? ? ??? 为使矩阵A 的秩有最少值，则λ应为（ ） （A ）2； （B ）－1; (C)94; (D)12 ; 3. n 元齐次线性方程组AX=0有非零解时，它的每一个基础解系中所含解向量的个数等于（ ） （A ）R )(A -n ； （B ）)(R n A + （C ）)(n R -A ; (D))( n R +A 4.设123412342 34234355222χχχχχχχχχχχλ+-+=??+-+=??+-=? 当λ取（ ）时，方程组有解。 （A ）-12 (B) 12 (C)1- (D)1
最速下降法求解线性代数方程组要求：对于给定的系数矩阵、右端项和初值，可以求解线性代数方程组 一、最速下降法数学理论 PP?tX?Xf(X)的负梯中，在基本迭代公式每次迭代搜索方向取为目标函数kk1kkk?t)X??f(P?取为最优步长，由此确定的算法称为最速度方向，即，而每次迭代的步长kkk下降法。 X)Xminf(kk。现在次，获得了第，假定我们已经迭代了为了求解问题个迭代点k X出发，可选择的下降方法很多，一个非常自然的想法是沿最速下降方向（即负梯度方从k X邻近的范围内是这样。因此，去搜索方向为 )进行搜索应该是有利的，至少在向k P???f(X). kk P k?1进行一维搜索，由此得到第为了使目标函数在搜索方向上获得最多的下降，沿k个跌带点，即 X?X?t?f(X)，kk1k?k t按下式确定其中步长因子k f(X?t?f(X))?minf(X?t?f(X))， kkkkkk X?ls(X,??f(X)). （ 1） k1k?k X X,XX,, ,,?k0,12是初始点，由计算就可以得到一个点列,显然，令其中0210{X}f)X(X)(f 的满足一定的条件时，由式（）所产生的点列必收敛于者任意选定。当1k极小点。 二、最速下降法的基本思想和迭代步骤 ???,)(Xf(X)g. ，终止限已知目标函数及其梯度和321Xf?f(X),g?g(X)k?0. ，计算；置（1）选定初始点00000X?ls(X,?g)f?f(X),g?g(X). （2）作直线搜索：；计算 k?1kk1?k1k?kk?1?1(X,f(X))k?k?1，置，结束；用终止准则检验是否满足：若满足，则打印最优解否则，1k?1?k转（2） （3）最速下降法算法流程图如图所示.
本科毕业论文 （ 2010 届） 题目线性方程组的直接解法及matlab的实现 学院数学与信息工程学院 专业数学与应用数学 班级2006级数学1 班 学号0604010127 学生姓名胡婷婷 指导教师王洁 完成日期2010年5月
摘要 随着科技技术的发展及人类对自然界的不断探索模拟.在自然科学和工程问题中的很多问题的解决常常归结为线性代数问题！ 本文的主要内容是对线性方程组求解方法的探讨,主要介绍了四种求解线性方程组的方法,第一种是教科书上常见的消元法,我们称之为基本法.第二种方法是标准上三角形求解法,即将增广矩阵经过初等变换后化成标准上三角形,然后求解.它改进了一般教科书上的常见方法,与常见方法比较有如下优点:1)规范了自由未知量的选取;2)只用矩阵运算;3)减少了计算量.第三种方法是对特定的方程组（系数矩阵A为n阶对称正定矩阵,且A的顺序主子式均不为零.）的求解方法进行描述,并且为这种线性方程的求解提供了固定的公式化的方法.第四种方法是对现在实际问题中常常会遇到的系数矩阵为三对角矩阵的方程组的求解方法.同时给出这几种方法的数值解法（matlab程序）,由于运用电脑软件求解,所以必须考虑计算方法的时间、空间上的效率以及算法的数值稳定性问题,所以针对不同类型的线性方程组有不同的解法.但是,基本的方法可以归结为两大类,即直接法和迭代法. 关键词 高斯消去法;三角分解法;乔莱斯基分解法;追赶法
Abstract Systems of linear equations are associated with many problems in engineering and scinence ,as well as with applications of mathematics to the social sciences and the quantitative study of business and economic problems. The main content of this article is the method for solving linear equations, we introduce four methods for solving linear equations in this paper. The first is the elimination method which is commonly found in textbooks, and we call the Basic Law. The second method is Standard on the triangle Solution, that first change Augmented matrix into standards in primary triangle, and then solving. It improves the general textbook on common methods, compared with the common method has the following advantages:1) Specification of the free choice of unknowns; 2)Only matrix operations;3) Reduce the computation. The third method describes a way to solve a Specific equations(N coefficient matrix A is symmetric positive definite matrix, and A are not zero-order principal minor), And for this linear equation provides a fixed formulaic approach. The fourth method is to present practical problems often encountered in the coefficient matrix is tridiagonal matrix method for solving the equations. These methods are given numerical solution of (matlab program), As the use of computer software to solve, it is necessary to consider ways of computing time and space efficiency and numerical stability of algorithms, Therefore, different types of linear equations have a different solution. However, the basic method can be classified into two categories, namely direct methods and iterative methods. Key words Gaussian elimination; Triangular decomposition; Cholesky decomposition method; Thomas algorithm
解线性方程组的直接解法 一、实验目的及要求 关于线性方程组的数值解法一般分为两大类：直接法与迭代法。直接法是在没有舍入误差的情况下，通过有限步运算来求方程组解的方法。通过本次试验的学习，应该掌握各种直接法，如：高斯列主元消去法，LU分解法和平方根法等算法的基本思想和原理，了解它们各自的优缺点及适用范围。 二、相关理论知识 求解线性方程组的直接方法有以下几种： 1、利用左除运算符直接求解 线性方程组为b x\ =即可。 A Ax=，则输入b 2、列主元的高斯消元法 程序流程图： 输入系数矩阵A，向量b，输出线性方程组的解x。 根据矩阵的秩判断是否有解，若无解停止；否则，顺序进行； 对于1 p :1- =n 选择第p列中最大元，并且交换行； 消元计算； 回代求解。（此部分可以参看课本第150页相关算法） 3、利用矩阵的分解求解线性方程组 （1）LU分解 调用matlab中的函数lu即可，调用格式如下： [L,U]=lu（A） 注意：L往往不是一个下三角，但是可以经过行的变换化为单位下三角。 （2）平方根法
调用matlab 中的函数chol 即可，调用格式如下： R=chol （A ） 输出的是一个上三角矩阵R ，使得R R A T =。 三、研究、解答以下问题 问题1、先将矩阵A 进行楚列斯基分解，然后解方程组b Ax =(即利用平方根法求解线性方程组，直接调用函数)： ??????? ??--------=19631699723723312312A ，?????? ? ??-=71636b 解答： 程序： A=[12 -3 2 1;-3 23 -7 -3;2 -7 99 -6;1 -3 -6 19]; R=chol(A) b=[6 3 -16 7]'; y=inv(R')*b %y=R'\b x=inv(R)*y %x=R\y 结果： R =3.4641 -0.8660 0.5774 0.2887 0 4.7170 -1.3780 -0.5830 0 0 9.8371 -0.7085 0 0 0 4.2514 y =1.7321 0.9540 -1.5945 1.3940 x =0.5463 0.2023 -0.1385 0.3279 问题 2、先将矩阵A 进行LU 分解，然后解方程组b Ax =（直接调用函数）： ?????????? ??----=8162517623158765211331056897031354376231A ，????????? ? ??-=715513252b
用高斯消元法求解线性代数方程组 1234111 5 -413-2823113-2104151 3-21719x x x x ??????????????????=?????? ?????? ?????? 1111X *??????=?????? （X*是方程组的精确解） 1 高斯消去法 1.1 基本思想及计算过程 高斯（Gauss ）消去法是解线性方程组最常用的方法之一，它的基本思想是通过逐步消元，把方程组化为系数矩阵为三角形矩阵的同解方程组，然后用回代法解此三角形方程组得原方程组的解。 为便于叙述，先以一个三阶线性方程组为例来说明高斯消去法的基本思想。 ??? ??=++II =++I =++III) (323034)(5 253)(6432321 321321x x x x x x x x x 把方程（I ）乘（2 3 - ）后加到方程（II ）上去，把方程（I ）乘（2 4- ）后加到方程（III ）上 去，即可消去方程（II ）、（III ）中的x 1，得同解方程组 ?? ? ??=+-II -=-I =++III) (20 223)(445.0)(6 4323232321x x x x x x x 将方程（II ）乘（ 5 .03 ）后加于方程（III ），得同解方程组： ?? ? ??-=-II -=-I =++III) (42)(445.0)(6432332321x x x x x x 由回代公式（3.5）得x 3 = 2，x 2 = 8，x 1 = -13。 下面考察一般形式的线性方程组的解法，为叙述问题方便，将b i 写成a i , n +1，i = 1, 2,…,n 。
第四节 线性方程组解的判定 从本节开始，讨论含有n 个未知量、m 个方程的线性方程组的解。 11112211211222 22 11 22n n n n m m mn n m a x a x a x b a x a x a x b a x a x a x b +++=??+ ++= ????+++=? （13—2） 主要问题是要判断出方程组（13-2）何时有解？何时无解？有解时解有多少？如何求出方程组的解。 线性方程组有没有解，以及有怎样的解，完全决定于方程组的系数和常数项。因此，将线性方程组写成矩阵形式或向量形式，以矩阵或向量作为讨论线性方程组的工具，将带来极大的方便。 方程组（13-2）中各未知量的系数组成的矩阵11121212221 2 n n m m mn a a a a a a A a a a ? ?? ? ? ?=?? ?? ? ? 称为方程组（13-2）的系数矩阵。由各系数与常数项组成的矩阵，称为增广矩阵，记作A ，即 11121121 222212 n n m m mn m a a a b a a a b A a a a b ?? ????=??? ??? 方程组（13-2）中的未知量组成一个n 行、1列的矩阵（或列向量），记作X;常数项组成一个m 行、1 列的矩阵(或列向量），记作b ，即12n x x X x ??????=?????? ,12 m b b b b ?? ????=?????? 由矩阵运算，方程组(13-2)实际上是如下关系111212122212 n n m m mn a a a a a a a a a ? ?? ? ? ? ?? ?? ? ? 12n x x x ???????????? =12m b b b ???????????? 即 AX=b
第4章 线性方程组的直接解法 本章主要内容 线性方程组的直接解法——消元法（高斯消元法、主元消元法）. 矩阵的三角分解法（ Doolittle 分解、Crout 分解、 LDU 分解） 紧凑格式 改进平方根法. 本章重点、难点 一、消元法（高斯消元法、列主元消元法） 本章求解的是n 阶线性方程组Ax=b 的（即方程的个数和未知量的个数相等的线性方程组） ?????????=+???++????????????? ??=+???++=+???++n n nn n n n n n b x a x a x a b x a x a x a b x a x a x a 22112 3222212111212111 1. 高斯消元法 ①高斯消元法的基本思想：通过对线性方程组Ax=b 的进行同解消元变换（也可以用矩阵的初等行变换法进行线性方程组的消元变换），将线性方程组化为上三角形方程组，然后用回代法求出此线性方程组的解。 ②高斯消元法计算公式： ????? ? ? ????????--=-=--==? ????? ????? ???? +=-=-=====-+=------------∑)1,..., 2,1()1,..., 2,1(,...,1,,,,...,2,1) ,...,2,1,(,) 1(1)1()1()1() 1() 1()1() 1()1()() 1()1()1()1()(,)0()0(n n i a x a b x n n i a b x n k j i b a a b b a a a a a n k n j i b b a a i ii n i j j i ij i i i n nn n n n k k k kk k ik k i k i k kj k kk k ik k ij k ij i i ij ij 对回代公式： 消元公式：
第2章线性方程组的直接解法 2.1实验目的 理解线性方程组计算机解法中的直接解法的求解过程和特点，学习科学计算的方法和简单的编程技术。 2.2概念与结论 1. n阶线性方程组 如果未知量的个数为 n ,而且关于这些未知量x1,x2, …,x n的幂次都是一次的(线性的)那末, n 个方程 a11x1+a12x2+ … +a1n x n=b1 ┆┆┆ (1) a n1x1+a n2x2+ … +a nn x n= b n 构成一个含n个未知量的线性方程组,称为n阶线性方程组。其中,系数a11,…,a1n,a21, …,a2n, …,a n1, …,a nn 和b1, …,b n都是给定的常数。 方程组(1)也常用矩阵的形式表示,写为 Ax=b 其中,A是由系数按次序排列构成的一个n阶矩阵,称为方程组的系数矩阵,x和b都是n维向量,b称为方程组的右端向量。 2. n阶线性方程组的解 使方程组(1)中每一个方程都成立的一组数x1*,x2*, …,x n*称为式(1)的解,把它记为向量的形式,称为解向量. 3.一些特殊的线性方程组 1) 上三角方程组 2) 三对角方程组 ? ? ? ? ? ? ? ? ? ? ? ? = ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? - - - - - n n nn n n n n n n n n b b b x x x a a a a a a a a a a a a 2 1 2 1 1 1 1 2 1 2 23 22 1 1 1 13 12 11
4.矩阵的Doolittle 分解 5.Doolittle 分解的紧凑格式 6．矩阵的Crout 分解 ????????? ? ??=?????????? ???????????? ? ?--n n n n n n d d d x x x b a c b c b a c b a c b 21 2111333 22211???? ?? ? ? ???????? ??=??????? ??nn n n n n nn n n n n u u u u u u l l l a a a a a a a a a 222 11211 2 1 21 2 1 2222111211111 ???? ?? ? ? ???????? ??=??????? ??11 1 21122 1 2221 11 2 1 2222111211 n n nn n n nn n n n n u u u l l l l l l a a a a a a a a a ????? ?? ? ??nn n n n n n n u l l l u u l l u u u l u u u u 3 2 1 333323122322211131211
第二章线性代数方程组的直接解法 教学目标： 1.了解线性代数方程组的结构、基本理论以及相关解法的发展历程； 2.掌握高斯消去法的原理和计算步骤，理解顺序消去法能够实现的条件，并在此基础上理解矩阵的三角分解（即LU分解），能应用高斯消去法熟练计算简单的线性代数方程组； 3.在理解高斯消去法的缺点的基础上，掌握有换行步骤的高斯消去法，从而理解和掌握选主元素的高斯消去法，尤其是列主元素消去法的理论和计算步骤，并能灵活的应用于实际中。 教学重点： 1. 高斯消去法的原理和计算步骤； 2. 顺序消去法能够实现的条件； 3. 矩阵的三角分解（即LU分解）； 4. 列主元素消去法的理论和计算步骤。 教学难点： 1. 高斯消去法的原理和计算步骤； 2. 矩阵的三角分解（即LU分解）； 3. 列主元素消去法的理论和计算步骤。 教学方法： 教具： 引言 在自然科学和工程技术中，许多问题的解决常常归结为线性方程组的求解，有的问题的数学模型中虽不直接表现为线性方程组，但它的数值解法中将问题“离散化”或“线性化”为线性方程组。例如，电学中的网络问题、船体数学放样中建立三次样条函数问题、最小二乘法用于求解实验数据的曲线拟合问题、求解非线性方程组问题、用差分法或有限元法求解常微分方程边值问题及偏微分方程的定解问题，都要导致求解一个或若干个线性方程组的问题。 目前，计算机上解线性方程组的数值方法尽管很多，但归纳起来，大致可以分为两大类：一类是直接法（也称精确解法）；另一类是迭代法。例如线性代数中的Cramer法则就是一种直接法，但其对高阶方程组计算量太大，不是一种实用的算法。实用的直接法中具有代表性的算法是高斯（Gauss）消元法，其它算法都是它的变形和应用。 在数值计算历史上，直接法和迭代法交替生辉。一种解法的兴旺与计算机的硬件环境和问题规模是密切相关的。一般说来，对同等规模的线性方程组，直接法对计算机的要求高于迭代法。对于中、低阶（200 n ）以及高阶带形的线性方程组，由于直接法的准确性和可靠性高，一般都用直接法求解。对于一般高阶方程组，特别是系数矩阵为大型稀疏矩阵的线性方程组用迭代法有效。
线性代数方程组求解 一、实验要求 编程求解方程组: 方程组1: 方程组2: 方程组3： 要求: 用C/C++语言实现如下函数： 1.bool lu(double* a， int＊ pivot, int n）； 实现矩阵的LU分解。 pivot为输出参数,pivot[0,n）中存放主元的位置排列. 函数成功时返回false，否则返回true。 2.bool guass（double const* lu， int const* p, double* b, int n）；
求线代数方程组的解 设矩阵Lunxn 为某个矩阵anxn 的LU 分解，在内存中按行优先次序存放。p[0，n)为LU 分解的主元排列.b 为方程组Ax=b 的右端向量.此函数计算方程组Ax=b 的解，并将结果存放在数组b ［0，n ）中.函数成功时返回false ，否则返回true 。 3。 void qr(double* a ， double ＊ d, int n);矩阵的QR 分解 假设数组anxn 在内存中按行优先次序存放。此函数使用HouseHolder 变换将其就地进行QR 分解。 d 为输出参数，d [0,n) 中存放QR 分解的上三角对角线元素。 4。 bool hshld(double const*qr ， double const*d, double*b ， int n); 求线代数方程组的解 设矩阵qrnxn 为某个矩阵anxn 的QR 分解,在内存中按行优先次序存放。d [0,n ） 为QR 分解的上三角对角线元素。b 为方程组Ax=b 的右端向量。 函数计算方程组Ax=b 的解,并将结果存放在数组b[0，n)中。 函数成功时返回false ，否则返回true 。 二、问题分析 求解线性方程组Ax=b ，其实质就是把它的系数矩阵A 通过各种变换成一个下三角或上三角矩阵，从而简化方程组的求解。因此,在求解线性方程组的过程中，把系数矩阵A 变换成上三角或下三角矩阵显得尤为重要,然而矩阵A 的变换通常有两种分解方法：LU 分解法和QR 分解法。 1、LU 分解法： 将A 分解为一个下三角矩阵L 和一个上三角矩阵U,即:A=LU ， 其中 L=??????? ?????1001 00 12121 n n l l l ， U=? ? ??? ? ??????nn n n u u u u u u 000 00222112 11 2、QR 分解法： 将A 分解为一个正交矩阵Q 和一个上三角矩阵R,即：A=QR 三、实验原理 解Ax=b 的问题就等价于要求解两个三角形方程组： ⑴ Ly=b，求y; ⑵ Ux=y,求x 。 设A 为非奇异矩阵，且有分解式A=LU , L 为单位下三角阵，U 为上三角
实验五 线性方程组的直接解法 一、实验内容 1、用列主元素法求解方程组 15 123459.170.31059.43146.785.291 6.3112111.295221211x x x x -?????????????--??????=?????????????? ???? 并计算误差b-Ax ，分析结果的好坏； 2、 用改进Cholesky 方法求对称正定阵线性方程组 1234248.72171013.741090.7x x x -????????????-=????????????-?????? 并计算误差b-Ax ，分析结果的好坏； 3、 用追赶法解方程组 123421006132010121000351x x x x -????????????--??????=??????--??????-???? ?? 二、要求 1、 对上述三个方程组分别利用Gauss 列主元消去法；Cholesky 方法；追赶法求解（选择其一）； 2、 应用结构程序设计编出通用程序； 3、 比较计算结果，分析数值解误差的原因； 三、目的和意义 1、通过该课题的实验，体会模块化结构程序设计方法的优点； 2、运用所学的计算方法，解决各类线性方程组的直接算法； 3、提高分析和解决问题的能力，做到学以致用； 4、 通过三对角形线性方程组的解法，体会稀疏线性方程组解法的特点。 四、实验学时：2学时 五、实验步骤： 1．进入matlab 开发环境； 2．根据实验内容和要求编写程序； 3．调试程序； 4．运行程序； 5．撰写报告,讨论分析实验结果．
六、程序 1、Gauss列主元素消去法 function x=Gauss_pivot(A,b) %用Gauss列主元素法求解线性方程组Ax=b %x是未知向量 n=length(b); x=zeros(n,1); c=zeros(1,n); d1=0; %消元计算 for i=1:n-1 max=abs(A(i,i)); m=i; for j=i+1:n if max 三元线性方程组的几何解法 任春丽，王金金 (西安电子科技人学理学院数学系，陕西酋安710071 ) 线性方程组是线性代数中重要的内容，其解的结构在线性代数课程中已通过向量及矩阵理论讨论的非常清楚，但在教材中很少提及几何意义.由于三元线性方程表示空间屮的平而，因此，通过平面图形Z间的位置关系求解线性方程组，不仅形象、直观，而且为从三维空间抽象的代数问题推广到n维空间更定了基础°文献[2] 丿IJ矩阵 的秩判别了空间屮平面、直线之间的位證关系；相反的，本文利用空间中平而、肓线之间的位宜关系讨论了三元线性方程组解的情况，并举例说明。 1.两个方程的三元线性方程组 设方程组(I)： [仲+恥+C"。-街俩个平面) A2X +B2y + C2z = D2—兀2 讨论：令e=4，d，G，o)(心1,2), %=Q,B,C)(i = l,2) ⑴若wa，即牛鲁咱唔‘则 眄与龙2重合，方程组(I)有无穷多解； (2)若n.//n2i a^a29即4 =邑』』, 1 2 1 2 码场C? D2则眄与?平行但不重合，方程组(I )无解； (3)若讥叫，则陌与幻相交，方程纨I)有无穷多解，其解为相交直线上的所有点。 例1求解下列线性方程组 3兀 + 6y — 3z = 8 fx + 2y-z = 7 (1){ : (2){ ?一兀一 2y + z = 3 [-2x + y + z = 4 解⑴因为—7^-,所以两个平 -1-213 血平行但不重合，故方程组无解； (2)因为阿x〃2 =(1，2,T)x(一2,1,1) = (3丄5) H 0, 所以两个平面相交于H线L,故方程组有无穷多 解。又点(1,4,2)在L上，故直线L的参数方程x = 1 + 3f, 为：」= 4+r,即是方程组的通解。 z = 2 + 5/. 2.三个方程的三元线性方程组 设方程组(II)： A}x + + Gz = °―兀、 < A2x + B2y + C2z = D2—兀2(三个平面) A.x + B,y^C.z = D. 一心 讨论:令q=Q，d，G，q)(i = l,2,3), n,=(4.,B/,C/)(i = l,2,3)o (1)若= 1,2,3)中至少有两个平行，则至 少有两个平面重合，其解的讨论同第1 H； (2)若? (/ = 1,2,3)屮至少有两个平行，但相应的乞?加勺(心力，则至少冇两个平面平行但 不重合，方程组(II)无解； (3)若?加? (心/),则三个平面两两相交， 方程组(II)可能有解，也可能无解。进一步：求 x = x Q + mt, ! IW与兀2的交线L的参数式方程:\y = y o+ntf z = 5 + pt. 如果厶〃龙3，但点(兀O，y°，Zo)不在龙3上，则 7、5 一般线性方程组 课题: 一般线性方程组 目的要求:1.掌握矩阵秩概念 ２.掌握线性方程组解判定方法; ３.掌握齐次线性方程组的解法。 重点: 线性方程组解判定方法 难点: 线性方程组的消元法 教学方法: 讲练结合 教学时数: 4课时 教学进程: 一、矩阵的秩 矩阵的秩就是矩阵的重要特性之一,它在线性方程组解的讨论中起着关键的作用. 定义:矩阵A 的阶梯形矩阵所含非零行的行数称为矩阵A 的秩,记为r (A ). 根据这个定义,可以得出求矩阵A 的秩的一般步骤: 1． 用矩阵的初等行变换把A 化为阶梯形矩阵; 2． 数一下阶梯形矩阵中有多少个非零行. 例1 求矩阵?? ? ? ? ? ? ? ?--=28552311314321 112 21A 的秩. 解 ???? ?? ? ??-----?????→?---??????? ??--=6110305502550011221)(2)()(3)() ()(2855231131432111221141312r r r r r r A ??? ?? ?? ??--?????→?+??????? ??-----?????→??255000000611011221)(5)(255003055061 1011221)()(2324r r r r ????? ? ? ??--?????→??00002550061 1011221)()(43r r 所以r (A )=3. 例2 求矩阵????? ?? ? ??------=231453312112231B 的秩. 解 ??????? ? ? ?------?????→?---+???????? ??------=46024077 055 0231)()()(3)() (2)() (2)(23145331211223115 141312r r r r r r r r B ??????? ? ???????→??-???????? ? ??????→?+++???????? ??------???→?000000 200110 231 )()()()(200200000 110231)(6)()(4)() (7)(460240*********)(5143452524232r r r r r r r r r r r 所以r (B )=3. 二、 一般线性方程组的解 一般的线性方程组,它的未知数个数与方程的个数可以相等也可以不相等.对于n 个未知 数n 个方程的线性方程组,当它的系数行列式不为零时,可以有以下三种求解方法:⑴克莱姆法则;⑵逆矩阵;⑶矩阵法.其中矩阵法还能用来求解未知数个数与方程个数不相等的线性方程组.本节将运用矩阵法来讨论一般的线性方程组的解.先考察先面的两个例子. 例3 讨论线性方程组??? ??=+--=-++=-++0 524232324321 43214321x x x x x x x x x x x x 的解. 解 ???? ? ??-------?????→?--????? ??----=228402284021321)()() (3)(015214112 321321~ 1312r r r r A ????? ? ??--???→?-????? ??----????→?-00000212121021321)(41000002284021321)()(223r r r ? ???? ? ??--?????→?-00000212121010101)(2)(21r r ① 最后一个矩阵对应于方程组:132********x x x x x -=???+-=??,因此有132******** x x x x x =+?? ?=-+??. 由于当x 3与x 4分别任意取定一个值时,都可得到方程组的一组解,因此该方程组有无穷多 组解. 线性方程组解法综述 Prepared on 22 November 2020 线性方程组解法的研究综述 摘要：这篇论文在说明了线性方程组的应用目的的基础上，提出了线性方程组求解的研究现状，并列举了常用的求解方法，同时说明了它们的应用条件，剖析了各种方法的不足之处。 关键词高斯消元迭代病态方程组 一、问题提出 在自然科学和工程实际应用中，有许多问题的求解最终都转化为线性方程组的求解问题。例如,电学中的网络问题，曲线拟合中常用的最小二乘法、样条函数插值、解非线性方程组、求解偏微分方程的差分法、有限元法和边界元法以及目前工程实践中普遍存在的反演问题等。特别是在图像恢复、模型参数估计、解卷积、带限信号外推、地震勘探等众多领域，都需要求解线性方程组。 由于线性方程组问题在理论上的重要性和在工程实际应用中的大量存在，多年来人们在这方面做了广泛深入的研究和探讨，并取得了许多有价值的成果.由于模型误差、测量误差、计算误差等各种误差的存在，常常使得线性方程组中的系数矩阵和非齐次项信息具有某种程度的近似性(即扰动性)，这种近似性显然会使得线性方程组的求解不容易得到真实的理论解。此时，不同的求解方法由于运算机理不一样，求解过程中误差积累程度就不一样，因此必然会使得不同的求解方法得到的解具有不同的逼近真解的误差程度，尤其对具有病态性的方程组而言，由于病态线性方程组的条件数很大，数据误差以及计算过程中引入的舍入误差往往会使线性方程组的解不稳定，即不管原始数据的误差多么小，都可能造成解的很大变化，使线性方程组的解严重失真。因此，许多现有的方 法都是无效的，病态线性方程组的求解变得相当困难。求解线性方程组的最常用的方法主要有直接法和迭代法两大类，其中直接法中最常用的方法是高斯消元法。但是，该方法求解病态线性方程组时不能得到合理的解，误差很大。 二、研究现状 目前关于线性方程组的数值解法一般有两大类。一类是直接方法，另一类是迭代方法。直接方法最基本的是高斯消元法及其变形，这类方法是解低阶稠密矩阵方程组的有效方法，近十几年来直接法在求解具有较大型稀疏矩阵方程组方面取得了较大进展。迭代法就是用某种迭代过程去逐步逼近线性方程组的精确解，迭代法具有需要计算机的存储单元较少，程序设计简单，原始系数矩阵在计算过程中始终不变等优点，但存在收敛性及收敛速度问题。迭代法是解大型稀疏矩阵方程组的重要方法。当前对迭代算法的研究已经较为成熟，但如何使之适合新体系模型，以获得更好的性能加速一直是应用和体系设计者关心的问题。 三、常用方法比较 1.直接方法 直接方法是指假设计算过程中不产生舍入误差，经过有限次运算可求得方程组的精确解的方法。事实上，由于舍入误差的存在，用直接法一般也只能求得方程组的近似解。直接方法中主要有三种方法：克拉默法则、高斯消元法、LU 分解法。 （1）克拉默法则 设有线性方程组（ n 个未知数 n 个方程）三元线性方程组的几何解法.doc
一般线性方程组
线性方程组解法综述
相关主题
文本预览