数值分析第2章_解线性方程组的直接法

1、数值分析数值分析1第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分第第3 3章章 解线性方程组的直接法解线性方程组的直接法&3.1 Gauss消去法消去法&3.2 LU分解分解&3.3 三对角方程组的追赶法三对角方程组的追赶法Direct Methods for Solving Linear Systems求解求解bxA 数值分析数值分析2第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分其中其中 本章讨论本章讨论n元线性方程组元线性方程组 nnnnnnnnnnbxaxaxabxaxa

2、xabxaxaxa.22112222212111212111的解法。的解法。 Ax=b111212122212.,.nnnnnnaaaaaaAaaa 12,nxxxx 12nbbbb 方程组的矩阵形式为方程组的矩阵形式为 数值分析数值分析3第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分求解求解,n nA xb AR 0det( )A 克莱姆克莱姆（Cramer法则）法则）: :1 2, ,iiDxinD所需乘除法的运算量大约为所需乘除法的运算量大约为(n+1)!+nn=20时，每秒时，每秒1亿亿次运算速度的计算机要算次运算速度的计算机要算30多万年

3、！多万年！其中，其中，D=det(A), Di 是用向量是用向量b 代替代替A的第的第i 列后所得矩阵的列后所得矩阵的行列式。行列式。数值分析数值分析4第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分 所谓直接解法是指若不考虑计算过程中的舍入误差，所谓直接解法是指若不考虑计算过程中的舍入误差，经过经过有限次算术运算有限次算术运算就能求出线性方程组的精确解的方法。就能求出线性方程组的精确解的方法。线性方程组线性方程组Ax=b的一般数值解法的一般数值解法1.直接法：直接法：适用于低阶稠密方程组适用于低阶稠密方程组Gauss消去法消去法、三角三角分解法分解

4、法2.迭代法：迭代法：通过构造迭代方程组进行迭代。通过构造迭代方程组进行迭代。适用于大型稀疏方程组适用于大型稀疏方程组非零元素较多，非零元素较多，零元素较少零元素较少上万阶，零元素很多，上万阶，零元素很多，非零元素很少非零元素很少 雅克比迭代法雅克比迭代法 赛德尔迭代法赛德尔迭代法数值分析数值分析5第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分3.1 Gauss消去法消去法3.1.1 高斯消去法高斯消去法 高斯消元法是一个古老的直接法高斯消元法是一个古老的直接法, 由它改进得到的选主由它改进得到的选主元法元法, 是目前计算机上常用于求低阶稠密矩阵方

5、程组的有效是目前计算机上常用于求低阶稠密矩阵方程组的有效方法方法, 其特点就是通过消元将其特点就是通过消元将一般线性方程组一般线性方程组的求解问题转的求解问题转化为化为三角方程组三角方程组的求解问题。的求解问题。 /* Gaussian Elimination */ 顺顺序序高高斯斯消消去去法法选选主主元元高高斯斯消消去去法法数值分析数值分析6第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分1.1.消元过程：消元过程：用初等行变换将原方程组的系数矩阵化为用初等行变换将原方程组的系数矩阵化为 上三角形矩阵（简称上三角阵）。上三角形矩阵（简称上三角阵）。

