数值分析第五章直接法

1、第五章 解线性方的直接方法§1引言线性方数值解法一般有两类：直接法：经过有限步算术运算，可求得精确解的方法 (不计舍入误差!)。方但由于舍入误差的和影响，只能求得方近似解。1/72直接方法数值分析迭代法就是通过极限过程去逐步逼近线性方精确解的方法。迭代法具有需要计算机的单元较少、程序设计简单、原始系数矩阵不变等优点，但收敛性及收敛速度问题。迭代法是解大型稀疏矩阵方的重要方法。2/72直接方法数值分析迭代法就是通过极限过程去逐步逼近线性方精确解的方法。迭代法具有需要计算机的单元较少、程序设计简单、原始系数矩阵不变等优点，但收敛性及收敛速度问题。迭代法是解大型稀疏矩阵方的重要方法。本章：

2、消去法及其变形。这类方法适合低阶稠密矩阵方及某些大型稀疏矩阵方。2/72直接方法数值分析n 阶线性方：aax + a12x2 + · · · + a1nxn= b1= b2111x + a22x2 + · · · + a2nxn211· · ·an1x1+ an2x2 + · · · + annxn = bn矩阵形式记为 Ax = b，这里A = aijn×n, x = (x1, · · · , xn)T ，b = (b1, ·

3、; · · , bn)T 。3/72直接方法数值分析§2本节消去法消去法及消去法和矩阵三角分解之间的关系。古老的求解线性方消去法是一个的方法，但由于它的改进、变形得到的选主元素消去法、三角分解法仍然是目前计算机上常用的有效方法。4/72直接方法数值分析一、消去法例：用消去法解线性方x + x2 + x3 = 614x2 x3 = 5 2x1 2x2 + x3= 15/72直接方法数值分析一、消去法例：用消去法解线性方x + x2 + x3 = 614x2 x3 = 52x 2x2 + x3 = 11解：消元x + x2 + x3= 614x2 x3 = 5 4x2

4、 x3 = 115/72直接方法数值分析x + x2 + x3 = 614x2 x3 = 52x = 63解为 x = (1, 2, 3)T 。用矩阵形式：6/72直接方法数值分析10142111111651(A|b) =26r32×r1r30044115117/72直接方法数值分析100140112656r3(1)r2r3x = (1, 2, 3)T消去法的基本思想是用逐次消去未知数的方法把原线性方等价的三角形线性方Ax = b 化为与其，而求解三角形线性方可用回代的方法求解。8/72直接方法数值分析矩阵角度：行变换将系数矩阵变为上三角矩阵。消去法Ax = b 记为 A(1)x =

5、 b(1)。.若 a(1)= 0：11(1)(1)11第二行 第一行第三行 第一行= 新第二行= 新第三行×a/a21(1)(1)×a/a31119/72直接方法数值分析· · · · · ·第 n 行 第一行 ×a/a= 新第 n 行(1)(1)n111相当于第 i 个方程 第一个方程 × 数 新的第 i 方程同解！第一方程不动！10/72直接方法数值分析· · · · · ·第 n 行 第一行 ×a/a= 新第 n 行(1

6、)(1)n111相当于第 i 个方程 第一个方程 × 数 新的第 i 方程同解！第一方程不动！上述消元过程除第一个方程不变以外，第 2 至第 n 个方程全消去了变量 x1，而系数和常数项全得到新值：10/72直接方法数值分析(1)(1)(1)(1)= b(1)ax + ax + ax + · · · + ax123n1112131n1(2)(2)(2)= b(2)ax + ax + · · · + ax23n22232n2(2)(2)(2)= b(2)+ · · · + axax + ax23n

7、32333n3· · · · · ·(2)+ a(2)x(2)= b(2)ax+ · · · + axnnn23nn2n3：A(2)x = b(2)。得到新同解方11/72直接方法数值分析这里 a(2) = a(1)(1)= a(1)/a(1) l a, li1i111ijij1ji1b(2)= b(1)(1) l b, i, j = 2, 3, · · ·, ni1ii112/72直接方法数值分析第二步消元：若 a(2) = 0 ，对除第一行第22一列外的子阵作计算：(1)

8、11a(1)a(1)a(1)(1)· · ·· · ·· · ·ab12131n1a(2)a(2)a(2)(2)00b220232n2a(3)a(3)(3)A(3)，(3)=b=b3n . 3.33.a(3)a(3)(3)00· · ·bnnnn313/72直接方法数值分析a(3) = a(2)(2)= a(2)/a(2) l a, li2i2ijij2ji222b(3) = b(2)(2) l b, i, j = 3, 4, · · · , n

