第四章线性方程组直接法,矩阵三角分解

§2 直接三角分解法
三角分解法也是直接法，基本思想是： 将系数矩阵A分解为两个三角形矩阵L和U的 乘积A=LU ，将方程组AX=b的求解问题归结为 两个三角形方程组 LY=b与UX=Y的求解问题。
即：先由LY=b求出Y ，然后由UX=Y求出X ， 从而获得AX=b的解。
(1) A为一般稠密（零元素占很小比例）矩阵 的杜利特尔(Doolittlr)和克劳特(Crout)分解法；
1 0 0
3

7

2
2 2

1 12
7 6

1

0
0
16

3
等价的三角方程组为


12


3 3 2
3 7
2

x1

x2


15

15

2

16


x3

16
an1
bn1
cn1


xn1


fn1

an bn xn fn
其中方程组AX=f 的系数矩阵A的元素满足条件：
b1 c1 0

bi ai ci

bn

an
0
（1） 且 aici 0
(i 2,3, , n 1)
由以上推导过程知，方程组AX=f 有唯一解
由（3）式可得计算 i 的递推公式
1i

c1 ci
/ b1 /(bi

ai i1)
(i 2,3,
（4）

u22
u11
u2n



l n1 l n2
1

unn

即
a11 a12 a 21 a22
a1n
a2n


u11 l21u11
u12 l21u12 u22
u1n

l21u1n

u2n


a n1 a n2
ann
ln1u 11
由（5.3.1）- （5.3.4）求得L和U后，解方程组Ax=b 化为求解LUx=b，若记Ux=y，则有Ly=b。于是可分两部解 方程组LUx=b，只要逐次向前代入的方法即可求得y。第
二步求解Ux=y，只要逐次用向后回代的方法即可求得x。 设 x=（x1 ，x2， ···xn) T, y=（y1, y2, ···yn) T,
n

i1
lniuin

unn

第四章方程组的直接解法
由A的第1行和第1列可计算出U的第1行和L的第1列，即
u1 j a1 j , j 1, 2, , n,
（5.3.1）
lk1

ak1 u11
,k

2, 3,
, n.
（5.3.2）
如果U的第1至k-1列和L的第1至k-1列已经算出，则由
解 设 A=LU，即
l11 a11 1, l21 a21 2, l31 a31 0
u12

a12 l11
2, u13

a13 l11
1,

l22 a22 l21u12 3, l32 a32 l31u12 1

三角阵。等式左边是单位下三角阵，右边是上三角阵，要使等式
成则立L ， L只1 ,能U等于U单1，位即矩此阵三I。角于分是解L唯1一L1。
UU
1 1
I,
1 2 1
1 2 1
例7 解：
设 A 3 7
1
，试将A进行三角分解。
1 1 3
由高斯消去法得到
m21
3 1
3，m31
1 1
1
m 32
L1
1 1
0 0 1 2
例：
求
0 1 2
0 1 0
3 0 1
103的PLU分 解 。
解：用1，2， ，n的排列表示n阶置换阵P，其中排列的第i个元素
j，表示P的i行非零元素位于j列。则分解过程如下：
1 0 0 1 2
3 1 1 0 1
3 1 1 0
2 0
43
1 2
0 1 0
3 0 1
0 1 3
Ux j y j
Ly
j
bj
n1
k
n(n 1)
n2
n 次乘法
k 1
2
22
Ux j y j n k n(n 1) n2 n 次乘除法
k 1
2
22
即共需n 2 次乘除法运算。
n 2 次 乘 除 法
三角分解法的存放元素的方法：
以A (a ij )33 为例，
a11 A a21
1 mk1,k 1
k，
Lk1
1 mk1,k 1
k
mnk
1
mn,k
1
A ( L11 L21
L1 n1
)U
LU，1
a (1) 11

当系数矩阵存在某些特殊结构时（如带状矩阵、稀疏矩阵等），列主元消元法可能不是最优的求解方法。 此时可以考虑使用其他直接法或间接法进行求解。
04
矩阵的三角分解法
LU分解法
定义：将系数矩阵A分解为一个下三角 矩阵L和一个上三角矩阵U的乘积，即 A=LU。
适用范围：适用于所有可逆矩阵，特别 适用于中小型稠密矩阵。
迭代法收敛性判断
在迭代法求解方程组时，可以通过观察迭代过程中解向量的范数的变化情况来判断迭代法 是否收敛。如果解向量的范数逐渐减小并趋于零，则表明迭代法收敛。
方程组性态分析
方程组的性态是指方程组解的存在性、唯一性和稳定性等方面的性质。通过分析方程组的 系数矩阵的范数，可以对方程组的性态进行初步的判断。例如，如果系数矩阵的谱半径（ 即最大特征值的模）较小，则方程组往往具有较好的性态。
03
线性方程组在科学研究、工程技术和经济管理等领域具有广 泛的应用。
直接法的定义与分类
1
直接法是一种通过有限步四则运算求解线性方程 组的方法，具有计算精度高、稳定性好的特点。
2
直接法可分为高斯消元法、列主元消元法、全主 元消元法等多种方法，其中高斯消元法是最基本 的方法。
3
各种直接法的主要区别在于选主元和消元的过程 中采用不同的策略，以达到提高计算精度和稳定 性的目的。
对系数矩阵A进行Crout分解，得到下三角矩阵L和单位 上三角矩阵U。
利用后向代入法求解Ux=y，得到向量x。
求解步骤
利用前向代入法求解Ly=b，得到向量y。
适用范围：适用于所有可逆矩阵，特别适用于中小型稠 密矩阵。与LU分解法和Doolittle分解法相比，Crout 分解法在某些情况下具有更高的计算效率。
性质

