中国矿业大学：《数值计算方法》课程教学课件（讲稿）第3章 线性方程组解法 Direct Method for Solving Linear Systems

中国矿亚大整CHINA UNIVERSITYOFMININGANDTECHNOLOGYCH3线性方程组解法/*Direct Method forSolving Linear Systems */$1消去法$2矩阵分解法$3方程组的性态和条件数$4迭代法

CHINA UNIVERSITY OF MINING AND TECHNOLOGY CH3 线性方程组解法 /* Direct Method for Solving Linear Systems */ §1 消去法 §2 矩阵分解法 §3 方程组的性态和条件数 §4 迭代法

中国矿亚大医CHINAUNIVERSITY OFMININGANDTECHNOLOGY81消去法一、高斯顺序消去法/*GaussianElimination*2x,+x2 +x,=7口例题 求解34x+5x,-x,=11-2x2 +x,=0X解 Stepl：消元23+A=(A,b)=-2r3x25-3r3-0.5r0-2710X, =-6/(-2)= 3X2=(-3+3×3)/3=2Step2:回代人X,=(7-1×3-1×2)/2=1

CHINA UNIVERSITY OF MINING AND TECHNOLOGY §1 消去法 解 1 23 1 23 1 23 7 4 5 11 2 0 x xx x xx x xx ⎧ 2 + + = ⎪⎨ + − = ⎪ − + = ⎩ Step1:消元 21 1 7 ( , ) 4 5 1 11 1 21 0 A Ab ⎡ ⎤ ⎢ ⎥ == − ⎢ ⎥ ⎢ − ⎥ ⎣ ⎦ 21 1 7 03 3 3 00 2 6 ⎡ ⎤ ⎢ ⎥ − − ⎢ ⎥ ⎢ − − ⎥ ⎣ ⎦ 3 2 53 2 r r + ⎯⎯⎯⎯× → Step2:回代 ⎧⎪⎨⎪⎩ 5 1 7 22 2 21 1 7 03 3 3 0 ⎡ ⎤ ⎢ ⎥ − − ⎢ ⎥ ⎢ − − ⎥ ⎣ ⎦ 2 1 3 1 20.5 r r r r − ⎯⎯⎯→ − ‡ 例题 求解 x3 = − −= 6/( 2) 3 x2 = ( 3 3 3)/ 3 2 −+ × = x1 = ( )/ 71312 2 1 −×−× = 一、高斯顺序消去法 /* Gaussian Elimination */

中国矿亚大医CHINA UNIVERSITY OFMININGAND TECHNOLOGY1.计算机上所用的公式ax, +ax, +...+ainx,=ain+ia2x, +a22x, +...+a2n, =a2,n+1求解方程：am,+an,+...+amX,=ann+1下面研究它的计算规律：

CHINA UNIVERSITY OF MINING AND TECHNOLOGY nn n nn n n n nn n n n ax ax ax a ax ax ax a ax ax ax a + + + ⎧ + ++ = ⎪ ⎪ + ++ = ⎨ ⎪ ⎪ + ++ = ⎩ 11 1 12 2 1 1, 1 21 1 22 2 2 2, 1 11 22 , 1 " " """""""""""" " 求解方程： 1.计算机上所用的公式 下面研究它的计算规律：

中国矿亚大鉴CHINAUNIVERSITYOF MININGANDTECHNOLOGYal+aa.faalo...doaoao(0)a0a.0a2,n+l..............aafaaC1)消元记4(=at0)aa.(0)(0)(0)(0)(0)ak+1,2ak+1,kak+1,+1ak+1,#ak+l,n+1...............alk+a(0)aaatoan,n+1假设0,令=/0Stepl:(i=2, ... n)aaao(0)(0)ai,k+1ai,n+1.....agaadlada0....lin'A(0).............allaaalktadalhat1i=2,...n...(1)(1)(1)(1)(1)ak+1,2ak+1nak+1,kak+1,k+1ak+1,n+1.............a0aaaltaaal)0n2n,n+i

