大连理工大学计算机科学计算第二章1.pdf

2.1.1 Gauss消去法与矩阵的消去法与矩阵的LU分解分解2.1.2 Gauss列主元消去法与带列主元的列主元消去法与带列主元的LU分解分解2.1.3 对称矩阵的对称矩阵的Cholesky分解分解2.1.4 三对角矩阵的三角分解三对角矩阵的三角分解2.1 矩阵的三角分解及其应用矩阵的三角分解及其应用2.1.5 条件数与方程组的性态条件数与方程组的性态2.1.6 矩阵的矩阵的QR分解分解矩阵分解矩阵分解是设计算法的主要技巧是设计算法的主要技巧对于一个给定的矩阵计算问题，我们研究的首要问题就是，如何根据给定的问题的特点，设计出求解这一问题的有效的计 算方法 设计算法的基本思想就是设法将一个一般的矩阵计算问题转化为一个或几个已与求解的特殊问题，而通常完成这一 转化任务的最主要的技巧就是对于一个给定的矩阵计算问题，我们研究的首要问题就是，如何根据给定的问题的特点，设计出求解这一问题的有效的计 算方法 设计算法的基本思想就是设法将一个一般的矩阵计算问题转化为一个或几个已与求解的特殊问题，而通常完成这一 转化任务的最主要的技巧就是矩阵分解矩阵分解，即将一个给定的矩阵 分解为几个特殊类型的矩阵的乘积。