⎛1 0 ⎛1 3 2 1 ⎞ ⎜3 1 ⎜ ⎟ ⎜ 3 13 12 9 ⎜ ⎟ = ⎜2 3 ⎜ 2 12 29 15 ⎟ ⎜ 2 ⎜ ⎟ ⎜ 1 9 15 34 3 ⎝ ⎠ ⎜1 ⎜ 2 ⎝ ⎛1 ⎜ ⎜3 =⎜ ⎜2 ⎜ ⎜ ⎜1 ⎝ 0 1 3 2 3 2 0⎞ ⎟ 0⎟⎛1 ⎜ ⎟⎜0 1 0⎟⎜ 0 ⎟⎜ 1 ⎟ 0 1⎟⎝ 4 ⎠ 0 0
⎛1⎞ 0 0 0 ⎞ ⎛ y1 ⎞ ⎛ 1 ⎞ ⎛ y1 ⎞ ⎜ 5 ⎟ ⎜ ⎟ ⎜ ⎟ ⎟⎜ ⎟ ⎜ ⎟ y 4 0 0 ⎟ ⎜ y2 ⎟ ⎜ 10 ⎟ 2 ⎟。 = ，得到 ⎜ 2 ⎟ = ⎜ ⎜ ⎜ ⎟ ⎜ ⎟ ⎟ ⎜ ⎟ y3 0 16 0 y3 24 3⎟ ⎜ ⎟ ⎜ ⎟ ⎟⎜ ⎟ ⎜ ⎟ 0 0 25 ⎠ ⎝ y4 ⎠ ⎝ 50 ⎠ ⎝ y4 ⎠ ⎜ 2 ⎟ ⎜2⎟ ⎝ ⎠
⎛ 1 0 0 0⎞ ⎜ ⎟ 6 ⎞ ⎜ 2 1 0 0⎟⎛3 ⎟ห้องสมุดไป่ตู้⎟⎜0 6 ⎟ ⎜3 ⎜ ⎟⎜ = 1 8⎟ ⎜ 0 1 0⎟⎜0 ⎟ ⎜3 ⎟⎜ 12 ⎠ ⎜ ⎟⎝0 4 1 0 1 ⎜ ⎟ ⎝3 ⎠
6 3 6⎞ ⎟ 1 0 2⎟ 0 2 6⎟ ⎟ 0 0 2⎠
解方程组
⎛ 1 0 0 0⎞ ⎜ ⎟ ⎜ 2 1 0 0 ⎟ ⎛ y1 ⎞ ⎛ 9 ⎞ ⎜3 ⎟⎜ y ⎟ ⎜ 7 ⎟ ⎜1 ⎟⎜ 2 ⎟ = ⎜ ⎟ 0 1 0 ⎟ ⎜ y3 ⎟ ⎜ 1 ⎟ ⎜ ⎜3 ⎟⎜ ⎟ ⎜ ⎟ ⎜4 ⎟ ⎝ y4 ⎠ ⎝13 ⎠ 1 0 1⎟ ⎜ ⎝3 ⎠
⎛3 ⎜ ⎜2 ⎜1 ⎜ ⎝4
6 3 5 2 2 3
6 6 8
1 0 0 0 1 0 0 0 1
9 4 12 0 0 0
2 3 1 0 2 6 − 3 4 1 0 4 − 3 1 0 2 −

解线性代数方程————————————————————————————————作者：————————————————————————————————日期：求解线性方程组的直接解法5.3特殊矩阵的三角分解①实对称矩阵的LDL T分解设A是实对称阵,且A的所有顺序主子式均不为零，则LDR分解中R=L T, 故可用以作LDL T分解.这就是说,当A的对角元素非零时，我们可以作LU分解,也就得到LDL T分解,L相同,是单位上三角阵,U的对角元素构成D.不过没有利用对称性,存储量运算量都未能节省—预计是一半。

试用n=3的计算表格说明如何实现节省。

d1=u11 =a11u12=a12l21=u12/d1u13=a13l31=u13/d1d2=u22=a22-l21u12u23=a23-l21u13l32=u23/d2u33=a33-l31u13-l32u23这样,可用上半部元素逐列计算D,L T。

也可用下半部元素逐行计算L,D。

引进輔助量t1, t2代替u1j,u2j,并利用对称性得到：d1=a11t1=a21l21= t1/d1d2= a22-t1l21t1=a31 l31=t1/d1t2=a32-t1l21l32=t2/d2d3=a33-t1l31-t2l32据此不难写出LDL T分解A=LDL T的计算公式和程序(逐行计算L,D).d1=a11for i=2:nfor j=1:i-1t j=a ij-l j1t1-l j2t2-…-l j,j-1t j-1l ij=t j/d jendd i=a ii-l i1t1-l i2t2-…- l i,i-1t i-1end存储约n(n+1)/2单元,乘加运算各约n3/6.利用LDL T分解解Ax=b分四步:1．分解A=LDL T2．解Lg=b 求g3．解Dy=g 求y4．解L T x=y 求x②实对称正定矩阵的LL T分解A实对称正定时顺序主子式皆正,可作LDL T,D的对角元素皆正,有正的平方根。

用矩阵的直接三角分解法解方程组矩阵的直接三角分解法（LU分解法）是解线性方程组的一种常用方法。

该方法通过将系数矩阵分解为一个下三角矩阵和一个上三角矩阵的乘积，从而简化方程组的求解过程。

下面我们就来详细分步骤地介绍一下这种方法的求解过程。

第一步，将原线性方程组表示为矩阵形式，即将系数矩阵、未知量矩阵和常数矩阵分别表示为A、X和B。

我们的目标是找到一个下三角矩阵L和一个上三角矩阵U，使得方程组可以表示为LUx = B的形式。

第二步，通过高斯消元法将系数矩阵A化为上三角矩阵U。

具体地，我们将系数矩阵A变换为U的过程可以分解为一系列的初等矩阵变换，例如交换两行、乘以一个非零常数和将某一行加上另一行的若干倍等等。

这些初等矩阵变换可以表示为一个矩阵M的乘积，即A =M1M2...MnU。

