第二章解线性代数方程组的直接法11 「a11a12 b A= a21 a22 02 2 Lam 现在，我们给出用Gauss消去法求式(2-2)解的计算过程. 算法2.1用Gauss消去法求解线代数方程组(2-2). 我们先分别记矩阵A”=A,向量b”=b,它们的元素分别为 a=ag(i,j=1,2,,n), 6=b:(i=1,2,…,n) 1)消元过程 第一步：若a午0，可对i=2,3,…,n进行如下计算，用m1=一a/a乘方程 式(2-2)两边的第一行加到第i行中去，得到 [a a an …a7[x17 647 0 a经 a … a b%2 0 a a … b52 (2-3) 0 a … xn 82) 这里 ag2=a十mm·a， (i,j=2,3,…,n), b2=6+m4·b4”, (i=2,3,…,n) 第二步：若a经卡0，可对i=3,…,n进行如下计算，用m2=一a/a2乘方程组 (2-3)两边的第二行加到第i行去，得到 fa g … 0 a … … bg2 0 0 a g b 、0 0 … aaxnJ b3) 这里
第二章解线性代数方程组的直接法 11 α11 α12 ••• a 1" Xl bl a 22 '" α2" b 2 , x= , b= • • • • • • • • • • • • • • • • • • a"l a ,,2 ... α"" X n b n 现在，我们给出用 s s 求式 算法 1用 s消去法求解线代数方程组 我们先分别记矩阵 (1 = A (1 =b 它们 41)=av(i ，j=1 ，2 bjl>=bz <i=l 2，…，的 1)消元过程 第一步:若 0，可对 ，…， η进行如下计算，用 =-ajJ)/aji} 方程 )两边的第一行加到第i行中去，得到 (1) (1) (1) (1) bjl) all a 12 au ... a ln Xl O (2) (2) (2) bz<2> azz a 23 ... a 2n X 2 O (2) (2) (2) X 3 b~2) I (2-3) a :i2 a 33 ... a 3, ‘ • • • • • • • • • • • • • • • • • • • • • O (2) (2) α~) J LXnJ Lb;2> a n2 a n3 ... 这里 α;Z 〉=41) 十nzz1·ai;) ，(i ，j=2 ，3 bj2 〉=bjl 十mzl-bjlv (i=2 ,3 ,… , n ) . 第二步 z若 进行 (2-3) (1) (1) (l) l b~l) all α12 .., ... GIn O (2) (2) b;2) a 22 •• • ... a Ztl X2 2 O O (3) (3) X 3 b;3) a 33 ... a 3n 3 • • • • • • • • • • • • • • • • • • • • • O O ( 3) (3) 二[" b~3) a 1l3 ... a"" n 这里
12第I部分数值分析 ag=ag2+m2·a号，(i,j=3,…,n) 69=62+ma·b2,(i=3,…,n). 依次下去，…，一直做到第n一1，即 Ta a … ati a 6 0 a a21 a 2 … (2-4) a”-1 a Cx-1 b” 0 0 2)回代过程 若a侧卡0，我们可以从式(2-4)逐次回代计算出方程式(2-2)的解 =bm la z,=(-,Ao0x,/,=m-1,…2,1D. 如果在消元过程的第一步中，a=0,由于矩阵A非奇，所以在A的第一列中至 少有一个元素牛0，于是可以通过对方程两边进行第一行与第行的行交换，将 a:调到方程式(21)位置，然后消元计算.同理，对以后各步都可以进行这样的行交 换，以使a经，g,…,“-均不为零，最后，由A的非奇异性得到a亦不为零.■ 纵观算法2.1，我们得到： 定理2.1如果方程组(2-2)的系数矩阵A为非奇，则它可以通过Gauss消去法 (即：算法2.1)进行求解 下面，我们分析在消元过程中不需进行行交换的Guss消去法的乘除运算工作 量： 1)消元过程的计算是，在第k步的消元中，对矩阵消元需作(n一)次除法运算 (n一k)2次乘法运算，对右端需作（一）次乘法运算，于是，总的消元过程乘除法运 算量为： 2(m-)+n-2+(m-)=号r+z0-吾m 2)回代过程的计算是，计算每个x:需作(n一)次乘运算，于是总的回代过程乘 除法运算量为 (m-)=7n(n+1)
12 分 数值分析 (3) _ ..(2) I (2) ""==GZJ • a2j- , (i ,j = 3 ,… ,n ) by)=bj2} • b;2) , (i = 3 ,… ,n ) . 依次下去，……，一直做到第 ，即 (I) (1) (1) (1) all a r bi!) l2 •• • 1， 11 a l n XI O (2) (2) (2 ) X 2 b~2) α22 ... a 2.11一1 2 n 2 • • • • • • • • • • • • • • (2-4) • • • • • • • • • (n (n-I) b{n-1> • • an 1， l a n- I •n X n- 1 • • n-I O O (n) X .., ... n b~n) nn " 2) 代过程 我们 可 方程式 X n =b~n) n zb=(bf>-EGf)Zz)/ar , s=k+1 (k=n-l ,… , 2 , 1) . 如果在消元过程的第一步中， 0，由于矩阵 A非奇，所以在 (I)的第一列中至 少有一个元素气， 对方 边进行 第il I调到方程式 )位置，然后消元计算.同理，对以后各步都可以进行这样的行交 换，以使 2， }，… 1均不为零.最后，由 A的非奇异性得到心)亦不为零 • 纵观算法 我们 定理 果方 的 系 s s (即:算法 1)进行求解. • 下面，我们分析在消元过程中不需进行行交换的 运 算 量: 1)消元过程的计算是，在第 法运 Cn-k)2 次乘法运算 对右 乘法 的 消 过程 法运 算量为: n 5-6 n 1-2 n -TI"2 l-3 n 'R n , R + 2) 代过 算每 次乘 总 的 代 过程乘 除法运算量为 2;(n-h)=÷n( 1)
第二章解线性代数方程组的直接法13 因此，用不需进行行交换的Guss消去法计算线代数方程组(2-2)所需的总的乘除 运算量次数为 1 1 如果在消元过程中考虑进行行交换，则第k个消元步至多需要(n一k)次的非零 判断以及(n一)次两个元素的对换.于是，总的非零判断次数最多为 (m-)=nn2) =1 总的两个元素的对换次数最多为 m-=a-边 2 另外，如果在算法2.1的消元过程中，对每一个当前消元步，比如第步，都进行 这样的判断，必要时，还进行行交换，以使得|a|≥a|,从而1m|≤1，(i=十1， ·,).这样，在消元过程和回代过程中，就避免了绝对值较小的数作为除数的情况， 于是，计算过程稳定.我们称经这种修改后的算法2.1为列选主元Guss消去计算线 代数方程组的数值计算例子， 例2.1试用Gauss消去法计算线代数方程组 111117「x] 「57 21111 6 32111 8 43211 12 54321xJ 15 解首先进行消元过程，对方程组两边第1行分别乘（一2）倍加到第2行、乘 (-3)倍加到第3行、乘（一4）倍加到第4行、乘（一5）倍加到第5行，得到 11 1 0 -1 4 0 -1 -2 -2 -2 1 0-1-2-3 -3 x L0-1-2-3 一4」x5」 -10 对方程组两边第2行乘（一1）倍分别加到第3行、第4行、第5行，得到
第二章解线性代数方程组的直接法 1 3 因此，用不需进行行交换的 s消去法计算线代数方程组 )所需的总的乘除 运算量次数为 ，1 25 ，1"" 1 , , 2 3 +一旷一 --;;- n( 1) →n' 十n· --;:;- n. ,. I 2 ,. 6 .., 2 如果在消元过程中考虑进行行交换，则第 h个消元步至多需要 η一的次的非零 判断以及 )次两个元素的对换.于是，总的非零判断次数最多为 I) 21(n = 一 总的两个元素的对换次数最多为 rl/1 21(η 另外，如果在算法 每一 第h 进行 这样的判断，必要时，还进行行交换，以使得 ai:) (i = k+ l , … ,n ) 过程 代过程 就避 值较小 数作 为 除 于是，计算过程稳定.我们称经这种修改后的算法 元Gauss 代数方程组的数值计算例子. 1试用 s消去法计算线代数方程组 1 1 1 1 1 Xl 5 ' 2 1 1 1 1 6 3 2 1 1 1 I IX 3 8 4 3 2 l l X 1 11 5 4 3 2 1 X s 15 解首先进行消元过程，对方程组两边第 1行分别乘(- 2) 第2 (-3) 到第3 第4 …5) 第5 1 1 1 1 l Xl 5 O X 2 O -2 X 3 O -1 -3 -3 X 1 -9 O -2 -4 X s 对方程组两边第 2行乘(-1)倍分别加到第 3行、第 4行、第 5行，得到
14第I部分数值分析 1 1 11 11「x17 「51 0 -1 -1-1-1x2 -4 0 0 -1 -1 -1z3 -3 00 -1-2 -21x -5 L00 -1-2 一3x5」 对方程组两边第3行乘（一1）倍分别加到第4行、第5行，得到 1 1 1 17x7 5 0 -1 -1 -1 -1x2 -4 0 0 -1 -3 0 0 0 -1 -1 工4 2 0 0 0 -1 -2x -3 对方程组两边第4行乘（一1）倍加到第5行，得到 1 1 1 11「x1 「57 0-1-1-1-1x2 -4 0 -1 -1 1/ -3 0 0 0 -1 -1x -2 00 0 0 -1zJ L-1 然后，回代计算出 x5=1,x4=1,x3=1,x2=1,x1=1. I 例2.2采用四位有效数字，分别用不选主元Gauss消去法和列选主元Gauss 消去法计算线代数方程组 「0.003000 59.147「x7=「59.171 (2-5) L5.291 -6.130JLx2」L46.78」 (此方程组的精确解为：x1=10.00,x2=1.000). 解首先用不选主元Gauss消去法计算式(2-5) 消元计算（考虑四位有效数字）： 5.291 m1=-0.0030000=-1763.66≈-1764， 对方程组消元，于是得到
14 第I 值分 1 1 1 1 1 l IXl I r 5 O -1 X z I 1-4 O O X 3 1=1-3 O O -1 -2 -2 X 1 I |一 O O -3 I 1-6 对方程组两边第3行乘(一1)倍分别加到第4行、第 5行，得到 1 1 1 1 1 Xl 5 O -1 -1 -4 O O -1 X 3 O O O X 4 I 1-2 O O O -1 -2 I 1-3 对方程组两边第4行乘(-1)倍加到第5行，得到 1 l 1 1 1 Xl 5 O -1 X z O O -1 X 3 O O O X 1 I 1-2 O O O O X 5 I |一 然后，回代计算出 X s =1 1 , X 3 = 1 , X 2 = 1, Xl = 1. • tl 2. 别 用 不 元Gauss 去 法 元Gauss 消去法计算线代数方程组 0.003000 5.291 31;。 ] 59.17 46. 78 , (2-5) (此方程组的精确解为 0 0 = 1. 000). 解首先用不选主元 s消去法计算式 位有 : 5. 291 =一 7 6 3 6 6 7 6 ZI· 0.0030000 对方程组消元，于是得到
第二章解线性代数方程组的直接法15 Γ0.003000 59.147x17_「59.171 0 -104300JLx2」L-104400 回代计算： x2=1.001,x1=-10.00. 由此看出，在计算x2时产生的误差0.001，导致了求解x1时产生更大的误差，即误 差扩大了20000倍. 下面采用列选主元Gauss消去法计算式(2-5)，交换方程组(2-5)的第1行与第 2行，得 f5.291 -6.1307「x7「46.78 L0.0030000 59.17JLx2J L59.17 消元计算（考虑四位有效数字）： 7m1=-0-030000=-0.0005670. 5.291 方程组消元后，得 「5.291-6.1307fx11「46.781 L o 59.14JFL59,14 回代计算： x2=1.000,x1=10.00 与不选主元的Gauss消去法相比，显然，用列选主元Gauss消去法可以得到好 的结果. §2.2矩阵的三角分解 在本节中，我们将讨论基于Guss消去法思想的另一种求解线代数方程组的直 接法—矩阵的三角分解 回顾§2.1的算法2.1，当消元过程不需作行交换以调整对角线上非零元时，算 法2.1的消元过程与下面等价： 第1步等价于a午0，并用矩阵
第二章解线性代数方程组的直接法 1 5 OYooo-24。 ] 59.17 -104400 回代计算: 1. x 1 = - 10. 00. 由此看出，在计算 产生 001 导 致 求 解 更 大 差扩大了 2 0 0 0 0 下面采用列选主元 s消去法计算式 ，交换方程组 )的第 1行与第 5. 291 0.0030000 ;:1:t 46. 78 59.17 消元计算(考虑四位有效数字): nu .• -- AU nUnunuFhdPO nu- ;--nu-QU nu--inum 方程组消元后，得 5.291 O 1:1; 46. 78 59. 14 回代计算: X 2 = 1. 000 1:: = 10.00. • 与不选主元的 s消去法相比，显然，用列选主元 s消去法可以得到好 的结果. § 2.2 在本节中，我们将讨论基于 s消去法思想的另一种求解线代数方程组的直 接法一一矩阵的三角分解. 回顾§ 2. 法2. 1，当消元过程不需作行交换以调整对角线上非零元时，算 下 面等 1步等价于 ; : 〉 0，并用矩阵