9、i2ii2得到同解方A(3)x = b(3)(1)(1)(1)(1)= b(1)+ · · · + axax + ax + ax123n1112131n1(2)(2)(2)= b(2)ax + ax + · · · + ax23n22232n2(3)(3)= b(3)ax + · · · + ax3n333n3.(3)(3)= b(3)+ · · · + axax3nnnnn314/72直接方法数值分析若 a(3)= 0，则此消去过程可依次进行下33去。第 n 1 步消去过程

10、后，得到等价三角方。A(n)x = b(n)(1)(1)(1)(1)= b(1)+ · · · + axax + ax + ax123n1112131n1(2)(2)(2)= b(2)ax + ax + · · · + ax23n22232n2(3)(3)= b(3)ax + · · · + ax3n333n3.(n)= b(n)axnnnn15/72直接方法数值分析计算出 A(n), b(n)的过程称消去过程。16/72直接方法数值分析计算出 A(n), b(n)消去过程算法的过程称消去过程。a(k)=

11、 0ika(k+1) = a(k)(k)(k)(k) a(a/a)ijijkjikkkb(k+1) = b(k)(k)(k)(k) b(a/a)iikikkkk + 1 i, j n, k = 1, 2, · · · , n 116/72直接方法数值分析回代过程算法(1)(1)1i(1)= b(1)ax + · · · + ax + · · · + ax1in111n1· · · · · ·(i)(i)= b(i)ax + · 

12、3; · + · · · + axiniiini· · · · · ·(n1)(n1)= b(n1)ax+ axn1nn1,n1n1,nn1(n)= b(n)axnnnn17/72直接方法数值分析= b(n)/a(n)xnnnn= (b(i)na(i)xj)/a(i)xiij=i+1ijiii = n 1, n 2, · · · , 118/72直接方法数值分析= b(n)/a(n)xnnnn= (b(i)na(i)xj)/a(i)xiij=i+1ijiii = n

13、 1, n 2, · · · , 1Gauss 消去法乘除法计算量消去第一列的 n 1 个系数要计算n(n 1) 个乘法；消去第二列的 n 2 个系数要计算(n 1)(n 2) 个乘法；18/72直接方法数值分析n k=1(k2 k) =n (n2 1)总计除法回3n1n(n1)k =k=12n(n+1) 2+ n2 计算量n331n，（n = 30 时，总乘除法共为 9890）3消去法对某些矩阵可能会失败。19/72直接方法数值分析例：A = 01 1 0 (k)约化主元素 a(k = 1, 2, · · ·, n)kk20/72直

14、接方法数值分析例：A = 01 1 0 (k)约化主元素 a(k = 1, 2, · · · , n)kk定理：约化主元素 a(i) =0(i = 1, 2, · · · , k)ii的充要条件是矩阵 A 的顺序主子式Di =0(i = 1, 2, · · · , k)。20/72直接方法数值分析二、Gauss 消去法的矩阵表示每一步消去过程相当于初等变换矩阵 Lk。记：A(2)其中= L1A(1)，b(2)= L1b(1)，1l2110· · ·0L1 =l1·

15、· ·0· · ·131ln121/72直接方法数值分析= a(1)/a(1),li1i111i = 2, 3, · · · , n.记：A(3) = L2A(2), b(3)= L2b(2)。22/72直接方法数值分析 101l32· · ·L2=01· · ·0 0ln2· · ·1(2)(2)li2= a/a, i = 3, 4, · · · , n.i222A(3) = L2L1A(1),

16、 b(3)= L2L1b(1)23/72直接方法数值分析Li 与 Li1：10.1. . .=.Li1li+1,i01. . .0.lni124/72直接方法数值分析10.1. . .=.Li11li+1,i.lni01. . .0125/72直接方法数值分析A(n)= Ln1Ln2 · · · L1A(1)b(n)= Ln1Ln2 · · · L1b(1)26/72直接方法数值分析A(n)= Ln1Ln2 · · · L1A(1)b(n)A(1)= Ln1Ln2 · · ·

17、 L1b(1)111(n)= LL· · · LA12n1A(1) = LA(n)111L = LL· · · L12n126/72直接方法数值分析 111 =l10001l32l1l32 2121l3111l31127/72直接方法数值分析 111 =l1001l32l1l32 12121l310111l311l21.L =. . .· · ·ln1ln2127/72直接方法数值分析例：用消去法解线性方x + x2 + x3 = 614x2 x3 = 5 2x1 2x2 + x3= 128/72直接方法

