当前位置：文档之家 › 高斯变换与矩阵三角分解(课堂PPT)

高斯变换与矩阵三角分解(课堂PPT)

  • 格式：ppt
  • 大小：1.11 MB
  • 文档页数：54

下载文档原格式

  / 54

合集下载

ch05b矩阵三角分解

ch05b矩阵三角分解
第五章 线性方程组直接解法
第三节 矩阵三角分解
矩阵三角分解
将一个矩阵分解成结构简单的三角形矩阵的乘积称为 矩阵的三角分解。 矩阵的三角分解。 高斯消去过程其实就是一个矩阵的三角分解过程。 高斯消去过程其实就是一个矩阵的三角分解过程。
LU分解紧凑方式 分解紧凑方式直接利用矩阵乘来自来计算 LU分解 分解令
对称矩阵的Cholesky分解
又因为 A是正定的，则 A的顺序主子式均大于零 故有 ∆ 1 = d1 > 0 得 d1 > 0；由 ∆ 2 = d1d 2 > 0 得 d n > 0。
得 d 2 > 0； ......;由 ∆ n = d1d 2 ...... d n > 0 即 d1 , d 2 ,..., d n均大于零
a ij =
∑1 l ik l jk k=
n
∑1 l ik l jk k=
∑1 k=
+ l ij l jj
Ax=b LLTx=b 记LTx=y,Ly=b 求出y, 由Ly=b求出 , 求出 再由L 求出x 再由 Tx=y求出 求出
公式：故对于j=1,2, ,n 公式：故对于j=1,2,…,n j=1,2, 1）求L l =（ a − j − 1 l 2）1 2
对称矩阵的Cholesky分解
由Doolittle分解，A有唯一分解
A = LU = A = ( LU ) = U L
T T T T
即 U T LT = LU，有U T = L，LT = U 所以 LT = U，也就是A = LLT。
对称矩阵的Cholesky分解
定理 设A为对称正定矩阵，则存在唯一 分解A=LDLT，其中L为单位下三角阵，
1 2 1 2 1 2

高斯变换与矩阵三角分解(课堂PPT)

高斯变换与矩阵三角分解(课堂PPT)
数值分析
第五节 高斯变换阵与矩阵的三角分解
一、Gauss变换阵
设 向 量 l j 0,...0, l j1, j , l j2, j ,...,ln, j T Rn
e j 0,...0,1,0,...,0T Rn
( j)
定义Gauss变换阵为
0
M
0
Lj
I l jeTj
I
l
j1
定义消元乘数 m ij xi x j ,(i j 1, j 2, ..., n)
1
O
1
0
M
0
Lj I l jeTj
1 m j1, j
M
1 O
其中
l
j
m j1, j
M
mn, j
1
mn, j
于是有
Lj x y (x1, x2,..., xj ,0,...,0)T
以下各行进行初等行变换。
3. 用Lj右乘矩阵A,只改变A的第j列
a11 a12 a13 1 0
例：AL1
a21
a22
a23
m21
1
a31 a32 a33 m31 0
a11 a12m21 a13m31 a12
a21
a22m21
a23m31
a22
a31 a32m21 a33m31 a32
LI U
数值分析 23
数值分析
LU分解的MATLAB程序
function A=lud(A)
%i 功 能k ： 1对,L方阵, nA作三角分解A=LU,其中，
%
L为单位下三角阵，U为上三角阵，
%（输1）入：m方ik 阵Aa。ik(k ) / akk(k )
%%（输 注2出意）：：ai紧 当j(k凑A1的存) 主储a元Aij==(k0[)L时\U退m].出ikaMkja(tkl)a，b.j k 1,L , n

高斯消元法与矩阵的初等变换.ppt

高斯消元法与矩阵的初等变换.ppt

6
1

2
2020/1/1
线性代数教学课件
18
step 6. 将 矩 阵 化 成 B 型 矩 阵 2 r3
1 2 5 3 6 14
0 0 0 0
1 0
0 0
7 2 1
6 2
7 2

r3