CHINA UNIVERSITY OF MINING AND TECHNOLOGY Step 1： 0 0 1 1 11 2 i i laa i n = = () () 令 / ( , ., ) i n = 2, ., i i r lr − 1 1 a ≠ (0) 11 假设 ，0 (0) (0) (0) (0) (0) (0) 11 12 1 1, 1 1 1, 1 (0) (0) (0) (0) (0) (0) 21 22 2 2, 1 2 2, 1 (0) (0) (0) (0) (0) (0) (0) 1 2 ,1 ,1 (0) (0) (0) 1,1 1,2 1, . . . . . . . . . . . . . kk nn kk nn k k kk k k kn k n k k kk k aa aa aa aa aa aa A aa aa aa aa aa + + + + + + ++ + + = (0) (0) (0) 1, 1 1, 1, 1 (0) (0) (0) (0) (0) (0) 1 2 ,1 ,1 . . . . . . . . . k kn kn n n nk n k nn n n a a aa aa aa + + ++ + + ⎛ ⎞ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ kk nn kk nn k kk k k kn k n k kk kk kn k aa a a a a a aa aa a aa aa a aa aa + + + + + + + + ++ + + (0) (0) (0) (0) (0) (0) 11 12 1 1, (1) (1) (1) (1) (1) (1) (1) (1) (1) (1) (1) ( 1 1 1, 1 22 2 2, 1 2 2, 1 2 , 1) (1) (1) 1 ,1 1,2 1, 1, 1 1, . . . . . . . . . . . . . 0 0 . 0 n n nk n k nn n n a aa aa + + + ⎛ ⎞ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ (1) (1) (1) ( 1, 1 2 ,1 ,1 1) (1) (1) . . . . . 0 . . . A(0) 1)消元 记