从而，我们得到了上三角矩阵U。

第三步，同样通过一系列初等矩阵变换将U转化为下三角矩阵L。

这些初等矩阵变换可以表示为一个矩阵N的乘积，即U = NL1L2...Lm。

从而，我们得到了下三角矩阵L。

第四步，将方程组表示为LUx = B的形式。

具体地，我们将A, X 和B分解为L, U和x的乘积，即A = LU，X = UL，B = Ux。

从而，原方程组可以表示为LUx = B，即L(Ux) = B。

第五步，解方程组L(Ux) = B。

由于L是下三角矩阵，因此可以通过前代法求解得到Ux。

具体地，我们先通过Lw = B求解出向量w，然后再通过Ux = w求解出未知量向量x。

总的来说，矩阵的直接三角分解法（LU分解法）是一种常用的解线性方程组的方法。

它将原方程组表示为LUx = B的形式，然后通过前代法和回代法求解得到未知量向量x。

这种方法具有求解速度快、计算量小的优点，因此在实际应用中得到了广泛的应用。

线性方程组的解法及其应用摘要:线性方程组是线性代数的核心内容之一，其解法研究是代数学中经典且重要的研究课题.本文综述了几种不同类型的线性方程组的解法，如消元法、克拉默法则、广义逆矩阵法、直接三角形法、平方根法、追赶法，并以具体例子介绍不同解法的应用技巧. 在这些解法中，广义逆矩阵方法，具有表达式清晰，使用范围广的特点.另外，这些方法利于快速有效地解决线性方程组的求解问题，为解线性方程组提供一个简易平台，促进了理论与实际的结合.关键词:线性方程组解法广义逆矩阵应用实例1. 引言线性方程组理论是高等数学中十分重要的内容，而线性方程组的解法是利用线性方程组理论解决问题的关键.本文主要介绍线性方程组的广义逆矩阵法、追赶法、平方根法等求解方法，为求解线性方程组提供一个平台.文章也给出线性方程组在其他领域中的应用实例，揭示了各学科之间的内通性.首先，我们讨论一般线性方程组.这里所指的一般线性方程组形式为11112211211222221122,,.n n n n s s sn n s a x a x a x b a x a x a x b a x a x a x b +++=⎧⎪+++=⎪⎨⎪⎪+++=⎩ ()i()i 式中(1,2,,)i x i n =代表未知量，(1,2,,;1,2,,)ij a i s j n ==称为方程组的系数，(1,2,,)j b j n =称为常数项.线性方程组)(i 称为齐次线性方程组，如果常数项全为零，即120s b b b ====.令111212122212n n s s sn a a a a a a A a a a ⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦，12n x x X x ⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦, 12s b b B b ⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦，则()i 可用矩阵乘法表示为AX B =，,,.m n n m A C X C B C ⨯∈∈∈2. 线性方程组的解法2.1 消元法在初等代数里，我们已经学过用代入消元法和加减消元法解简单的二元、三元线性方程组.实际上，这个方法比用行列式解方程组更具有普遍性.但对于那些高元的线性方程组来说，消元法是比较繁琐的，不易使用.例 1 解线性方程组123123123123324,32511,23,237.x x x x x x x x x x x x +-=⎧⎪+-=⎪⎨++=⎪⎪-++=-⎩ 解 分别将第一个方程的(-3)倍，(-2)倍和2倍加到第二、三、四个方程上，整理得123232323324,71,555,7 1.x x x x x x x x x +-=⎧⎪-+=-⎪⎨-+=-⎪⎪-=⎩将此方程组第二个方程加到第四个方程上，使该方程两边全为零，并将第三个方程的两边乘以15-，得1232323324,71,1.x x x x x x x +-=⎧⎪-+=-⎨⎪-=⎩再将第三个方程的7倍加到第二个方程上，消去第二个方程中的未知量2x ，整理得123233324,1,6 6.x x x x x x +-=⎧⎪-=⎨⎪-=⎩最后解得123(,,)(2,0,1)T T x x x =--.正如消元法是我们接触比较早的，被我们所熟悉的一种方法，在此只给出三元线性方程组的解法，三元以上的方程组的具体理论、性质和解题过程详见参考文献[1]. 2.2 应用克莱姆法则对于未知个数与方程个数相等的情形，我们有定理1[1] 如果含有n 个方程的n 元线性方程组11112211211222221122,,.n 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 +++=⎧⎪+++=⎪⎨⎪⎪+++=⎩ ()ii的系数矩阵111212122212n n n n nn a a a a a a A a a a ⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦的行列式111212122212det 0n n n n nna a a a a a A a a a =≠，那么线性方程组()ii 有唯一解：det (1,2,,),det j j B x j n A==其中det j B 是把矩阵中第j 列换成线性方程组的常数项12,,,n b b b 所成的矩阵的行列式，即111,111,11222,122,121,1,1det,1,2,,.j j n j j n j n n j n n j nna ab a a a a b a a B j n a a b a a -+-+-+==此外，还可以叙述为，如果含有n 个未知数、n 个方程的线性方程组Ax b =的系数矩阵的行列式det 0A ≠，则线性方程组Ax b =一定有解，且解是唯一的. 例2 解线性方程组12342341242342344,3,31,73 3.x x x x x x x x x x x x x -+-=⎧⎪-+=-⎪⎨++=⎪⎪-++=-⎩ 解 由已知可得系数行列式12341234123401110111111det 16013015352073173148A ---------====≠----,因此线性方程组有唯一解.又因124234143431110311det 128,det 48,1301110137310331B B -------==-==-341244123401310113det 96,det 0.1311130107310733B B ------====--故线性方程组的解为1234(,,,)(8,3,6,0)T T x x x x =-.克莱姆法则主要给出了解与系数的明显关系，但只能应用于系数矩阵的行列式不为零的线性方程组，并且它进行计算是不方便的. 2.5 直接三角分解法[5]设有线性方程组11112211211222221122,,,n 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 +++=⎧⎪+++=⎪⎨⎪⎪+++=⎩或写成矩阵形式Ax b =，其中111212122212n n n n nn a a a a a a A a a a ⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦，12n x x x x ⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦，12n b b b b ⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦.若A 为非奇异矩阵，且有分解式A LU =，其中U 为上三角矩阵，L 为单位下三角矩阵，即11121212221,1111n n n n n nn u u u l u u A LU l l u -⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥==⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦, 则线性方程组Ax b =的求解等价于 解以下两个三角方程组：(1)Ly b =，求y ； (2)Ux y =，求x .直接三角形分解法求解线性方程组，基本步骤如下： 第一步： 11,(1,2,,),i i u a i n == 1111,(2,3,,)i i l a u i n ==,计算U 的第r 行，L 的第r 列元素，2,3,,r n =.第二步： 11,(,1,,)r ri ri rk ki k u a l u i r r n -==-=+∑.第三步： 11,(1,,;)r ir ir ik kr rr k l a l u u i r n r n -==(-)=+≠∑.求解Ly b =，Ux y =的计算公式如下：第四步： ()1111,,2,3,.i i i ik k k y b y b l y i n -==⎧⎪⎨=-=⎪⎩∑第五步： 1,(),(1,2,,1).n n nn n i i ik k ii k i x y u x y u x u i n n =+=⎧⎪⎨=-=--⎪⎩∑例5 求解线性方程组1231212321,42,227.x x x x x x x x ++=⎧⎪+=-⎨⎪-++=⎩解 由直接三角分解法第二、三步可得211100211410210012221131004A LU ⎡⎤⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥==--=⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥---⎣⎦⎣⎦⎣⎦. 于是线性方程组变为LUx b =，求解线性方程组(1,2,7)T Ly =-，得(1,4,4)T y =--；求解线性方程组(1,4,4)T Ux =--，得(1,2,1)T x =-.2.6 平方根法[7]在许多应用中，欲求解的线性方程组的系数矩阵是对称正定的.所谓平方根法，就是利用对称正定矩阵的三角分解而得到的求解具有对称正定矩阵的线性方程组的一中有效方法，目前在计算机上广泛应用平方根法解此类方程组.定理6[12] 若A 的各阶顺序主子式非零，则A 可以分解为A LDU =，其中L 是单位下三角矩阵，U 是单位上三角矩阵，D 是对角矩阵，且这种分解是唯一的.定理7[12] 设A 为对称正定矩阵，则存在三角分解T A LL =，其中L 是非奇异下三角形矩阵，且当限定L 的对角线元素为正时，这种分解是唯一的.应用对称正定矩阵的平方根法，可以解具有对称正定系数矩阵的线性方程组Ax b =，具体算法如下：1) 对j =1,2，，n ，计算11221()j jj jj jkk l a l -==-∑，11j ij ij ik jk k l a l l -==-∑(1,,)i j n =+.2) 求解线性方程组Ax b =等价于解两个三角方程组,.TLy b L x y =⎧⎨=⎩ 计算11()i i i ik k ii k y b l y l -==-∑，(i =1,2，，n ), 1()ni i ki kii k i x b lx l =+=-∑，(i n =,1n -,,2,1)，即可.例6 求解线性方程组12341161 4.25 2.750.5.1 2.75 3.5 1.25x x x -⎡⎤⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥-=-⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦ 解 设1111213121222232313233334111 4.25 2.751 2.75 3.5l l l l l l l l l l l l -⎡⎤⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥-=⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦, 由矩阵乘法得1121223132332,0.5,2,0.5, 1.5, 1.l l l l l l ==-====解下三角方程组123260.520.50.5 1.51 1.25y y y ⎡⎤⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥-=-⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦, 得1233,0.5,1,y y y ===-再由123230.520.50.5 1.511Tx x x ⎡⎤⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥-=⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥-⎣⎦⎣⎦⎣⎦, 得线性方程组的解为123(,,)(2,1,1)T T x x x =-.可以用消元法解此方程组,但发现此方程组的系数矩阵为正定矩阵，运用平方根法解这个方程组比较容易，而且理论分析指出，解对称正定方程组的平方根法是一个稳定的算法，其在工程计算中使用比较广泛. 2.7 追赶法[5]在许多实际问题中，都会要求解系数矩阵为对角占优的三对角方程组11112222211111iiii i n n n n n nn n n x k b c x k a b c a b c x k a b c x k a b x k -----⎡⎤⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦， 简记作 Ax k =， 其中A 满足下列对角占优条件：(1) 110b c >>;(2) i i i b a c ≥+, i a ,i c 0≠(i =2,3, ,1n -);(3) 0n n b c >>.由系数矩阵A 的特点，可以将A 分解为两个三角矩阵的乘积，即A LU =，其中L 为下三角矩阵，U 为单位上三角矩阵.求解线性方程组Ax k =等价于解两个三角方程组Ly k =与Ux y =，先后求y 与x ，从而得到以下解三角方程组的追赶法公式：第一步：计算的递推公式111c b β=，1()i i i i i c b a ββ-=-，(2i =，3，，1)n -;第二步：解Ly k =：111y k b =，11()()i i i i i i i y k a y b a β--=--，(2,3,,)i n =;第三步：解Ux y =：n n x y =，1i i i i x y x β+=-，(1,2,,2,1)i n n =--.例7 求解三对角线性方程组123421001131020111200210x x x x ⎡⎤⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦.解 设有三角分解111122222233333344441111b c p q a b c a p q a b c a p q a b a p ⎡⎤⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦， 由矩阵乘法易得111,,1,2,3.,2,3,4.i i i ii i i p b q c p i p b a q i -=⎧⎪==⎨⎪=-=⎩ 将已知系数矩阵的元素代人上式有11223342,12,52,25,35,53,73.p q p q p q p ==⎧⎪==⎪⎨==⎪⎪=⎩ 解线性方程组112233441121220p y p y p y p y ⎡⎤⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦, 得123412,35,73, 2.y y y y ====再解线性方程组111222333441111x y q x y q x y q x y ⎡⎤⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦,得原线性方程组的为1234(,,,)(0,1,1,2)T T x x x x =-.追赶法是以LU 分解为基础的求解方法，因此它的不足之处是当某个0=k u 时，就不能进行.但是当方程组的系数矩阵A 中有很多零元素时，利用三对角方程组系数矩阵的稀疏性，使零元素不参加运算，可以类似于追赶法来简化计算过程，从而极大地节省了计算量和存储量.这也是追赶法的最大特点.3. 应用举例3.1 线性方程组在解析几何中的应用例8 已知平面上三条不同直线的方程分别为1L ：230ax by c ++=，2L ：230bx cy a ++=，3L ：230cx ay b ++=，试证：这三条直线交于一点的充分必要条件为0a b c ++=.证 必要性 设三直线1L ，2L ，3L 交于一点，则线性方程组232323ax by cbx cy a cx ay b +=-⎧⎪+=-⎨⎪+=-⎩ ()iii有惟一解，故系数矩阵222a b A b c c a ⎡⎤⎢⎥=⎢⎥⎢⎥⎣⎦与增广矩阵232323a b c A b c a c a b --⎡⎤⎢⎥=-⎢⎥⎢⎥-⎣⎦的秩均为2，于是0A -=，即22223236()()23a bcA bc a a b c a b c ab ac bc ca b--=-=++++----=0,所以0a b c ++=.充分性 由0a b c ++=，则从必要性的证明可知，0A -=，故()3r A -<.由于22222132()2[()]2[()]0224a b ac b a a b b a b b b c =-=-++=-++≠, 故()()2r A r A -==.因此线性方程组()iii 有惟一解，即三直线1L ，2L ，3L 交于一点. 3.2 线性方程组在产品生产量中的应用例9 设有一个经济系统包括3个部门，在某一个生产周期内各部门间的消耗及最终产品如表所示：求各部门的总产品.解 设i x 表示第i 部门的总产品.由已知可以得到线性方程组()I A x y -=，其中0.250.10.1()0.20.20.10.10.10.2ij A a ⎡⎤⎢⎥==⎢⎥⎢⎥⎣⎦，0.750.10.10.20.80.10.10.10.8I A --⎡⎤⎢⎥-=--⎢⎥⎢⎥--⎣⎦，(245,90,175)T y =. 利用矩阵的初等变换可以求得1126181810()34118198912017116I A -⎡⎤⎢⎥-=⎢⎥⎢⎥⎣⎦, 所以线性方程组()I A x y -=的解为消耗系数 消耗部门 生产部门123最终产品1 0.25 0.1 0.1 2452 0.2 0.2 0.1 90 30.10.10.21751126181824540010()3411819902508912017116175300x I A y -⎡⎤⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥=-==⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦. 4. 结束语本文针对不同的线性方程组给出了一些计算方法，及线性方程组的应用实例.根据线性方程组自身所具有的特点，可以选择相应合适的方法，而对于那些特殊类型的线性方程组的解法，有待进一步的讨论与研究．参考文献：[1] 北京大学数学系几何与代数教研室前代数小组编. 高等代数[M].3版.北京：高等教育出版社，2003.105-112.[2] 白梅花. 线性方程组若干应用实例举例[J].科技资讯,2011,(27):200-201.[3] 康道坤，陈劲. 广义逆下线性方程组的解结构及其推广[J].大理学院学报,2011，10(4):7-9. [4] 卢刚.线性代数[M]. 北京：高等教育出版社,2002.64-72.[5] 李庆扬，王能超，易大义. 数值分析[M].4版.武汉：华中科技大学出版社,2006.177-185. [6] 苏育才，姜翠波，张跃辉. 矩阵理论[M].北京：科学出版社,2006.200-206. [7] 首都师范大学数学系组编. 数值分析[M].北京：科学出版社,2000.28-32.[8] 徐仲，张凯院，陆全，等. 矩阵论简明教程[M].2版.北京：科学出版社,2005.141-147. [9] 谢寿才，陈渊. 大学数学[M].北京：科学出版社,2010.37-40.[10] 徐仲，张凯院，陆全. 矩阵论[M].西安：西北工业大学出版社,2002.228-245.[11] 尹钊，钟卫民，赵丽君. 线性方程组的广义逆矩阵解法[J].哈尔滨师范大学自然科学学 报,1999,15(5):21-22. [12] 张明淳. 工程矩阵理论[M].1版.南京：东南大学出版社,1995.172-173.[13] 赵树嫄. 线性代数(经济应用数学基础)[M].4版.北京：中国人民大学出版社,2008.150-157.。

