《计算方法第六章》由会员分享，可在线阅读，更多相关《计算方法第六章（58页珍藏版）》请在金锄头文库上搜索。
1、第六章 解线性代数方程组的直接法 6.1 高斯消去法 6.2 主元素消去法 6.3 LU分解 6.4 平方根法和LDLT分解 6.5 误差分析 计算方法 第六章 2 研究对象是 n 阶线性代数方程组 Axb bAx1 nnnnnnnnnnbbbbxxxxaaaaaaaaaA.,.,.2121212222111211 其中 A 为系数矩阵，x是未知量，b是右端项。 计算方法 第六章 3 线性方程组在科学和工程中十分常见，比如工程中广泛 应用的有限元法，其实质是解如下的方程组 KF K 是总刚度矩阵，为正定对称矩阵，是位移向量，F是载荷向量。当结构为线性时（材料为线性材料，变形 在线性变化范围内）
2、 ，该方程组为线性方程组。 现代工程有限元分析的规模可达一千万阶以上，因此线 性方程组的求解效率至关重要。大规模和稀疏性是有限 元求解的特点。 计算方法 第六章 4 若线性方程组的系数矩阵 A 非奇异，即 A 的行列式 det A 0，则方 程组有唯一解。 当系数矩阵 A 的阶数 n 不大时，可用 Cramer 法则（1750 年）求解 nixi i,.,2 , 1, i是把中第 i 列元素换成右端项而得到的行列式。 其乘法计算量是) 1()!1(nn，当 n 稍大时，计算量相当大。 例如，当 n = 20 时，Cramer 法则的乘除法运算总数超过 5 1019次， 而高斯消去法为 3060
3、 次。 矩阵求逆的追求 计算方法 第六章 5 高斯消去法矩阵求逆，需要n3个量级的计算量（如果矩阵有特殊的结构， 比如大部分元素是零或者满足快速傅立叶变化的矩阵，则可以更快数值 求逆）。对一般情形的可逆矩阵，这个n3个量级的计算量在1969年被 减少到n2.81 ; 1990年被减少到n2.376 。在过去的20年，这一结果仅仅 被减少到n2.373 。 问题：我们可不可以把一般情形的可逆矩阵求逆的工作量减少到n2+ 的量级，其中 是充分小的正数。 “If this problem is solved affirmatively, it would change the world.” 牛津大
4、学计算中心主任、英国皇家学会院士、美国工业与应用数学 会（SIAM）主席Nick Trfethen 教授 计算方法 第六章 6 求解线性方程组有直接法和迭代法两类方法： (1) 直接法：对方程进行变形，经过有限步运算后能求得方 程组的精确解， 如果不计原始数据误差及计算的舍入误 差。 (2) 迭代法：构造一个迭代公式，由此求出一个无限的向量 序列，使它的极限为所求方程组的解向量。迭代法存在 收敛性问题。 对于有限元方程，20 万自由度以下多用直接法，如 LDLT 分解（SAP84） 。20 万自由度以上可用迭代法，热门的如预 条件共轭梯度法(PCG)。 计算方法 第六章 7 6.1 高斯消去法
5、高斯消去法 即高斯-约当消去法，是解线性方程组的古典方法。 公元前 150 年的九章算术中就出现了高斯消去法的思想。 高斯（Gauss）大约在 1800 年提出了高斯消去法并用它解决 了天体计算和后来的地球表面测量计算中的最小二乘法问 题。 基本思想：用逐次消去一个未知数的方法，把原来的线性方 程组化为一个与其等价的系数矩阵为上三角阵的方程组。 高斯消去法的求解分消元和回代两个过程，也有无回代过程 的高斯消去法（系数矩阵化为单位阵） 计算方法 第六章 8 对于方程组 (1)(1)(1)(1) 11112211(1)(1)(1)(1) 21122222(1)(1)(1)(1) 1122.nnnn
6、nnnnnna xa xa xba xa xa xba xa xa xb 若(1) 110a，则对第二方程减去第一个方程乘以(1)(1) 2111/aa，第三个方程减去第一个方程乘以(1)(1) 3111/aa。 。 。得到(i)- (1)(1) 111/(1), i=2,3,.,niaa 计算方法 第六章 9 (1)(1)(1)(1)(1) 11112213311(2)(2)(2)(2) 22223322(2)(2)(2)(2) 32233333(2)(2)(2)(2) 2233.nnnnnnnnnnnna xa xa xa xbaxaxaxbaxaxaxbaxaxaxb 若(2) 220a
7、，则对第三个方程减去第二个方程乘以(2)(2) 3222/aa，第四个方程减去第二个方程乘以(2)(2) 4222/aa，可得 （i）-(2)(2) 222/(2),3,4,.,iaain 计算方法 第六章 10 (1)(1)(1)(1)(1) 11112213311(2)(2)(2)(2) 22223322(3)(3)(3) 33333(3)(3)(3) 33.nnnnnnnnnnna xa xa xa xbaxaxaxbaxaxbaxaxb 以此类推，上述步骤在经过 n-1 次后得到： (1)(1)(1)(1)(1) 11112213311(2)(2)(2)(2) 22223322(3)(
8、3)(3) 33333( )( ).nnnnnnnn nnnna xa xa xa xbaxaxaxbaxaxbaxb 计算方法 第六章 11 其系数矩阵( )nA为 ( )nA=(1)(1)(1)(1) 1112131(2)(2)(2) 22232(3)(3) 333( ).0.00.000.nnnn nnaaaaaaaaaa ， (1) 1(2) 2 ( )(3) 3( ).nn nbbbbb 把系数矩阵(1)A化为上三角阵( )nA的过程称为消元。 计算方法 第六章 12 (1)( )(1)( )(1)( )( )( )( )(1)( )( )( )( )(1),(/)1,1(/)01k
9、kkk ijijiikkkkk ijijikkkkjkkkkk iiikkkkk ijaabbik jnaaaaakin kjnbbaabajkin 基准行以上的行不动，基准行以下的上三角变形，基准行以下的其余元素为零 计算方法 第六章 13 回代 若( )0n nna ( )( )( )( )( )1/()/1,2,.,1nn nnnnn iii iiijjii j ixbaxba xainn 所以高斯消去法分消元和回代两个过程。 高斯消去法运算量：3211 33nnn次乘除法运算 计算方法 第六章 14 高斯消去法的矩阵解释： ( )(1) 1221( )(1) 1221.n nnn nn
10、AMMMMAbMMMMb因此高斯消去法的消元过程实质上是用一系列初等变换矩阵左乘原方程组的 系数矩阵和右端项，而将系数矩阵三角化。 其中初等变换矩阵iM是第 i 列对角线以下元素为非零的单位下三角矩阵。 i+1,i,1 01 :. 0.1 0.-1. 0.-0. 1in iM mm 计算方法 第六章 15 ( )( )(1)1111( ) 1221/(1,2,., )ii jiijiin nnmaajiinAMMMMA 令上三角矩阵 U: ( )1111 1221nnnUALMMMM 则(1)ALU L 为单位下三角矩阵 计算方法 第六章 16 6.2 主元素消去法主元素消去法 高斯消去法的前
11、提条件是系数矩阵中0)(k kka，如果对角线元素0)(k kka或很小， 会导致其它元素量级的巨大增长和舍入误差的扩散，导致计算结果不可靠。 例 6.1 12120.00011 2xx xx ，用三位尾数的浮点数求解 把 x1消去，得1220.000111000010000xxx 解得211,0xx 该方程组的准确解是12100009998,99999999xx 计算方法 第六章 17 若将两个方程交换，变为121220.00011xxxx 消去第二个方程的1x得12221xxx 从而得121xx 主元素消去法分全主元素消去法和列主元素消去法两种。 全主元素消去法： 在系数矩阵中选取绝对值最
12、大的数作为 对角线元素。 计算方法 第六章 18 例 6.2 全主元消去法 列主元消去法 123123123123315183156xxxxxxxxx 123123123123315183156xxxxxxxxx 取系数矩阵的最大值做(1) 11a 取第 1 列的最大值作(1) 11a 123123123183151233156xxxxxxxxx 123123123183151233156xxxxxxxxx 计算方法 第六章 19 消去1x得 1232323183152.3335.0001.1670.9445.167xxxxxxx 1232323183152.3335.0001.1670.94
13、45.167xxxxxxx 在后面的两个方程中，再选绝对值最大的作为(2) 22a 得1323232183152.3335.0000.9441.1675.167xxxxxxx 000. 5333. 2167. 5944. 0167. 1153183232231xxxxxxx计算方法 第六章 20 消去3x得 消去 x2得 13232218315 2.3335.000 1.5723.144xxx xx x 12323318315 1.1670.9445.167 3.14199.4276xxx xx x 进行回代得 2312.000,3.000,1.000xxx 准确解为1231,2,3xxx 计算方法 第六章 21 全主元素消去得到的三角形方程可表示为( )( )nnA Yb ( )(1) 11222211121n nnnnnAMPMPMP MP AQ QQ ( )(1) 11222211n nnnnbMPMPMP MP b 121nXQ QQY 交换两行的位置，相当于系数矩阵和右端项左乘矩阵kP 交换两列的位置，相当于系数矩阵和右端项右乘矩阵kQ 计算方法 第六章 22 列主元素消去法只按列找最大值，未知数的次序并不改变 ( )( )nnAXb ( )(1) 11222211( )(1) 11222211n nnnnn nnnnAMPMPMP MP AbMPMPM