6、2.2.回代过程：回代过程：对上三角形方程组的最后一个方程求解，对上三角形方程组的最后一个方程求解，将求得的解逐步往上一个方程代入求解。将求得的解逐步往上一个方程代入求解。 思思路路首先将首先将A化为上三角阵化为上三角阵/* upper-triangular matrix，再回代求解再回代求解。=1. Gauss（顺序）消去法的基本思想（顺序）消去法的基本思想不作行交换！不作行交换！ 数值分析数值分析7第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分 例例3-1 用消去法解方程组用消去法解方程组 1231231232241239222333 ( )

7、( )( )xxxxxxxxx 第第2步步. 回代过程回代过程 解解121231( ) ( ) ()( ) ( ) 第第1步步. 消元过程，对增广矩阵进行消元消元过程，对增广矩阵进行消元 得等价的三角形方程组得等价的三角形方程组 1232332241527222121355( ) ()()xxxxxx 解为解为 2 2 1( , ) .Tx 212412392233 2124502720157 5322( ) ( ) 21245027221210055 数值分析数值分析8第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分记记,)()1()1(nnija

8、AA 1( )bb Step 1：设设 ，计算因子，计算因子1110( )a )., 2(/)1(11)1(11niaamii 将增广矩阵将增广矩阵/* augmented matrix */第第 i 行行 mi1 第第1 1行行，得到得到)1(1)1(1)1(12)1(11.baaan)2(A) 2(b).,2,()1(11)1()2()1(11)1()2(njibmbbamaaiiijiijij 其中其中Step k：设设 ，计算因子，计算因子且计算且计算0( )kkka )., 1(/)()(nkiaamkkkkikik )., 1,()()()1()()()1(nkjibmbbamaa

9、kkikkikikkjikkijkij 共进行共进行 ？ 步步n 1 )()2(2)1(121)()2(2)2(22)1(1)1(12)1(11.nnnnnnnnbbbxxxaaaaaa2. 2. 计算步骤计算步骤消元消元数值分析数值分析9第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分回代回代)()(/nnnnnnabx ) 1., 1()(1)()( niaxabxiiinijjiijiii数值分析数值分析10第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分3. 3. 使用条件使用条件高斯消去法能按顺序

10、进行到底的充要条件是高斯消去法能按顺序进行到底的充要条件是 在原方程组的系数矩阵中如何反映出这个条件呢在原方程组的系数矩阵中如何反映出这个条件呢? ?( )0,1,2,kkkaknA的的k阶顺序主子矩阵阶顺序主子矩阵Ak的行列式的行列式 (1)1112111121(2)(2)21222(1)(2)( )2221122( )120det00kkkkkkkkkkkkkkkaaaaaaaaaaaAa aaaaaa，nk, 2 , 1 定理定理 若若A的所有的所有顺序主子式顺序主子式 /* determinant of leading principal submatrices */均不为均不为0，则

11、高斯消元无需换行即可，则高斯消元无需换行即可进行到底，得到唯一解。进行到底，得到唯一解。iiiiiaaaaA.)det(1111 使用条件之一使用条件之一 数值分析数值分析11第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分 n阶矩阵阶矩阵A为为严格对角占优矩阵严格对角占优矩阵是指其每个主对是指其每个主对角元的绝对值大于同一行其他元素绝对值之和，即角元的绝对值大于同一行其他元素绝对值之和，即11 2, ,niii jjjiaain 一阶严格对角占优矩阵指一个非零数。一阶严格对角占优矩阵指一个非零数。 定理定理 方程组系数矩阵方程组系数矩阵A为严格对角

12、占优矩阵则可实为严格对角占优矩阵则可实现用顺序高斯消去法求解。现用顺序高斯消去法求解。使用条件之二使用条件之二 数值分析数值分析12第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分由于计算机中乘除由于计算机中乘除 运算的时间远远超过加减运算的时间，运算的时间远远超过加减运算的时间，故估计某种算法的运算量时，往往只估计故估计某种算法的运算量时，往往只估计乘除的次数乘除的次数，而且，而且通常以乘除次数通常以乘除次数的的最高次幂最高次幂为运算量的为运算量的数量级数量级。 高斯消去法高斯消去法:Step k：设设 ，计算因子，计算因子且计算且计算0)( kk

13、ka)., 1(/)()(nkiaamkkkkikik )., 1,()()()1()()()1(nkjibmbbamaakkikkikikkjikkijkij 共进行共进行n 1步步 )()2(2)1(121)()2(2)2(22)1(1)1(12)1(11.nnnnnnnnbbbxxxaaaaaa)()(/nnnnnnabx ) 1., 1()(1)()( niaxabxiiinijjiijiii(n k) 次次(n k)2 次次(n k) 次次(n k) (n k + 2) 次次nnnknknnk6523)2)(2311 消元乘除次数：消元乘除次数：1 次次(n i +1) 次次22)1