3
计算 LU 分解
利用矩阵乘法直接计算 LU 分解
1 l21 ln1
u11 u121 源自u22 ln,n1 1
u1n a11 a12 u2na21 a22
unn an1 an2
a1n a2n
ann
LU =A
比较等式两边的第一行得：u1j = a1j ( j = 1,…, n )U 的第一行
1 AL D L T l21 1
d1

d2
ln 1
ln,n1 1
1l21 1 dn
ln 1 ln2
1
计算公式
n
j1
aij likdkljk likdkljklijdjljj
k1
k1
aij likdkljk likdkljklijdjljj
n
j1
aij likljk likljkljjlij
k1
k1
a1n a2n
ann
9
Cholesky 分解算法
算法 ：(Cholesky 分解 )
for j = 1 to n
1
l jj
ajj

j1
l
2 jk
2
,

k1

j1

lij aij likljk ljj ,
8
计算 Cholesky 分解
Cholesky 分解的计算
直接比较等式两边的元素
l11 l21 ln1
l11 l21
l22

l22
ln,n1 lnn
计算公式
ln1 a11 a12 ln2a21 a22

算法 Gauss(A,a,b,n,x)
1. 消元 For k=1,2, … , n-1 1.1 if akk=0 , stop; 1.2 For i=k+1,k+2, …, n 1.2.1 l ik=aik /akk => aik 1.2.2 For j=k+1，k+2, … ,n ai j -aik ak j =>aij 1.2.3 bi -aik bk=> bi 2. 回代 2.1 bn / an=>xn; 2.2 For i=n-1,n-2, …, 2,1 2.2.1 bk => S 2.2.2 For j=k+1，k+2, … ,n S –akj xj =>S 2.2.3 S/ akk => xk a1 1 a1 2 a13 a2 1 a2 2 a23
线性方程组的直接解法
刘 斌
线性方程组的直接解法
§1 Gauss消去法 1.1 顺序Gauss消去法
1.2
§2 2.1 2.2 2.3
列主元Gauss消去法
Gauss消去法的矩阵运算 Doolittle分解法 平方根法
直接三角分解方法
2.4
追赶法
引入
在科学计算中，经常需要求解含有n个未知量 的n个方程构成的线性方程组 a11 x1 a12 x2 a1n xn b1 a21 x1 a22 x2 a2 n xn b2 (1) an1 x1 an 2 x2 ann xn bn
(1) a12 ( 2) a22 0
(1) (1) a13 a1 n ( 2) ( 2) a23 a2 n ( 3) ( 3) a33 a3 n
0

