xn
b n...
a
... nn
利用3.3节的回代法求解上述上三角方程组
25.05.2020
19
3.4 高斯消去法和选主元（续7）
消去过程
2x1 x2 4x3 16 3x1 2x2 x3 10 x1 3x2 3x3 16
2x1 x2 4x3 16
1 2
x2
5x3 -14
x1 3x2 3x3 16
17
3.4 高斯消去法和选主元（续5）
a11x1 a12x2 a13x3 a1nxn b1 a2 2x2 a2 3x3 a2nxn b2 a3 2x2 a3 3x3 a3nxn b3
an 2x2 an3x3 an nxn bn
a
' j
2
/
a
' 2
2
25.05.2020
in1,..2.,1
25.05.2020
11
上三角线性方程组的求解（续1）
(2) 式可简写成 Ux b， 其中
u11 U
u12 u 22
u1n u2n
unn
25.05.2020
12
3.4 高斯消去法和选主元
求解有N个方程和N个未知数的一般方程组 AX=B的一般做法：构造一个等价的上三角 方程组UX=Y，并利用回代法求解
2 x1 x2 4 x3 16
1 2
x2
5 x3 -14
5 2
x2
x3
8
25.05.2020
2x1 x2 4x3 16 x2 10x3 -28 26x3 78
20
3.4 高斯消去法和选主元（续8）
回代过程
x3
78 26
3
x2 -28 10 x3 -28 10 3
2
x1
16
线性代数方面的计算方法就是研究求解线性方程 组的一些数值解法与研究计算矩阵的特征值及特 征向量的数值方法。
25.05.2020
2
线性方程组求解问题
考虑线性方程组 Ax = b 其中A是一个(n ×n)的非奇异矩阵, x是要求解
的n维未知向量, b是n维常向量
a11 a12 a1nx1 b1
o作r 如下行变换之后方程组的解向量 x 不变
对调方程组的两行 用非零常数乘以方程组的某一行 将方程组的某一行乘以一个非零常数，再加到另一行上
通过对增广矩阵[A|B]进行如上的行变换求解
25.05.2020
15
3.4 高斯消去法和选主元（续3）
a11x1 a12x2 a13x3 a1nxn b1 a21x1 a22x2 a23x3 a2nxn b2 a31x1 a32x2 a33x3 a3nxn b3
23
3.4 高斯消去法和选主元（续11）
病态问题：矩阵A中元素的微小变化引起解 的很大变化
1 0.48
0.299xx121.347
x1
x
2
1 1
1 0.49
0.299xx121.347
x1
x
2
3
0
cond(A)=207.012
25.05.2020
24
图形解释
2.5
2
1.5
1
0.5
0
-0.5
-2
-1
0
1
2
3
4
25.05.2020
25
3.4 高斯消去法和选主元（续12）
一个线性方程组称 为是病态的，如果 其系数矩阵接近奇 异且它的行列式接 近0
矩阵条件数 cond(A)=||A||||A-1||
25.05.2020
26
3.5 三角分解法
A=LU:下三角矩阵L的主对角线为1，上三角矩阵 U的对角线元素非零
一解
矩阵A是非奇异的（即A-1存在） 方程组AX=0有唯一解X=0 det(A) ≠0
25.05.2020
4
线性方程组的解
最常见的求线性方程组Ax=b的解的方法是在方 程组两侧同乘以矩阵A的逆
Ax = b
A 1A xA 1b xA1b
Gram法则：
xi
Di D
i 1,2,...,n，其中
Ddet(A)0，Di det(Ai)，Ai是A的第 i列用b代替所得。
an1x1 an2x2 an3x3 annxn bn
a31/a11 an1/a11
25.05.2020
a11x1 a12x2 a13x3 a1nxn b1 a2 2x2 a2 3x3 a2nxn b2 a3 2x2 a3 3x3 a3nxn b3 an 2x2 an3x3 an nxn bn
m m3 41 1
m32 m42