14、(1211nninni 回代乘除次数：回代乘除次数：高斯消去法的总乘除次数为高斯消去法的总乘除次数为 ，运算量为，运算量为 级。级。nnn31323 33n4. 4. 计算量计算量数值分析数值分析13第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分Gauss消去法算法消去法算法kkikikikaama/ nkj,1 .*kjikijijamaa kikiibmbb* 消元计算消元计算 nki,1 for 1,2,1 nkfor for 回代求解回代求解 nnnnabb/ 1 ,2,1 ni *iiijjbbab for /iiiibba1,jin f

15、or 数值分析数值分析14第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分3.1.2 高斯列主元消去法高斯列主元消去法 为避免这种情况的发生为避免这种情况的发生, 可通过交换方程的次可通过交换方程的次序，选取绝对值大的元素作主元序，选取绝对值大的元素作主元. 基于这种思想导基于这种思想导出了主元素法出了主元素法在在高斯消去法消去过程中可能出现高斯消去法消去过程中可能出现 的情况，的情况，这时高斯消去法将无法进行；即使主因素这时高斯消去法将无法进行；即使主因素 但但很小很小，其作除数，其作除数 ，也会导致其它元素数量级的，也会导致其它元素数量级的严重增

16、长和舍入误差的扩散严重增长和舍入误差的扩散.( )0kkka( )0kkka/* Pivoting Strategies */数值分析数值分析15第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分例例 单精度解方程组单精度解方程组 211021219xxxx/* 精确解为精确解为 和和 */.1000.00. 1101191 x8个个.8999.99. 0212 xx8个个用高斯消元法计算：用高斯消元法计算：911212110/ aam999212210101010.0 . 011 ma8个个92121012 mb 9991010011100, 112

17、 xx小主元小主元 可能导致计算可能导致计算失败。失败。数值分析数值分析16第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分 完完全主元消去法全主元消去法/* Complete Pivoting */每一步选绝对值最大的元素为主元素，保证每一步选绝对值最大的元素为主元素，保证1| ikmStep k: 选取选取;0|max|, ijnjikjiaakk If ik k then 交换第交换第 k 行与第行与第 ik 行行; If jk k then 交换第交换第 k 列与第列与第 jk 列列; 消元消元列交换改变了列交换改变了 xi 的顺序，须记录的

18、顺序，须记录交换次序交换次序，解完后，解完后再换回来。再换回来。选主元时要花费较多机器时间选主元时要花费较多机器时间数值分析数值分析17第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分 列主元消去法列主元消去法/* Partial Pivoting */省去换列的步骤，每次仅选一列中最大的元。省去换列的步骤，每次仅选一列中最大的元。0|max|, iknikkiaak例：例： 211111091,112 xx 110211 11102119 列主元法没有全主元法稳定。列主元法没有全主元法稳定。0,112 xx例：例： 2111010199 99991

19、010010101注意：这两个方程组注意：这两个方程组在数学上在数学上严格等价严格等价。 数值分析数值分析18第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分定理定理 系数矩阵为对称严格对角占优，则系数矩阵为对称严格对角占优，则 全是主元。全是主元。( ),1,2,kkkakn (1)(2)( )1122det( 1)mnnnAa aa 列主元法的消元列主元法的消元过程过程 计算过程有计算过程有2次行交换，故次行交换，故m=2，主元为主元为5，-1.6，2 det A=(-1)25(-1.6)2=16 m为消元过程中交换行的次数。为消元过程中交换行的

20、次数。3 5 4 5 7 34 4 2A573201.60.40.40022列主元消去法常用来求行列式列主元消去法常用来求行列式数值分析数值分析19第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分3.2 LU分解分解定义定义3-1 若若n阶矩阵阶矩阵A可分解为一个可分解为一个下三角矩阵下三角矩阵 L 和一个和一个上三角上三角矩阵矩阵U 的乘积，即的乘积，即A=LU则称这种分解为方阵则称这种分解为方阵A的一种的一种 LU 分解分解，通常也称为方阵，通常也称为方阵A的的三三角分解法角分解法。1o 若若L为单位下三角矩阵，则称为为单位下三角矩阵，则称为A的

21、的Doolittle分解；分解；2o 若若U为单位上三角矩阵，则称为为单位上三角矩阵，则称为A的的Crout分解。分解。MMAUU 单单位位下下三三角角阵阵高高斯斯消消元元法法上上三三角角阵阵1LM 记记), 2 , 1(0)(nkakkkA的顺序主子式不为零什么条件下存在什么条件下存在LU分解？分解？数值分析数值分析20第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分201 ,(, , ),.kDLULUAnAknA 顺顺序序主主子子式式单单位位下下三三角角矩矩阵阵矩矩阵阵的的分分解解设设 为为 阶阶矩矩阵阵 如如果果 的的则则 可可分分解解为为一

22、一个个和和上上三三角角矩矩一一个个单单位位的的乘乘积积，且且这这种种分分解解是是唯唯一一阵阵的的定定理理3 32 2) )- - ( (例例 设设 讨论讨论a 取何值时，矩阵取何值时，矩阵A可作可作LU 分解分解。 12 21aA解解 当当A的顺序主子式不为零，矩阵的顺序主子式不为零，矩阵A有有LU 分解分解。 所以，有所以，有10a (1)2 20a 1a 3a 数值分析数值分析21第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分 非奇异矩阵不一定存在非奇异矩阵不一定存在LU分解。分解。0110A解解 A是是非奇异矩阵，假设有非奇异矩阵，假设有LU

23、分解分解01101010bdac 比较等式两端第比较等式两端第1列，可得列，可得 上二式不能同时成立，即非奇异矩阵上二式不能同时成立，即非奇异矩阵A不存在不存在LU分解。分解。0,b 1ab 例例 数值分析数值分析22第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分3.2.1 Doolittle（杜利特尔）分解（杜利特尔）分解 Doolittle Factorization直接直接LU分解法分解法通过比较法直接导出通过比较法直接导出L 和和 U 的计算公式。的计算公式。思思路路 nnnnnnnnuuullaaaa.1.11.1111211111 ),

24、min(1jikjkkiul jia L、U 的元素的确定的元素的确定111 2(, , ),iiuain ), 2(/,11111111niualulaiiii 得得U 的第的第1行元素行元素得得L 的第的第1列元素列元素数值分析数值分析23第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分 ),min(1jikjkkijiula固定固定 i : :对对 j = i, i+1, , n 有有ijkjikikijuula 11lii = 1kjikikijijulau 11将将 i ，j 对换，对对换，对 j = i, i+1, , n 有有iijik

25、iikjkjiulula 11iiikkijkjijiuulal/ )(11 2, 3, , kn对对计计算算数值分析数值分析24第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分111213212223313233 2 2 31 4 7 7 1 25uuuALlUuullu， 4 1 例例1112132131222221 12232321 13323231 1222333331 1332233421 ,2,2,3,2,1222,72 23,72 3111()(4( 1)2)233,5( 1)32 16nruuullrual uual ulal uur

26、ual ul u Doolittle Factorization数值分析数值分析25第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分LU分解求解线性方程组分解求解线性方程组 , AXbLUXbLYbUXY 112122313211(1)111211122222111 1nnn nnnnnnnnnyblybllLYblllybuuuxyuuxyUXYuxy三三角角方方程程组组数值分析数值分析26第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分11-11 , 2, 3, , (1) iiijijjinYybyy

27、bl解解 ： 1 , 1, , 1 2 nnnnniijjiiij iinyXxuyxu xu（ ）解解 ：对方程组求解对方程组求解, ,只要得到了系数矩阵的三角分解形只要得到了系数矩阵的三角分解形式式, ,再利用再利用前代前代算法和算法和回代回代算法解两个三角方程组算法解两个三角方程组即得即得. .P计算量计算量乘除法大约乘除法大约n33 3次，和高斯消去法计算量基本相同次，和高斯消去法计算量基本相同. . 每解一个方程组每解一个方程组Ax=b，仅需要仅需要增加增加n2次乘除法运算次乘除法运算. . 数值分析数值分析27第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月1

28、4日日7时时22分分例例 用用LU分解法求解方程组分解法求解方程组123123123223347712457xxxxxxxxx 解解 先对系数矩阵进行先对系数矩阵进行LU分解分解 A=LU 100223210031121006LU，求解两个三角形方程组，求解两个三角形方程组， , bLy yUx 得得11212332127yyyyyy 12323322333566xxxxxx 123356yyy 321122xxx 数值分析数值分析28第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分 例例 用三角分解法解用三角分解法解 .20181451325232

29、1321xxx解解,11111 au,21/2/112121 ual,122512212222ulau,21212 au,31313 au31/3/113131ual,432213212323ulau,51/)231(/)(2212313232uulal.24)4()5(335233213313333ululau2400410321153012001A.LU从而从而求解求解 ,)20,18,14(TyL,)72,10,14(TxU,)72,10,14(Ty得得求解求解.)3,2, 1(Tx 得得数值分析数值分析29第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7

30、时时22分分例例 用三角分解法用三角分解法 求解下列方程组求解下列方程组123412312341346262414535xxxxxxxxxxxxxx 解解 系数矩阵系数矩阵6211241011411 013A 131616 6211 1032313151103710910 937 19174111311165911161037L 62111021333379101019174U 6323519174y 1111x 数值分析数值分析30第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分选主元的三角分解法选主元的三角分解法 直接三角分解当直接三角分解当 时

31、计算将中断，时计算将中断，0rru当当 绝对值很小时，计算可能引起舍入误差的累积绝对值很小时，计算可能引起舍入误差的累积. . rru如果如果 非奇异，可通过交换非奇异，可通过交换 的行实现矩阵的行实现矩阵 的的 分解分解. .AAPALU直接三角分解法直接三角分解法( )0(1,2, )kkkakn不满足不满足列主元所在行与第列主元所在行与第k行交换行交换乘以初等交换阵乘以初等交换阵数值分析数值分析31第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分3.2.2 Crout（）分解）分解,LUA 111211112121222212221212111

32、.nnnnnnnnnnnnaaaluuaaalluAaaalll 假设假设其中其中L为下三角矩阵，为下三角矩阵， U为单位上三角矩阵，为单位上三角矩阵，Crout Factorization数值分析数值分析32第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分3.2.3 Cholesky（楚列斯基楚列斯基）分解）分解平方根法平方根法定义定义3-2 若矩阵若矩阵 ,nnAR 满满 足足2( ) A的的各各阶阶顺顺序序主主子子式式都都为为正正 (1) , TAA 则称则称A为对称正定矩阵。为对称正定矩阵。例例 判判断断矩矩阵阵410141014A 的的正正

33、定定性性。 解解 TAA， A为为对对称称矩矩阵阵， 即即A为为对对称称正正定定矩矩阵阵。 140A ，24 411150()()A ，3560A 数值分析数值分析33第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分A为为对称正定阵，则存在唯一的对称正定阵，则存在唯一的LU分解分解U =uij=u11uij / uii111u22unn记为记为UD A 对称对称TUL 即即TLDLA 记记 D1/2 =11u22unnu2/1LDL 则则 仍是下三角阵仍是下三角阵TLLA nnRL 定理定理 设矩阵设矩阵A对称正定，则存在非奇异下三角阵对称正定，则存

34、在非奇异下三角阵 使得使得 。若限定。若限定L对角元为正，则分解唯一。对角元为正，则分解唯一。TLLA 11211112322222111nnuuuuuuuu数值分析数值分析34第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分3353595917A例：例：对矩阵对矩阵 进行楚列斯基分解。进行楚列斯基分解。解：解： A为对称矩阵，且为对称矩阵，且12330,6040AAA ， A对称正定。对称正定。1i 11113la 131221311111352,3,33aajljlll 1112111112112122221222221212nnnnnnnnnn

35、nnnnaaallllaaallllaaallll数值分析数值分析35第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分332522 233L2222333331325217()(2 2)33lall3,i 2i ，2222221532lal 3j ，323231 2122151()(93)2 232lal ll 3353595917A1111211212222212nnnnnnnnllllllllllll数值分析数值分析36第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分矩阵矩阵LLT分解的实际计算公式：分

36、解的实际计算公式：1 2kn , ,for12,jkkn for12,ikkn forikikkkaaa mjmjmkjkaaaa 1mj jn ,forkkkkaa 数值分析数值分析37第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分解解61410242212231212312112312 064171024424321321321xxxxxxxxx 例例 解线性方程组解线性方程组 113212112312A1232413172110,yyy 解解123251yyy 得得123212231511xxx 再再解解，123121xxx 得得212 21

37、23 21231 数值分析数值分析38第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分 Cholesky分解法求解方程组中需说明的几个问题分解法求解方程组中需说明的几个问题工作量：约为工作量：约为LU分解的分解的一半一半； 不必选主元：不必选主元：A的的正定性正定性和算法的和算法的稳定性稳定性稳定性：是数值稳定的；稳定性：是数值稳定的；()ikiilaik缺陷：存在缺陷：存在开平方开平方运算。运算。改进方法：改进方法： LDLT 分解分解改进的平方根法改进的平方根法数值分析数值分析39第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5

38、月月14日日7时时22分分 改进的平方根法改进的平方根法 避免开方运算避免开方运算TAL D L 即即 1212122112111111.nnnnnldldllAdll .1112121221122111 nnnnnllldldlddlddA nkkjTikijLLDa1)()( nkjkkikldl1 11.jkjjjijjkkikldlldl数值分析数值分析40第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分 l.l. );1,2, 1(/11ijdldlaljjkjkkikijijni,2,1 对于对于 2.2. .112ikkikiiidla

39、d引进引进 ,jijijdlt按行计算按行计算 元素的公式：元素的公式： TL ,111ad 1.1. );1,2, 1(11ijltatjkjkikijij 2.2. );1,2, 1(/ijdtljijij 3.3. 11ikikikiiiltadni,3,2 对于对于 ,TTLA nkkjTikijLLDa1)()( nkjkkikldl1 11.jkjjjijjkkikldlldl数值分析数值分析41第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分3nt2nt1nt32t31t21t1dStep12dStep23dStep321l31l1nl

40、32l2nl3nlndStepn 333231222111aaaaaaA对对称称 332312211dlldld 33323122211aaaatd 3332312211attdld 3332312211aaadld元素的储存比消去法节省一半，但比平方根法多用一个单元内存，元素的储存比消去法节省一半，但比平方根法多用一个单元内存， LDLT的计算顺序的计算顺序数值分析数值分析42第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分 LDLT分解公式：分解公式：Axb TLDL xb TLybDL xy 求解方程组求解方程组等价方程组等价方程组1TLybL

41、 xD y 11112 3, ,iiainaa for1 21ji , ,for11imimkkkmiiiaavaa ()jijjjva a 11iiiiiikkkaaa v 12miin ,for数值分析数值分析43第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分; 1, 1111 adi, 1, 22121 ati; 2, 1/212122212121 ltaddtl, 1, 1, 3213132323131 ltatati; 3, 5 . 0/, 1/323231313332323213131 ltltaddtldtl 15 . 01111L

42、321D 128415 . 01111321yyy 644321yyy 64415 . 01111321321xxx 211321xxx12311141328 .12 4.512xxx 例例 用用LDLT解方程组解方程组解解数值分析数值分析44第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分12311141328 .12 4.512xxx 例例 用用LDLT解方程组解方程组解解 5 . 421231111 1 211 3211211 15 . 01111L 321D 128415 . 01111321yyy 644321yyy 64415 . 011

43、11321321xxx 211321xxx数值分析数值分析45第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分3.3 三对角方程组的追赶法三对角方程组的追赶法系数矩阵为对角占优的三对角线方程组系数矩阵为对角占优的三对角线方程组,12112111122211 nnnnnnnnnffffxxxxbacbacbacb简记为简记为 .A xf 其中，当其中，当 且：，,01时ijaji 0; 1 cba1)();1,3 ,2(0,)( nicacabbiiiii, 0. nnabc)(LU分解会是什么样子？分解会是什么样子？数值分析数值分析46第第3章章 解

44、线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分,LUA 其中其中L为下三角矩阵，为下三角矩阵，U为单位上三角矩阵为单位上三角矩阵. . 由系数阵由系数阵A的特点，可以将的特点，可以将A分解为两个三角阵的乘积，分解为两个三角阵的乘积，即即 设设 nnnnnbacbacbacbA11122211,11111221 nnn 其中其中 为待定系数为待定系数. . iii,由矩阵乘法由矩阵乘法,11111 cb )1,2(niciii ),2(,1nibaiiiiii 或分解为：或分解为：L为单位下三角矩阵，为单位下三角矩阵，U为上三角矩阵为上三角矩阵. . 数值分析数值

45、分析47第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分计算公式计算公式1111111, bcc b1iiiiba 1 iiiiiiiccba 1nnnnba i = 2, 3, , n-1求解求解 等价于求解两个三角形方程组：等价于求解两个三角形方程组： ,fAx ;,)1(yfLy求.,)2(xyUx求数值分析数值分析48第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分三对角线方程组的三对角线方程组的追赶法公式追赶法公式： 1. 1. 计算计算 的递推公式的递推公式 i111/bc);1,3,2()/(

46、1niabciiiii 2. 2. 解解 fLy ,/111bfy );,3,2()/()(11niabyafyiiiiiii 3. 3. 解解 yUx ,nnyx).1 ,2,2,1(1nnixyxiiii121nnyyy21赶：赶：11xxxnn追：追：数值分析数值分析49第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分 解解2112112112A 12 3111232 111232232 111123223432 11112322334342 1111232233434542 1122 111123223433454211A11 所所以以123

47、411121121021020 xxxx 例例3-7 应用追赶法求解线性方程组应用追赶法求解线性方程组数值分析数值分析50第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分123411132435421000yyyy 解解方方程程，123412131415yyyy 得得1234112212331344151111xxxx 再再解解方方程程，123445352515xxxx 得得数值分析数值分析51第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分 解解 3123123123A 13 11331132 11311

48、631132 1113113911631132 11133922113911631132 3913939221139116311321113 1332 11111113A392211632391391139311所以所以 91511731231231234321xxxx例例11 解线性方程组解线性方程组数值分析数值分析52第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分小小 结结数值分析数值分析53第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分矩阵三角分解法矩阵三角分解法高斯消去过程实现了高斯消去过程实现

49、了A的一个三角因子分解的一个三角因子分解A=LU，其中其中L一个单位下三角阵，一个单位下三角阵， U为为上三角阵上三角阵. .此分解此分解称为称为A的的Doolittle分解分解.定理定理 若若A的所有顺序主子式的所有顺序主子式 均不为均不为0，则，则 A 的的 LU 分解唯一（其中分解唯一（其中 L 为为单位单位下三角阵）。下三角阵）。nnRL 定理定理 设矩阵设矩阵A对称正定，则存在非奇异下三角阵对称正定，则存在非奇异下三角阵 使得使得 。若限定。若限定 L 对角元为正，则分解对角元为正，则分解唯一。这种分解称为平方根分解或乔累斯基分解。唯一。这种分解称为平方根分解或乔累斯基分解。TLLA

50、 数值分析数值分析54第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分直直 接接 法法 的的MATLAB 用用 法法1. 求求解解bAx bAx ，输出方程的解x. 2. LU分分解解 使用列主元素消元法进行。u =chol(A)： 对 正 定 对 称 矩 阵 A 的 Cholesky 分解 ， 输 出 u 为 上 三 角 阵 U， 使 A=UTU x,y=lu(A)： 输出x为一交换阵与单位下三角阵 之积L，y 为上三角阵U，使LUA. . x,y,p=lu(A)：输出 x 为单位下三角阵 L，y 为 上三角阵 U，p 为一交换阵 P，使LUPA . . 数值分析数值分析55第第3章章 解线性方程组的直接法解线性方程组的直接法2022年年5月月14日日7时时22分分分析：分析：（1）若A可逆,则PA可分解为一个单位下三角阵L 和一 个上三角阵U 的积 PA=LU 这种分解是唯一的，称矩阵LU分解。 P由单位阵经若干 次行交换得到。 （2）解矩阵方程Ax=b, 则 PAx=Pb 即 LU x=Pb 例例(1) 将矩阵A进行LU分解, (2) 解矩阵方程Ax=b,4321,98754113211143214321bA其中bLPUx111)(LPbLx1111-1L ,U其中数值分析数值分析56第第3章章 解线性方程组的直接法解线性方