3 1 2
H2H1A
0
1
1
R
0
0
0
矩阵分析简明教程
Q
H
H 1
21
1 3
1
2 2
2 1 2
2
2 1
所求的QR分解为
A QR
8
0 1 1
矩阵分析简明教程
1 5
x1 2x2 x3 5x2 3x3
0 1
12 5
x3
4 5
(
5 12
)
3 5
x1
2x2 x2
1 3 0
x3
1 3
(2)
x1 x2
1 3 0
x3 1 3
(II )
矩阵分析简明教程
用矩阵形式表示，系数矩阵
1 2 1 r12 (3) 1 2 1
角方阵 R ，使得
A QR
当 m = n 时 ，Q 就 是 酉 矩 阵 或 正 交 矩 阵 。
矩阵分析简明教程
例 1 将下列矩阵进行QR分解：
1 2 2
A
1 0
0 1
2 1
4
矩阵分析简明教程
解： 1 (1,1，0, )T， 1 1 (1,1，0)T
1
||
1 1
||
1 (1,1, 0)T 2
定理4.2.3 设 e1 1, 0,, 0T C n ,
x1 , x2 ,, xn T C n , 0
令
x1
x1 ,
,
x1
0 ，u
e1
x1 0
e1
H E 2uuH是n 阶Householder矩阵，且
H -e1
矩阵分析简明教程
定理4.2.4（QR分解）设 A为 任 一 n 阶 矩 阵 则必存在 n 阶酉矩阵 Q 和 n 阶上三角方