r2
;
6 r3 r1
1 2 5 3 0 2
第二章 矩 阵
第一节 高斯消元法与矩阵的初等变换 第二节 矩阵的运算 第三节 特殊矩阵 第四节 逆矩阵 第五节 分块矩阵 第六节 利用初等变换求逆矩阵
第七节 矩阵的秩
2020/1/1
线性代数教学课件
1
第一节 高斯消元法与矩阵的初等变换
一 消元法解方程
二、矩阵的定义 三 矩阵的初等变换
四 方程组的求解问题 五 利用 Gauss 消员元法求解线性方程
2020/1/1
线性代数教学课件
23
非齐次线性方程组(1)的解的讨论
A (A d) B
(B
1 0 0 c1r1 c1n d1 0 1 0 c2r1 c2n d2



d ) 0 0 1 crr1 crn dr
0 0 0 b3
方程组(3)是方程组(2)同解的梯形方程组。
如果 b 3 方程组(3)无解，从而方程组(2)无
解。当 b 3 时，方程组(3)改写为
Βιβλιοθήκη x1 x2 2 3x3 1 x3
其中变量 x3 可自由选取，
令 x3 k 代入上式，得到
2020/1/1
线性代数教学课件
(5)

高斯消元法与矩阵的初等变换精品PPT课件

高斯消元法与矩阵的初等变换精品PPT课件

0, 6,
2 3
3x2 3x3 4x4 3, 4
1 x1 x2 2 x3 x4 4, 1
2 2
3 52 4 32
x2 x3 x4 0, 2x4 6, x4 3,
2 3 4
7
x1 x2 2 x3 x4 4, 1
x2 x3 x4 0, 2x4 6,
矩阵的初等变换
初等行变换 初等列变换
矩阵的初等变换是矩阵的一种基本运算，应用广泛.
12
用矩阵的初等行变换 解方程组（1）：
2x1 x2 x3 x4 2, 1
4xx116xx2222xx33x24x4
4, 4,
2 3
3x1 6x2 9x3 7x4 9, 4
（1）
2
A
1 4 3
（1）对于每个非零行(元素不全为0)的非0首元 都出现在上一行非0首元的右边； （2）零行(元素全为0) 都在下方。
1 1 2 1 4
0 1 1 1 0
0 0
0 0
0 0
1 0
3 0
是行阶梯形矩阵
1 2 1 5 4
0 1 1 2 3
0 0
2 0
0 0
1 0
3 0
不是行阶梯形矩阵
a2n
，X
amn
x 1
x2
,
x n
b
b 1 b2 b m
A [ A, b]
2
齐次方程组：AX = 0;
非齐次方程组：AX = b, b 0
(b中至少有一分量不为零)
x 1
定义 X
x2
使得AX
=
b
成立，则称X为AX
=
b的解：
xn

数值分析第4讲矩阵的三角分解法

数值分析第4讲矩阵的三角分解法

a1 b1
1
1 1
c2
a2
cn
bn1 an
2
2
n
n
1
n 1
1
ii
ci ai
, i 2,
ci i1 ,
,n i 1,
,n
i bi i , i 1, , n
, c1 0
yi
(
fi
ci yi1)
i
xi yi i xi1 ,
, i 1, , n
i n, ,1 (n 0)
r 1
这时lir 1
ari uri ari lrkuki (i r 1, , n, r n) k 1
数值分析
求解Ly=Pb及Ux=y的算法：
2. 对i 1,2, ,n 1,
(1) t Ip(i) (2) 如果i t则转(3)
bi bt
(3) 继续循环
i 1 3. bi bi lik bk (i 2,3, , n)
bi lij y j
yi
j 1
lii
, i 1, , n
n
xi yi uij x j , i n, ,1 j i 1
数值分析
数值分析
定理2.4 若矩阵A非奇异，则存在置换矩阵Q， 使得QA可以作Doolittle分解
QA=LU 其中L是单位下三角矩阵，U是上三角矩阵。
数值分析
选主元直接三角分解法
数值分析
所以，有计算过程如下：
i ai ci i1
i
yi
bi
i
( fi
ci
yi 1 )
i
xk yk k xk1 ,
1 2 n和y1 y2 yn 为追；xn xn1 x1为赶.

数值分析矩阵的三角分解