18、数值分析由增广矩阵表示消元过程有1021421121116511001441116511|b) =(A1 1656004029/72直接方法数值分析(k)(k)由 lik= a/a, (i = k + 1, · · · , n)ikkk得 l= 0, l= 1，故有= 2, l2131 3210201100110011 A = LU4012 30/72直接方法数值分析三、主元素消去法消元过程中可能出现 a(k) = 0 的在kk情况，这时消去法将无法进行；即使主元素 a(k)= 0 但很小，用其作除数，也会kk导致其他元素数量级的严重增长和舍入误差的扩散。31/7

19、2直接方法数值分析为避免此种情况的发生，可通过交换方程的次序，选取绝对值大的元素作主元主元素法。32/72直接方法数值分析为避免此种情况的发生，可通过交换方程的次序，选取绝对值大的元素作主元主元素法。= a(k)/a(k)时避免 lik 过大，只要取likikkk= maxa(k)(k)i, j = k, k + 1, · · · , n，a,ijkk称为主元素 Gauss 消去法；= max或 a(k)(k)i = k, k + 1, · · · , n，a,kkik称为列主元 Gauss 消去法。32/72直接方法数值分析选主元素

20、的矩阵表示 1000. .0.1.1· · ·0· · ·· · ·1· · ·· · ·· · ·· · ·0k. .Ik,ik=.1.01· · ·0· · ·· · ·· · ·· · ·· · ·1&#

21、183; · ·. . .· · ·0ik.0.00· · ·· · ·· · ·· · ·133/72直接方法数值分析A(n)X= b(n)A(n)A(1)· · · L1I1,i= Ln1In1,iLn2In2,in1n21b(n)b(1)= Ln1In1,iLn2In2,i· · · L1I1,in1n2134/72直接方法数值分析例： 三阶方3.000 x1

22、1.000 0.0011.0002.0003.7121.072=4.6235.643x2.0003.000 22.000x3四位有效数字精确解为x = (0.4904, 0.05104, 0.3675)T35/72直接方法数值分析解：（1）消去法0.0011.0002.0003.7121.0723.000300560063.0004.6235.6431.000100220031.0002.000|b) =(A2.0003.0000.001 2.000002004400136/72直接方法数值分析0.001002.000200403.00030055.0001.00010022.000x = (

23、0.4000, 0.09980, 0.4000)T37/72直接方法数值分析（2）列主元素法：交换行，避免绝对值小的主元作除数。2.0001.0000.0011.0723.7122.0005.6434.6233.0003.0002.000|b) =(A1.0002.000001.0723.1762.0015.6431.8013.0033.0000.5001.00238/72直接方法数值分析2.000001.0723.17605.6431.8011.8683.0000.5000.687x = (0.4900, 0.05113, 0.3678)T39/72直接方法数值分析2.000001.0723

24、.17605.6431.8011.8683.0000.5000.687x = (0.4900, 0.05113, 0.3678)Tx = (0.4904, 0.05104, 0.3675)T （精）x = (0.4000, 0.09980, 0.4000)T39/72直接方法数值分析§3矩阵三角分解法消去法的变形一、直接三角分解法原方程 Ax = b，由于 A = LU ，求解Ax = b 等价于求解两个三角方Ly = b，Ux = y。：40/72直接方法数值分析1. 解 y： y1 = b1i1yi= bi lijyj,i = 2, 3, · · ·

25、 , nj=141/72直接方法数值分析1. 解 y： y1 = b1i1yi = bi lijyj, i = 2, 3, · · · , nj=12. 解 x：xn = yn/unnxi = (yi uijxj) /uiii+1 j=ni = n 1, · · · , 141/72直接方法数值分析例：用直接三角分解法解 13 x1 14 251=2325x1820 2x342/72直接方法数值分析例：用直接三角分解法解 13 x1 14 2=2 5 23 1 5x1820 2x3解：用分解计算公式得12301500110021034

26、24 = LUA = 42/72直接方法数值分析求解Ly = (14, 18, 20)T y = (14, 10, 72)TUx = (14, 10, 72)T x = (1, 2, 3)T43/72直接方法数值分析求解Ly = (14, 18, 20)T y = (14, 10, 72)TUx = (14, 10, 72)T x = (1, 2, 3)T 21 1322 1 12 1 1121252323232121252353235112243/72直接方法数值分析故 20 2132122112120135152013235 =11000 144/72直接方法数值分析故 20 213212

27、2112120135152013235 =11000 1另外一法： 21 101l32001uu12u220u13u23 u33111 =l00113 22 2 21l31顺序解出：u11, u12, u13, l21, l31, u22, u23,l32, u33。44/72直接方法数值分析0 21 112120135152013235211132 =00022 145/72直接方法数值分析0 21 1121201520132352113 =1 00022 3511 2列主元消去法 PA = LU ，其中 P换矩阵。所谓置换矩阵是置换的行所得到的矩阵。为置矩阵45/72直接方法数值分析下面说

28、明对矩阵 12 3A =1 2 22 1 1如何做这项工作。46/72直接方法数值分析下面说明对矩阵 12 3A =1 2 22 1 1如何做这项工作。12122523213232146/72直接方法数值分析第一、二个主元分别在第 3 行和第 1 行。121222121523511523323511323，作适当行变换255此时，可正常作 LU 分解。47/72直接方法数值分析对阵矩阵做相同的行变换，得置换矩 01 00111212P =100013500 2152013235 PA =000 148/72直接方法数值分析§4和矩阵的定义: 设对任意x Rn，按一定的规则有一实数与之

29、对应，记为x，若 x 满足1.x 0，且 x = 0 当且仅当 x = 0；(正定)2. x = | · x， 为任意实数；(齐次)49/72直接方法数值分析3. x + y x + y，对任意x, y Rn。(三角不等式)则称 x 为x 的。50/72直接方法数值分析3. x + y x + y，对任意x, y Rn。(三角不等式)则称 x 为x 的。由 (3) 可推出不等式4. |x y| x y，对任意x, y Rn。50/72直接方法数值分析例22nx2 =x + · · · + x1x = max|x1|, · · 

30、3; , |xn|x1 = |x1| + · · · + |xn|51/72直接方法数值分析例22nx2 =x + · · · + x1x = max|x1|, · · · , |xn|x1 = |x1| + · · · + |xn|一般地，xp = (|x1|p + · · · + |xn|p)1/p, p 1x = lim xpp51/72直接方法数值分析例：计算x = (1, 2, 3)T 的各种范数。解：x1 = 6, x = 3, x2

31、 = 14。比较长度：x = (4, 4, 4, 4), y = (0, 5, 5, 5)，z = (6, 0, 0, 0)52/72直接方法数值分析 1x16 288.666 456，1-yz156最大，-最长不一定。具体到一个最小。具体到一个，哪个53/72直接方法数值分析矩阵的定义：对任意 n 阶方阵 A，按一定的规则由一实数与之对应，记为 A。若A 满足1. A 0，且 A = 0 当且仅当 A = 0；(正定)2. A = | · A， 为任意实数；(齐次)54/72直接方法数值分析3. A + B A + B，对任意 A, B两个 n 阶方阵；(三角)4.AB A B（相

32、容性条件）则称 A 为矩阵 A 的。55/72直接方法数值分析一般用来估计误差。此时矩阵和向量会同时参加讨论，因此需要引进一种矩阵，与相容，即x Rn。Ax Ax 对任何阶方阵 A 都成立。为此，引进矩阵的算子和 n56/72直接方法数值分析定义：设 x Rn，A Rn×n，给出一种x，相应定义A = max Ax 。xx=0是 Rn×n可验证 A与 x 相容的范，也称从属数，称为 A 的算子。57/72直接方法数值分析设 A = (aij) 为 n 阶方阵。A1 = max Ax1 = maxn i=1|aij|x1=11jn向量的 1 范数的最大值称为矩阵的列范数。58

33、/72直接方法数值分析设 A = (aij) 为 n 阶方阵。A1 = max Ax1 = maxn i=1|aij|1jnx1=1的 1 的最大值称为矩阵的列。A2 = max Ax2 = 1，其中 1 是x2=1AT A 的最大特征值。又称为谱。58/72直接方法数值分析A =max Ax = maxnj=1|aij|1 inx=1为矩阵的行的 1 。的最大值称为矩阵的行59/72直接方法数值分析§5误差分析一、矩阵的条件数考虑线性方异，x 是方Ax = b，其中 A 非奇的精确解。由于 A 或 b 中的元素是测量得到或计算而来，因而有观测误差或舍入误差。因此，我们处理的实际矩阵

34、是A + A, b + b。60/72直接方法数值分析下面的影响。研究 A 或 b 的微小误差对解例：方x + x2= 21x + 1.00001x2 = 21解为 (x1, x2)T = (2, 0)T 。61/72直接方法数值分析而方x + x2 = 21x + 1.00001x2 = 2.000011解为 (x1, x2)T = (1, 1)T 。也可表示成 A(x + x) = (b + b)。这里b = (0, 0.00001)T , x = (1, 1)T 。62/72直接方法数值分析定义：如果矩阵 A 或常数项 b 的微小变化，引起方则称此方A 称为“Ax = b 解的巨大变化，为“”方，矩阵”矩阵（相对于方而，言）。否则称方为“良态”方A 称为“良态”矩阵。63/72直接方法数值分析定义：如果矩阵 A 或常数项 b 的微小变化，引起方则称此方A 称为“Ax = b 解的巨大变化，为“”方，矩阵”矩阵（相对于方而，言）。否则称方为“良态”方A 称为“良态”矩阵。矩阵的“”性质是矩阵本身的特性。63/72直接方法数值分析定义：设 A 为非奇异阵，称数cond(A)v = A1v Av (v = 1, 2或)为矩阵 A 的条件数。A1 A 刻划了解对原始数据变化的灵敏程度, 即刻划了方度。的“”程64/72直接方法数值分析常用的条件数，有(1)cond(A)