如果U的第1至k-1列和L的第1至k-1列已经算出，则由
ak1 lk1 , k 2,3, u11
k r 1
, n.
（4.2.2）
a l u ,j k , k 1 , , n , kj kr rj
可得U的第k行元素
ukj =akj 同理，由
k

k 1 r 1
l kr u rj
用向后回代的方法即可求得x。设x=（x1 ，x2， · · · xn) T, y=（y1, y2, · · · yn) T,b= （b1 ，b2， · · · bn) T, 则有计算公式
y b 1 1 i 1 （4.2.5） y b l y 1 , 2 ,..., n i i ir r ,i r 1
(4.2.8)
利用(4.2.7)和(4.2.7)可得
u1 b 1 n li ai / ui1, i 2,3,... u b l c , i 2,3,... n i i i1 i
(4.2.9)
由此可求得L和U的所有元素.。解原方程组Ax=b可分为两步Ly=d 和Ux=y,计算公式为
由于方车程组的右端参与了消元计算，所以Ly=Pb的解为y=b（3）= （20，14/3，216/39） T 。解Ux=y得x=（1，2，3） T
4.2.2
三对角方程组的追赶法
b a1 A c1 b c2 a n1 bn1 an c n1 bn



(k ) akk

uk 1,k 1 l k , k 1 l n , k 1

(k ) ank
u1n u2 n uk 1,n (k ) akn (k ) ann

u1i (i 1, 2, , n) 与L的第1列元素 li1 (i 2,3, , n)
(b) 对k+2,3,…,n 按计算公式(3),(4)依次
计算U的第k行元素 uki (i k, k 1, , n) 与L的第
k列元素 lik (i k 1, , n; k n)
20 求解三角形方程组LY=b，即按计算公
(i k, k 1, , n) （3）
k 1
lik (aik liju jk ) / ukk j 1
(i k 1, , n; k n) （4）
在我们利用杜利特尔矩阵分解解线性方程 组AX=b时,只要实现矩阵分解A=LU,依次解三角 形方程组LY=b与UX=Y即可。
计算公式：
y1
yk
对那些明确是1或是0的元素不再求。 由矩阵乘法规则与相等条件,
利用 aij 在上述计算过程中，
导出计算 lij 或 uij 的公式。
例如
第一步计算由 ai1 li1u11 得
u1i a1i (i 1,2, ,n)
第二步计算由 a1i u1i 得 li1 ai1 / u11 (i 2,3, ,n)
, n 1)
因此有 1 c1 / a1且0 1 1 由 a2 b2 a21 b2 a2 1 b2 a2 c2 0 有 2 c2 / a2且0 2 1
一般地，用归纳法可以证明
ai ci 0 （即0 i 1） (i 1, 2, , n 1)
因此我们从关系式（2）解出待定系数为
5 3 2, 2 3 5
3
2
3
4
b 7
1
0
2、用追赶法求方程组的解
4 1 0 0 x1 3
1
4
1