数值分析矩阵的三角分解
= 2 1 0 0 1 0 1 0
1 0 0 = 2 1 0
1 1 1
0 0 1 0 1 1
数值分析
数值分析
记 A A(1) a1M(11)
... O
a1M(1n)
1(1)
,
(1) 2
,
...,
(1) n
an(11)
...
a(1) nn
第一步：设a1(11) 0, 取mi1 aa（（1i1111））, i 2, ..., n
j
0
L
010L
0
M
ln j
数值分析
数值分析
1
Lj
I
l jeTj
O 1 1 l j1 j 1
M
O
ln j
1 0 0 0
L2
0 0
0
1 l3,2 l4,2
0 1 0
0 0
I
l 2e2T
1
1
数值分析
数值分析
Gauss变换阵的性质：
1
O
1
1. Lj1 I l jeTj
m21
M
mn1
1 O
a(1) 11 M
... O
1
a(1) n1
...
a1M(1n)
a(1) nn
a1(11)
L1 A(1)
a(1) 12
L
a(2) 22
L
MO
a(2) n2
L
a(1) 1n
a(2) 2n
M
A( 2 )
1(
2
)
,
(2 2
)
,
...,
(2) n
0
3

矩阵分解ppt课件

2 1 6 5 1 2 2 8
1 0 0 01 0 0 01 0 2 1

1 2
1 1
0 1
0 0 0 0
2 0
0 1
0 0 0 0
1 0
1 1
2 L~DU~ 1
1
2 1
2
1
0
0
0
5 0
0
0
1
Department of Mathematics
Department of Mathematics
7
思 路
通过比较法直接导出 L ~和 U 的计算公式。
a11 a12 a1n 1
u11 u12 u1n
Aa21
a22
a2nl21
1


u22 u2n
an1 an2 ann ln1 1
L 为一般下三角阵而 U~为单位上三角阵的分解称
为L ~C为rou单t 位分下解三。角阵而 U为一般上三角阵的分解
称为Doolittle分解
证明: AL~U 设: AL ~U
L ~ (li) jn n ,(lij 0 ,ij)
U (u i) jn n ,(u ij 0 ,ij)
1 2 4 5l21 l22 0 00 1 u23 u24
2 1 6 5 1 2 2 8
ll43
1 1
l32 l42
l33 l43
00 l440
0 0
1 0
u134
Department of Mathematics
10
由此: l11 1, l21 1, l31 2, l41 1
2 1 6 5 2 1 1 00 0 1 1 1 2 2 8 1 2 2 50 0 0 1

《矩阵的分解》课件

矩阵分解的算法实 现
高斯消元法
基本思想：通过行变换将矩阵 化为上三角矩阵或对角矩阵
步骤：选择主元素、消元、回 代
应用：求解线性方程组、求逆 矩阵、求特征值和特征向量
优点：计算量小，易于实现， 适用于稀疏矩阵和带状矩阵
迭代法
迭代法的基本思想：通过不断迭代， 逐步逼近目标解
迭代法的应用：在矩阵分解、数值 优化、图像处理等领域有广泛应用
U：上三角矩阵，对角线以上元素为0
LDU分解的应用：求解线性方程组、计算矩阵的逆矩阵等
平方根分解
平方根分解的定义：将矩阵分解为 两个矩阵的乘积，其中一个矩阵是 单位矩阵，另一个矩阵是矩阵的平 方根。
平方根分解的应用：平方根分解在 数值计算、线性代数、优化等领域 有着广泛的应用。
添加标题
添加标题
添加标题
添加标题
添加标题
添加标题
迭代法的步骤：设定初始值，计算 迭代函数，更新迭代值，直到满足 停止条件
迭代法的优缺点：优点是简单易实 现，缺点是收敛速度慢，容易陷入 局部最优解
共轭梯度法
共轭梯度法是一种求解线性方程组的迭代方法 共轭梯度法的基本思想是利用共轭梯度方向进行迭代 共轭梯度法的优点是收敛速度快，稳定性好 共轭梯度法的缺点是计算量大，需要存储大量的中间结果
a. 选取一组向量 b. 计算向量组的内积 c. 计算向量组的正交化向量 d. 重复步骤b和c，直到所有向量都正交
优点： a. 简单易行 b. 适用于任意维数的向量组
a. 简单易行 b. 适用于任意维数的向量组
应用： a. 矩阵的正交分解 b. 线性代数的其他领域
a. 矩阵的正交分解 b. 线性代数的其他领域
添加标题
添加标题

三角分解