a0aloal+ala中国矿亚大鉴CHINA UNIVEaadaadat0.....R-1(k-1)(k1)(k-1)A(k-l)假设第k-1步消元后1ak,n+1ak.k+11kn(k-l)(k-1)(k-1)ak+1,kak+1,k+1ak+1,nak+l,n+1.........(k-1)(k1)(k-1)(k-1)1aan,n+1Ian,k+1nknn(k-1(k-1)Step k： 若ak-" 0, 计算lx =ak(i=k+l,...,n)akk以及a(k)=a(t-1) -liak(i=k+l.., n; j=k+l,....n+1)(0)(0)1o(0)(0)aodikai.k+1dinai.n+1(agha.ada..(1)ad122............(k-1)at!ikK(k-1)(k-1)ak.k+lkkdknA(K)(k)(k)(k)-i=k+l,.nak+1,n+1ak+1,k+1ak+1.n...(k)(k)(k)a11n,k+1nnn,n+1

CHINA UNIVERSITY OF MINING AND TECHNOLOGY 假设第 步消元后 k − 1 kk nn kk nn k kk kk kk k k kn k n k k kk kk k aa a a a a a aa aa A aa aa aa a + + + + − −− −− + + − − + ++ + = (0) (0) (0) (0) (0) (0) 11 12 1 1, 1 1 1, 1 (1) (1) (1) (1) (1) 22 2 2, 1 2 2, 1 ( 1) ( 1) ( 1) ( 1) ( 1) ,1 ,1 ( 1) ( 1) 1, 1, 1 . . . . . . . . . . 0 0 0 0 0 . . . . . . . . . k k n kn kk kk nk n k nn n n a aa aa − − + + −− −− + + ⎛ ⎞ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ ( 1) ( 1) 1, 1, 1 ( 1) ( 1) ( 1) ( 1) ,1 ,1 . . . 0 0 . . . . . . . . Step k ： ik n = + 1, ., i ik k r lr − k kk a − ≠ ( 1) 若 ，0 k k ik ik kk la a − − = ( 1) ( 1) 计算 / ( 1, ., ) ik n = + kk k ij ij ik kj a a la − − = − 以及 ( ) ( 1) ( 1) ( 1 . ; 1,., 1) ik n = + =+ + , , j k n k A( 1) − ( ) k A kk nn kk nn kk kk kk k k kn k n k kn k k k n k k aa a a a a a aa aa aa aa a aa + + + + −− −− + + ++ + ++ (0) (0) (0) (0) (0) (0) 11 12 1 1, 1 1 1, 1 (1) (1) (1) (1) (1) 22 2 2, 1 2 2, 1 ( 1) ( 1) ( 1) ( 1) ,1 ,1 1, 1 1, 1, 1 () () ( . . . . . . . . . . . 0 0 0 00 0 . . . . . n k nn n n k kk a aa + + ⎛ ⎞ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ , 1 ) () () () , 1 . . . . . . . . . 0 0 . 0 . Δ

Stepn-l：消元结束，A化为上三角矩阵aif(0)aiatalftadil()adlaad...(k-1)(k-1),(k-1)(k-1)ak.k+1(knak,n+1kk(k)(k)(k)ak+1,k+1ak+,nak+1,n+1a(n-1)(n-1)n,n+1k=1,2,..,n-l, a ±0i=k+l,...n在实际编程中为了节省内存ai不引入新变量akkj=k+1,...,n+1消元过程记为：a-aia=a

CHINA UNIVERSITY OF MINING AND TECHNOLOGY Step n-1：消元结束， A化为上三角矩阵 kk nn kk nn n kk kk kk k k kn k n k k kk kn kn aa a a a a a aa aa A aa aa a aa + + + + − −− −− + + ++ + + = (0) (0) (0) (0) (0) (0) 11 12 1 1, 1 1 1, 1 (1) (1) (1) (1) (1) 22 2 2, 1 2 2, 1 ( 1) ( 1) ( 1) ( 1) ( 1) ,1 ,1 () () 1, 1 1, 1, . . . . . . . . . . . . 0 0 . 0 . . 0 0 . . . 0 k n n nn n n a a + − − + ⎛ ⎞ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ ( ) 1 ( 1) ( 1) , 1 . . . . . . . 0 . . . 0 0 . 0 12 1 0 kk k na = , ,., − ≠ ， ik n = + 1,., ik ik ik kk a l a a = ⇒ jk n = + + 1,., 1 ij ik kj ij a aa a − ⇒ 在实际编程中， 为了节省内存， 不引入新变量， 消元过程记为：

中国矿亚大医CHINA UNIVERSITY OF MININGAND TECHNOLOGY消元结束后，增广矩阵化为如下“形式”afaaaa...ad(1)a(1)aa2,k+1a2,n+1.....(k-1)(k-1),(k-1)(k-1)aknak,k+1ak,n+1akk(k)(k)(k)ak+1,k+1ak+1,nak+1,n+lK+1,k......-(n-1)aan!(mnn.k+12) 回代aaleroa(0X112(1)aad(1)X222azkA/a"-(n-1)n.n+1(k-1)[k-]](k-1)La(k-1) =(alla(k-1)Xk-1Zak,k+1RaknakkkjKA(k)(Kj=k+1Xkak+1,n+1.k+1,k+1(k =n-1,...,1)BXn

CHINA UNIVERSITY OF MINING AND TECHNOLOGY kk nn kk nn kk kk kk k k kn k n k kk k k k k k kk aa a a a a l a a l l a aa aa a l a l l a a + + + + + −− −− + + + + ++ + (0) (0) (0) (0) (0) (0) 11 12 1 1, 1 1 1, 1 (1) (1) (1) (1) (1) 22 2 2, 1 2 2, 1 ( 1) ( 1) ( 1) ( 1) ,1 ,1 ( ) 1, 21 1 2 1,1 1.2 1, 1 1 . . . . . . . . . . . . . . . n n nk n k k n kn n n k nn n n ll l l a a a + + + − − + ⎡ ⎤ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ () () , 1, 1 ( 1) ( 1) 12 1 , , 1 . . . . . . . . . . . n n n n n nn n k kk k k n kj j kk j k xa a x a a xa k n − − + − −− + = + ⎧ = ⎪ ⎪ ⎨ = − ⎪ ⎪ ⎩ = − ∑ ( 1) 1 , 1 ( 1) ( 1) ( 1) , 1 1 / ( )/ ( 1, ,1) " 1 (0) (0) (0) (0) (0) 11 12 1 1, 1 1 (1) (1) (1) (1) 22 2 2, 1 2 ( 1) ( 1) ( 1) , 1 ( ) 21 1 2 1,1 1.2 1, ( ) 1, 1 , 2 1 1 . . . . . . . . . . . . . . . . . . . . . . . . kk n kk n kk k kk k k kn k k kk kn k k k k kk k k l l l aa a a a a aa a a a x x l a l a a x l x + + −− − + + + + − + + + 1 ) 1 ( , 1 2 . . . . . . . . n n nk n k n n n n l l l l a x − + ⎡ ⎤ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ 消元结束后，增广矩阵化为如下“形式” 2) 回代

中国矿亚大墅CHINA UNIVERSITYOF MININGANDTECHNOLOGY口一个模拟计算机求解的例子11151X+x+x+=52-121X+2x2-x+4x4=-2解A=求解32-52-3-2x-3x,+2x,-5x4=332103x+x+2x+x=105115-2T-2A→2S-1/113-2/1-19-2/1-53-53/1-2-1-21-222025/25/2432S2

CHINA UNIVERSITY OF MINING AND TECHNOLOGY ‡ 一个模拟计算机求解的例子 1 23 4 1 23 4 12 3 4 12 34 5 2 42 23 2 5 3 3 2 10 x xx x x xx x xx x x xx xx ⎧ + ++ = ⎪ ⎪ + − + =− ⎨−− + − = ⎪ ⎪ ⎩ ++ += 求解 解 A = 1 1/ −2 1/ 3 1/ − 2 3 −1 1/ −2 1/ 1 –2 3 –7 1 1 1 1 5 –1 4 – 3 13 –2 –1 –2 –5 2 0 6 –5 4 –19 1 1 1 1 5 1 1 –2 3 –7 –5/2 4 –4 1 1 1 1 5 –2 –1 2 0 6 1 1 –2 3 –7 3 –2 A → → → → 11115 12142 23253 3 1 2 1 10 − − −− − 1 1 1 1 1 –2 –1 2 0 3 –5/2 4 –1 1 1 –2 3 2 3 –2

中国矿大医CHINA UNIVERSITY OFMININGAND TECHNOLOGY2.消去法成立的条件a(k-1) +0,(k =1,2.",n-1)kk.动态变化！n+n?次乘法3.计算量33

CHINA UNIVERSITY OF MINING AND TECHNOLOGY ( 1) 0, ( 1,2 , 1) k kk akn − ≠ = − " 3 2 3 3 n n + − n 次乘法 动态变化! 2. 消去法成立的条件 3. 计算量

中国矿基大医CHINA UNIVERSITYOF MINING ANDTECHNOLOGY1[10-9x +X2 =11.00000000100X例1单精度求解1-10-9精确解：X+x=2=0.99999999899.x =2-x高斯消去法10-A（I)（手算的结果）1-1×102-1x10°大数吃小数！10-9（计算机算的结果）2-10°-102-[10°x +x2 = 1X=0*：结果不可靠！[,=110°x, =10°原因：主元（a.）太小，方法不稳定！

CHINA UNIVERSITY OF MINING AND TECHNOLOGY 1 2 1 2 1 2 x x x x -9 10 例1 单精度求解 ⎧ + = ⎨ ⎩ + = 1 9 2 1 1 1.00000000100. 1 10 2 0.99999999899. x x x − ⎧ ⎪ = = ⎨ − ⎪ ⎩ =− = 精确解： )高斯消去法 ( ) A − ⎛ ⎞ = ⎜ ⎟ ⎝ ⎠ 9 0 10 1 1 112 ( ) A − − × ⎛ ⎟ − × ⎠ ⎞ ⎜ = ⎝ 9 1 9 9 1 1 10 2 1 10 10 1 1 0 (手算的结果) (计算机算的结果) 1 2 2 x x 1 x ⎧⎪ + = ⇒ ⎨ ⎪⎩ = -9 9 9 10 10 10 1 2 x 0 x ⎧ = ⇒ ⎨ ⎩ = 1 a 主元( )太小，方法不稳定！ 11 ⎯ r r ⎯⎯→ − 9 2 1 10 原因： ( ) A − ⎛ ⎞ − − ≈ = ⎜ ⎟ ⎝ ⎠ 9 9 1 9 10 10 10 1 1 0  8: 结果不可靠! 大数吃小数！