类似选主元法
练习 利用LU分解法求解方程组
1 2 3 x1 2 1 3 5 x2 4. 1 3 6 x3 5
1001 2 3 2 1 答L： U 110 01 2 ， y 2 ,x 0 .
111 001 1 1
二、解三对角方程组的追赶法
在数值求解常微分方程边值问题、热传导方程和建立
二、向量和矩阵的范数
定义1 ( 向量范数) x 和 y 是 Rn 中的任意向量 , 向量范数‖•‖是定义
在 Rn上的实值函数, 它满足:
(1) ‖ x ‖≥0, 并且当且仅当 x=0 时, ‖ x ‖=0;
(2) ‖k x ‖=|k| ‖ x ‖, k 是一个实数;
(3) ‖ x + y ‖≤ ‖ x ‖+ ‖ y ‖
1 0 01 2 3
A 2 3
1 5
0 0 1 0
1 0
4
24
LU
3=-72/-24; 2=[-10+4*3]/1;
求解
1=[14-(2*2+3*3)]/1]
Ly (14, 18, 20)T , 得y (14, 10,72)T 同理当 ukk 0或 Ux (14, 10, 72)T , 得x (1, 2, 3)T 很小时，可用
子式 Di 0(i 1,2,,k)，即
a11 Di
ai1
a1i
aii
0aa1i((i1i1))
0 Di
Di1 0
由于高斯消去法过在程消中元可能ak(出 kk) 现 0的情况， 这时消去法将无；法即进使行主a元 k(kk) 素0但很小时， 用其作除数，会他导元致素其数量级的长严和重舍增
入误差的扩散，使最得后计也算的解不可靠。

17
定理 1 矩阵 A 可以三角分解的条件如下：
1. 若矩阵 A 的所有顺序主子式不等于零; 2. 若矩阵 A 对称正定; 3. 若矩阵 A 严格对角占优，即：
akk akj , k 1, 2, n 。
j k
18
2 2 1 A 4 5 4 例 3 已知矩阵 ，检验 A 是否满足三角分解的条件， 2 4 3
n n n n a11 a1 a b k 1n 1 n n n akk akn bk n n ann bn
7
消元公式：
(0) aij aij , bi(0) bi , ( i , j 1, 2, ..., n) For k 1, 2, ..., n 1 (k ) ( k 1) ( k 1) aij aij lik akj b( k ) b( k 1) l b( k 1) i i ik k ( k 1) ( k 1) akk ; i , j k 1, ..., n lik aik
利用增广矩阵的初等行变换法表示为：
1 1 2 2 1 1 2 2 1 1 2 2 2 1 1 2 1 3 2 1 3 2 A b 4 1 2 1 3 6 7 3 1
k 1
1
ai1 lik uk1 li1u11 ，
k 1
1
即： li1 ai1 u11 i 2, 3,, n .
这是 U 的第一行和 L 的第一列。
22
设： U 的前 m 1 行和 L 前 m 1 列均已算出，那么：
amj lmk ukj lmk ukj lmmumj ,

直接三角分解法
• 直接三角分解法简介 • 直接三角分解法的算法原理 • 直接三角分解法的实现过程 • 直接三角分解法的应用案例 • 直接三角分解法的优化与改进
01
直接三角分解法简介
定义与特点
定义
高效
直接三角分解法是一种线性代数中的方法 ，用于将一个矩阵分解为一个下三角矩阵 和一个上三角矩阵的乘积。
计算分解矩阵
根据所选方法计算出左奇 异矩阵、右奇异矩阵和奇 异值矩阵。
提取关键信息
从分解矩阵中提取关键信 息，如主成分或特征向量， 用于后续分析。
结果
可视化结果
将分解结果以图表、图像等形式呈现，便于直观 理解。
量化分析
对分解结果进行量化分析，如计算各主成分的贡 献率或方差解释率。
决策建议
根据分析结果提供决策建议，指导后续工作。
图像修复
通过直接三角分解法，可以将图像中的损坏或缺失部分进行修复或替 换，从而得到完整的图像。
05
直接三角分解法的优化与改进
算法优化
减少计算量
通过选择合适的算法和数据结构，减少不必要的计算和重复计算， 提高算法的效率。
并行化处理
将算法中的计算任务分解为多个子任务，并利用多核处理器或多 线程技术并行处理，加快计算速度。
利用三角分解法，可以方便地计算矩阵的逆和行列式，对于解决一些数学问题具有重要意义。
在机器学习中的应用
矩阵分解
在推荐系统和协同过滤等机器学习算法中，矩阵分解是一种常见的方法。通过直接三角分 解法，可以将矩阵分解成低秩矩阵和稀疏矩阵，从而更好地表示用户和物品之间的关系。
降维处理
在处理高维数据时，直接三角分解法可以用于降维处理，将高维数据投影到低维空间，保 留主要特征，降低计算复杂度。