列主元素高斯消去法相当于先进行一系列行交换后再对 PAX Pb 应用顺序高斯消去法.
定理8(列主元三角分解) 若A为非奇异矩阵, 则存在排列 矩阵P使得 PA LU 其中L为单位下三角矩阵,U为上三角矩阵. 说明: L, U, Ip的存贮.
§7.4
高斯消去法的变形
设有线性方程组：AX=b
a11 a12 a1n x1 b1 a x b a22 a2 n 21 , X 2 , b 2 . A 如何简单的实现三 a x 角分解？ bn an 2 ann n1 n
本节主要内容
1、回顾高斯消去法与三角分解的关系 2、三角分解的条件、方法与应用
下面用矩阵描述列主元消去法
L1I1,i1 A(1) A( 2) , L1I1,i1b(1) b( 2) ,, Lk I k ,ik A( k ) A( k 1) , Lk I k ,ik b( k ) b( k 1) .
其中I k ,ik 为初等置换阵.
于是 Ln 1I n 1,in1 L2 I 2,i2 L1I1,i1 A A( n ) U . ~ ~ P为排列矩阵 即 P A U , P b b( n ) . ~ L为单位下三角矩阵 下面就n 4考察P .
UA
( 4)
L3 I3,i3 L2 I 2,i2 L1I1,i1 A
PA 选主元三角分解算法： A, 整型Ip(n)记录主行, x b.
1. 对r 1,2,, n, r 1 (1) 计算si : air si air lik ukr (i r ,, n). k 1 (2) 选主元：取ir 使得 sir max si ，Ip(r ) ir

矩阵的三角分解

(0) (1)
r −1 air 可定义 cir = r −1 ，并构造 Frobenius 矩阵 arr
r −1
6
1 1 Lr = cr +1r cnr
1 1
1 1 1 → L− = r −cr +1r −cnr
(0) a12 (1) a22
a1(0) n (1) a2 n ( n −1) ann
则完成了消元的过程
而消元法能进行下去的条件是 ∆ r = ≠ 0 (r 1, 2,, n − 1) 二、 LU 分解与 LDU 分解
= A(0) = L1 A(1) = L1L2 A(2) = = L1L2 L3 Ln −1 A( n −1) A
第十讲 矩阵的三角分解
1
一、 Gauss 消元法的矩阵形式 n 元线性方程组
b1 a11ξ1 + a12ξ 2 + + a1nξ n = a ξ + a ξ + + a ξ = b2 21 1 22 2 2n n bn an1ξ1 + an 2ξ 2 + + annξ n = A = (aij ) T x = [ ξ , ξ , ξ ] n 1 2 b = [b , b b ]T 1 2 n
计算可得
→
0 1 −c 1 21 −1 L1 = c 0 1 − n1
3
(0) a11 −1 (0) (1) = = A L 1 A 0
(0) a1(0) a12 n (1) (1) a2 a22 n (1) (1) an a nn 2
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