即将一个给定的矩阵 分解为几个特殊类型的矩阵的乘积例如，如下的两个三角方程组例如，如下的两个三角方程组⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛=⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛nnnnnnbbbxxxllllllMMLOMM212121222111111111122111nnnnnnnnnnuuuycycuu uyc−−−−⎛⎞⎛⎞⎛⎞ ⎜⎟⎜⎟⎜⎟ ⎜⎟⎜⎟⎜⎟=⎜⎟⎜⎟⎜⎟ ⎜⎟⎜⎟⎜⎟⎝⎠⎝⎠⎝⎠LOMMMM是容易求解的 这样就将如何求解线性方程组的问题转化为 如何实现上述矩阵分解的问题这正是本章将要介绍的内容是容易求解的 这样就将如何求解线性方程组的问题转化为 如何实现上述矩阵分解的问题这正是本章将要介绍的内容和和Gauss消去法与矩阵的消去法与矩阵的LU分解分解2.1.1例1例1Gauss消去法求解线性方程组消去法求解线性方程组bAx =的一个实例的一个实例⎧ ⎪⎪⎨ ⎪ ⎪⎩(0) 123124xxxr++=(0) 1234243311xxxxr+++=(0) 12343879529xxxxr+++=(0) 12344679830xxxxr+++=第一步，消去第一步，消去)0( 2r)0( 3r、和、和)0( 4r中的中的1x，，即用即用)0( 2)0( 124rr+×⎟ ⎠⎞⎜⎝⎛−)0( 3)0( 128rr+×⎟⎠⎞⎜⎝⎛−、、和和)0( 4)0( 126rr+×⎟ ⎠⎞⎜⎝⎛−得得⎧ ⎪⎪⎨ ⎪ ⎪⎩(0) 123124xxxr++=(1) 23423xxxr++=(1) 234335513xxxr++=(1) 234446818xxxr++=第二步，消去和中的第二步，消去和中的，，即用和得即用和得⎧ ⎪⎪⎨ ⎪ ⎪⎩)1( 3r)1( 4r2x)1( 3)1( 213rr+×⎟⎠⎞⎜⎝⎛−)1( 4)1( 214rr+×⎟ ⎠⎞⎜⎝⎛−(0) 123124xxxr++=(1) 23423xxxr++=(2) 343224xxr+=(2) 3442418xxr+=第三步，消去第三步，消去中的中的，，即用 得即用 得)2( 4r3x)1( 4)2( 322rr+×⎟ ⎠⎞⎜⎝⎛−(3) 4422xr=⎧ ⎪⎪⎨ ⎪ ⎪⎩(0) 123124xxxr++=(1) 23423xxxr++=(2) 343224xxr+=242243=+ xx3432=++xxx42321=++xxx4x=21=224=x⇒⇒⇒⇒Gauss 消去法的实质是首先通过一系列的 初等行变换将增广矩阵化成上三角增广消去法的实质是首先通过一系列的 初等行变换将增广矩阵化成上三角增广)|(bA 然后通过回代求与然后通过回代求与 Ax=b 三角方程 组三角方程 组 Ux=c 的解。

的解上述为回代求解过程，得解:上述为回代求解过程，得解:()Tx1, 1, 1, 1=322 14x + × =3242x =−31x =322x =21 13x+ + =232x=−21x=12114x + +=1242x =−122x =11x =(| ) ,U c矩阵矩阵我们来观察我们来观察Gauss消去法求的解，消去法求的解，bAx =)|(bA化成上三角矩阵化成上三角矩阵)|(cU的过程，增广矩阵 如何通过矩阵的变换来实现的的过程，增广矩阵 如何通过矩阵的变换来实现的⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛=⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛=3029114,8976597813340112bA返回返回首先，注意首先，注意解：解：⎯⎯⎯⎯ →第一次消元⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛⎯⎯⎯→⎯64200422003111040112第二次消元⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛⎯⎯⎯→⎯22000422003111040112第三次消元= =)|(cU21104 433111879529 679830⎛⎞ ⎜⎟ ⎜⎟ ⎜⎟ ⎜⎟⎝⎠()|=A b2110401113 035513 046818⎛⎞ ⎜⎟ ⎜⎟ ⎜⎟ ⎜⎟⎝⎠=AL1⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛−−−89765978133401121314121⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛=8640553011100112()=ALL12⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛−−141311⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛8640553011100112⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛=4200220011100112三次消元过程写成矩阵的形式分别为：三次消元过程写成矩阵的形式分别为：()=ALLL123⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛−11111⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛4200220011100112U=⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛=2000220011100112kL =1,,1111kkn kll+⎛⎞ ⎜⎟ ⎜⎟ ⎜⎟ ⎜⎟−⎜⎟ ⎜⎟ ⎜⎟⎜⎟−⎝⎠OMO有令人惊奇，而平凡的性质：有令人惊奇，而平凡的性质：kLkL的逆恰好是本身的每一个对角线以下的元素都取的逆恰好是本身的每一个对角线以下的元素都取(1)(1)相反数；相反数；1,,11 11kkn kll+⎛⎞ ⎜⎟ ⎜⎟ ⎜⎟ ⎜⎟ ⎜⎟ ⎜⎟ ⎜⎟⎜⎟⎝⎠OMO=−1 kL即即注意单位下三角矩阵 （注意单位下三角矩阵 （Gauss变换变换））则则Lk k可写成可写成事实上，我们定义向量(事实上，我们定义向量(Gauss向量向量)：)：()T knkkkllLL100+=l(),00100T kLL=e=−=T kkkelIL。

0=kT kle其中其中()T kkIl e−()T kkIl e+TTTT kkkkkkkkIl el el e l e=−+−I=而而第第k+1个分量+1个分量第第k个分量个分量1,,11 11kkn kll+⎛⎞ ⎜⎟ ⎜⎟ ⎜⎟ ⎜⎟−⎜⎟ ⎜⎟ ⎜⎟⎜⎟−⎝⎠OMO()T kkIl e+=1111⎛⎞ ⎜⎟ ⎜⎟ ⎜⎟+⎜⎟ ⎜⎟ ⎜⎟ ⎜⎟⎜⎟⎝⎠OOkL的逆为：故的逆为：故=−1 kL1,,00 00kkn kll+⎛⎞ ⎜⎟ ⎜⎟ ⎜⎟ ⎜⎟ ⎜⎟ ⎜⎟ ⎜⎟⎜⎟⎝⎠OMO1,,1111kkn kll+⎛⎞ ⎜⎟ ⎜⎟ ⎜⎟= ⎜⎟ ⎜⎟ ⎜⎟ ⎜⎟⎜⎟⎝⎠OMO⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛−−−1314121 =1L=2L⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛−−141311 =3L⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛−11111⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛1314121 1 1−L= =1 2−L⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛141311====1 3−L⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛11111c则对于例题中的单位下三角阵而言，就有：则对于例题中的单位下三角阵而言，就有：cc()T kkIl e+()11T kkIle+++1111TTTT kkkkkkkkIl elel e le++++=++−11TT kkkkIl ele++=++1,2,2,1,,111 11 1kkkkkkn kn kl llll+++++⎛⎞ ⎜⎟ ⎜⎟ ⎜⎟ ⎜⎟ ⎜⎟ ⎜⎟ ⎜⎟ ⎜⎟ ⎜⎟⎝⎠OOMM1− kL=− +1 1kL=（（2）乘积矩阵）乘积矩阵L恰好是它们具有的非零对角线以下元素嵌入 到相应位置的单位下三角矩阵。

考虑矩阵乘积恰好是它们具有的非零对角线以下元素嵌入 到相应位置的单位下三角矩阵考虑矩阵乘积1− kL1 1− +kL当我们取所有这些矩阵乘积当我们取所有这些矩阵乘积L时，对角线下面的每处都有同样方便的性质：时，对角线下面的每处都有同样方便的性质：1 1−L1 2−L1 1− −nL=L=L⎟⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎜⎝⎛−1111121323121nnnnllllllLOOMM这样一来，例题中的计算过程可以表示为这样一来，例题中的计算过程可以表示为AU1L2L3L1 3−L1 3−L1 2−L1 2−L1 1−L1 1−L= ==L1 31 21 1−−−LLL令令⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛11111 1−L= =1 2−L⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛1111 1 3−L⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛1111=====L=−−−1 31 21 1LLL111113 4342则由性质（则由性质（2），可得出），可得出L的表达式，即的表达式，即即得到矩阵即得到矩阵A的一个的一个LU分解对于分解对于n阶方阵阶方阵A，，定义2.1定义2.1LU⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛1143134121⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛2221110112⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛8976597813340112A= =如果存在如果存在n阶单位下阶单位下三角矩阵三角矩阵LLUA=则称其为矩阵则称其为矩阵A的的LU分解， 也称分解， 也称 Doolittle分解分解。

从而有从而有和和n阶上三角矩阵阶上三角矩阵U， 使得， 使得⇔= BAX⎩⎨⎧ == YUXBLYc()BXLU=Doolittle方法求解线性方程组：方法求解线性方程组：其中其中A，，X，，B，，Y 均为矩阵均为矩阵⎟⎟⎟⎠⎞⎜⎜⎜⎝⎛−−−5150710623用用Gauss消去法求解如下方程组，并求消去法求解如下方程组，并求A的的LU分解⎟⎟⎟⎠⎞⎜⎜⎜⎝⎛321xxx⎟⎟⎟⎠⎞⎜⎜⎜⎝⎛ =674练习题练习题解：解：⎟⎟⎟⎠⎞⎜⎜⎜⎝⎛−−−6515707104623 ⎯→⎯消元326416102033 73801533⎛⎞ ⎜⎟− ⎜⎟−⎜⎟ ⎜⎟ ⎜⎟ ⎜⎟⎜⎟⎝⎠⎯→⎯消元3264 16102033 00115 115−⎛⎞ ⎜⎟−⎜⎟ ⎜⎟ ⎜⎟⎝⎠31x = 21,x = −10,x =从而求得方程组解从而求得方程组解：A= LU那么,得到那么,得到326 10203 00115−⎛⎞ ⎜⎟−⎜⎟=⎜⎟ ⎜⎟⎝⎠U110010103 5013⎛⎞ ⎜⎟ ⎜⎟ ⎜⎟=⎜⎟ ⎜⎟ ⎜⎟ ⎝⎠L 2100010 071⎛⎞ ⎜⎟=⎜⎟⎜⎟⎝⎠L326 10203 00115−⎛⎞ ⎜⎟−⎜⎟ ⎜⎟ ⎜⎟⎝⎠10010103 5713⎛⎞ ⎜⎟ ⎜⎟ ⎜⎟−⎜⎟ ⎜⎟ ⎜⎟−−⎜⎟⎝⎠326 1070 515−⎛⎞ ⎜⎟−=⎜⎟⎜⎟−⎝⎠已知已知-1-1 1210010103 5713⎛⎞ ⎜⎟ ⎜⎟ ⎜⎟= −⎜⎟ ⎜⎟ ⎜⎟−−⎝⎠L = L L从而从而⎟⎟⎟⎠⎞⎜⎜⎜⎝⎛−−−5150710623求求A的的LU分解，并用于求解如下方程组。

解：注意到分解，并用于求解如下方程组解：注意到⎟⎟⎟⎠⎞⎜⎜⎜⎝⎛321xxx⎟⎟⎟⎠⎞⎜⎜⎜⎝⎛ =674练习题练习题3261070 515−⎛⎞ ⎜⎟−⎜⎟⎜⎟−⎝⎠32610203 70153⎛⎞ ⎜⎟− ⎜⎟−⎜⎟=⎜⎟ ⎜⎟ ⎜⎟⎜⎟⎝⎠10010103 5013⎛⎞ ⎜⎟。