线性代数方程组的解法关键词：线性代数方程组；高斯消元法；列主元消元法；三角分解法；杜立特尔分解法；迭代法；雅可比迭代法；高斯-赛德尔迭代法1引言目前，解线性代数方程组在计算机上常用的的方法大致把它分为两类：“直接法”与“迭代法”.在线性代数中曾指出阶线性代数方程组有唯一的解，并且可以用克拉默法则求方程组的解，初次看来问题已经解决，但从使用效果看并不是这样的.因为求阶线性代数方程组，如果用克拉默法则，需要计算个阶行列式，每个阶行列式为项之和，每项又是个元素的乘积，所以计算中仅乘法次数就高达次，当较大时，它的计算量是非常惊人的.因为现在所碰到的很多问题都需要很大的计算量，故需要好用的算法来求解.先来回顾一下回代过程和迭代过程.(1)是一个三角形方程组，当有唯一解时，可以用反推的方式求解，也就是先从第个方程解得， (2)然后代入第个方程，可得到， (3)如此继续下去，假设已得到，， , ,代进第个方程即得的计算， (4)上述求解的过程叫做回代过程.定义1[1] (向量的范数) 若向量的某个实值函数满足1.是非负的，即且的充要条件是 ;2.是齐次的，即 ;3.三角不等式，即对，总是有.那么上向量的范数（或模）就是 .下面给几个最常遇到的向量范数.向量的“1”范数：(5)向量的“2”范数：(6)向量的范数：(7)例1设求 , , .解由式（5）,（6）及（7）知.定义2若矩阵的某个实值函数满足1.是非负的，即且的充要条件是 ;2.是齐次的，即 ;3.三角不等式，即对总有;1.矩阵的乘法不等式，即对总有，那么称为上矩阵的范数（或模）.表 1是矩阵几个常用算子范数的定义与算式.表 1范数名称记号定义计算公式“1”范数（又名列模）“2”范数（又名谱模）“”范数（又名行模）的极限就是方程组的解向量，这时候在给定允许的误差内，只要适当的大,就可以作为方程组在满足精度要求条件下的近似解.这种求近似解的方法就是解线性方程组的一类基本的迭代解法，其中称为迭代矩阵，公式（9）称迭代公式（或迭代过程）,由迭代公式得到的序列叫做迭代序列.如果迭代的序列是收敛的，则称为迭代法收敛；如果迭代的序列是不收敛，则称它是迭代法发散.定理3设 .如果约化主元素，则可以利用高斯消元的方法把方程组约化成三角形方程组来求解，其计算公式如下：（1）消元计算：对依次计算（2）回代计算：3用高斯消元法与列主元消元法解线性代数方程组（重点）！3.1 高斯消元法解方程组用高斯消元的方法求线性代数方程组的解的整个计算过程可分为两个环节，也就是利用按照次序消去未知数的方法，把原来的方程组转化成跟它同解的三角形方程组（这个转化的过程叫消元过程），再通过回代过程求三角形方程组的解，最终得到原来方程组的解.其中按照方程的顺进行消元的高斯消元法，又叫顺序消元法.3.2列主元消元法解方程组列主元消元法实际上是一种行交换的消元法，它跟顺序消元法比较而言，主要特点是在进行第次消元前，不管的值是否等于零，都在子块的第一列中选择一个元，使，并将中的第行元与第行元互相变换（相当于交换同解方程组中的第个方程），然后再进行消元计算得到结果.注：列主元素法的精度虽然稍低于全主元素法[1]，但它计算简单，相对比全主元素法它的工作的量大大减少，并且从计算经验和理论分析都可以表明，它与全主元素法同样拥有很好的值稳定性，列主元素法是求解中小型浓密型方程组的最好的方法之一.4用三角分解法解线性代数方程组4.1 矩阵的三角分解定义4把一个阶矩阵分解成两个三角矩阵相乘的形式称为矩阵的三角分解.常见的矩阵三角分解是其中是下三角形的矩阵,是上三角形的矩阵.定理5[1]（矩阵三角分解基本定理）设 .若的顺序主子式，那么存在唯一的杜利特尔分解其中是单位下三角形矩阵，为非奇异的上三角形矩阵.如果是单位下三角形的矩阵，是上三角形的矩阵，那么把这种分解法称为杜利特尔分解法，其中杜利特尔分解法是这种三角分解的一种特例，下面主要介绍利用杜利特尔分解法来求方程组的解.4.2 用杜利特尔分解法解线性代数方程组用杜利特尔分解法解方程组的步骤可以把它归纳为（1）实现分解，也就是1.按算式（11）（12）依次计算的第一行元与的第一列元；1.对按算式（13）（14）依次计算的第行元与的第列元.（2）求解三角形方程组，即按算式依次计算 .（3）求解三角形方程组，即按算式依次计算.利用杜利特尔分解法解方程组与高斯消元法是相似的，它重要的优点是：在利用分解，解有相同的系数矩阵的方程组时,用杜利特尔分解法非常方便，只用两个式子就可以得到方程组的解.5用迭代法解线性代数方程组用迭代法求方程组的解，需要考虑迭代过程的收敛性，在下面的讨论中，都假设方程组的系数矩阵的对角阵是不为零的.5.1 用雅可比迭代法解方程组对于一般线性方程组，如果从第个方程解出，就可以把它转化成等价的方程组. （15）从而可以得到对应的迭代公式（16）这就是解一般方程组的分量形式的雅可比(Jacobi)迭代公式.如果把它改成（17）并把系数矩阵表示成（18）其中则可以看出式的左右两端分别是向量和的第个分量，故因为可逆，所以于是就可以得到是雅可比迭代的公式.其中（称为雅可比迭代矩阵）， .5.2 用高斯-赛德尔迭代法解方程组高斯-赛德尔迭代法也是常用的迭代法，设线性代数方程组为，则高斯-赛德尔迭代法的迭代公式为（19）其中迭代法（19）就称为高斯-赛德尔迭代法.通过雅可比迭代法类似的途径，就可以得到矩阵的表达式其中（称为高斯-赛德尔迭代矩阵）， .高斯-赛德尔迭代法与雅可比迭代法都有算式简单、容易在计算机上实现等优点，但是用计算机来计算时，雅可比迭代法需要两组工作单元用来寄存与的量，而高斯赛-德尔迭代法只需一组工作单元存放或的分量.对于给定的线性方程组，用这两种方法求解可能都收敛或者都不收敛，也可能一个收敛另一个不收敛，两种方法的收敛速度也不一样.5.3 迭代法的收敛条件与误差分析定义6[1]矩阵全部的特征值的模的最大值，叫做矩阵的谱半径，记作 ,即.定理7[1]对任意初始向量迭代过程收敛的充要条件是；当时，越小，那么其收敛的速度是越快的.由定理7可知，用雅可比迭代法求解时，其迭代的过程是收敛的，而用高斯-赛德尔迭代法来求解,其迭代的过程是发散的.在不同条件下，收敛的速度是不同的，对同一矩阵，一种方法是收敛的，一种方法发散.第 7 页。