1 m43
00 10
0 0
u33 0
u u3 44 4
A非奇异蕴含着对所有的k有ukk≠0，k=1,2,3,4.
25.05.2020
27
矩阵的LU分解
是否所有的非奇异矩阵A都能作LU分解呢？
一个例子：
A
0
1
1 0
1 a
0 b 1 0
d
c
N阶方阵A有唯一LU分解的充要条件是A的各阶 顺序主子式均不为零
如果两个N×N线性方程组的解相同，则称 二者等价
对一个给定方程组进行初等变换，不会改 变它的解
25.05.2020
13
3.4 高斯消去法和选主元（续1）
考虑一个简单的例子：
3x1 2x2 7 4x1 x2 1
求解第二个方程，得
x2 5
第二个方程减去第 一个方程除以3再乘 以4得到的新方程， 得到新的方程组：
偏序选主元策略 |akp|=max{|app|,|app+1|,…,|aN-1p|,|aNp|}
按比例偏序选主元（平衡）策略
sr=max{|arp|,|arp+1|,…,|arN|} 其中r=p,p+1,…,N
|akp|m ax{|app|,|ap1p|,L,|aNp|}
sk
sp sp1
sN
25.05.2020
关于线性方程组的数值解法一般有两类
直接法：若在计算过程中没有舍入误差，经 过有限步算术运算，可求得方程组的精确解 的方法
迭代法：用某种极限过程去逐步逼近线性方 程组精确解的方法
迭代法具有占存储单元少，程序设计简单， 原始系数矩阵在迭代过程中不变等优点，但 存在收敛性及收敛速度等问题
25.05.2020
选主元以避免
a
( p
p p
)
0
，如果此主元非零，则不
换行；如果此主元为零，则寻找第p行下满足
a
( k
p p
)
0
的第1行，将此行与第p行互换，使新主元非零。
平凡选主元策略
25.05.2020
22
3.4 高斯消去法和选主元（续10）
选主元以减少误差：把元素中的最大绝对值移到 主对角线上
例3.17和3.18
定义3.4 如果非奇异矩阵A可表示为下三角矩阵L和上 三角矩阵U的乘积：A=LU，则A存在一个三角分解
a11 a12 a13 a14 1 0 0 0u11 u12 u13 u14
a21 a22 a23 a24m21 1 0 00 u22 u23 u24
a a3 41 1
a32 a42
a33 a43
a a3 44 4
25.05.2020
9
3.3 上三角线性方程组（续2）
求解上三角线性方程组的回代算法
xn
b
... n
a
... n
a11x1 a12x2 a13x3 a1nxn b1 a2 2x2 a2 3x3 a2nxn b2 a3 3x3 a3nxn b3
a n . .1 ,.n 1 x n 1+ n . .1 ,.n x a nn .b .1 .
25.05.2020
8
3.3 上三角线性方程组（续1）
条件akk≠0很重要，因为回代算法中包含对akk的除 法。如果条件不满足，则可能无解或有无穷解
定理3.6 如果N×N矩阵A=[aij]是上三角矩阵或下 三角矩阵，则
N
det(A)a11a22LaNN aii i1
联系定理3.4，可知要条件akk≠0成立才能保证方 程组存在唯一解
第3章 线性方程组 AX=B的数值解法
25.05.2020
1
引言
在自然科学和工程技术中很多问题的解决常常归 结为解线性代数方程组。例如电学中的网络问题， 船体数学放样中建立三次样条函数问题，用最小 二乘法求实验数据的曲线拟合问题，解非线性方 程组问题，用差分法或者有限元法解常微分方程， 偏微分方程边值问题等都导致求解线性方程组， 而且后面几种情况常常归结为求解大型线性方程 组。
25.05.2020
28
3.5 三角分解法（续1）
利用前代/回代算法求解形如Lx=b或Ux=b的线性 方程组是容易的
如果对一个给定的矩阵A，能够找到一个下三角 矩阵L和一个上三角矩阵U，使A=LU
则求解线性方程组Ax=b的问题可以分解成两个简 单的问题：
Ly=b Ux=y
易见：Ax=(LU)x=L(Ux)=Ly=b
an...nxn bn...
xn1
bn...1 - an...1,nxn an..1.,n1
最后
n
x 1b 1(a 1x21 a a 1 x3 11 a nxn)b 1(k a 1 2 a 1 k 1 xk)
25.05.2020
10
上三角线性方程组的求解
基本算法：
xxni b(nbi/unjnni1uijxj )/iui
an1x1 an2x2 an3x3 annxn bn