1
对A(1)的第一列
(1) 1
构
造L1 , 使L11(1) a11 , 0, ..., 0 T .
L1
m21
M
1
O
mn1
1
1
L1 A(1)
m21
M
mn1
1 O
a1M(11)
... O
1 an(11) ...
a1M(1n)
a(1) nn
数值分析 14
数值分析
1
L1 A(1)
0
3 0
1
9
0
数值分析 10
数值分析
二、矩阵的三角分解 1. 顺序高斯消元与LU分解的等价性
顺序高斯消元的基本思想：将矩阵A的下三角部分 消为零，即
aa12((1111))
a(1) 12
a(1) 22
L L
L L L
an(11)
a(1) n2
L
a(1) 1n
a(1) 2n
L
a(1) nn
1 2 3 0 1 2
0 0 3
数值分析 12
数值分析 1 2 3 例2 求矩阵A= 2 3 4的LU分解.
1 3 2
解：A(3) L2 A(2) L2 L1 A
A L11 L21U
1 2 3 0 1 2 =U
0 0 3
1 0 0
L1
=
2
1
0
1 0 1
1 0 0
L2
=
0
1
0
0 1 1
j
0
L
010L
0
M
ln j
数值分析 1
数值分析
1
O
Lj
I
l jeTj
1 1
l j1 j 1
M
O
ln j
1 0 0 0
L2
0 0
0
1 l3,2 l4,2
0 1 0
0 0
I
l 2e2T
1
1
数值分析 2
数值分析
Gauss变换阵的性质：
1
O
1
1. Lj1 I l jeTj
以下各行进行初等行变换。
3. 用Lj右乘矩阵A,只改变A的第j列
a11 a12 a13 1 0
例：AL1
a21
a22
a23
m21
1
a31 a32 a33 m31 0
a11 a12m21 a13m31 a12
a21
a22m21
a23m31
a22
a31 a32m21 a33m31 a32
n1 n1
)
1
l21
1
l31 M
l32 M
1
O
M M
1
ln1 ln2 ln3 ... ln,n1 1
数值分析 4
数值分析
3.
L
1 1
L
1 2
...
L
1 n1
(I
l 1e1T
)( I
l 2e2T
)...( I
l
eT
n1 n1
)
1
l21
1
l31 M
l32 M
1
O
M M
1
ln1 ln2 ln3 ... ln,n1 1
定义消元乘数 m ij xi x j ,(i j 1, j 2, ..., n)
1
O
1
0
M
0
Lj I l jeTj
1 m j1, j
M
1 O
其中
l
j
m j1, j
M
mn, j
1
mn, j
于是有
Lj x y (x1, x2,..., xj ,0,...,0)T
a(1) 11
a(1) 12
L
a(2) 22
L
O
a(1) 1n
a(2) 2n
M
a(n) nn
数值分析 11
数值分析
例1 用Gauss消元法将矩阵A
化为上三角矩阵
1 2 3 A= 2 3 4
1 3 2
解：n 3, a11 1 0
m21 a21 / a11 2 / 1 2 m31 a31 / a11 1 / 1 1
数值分析 7
数值分析
例：x ( x1 , x2 , x3 )T，x1 0
1 0
L1
m2，1
1
m3，1 0
0
0，m 1
i1
xi
x1
,(i
2，3)
10
L1 x
x2
x1
1
x3
x1
0
0
x1
x1
0
x2
0
x3 0
1
数值分析 8
数值分析
2. 用Lj左乘矩阵A, Lj A相当于对A的第j行
数值分析
第五节 高斯变换阵与矩阵的三角分解
一、Gauss变换阵
设 向 量 l j 0,...0, l j1, j , l j2, j ,...,ln, j T Rn
e j 0,...0,1,0,...,0T Rn
( j)
定义Gauss变换阵为
0
M
0
Lj
I l jeTjIlj1源自m21Mmn1
1 O
1
a(1) 11 M
a(1) n1
... O ...
a1M(1n)
a(1) nn
a1(11)
L1 A(1)
a(1) 12
L
a(2) 22
L
MO
a(2) n2
L
a(1) 1n
a(2) 2n
M
A( 2 )
数值分析 5
数值分析
1 0 0 1 0 0
L1 L2
l21
1
0 0
1
0
l31 0 1 0 l32 1
1 0 0
l21
1
0
l31 l32 1
L2 L1
数值分析 6
数值分析
Gauss变换阵的作用：
1. x ( x1 , x2 , ..., x j , x j1, ..., xn )T 0,且x j 0
1
L1
=
2
1
1
1
L1 A完成第一步消元, 得 :
1 2 3 A(2) L1 A 0 1 2
0 1 1
a (2) 22
1
0
m32
a (2) 32
/
a (2) 22
1 /(1)
1
1
L2
=
1
,L2
A(
2
)
L2 L1 A
1 1
完成第二步消元, 得
A(3) L2 A(2) L2 L1 A
令：L L11 L21
1 0 0 1
=
2
1
0 0
1 0 1 0
1 0 0
=
2
1
0
1 1 1
0 0 1 0 1 1
数值分析 13
数值分析
记 A A(1) a1M(11)
... O
an(11) ...
a1M(1n)
1(1)
,
(1) 2
,
...,
(1) n
a(1) nn
第一步：设a1(11) 0, 取mi1 aa（ （1i1111） ）, i 2, ..., n
1
l j1, j 1
M O
ln, j
1
证：L j Lj1 ( I l jeTj )( I l jeTj )
I
l jeTj
l jeTj
l
j
eTj
l
j
e
T j
I
Lj1 L j
数值分析 3
数值分析
2. L1 L 2 ...L n1
(I
l 1e1T
)( I
l 2e2T
)...( I
l
eT
0 0 1
a13
a23
a33
数值分析 9
数值分析
例：设 x (1, 3, 6,9)T ,求一Gauss变换阵L2使 L2 x (1, 3, 0, 0)T .
1 0 0 0
解：L2
0 0
1 2
0 0 1 0
0 3 0 1
1 0 0 0 1 1
L2
x
0 0
1 2
0
0
3
3
1 0 6 0